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