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