The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/hpfs/hpfs_alsubr.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 4e00aadda614e26309950cac5433b575


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.