1 /*- 2 * Copyright (c) 1998, 1999 Semen Ustimenko (semenu@FreeBSD.org) 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 * $FreeBSD: src/sys/fs/hpfs/hpfs_alsubr.c,v 1.1 1999/12/09 19:09:58 semenu Exp $ 27 */ 28 29 #include <sys/param.h> 30 #include <sys/systm.h> 31 #include <sys/kernel.h> 32 #include <sys/proc.h> 33 #include <sys/time.h> 34 #include <sys/types.h> 35 #include <sys/stat.h> 36 #include <sys/vnode.h> 37 #include <sys/mount.h> 38 #include <sys/malloc.h> 39 #include <sys/buf.h> 40 41 #include <sys/buf2.h> 42 43 #include "hpfs.h" 44 #include "hpfs_subr.h" 45 46 #define AE_DONE 0 /* Nothing to change */ 47 #define AE_SPLIT 2 /* Split was done, ranp is valid */ 48 49 int hpfs_addextentr (struct hpfsmount *, lsn_t, alleaf_t *, 50 alnode_t *, u_long *); 51 int hpfs_allocalsec (struct hpfsmount *, lsn_t, struct buf **); 52 int hpfs_alblk2alsec (struct hpfsmount *, alblk_t *, alsec_t **, 53 struct buf **); 54 int hpfs_splitalsec (struct hpfsmount *, alsec_t *, alsec_t **, 55 struct buf **); 56 int hpfs_concatalsec (struct hpfsmount *, alsec_t *, alsec_t *, 57 alnode_t *); 58 59 /* 60 * Map file offset to disk offset. hpfsnode have to be locked. 61 */ 62 int 63 hpfs_hpbmap(struct hpfsnode *hp, daddr_t bn, daddr_t *bnp, int *runp) 64 { 65 struct buf *bp; 66 alblk_t * abp; 67 alleaf_t *alp; 68 alnode_t *anp; 69 int error, i; 70 71 dprintf(("hpfs_hpbmap(0x%x, 0x%x): ",hp->h_no, bn)); 72 73 bp = NULL; 74 abp = &hp->h_fn.fn_ab; 75 alp = (alleaf_t *)&hp->h_fn.fn_abd; 76 anp = (alnode_t *)&hp->h_fn.fn_abd; 77 78 dive: 79 if (abp->ab_flag & AB_NODES) { 80 for (i=0; i<abp->ab_busycnt; i++, anp++) { 81 dprintf(("[0x%x,0x%x] ",anp->an_nextoff,anp->an_lsn)); 82 if (bn < anp->an_nextoff) { 83 alsec_t *asp; 84 85 dprintf(("< found | ")); 86 87 if (bp) 88 brelse(bp); 89 error = bread(hp->h_devvp, 90 dbtodoff(anp->an_lsn), 91 DEV_BSIZE, &bp); 92 if (error) { 93 kprintf("hpfs_hpbmap: bread error\n"); 94 brelse(bp); 95 return (error); 96 } 97 98 asp = (alsec_t *) bp->b_data; 99 if (asp->as_magic != AS_MAGIC) { 100 brelse(bp); 101 kprintf("hpfs_hpbmap: " 102 "MAGIC DOESN'T MATCH"); 103 return (EINVAL); 104 } 105 106 abp = &asp->as_ab; 107 alp = (alleaf_t *)&asp->as_abd; 108 anp = (alnode_t *)&asp->as_abd; 109 110 goto dive; 111 } 112 } 113 } else { 114 for (i=0; i<abp->ab_busycnt; i++, alp++) { 115 dprintf(("[0x%x,0x%x,0x%x] ", 116 alp->al_off,alp->al_len,alp->al_lsn)); 117 118 if ((bn >= alp->al_off) && 119 (!alp->al_len || (bn < alp->al_off + alp->al_len))) { 120 dprintf(("found, ")); 121 122 *bnp = bn - alp->al_off + alp->al_lsn; 123 124 dprintf((" 0x%x ", *bnp)); 125 126 if (runp != NULL) { 127 if (alp->al_len) 128 *runp = alp->al_off - 1 + 129 alp->al_len - bn; 130 else 131 *runp = 3; /* XXX */ 132 133 dprintf((" 0x%x cont", *runp)); 134 } 135 136 if (bp) 137 brelse(bp); 138 139 dprintf(("\n")); 140 return (0); 141 } 142 } 143 } 144 145 dprintf(("END, notfound\n")); 146 if (bp) 147 brelse(bp); 148 149 dprintf(("hpfs_hpbmap: offset too big\n")); 150 151 return (EFBIG); 152 } 153 154 /* 155 * Find place and preinitialize AlSec structure 156 * AlBlk is initialized to contain AlLeafs. 157 */ 158 int 159 hpfs_allocalsec(struct hpfsmount *hpmp, lsn_t parlsn, struct buf **bpp) 160 { 161 alsec_t * asp; 162 struct buf * bp; 163 lsn_t lsn; 164 int error; 165 166 *bpp = NULL; 167 168 error = hpfs_bmfblookup(hpmp, &lsn); 169 if (error) { 170 kprintf("hpfs_allocalsec: CAN'T ALLOC SPACE FOR AlSec\n"); 171 return (error); 172 } 173 174 error = hpfs_bmmarkbusy(hpmp, lsn, 1); 175 if (error) 176 return (error); 177 178 bp = getblk(hpmp->hpm_devvp, dbtodoff(lsn), DEV_BSIZE, 0, 0); 179 clrbuf(bp); 180 181 /* Fill AlSec info */ 182 asp = (alsec_t *) bp->b_data; 183 asp->as_magic = AS_MAGIC; 184 asp->as_self = lsn; 185 asp->as_parent = parlsn; 186 187 /* Fill AlBlk */ 188 asp->as_ab.ab_flag = 0; 189 asp->as_ab.ab_busycnt = 0; 190 asp->as_ab.ab_freecnt = 0x28; 191 asp->as_ab.ab_freeoff = sizeof(alblk_t); 192 193 *bpp = bp; 194 195 return (0); 196 } 197 198 /* 199 * Split AlSec structure into new allocated: 200 * allocate new AlSec; then move second half of asp's entries in 201 * into it; set proper flags. 202 * 203 * IF AlSec CONTAINS AlNodes, THEN YOU ALMOST EVERYTIME HAVE TO 204 * FIX LAST AlNode in OLD AlSec (NEXTOFF TO BE 0xFFFFFFFF). 205 * TOGETHER WITH FIXING ALL CHILDREN'S AlSecs (THEY HAVE GOT NEW PARENT). 206 */ 207 int 208 hpfs_splitalsec(struct hpfsmount *hpmp, alsec_t *asp, alsec_t **naspp, 209 struct buf **nbpp) 210 { 211 alsec_t *nasp; 212 struct buf *nbp; 213 alblk_t *abp; 214 alblk_t *nabp; 215 int error, n1, n2, sz; 216 217 error = hpfs_allocalsec(hpmp, asp->as_parent, &nbp); 218 if (error) 219 return (error); 220 221 nasp = (alsec_t *)nbp->b_data; 222 nabp = &nasp->as_ab; 223 abp = &asp->as_ab; 224 225 n1 = (abp->ab_busycnt + 1) / 2; 226 n2 = (abp->ab_busycnt - n1); 227 sz = (abp->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t); 228 229 bcopy((caddr_t)abp + sizeof(alblk_t) + n1 * sz, 230 (caddr_t)nabp + sizeof(alblk_t), n2 * sz); 231 232 nabp->ab_flag = abp->ab_flag; 233 nabp->ab_busycnt = n2; 234 nabp->ab_freecnt = (0x1e0 / sz - n2); 235 nabp->ab_freeoff += n2 * sz; 236 237 abp->ab_busycnt -= n1; 238 abp->ab_freecnt += n1; 239 abp->ab_freeoff -= n1 * sz; 240 241 *naspp = nasp; 242 *nbpp = nbp; 243 244 return (0); 245 } 246 247 /* 248 * Try to concatenate two AlSec's 249 * 250 * Moves all entries from AlSec corresponding (as1p, aanp[1]) into 251 * corresponding aanp[0] one. If not enough space, then return ENOSPC. 252 * 253 * WARNING! YOU HAVE TO FIX aanp VALUES YOURSELF LATER: 254 * aanp[0].an_nextoff = aanp[1].an_nextoff; 255 */ 256 int 257 hpfs_concatalsec(struct hpfsmount *hpmp, alsec_t *as0p, alsec_t *as1p, 258 alnode_t *aanp) 259 { 260 alblk_t *ab0p; 261 alblk_t *ab1p; 262 int sz; 263 264 dprintf(("hpfs_concatalsec: AlSecs at 0x%x and 0x%x \n", 265 as0p->as_self,as1p->as_self)); 266 267 ab0p = &as0p->as_ab; 268 ab1p = &as1p->as_ab; 269 sz = (ab0p->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t); 270 271 if (ab0p->ab_freecnt > ab1p->ab_busycnt) { 272 /* 273 * Concatenate AlSecs 274 */ 275 if (ab0p->ab_flag & AB_NODES) 276 AB_LASTANP(ab0p)->an_nextoff = aanp[0].an_nextoff; 277 278 bcopy (AB_ALNODE(ab1p), AB_FREEANP(ab0p), 279 ab1p->ab_busycnt * sz); 280 281 AB_ADDNREC(ab0p, sz, ab1p->ab_busycnt); 282 283 return (0); 284 } else { 285 /* Not enough space to concatenate */ 286 return (ENOSPC); 287 } 288 } 289 290 /* 291 * Transform AlBlk structure into new allocated 292 * AlSec. 293 * 294 * DOESN'T SET AlSec'S PARENT LSN. 295 */ 296 int 297 hpfs_alblk2alsec(struct hpfsmount *hpmp, alblk_t *abp, alsec_t **naspp, 298 struct buf **nbpp) 299 { 300 alsec_t *nasp; 301 alblk_t *nabp; 302 struct buf *nbp; 303 int error, sz; 304 305 error = hpfs_allocalsec(hpmp, 0, &nbp); 306 if (error) 307 return (error); 308 309 nasp = (alsec_t *)nbp->b_data; 310 nabp = &nasp->as_ab; 311 312 sz = (abp->ab_flag & AB_NODES) ? sizeof(alnode_t) : sizeof(alleaf_t); 313 314 bcopy (abp, nabp, sizeof(alblk_t) + sz * abp->ab_busycnt); 315 316 nabp->ab_freecnt = 0x1e0 / sz - nabp->ab_busycnt; 317 318 *naspp = nasp; 319 *nbpp = nbp; 320 321 return (0); 322 } 323 324 /* 325 * Allocate len blocks and concatenate them to file. 326 * If we hadn't found contignous run of len blocks, concatenate 327 * as much as we can, and return. 328 * 329 */ 330 int 331 hpfs_addextent(struct hpfsmount *hpmp, struct hpfsnode *hp, u_long len) 332 { 333 alblk_t *rabp; 334 alnode_t ranp[2]; 335 alleaf_t al; 336 int error; 337 u_long pf; 338 339 /* 340 * We don't know for now start lsn of block 341 */ 342 al.al_lsn = ~0; 343 al.al_len = len; 344 al.al_off = (hp->h_fn.fn_size + DEV_BSIZE - 1) >> DEV_BSHIFT; 345 346 rabp = &hp->h_fn.fn_ab; 347 348 /* Init AlBlk if this is first extent */ 349 if (al.al_off == 0) { 350 lsn_t nlsn; 351 u_long nlen; 352 353 dprintf(("hpfs_addextent: init AlBlk in root\n")); 354 355 rabp->ab_busycnt = 0; 356 rabp->ab_freecnt = 0x8; 357 rabp->ab_freeoff = sizeof(alblk_t); 358 rabp->ab_flag = 0; 359 360 error = hpfs_bmlookup (hpmp, 0, hp->h_no + 1, al.al_len, &nlsn, &nlen); 361 if (error) 362 return (error); 363 364 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen); 365 if (error) 366 return (error); 367 368 dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn, nlen)); 369 370 AL_SET(AB_FREEALP(rabp), al.al_off, nlen, nlsn); 371 AB_ADDAL(rabp); 372 373 al.al_off += nlen; 374 al.al_len -= nlen; 375 } 376 377 retry: 378 dprintf(("hpfs_addextent: AlBlk: [0x%x, 0x%x, 0x%x] need: 0x%x\n", 379 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag, al.al_len)); 380 381 while ((al.al_len) && (rabp->ab_freecnt > 0)) { 382 if (rabp->ab_flag & AB_NODES) { 383 alnode_t *anp; 384 /* 385 * This is level containing AlNodes, so try to 386 * insert recursively into last entry. 387 */ 388 anp = AB_LASTANP(rabp); 389 dprintf(("hpfs_addextent: AlNode: [0x%x,0x%x] \n", 390 anp->an_nextoff,anp->an_lsn)); 391 392 /* 393 * Try to insert... 394 */ 395 error = hpfs_addextentr (hpmp, anp->an_lsn, &al, ranp, &pf); 396 if (error) { 397 kprintf("hpfs_addextent: FAILED %d\n",error); 398 return (error); 399 } 400 401 switch (pf) { 402 case AE_SPLIT: 403 dprintf(("hpfs_addextent: successful (split)\n")); 404 /* 405 * Then hpfs_addextentr has split tree below, now 406 * we need to fix this level. Particulary: 407 * fix last AlNode and add another one. 408 */ 409 410 bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2); 411 AB_ADDAN(rabp); 412 break; 413 414 default: 415 case AE_DONE: 416 dprintf(("hpfs_addextent: successful\n")); 417 break; 418 } 419 } else { 420 alleaf_t *alp; 421 422 alp = AB_LASTALP(rabp); 423 dprintf(("hpfs_addextent: AlLeaf: [0x%x,0x%x,0x%x] \n", 424 alp->al_off,alp->al_len,alp->al_lsn)); 425 426 /* Check if we trying to add in right place */ 427 if (alp->al_off + alp->al_len == al.al_off) { 428 lsn_t nlsn; 429 u_long nlen; 430 431 /* 432 * Search bitmap for block begining from 433 * alp->al_lsn + alp->al_len and long of ralp->al_len 434 */ 435 error = hpfs_bmlookup (hpmp, 0, 436 alp->al_lsn + alp->al_len, al.al_len, &nlsn, &nlen); 437 if (error) 438 return (error); 439 440 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen); 441 if (error) 442 return (error); 443 444 dprintf(("hpfs_addextent: new: 0x%x 0x%lx, ", nlsn, nlen)); 445 446 if (alp->al_lsn + alp->al_len == nlsn) { 447 dprintf(("extended existed leaf\n")); 448 449 alp->al_len += nlen; 450 } else { 451 dprintf(("created new leaf\n")); 452 AL_SET(AB_FREEALP(rabp), al.al_off, nlen, nlsn); 453 AB_ADDAL(rabp); 454 } 455 al.al_off += nlen; 456 al.al_len -= nlen; 457 } else { 458 kprintf("hpfs_addextent: INTERNAL INCONSISTENCE\n"); 459 return (EINVAL); 460 } 461 } 462 } 463 464 /* 465 * Move AlBlk contain to new AlSec (it will fit more 466 * entries) if overflowed (no more free entries). 467 */ 468 if (rabp->ab_freecnt <= 0) { 469 struct buf *nbp; 470 alsec_t * nrasp; 471 472 dprintf(("hpfs_addextent: overflow, convt\n")); 473 474 /* 475 * Convert AlBlk to new AlSec, it will set 476 * AB_FNPARENT also. 477 */ 478 rabp->ab_flag |= AB_FNPARENT; 479 error = hpfs_alblk2alsec (hpmp, rabp, &nrasp, &nbp); 480 if (error) { 481 kprintf("hpfs_addextent: CAN'T CONVT\n"); 482 return (error); 483 } 484 nrasp->as_parent = hp->h_no; 485 486 /* 487 * Scan all childrens (if exist), set new parent and 488 * clean their AB_FNPARENT flag. 489 */ 490 if (rabp->ab_flag & AB_NODES) { 491 int i; 492 alsec_t * asp; 493 alnode_t * anp; 494 struct buf * bp; 495 496 anp = AB_ALNODE(rabp); 497 for (i=0; i<rabp->ab_busycnt; i++) { 498 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp); 499 if (error) 500 return (error); 501 502 asp = (alsec_t *)bp->b_data; 503 asp->as_ab.ab_flag &= ~AB_FNPARENT; 504 asp->as_parent = nrasp->as_self; 505 506 bdwrite(bp); 507 anp ++; 508 } 509 } 510 511 /* Convert AlBlk to contain AlNodes */ 512 rabp->ab_flag = AB_NODES; 513 rabp->ab_busycnt = 0; 514 rabp->ab_freecnt = 0xC; 515 rabp->ab_freeoff = sizeof(alblk_t); 516 517 /* Add AlNode for new allocated AlSec */ 518 AN_SET(AB_FREEANP(rabp), ~0, nrasp->as_self); 519 AB_ADDAN(rabp); 520 521 bdwrite(nbp); 522 } 523 524 if (al.al_len) { 525 dprintf(("hpfs_addextent: root retry\n")); 526 goto retry; 527 } 528 529 return (0); 530 } 531 532 /* 533 * Descent down to the end of tree, then search for 534 * ralp->len contignous run begining from last run's end and 535 * concatenate new block! If we can't find one, then... 536 * 537 * Parameters: 538 * hpmp: Mix info 539 * rlsn: LSN containing AlSec 540 * ralp: AlLeaf to insert 541 * ranp: New AlNodes' values 542 * resp: Mix returning info 543 */ 544 int 545 hpfs_addextentr(struct hpfsmount *hpmp, lsn_t rlsn, alleaf_t *ralp, 546 alnode_t *ranp, u_long *resp) 547 { 548 struct buf *rbp; 549 alsec_t *rasp; 550 alblk_t *rabp; 551 alleaf_t *alp; 552 alnode_t *anp; 553 int error; 554 u_long pf; 555 u_long wb; 556 557 *resp = 0; 558 559 dprintf(("hpfs_addextentr: AlSec at 0x%x\n", rlsn)); 560 561 error = hpfs_breadalsec(hpmp, rlsn, &rbp); 562 if (error) 563 return (error); 564 565 rasp = (alsec_t *)rbp->b_data; 566 rabp = &rasp->as_ab; 567 wb = 0; 568 569 dprintf(("hpfs_addextentr: AlBlk: [0x%x, 0x%x, 0x%x]\n", 570 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag)); 571 572 while ((ralp->al_len) && (rabp->ab_freecnt > 0)) { 573 if (rabp->ab_flag & AB_NODES) { 574 /* 575 * This is level containing AlNodes, so try to 576 * insert recursively into last entry. 577 */ 578 anp = AB_LASTANP(rabp); 579 dprintf(("hpfs_addextentr: AlNode: [0x%x,0x%x] \n", 580 anp->an_nextoff,anp->an_lsn)); 581 582 /* 583 * Try to insert... 584 */ 585 error = hpfs_addextentr (hpmp, anp->an_lsn, ralp, ranp, &pf); 586 if (error) { 587 kprintf("hpfs_addextentr: FAILED %d\n",error); 588 goto fail; 589 } 590 591 switch (pf) { 592 case AE_SPLIT: 593 dprintf(("hpfs_addextentr: successful (split)\n")); 594 /* 595 * Then hpfs_addextentr has split tree below, now 596 * we need to fix this level. Particulary: 597 * fix last AlNode and add another one. 598 */ 599 bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2); 600 AB_ADDAN(rabp); 601 wb = 1; 602 break; 603 604 default: 605 case AE_DONE: 606 dprintf(("hpfs_addextentr: successful\n")); 607 break; 608 } 609 } else { 610 alp = AB_LASTALP(rabp); 611 dprintf(("hpfs_addextentr: AlLeaf: [0x%x,0x%x,0x%x] \n", 612 alp->al_off,alp->al_len,alp->al_lsn)); 613 614 /* Check if we trying to add in right place */ 615 if (alp->al_off + alp->al_len == ralp->al_off) { 616 lsn_t nlsn; 617 u_long nlen; 618 /* 619 * Search bitmap for block begining from 620 * alp->al_lsn + alp->al_len and long of ralp->al_len 621 */ 622 error = hpfs_bmlookup (hpmp, 0, 623 alp->al_lsn + alp->al_len, ralp->al_len, &nlsn, &nlen); 624 if (error) 625 goto fail; 626 627 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen); 628 if (error) 629 goto fail; 630 631 dprintf(("hpfs_addextentr: new: 0x%x 0x%lx, ", nlsn, nlen)); 632 633 /* 634 * If ending of existed entry fits the 635 * begining of the extent being added, 636 * then we add concatenate two extents. 637 */ 638 if (alp->al_lsn + alp->al_len == nlsn) { 639 dprintf(("concat\n")); 640 alp->al_len += nlen; 641 } else { 642 dprintf(("created new leaf\n")); 643 AL_SET(AB_FREEALP(rabp), ralp->al_off, nlen, nlsn); 644 AB_ADDAL(rabp); 645 } 646 647 ralp->al_len -= nlen; 648 ralp->al_off += nlen; 649 } else { 650 kprintf("hpfs_addextentr: INTERNAL INCONSISTENCE\n"); 651 error = (EINVAL); 652 goto fail; 653 } 654 } 655 } 656 657 /* 658 * Split AlBlk if overflowed. 659 */ 660 if (rabp->ab_freecnt <= 0) { 661 struct buf *nbp; 662 alsec_t * nrasp; 663 664 dprintf(("hpfs_addextentr: overflow, split\n")); 665 666 error = hpfs_splitalsec (hpmp, rasp, &nrasp, &nbp); 667 if (error) { 668 kprintf("hpfs_addextent: CAN'T SPLIT\n"); 669 goto fail; 670 } 671 672 if (rabp->ab_flag & AB_NODES) { 673 int i; 674 alsec_t * asp; 675 alnode_t * anp; 676 struct buf * bp; 677 678 ranp[0].an_nextoff = 679 AB_LASTANP(&rasp->as_ab)->an_nextoff; 680 681 /* We need to set left subtree's last entry 682 * offset to 0xFFFFFFFF for OS/2 to be able 683 * to read our files. It treats absence of 684 * 0xFFFFFFFF as error. 685 */ 686 AB_LASTANP(&rasp->as_ab)->an_nextoff = ~0; 687 688 /* We need to fix new allocated AlSec's 689 * children, becouse their parent has changed. 690 */ 691 anp = AB_ALNODE(&nrasp->as_ab); 692 for (i=0; i<nrasp->as_ab.ab_busycnt; i++) { 693 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp); 694 if (error) { 695 brelse(nbp); 696 goto fail; 697 } 698 699 asp = (alsec_t *)bp->b_data; 700 asp->as_parent = nrasp->as_self; 701 702 bdwrite(bp); 703 anp ++; 704 } 705 } else { 706 ranp[0].an_nextoff = 707 AB_ALLEAF(&nrasp->as_ab)->al_off; 708 } 709 710 ranp[0].an_lsn = rasp->as_self; 711 ranp[1].an_nextoff = ~0; 712 ranp[1].an_lsn = nrasp->as_self; 713 714 bdwrite(nbp); 715 716 *resp = AE_SPLIT; 717 wb = 1; 718 } 719 720 if (wb) 721 bdwrite (rbp); 722 else 723 brelse(rbp); 724 725 return (0); 726 727 fail: 728 brelse(rbp); 729 730 return (error); 731 } 732 733 /* 734 * Recursive routine walking down the b-tree and deallocating all 735 * extents above bn. Returns *resp != 0 if alblk was totally 736 * deallocated and may be freed. Tries to keep b-tree. 737 * 738 * (XXXX) NOTE! THIS ROUTINE WILL NEVER DECREMENT DEPTH OF 739 * THE TREE. 740 */ 741 int 742 hpfs_truncatealblk(struct hpfsmount *hpmp, alblk_t *abp, lsn_t bn, int *resp) 743 { 744 int error; 745 alleaf_t *alp; 746 alnode_t *anp; 747 alsec_t *asp; 748 struct buf *bp; 749 750 dprintf(("hpfs_truncatealblk: AlBlk: [0x%x,0x%x, 0x%x]\n", 751 abp->ab_freecnt, abp->ab_busycnt, abp->ab_flag)); 752 753 if (abp->ab_flag & AB_NODES) { 754 /* 755 * Scan array of AlNodes backward, 756 * diving in recursion if needed 757 */ 758 anp = AB_LASTANP(abp); 759 760 while (abp->ab_busycnt && (bn <= anp->an_nextoff)) { 761 dprintf(("hpfs_truncatealblk: AlNode: [0x%x,0x%x] \n", 762 anp->an_nextoff,anp->an_lsn)); 763 764 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp); 765 if (error) 766 return (error); 767 768 asp = (alsec_t *)bp->b_data; 769 770 error = hpfs_truncatealblk (hpmp, 771 &asp->as_ab, bn, resp); 772 if (error) { 773 brelse(bp); 774 return (error); 775 } 776 777 if (*resp) { 778 brelse (bp); 779 780 error = hpfs_bmmarkfree(hpmp, 781 anp->an_lsn, 1); 782 if (error) 783 return (error); 784 785 AB_RMAN(abp); 786 anp --; 787 } else { 788 /* 789 * We have deallocated some entries, some space 790 * migth been freed, then try to concat two 791 * last AlSec. 792 */ 793 anp->an_nextoff = ~0; 794 if (abp->ab_busycnt >= 2) { 795 alsec_t *as0p; 796 struct buf *b0p; 797 798 error = hpfs_breadalsec(hpmp, 799 (anp-1)->an_lsn, &b0p); 800 if (error) 801 return (error); 802 803 as0p = (alsec_t *)b0p->b_data; 804 error = hpfs_concatalsec(hpmp, 805 as0p, asp, anp - 1); 806 if (error == ENOSPC) { 807 /* Not enough space */ 808 brelse (b0p); 809 bdwrite (bp); 810 } else if (error == 0) { 811 /* All OK */ 812 (anp-1)->an_nextoff = anp->an_nextoff; 813 814 bdwrite (b0p); 815 brelse (bp); 816 817 error = hpfs_bmmarkfree(hpmp, 818 anp->an_lsn, 1); 819 if (error) 820 return (error); 821 822 AB_RMAN(abp); 823 } else { 824 /* True error */ 825 brelse (b0p); 826 brelse (bp); 827 return (error); 828 } 829 } else { 830 /* Nowhere to concatenate */ 831 bdwrite (bp); 832 } 833 834 /* There can not be any more entries 835 * over greater bn, becouse last AlSec 836 * wasn't freed totally. So go out. 837 */ 838 break; 839 } 840 } 841 842 if (abp->ab_busycnt == 0) 843 *resp = 1; 844 else 845 *resp = 0; 846 } else { 847 /* 848 * Scan array of AlLeafs backward, 849 * free all above bn. 850 */ 851 alp = AB_LASTALP(abp); 852 853 while (abp->ab_busycnt && (bn < alp->al_off + alp->al_len)){ 854 dprintf(("hpfs_truncatealblk: AlLeaf: [0x%x,0x%x,0x%x] \n", 855 alp->al_off,alp->al_len,alp->al_lsn)); 856 857 if (bn <= alp->al_off) { 858 error = hpfs_bmmarkfree(hpmp, alp->al_lsn, 859 alp->al_len); 860 if (error) 861 return (error); 862 863 AB_RMAL(abp); 864 alp --; 865 } else if ((bn > alp->al_off) && 866 (bn < alp->al_off + alp->al_len)){ 867 error = hpfs_bmmarkfree(hpmp, 868 alp->al_lsn + bn - alp->al_off, 869 alp->al_len - bn + alp->al_off); 870 if (error) 871 return (error); 872 873 alp->al_len = bn - alp->al_off; 874 875 break; 876 } else 877 break; 878 } 879 } 880 881 /* Signal parent deallocation, if need */ 882 if (abp->ab_busycnt == 0) 883 *resp = 1; 884 else 885 *resp = 0; 886 887 return (0); 888 } 889