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

Cache object: 83db410f74e9265d2f8e9ae1fff6d3e8


[ 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.