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/ext2fs/ext2_alloc.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  *  modified for Lites 1.1
    3  *
    4  *  Aug 1995, Godmar Back (gback@cs.utah.edu)
    5  *  University of Utah, Department of Computer Science
    6  */
    7 /*-
    8  * Copyright (c) 1982, 1986, 1989, 1993
    9  *      The Regents of the University of California.  All rights reserved.
   10  *
   11  * Redistribution and use in source and binary forms, with or without
   12  * modification, are permitted provided that the following conditions
   13  * are met:
   14  * 1. Redistributions of source code must retain the above copyright
   15  *    notice, this list of conditions and the following disclaimer.
   16  * 2. Redistributions in binary form must reproduce the above copyright
   17  *    notice, this list of conditions and the following disclaimer in the
   18  *    documentation and/or other materials provided with the distribution.
   19  * 4. Neither the name of the University nor the names of its contributors
   20  *    may be used to endorse or promote products derived from this software
   21  *    without specific prior written permission.
   22  *
   23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   33  * SUCH DAMAGE.
   34  *
   35  *      @(#)ffs_alloc.c 8.8 (Berkeley) 2/21/94
   36  * $FreeBSD: releng/11.2/sys/fs/ext2fs/ext2_alloc.c 331722 2018-03-29 02:50:57Z eadler $
   37  */
   38 
   39 #include <sys/param.h>
   40 #include <sys/systm.h>
   41 #include <sys/conf.h>
   42 #include <sys/vnode.h>
   43 #include <sys/stat.h>
   44 #include <sys/mount.h>
   45 #include <sys/sysctl.h>
   46 #include <sys/syslog.h>
   47 #include <sys/buf.h>
   48 #include <sys/endian.h>
   49 
   50 #include <fs/ext2fs/fs.h>
   51 #include <fs/ext2fs/inode.h>
   52 #include <fs/ext2fs/ext2_mount.h>
   53 #include <fs/ext2fs/ext2fs.h>
   54 #include <fs/ext2fs/ext2_extern.h>
   55 
   56 static daddr_t  ext2_alloccg(struct inode *, int, daddr_t, int);
   57 static daddr_t  ext2_clusteralloc(struct inode *, int, daddr_t, int);
   58 static u_long   ext2_dirpref(struct inode *);
   59 static u_long   ext2_hashalloc(struct inode *, int, long, int,
   60                                 daddr_t (*)(struct inode *, int, daddr_t, 
   61                                                 int));
   62 static daddr_t  ext2_nodealloccg(struct inode *, int, daddr_t, int);
   63 static daddr_t  ext2_mapsearch(struct m_ext2fs *, char *, daddr_t);
   64 
   65 /*
   66  * Allocate a block in the filesystem.
   67  *
   68  * A preference may be optionally specified. If a preference is given
   69  * the following hierarchy is used to allocate a block:
   70  *   1) allocate the requested block.
   71  *   2) allocate a rotationally optimal block in the same cylinder.
   72  *   3) allocate a block in the same cylinder group.
   73  *   4) quadradically rehash into other cylinder groups, until an
   74  *        available block is located.
   75  * If no block preference is given the following hierarchy is used
   76  * to allocate a block:
   77  *   1) allocate a block in the cylinder group that contains the
   78  *        inode for the file.
   79  *   2) quadradically rehash into other cylinder groups, until an
   80  *        available block is located.
   81  */
   82 int
   83 ext2_alloc(struct inode *ip, daddr_t lbn, e4fs_daddr_t bpref, int size,
   84     struct ucred *cred, e4fs_daddr_t *bnp)
   85 {
   86         struct m_ext2fs *fs;
   87         struct ext2mount *ump;
   88         int32_t bno;
   89         int cg;
   90 
   91         *bnp = 0;
   92         fs = ip->i_e2fs;
   93         ump = ip->i_ump;
   94         mtx_assert(EXT2_MTX(ump), MA_OWNED);
   95 #ifdef INVARIANTS
   96         if ((u_int)size > fs->e2fs_bsize || blkoff(fs, size) != 0) {
   97                 vn_printf(ip->i_devvp, "bsize = %lu, size = %d, fs = %s\n",
   98                     (long unsigned int)fs->e2fs_bsize, size, fs->e2fs_fsmnt);
   99                 panic("ext2_alloc: bad size");
  100         }
  101         if (cred == NOCRED)
  102                 panic("ext2_alloc: missing credential");
  103 #endif          /* INVARIANTS */
  104         if (size == fs->e2fs_bsize && fs->e2fs->e2fs_fbcount == 0)
  105                 goto nospace;
  106         if (cred->cr_uid != 0 &&
  107             fs->e2fs->e2fs_fbcount < fs->e2fs->e2fs_rbcount)
  108                 goto nospace;
  109         if (bpref >= fs->e2fs->e2fs_bcount)
  110                 bpref = 0;
  111         if (bpref == 0)
  112                 cg = ino_to_cg(fs, ip->i_number);
  113         else
  114                 cg = dtog(fs, bpref);
  115         bno = (daddr_t)ext2_hashalloc(ip, cg, bpref, fs->e2fs_bsize,
  116             ext2_alloccg);
  117         if (bno > 0) {
  118                 /* set next_alloc fields as done in block_getblk */
  119                 ip->i_next_alloc_block = lbn;
  120                 ip->i_next_alloc_goal = bno;
  121 
  122                 ip->i_blocks += btodb(fs->e2fs_bsize);
  123                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
  124                 *bnp = bno;
  125                 return (0);
  126         }
  127 nospace:
  128         EXT2_UNLOCK(ump);
  129         ext2_fserr(fs, cred->cr_uid, "filesystem full");
  130         uprintf("\n%s: write failed, filesystem is full\n", fs->e2fs_fsmnt);
  131         return (ENOSPC);
  132 }
  133 
  134 /*
  135  * Allocate EA's block for inode.
  136  */
  137 daddr_t
  138 ext2_allocfacl(struct inode *ip)
  139 {
  140         struct m_ext2fs *fs;
  141         daddr_t facl;
  142 
  143         fs = ip->i_e2fs;
  144 
  145         EXT2_LOCK(ip->i_ump);
  146         facl = ext2_alloccg(ip, ino_to_cg(fs, ip->i_number), 0, fs->e2fs_bsize);
  147         if (0 == facl)
  148                 EXT2_UNLOCK(ip->i_ump);
  149 
  150         return (facl);
  151 }
  152 
  153 /*
  154  * Reallocate a sequence of blocks into a contiguous sequence of blocks.
  155  *
  156  * The vnode and an array of buffer pointers for a range of sequential
  157  * logical blocks to be made contiguous is given. The allocator attempts
  158  * to find a range of sequential blocks starting as close as possible to
  159  * an fs_rotdelay offset from the end of the allocation for the logical
  160  * block immediately preceding the current range. If successful, the
  161  * physical block numbers in the buffer pointers and in the inode are
  162  * changed to reflect the new allocation. If unsuccessful, the allocation
  163  * is left unchanged. The success in doing the reallocation is returned.
  164  * Note that the error return is not reflected back to the user. Rather
  165  * the previous block allocation will be used.
  166  */
  167 
  168 static SYSCTL_NODE(_vfs, OID_AUTO, ext2fs, CTLFLAG_RW, 0, "EXT2FS filesystem");
  169 
  170 static int doasyncfree = 1;
  171 
  172 SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0,
  173     "Use asychronous writes to update block pointers when freeing blocks");
  174 
  175 static int doreallocblks = 0;
  176 
  177 SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, "");
  178 
  179 int
  180 ext2_reallocblks(struct vop_reallocblks_args *ap)
  181 {
  182         struct m_ext2fs *fs;
  183         struct inode *ip;
  184         struct vnode *vp;
  185         struct buf *sbp, *ebp;
  186         uint32_t *bap, *sbap, *ebap;
  187         struct ext2mount *ump;
  188         struct cluster_save *buflist;
  189         struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
  190         e2fs_lbn_t start_lbn, end_lbn;
  191         int soff;
  192         e2fs_daddr_t newblk, blkno;
  193         int i, len, start_lvl, end_lvl, pref, ssize;
  194 
  195         if (doreallocblks == 0)
  196                 return (ENOSPC);
  197 
  198         vp = ap->a_vp;
  199         ip = VTOI(vp);
  200         fs = ip->i_e2fs;
  201         ump = ip->i_ump;
  202 
  203         if (fs->e2fs_contigsumsize <= 0)
  204                 return (ENOSPC);
  205 
  206         buflist = ap->a_buflist;
  207         len = buflist->bs_nchildren;
  208         start_lbn = buflist->bs_children[0]->b_lblkno;
  209         end_lbn = start_lbn + len - 1;
  210 #ifdef INVARIANTS
  211         for (i = 1; i < len; i++)
  212                 if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
  213                         panic("ext2_reallocblks: non-cluster");
  214 #endif
  215         /*
  216          * If the cluster crosses the boundary for the first indirect
  217          * block, leave space for the indirect block. Indirect blocks
  218          * are initially laid out in a position after the last direct
  219          * block. Block reallocation would usually destroy locality by
  220          * moving the indirect block out of the way to make room for
  221          * data blocks if we didn't compensate here. We should also do
  222          * this for other indirect block boundaries, but it is only
  223          * important for the first one.
  224          */
  225         if (start_lbn < NDADDR && end_lbn >= NDADDR)
  226                 return (ENOSPC);
  227         /*
  228          * If the latest allocation is in a new cylinder group, assume that
  229          * the filesystem has decided to move and do not force it back to
  230          * the previous cylinder group.
  231          */
  232         if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
  233             dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
  234                 return (ENOSPC);
  235         if (ext2_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
  236             ext2_getlbns(vp, end_lbn, end_ap, &end_lvl))
  237                 return (ENOSPC);
  238         /*
  239          * Get the starting offset and block map for the first block.
  240          */
  241         if (start_lvl == 0) {
  242                 sbap = &ip->i_db[0];
  243                 soff = start_lbn;
  244         } else {
  245                 idp = &start_ap[start_lvl - 1];
  246                 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &sbp)) {
  247                         brelse(sbp);
  248                         return (ENOSPC);
  249                 }
  250                 sbap = (u_int *)sbp->b_data;
  251                 soff = idp->in_off;
  252         }
  253         /*
  254          * If the block range spans two block maps, get the second map.
  255          */
  256         ebap = NULL;
  257         if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
  258                 ssize = len;
  259         } else {
  260 #ifdef INVARIANTS
  261                 if (start_ap[start_lvl - 1].in_lbn == idp->in_lbn)
  262                         panic("ext2_reallocblks: start == end");
  263 #endif
  264                 ssize = len - (idp->in_off + 1);
  265                 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp))
  266                         goto fail;
  267                 ebap = (u_int *)ebp->b_data;
  268         }
  269         /*
  270          * Find the preferred location for the cluster.
  271          */
  272         EXT2_LOCK(ump);
  273         pref = ext2_blkpref(ip, start_lbn, soff, sbap, 0);
  274         /*
  275          * Search the block map looking for an allocation of the desired size.
  276          */
  277         if ((newblk = (e2fs_daddr_t)ext2_hashalloc(ip, dtog(fs, pref), pref,
  278             len, ext2_clusteralloc)) == 0) {
  279                 EXT2_UNLOCK(ump);
  280                 goto fail;
  281         }
  282         /*
  283          * We have found a new contiguous block.
  284          *
  285          * First we have to replace the old block pointers with the new
  286          * block pointers in the inode and indirect blocks associated
  287          * with the file.
  288          */
  289 #ifdef DEBUG
  290         printf("realloc: ino %ju, lbns %jd-%jd\n\told:",
  291             (uintmax_t)ip->i_number, (intmax_t)start_lbn, (intmax_t)end_lbn);
  292 #endif  /* DEBUG */
  293         blkno = newblk;
  294         for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
  295                 if (i == ssize) {
  296                         bap = ebap;
  297                         soff = -i;
  298                 }
  299 #ifdef INVARIANTS
  300                 if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap))
  301                         panic("ext2_reallocblks: alloc mismatch");
  302 #endif
  303 #ifdef DEBUG
  304                 printf(" %d,", *bap);
  305 #endif  /* DEBUG */
  306                 *bap++ = blkno;
  307         }
  308         /*
  309          * Next we must write out the modified inode and indirect blocks.
  310          * For strict correctness, the writes should be synchronous since
  311          * the old block values may have been written to disk. In practise
  312          * they are almost never written, but if we are concerned about
  313          * strict correctness, the `doasyncfree' flag should be set to zero.
  314          *
  315          * The test on `doasyncfree' should be changed to test a flag
  316          * that shows whether the associated buffers and inodes have
  317          * been written. The flag should be set when the cluster is
  318          * started and cleared whenever the buffer or inode is flushed.
  319          * We can then check below to see if it is set, and do the
  320          * synchronous write only when it has been cleared.
  321          */
  322         if (sbap != &ip->i_db[0]) {
  323                 if (doasyncfree)
  324                         bdwrite(sbp);
  325                 else
  326                         bwrite(sbp);
  327         } else {
  328                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
  329                 if (!doasyncfree)
  330                         ext2_update(vp, 1);
  331         }
  332         if (ssize < len) {
  333                 if (doasyncfree)
  334                         bdwrite(ebp);
  335                 else
  336                         bwrite(ebp);
  337         }
  338         /*
  339          * Last, free the old blocks and assign the new blocks to the buffers.
  340          */
  341 #ifdef DEBUG
  342         printf("\n\tnew:");
  343 #endif  /* DEBUG */
  344         for (blkno = newblk, i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
  345                 ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
  346                     fs->e2fs_bsize);
  347                 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
  348 #ifdef DEBUG
  349                 printf(" %d,", blkno);
  350 #endif  /* DEBUG */
  351         }
  352 #ifdef DEBUG
  353         printf("\n");
  354 #endif  /* DEBUG */
  355         return (0);
  356 
  357 fail:
  358         if (ssize < len)
  359                 brelse(ebp);
  360         if (sbap != &ip->i_db[0])
  361                 brelse(sbp);
  362         return (ENOSPC);
  363 }
  364 
  365 /*
  366  * Allocate an inode in the filesystem.
  367  *
  368  */
  369 int
  370 ext2_valloc(struct vnode *pvp, int mode, struct ucred *cred, struct vnode **vpp)
  371 {
  372         struct timespec ts;
  373         struct inode *pip;
  374         struct m_ext2fs *fs;
  375         struct inode *ip;
  376         struct ext2mount *ump;
  377         ino_t ino, ipref;
  378         int i, error, cg;
  379 
  380         *vpp = NULL;
  381         pip = VTOI(pvp);
  382         fs = pip->i_e2fs;
  383         ump = pip->i_ump;
  384 
  385         EXT2_LOCK(ump);
  386         if (fs->e2fs->e2fs_ficount == 0)
  387                 goto noinodes;
  388         /*
  389          * If it is a directory then obtain a cylinder group based on
  390          * ext2_dirpref else obtain it using ino_to_cg. The preferred inode is
  391          * always the next inode.
  392          */
  393         if ((mode & IFMT) == IFDIR) {
  394                 cg = ext2_dirpref(pip);
  395                 if (fs->e2fs_contigdirs[cg] < 255)
  396                         fs->e2fs_contigdirs[cg]++;
  397         } else {
  398                 cg = ino_to_cg(fs, pip->i_number);
  399                 if (fs->e2fs_contigdirs[cg] > 0)
  400                         fs->e2fs_contigdirs[cg]--;
  401         }
  402         ipref = cg * fs->e2fs->e2fs_ipg + 1;
  403         ino = (ino_t)ext2_hashalloc(pip, cg, (long)ipref, mode, ext2_nodealloccg);
  404 
  405         if (ino == 0)
  406                 goto noinodes;
  407         error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp);
  408         if (error) {
  409                 ext2_vfree(pvp, ino, mode);
  410                 return (error);
  411         }
  412         ip = VTOI(*vpp);
  413 
  414         /*
  415          * The question is whether using VGET was such good idea at all:
  416          * Linux doesn't read the old inode in when it is allocating a
  417          * new one. I will set at least i_size and i_blocks to zero.
  418          */
  419         ip->i_flag = 0;
  420         ip->i_size = 0;
  421         ip->i_blocks = 0;
  422         ip->i_mode = 0;
  423         ip->i_flags = 0;
  424         /* now we want to make sure that the block pointers are zeroed out */
  425         for (i = 0; i < NDADDR; i++)
  426                 ip->i_db[i] = 0;
  427         for (i = 0; i < NIADDR; i++)
  428                 ip->i_ib[i] = 0;
  429 
  430         /*
  431          * Set up a new generation number for this inode.
  432          * Avoid zero values.
  433          */
  434         do {
  435                 ip->i_gen = arc4random();
  436         } while (ip->i_gen == 0);
  437 
  438         vfs_timestamp(&ts);
  439         ip->i_birthtime = ts.tv_sec;
  440         ip->i_birthnsec = ts.tv_nsec;
  441 
  442 /*
  443 printf("ext2_valloc: allocated inode %d\n", ino);
  444 */
  445         return (0);
  446 noinodes:
  447         EXT2_UNLOCK(ump);
  448         ext2_fserr(fs, cred->cr_uid, "out of inodes");
  449         uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt);
  450         return (ENOSPC);
  451 }
  452 
  453 /*
  454  * Find a cylinder to place a directory.
  455  *
  456  * The policy implemented by this algorithm is to allocate a
  457  * directory inode in the same cylinder group as its parent
  458  * directory, but also to reserve space for its files inodes
  459  * and data. Restrict the number of directories which may be
  460  * allocated one after another in the same cylinder group
  461  * without intervening allocation of files.
  462  *
  463  * If we allocate a first level directory then force allocation
  464  * in another cylinder group.
  465  *
  466  */
  467 static u_long
  468 ext2_dirpref(struct inode *pip)
  469 {
  470         struct m_ext2fs *fs;
  471         int cg, prefcg, cgsize;
  472         u_int avgifree, avgbfree, avgndir, curdirsize;
  473         u_int minifree, minbfree, maxndir;
  474         u_int mincg, minndir;
  475         u_int dirsize, maxcontigdirs;
  476 
  477         mtx_assert(EXT2_MTX(pip->i_ump), MA_OWNED);
  478         fs = pip->i_e2fs;
  479 
  480         avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount;
  481         avgbfree = fs->e2fs->e2fs_fbcount / fs->e2fs_gcount;
  482         avgndir = fs->e2fs_total_dir / fs->e2fs_gcount;
  483 
  484         /*
  485          * Force allocation in another cg if creating a first level dir.
  486          */
  487         ASSERT_VOP_LOCKED(ITOV(pip), "ext2fs_dirpref");
  488         if (ITOV(pip)->v_vflag & VV_ROOT) {
  489                 prefcg = arc4random() % fs->e2fs_gcount;
  490                 mincg = prefcg;
  491                 minndir = fs->e2fs_ipg;
  492                 for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
  493                         if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
  494                             fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
  495                             fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
  496                                 mincg = cg;
  497                                 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
  498                         }
  499                 for (cg = 0; cg < prefcg; cg++)
  500                         if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
  501                             fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
  502                             fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
  503                                 mincg = cg;
  504                                 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
  505                         }
  506                 return (mincg);
  507         }
  508         /*
  509          * Count various limits which used for
  510          * optimal allocation of a directory inode.
  511          */
  512         maxndir = min(avgndir + fs->e2fs_ipg / 16, fs->e2fs_ipg);
  513         minifree = avgifree - avgifree / 4;
  514         if (minifree < 1)
  515                 minifree = 1;
  516         minbfree = avgbfree - avgbfree / 4;
  517         if (minbfree < 1)
  518                 minbfree = 1;
  519         cgsize = fs->e2fs_fsize * fs->e2fs_fpg;
  520         dirsize = AVGDIRSIZE;
  521         curdirsize = avgndir ? (cgsize - avgbfree * fs->e2fs_bsize) / avgndir : 0;
  522         if (dirsize < curdirsize)
  523                 dirsize = curdirsize;
  524         maxcontigdirs = min((avgbfree * fs->e2fs_bsize) / dirsize, 255);
  525         maxcontigdirs = min(maxcontigdirs, fs->e2fs_ipg / AFPDIR);
  526         if (maxcontigdirs == 0)
  527                 maxcontigdirs = 1;
  528 
  529         /*
  530          * Limit number of dirs in one cg and reserve space for
  531          * regular files, but only if we have no deficit in
  532          * inodes or space.
  533          */
  534         prefcg = ino_to_cg(fs, pip->i_number);
  535         for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
  536                 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
  537                     fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
  538                     fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
  539                         if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
  540                                 return (cg);
  541                 }
  542         for (cg = 0; cg < prefcg; cg++)
  543                 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
  544                     fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
  545                     fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
  546                         if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
  547                                 return (cg);
  548                 }
  549         /*
  550          * This is a backstop when we have deficit in space.
  551          */
  552         for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
  553                 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
  554                         return (cg);
  555         for (cg = 0; cg < prefcg; cg++)
  556                 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
  557                         break;
  558         return (cg);
  559 }
  560 
  561 /*
  562  * Select the desired position for the next block in a file.
  563  *
  564  * we try to mimic what Remy does in inode_getblk/block_getblk
  565  *
  566  * we note: blocknr == 0 means that we're about to allocate either
  567  * a direct block or a pointer block at the first level of indirection
  568  * (In other words, stuff that will go in i_db[] or i_ib[])
  569  *
  570  * blocknr != 0 means that we're allocating a block that is none
  571  * of the above. Then, blocknr tells us the number of the block
  572  * that will hold the pointer
  573  */
  574 e4fs_daddr_t
  575 ext2_blkpref(struct inode *ip, e2fs_lbn_t lbn, int indx, e2fs_daddr_t *bap,
  576     e2fs_daddr_t blocknr)
  577 {
  578         int tmp;
  579 
  580         mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED);
  581 
  582         /*
  583          * If the next block is actually what we thought it is, then set the
  584          * goal to what we thought it should be.
  585          */
  586         if (ip->i_next_alloc_block == lbn && ip->i_next_alloc_goal != 0)
  587                 return ip->i_next_alloc_goal;
  588 
  589         /*
  590          * Now check whether we were provided with an array that basically
  591          * tells us previous blocks to which we want to stay close.
  592          */
  593         if (bap)
  594                 for (tmp = indx - 1; tmp >= 0; tmp--)
  595                         if (bap[tmp])
  596                                 return bap[tmp];
  597 
  598         /*
  599          * Else lets fall back to the blocknr or, if there is none, follow
  600          * the rule that a block should be allocated near its inode.
  601          */
  602         return blocknr ? blocknr :
  603             (e2fs_daddr_t)(ip->i_block_group *
  604             EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) +
  605             ip->i_e2fs->e2fs->e2fs_first_dblock;
  606 }
  607 
  608 /*
  609  * Implement the cylinder overflow algorithm.
  610  *
  611  * The policy implemented by this algorithm is:
  612  *   1) allocate the block in its requested cylinder group.
  613  *   2) quadradically rehash on the cylinder group number.
  614  *   3) brute force search for a free block.
  615  */
  616 static u_long
  617 ext2_hashalloc(struct inode *ip, int cg, long pref, int size,
  618     daddr_t (*allocator) (struct inode *, int, daddr_t, int))
  619 {
  620         struct m_ext2fs *fs;
  621         ino_t result;
  622         int i, icg = cg;
  623 
  624         mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED);
  625         fs = ip->i_e2fs;
  626         /*
  627          * 1: preferred cylinder group
  628          */
  629         result = (*allocator)(ip, cg, pref, size);
  630         if (result)
  631                 return (result);
  632         /*
  633          * 2: quadratic rehash
  634          */
  635         for (i = 1; i < fs->e2fs_gcount; i *= 2) {
  636                 cg += i;
  637                 if (cg >= fs->e2fs_gcount)
  638                         cg -= fs->e2fs_gcount;
  639                 result = (*allocator)(ip, cg, 0, size);
  640                 if (result)
  641                         return (result);
  642         }
  643         /*
  644          * 3: brute force search
  645          * Note that we start at i == 2, since 0 was checked initially,
  646          * and 1 is always checked in the quadratic rehash.
  647          */
  648         cg = (icg + 2) % fs->e2fs_gcount;
  649         for (i = 2; i < fs->e2fs_gcount; i++) {
  650                 result = (*allocator)(ip, cg, 0, size);
  651                 if (result)
  652                         return (result);
  653                 cg++;
  654                 if (cg == fs->e2fs_gcount)
  655                         cg = 0;
  656         }
  657         return (0);
  658 }
  659 
  660 static unsigned long
  661 ext2_cg_num_gdb(struct m_ext2fs *fs, int cg)
  662 {
  663         int gd_per_block, metagroup, first, last;
  664 
  665         gd_per_block = fs->e2fs_bsize / sizeof(struct ext2_gd);
  666         metagroup = cg / gd_per_block;
  667         first = metagroup * gd_per_block;
  668         last = first + gd_per_block - 1;
  669 
  670         if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_META_BG) ||
  671             metagroup < fs->e2fs->e3fs_first_meta_bg) {
  672                 if (!ext2_cg_has_sb(fs, cg))
  673                         return (0);
  674                 if (EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_META_BG))
  675                         return (fs->e2fs->e3fs_first_meta_bg);
  676                 return (fs->e2fs_gdbcount);
  677         }
  678 
  679         if (cg == first || cg == first + 1 || cg == last)
  680                 return (1);
  681         return (0);
  682 
  683 }
  684 
  685 static int
  686 ext2_num_base_meta_blocks(struct m_ext2fs *fs, int cg)
  687 {
  688         int num, gd_per_block;
  689 
  690         gd_per_block = fs->e2fs_bsize / sizeof(struct ext2_gd);
  691         num = ext2_cg_has_sb(fs, cg);
  692 
  693         if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_META_BG) ||
  694             cg < fs->e2fs->e3fs_first_meta_bg * gd_per_block) {
  695                 if (num) {
  696                         num += ext2_cg_num_gdb(fs, cg);
  697                         num += fs->e2fs->e2fs_reserved_ngdb;
  698                 }
  699         } else {
  700                 num += ext2_cg_num_gdb(fs, cg);
  701         }
  702         
  703         return (num);
  704 }
  705 
  706 static int
  707 ext2_get_cg_number(struct m_ext2fs *fs, daddr_t blk)
  708 {
  709         int cg;
  710 
  711         if (fs->e2fs->e2fs_bpg == fs->e2fs_bsize * 8)
  712                 cg = (blk - fs->e2fs->e2fs_first_dblock) / (fs->e2fs_bsize * 8);
  713         else
  714                 cg = blk - fs->e2fs->e2fs_first_dblock;
  715 
  716         return (cg);
  717 }
  718 
  719 static void
  720 ext2_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
  721 {
  722         int i;
  723 
  724         if (start_bit >= end_bit)
  725                 return;
  726 
  727         for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
  728                 setbit(bitmap, i);
  729         if (i < end_bit)
  730                 memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
  731 }
  732 
  733 static int
  734 ext2_cg_block_bitmap_init(struct m_ext2fs *fs, int cg, struct buf *bp)
  735 {
  736         int bit, bit_max, inodes_per_block;
  737         uint32_t start, tmp;
  738 
  739         if (!EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM) ||
  740             !(fs->e2fs_gd[cg].ext4bgd_flags & EXT2_BG_BLOCK_UNINIT))
  741                 return (0);
  742 
  743         memset(bp->b_data, 0, fs->e2fs_bsize);
  744 
  745         bit_max = ext2_num_base_meta_blocks(fs, cg);
  746         if ((bit_max >> 3) >= fs->e2fs_bsize)
  747                 return (EINVAL);
  748 
  749         for (bit = 0; bit < bit_max; bit++)
  750                 setbit(bp->b_data, bit);
  751 
  752         start = cg * fs->e2fs->e2fs_bpg + fs->e2fs->e2fs_first_dblock;
  753 
  754         /* Set bits for block and inode bitmaps, and inode table */
  755         tmp = fs->e2fs_gd[cg].ext2bgd_b_bitmap;
  756         if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_FLEX_BG) ||
  757             tmp == ext2_get_cg_number(fs, cg))
  758                 setbit(bp->b_data, tmp - start);
  759 
  760         tmp = fs->e2fs_gd[cg].ext2bgd_i_bitmap;
  761         if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_FLEX_BG) ||
  762             tmp == ext2_get_cg_number(fs, cg))
  763                 setbit(bp->b_data, tmp - start);
  764 
  765         tmp = fs->e2fs_gd[cg].ext2bgd_i_tables;
  766         inodes_per_block = fs->e2fs_bsize/EXT2_INODE_SIZE(fs);
  767         while( tmp < fs->e2fs_gd[cg].ext2bgd_i_tables +
  768             fs->e2fs->e2fs_ipg / inodes_per_block ) {
  769                 if (!EXT2_HAS_INCOMPAT_FEATURE(fs, EXT2F_INCOMPAT_FLEX_BG) ||
  770                     tmp == ext2_get_cg_number(fs, cg))
  771                         setbit(bp->b_data, tmp - start);
  772                 tmp++;
  773         }
  774 
  775         /*
  776          * Also if the number of blocks within the group is less than
  777          * the blocksize * 8 ( which is the size of bitmap ), set rest
  778          * of the block bitmap to 1
  779          */
  780         ext2_mark_bitmap_end(fs->e2fs->e2fs_bpg, fs->e2fs_bsize * 8,
  781             bp->b_data);
  782 
  783         /* Clean the flag */
  784         fs->e2fs_gd[cg].ext4bgd_flags &= ~EXT2_BG_BLOCK_UNINIT;
  785 
  786         return (0);
  787 }
  788 
  789 /*
  790  * Determine whether a block can be allocated.
  791  *
  792  * Check to see if a block of the appropriate size is available,
  793  * and if it is, allocate it.
  794  */
  795 static daddr_t
  796 ext2_alloccg(struct inode *ip, int cg, daddr_t bpref, int size)
  797 {
  798         struct m_ext2fs *fs;
  799         struct buf *bp;
  800         struct ext2mount *ump;
  801         daddr_t bno, runstart, runlen;
  802         int bit, loc, end, error, start;
  803         char *bbp;
  804         /* XXX ondisk32 */
  805         fs = ip->i_e2fs;
  806         ump = ip->i_ump;
  807         if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0)
  808                 return (0);
  809         EXT2_UNLOCK(ump);
  810         error = bread(ip->i_devvp, fsbtodb(fs,
  811             fs->e2fs_gd[cg].ext2bgd_b_bitmap),
  812             (int)fs->e2fs_bsize, NOCRED, &bp);
  813         if (error) {
  814                 brelse(bp);
  815                 EXT2_LOCK(ump);
  816                 return (0);
  817         }
  818         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM)) {
  819                 error = ext2_cg_block_bitmap_init(fs, cg, bp);
  820                 if (error) {
  821                         brelse(bp);
  822                         EXT2_LOCK(ump);
  823                         return (0);
  824                 }
  825         }
  826         if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) {
  827                 /*
  828                  * Another thread allocated the last block in this
  829                  * group while we were waiting for the buffer.
  830                  */
  831                 brelse(bp);
  832                 EXT2_LOCK(ump);
  833                 return (0);
  834         }
  835         bbp = (char *)bp->b_data;
  836 
  837         if (dtog(fs, bpref) != cg)
  838                 bpref = 0;
  839         if (bpref != 0) {
  840                 bpref = dtogd(fs, bpref);
  841                 /*
  842                  * if the requested block is available, use it
  843                  */
  844                 if (isclr(bbp, bpref)) {
  845                         bno = bpref;
  846                         goto gotit;
  847                 }
  848         }
  849         /*
  850          * no blocks in the requested cylinder, so take next
  851          * available one in this cylinder group.
  852          * first try to get 8 contigous blocks, then fall back to a single
  853          * block.
  854          */
  855         if (bpref)
  856                 start = dtogd(fs, bpref) / NBBY;
  857         else
  858                 start = 0;
  859         end = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
  860 retry:
  861         runlen = 0;
  862         runstart = 0;
  863         for (loc = start; loc < end; loc++) {
  864                 if (bbp[loc] == (char)0xff) {
  865                         runlen = 0;
  866                         continue;
  867                 }
  868 
  869                 /* Start of a run, find the number of high clear bits. */
  870                 if (runlen == 0) {
  871                         bit = fls(bbp[loc]);
  872                         runlen = NBBY - bit;
  873                         runstart = loc * NBBY + bit;
  874                 } else if (bbp[loc] == 0) {
  875                         /* Continue a run. */
  876                         runlen += NBBY;
  877                 } else {
  878                         /*
  879                          * Finish the current run.  If it isn't long
  880                          * enough, start a new one.
  881                          */
  882                         bit = ffs(bbp[loc]) - 1;
  883                         runlen += bit;
  884                         if (runlen >= 8) {
  885                                 bno = runstart;
  886                                 goto gotit;
  887                         }
  888 
  889                         /* Run was too short, start a new one. */
  890                         bit = fls(bbp[loc]);
  891                         runlen = NBBY - bit;
  892                         runstart = loc * NBBY + bit;
  893                 }
  894 
  895                 /* If the current run is long enough, use it. */
  896                 if (runlen >= 8) {
  897                         bno = runstart;
  898                         goto gotit;
  899                 }
  900         }
  901         if (start != 0) {
  902                 end = start;
  903                 start = 0;
  904                 goto retry;
  905         }
  906         bno = ext2_mapsearch(fs, bbp, bpref);
  907         if (bno < 0) {
  908                 brelse(bp);
  909                 EXT2_LOCK(ump);
  910                 return (0);
  911         }
  912 gotit:
  913 #ifdef INVARIANTS
  914         if (isset(bbp, bno)) {
  915                 printf("ext2fs_alloccgblk: cg=%d bno=%jd fs=%s\n",
  916                     cg, (intmax_t)bno, fs->e2fs_fsmnt);
  917                 panic("ext2fs_alloccg: dup alloc");
  918         }
  919 #endif
  920         setbit(bbp, bno);
  921         EXT2_LOCK(ump);
  922         ext2_clusteracct(fs, bbp, cg, bno, -1);
  923         fs->e2fs->e2fs_fbcount--;
  924         fs->e2fs_gd[cg].ext2bgd_nbfree--;
  925         fs->e2fs_fmod = 1;
  926         EXT2_UNLOCK(ump);
  927         bdwrite(bp);
  928         return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
  929 }
  930 
  931 /*
  932  * Determine whether a cluster can be allocated.
  933  */
  934 static daddr_t
  935 ext2_clusteralloc(struct inode *ip, int cg, daddr_t bpref, int len)
  936 {
  937         struct m_ext2fs *fs;
  938         struct ext2mount *ump;
  939         struct buf *bp;
  940         char *bbp;
  941         int bit, error, got, i, loc, run;
  942         int32_t *lp;
  943         daddr_t bno;
  944 
  945         fs = ip->i_e2fs;
  946         ump = ip->i_ump;
  947 
  948         if (fs->e2fs_maxcluster[cg] < len)
  949                 return (0);
  950 
  951         EXT2_UNLOCK(ump);
  952         error = bread(ip->i_devvp,
  953             fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap),
  954             (int)fs->e2fs_bsize, NOCRED, &bp);
  955         if (error)
  956                 goto fail_lock;
  957 
  958         bbp = (char *)bp->b_data;
  959         EXT2_LOCK(ump);
  960         /*
  961          * Check to see if a cluster of the needed size (or bigger) is
  962          * available in this cylinder group.
  963          */
  964         lp = &fs->e2fs_clustersum[cg].cs_sum[len];
  965         for (i = len; i <= fs->e2fs_contigsumsize; i++)
  966                 if (*lp++ > 0)
  967                         break;
  968         if (i > fs->e2fs_contigsumsize) {
  969                 /*
  970                  * Update the cluster summary information to reflect
  971                  * the true maximum-sized cluster so that future cluster
  972                  * allocation requests can avoid reading the bitmap only
  973                  * to find no cluster.
  974                  */
  975                 lp = &fs->e2fs_clustersum[cg].cs_sum[len - 1];
  976                 for (i = len - 1; i > 0; i--)
  977                         if (*lp-- > 0)
  978                                 break;
  979                 fs->e2fs_maxcluster[cg] = i;
  980                 goto fail;
  981         }
  982         EXT2_UNLOCK(ump);
  983 
  984         /* Search the bitmap to find a big enough cluster like in FFS. */
  985         if (dtog(fs, bpref) != cg)
  986                 bpref = 0;
  987         if (bpref != 0)
  988                 bpref = dtogd(fs, bpref);
  989         loc = bpref / NBBY;
  990         bit = 1 << (bpref % NBBY);
  991         for (run = 0, got = bpref; got < fs->e2fs->e2fs_fpg; got++) {
  992                 if ((bbp[loc] & bit) != 0)
  993                         run = 0;
  994                 else {
  995                         run++;
  996                         if (run == len)
  997                                 break;
  998                 }
  999                 if ((got & (NBBY - 1)) != (NBBY - 1))
 1000                         bit <<= 1;
 1001                 else {
 1002                         loc++;
 1003                         bit = 1;
 1004                 }
 1005         }
 1006 
 1007         if (got >= fs->e2fs->e2fs_fpg)
 1008                 goto fail_lock;
 1009 
 1010         /* Allocate the cluster that we found. */
 1011         for (i = 1; i < len; i++)
 1012                 if (!isclr(bbp, got - run + i))
 1013                         panic("ext2_clusteralloc: map mismatch");
 1014 
 1015         bno = got - run + 1;
 1016         if (bno >= fs->e2fs->e2fs_fpg)
 1017                 panic("ext2_clusteralloc: allocated out of group");
 1018 
 1019         EXT2_LOCK(ump);
 1020         for (i = 0; i < len; i += fs->e2fs_fpb) {
 1021                 setbit(bbp, bno + i);
 1022                 ext2_clusteracct(fs, bbp, cg, bno + i, -1);
 1023                 fs->e2fs->e2fs_fbcount--;
 1024                 fs->e2fs_gd[cg].ext2bgd_nbfree--;
 1025         }
 1026         fs->e2fs_fmod = 1;
 1027         EXT2_UNLOCK(ump);
 1028 
 1029         bdwrite(bp);
 1030         return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
 1031 
 1032 fail_lock:
 1033         EXT2_LOCK(ump);
 1034 fail:
 1035         brelse(bp);
 1036         return (0);
 1037 }
 1038 
 1039 static int
 1040 ext2_zero_inode_table(struct inode *ip, int cg)
 1041 {
 1042         struct m_ext2fs *fs;
 1043         struct buf *bp;
 1044         int i, all_blks, used_blks;
 1045 
 1046         fs = ip->i_e2fs;
 1047 
 1048         if (fs->e2fs_gd[cg].ext4bgd_flags & EXT2_BG_INODE_ZEROED)
 1049                 return (0);
 1050 
 1051         all_blks = fs->e2fs->e2fs_inode_size * fs->e2fs->e2fs_ipg /
 1052             fs->e2fs_bsize;
 1053 
 1054         used_blks = howmany(fs->e2fs->e2fs_ipg -
 1055             fs->e2fs_gd[cg].ext4bgd_i_unused,
 1056             fs->e2fs_bsize / EXT2_INODE_SIZE(fs));
 1057 
 1058         for (i = 0; i < all_blks - used_blks; i++) {
 1059                 bp = getblk(ip->i_devvp, fsbtodb(fs,
 1060                     fs->e2fs_gd[cg].ext2bgd_i_tables + used_blks + i),
 1061                     fs->e2fs_bsize, 0, 0, 0);
 1062                 if (!bp)
 1063                         return (EIO);
 1064 
 1065                 vfs_bio_bzero_buf(bp, 0, fs->e2fs_bsize);
 1066                 bawrite(bp);
 1067         }
 1068 
 1069         fs->e2fs_gd[cg].ext4bgd_flags |= EXT2_BG_INODE_ZEROED;
 1070 
 1071         return (0);
 1072 }
 1073 
 1074 /*
 1075  * Determine whether an inode can be allocated.
 1076  *
 1077  * Check to see if an inode is available, and if it is,
 1078  * allocate it using tode in the specified cylinder group.
 1079  */
 1080 static daddr_t
 1081 ext2_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode)
 1082 {
 1083         struct m_ext2fs *fs;
 1084         struct buf *bp;
 1085         struct ext2mount *ump;
 1086         int error, start, len;
 1087         char *ibp, *loc;
 1088 
 1089         ipref--;        /* to avoid a lot of (ipref -1) */
 1090         if (ipref == -1)
 1091                 ipref = 0;
 1092         fs = ip->i_e2fs;
 1093         ump = ip->i_ump;
 1094         if (fs->e2fs_gd[cg].ext2bgd_nifree == 0)
 1095                 return (0);
 1096         EXT2_UNLOCK(ump);
 1097         error = bread(ip->i_devvp, fsbtodb(fs,
 1098             fs->e2fs_gd[cg].ext2bgd_i_bitmap),
 1099             (int)fs->e2fs_bsize, NOCRED, &bp);
 1100         if (error) {
 1101                 brelse(bp);
 1102                 EXT2_LOCK(ump);
 1103                 return (0);
 1104         }
 1105         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM)) {
 1106                 if (fs->e2fs_gd[cg].ext4bgd_flags & EXT2_BG_INODE_UNINIT) {
 1107                         memset(bp->b_data, 0, fs->e2fs_bsize);
 1108                         fs->e2fs_gd[cg].ext4bgd_flags &= ~EXT2_BG_INODE_UNINIT;
 1109                 }
 1110                 error = ext2_zero_inode_table(ip, cg);
 1111                 if (error) {
 1112                         brelse(bp);
 1113                         EXT2_LOCK(ump);
 1114                         return (0);
 1115                 }
 1116         }
 1117         if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) {
 1118                 /*
 1119                  * Another thread allocated the last i-node in this
 1120                  * group while we were waiting for the buffer.
 1121                  */
 1122                 brelse(bp);
 1123                 EXT2_LOCK(ump);
 1124                 return (0);
 1125         }
 1126         ibp = (char *)bp->b_data;
 1127         if (ipref) {
 1128                 ipref %= fs->e2fs->e2fs_ipg;
 1129                 if (isclr(ibp, ipref))
 1130                         goto gotit;
 1131         }
 1132         start = ipref / NBBY;
 1133         len = howmany(fs->e2fs->e2fs_ipg - ipref, NBBY);
 1134         loc = memcchr(&ibp[start], 0xff, len);
 1135         if (loc == NULL) {
 1136                 len = start + 1;
 1137                 start = 0;
 1138                 loc = memcchr(&ibp[start], 0xff, len);
 1139                 if (loc == NULL) {
 1140                         printf("cg = %d, ipref = %lld, fs = %s\n",
 1141                             cg, (long long)ipref, fs->e2fs_fsmnt);
 1142                         panic("ext2fs_nodealloccg: map corrupted");
 1143                         /* NOTREACHED */
 1144                 }
 1145         }
 1146         ipref = (loc - ibp) * NBBY + ffs(~*loc) - 1;
 1147 gotit:
 1148         setbit(ibp, ipref);
 1149         EXT2_LOCK(ump);
 1150         fs->e2fs_gd[cg].ext2bgd_nifree--;
 1151         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM))
 1152                 fs->e2fs_gd[cg].ext4bgd_i_unused--;
 1153         fs->e2fs->e2fs_ficount--;
 1154         fs->e2fs_fmod = 1;
 1155         if ((mode & IFMT) == IFDIR) {
 1156                 fs->e2fs_gd[cg].ext2bgd_ndirs++;
 1157                 fs->e2fs_total_dir++;
 1158         }
 1159         EXT2_UNLOCK(ump);
 1160         bdwrite(bp);
 1161         return (cg * fs->e2fs->e2fs_ipg + ipref + 1);
 1162 }
 1163 
 1164 /*
 1165  * Free a block or fragment.
 1166  *
 1167  */
 1168 void
 1169 ext2_blkfree(struct inode *ip, e4fs_daddr_t bno, long size)
 1170 {
 1171         struct m_ext2fs *fs;
 1172         struct buf *bp;
 1173         struct ext2mount *ump;
 1174         int cg, error;
 1175         char *bbp;
 1176 
 1177         fs = ip->i_e2fs;
 1178         ump = ip->i_ump;
 1179         cg = dtog(fs, bno);
 1180         if ((u_int)bno >= fs->e2fs->e2fs_bcount) {
 1181                 printf("bad block %lld, ino %ju\n", (long long)bno,
 1182                     (uintmax_t)ip->i_number);
 1183                 ext2_fserr(fs, ip->i_uid, "bad block");
 1184                 return;
 1185         }
 1186         error = bread(ip->i_devvp,
 1187             fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap),
 1188             (int)fs->e2fs_bsize, NOCRED, &bp);
 1189         if (error) {
 1190                 brelse(bp);
 1191                 return;
 1192         }
 1193         bbp = (char *)bp->b_data;
 1194         bno = dtogd(fs, bno);
 1195         if (isclr(bbp, bno)) {
 1196                 printf("block = %lld, fs = %s\n",
 1197                     (long long)bno, fs->e2fs_fsmnt);
 1198                 panic("ext2_blkfree: freeing free block");
 1199         }
 1200         clrbit(bbp, bno);
 1201         EXT2_LOCK(ump);
 1202         ext2_clusteracct(fs, bbp, cg, bno, 1);
 1203         fs->e2fs->e2fs_fbcount++;
 1204         fs->e2fs_gd[cg].ext2bgd_nbfree++;
 1205         fs->e2fs_fmod = 1;
 1206         EXT2_UNLOCK(ump);
 1207         bdwrite(bp);
 1208 }
 1209 
 1210 /*
 1211  * Free an inode.
 1212  *
 1213  */
 1214 int
 1215 ext2_vfree(struct vnode *pvp, ino_t ino, int mode)
 1216 {
 1217         struct m_ext2fs *fs;
 1218         struct inode *pip;
 1219         struct buf *bp;
 1220         struct ext2mount *ump;
 1221         int error, cg;
 1222         char *ibp;
 1223 
 1224         pip = VTOI(pvp);
 1225         fs = pip->i_e2fs;
 1226         ump = pip->i_ump;
 1227         if ((u_int)ino > fs->e2fs_ipg * fs->e2fs_gcount)
 1228                 panic("ext2_vfree: range: devvp = %p, ino = %ju, fs = %s",
 1229                     pip->i_devvp, (uintmax_t)ino, fs->e2fs_fsmnt);
 1230 
 1231         cg = ino_to_cg(fs, ino);
 1232         error = bread(pip->i_devvp,
 1233             fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_i_bitmap),
 1234             (int)fs->e2fs_bsize, NOCRED, &bp);
 1235         if (error) {
 1236                 brelse(bp);
 1237                 return (0);
 1238         }
 1239         ibp = (char *)bp->b_data;
 1240         ino = (ino - 1) % fs->e2fs->e2fs_ipg;
 1241         if (isclr(ibp, ino)) {
 1242                 printf("ino = %llu, fs = %s\n",
 1243                     (unsigned long long)ino, fs->e2fs_fsmnt);
 1244                 if (fs->e2fs_ronly == 0)
 1245                         panic("ext2_vfree: freeing free inode");
 1246         }
 1247         clrbit(ibp, ino);
 1248         EXT2_LOCK(ump);
 1249         fs->e2fs->e2fs_ficount++;
 1250         fs->e2fs_gd[cg].ext2bgd_nifree++;
 1251         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_GDT_CSUM))
 1252                 fs->e2fs_gd[cg].ext4bgd_i_unused++;
 1253         if ((mode & IFMT) == IFDIR) {
 1254                 fs->e2fs_gd[cg].ext2bgd_ndirs--;
 1255                 fs->e2fs_total_dir--;
 1256         }
 1257         fs->e2fs_fmod = 1;
 1258         EXT2_UNLOCK(ump);
 1259         bdwrite(bp);
 1260         return (0);
 1261 }
 1262 
 1263 /*
 1264  * Find a block in the specified cylinder group.
 1265  *
 1266  * It is a panic if a request is made to find a block if none are
 1267  * available.
 1268  */
 1269 static daddr_t
 1270 ext2_mapsearch(struct m_ext2fs *fs, char *bbp, daddr_t bpref)
 1271 {
 1272         char *loc;
 1273         int start, len;
 1274 
 1275         /*
 1276          * find the fragment by searching through the free block
 1277          * map for an appropriate bit pattern
 1278          */
 1279         if (bpref)
 1280                 start = dtogd(fs, bpref) / NBBY;
 1281         else
 1282                 start = 0;
 1283         len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
 1284         loc = memcchr(&bbp[start], 0xff, len);
 1285         if (loc == NULL) {
 1286                 len = start + 1;
 1287                 start = 0;
 1288                 loc = memcchr(&bbp[start], 0xff, len);
 1289                 if (loc == NULL) {
 1290                         printf("start = %d, len = %d, fs = %s\n",
 1291                             start, len, fs->e2fs_fsmnt);
 1292                         panic("ext2_mapsearch: map corrupted");
 1293                         /* NOTREACHED */
 1294                 }
 1295         }
 1296         return ((loc - bbp) * NBBY + ffs(~*loc) - 1);
 1297 }
 1298 
 1299 /*
 1300  * Fserr prints the name of a filesystem with an error diagnostic.
 1301  *
 1302  * The form of the error message is:
 1303  *      fs: error message
 1304  */
 1305 void
 1306 ext2_fserr(struct m_ext2fs *fs, uid_t uid, char *cp)
 1307 {
 1308 
 1309         log(LOG_ERR, "uid %u on %s: %s\n", uid, fs->e2fs_fsmnt, cp);
 1310 }
 1311 
 1312 int
 1313 ext2_cg_has_sb(struct m_ext2fs *fs, int cg)
 1314 {
 1315         int a3, a5, a7;
 1316 
 1317         if (cg == 0)
 1318                 return (1);
 1319 
 1320         if (EXT2_HAS_COMPAT_FEATURE(fs, EXT2F_COMPAT_SPARSESUPER2)) {
 1321                 if (cg == fs->e2fs->e4fs_backup_bgs[0] ||
 1322                     cg == fs->e2fs->e4fs_backup_bgs[1])
 1323                         return (1);
 1324                 return (0);
 1325         }
 1326 
 1327         if ((cg <= 1) ||
 1328             !EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_SPARSESUPER))
 1329                 return (1);
 1330 
 1331         if (!(cg & 1))
 1332                 return (0);
 1333 
 1334         for (a3 = 3, a5 = 5, a7 = 7;
 1335             a3 <= cg || a5 <= cg || a7 <= cg;
 1336             a3 *= 3, a5 *= 5, a7 *= 7)
 1337                 if (cg == a3 || cg == a5 || cg == a7)
 1338                         return (1);
 1339         return (0);
 1340 }

Cache object: 31f5d30098a8ffd7abdea995c95f23f7


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