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  * $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 }