Lines Matching refs:dmap
24 * 1) allocation and free requests that start at the dmap
25 * level and move up through the dmap control pages (i.e.
28 * 2) allocation requests that start at dmap control page
35 * as it works it way up from a single dmap to the required level
36 * of dmap control page.
45 * in addition to information found in dmaps and dmap control pages,
64 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
73 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
75 static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno,
78 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
80 static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks,
91 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
93 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
101 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
103 static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks);
104 static int dbInitDmapTree(struct dmap * dp);
113 * dmap bitmap words. the characters themselves serve as indexes
343 * the blocks will be free from the working map one dmap
358 struct dmap *dp;
385 * free the blocks a dmap at a time.
389 /* release previous dmap if any */
394 /* get the buffer for the current dmap. */
401 dp = (struct dmap *) mp->data;
404 * this dmap.
434 * dmap at a time.
457 struct dmap *dp;
478 * update the block state a dmap at a time.
483 /* get the buffer for the current dmap. */
496 dp = (struct dmap *) mp->data;
498 /* determine the bit number and word within the dmap of
500 * are to be updated within this dmap.
506 /* update the bits of the dmap words. the first and last
559 * update dmap lsn
697 * per dmap, we first try to allocate the new blocks
701 * allocate within the same dmap as contains the hint.
703 * if no blocks are available in the dmap or the allocation
704 * request is larger than the dmap size, we try to allocate
732 struct dmap *dp;
797 * single dmap. if so, try to allocate from the dmap containing
803 /* get the buffer for the dmap containing the hint.
811 dp = (struct dmap *) mp->data;
853 * the same dmap as the hint.
989 struct dmap *dp;
1023 * can fit into a dmap, the last block of the current allocation
1033 /* get the buffer for the dmap containing the first block
1043 dp = (struct dmap *) mp->data;
1067 * range within a dmap.
1071 * dp - pointer to dmap.
1082 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
1091 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1095 /* pick up a pointer to the leaves of the dmap tree.
1099 /* determine the bit number and word within the dmap of the
1106 * this dmap.
1123 * will be used for all dmap words fully contained within the
1124 * specified range. within this pass, the leaves of the dmap
1126 * single leaf may describe the free space of multiple dmap
1128 * corresponding to the dmap words of the block range.
1148 /* one or more dmap words are fully contained
1190 * a specified block (hint) within a dmap.
1192 * starting with the dmap leaf that covers the hint, we'll
1199 * dp - pointer to dmap.
1215 struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results)
1221 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1227 /* determine the word within the dmap that holds the hint
1228 * (i.e. blkno). also, determine the last word in the dmap
1243 * of the first block described by this dmap word.
1247 /* if not all bits of the dmap word are free, get the
1248 * starting bit number within the dmap word of the required
1275 * of blocks per dmap, the dmap control pages will be used to
1277 * search at the highest dmap control page level which
1290 * move the search to the next lower level dmap control page
1291 * corresponding to this leaf. we continue down the dmap control
1292 * pages until we find the dmap that contains or starts the
1293 * sufficient free space and we allocate at this dmap.
1295 * if the allocation group size is equal to the dmap size,
1296 * we'll start at the dmap corresponding to the allocation
1299 * the dmap control page search is also not performed if the
1301 * dmap of the allocation group to do the allocation. this is
1303 * part) of a larger binary buddy system, causing the dmap
1348 * 1 dmap), there is no need to search the dmap control page (below)
1350 * group is already fully described by a dmap. in this case, we
1351 * just call dbAllocCtl() to search the dmap tree and allocate the
1356 * two reasons. first, it makes no sense searching the dmap control
1358 * the dmap control pages may indicate that the allocation group
1376 /* the buffer for the dmap control page that fully describes the
1392 /* search the subtree(s) of the dmap control page that describes
1394 * determine how many allocation groups are represented in a dmap
1403 /* dmap control page trees fan-out by 4 and a single allocation
1405 * dmap control page, depending upon the ag size. examine the ag's
1448 * the next level of dmap control pages.
1453 * level dmap control pages. we need to if the number of
1459 /* search the lower level dmap control pages to get
1460 * the starting block number of the dmap that
1502 * searching down the dmap control pages, starting with the
1526 /* starting with the top level dmap control page, search
1527 * down the dmap control levels for sufficient free space.
1529 * block number of the dmap that contains or starts off the
1564 * - we write two times to the dmapctl and dmap pages
1659 * FUNCTION: starting at a specified dmap control page level and block
1660 * number, search down the dmap control levels for a range of
1665 * returns the starting block number within a dmap page that
1671 * level - starting dmap control page level.
1674 * on successful return, the first block within a dmap page
1692 /* starting at the specified dmap control page level and block
1693 * number, search down the dmap control levels for the starting
1694 * block number of a dmap page that contains or starts off
1698 /* get the buffer of the dmap control page for the block
1715 /* search the tree within the dmap control page for
1731 "dmap inconsistent\n");
1738 * the dmap control page (i.e. the leaf) at which free
1743 /* we stop the search at this dmap control page level if
1761 * blocks starting within a specific dmap.
1764 * the dmap control pages above the actual dmaps for contiguous
1775 * group whose size is equal to the number of blocks per dmap.
1776 * in this case, the dmap control pages are not examined prior
1780 * for a request size that fits within a dmap, this routine relies
1781 * upon the dmap's dmtree to find the requested contiguous free
1782 * space. for request sizes that are larger than a dmap, the
1784 * first dmap (i.e. blkno).
1790 * blkno - starting block number of the dmap to start the allocation
1808 struct dmap *dp;
1810 /* check if the allocation request is confined to a single dmap.
1813 /* get the buffer for the dmap.
1819 dp = (struct dmap *) mp->data;
1833 * a dmap boundary.
1837 /* allocate the blocks dmap by dmap.
1840 /* get the buffer for the dmap.
1848 dp = (struct dmap *) mp->data;
1850 /* the dmap better be all free.
1855 "the dmap is not all free\n");
1860 /* determine how many blocks to allocate from this dmap.
1864 /* allocate the blocks from the dmap.
1889 /* try to backout the allocations dmap by dmap.
1893 /* get the buffer for this dmap.
1905 dp = (struct dmap *) mp->data;
1907 /* free the blocks is this dmap.
1931 * from a specified dmap.
1939 * dp - pointer to dmap to attempt to allocate blocks from.
1955 struct dmap * dp, int nblocks, int l2nb, s64 * results)
1963 /* search the tree within the dmap page for sufficient
1978 /* if not all bits of the dmap word are free, get the starting
1979 * bit number within the dmap word of the required string of free
1997 * of a specified block range within a dmap.
1999 * this routine allocates the specified blocks from the dmap
2002 * the dmap to change (i.e. the value of the root of the dmap's
2004 * up through the appropriate levels of the dmap control pages
2005 * by a call to dbAdjCtl() for the L0 dmap control page that
2006 * covers this dmap.
2010 * dp - pointer to dmap to allocate the block range from.
2020 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2027 * of the dmap tree.
2038 /* root changed. bubble the change up to the dmap control pages.
2053 * of a specified block range within a dmap.
2055 * this routine frees the specified blocks from the dmap through
2057 * causes the maximum string of free blocks within the dmap to
2058 * change (i.e. the value of the root of the dmap's dmtree), this
2060 * appropriate levels of the dmap control pages by a call to
2061 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
2065 * dp - pointer to dmap to free the block range from.
2075 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2082 * of the dmap tree.
2093 /* root changed. bubble the change up to the dmap control pages.
2101 * to back split the dmap tree if the deallocation caused
2118 * FUNCTION: allocate a specified block range from a dmap.
2120 * this routine updates the dmap to reflect the working
2123 * of the binary buddy system described by the dmap's dmtree
2125 * dmap's dmtree, as a whole, to reflect the allocated range.
2129 * dp - pointer to dmap to allocate bits from.
2137 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2145 /* pick up a pointer to the leaves of the dmap tree */
2148 /* determine the bit number and word within the dmap of the
2154 /* block range better be within the dmap */
2157 /* allocate the bits of the dmap's words corresponding to the block
2162 * updating the leaf corresponding to the dmap word. a single pass
2163 * will be used for all dmap words fully contained within the
2165 * dmap words will be marked as free in a single shot and the leaves
2167 * multiple dmap words, so we may update only a subset of the actual
2168 * leaves corresponding to the dmap words of the block range.
2181 * this dmap word.
2186 /* update the leaf for this dmap word. in addition
2188 * of the updated dmap word, dbSplit() will split
2196 /* one or more dmap words are fully contained
2234 /* get the number of dmap words handled */
2241 /* update the free count for this dmap */
2265 * FUNCTION: free a specified block range from a dmap.
2267 * this routine updates the dmap to reflect the working
2270 * of the binary buddy system described by the dmap's dmtree
2271 * leaves to reflect the bits freed. it also causes the dmap's
2276 * dp - pointer to dmap to free bits from.
2284 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2292 /* determine the bit number and word within the dmap of the
2298 /* block range better be within the dmap.
2307 * the leaf corresponding to the dmap word. a single pass will be used
2308 * for all dmap words fully contained within the specified range.
2309 * within this pass, the bits of all fully contained dmap words will
2311 * single leaf may describe the free space of multiple dmap words,
2313 * to the dmap words of the block range.
2330 * dmap word.
2336 /* update the leaf for this dmap word.
2345 /* one or more dmap words are fully contained
2376 /* get the number of dmap words handled.
2384 /* update the free count for this dmap.
2429 * FUNCTION: adjust a dmap control page at a specified level to reflect
2430 * the change in a lower level dmap or dmap control page's
2433 * or deallocation of a range of blocks with a single dmap.
2436 * the lower level dmap or dmap control page root and the
2445 * if the adjustment of the dmap control page, itself, causes its
2446 * root to change, this change will be bubbled up to the next dmap
2448 * the new root value and the next dmap control page level to
2452 * blkno - the first block of a block range within a dmap. it is
2454 * requires the dmap control page to be adjusted.
2455 * newval - the new value of the lower level dmap or dmap control
2458 * level - current level of dmap control page (i.e. L0, L1, L2) to
2477 /* get the buffer for the dmap control page for the specified
2493 * the index within the dmap control tree.
2540 /* check if the root of the current dmap control page changed due
2541 * to the update and if the current dmap control page is not at
2545 * reflect the change in root for the current dmap control page.
2552 /* bubble up the new root of this dmap control page to
2560 * current dmap control page.
2655 /* adjust the dmap tree to reflect the specified leaf's new
2993 * dmap bitmap word value.
2999 * word - dmap bitmap word value.
3046 * largest binary buddy of free bits within a dmap word.
3171 * the blocks will be alloc from the working map one dmap
3186 struct dmap *dp;
3198 * allocate the blocks a dmap at a time.
3202 /* release previous dmap if any */
3207 /* get the buffer for the current dmap. */
3214 dp = (struct dmap *) mp->data;
3217 * this dmap.
3238 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
3247 * of the dmap tree.
3251 /* determine the bit number and word within the dmap of the
3257 /* block range better be within the dmap */
3260 /* allocate the bits of the dmap's words corresponding to the block
3265 * updating the leaf corresponding to the dmap word. a single pass
3266 * will be used for all dmap words fully contained within the
3268 * dmap words will be marked as free in a single shot and the leaves
3270 * multiple dmap words, so we may update only a subset of the actual
3271 * leaves corresponding to the dmap words of the block range.
3284 * this dmap word.
3291 /* one or more dmap words are fully contained
3305 /* update the free count for this dmap */
3331 /* root changed. bubble the change up to the dmap control pages.
3368 struct dmap *dp;
3383 * the mkfs hidden dmap page.
3499 /* compute start dmap */
3514 /* compute start dmap */
3517 p += nbperpage; /* 1st dmap of L0.j */
3521 * extend each dmap in L0
3525 * reconstruct the dmap page, and
3529 /* read in dmap page: */
3536 /* assign/init dmap page */
3545 dp = (struct dmap *) mp->data;
3561 } /* for each dmap in a L0 */
3708 * FUNCTION: initialize working/persistent bitmap of the dmap page
3722 static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks)
3726 /* starting block number within the dmap */
3813 * FUNCTION: initialize summary tree of the specified dmap:
3815 * at entry, bitmap of the dmap has been initialized;
3818 * dp - dmap to complete
3819 * blkno - starting block number for this dmap
3820 * treemax - will be filled in with max free for this dmap
3824 static int dbInitDmapTree(struct dmap * dp)
3846 /* build the dmap's binary buddy summary tree */
3854 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3958 * low level dmapctl or dmap).
3964 /* build the dmap's binary buddy summary tree */
4038 /* At each level, accumulate the number of dmap pages covered by