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