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.6 2006/01/13 21:09:27 swildner 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 * Parameters: 537 * hpmp: Mix info 538 * rlsn: LSN containing AlSec 539 * ralp: AlLeaf to insert 540 * ranp: New AlNodes' values 541 * resp: Mix returning info 542 */ 543 int 544 hpfs_addextentr(struct hpfsmount *hpmp, lsn_t rlsn, alleaf_t *ralp, 545 alnode_t *ranp, u_long *resp) 546 { 547 struct buf *rbp; 548 alsec_t *rasp; 549 alblk_t *rabp; 550 alleaf_t *alp; 551 alnode_t *anp; 552 int error; 553 u_long pf; 554 u_long wb; 555 556 *resp = 0; 557 558 dprintf(("hpfs_addextentr: AlSec at 0x%x\n", rlsn)); 559 560 error = hpfs_breadalsec(hpmp, rlsn, &rbp); 561 if (error) 562 return (error); 563 564 rasp = (alsec_t *)rbp->b_data; 565 rabp = &rasp->as_ab; 566 wb = 0; 567 568 dprintf(("hpfs_addextentr: AlBlk: [0x%x, 0x%x, 0x%x]\n", 569 rabp->ab_freecnt, rabp->ab_busycnt, rabp->ab_flag)); 570 571 while ((ralp->al_len) && (rabp->ab_freecnt > 0)) { 572 if (rabp->ab_flag & AB_NODES) { 573 /* 574 * This is level containing AlNodes, so try to 575 * insert recursively into last entry. 576 */ 577 anp = AB_LASTANP(rabp); 578 dprintf(("hpfs_addextentr: AlNode: [0x%x,0x%x] \n", 579 anp->an_nextoff,anp->an_lsn)); 580 581 /* 582 * Try to insert... 583 */ 584 error = hpfs_addextentr (hpmp, anp->an_lsn, ralp, ranp, &pf); 585 if (error) { 586 printf("hpfs_addextentr: FAILED %d\n",error); 587 goto fail; 588 } 589 590 switch (pf) { 591 case AE_SPLIT: 592 dprintf(("hpfs_addextentr: successful (split)\n")); 593 /* 594 * Then hpfs_addextentr has split tree below, now 595 * we need to fix this level. Particulary: 596 * fix last AlNode and add another one. 597 */ 598 bcopy(ranp, AB_LASTANP(rabp), sizeof(alnode_t) * 2); 599 AB_ADDAN(rabp); 600 wb = 1; 601 break; 602 603 default: 604 case AE_DONE: 605 dprintf(("hpfs_addextentr: successful\n")); 606 break; 607 } 608 } else { 609 alp = AB_LASTALP(rabp); 610 dprintf(("hpfs_addextentr: AlLeaf: [0x%x,0x%x,0x%x] \n", 611 alp->al_off,alp->al_len,alp->al_lsn)); 612 613 /* Check if we trying to add in right place */ 614 if (alp->al_off + alp->al_len == ralp->al_off) { 615 lsn_t nlsn; 616 u_long nlen; 617 /* 618 * Search bitmap for block begining from 619 * alp->al_lsn + alp->al_len and long of ralp->al_len 620 */ 621 error = hpfs_bmlookup (hpmp, 0, 622 alp->al_lsn + alp->al_len, ralp->al_len, &nlsn, &nlen); 623 if (error) 624 goto fail; 625 626 error = hpfs_bmmarkbusy(hpmp, nlsn, nlen); 627 if (error) 628 goto fail; 629 630 dprintf(("hpfs_addextentr: new: 0x%x 0x%lx, ", nlsn, nlen)); 631 632 /* 633 * If ending of existed entry fits the 634 * begining of the extent being added, 635 * then we add concatenate two extents. 636 */ 637 if (alp->al_lsn + alp->al_len == nlsn) { 638 dprintf(("concat\n")); 639 alp->al_len += nlen; 640 } else { 641 dprintf(("created new leaf\n")); 642 AL_SET(AB_FREEALP(rabp), ralp->al_off, nlen, nlsn); 643 AB_ADDAL(rabp); 644 } 645 646 ralp->al_len -= nlen; 647 ralp->al_off += nlen; 648 } else { 649 printf("hpfs_addextentr: INTERNAL INCONSISTENCE\n"); 650 error = (EINVAL); 651 goto fail; 652 } 653 } 654 } 655 656 /* 657 * Split AlBlk if overflowed. 658 */ 659 if (rabp->ab_freecnt <= 0) { 660 struct buf *nbp; 661 alsec_t * nrasp; 662 663 dprintf(("hpfs_addextentr: overflow, split\n")); 664 665 error = hpfs_splitalsec (hpmp, rasp, &nrasp, &nbp); 666 if (error) { 667 printf("hpfs_addextent: CAN'T SPLIT\n"); 668 goto fail; 669 } 670 671 if (rabp->ab_flag & AB_NODES) { 672 int i; 673 alsec_t * asp; 674 alnode_t * anp; 675 struct buf * bp; 676 677 ranp[0].an_nextoff = 678 AB_LASTANP(&rasp->as_ab)->an_nextoff; 679 680 /* We need to set left subtree's last entry 681 * offset to 0xFFFFFFFF for OS/2 to be able 682 * to read our files. It treats absence of 683 * 0xFFFFFFFF as error. 684 */ 685 AB_LASTANP(&rasp->as_ab)->an_nextoff = ~0; 686 687 /* We need to fix new allocated AlSec's 688 * children, becouse their parent has changed. 689 */ 690 anp = AB_ALNODE(&nrasp->as_ab); 691 for (i=0; i<nrasp->as_ab.ab_busycnt; i++) { 692 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp); 693 if (error) { 694 brelse(nbp); 695 goto fail; 696 } 697 698 asp = (alsec_t *)bp->b_data; 699 asp->as_parent = nrasp->as_self; 700 701 bdwrite(bp); 702 anp ++; 703 } 704 } else { 705 ranp[0].an_nextoff = 706 AB_ALLEAF(&nrasp->as_ab)->al_off; 707 } 708 709 ranp[0].an_lsn = rasp->as_self; 710 ranp[1].an_nextoff = ~0; 711 ranp[1].an_lsn = nrasp->as_self; 712 713 bdwrite(nbp); 714 715 *resp = AE_SPLIT; 716 wb = 1; 717 } 718 719 if (wb) 720 bdwrite (rbp); 721 else 722 brelse(rbp); 723 724 return (0); 725 726 fail: 727 brelse(rbp); 728 729 return (error); 730 } 731 732 /* 733 * Recursive routine walking down the b-tree and deallocating all 734 * extents above bn. Returns *resp != 0 if alblk was totally 735 * deallocated and may be freed. Tries to keep b-tree. 736 * 737 * (XXXX) NOTE! THIS ROUTINE WILL NEVER DECREMENT DEPTH OF 738 * THE TREE. 739 */ 740 int 741 hpfs_truncatealblk(struct hpfsmount *hpmp, alblk_t *abp, lsn_t bn, int *resp) 742 { 743 int error; 744 alleaf_t *alp; 745 alnode_t *anp; 746 alsec_t *asp; 747 struct buf *bp; 748 749 dprintf(("hpfs_truncatealblk: AlBlk: [0x%x,0x%x, 0x%x]\n", 750 abp->ab_freecnt, abp->ab_busycnt, abp->ab_flag)); 751 752 if (abp->ab_flag & AB_NODES) { 753 /* 754 * Scan array of AlNodes backward, 755 * diving in recursion if needed 756 */ 757 anp = AB_LASTANP(abp); 758 759 while (abp->ab_busycnt && (bn <= anp->an_nextoff)) { 760 dprintf(("hpfs_truncatealblk: AlNode: [0x%x,0x%x] \n", 761 anp->an_nextoff,anp->an_lsn)); 762 763 error = hpfs_breadalsec(hpmp, anp->an_lsn, &bp); 764 if (error) 765 return (error); 766 767 asp = (alsec_t *)bp->b_data; 768 769 error = hpfs_truncatealblk (hpmp, 770 &asp->as_ab, bn, resp); 771 if (error) { 772 brelse(bp); 773 return (error); 774 } 775 776 if (*resp) { 777 brelse (bp); 778 779 error = hpfs_bmmarkfree(hpmp, 780 anp->an_lsn, 1); 781 if (error) 782 return (error); 783 784 AB_RMAN(abp); 785 anp --; 786 } else { 787 /* 788 * We have deallocated some entries, some space 789 * migth been freed, then try to concat two 790 * last AlSec. 791 */ 792 anp->an_nextoff = ~0; 793 if (abp->ab_busycnt >= 2) { 794 alsec_t *as0p; 795 struct buf *b0p; 796 797 error = hpfs_breadalsec(hpmp, 798 (anp-1)->an_lsn, &b0p); 799 if (error) 800 return (error); 801 802 as0p = (alsec_t *)b0p->b_data; 803 error = hpfs_concatalsec(hpmp, 804 as0p, asp, anp - 1); 805 if (error == ENOSPC) { 806 /* Not enought space */ 807 brelse (b0p); 808 bdwrite (bp); 809 } else if (error == 0) { 810 /* All OK */ 811 (anp-1)->an_nextoff = anp->an_nextoff; 812 813 bdwrite (b0p); 814 brelse (bp); 815 816 error = hpfs_bmmarkfree(hpmp, 817 anp->an_lsn, 1); 818 if (error) 819 return (error); 820 821 AB_RMAN(abp); 822 } else { 823 /* True error */ 824 brelse (b0p); 825 brelse (bp); 826 return (error); 827 } 828 } else { 829 /* Nowhere to concatenate */ 830 bdwrite (bp); 831 } 832 833 /* There can not be any more entries 834 * over greater bn, becouse last AlSec 835 * wasn't freed totally. So go out. 836 */ 837 break; 838 } 839 } 840 841 if (abp->ab_busycnt == 0) 842 *resp = 1; 843 else 844 *resp = 0; 845 } else { 846 /* 847 * Scan array of AlLeafs backward, 848 * free all above bn. 849 */ 850 alp = AB_LASTALP(abp); 851 852 while (abp->ab_busycnt && (bn < alp->al_off + alp->al_len)){ 853 dprintf(("hpfs_truncatealblk: AlLeaf: [0x%x,0x%x,0x%x] \n", 854 alp->al_off,alp->al_len,alp->al_lsn)); 855 856 if (bn <= alp->al_off) { 857 error = hpfs_bmmarkfree(hpmp, alp->al_lsn, 858 alp->al_len); 859 if (error) 860 return (error); 861 862 AB_RMAL(abp); 863 alp --; 864 } else if ((bn > alp->al_off) && 865 (bn < alp->al_off + alp->al_len)){ 866 error = hpfs_bmmarkfree(hpmp, 867 alp->al_lsn + bn - alp->al_off, 868 alp->al_len - bn + alp->al_off); 869 if (error) 870 return (error); 871 872 alp->al_len = bn - alp->al_off; 873 874 break; 875 } else 876 break; 877 } 878 } 879 880 /* Signal parent deallocation, if need */ 881 if (abp->ab_busycnt == 0) 882 *resp = 1; 883 else 884 *resp = 0; 885 886 return (0); 887 } 888