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