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