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