// SPDX-License-Identifier: GPL-2.0-or-later /* * Copyright (C) International Business Machines Corp., 2000-2004 * Portions Copyright (C) Tino Reichardt, 2012 */ #include <linux/fs.h> #include <linux/slab.h> #include "jfs_incore.h" #include "jfs_superblock.h" #include "jfs_dmap.h" #include "jfs_imap.h" #include "jfs_lock.h" #include "jfs_metapage.h" #include "jfs_debug.h" #include "jfs_discard.h" /* * SERIALIZATION of the Block Allocation Map. * * the working state of the block allocation map is accessed in * two directions: * * 1) allocation and free requests that start at the dmap * level and move up through the dmap control pages (i.e. * the vast majority of requests). * * 2) allocation requests that start at dmap control page * level and work down towards the dmaps. * * the serialization scheme used here is as follows. * * requests which start at the bottom are serialized against each * other through buffers and each requests holds onto its buffers * as it works it way up from a single dmap to the required level * of dmap control page. * requests that start at the top are serialized against each other * and request that start from the bottom by the multiple read/single * write inode lock of the bmap inode. requests starting at the top * take this lock in write mode while request starting at the bottom * take the lock in read mode. a single top-down request may proceed * exclusively while multiple bottoms-up requests may proceed * simultaneously (under the protection of busy buffers). * * in addition to information found in dmaps and dmap control pages, * the working state of the block allocation map also includes read/ * write information maintained in the bmap descriptor (i.e. total * free block count, allocation group level free block counts). * a single exclusive lock (BMAP_LOCK) is used to guard this information * in the face of multiple-bottoms up requests. * (lock ordering: IREAD_LOCK, BMAP_LOCK); * * accesses to the persistent state of the block allocation map (limited * to the persistent bitmaps in dmaps) is guarded by (busy) buffers. */ #define BMAP_LOCK_INIT(bmp) … #define BMAP_LOCK(bmp) … #define BMAP_UNLOCK(bmp) … /* * forward references */ static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks); static void dbSplit(dmtree_t *tp, int leafno, int splitsz, int newval, bool is_ctl); static int dbBackSplit(dmtree_t *tp, int leafno, bool is_ctl); static int dbJoin(dmtree_t *tp, int leafno, int newval, bool is_ctl); static void dbAdjTree(dmtree_t *tp, int leafno, int newval, bool is_ctl); static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level); static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results); static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks); static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results); static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks); static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks, int l2nb, s64 * results); static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results); static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results); static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks); static int dbFindBits(u32 word, int l2nb); static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno); static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl); static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks); static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks); static int dbMaxBud(u8 * cp); static int blkstol2(s64 nb); static int cntlz(u32 value); static int cnttz(u32 word); static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks); static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks); static int dbInitDmapTree(struct dmap * dp); static int dbInitTree(struct dmaptree * dtp); static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i); static int dbGetL2AGSize(s64 nblocks); /* * buddy table * * table used for determining buddy sizes within characters of * dmap bitmap words. the characters themselves serve as indexes * into the table, with the table elements yielding the maximum * binary buddy of free bits within the character. */ static const s8 budtab[256] = …; /* * NAME: dbMount() * * FUNCTION: initializate the block allocation map. * * memory is allocated for the in-core bmap descriptor and * the in-core descriptor is initialized from disk. * * PARAMETERS: * ipbmap - pointer to in-core inode for the block map. * * RETURN VALUES: * 0 - success * -ENOMEM - insufficient memory * -EIO - i/o error * -EINVAL - wrong bmap data */ int dbMount(struct inode *ipbmap) { … } /* * NAME: dbUnmount() * * FUNCTION: terminate the block allocation map in preparation for * file system unmount. * * the in-core bmap descriptor is written to disk and * the memory for this descriptor is freed. * * PARAMETERS: * ipbmap - pointer to in-core inode for the block map. * * RETURN VALUES: * 0 - success * -EIO - i/o error */ int dbUnmount(struct inode *ipbmap, int mounterror) { … } /* * dbSync() */ int dbSync(struct inode *ipbmap) { … } /* * NAME: dbFree() * * FUNCTION: free the specified block range from the working block * allocation map. * * the blocks will be free from the working map one dmap * at a time. * * PARAMETERS: * ip - pointer to in-core inode; * blkno - starting block number to be freed. * nblocks - number of blocks to be freed. * * RETURN VALUES: * 0 - success * -EIO - i/o error */ int dbFree(struct inode *ip, s64 blkno, s64 nblocks) { … } /* * NAME: dbUpdatePMap() * * FUNCTION: update the allocation state (free or allocate) of the * specified block range in the persistent block allocation map. * * the blocks will be updated in the persistent map one * dmap at a time. * * PARAMETERS: * ipbmap - pointer to in-core inode for the block map. * free - 'true' if block range is to be freed from the persistent * map; 'false' if it is to be allocated. * blkno - starting block number of the range. * nblocks - number of contiguous blocks in the range. * tblk - transaction block; * * RETURN VALUES: * 0 - success * -EIO - i/o error */ int dbUpdatePMap(struct inode *ipbmap, int free, s64 blkno, s64 nblocks, struct tblock * tblk) { … } /* * NAME: dbNextAG() * * FUNCTION: find the preferred allocation group for new allocations. * * Within the allocation groups, we maintain a preferred * allocation group which consists of a group with at least * average free space. It is the preferred group that we target * new inode allocation towards. The tie-in between inode * allocation and block allocation occurs as we allocate the * first (data) block of an inode and specify the inode (block) * as the allocation hint for this block. * * We try to avoid having more than one open file growing in * an allocation group, as this will lead to fragmentation. * This differs from the old OS/2 method of trying to keep * empty ags around for large allocations. * * PARAMETERS: * ipbmap - pointer to in-core inode for the block map. * * RETURN VALUES: * the preferred allocation group number. */ int dbNextAG(struct inode *ipbmap) { … } /* * NAME: dbAlloc() * * FUNCTION: attempt to allocate a specified number of contiguous free * blocks from the working allocation block map. * * the block allocation policy uses hints and a multi-step * approach. * * for allocation requests smaller than the number of blocks * per dmap, we first try to allocate the new blocks * immediately following the hint. if these blocks are not * available, we try to allocate blocks near the hint. if * no blocks near the hint are available, we next try to * allocate within the same dmap as contains the hint. * * if no blocks are available in the dmap or the allocation * request is larger than the dmap size, we try to allocate * within the same allocation group as contains the hint. if * this does not succeed, we finally try to allocate anywhere * within the aggregate. * * we also try to allocate anywhere within the aggregate * for allocation requests larger than the allocation group * size or requests that specify no hint value. * * PARAMETERS: * ip - pointer to in-core inode; * hint - allocation hint. * nblocks - number of contiguous blocks in the range. * results - on successful return, set to the starting block number * of the newly allocated contiguous range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error */ int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results) { … } /* * NAME: dbReAlloc() * * FUNCTION: attempt to extend a current allocation by a specified * number of blocks. * * this routine attempts to satisfy the allocation request * by first trying to extend the existing allocation in * place by allocating the additional blocks as the blocks * immediately following the current allocation. if these * blocks are not available, this routine will attempt to * allocate a new set of contiguous blocks large enough * to cover the existing allocation plus the additional * number of blocks required. * * PARAMETERS: * ip - pointer to in-core inode requiring allocation. * blkno - starting block of the current allocation. * nblocks - number of contiguous blocks within the current * allocation. * addnblocks - number of blocks to add to the allocation. * results - on successful return, set to the starting block number * of the existing allocation if the existing allocation * was extended in place or to a newly allocated contiguous * range if the existing allocation could not be extended * in place. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error */ int dbReAlloc(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks, s64 * results) { … } /* * NAME: dbExtend() * * FUNCTION: attempt to extend a current allocation by a specified * number of blocks. * * this routine attempts to satisfy the allocation request * by first trying to extend the existing allocation in * place by allocating the additional blocks as the blocks * immediately following the current allocation. * * PARAMETERS: * ip - pointer to in-core inode requiring allocation. * blkno - starting block of the current allocation. * nblocks - number of contiguous blocks within the current * allocation. * addnblocks - number of blocks to add to the allocation. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error */ static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks) { … } /* * NAME: dbAllocNext() * * FUNCTION: attempt to allocate the blocks of the specified block * range within a dmap. * * PARAMETERS: * bmp - pointer to bmap descriptor * dp - pointer to dmap. * blkno - starting block number of the range. * nblocks - number of contiguous free blocks of the range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * serialization: IREAD_LOCK(ipbmap) held on entry/exit; */ static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks) { … } /* * NAME: dbAllocNear() * * FUNCTION: attempt to allocate a number of contiguous free blocks near * a specified block (hint) within a dmap. * * starting with the dmap leaf that covers the hint, we'll * check the next four contiguous leaves for sufficient free * space. if sufficient free space is found, we'll allocate * the desired free space. * * PARAMETERS: * bmp - pointer to bmap descriptor * dp - pointer to dmap. * blkno - block number to allocate near. * nblocks - actual number of contiguous free blocks desired. * l2nb - log2 number of contiguous free blocks desired. * results - on successful return, set to the starting block number * of the newly allocated range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * serialization: IREAD_LOCK(ipbmap) held on entry/exit; */ static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results) { … } /* * NAME: dbAllocAG() * * FUNCTION: attempt to allocate the specified number of contiguous * free blocks within the specified allocation group. * * unless the allocation group size is equal to the number * of blocks per dmap, the dmap control pages will be used to * find the required free space, if available. we start the * search at the highest dmap control page level which * distinctly describes the allocation group's free space * (i.e. the highest level at which the allocation group's * free space is not mixed in with that of any other group). * in addition, we start the search within this level at a * height of the dmapctl dmtree at which the nodes distinctly * describe the allocation group's free space. at this height, * the allocation group's free space may be represented by 1 * or two sub-trees, depending on the allocation group size. * we search the top nodes of these subtrees left to right for * sufficient free space. if sufficient free space is found, * the subtree is searched to find the leftmost leaf that * has free space. once we have made it to the leaf, we * move the search to the next lower level dmap control page * corresponding to this leaf. we continue down the dmap control * pages until we find the dmap that contains or starts the * sufficient free space and we allocate at this dmap. * * if the allocation group size is equal to the dmap size, * we'll start at the dmap corresponding to the allocation * group and attempt the allocation at this level. * * the dmap control page search is also not performed if the * allocation group is completely free and we go to the first * dmap of the allocation group to do the allocation. this is * done because the allocation group may be part (not the first * part) of a larger binary buddy system, causing the dmap * control pages to indicate no free space (NOFREE) within * the allocation group. * * PARAMETERS: * bmp - pointer to bmap descriptor * agno - allocation group number. * nblocks - actual number of contiguous free blocks desired. * l2nb - log2 number of contiguous free blocks desired. * results - on successful return, set to the starting block number * of the newly allocated range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * note: IWRITE_LOCK(ipmap) held on entry/exit; */ static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results) { … } /* * NAME: dbAllocAny() * * FUNCTION: attempt to allocate the specified number of contiguous * free blocks anywhere in the file system. * * dbAllocAny() attempts to find the sufficient free space by * searching down the dmap control pages, starting with the * highest level (i.e. L0, L1, L2) control page. if free space * large enough to satisfy the desired free space is found, the * desired free space is allocated. * * PARAMETERS: * bmp - pointer to bmap descriptor * nblocks - actual number of contiguous free blocks desired. * l2nb - log2 number of contiguous free blocks desired. * results - on successful return, set to the starting block number * of the newly allocated range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * serialization: IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results) { … } /* * NAME: dbDiscardAG() * * FUNCTION: attempt to discard (TRIM) all free blocks of specific AG * * algorithm: * 1) allocate blocks, as large as possible and save them * while holding IWRITE_LOCK on ipbmap * 2) trim all these saved block/length values * 3) mark the blocks free again * * benefit: * - we work only on one ag at some time, minimizing how long we * need to lock ipbmap * - reading / writing the fs is possible most time, even on * trimming * * downside: * - we write two times to the dmapctl and dmap pages * - but for me, this seems the best way, better ideas? * /TR 2012 * * PARAMETERS: * ip - pointer to in-core inode * agno - ag to trim * minlen - minimum value of contiguous blocks * * RETURN VALUES: * s64 - actual number of blocks trimmed */ s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen) { … } /* * NAME: dbFindCtl() * * FUNCTION: starting at a specified dmap control page level and block * number, search down the dmap control levels for a range of * contiguous free blocks large enough to satisfy an allocation * request for the specified number of free blocks. * * if sufficient contiguous free blocks are found, this routine * returns the starting block number within a dmap page that * contains or starts a range of contiqious free blocks that * is sufficient in size. * * PARAMETERS: * bmp - pointer to bmap descriptor * level - starting dmap control page level. * l2nb - log2 number of contiguous free blocks desired. * *blkno - on entry, starting block number for conducting the search. * on successful return, the first block within a dmap page * that contains or starts a range of contiguous free blocks. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * serialization: IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno) { … } /* * NAME: dbAllocCtl() * * FUNCTION: attempt to allocate a specified number of contiguous * blocks starting within a specific dmap. * * this routine is called by higher level routines that search * the dmap control pages above the actual dmaps for contiguous * free space. the result of successful searches by these * routines are the starting block numbers within dmaps, with * the dmaps themselves containing the desired contiguous free * space or starting a contiguous free space of desired size * that is made up of the blocks of one or more dmaps. these * calls should not fail due to insufficent resources. * * this routine is called in some cases where it is not known * whether it will fail due to insufficient resources. more * specifically, this occurs when allocating from an allocation * group whose size is equal to the number of blocks per dmap. * in this case, the dmap control pages are not examined prior * to calling this routine (to save pathlength) and the call * might fail. * * for a request size that fits within a dmap, this routine relies * upon the dmap's dmtree to find the requested contiguous free * space. for request sizes that are larger than a dmap, the * requested free space will start at the first block of the * first dmap (i.e. blkno). * * PARAMETERS: * bmp - pointer to bmap descriptor * nblocks - actual number of contiguous free blocks to allocate. * l2nb - log2 number of contiguous free blocks to allocate. * blkno - starting block number of the dmap to start the allocation * from. * results - on successful return, set to the starting block number * of the newly allocated range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * serialization: IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results) { … } /* * NAME: dbAllocDmapLev() * * FUNCTION: attempt to allocate a specified number of contiguous blocks * from a specified dmap. * * this routine checks if the contiguous blocks are available. * if so, nblocks of blocks are allocated; otherwise, ENOSPC is * returned. * * PARAMETERS: * mp - pointer to bmap descriptor * dp - pointer to dmap to attempt to allocate blocks from. * l2nb - log2 number of contiguous block desired. * nblocks - actual number of contiguous block desired. * results - on successful return, set to the starting block number * of the newly allocated range. * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient disk resources * -EIO - i/o error * * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit; */ static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks, int l2nb, s64 * results) { … } /* * NAME: dbAllocDmap() * * FUNCTION: adjust the disk allocation map to reflect the allocation * of a specified block range within a dmap. * * this routine allocates the specified blocks from the dmap * through a call to dbAllocBits(). if the allocation of the * block range causes the maximum string of free blocks within * the dmap to change (i.e. the value of the root of the dmap's * dmtree), this routine will cause this change to be reflected * up through the appropriate levels of the dmap control pages * by a call to dbAdjCtl() for the L0 dmap control page that * covers this dmap. * * PARAMETERS: * bmp - pointer to bmap descriptor * dp - pointer to dmap to allocate the block range from. * blkno - starting block number of the block to be allocated. * nblocks - number of blocks to be allocated. * * RETURN VALUES: * 0 - success * -EIO - i/o error * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks) { … } /* * NAME: dbFreeDmap() * * FUNCTION: adjust the disk allocation map to reflect the allocation * of a specified block range within a dmap. * * this routine frees the specified blocks from the dmap through * a call to dbFreeBits(). if the deallocation of the block range * causes the maximum string of free blocks within the dmap to * change (i.e. the value of the root of the dmap's dmtree), this * routine will cause this change to be reflected up through the * appropriate levels of the dmap control pages by a call to * dbAdjCtl() for the L0 dmap control page that covers this dmap. * * PARAMETERS: * bmp - pointer to bmap descriptor * dp - pointer to dmap to free the block range from. * blkno - starting block number of the block to be freed. * nblocks - number of blocks to be freed. * * RETURN VALUES: * 0 - success * -EIO - i/o error * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks) { … } /* * NAME: dbAllocBits() * * FUNCTION: allocate a specified block range from a dmap. * * this routine updates the dmap to reflect the working * state allocation of the specified block range. it directly * updates the bits of the working map and causes the adjustment * of the binary buddy system described by the dmap's dmtree * leaves to reflect the bits allocated. it also causes the * dmap's dmtree, as a whole, to reflect the allocated range. * * PARAMETERS: * bmp - pointer to bmap descriptor * dp - pointer to dmap to allocate bits from. * blkno - starting block number of the bits to be allocated. * nblocks - number of bits to be allocated. * * RETURN VALUES: none * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks) { … } /* * NAME: dbFreeBits() * * FUNCTION: free a specified block range from a dmap. * * this routine updates the dmap to reflect the working * state allocation of the specified block range. it directly * updates the bits of the working map and causes the adjustment * of the binary buddy system described by the dmap's dmtree * leaves to reflect the bits freed. it also causes the dmap's * dmtree, as a whole, to reflect the deallocated range. * * PARAMETERS: * bmp - pointer to bmap descriptor * dp - pointer to dmap to free bits from. * blkno - starting block number of the bits to be freed. * nblocks - number of bits to be freed. * * RETURN VALUES: 0 for success * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks) { … } /* * NAME: dbAdjCtl() * * FUNCTION: adjust a dmap control page at a specified level to reflect * the change in a lower level dmap or dmap control page's * maximum string of free blocks (i.e. a change in the root * of the lower level object's dmtree) due to the allocation * or deallocation of a range of blocks with a single dmap. * * on entry, this routine is provided with the new value of * the lower level dmap or dmap control page root and the * starting block number of the block range whose allocation * or deallocation resulted in the root change. this range * is respresented by a single leaf of the current dmapctl * and the leaf will be updated with this value, possibly * causing a binary buddy system within the leaves to be * split or joined. the update may also cause the dmapctl's * dmtree to be updated. * * if the adjustment of the dmap control page, itself, causes its * root to change, this change will be bubbled up to the next dmap * control level by a recursive call to this routine, specifying * the new root value and the next dmap control page level to * be adjusted. * PARAMETERS: * bmp - pointer to bmap descriptor * blkno - the first block of a block range within a dmap. it is * the allocation or deallocation of this block range that * requires the dmap control page to be adjusted. * newval - the new value of the lower level dmap or dmap control * page root. * alloc - 'true' if adjustment is due to an allocation. * level - current level of dmap control page (i.e. L0, L1, L2) to * be adjusted. * * RETURN VALUES: * 0 - success * -EIO - i/o error * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level) { … } /* * NAME: dbSplit() * * FUNCTION: update the leaf of a dmtree with a new value, splitting * the leaf from the binary buddy system of the dmtree's * leaves, as required. * * PARAMETERS: * tp - pointer to the tree containing the leaf. * leafno - the number of the leaf to be updated. * splitsz - the size the binary buddy system starting at the leaf * must be split to, specified as the log2 number of blocks. * newval - the new value for the leaf. * * RETURN VALUES: none * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static void dbSplit(dmtree_t *tp, int leafno, int splitsz, int newval, bool is_ctl) { … } /* * NAME: dbBackSplit() * * FUNCTION: back split the binary buddy system of dmtree leaves * that hold a specified leaf until the specified leaf * starts its own binary buddy system. * * the allocators typically perform allocations at the start * of binary buddy systems and dbSplit() is used to accomplish * any required splits. in some cases, however, allocation * may occur in the middle of a binary system and requires a * back split, with the split proceeding out from the middle of * the system (less efficient) rather than the start of the * system (more efficient). the cases in which a back split * is required are rare and are limited to the first allocation * within an allocation group which is a part (not first part) * of a larger binary buddy system and a few exception cases * in which a previous join operation must be backed out. * * PARAMETERS: * tp - pointer to the tree containing the leaf. * leafno - the number of the leaf to be updated. * * RETURN VALUES: none * * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; */ static int dbBackSplit(dmtree_t *tp, int leafno, bool is_ctl) { … } /* * NAME: dbJoin() * * FUNCTION: update the leaf of a dmtree with a new value, joining * the leaf with other leaves of the dmtree into a multi-leaf * binary buddy system, as required. * * PARAMETERS: * tp - pointer to the tree containing the leaf. * leafno - the number of the leaf to be updated. * newval - the new value for the leaf. * * RETURN VALUES: none */ static int dbJoin(dmtree_t *tp, int leafno, int newval, bool is_ctl) { … } /* * NAME: dbAdjTree() * * FUNCTION: update a leaf of a dmtree with a new value, adjusting * the dmtree, as required, to reflect the new leaf value. * the combination of any buddies must already be done before * this is called. * * PARAMETERS: * tp - pointer to the tree to be adjusted. * leafno - the number of the leaf to be updated. * newval - the new value for the leaf. * * RETURN VALUES: none */ static void dbAdjTree(dmtree_t *tp, int leafno, int newval, bool is_ctl) { … } /* * NAME: dbFindLeaf() * * FUNCTION: search a dmtree_t for sufficient free blocks, returning * the index of a leaf describing the free blocks if * sufficient free blocks are found. * * the search starts at the top of the dmtree_t tree and * proceeds down the tree to the leftmost leaf with sufficient * free space. * * PARAMETERS: * tp - pointer to the tree to be searched. * l2nb - log2 number of free blocks to search for. * leafidx - return pointer to be set to the index of the leaf * describing at least l2nb free blocks if sufficient * free blocks are found. * is_ctl - determines if the tree is of type ctl * * RETURN VALUES: * 0 - success * -ENOSPC - insufficient free blocks. */ static int dbFindLeaf(dmtree_t *tp, int l2nb, int *leafidx, bool is_ctl) { … } /* * NAME: dbFindBits() * * FUNCTION: find a specified number of binary buddy free bits within a * dmap bitmap word value. * * this routine searches the bitmap value for (1 << l2nb) free * bits at (1 << l2nb) alignments within the value. * * PARAMETERS: * word - dmap bitmap word value. * l2nb - number of free bits specified as a log2 number. * * RETURN VALUES: * starting bit number of free bits. */ static int dbFindBits(u32 word, int l2nb) { … } /* * NAME: dbMaxBud(u8 *cp) * * FUNCTION: determine the largest binary buddy string of free * bits within 32-bits of the map. * * PARAMETERS: * cp - pointer to the 32-bit value. * * RETURN VALUES: * largest binary buddy of free bits within a dmap word. */ static int dbMaxBud(u8 * cp) { … } /* * NAME: cnttz(uint word) * * FUNCTION: determine the number of trailing zeros within a 32-bit * value. * * PARAMETERS: * value - 32-bit value to be examined. * * RETURN VALUES: * count of trailing zeros */ static int cnttz(u32 word) { … } /* * NAME: cntlz(u32 value) * * FUNCTION: determine the number of leading zeros within a 32-bit * value. * * PARAMETERS: * value - 32-bit value to be examined. * * RETURN VALUES: * count of leading zeros */ static int cntlz(u32 value) { … } /* * NAME: blkstol2(s64 nb) * * FUNCTION: convert a block count to its log2 value. if the block * count is not a l2 multiple, it is rounded up to the next * larger l2 multiple. * * PARAMETERS: * nb - number of blocks * * RETURN VALUES: * log2 number of blocks */ static int blkstol2(s64 nb) { … } /* * NAME: dbAllocBottomUp() * * FUNCTION: alloc the specified block range from the working block * allocation map. * * the blocks will be alloc from the working map one dmap * at a time. * * PARAMETERS: * ip - pointer to in-core inode; * blkno - starting block number to be freed. * nblocks - number of blocks to be freed. * * RETURN VALUES: * 0 - success * -EIO - i/o error */ int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks) { … } static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, int nblocks) { … } /* * NAME: dbExtendFS() * * FUNCTION: extend bmap from blkno for nblocks; * dbExtendFS() updates bmap ready for dbAllocBottomUp(); * * L2 * | * L1---------------------------------L1 * | | * L0---------L0---------L0 L0---------L0---------L0 * | | | | | | * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm; * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm * * <---old---><----------------------------extend-----------------------> */ int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) { … } /* * dbFinalizeBmap() */ void dbFinalizeBmap(struct inode *ipbmap) { … } /* * NAME: dbInitDmap()/ujfs_idmap_page() * * FUNCTION: initialize working/persistent bitmap of the dmap page * for the specified number of blocks: * * at entry, the bitmaps had been initialized as free (ZEROS); * The number of blocks will only account for the actually * existing blocks. Blocks which don't actually exist in * the aggregate will be marked as allocated (ONES); * * PARAMETERS: * dp - pointer to page of map * nblocks - number of blocks this page * * RETURNS: NONE */ static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks) { … } /* * NAME: dbInitDmapTree()/ujfs_complete_dmap() * * FUNCTION: initialize summary tree of the specified dmap: * * at entry, bitmap of the dmap has been initialized; * * PARAMETERS: * dp - dmap to complete * blkno - starting block number for this dmap * treemax - will be filled in with max free for this dmap * * RETURNS: max free string at the root of the tree */ static int dbInitDmapTree(struct dmap * dp) { … } /* * NAME: dbInitTree()/ujfs_adjtree() * * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl. * * at entry, the leaves of the tree has been initialized * from corresponding bitmap word or root of summary tree * of the child control page; * configure binary buddy system at the leaf level, then * bubble up the values of the leaf nodes up the tree. * * PARAMETERS: * cp - Pointer to the root of the tree * l2leaves- Number of leaf nodes as a power of 2 * l2min - Number of blocks that can be covered by a leaf * as a power of 2 * * RETURNS: max free string at the root of the tree */ static int dbInitTree(struct dmaptree * dtp) { … } /* * dbInitDmapCtl() * * function: initialize dmapctl page */ static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i) { … } /* * NAME: dbGetL2AGSize()/ujfs_getagl2size() * * FUNCTION: Determine log2(allocation group size) from aggregate size * * PARAMETERS: * nblocks - Number of blocks in aggregate * * RETURNS: log2(allocation group size) in aggregate blocks */ static int dbGetL2AGSize(s64 nblocks) { … } /* * NAME: dbMapFileSizeToMapSize() * * FUNCTION: compute number of blocks the block allocation map file * can cover from the map file size; * * RETURNS: Number of blocks which can be covered by this block map file; */ /* * maximum number of map pages at each level including control pages */ #define MAXL0PAGES … #define MAXL1PAGES … /* * convert number of map pages to the zero origin top dmapctl level */ #define BMAPPGTOLEV(npages) … s64 dbMapFileSizeToMapSize(struct inode * ipbmap) { … }
Codebase Browser
linux