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-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
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/10.2/sys/fs/ext2fs/ext2_alloc.c 277832 2015-01-28 15:36:24Z pfg $
   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 
   49 #include <fs/ext2fs/fs.h>
   50 #include <fs/ext2fs/inode.h>
   51 #include <fs/ext2fs/ext2_mount.h>
   52 #include <fs/ext2fs/ext2fs.h>
   53 #include <fs/ext2fs/ext2_extern.h>
   54 
   55 static daddr_t  ext2_alloccg(struct inode *, int, daddr_t, int);
   56 static daddr_t  ext2_clusteralloc(struct inode *, int, daddr_t, int);
   57 static u_long   ext2_dirpref(struct inode *);
   58 static void     ext2_fserr(struct m_ext2fs *, uid_t, char *);
   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         *bnp = 0;
   91         fs = ip->i_e2fs;
   92         ump = ip->i_ump;
   93         mtx_assert(EXT2_MTX(ump), MA_OWNED);
   94 #ifdef INVARIANTS
   95         if ((u_int)size > fs->e2fs_bsize || blkoff(fs, size) != 0) {
   96                 vn_printf(ip->i_devvp, "bsize = %lu, size = %d, fs = %s\n",
   97                     (long unsigned int)fs->e2fs_bsize, size, fs->e2fs_fsmnt);
   98                 panic("ext2_alloc: bad size");
   99         }
  100         if (cred == NOCRED)
  101                 panic("ext2_alloc: missing credential");
  102 #endif /* INVARIANTS */
  103         if (size == fs->e2fs_bsize && fs->e2fs->e2fs_fbcount == 0)
  104                 goto nospace;
  105         if (cred->cr_uid != 0 && 
  106                 fs->e2fs->e2fs_fbcount < fs->e2fs->e2fs_rbcount)
  107                 goto nospace;
  108         if (bpref >= fs->e2fs->e2fs_bcount)
  109                 bpref = 0;
  110         if (bpref == 0)
  111                 cg = ino_to_cg(fs, ip->i_number);
  112         else
  113                 cg = dtog(fs, bpref);
  114         bno = (daddr_t)ext2_hashalloc(ip, cg, bpref, fs->e2fs_bsize,
  115                                       ext2_alloccg);
  116         if (bno > 0) {
  117                 /* set next_alloc fields as done in block_getblk */
  118                 ip->i_next_alloc_block = lbn;
  119                 ip->i_next_alloc_goal = bno;
  120 
  121                 ip->i_blocks += btodb(fs->e2fs_bsize);
  122                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
  123                 *bnp = bno;
  124                 return (0);
  125         }
  126 nospace:
  127         EXT2_UNLOCK(ump);
  128         ext2_fserr(fs, cred->cr_uid, "filesystem full");
  129         uprintf("\n%s: write failed, filesystem is full\n", fs->e2fs_fsmnt);
  130         return (ENOSPC);
  131 }
  132 
  133 /*
  134  * Reallocate a sequence of blocks into a contiguous sequence of blocks.
  135  *
  136  * The vnode and an array of buffer pointers for a range of sequential
  137  * logical blocks to be made contiguous is given. The allocator attempts
  138  * to find a range of sequential blocks starting as close as possible to
  139  * an fs_rotdelay offset from the end of the allocation for the logical
  140  * block immediately preceding the current range. If successful, the
  141  * physical block numbers in the buffer pointers and in the inode are
  142  * changed to reflect the new allocation. If unsuccessful, the allocation
  143  * is left unchanged. The success in doing the reallocation is returned.
  144  * Note that the error return is not reflected back to the user. Rather
  145  * the previous block allocation will be used.
  146  */
  147 
  148 static SYSCTL_NODE(_vfs, OID_AUTO, ext2fs, CTLFLAG_RW, 0, "EXT2FS filesystem");
  149 
  150 static int doasyncfree = 1;
  151 SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doasyncfree, CTLFLAG_RW, &doasyncfree, 0,
  152     "Use asychronous writes to update block pointers when freeing blocks");
  153 
  154 static int doreallocblks = 1;
  155 SYSCTL_INT(_vfs_ext2fs, OID_AUTO, doreallocblks, CTLFLAG_RW, &doreallocblks, 0, "");
  156 
  157 int
  158 ext2_reallocblks(struct vop_reallocblks_args *ap)
  159 {
  160         struct m_ext2fs *fs;
  161         struct inode *ip;
  162         struct vnode *vp;
  163         struct buf *sbp, *ebp;
  164         uint32_t *bap, *sbap, *ebap = 0;
  165         struct ext2mount *ump;
  166         struct cluster_save *buflist;
  167         struct indir start_ap[NIADDR + 1], end_ap[NIADDR + 1], *idp;
  168         e2fs_lbn_t start_lbn, end_lbn;
  169         int soff;
  170         e2fs_daddr_t newblk, blkno;
  171         int i, len, start_lvl, end_lvl, pref, ssize;
  172 
  173         if (doreallocblks == 0)
  174                   return (ENOSPC);
  175 
  176         vp = ap->a_vp;
  177         ip = VTOI(vp);
  178         fs = ip->i_e2fs;
  179         ump = ip->i_ump;
  180 
  181         if (fs->e2fs_contigsumsize <= 0)
  182                 return (ENOSPC);
  183 
  184         buflist = ap->a_buflist;
  185         len = buflist->bs_nchildren;
  186         start_lbn = buflist->bs_children[0]->b_lblkno;
  187         end_lbn = start_lbn + len - 1;
  188 #ifdef INVARIANTS
  189         for (i = 1; i < len; i++)
  190                 if (buflist->bs_children[i]->b_lblkno != start_lbn + i)
  191                         panic("ext2_reallocblks: non-cluster");
  192 #endif
  193         /*
  194          * If the cluster crosses the boundary for the first indirect
  195          * block, leave space for the indirect block. Indirect blocks
  196          * are initially laid out in a position after the last direct
  197          * block. Block reallocation would usually destroy locality by
  198          * moving the indirect block out of the way to make room for
  199          * data blocks if we didn't compensate here. We should also do
  200          * this for other indirect block boundaries, but it is only
  201          * important for the first one.
  202          */
  203         if (start_lbn < NDADDR && end_lbn >= NDADDR)
  204                 return (ENOSPC);
  205         /*
  206          * If the latest allocation is in a new cylinder group, assume that
  207          * the filesystem has decided to move and do not force it back to
  208          * the previous cylinder group.
  209          */
  210         if (dtog(fs, dbtofsb(fs, buflist->bs_children[0]->b_blkno)) !=
  211             dtog(fs, dbtofsb(fs, buflist->bs_children[len - 1]->b_blkno)))
  212                 return (ENOSPC);
  213         if (ext2_getlbns(vp, start_lbn, start_ap, &start_lvl) ||
  214             ext2_getlbns(vp, end_lbn, end_ap, &end_lvl))
  215                 return (ENOSPC);
  216         /*
  217          * Get the starting offset and block map for the first block.
  218          */
  219         if (start_lvl == 0) {
  220                 sbap = &ip->i_db[0];
  221                 soff = start_lbn;
  222         } else {
  223                 idp = &start_ap[start_lvl - 1];
  224                 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &sbp)) {
  225                         brelse(sbp);
  226                         return (ENOSPC);
  227                 }
  228                 sbap = (u_int *)sbp->b_data;
  229                 soff = idp->in_off;
  230         }
  231         /*
  232          * If the block range spans two block maps, get the second map.
  233          */
  234         if (end_lvl == 0 || (idp = &end_ap[end_lvl - 1])->in_off + 1 >= len) {
  235                 ssize = len;
  236         } else {
  237 #ifdef INVARIANTS
  238                 if (start_ap[start_lvl-1].in_lbn == idp->in_lbn)
  239                         panic("ext2_reallocblks: start == end");
  240 #endif
  241                 ssize = len - (idp->in_off + 1);
  242                 if (bread(vp, idp->in_lbn, (int)fs->e2fs_bsize, NOCRED, &ebp))
  243                         goto fail;
  244                 ebap = (u_int *)ebp->b_data;
  245         }
  246         /*
  247          * Find the preferred location for the cluster.
  248          */
  249         EXT2_LOCK(ump);
  250         pref = ext2_blkpref(ip, start_lbn, soff, sbap, 0);
  251         /*
  252          * Search the block map looking for an allocation of the desired size.
  253          */
  254         if ((newblk = (e2fs_daddr_t)ext2_hashalloc(ip, dtog(fs, pref), pref,
  255             len, ext2_clusteralloc)) == 0){
  256                 EXT2_UNLOCK(ump);
  257                 goto fail;
  258         }       
  259         /*
  260          * We have found a new contiguous block.
  261          *
  262          * First we have to replace the old block pointers with the new
  263          * block pointers in the inode and indirect blocks associated
  264          * with the file.
  265          */
  266 #ifdef DEBUG
  267         printf("realloc: ino %d, lbns %jd-%jd\n\told:", ip->i_number,
  268             (intmax_t)start_lbn, (intmax_t)end_lbn);
  269 #endif /* DEBUG */
  270         blkno = newblk;
  271         for (bap = &sbap[soff], i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
  272                 if (i == ssize) {
  273                         bap = ebap;
  274                         soff = -i;
  275                 }
  276 #ifdef INVARIANTS
  277                 if (buflist->bs_children[i]->b_blkno != fsbtodb(fs, *bap))
  278                         panic("ext2_reallocblks: alloc mismatch");
  279 #endif
  280 #ifdef DEBUG
  281         printf(" %d,", *bap);
  282 #endif /* DEBUG */
  283                 *bap++ = blkno;
  284         }
  285         /*
  286          * Next we must write out the modified inode and indirect blocks.
  287          * For strict correctness, the writes should be synchronous since
  288          * the old block values may have been written to disk. In practise
  289          * they are almost never written, but if we are concerned about 
  290          * strict correctness, the `doasyncfree' flag should be set to zero.
  291          *
  292          * The test on `doasyncfree' should be changed to test a flag
  293          * that shows whether the associated buffers and inodes have
  294          * been written. The flag should be set when the cluster is
  295          * started and cleared whenever the buffer or inode is flushed.
  296          * We can then check below to see if it is set, and do the
  297          * synchronous write only when it has been cleared.
  298          */
  299         if (sbap != &ip->i_db[0]) {
  300                 if (doasyncfree)
  301                         bdwrite(sbp);
  302                 else
  303                         bwrite(sbp);
  304         } else {
  305                 ip->i_flag |= IN_CHANGE | IN_UPDATE;
  306                 if (!doasyncfree)
  307                         ext2_update(vp, 1);
  308         }
  309         if (ssize < len) {
  310                 if (doasyncfree)
  311                         bdwrite(ebp);
  312                 else
  313                         bwrite(ebp);
  314         }
  315         /*
  316          * Last, free the old blocks and assign the new blocks to the buffers.
  317          */
  318 #ifdef DEBUG
  319         printf("\n\tnew:");
  320 #endif /* DEBUG */
  321         for (blkno = newblk, i = 0; i < len; i++, blkno += fs->e2fs_fpb) {
  322                 ext2_blkfree(ip, dbtofsb(fs, buflist->bs_children[i]->b_blkno),
  323                     fs->e2fs_bsize);
  324                 buflist->bs_children[i]->b_blkno = fsbtodb(fs, blkno);
  325 #ifdef DEBUG
  326                 printf(" %d,", blkno);
  327 #endif /* DEBUG */
  328         }
  329 #ifdef DEBUG
  330         printf("\n");
  331 #endif /* DEBUG */
  332         return (0);
  333 
  334 fail:
  335         if (ssize < len)
  336                 brelse(ebp);
  337         if (sbap != &ip->i_db[0])
  338                 brelse(sbp);
  339         return (ENOSPC);
  340 }
  341 
  342 /*
  343  * Allocate an inode in the filesystem.
  344  * 
  345  */
  346 int
  347 ext2_valloc(struct vnode *pvp, int mode, struct ucred *cred, struct vnode **vpp)
  348 {
  349         struct timespec ts;
  350         struct inode *pip;
  351         struct m_ext2fs *fs;
  352         struct inode *ip;
  353         struct ext2mount *ump;
  354         ino_t ino, ipref;
  355         int i, error, cg;
  356         
  357         *vpp = NULL;
  358         pip = VTOI(pvp);
  359         fs = pip->i_e2fs;
  360         ump = pip->i_ump;
  361 
  362         EXT2_LOCK(ump);
  363         if (fs->e2fs->e2fs_ficount == 0)
  364                 goto noinodes;
  365         /*
  366          * If it is a directory then obtain a cylinder group based on
  367          * ext2_dirpref else obtain it using ino_to_cg. The preferred inode is
  368          * always the next inode.
  369          */
  370         if ((mode & IFMT) == IFDIR) {
  371                 cg = ext2_dirpref(pip);
  372                 if (fs->e2fs_contigdirs[cg] < 255)
  373                         fs->e2fs_contigdirs[cg]++;
  374         } else {
  375                 cg = ino_to_cg(fs, pip->i_number);
  376                 if (fs->e2fs_contigdirs[cg] > 0)
  377                         fs->e2fs_contigdirs[cg]--;
  378         }
  379         ipref = cg * fs->e2fs->e2fs_ipg + 1;
  380         ino = (ino_t)ext2_hashalloc(pip, cg, (long)ipref, mode, ext2_nodealloccg);
  381 
  382         if (ino == 0) 
  383                 goto noinodes;
  384         error = VFS_VGET(pvp->v_mount, ino, LK_EXCLUSIVE, vpp);
  385         if (error) {
  386                 ext2_vfree(pvp, ino, mode);
  387                 return (error);
  388         }
  389         ip = VTOI(*vpp);
  390 
  391         /*
  392          * The question is whether using VGET was such good idea at all:
  393          * Linux doesn't read the old inode in when it is allocating a
  394          * new one. I will set at least i_size and i_blocks to zero.
  395          */
  396         ip->i_size = 0;
  397         ip->i_blocks = 0;
  398         ip->i_mode = 0;
  399         ip->i_flags = 0;
  400         /* now we want to make sure that the block pointers are zeroed out */
  401         for (i = 0; i < NDADDR; i++)
  402                 ip->i_db[i] = 0;
  403         for (i = 0; i < NIADDR; i++)
  404                 ip->i_ib[i] = 0;
  405 
  406         /*
  407          * Set up a new generation number for this inode.
  408          * XXX check if this makes sense in ext2
  409          */
  410         if (ip->i_gen == 0 || ++ip->i_gen == 0)
  411                 ip->i_gen = random() / 2 + 1;
  412 
  413         vfs_timestamp(&ts);
  414         ip->i_birthtime = ts.tv_sec;
  415         ip->i_birthnsec = ts.tv_nsec;
  416 
  417 /*
  418 printf("ext2_valloc: allocated inode %d\n", ino);
  419 */
  420         return (0);
  421 noinodes:
  422         EXT2_UNLOCK(ump);
  423         ext2_fserr(fs, cred->cr_uid, "out of inodes");
  424         uprintf("\n%s: create/symlink failed, no inodes free\n", fs->e2fs_fsmnt);
  425         return (ENOSPC);
  426 }
  427 
  428 /*
  429  * Find a cylinder to place a directory.
  430  *
  431  * The policy implemented by this algorithm is to allocate a
  432  * directory inode in the same cylinder group as its parent
  433  * directory, but also to reserve space for its files inodes
  434  * and data. Restrict the number of directories which may be
  435  * allocated one after another in the same cylinder group
  436  * without intervening allocation of files.
  437  *
  438  * If we allocate a first level directory then force allocation
  439  * in another cylinder group.
  440  *
  441  */
  442 static u_long
  443 ext2_dirpref(struct inode *pip)
  444 {
  445         struct m_ext2fs *fs;
  446         int cg, prefcg, cgsize;
  447         u_int avgifree, avgbfree, avgndir, curdirsize;
  448         u_int minifree, minbfree, maxndir;
  449         u_int mincg, minndir;
  450         u_int dirsize, maxcontigdirs;
  451 
  452         mtx_assert(EXT2_MTX(pip->i_ump), MA_OWNED);
  453         fs = pip->i_e2fs;
  454 
  455         avgifree = fs->e2fs->e2fs_ficount / fs->e2fs_gcount;
  456         avgbfree = fs->e2fs->e2fs_fbcount / fs->e2fs_gcount;
  457         avgndir  = fs->e2fs_total_dir / fs->e2fs_gcount;
  458 
  459         /*
  460          * Force allocation in another cg if creating a first level dir.
  461          */
  462         ASSERT_VOP_LOCKED(ITOV(pip), "ext2fs_dirpref");
  463         if (ITOV(pip)->v_vflag & VV_ROOT) {
  464                 prefcg = arc4random() % fs->e2fs_gcount;
  465                 mincg = prefcg;
  466                 minndir = fs->e2fs_ipg;
  467                 for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
  468                         if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
  469                             fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
  470                             fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
  471                                 mincg = cg;
  472                                 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
  473                         }
  474                 for (cg = 0; cg < prefcg; cg++)
  475                         if (fs->e2fs_gd[cg].ext2bgd_ndirs < minndir &&
  476                             fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree &&
  477                             fs->e2fs_gd[cg].ext2bgd_nbfree >= avgbfree) {
  478                                 mincg = cg;
  479                                 minndir = fs->e2fs_gd[cg].ext2bgd_ndirs;
  480                         }
  481 
  482                 return (mincg);
  483         }
  484 
  485         /*
  486          * Count various limits which used for
  487          * optimal allocation of a directory inode.
  488          */
  489         maxndir = min(avgndir + fs->e2fs_ipg / 16, fs->e2fs_ipg);
  490         minifree = avgifree - avgifree / 4;
  491         if (minifree < 1)
  492                 minifree = 1;
  493         minbfree = avgbfree - avgbfree / 4;
  494         if (minbfree < 1)
  495                 minbfree = 1;
  496         cgsize = fs->e2fs_fsize * fs->e2fs_fpg;
  497         dirsize = AVGDIRSIZE;
  498         curdirsize = avgndir ? (cgsize - avgbfree * fs->e2fs_bsize) / avgndir : 0;
  499         if (dirsize < curdirsize)
  500                 dirsize = curdirsize;
  501         maxcontigdirs = min((avgbfree * fs->e2fs_bsize) / dirsize, 255);
  502         maxcontigdirs = min(maxcontigdirs, fs->e2fs_ipg / AFPDIR);
  503         if (maxcontigdirs == 0)
  504                 maxcontigdirs = 1;
  505 
  506         /*
  507          * Limit number of dirs in one cg and reserve space for 
  508          * regular files, but only if we have no deficit in
  509          * inodes or space.
  510          */
  511         prefcg = ino_to_cg(fs, pip->i_number);
  512         for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
  513                 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
  514                     fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
  515                     fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
  516                         if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
  517                                 return (cg);
  518                 }
  519         for (cg = 0; cg < prefcg; cg++)
  520                 if (fs->e2fs_gd[cg].ext2bgd_ndirs < maxndir &&
  521                     fs->e2fs_gd[cg].ext2bgd_nifree >= minifree &&
  522                     fs->e2fs_gd[cg].ext2bgd_nbfree >= minbfree) {
  523                         if (fs->e2fs_contigdirs[cg] < maxcontigdirs)
  524                                 return (cg);
  525                 }
  526         /*
  527          * This is a backstop when we have deficit in space.
  528          */
  529         for (cg = prefcg; cg < fs->e2fs_gcount; cg++)
  530                 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
  531                         return (cg);
  532         for (cg = 0; cg < prefcg; cg++)
  533                 if (fs->e2fs_gd[cg].ext2bgd_nifree >= avgifree)
  534                         break;
  535         return (cg);
  536 }
  537 
  538 /*
  539  * Select the desired position for the next block in a file.  
  540  *
  541  * we try to mimic what Remy does in inode_getblk/block_getblk
  542  *
  543  * we note: blocknr == 0 means that we're about to allocate either
  544  * a direct block or a pointer block at the first level of indirection
  545  * (In other words, stuff that will go in i_db[] or i_ib[])
  546  *
  547  * blocknr != 0 means that we're allocating a block that is none
  548  * of the above. Then, blocknr tells us the number of the block
  549  * that will hold the pointer
  550  */
  551 e4fs_daddr_t
  552 ext2_blkpref(struct inode *ip, e2fs_lbn_t lbn, int indx, e2fs_daddr_t *bap,
  553     e2fs_daddr_t blocknr)
  554 {
  555         int     tmp;
  556         mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED);
  557 
  558         /* if the next block is actually what we thought it is,
  559            then set the goal to what we thought it should be
  560         */
  561         if (ip->i_next_alloc_block == lbn && ip->i_next_alloc_goal != 0)
  562                 return ip->i_next_alloc_goal;
  563 
  564         /* now check whether we were provided with an array that basically
  565            tells us previous blocks to which we want to stay closeby
  566         */
  567         if (bap)
  568                 for (tmp = indx - 1; tmp >= 0; tmp--) 
  569                         if (bap[tmp]) 
  570                                 return bap[tmp];
  571 
  572         /* else let's fall back to the blocknr, or, if there is none,
  573            follow the rule that a block should be allocated near its inode
  574         */
  575         return blocknr ? blocknr :
  576                         (e2fs_daddr_t)(ip->i_block_group * 
  577                         EXT2_BLOCKS_PER_GROUP(ip->i_e2fs)) + 
  578                         ip->i_e2fs->e2fs->e2fs_first_dblock;
  579 }
  580 
  581 /*
  582  * Implement the cylinder overflow algorithm.
  583  *
  584  * The policy implemented by this algorithm is:
  585  *   1) allocate the block in its requested cylinder group.
  586  *   2) quadradically rehash on the cylinder group number.
  587  *   3) brute force search for a free block.
  588  */
  589 static u_long
  590 ext2_hashalloc(struct inode *ip, int cg, long pref, int size,
  591                 daddr_t (*allocator)(struct inode *, int, daddr_t, int))
  592 {
  593         struct m_ext2fs *fs;
  594         ino_t result;
  595         int i, icg = cg;
  596 
  597         mtx_assert(EXT2_MTX(ip->i_ump), MA_OWNED);
  598         fs = ip->i_e2fs;
  599         /*
  600          * 1: preferred cylinder group
  601          */
  602         result = (*allocator)(ip, cg, pref, size);
  603         if (result)
  604                 return (result);
  605         /*
  606          * 2: quadratic rehash
  607          */
  608         for (i = 1; i < fs->e2fs_gcount; i *= 2) {
  609                 cg += i;
  610                 if (cg >= fs->e2fs_gcount)
  611                         cg -= fs->e2fs_gcount;
  612                 result = (*allocator)(ip, cg, 0, size);
  613                 if (result)
  614                         return (result);
  615         }
  616         /*
  617          * 3: brute force search
  618          * Note that we start at i == 2, since 0 was checked initially,
  619          * and 1 is always checked in the quadratic rehash.
  620          */
  621         cg = (icg + 2) % fs->e2fs_gcount;
  622         for (i = 2; i < fs->e2fs_gcount; i++) {
  623                 result = (*allocator)(ip, cg, 0, size);
  624                 if (result)
  625                         return (result);
  626                 cg++;
  627                 if (cg == fs->e2fs_gcount)
  628                         cg = 0;
  629         }
  630         return (0);
  631 }
  632 
  633 /*
  634  * Determine whether a block can be allocated.
  635  *
  636  * Check to see if a block of the appropriate size is available,
  637  * and if it is, allocate it.
  638  */
  639 static daddr_t
  640 ext2_alloccg(struct inode *ip, int cg, daddr_t bpref, int size)
  641 {
  642         struct m_ext2fs *fs;
  643         struct buf *bp;
  644         struct ext2mount *ump;
  645         daddr_t bno, runstart, runlen;
  646         int bit, loc, end, error, start;
  647         char *bbp;
  648         /* XXX ondisk32 */
  649         fs = ip->i_e2fs;
  650         ump = ip->i_ump;
  651         if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0)
  652                 return (0);
  653         EXT2_UNLOCK(ump);
  654         error = bread(ip->i_devvp, fsbtodb(fs,
  655                 fs->e2fs_gd[cg].ext2bgd_b_bitmap),
  656                 (int)fs->e2fs_bsize, NOCRED, &bp);
  657         if (error) {
  658                 brelse(bp);
  659                 EXT2_LOCK(ump);
  660                 return (0);
  661         }
  662         if (fs->e2fs_gd[cg].ext2bgd_nbfree == 0) {
  663                 /*
  664                  * Another thread allocated the last block in this
  665                  * group while we were waiting for the buffer.
  666                  */
  667                 brelse(bp);
  668                 EXT2_LOCK(ump);
  669                 return (0);
  670         }
  671         bbp = (char *)bp->b_data;
  672 
  673         if (dtog(fs, bpref) != cg)
  674                 bpref = 0;
  675         if (bpref != 0) {
  676                 bpref = dtogd(fs, bpref);
  677                 /*
  678                  * if the requested block is available, use it
  679                  */
  680                 if (isclr(bbp, bpref)) {
  681                         bno = bpref;
  682                         goto gotit;
  683                 }
  684         }
  685         /*
  686          * no blocks in the requested cylinder, so take next
  687          * available one in this cylinder group.
  688          * first try to get 8 contigous blocks, then fall back to a single
  689          * block.
  690          */
  691         if (bpref)
  692                 start = dtogd(fs, bpref) / NBBY;
  693         else
  694                 start = 0;
  695         end = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
  696 retry:
  697         runlen = 0;
  698         runstart = 0;
  699         for (loc = start; loc < end; loc++) {
  700                 if (bbp[loc] == (char)0xff) {
  701                         runlen = 0;
  702                         continue;
  703                 }
  704 
  705                 /* Start of a run, find the number of high clear bits. */
  706                 if (runlen == 0) {
  707                         bit = fls(bbp[loc]);
  708                         runlen = NBBY - bit;
  709                         runstart = loc * NBBY + bit;
  710                 } else if (bbp[loc] == 0) {
  711                         /* Continue a run. */
  712                         runlen += NBBY;
  713                 } else {
  714                         /*
  715                          * Finish the current run.  If it isn't long
  716                          * enough, start a new one.
  717                          */
  718                         bit = ffs(bbp[loc]) - 1;
  719                         runlen += bit;
  720                         if (runlen >= 8) {
  721                                 bno = runstart;
  722                                 goto gotit;
  723                         }
  724 
  725                         /* Run was too short, start a new one. */
  726                         bit = fls(bbp[loc]);
  727                         runlen = NBBY - bit;
  728                         runstart = loc * NBBY + bit;
  729                 }
  730 
  731                 /* If the current run is long enough, use it. */
  732                 if (runlen >= 8) {
  733                         bno = runstart;
  734                         goto gotit;
  735                 }
  736         }
  737         if (start != 0) {
  738                 end = start;
  739                 start = 0;
  740                 goto retry;
  741         }
  742 
  743         bno = ext2_mapsearch(fs, bbp, bpref);
  744         if (bno < 0){
  745                 brelse(bp);
  746                 EXT2_LOCK(ump);
  747                 return (0);
  748         }
  749 gotit:
  750 #ifdef INVARIANTS
  751         if (isset(bbp, bno)) {
  752                 printf("ext2fs_alloccgblk: cg=%d bno=%jd fs=%s\n",
  753                         cg, (intmax_t)bno, fs->e2fs_fsmnt);
  754                 panic("ext2fs_alloccg: dup alloc");
  755         }
  756 #endif
  757         setbit(bbp, bno);
  758         EXT2_LOCK(ump);
  759         ext2_clusteracct(fs, bbp, cg, bno, -1);
  760         fs->e2fs->e2fs_fbcount--;
  761         fs->e2fs_gd[cg].ext2bgd_nbfree--;
  762         fs->e2fs_fmod = 1;
  763         EXT2_UNLOCK(ump);
  764         bdwrite(bp);
  765         return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
  766 }
  767 
  768 /*
  769  * Determine whether a cluster can be allocated.
  770  */
  771 static daddr_t
  772 ext2_clusteralloc(struct inode *ip, int cg, daddr_t bpref, int len)
  773 {
  774         struct m_ext2fs *fs;
  775         struct ext2mount *ump;
  776         struct buf *bp;
  777         char *bbp;
  778         int bit, error, got, i, loc, run;
  779         int32_t *lp;
  780         daddr_t bno;
  781 
  782         fs = ip->i_e2fs;
  783         ump = ip->i_ump;
  784 
  785         if (fs->e2fs_maxcluster[cg] < len)
  786                 return (0);
  787 
  788         EXT2_UNLOCK(ump);
  789         error = bread(ip->i_devvp,
  790             fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap),
  791             (int)fs->e2fs_bsize, NOCRED, &bp);
  792         if (error)
  793                 goto fail_lock;
  794 
  795         bbp = (char *)bp->b_data;
  796         EXT2_LOCK(ump);
  797         /*
  798          * Check to see if a cluster of the needed size (or bigger) is
  799          * available in this cylinder group.
  800          */
  801         lp = &fs->e2fs_clustersum[cg].cs_sum[len];
  802         for (i = len; i <= fs->e2fs_contigsumsize; i++)
  803                 if (*lp++ > 0)
  804                         break;
  805         if (i > fs->e2fs_contigsumsize) {
  806                 /*
  807                  * Update the cluster summary information to reflect
  808                  * the true maximum-sized cluster so that future cluster
  809                  * allocation requests can avoid reading the bitmap only
  810                  * to find no cluster.
  811                  */
  812                 lp = &fs->e2fs_clustersum[cg].cs_sum[len - 1];
  813                         for (i = len - 1; i > 0; i--)
  814                                 if (*lp-- > 0)
  815                                         break;
  816                 fs->e2fs_maxcluster[cg] = i;
  817                 goto fail;
  818         }
  819         EXT2_UNLOCK(ump);
  820 
  821         /* Search the bitmap to find a big enough cluster like in FFS. */
  822         if (dtog(fs, bpref) != cg)
  823                 bpref = 0;
  824         if (bpref != 0)
  825                 bpref = dtogd(fs, bpref);
  826         loc = bpref / NBBY;
  827         bit = 1 << (bpref % NBBY);
  828         for (run = 0, got = bpref; got < fs->e2fs->e2fs_fpg; got++) {
  829                 if ((bbp[loc] & bit) != 0)
  830                         run = 0;
  831                 else {
  832                         run++;
  833                         if (run == len)
  834                                 break;
  835                 }
  836                 if ((got & (NBBY - 1)) != (NBBY - 1))
  837                         bit <<= 1;
  838                 else {
  839                         loc++;
  840                         bit = 1;
  841                 }
  842         }
  843 
  844         if (got >= fs->e2fs->e2fs_fpg)
  845                 goto fail_lock;
  846 
  847         /* Allocate the cluster that we found. */
  848         for (i = 1; i < len; i++)
  849                 if (!isclr(bbp, got - run + i))
  850                         panic("ext2_clusteralloc: map mismatch");
  851 
  852         bno = got - run + 1;
  853         if (bno >= fs->e2fs->e2fs_fpg)
  854                 panic("ext2_clusteralloc: allocated out of group");
  855 
  856         EXT2_LOCK(ump);
  857         for (i = 0; i < len; i += fs->e2fs_fpb) {
  858                 setbit(bbp, bno + i);
  859                 ext2_clusteracct(fs, bbp, cg, bno + i, -1);
  860                 fs->e2fs->e2fs_fbcount--;
  861                 fs->e2fs_gd[cg].ext2bgd_nbfree--;
  862         }
  863         fs->e2fs_fmod = 1;
  864         EXT2_UNLOCK(ump);
  865 
  866         bdwrite(bp);
  867         return (cg * fs->e2fs->e2fs_fpg + fs->e2fs->e2fs_first_dblock + bno);
  868 
  869 fail_lock:
  870         EXT2_LOCK(ump);
  871 fail:
  872         brelse(bp);
  873         return (0);
  874 }
  875 
  876 /*
  877  * Determine whether an inode can be allocated.
  878  *
  879  * Check to see if an inode is available, and if it is,
  880  * allocate it using tode in the specified cylinder group.
  881  */
  882 static daddr_t
  883 ext2_nodealloccg(struct inode *ip, int cg, daddr_t ipref, int mode)
  884 {
  885         struct m_ext2fs *fs;
  886         struct buf *bp;
  887         struct ext2mount *ump;
  888         int error, start, len;
  889         char *ibp, *loc;
  890         ipref--; /* to avoid a lot of (ipref -1) */
  891         if (ipref == -1)
  892                 ipref = 0;
  893         fs = ip->i_e2fs;
  894         ump = ip->i_ump;
  895         if (fs->e2fs_gd[cg].ext2bgd_nifree == 0)
  896                 return (0);
  897         EXT2_UNLOCK(ump);       
  898         error = bread(ip->i_devvp, fsbtodb(fs,
  899                 fs->e2fs_gd[cg].ext2bgd_i_bitmap),
  900                 (int)fs->e2fs_bsize, NOCRED, &bp);
  901         if (error) {
  902                 brelse(bp);
  903                 EXT2_LOCK(ump);
  904                 return (0);
  905         }
  906         if (fs->e2fs_gd[cg].ext2bgd_nifree == 0) {
  907                 /*
  908                  * Another thread allocated the last i-node in this
  909                  * group while we were waiting for the buffer.
  910                  */
  911                 brelse(bp);
  912                 EXT2_LOCK(ump);
  913                 return (0);
  914         }
  915         ibp = (char *)bp->b_data;
  916         if (ipref) {
  917                 ipref %= fs->e2fs->e2fs_ipg;
  918                 if (isclr(ibp, ipref))
  919                         goto gotit;
  920         }
  921         start = ipref / NBBY;
  922         len = howmany(fs->e2fs->e2fs_ipg - ipref, NBBY);
  923         loc = memcchr(&ibp[start], 0xff, len);
  924         if (loc == NULL) {
  925                 len = start + 1;
  926                 start = 0;
  927                 loc = memcchr(&ibp[start], 0xff, len);
  928                 if (loc == NULL) {
  929                         printf("cg = %d, ipref = %lld, fs = %s\n",
  930                                 cg, (long long)ipref, fs->e2fs_fsmnt);
  931                         panic("ext2fs_nodealloccg: map corrupted");
  932                         /* NOTREACHED */
  933                 }
  934         }
  935         ipref = (loc - ibp) * NBBY + ffs(~*loc) - 1;
  936 gotit:
  937         setbit(ibp, ipref);
  938         EXT2_LOCK(ump);
  939         fs->e2fs_gd[cg].ext2bgd_nifree--;
  940         fs->e2fs->e2fs_ficount--;
  941         fs->e2fs_fmod = 1;
  942         if ((mode & IFMT) == IFDIR) {
  943                 fs->e2fs_gd[cg].ext2bgd_ndirs++;
  944                 fs->e2fs_total_dir++;
  945         }
  946         EXT2_UNLOCK(ump);
  947         bdwrite(bp);
  948         return (cg * fs->e2fs->e2fs_ipg + ipref +1);
  949 }
  950 
  951 /*
  952  * Free a block or fragment.
  953  *
  954  */
  955 void
  956 ext2_blkfree(struct inode *ip, e4fs_daddr_t bno, long size)
  957 {
  958         struct m_ext2fs *fs;
  959         struct buf *bp;
  960         struct ext2mount *ump;
  961         int cg, error;
  962         char *bbp;
  963 
  964         fs = ip->i_e2fs;
  965         ump = ip->i_ump;
  966         cg = dtog(fs, bno);
  967         if ((u_int)bno >= fs->e2fs->e2fs_bcount) {
  968                 printf("bad block %lld, ino %llu\n", (long long)bno,
  969                     (unsigned long long)ip->i_number);
  970                 ext2_fserr(fs, ip->i_uid, "bad block");
  971                 return;
  972         }
  973         error = bread(ip->i_devvp,
  974                 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_b_bitmap),
  975                 (int)fs->e2fs_bsize, NOCRED, &bp);
  976         if (error) {
  977                 brelse(bp);
  978                 return;
  979         }
  980         bbp = (char *)bp->b_data;
  981         bno = dtogd(fs, bno);
  982         if (isclr(bbp, bno)) {
  983                 printf("block = %lld, fs = %s\n",
  984                      (long long)bno, fs->e2fs_fsmnt);
  985                 panic("ext2_blkfree: freeing free block");
  986         }
  987         clrbit(bbp, bno);
  988         EXT2_LOCK(ump);
  989         ext2_clusteracct(fs, bbp, cg, bno, 1);
  990         fs->e2fs->e2fs_fbcount++;
  991         fs->e2fs_gd[cg].ext2bgd_nbfree++;
  992         fs->e2fs_fmod = 1;
  993         EXT2_UNLOCK(ump);
  994         bdwrite(bp);
  995 }
  996 
  997 /*
  998  * Free an inode.
  999  *
 1000  */
 1001 int
 1002 ext2_vfree(struct vnode *pvp, ino_t ino, int mode)
 1003 {
 1004         struct m_ext2fs *fs;
 1005         struct inode *pip;
 1006         struct buf *bp;
 1007         struct ext2mount *ump;
 1008         int error, cg;
 1009         char * ibp;
 1010 
 1011         pip = VTOI(pvp);
 1012         fs = pip->i_e2fs;
 1013         ump = pip->i_ump;
 1014         if ((u_int)ino > fs->e2fs_ipg * fs->e2fs_gcount)
 1015                 panic("ext2_vfree: range: devvp = %p, ino = %ju, fs = %s",
 1016                     pip->i_devvp, (uintmax_t)ino, fs->e2fs_fsmnt);
 1017 
 1018         cg = ino_to_cg(fs, ino);
 1019         error = bread(pip->i_devvp,
 1020                 fsbtodb(fs, fs->e2fs_gd[cg].ext2bgd_i_bitmap),
 1021                 (int)fs->e2fs_bsize, NOCRED, &bp);
 1022         if (error) {
 1023                 brelse(bp);
 1024                 return (0);
 1025         }
 1026         ibp = (char *)bp->b_data;
 1027         ino = (ino - 1) % fs->e2fs->e2fs_ipg;
 1028         if (isclr(ibp, ino)) {
 1029                 printf("ino = %llu, fs = %s\n",
 1030                          (unsigned long long)ino, fs->e2fs_fsmnt);
 1031                 if (fs->e2fs_ronly == 0)
 1032                         panic("ext2_vfree: freeing free inode");
 1033         }
 1034         clrbit(ibp, ino);
 1035         EXT2_LOCK(ump);
 1036         fs->e2fs->e2fs_ficount++;
 1037         fs->e2fs_gd[cg].ext2bgd_nifree++;
 1038         if ((mode & IFMT) == IFDIR) {
 1039                 fs->e2fs_gd[cg].ext2bgd_ndirs--;
 1040                 fs->e2fs_total_dir--;
 1041         }
 1042         fs->e2fs_fmod = 1;
 1043         EXT2_UNLOCK(ump);
 1044         bdwrite(bp);
 1045         return (0);
 1046 }
 1047 
 1048 /*
 1049  * Find a block in the specified cylinder group.
 1050  *
 1051  * It is a panic if a request is made to find a block if none are
 1052  * available.
 1053  */
 1054 static daddr_t
 1055 ext2_mapsearch(struct m_ext2fs *fs, char *bbp, daddr_t bpref)
 1056 {
 1057         char *loc;
 1058         int start, len;
 1059 
 1060         /*
 1061          * find the fragment by searching through the free block
 1062          * map for an appropriate bit pattern
 1063          */
 1064         if (bpref)
 1065                 start = dtogd(fs, bpref) / NBBY;
 1066         else
 1067                 start = 0;
 1068         len = howmany(fs->e2fs->e2fs_fpg, NBBY) - start;
 1069         loc = memcchr(&bbp[start], 0xff, len);
 1070         if (loc == NULL) {
 1071                 len = start + 1;
 1072                 start = 0;
 1073                 loc = memcchr(&bbp[start], 0xff, len);
 1074                 if (loc == NULL) {
 1075                         printf("start = %d, len = %d, fs = %s\n",
 1076                                 start, len, fs->e2fs_fsmnt);
 1077                         panic("ext2_mapsearch: map corrupted");
 1078                         /* NOTREACHED */
 1079                 }
 1080         }
 1081         return ((loc - bbp) * NBBY + ffs(~*loc) - 1);
 1082 }
 1083 
 1084 /*
 1085  * Fserr prints the name of a filesystem with an error diagnostic.
 1086  * 
 1087  * The form of the error message is:
 1088  *      fs: error message
 1089  */
 1090 static void
 1091 ext2_fserr(struct m_ext2fs *fs, uid_t uid, char *cp)
 1092 {
 1093 
 1094         log(LOG_ERR, "uid %u on %s: %s\n", uid, fs->e2fs_fsmnt, cp);
 1095 }
 1096 
 1097 int
 1098 cg_has_sb(int i)
 1099 {
 1100         int a3, a5, a7;
 1101 
 1102         if (i == 0 || i == 1)
 1103                 return 1;
 1104         for (a3 = 3, a5 = 5, a7 = 7;
 1105             a3 <= i || a5 <= i || a7 <= i;
 1106             a3 *= 3, a5 *= 5, a7 *= 7)
 1107                 if (i == a3 || i == a5 || i == a7)
 1108                         return 1;
 1109         return 0;
 1110 }

Cache object: d3606574e51867d4b53f42575435a93a


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