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