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