sys/vfs/hpfs/hpfs_alsubr.c

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