diff options
Diffstat (limited to 'fs/jfs/jfs_dmap.c')
-rw-r--r-- | fs/jfs/jfs_dmap.c | 180 |
1 files changed, 90 insertions, 90 deletions
diff --git a/fs/jfs/jfs_dmap.c b/fs/jfs/jfs_dmap.c index f05ebb629182..23546c8fd48b 100644 --- a/fs/jfs/jfs_dmap.c +++ b/fs/jfs/jfs_dmap.c | |||
@@ -3,16 +3,16 @@ | |||
3 | * | 3 | * |
4 | * This program is free software; you can redistribute it and/or modify | 4 | * This program is free software; you can redistribute it and/or modify |
5 | * it under the terms of the GNU General Public License as published by | 5 | * it under the terms of the GNU General Public License as published by |
6 | * the Free Software Foundation; either version 2 of the License, or | 6 | * the Free Software Foundation; either version 2 of the License, or |
7 | * (at your option) any later version. | 7 | * (at your option) any later version. |
8 | * | 8 | * |
9 | * This program is distributed in the hope that it will be useful, | 9 | * This program is distributed in the hope that it will be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See | 11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See |
12 | * the GNU General Public License for more details. | 12 | * the GNU General Public License for more details. |
13 | * | 13 | * |
14 | * You should have received a copy of the GNU General Public License | 14 | * You should have received a copy of the GNU General Public License |
15 | * along with this program; if not, write to the Free Software | 15 | * along with this program; if not, write to the Free Software |
16 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | 16 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
17 | */ | 17 | */ |
18 | 18 | ||
@@ -30,28 +30,28 @@ | |||
30 | * | 30 | * |
31 | * the working state of the block allocation map is accessed in | 31 | * the working state of the block allocation map is accessed in |
32 | * two directions: | 32 | * two directions: |
33 | * | 33 | * |
34 | * 1) allocation and free requests that start at the dmap | 34 | * 1) allocation and free requests that start at the dmap |
35 | * level and move up through the dmap control pages (i.e. | 35 | * level and move up through the dmap control pages (i.e. |
36 | * the vast majority of requests). | 36 | * the vast majority of requests). |
37 | * | 37 | * |
38 | * 2) allocation requests that start at dmap control page | 38 | * 2) allocation requests that start at dmap control page |
39 | * level and work down towards the dmaps. | 39 | * level and work down towards the dmaps. |
40 | * | ||
41 | * the serialization scheme used here is as follows. | ||
42 | * | 40 | * |
43 | * requests which start at the bottom are serialized against each | 41 | * the serialization scheme used here is as follows. |
44 | * other through buffers and each requests holds onto its buffers | 42 | * |
45 | * as it works it way up from a single dmap to the required level | 43 | * requests which start at the bottom are serialized against each |
44 | * other through buffers and each requests holds onto its buffers | ||
45 | * as it works it way up from a single dmap to the required level | ||
46 | * of dmap control page. | 46 | * of dmap control page. |
47 | * requests that start at the top are serialized against each other | 47 | * requests that start at the top are serialized against each other |
48 | * and request that start from the bottom by the multiple read/single | 48 | * and request that start from the bottom by the multiple read/single |
49 | * write inode lock of the bmap inode. requests starting at the top | 49 | * write inode lock of the bmap inode. requests starting at the top |
50 | * take this lock in write mode while request starting at the bottom | 50 | * take this lock in write mode while request starting at the bottom |
51 | * take the lock in read mode. a single top-down request may proceed | 51 | * take the lock in read mode. a single top-down request may proceed |
52 | * exclusively while multiple bottoms-up requests may proceed | 52 | * exclusively while multiple bottoms-up requests may proceed |
53 | * simultaneously (under the protection of busy buffers). | 53 | * simultaneously (under the protection of busy buffers). |
54 | * | 54 | * |
55 | * in addition to information found in dmaps and dmap control pages, | 55 | * in addition to information found in dmaps and dmap control pages, |
56 | * the working state of the block allocation map also includes read/ | 56 | * the working state of the block allocation map also includes read/ |
57 | * write information maintained in the bmap descriptor (i.e. total | 57 | * write information maintained in the bmap descriptor (i.e. total |
@@ -59,7 +59,7 @@ | |||
59 | * a single exclusive lock (BMAP_LOCK) is used to guard this information | 59 | * a single exclusive lock (BMAP_LOCK) is used to guard this information |
60 | * in the face of multiple-bottoms up requests. | 60 | * in the face of multiple-bottoms up requests. |
61 | * (lock ordering: IREAD_LOCK, BMAP_LOCK); | 61 | * (lock ordering: IREAD_LOCK, BMAP_LOCK); |
62 | * | 62 | * |
63 | * accesses to the persistent state of the block allocation map (limited | 63 | * accesses to the persistent state of the block allocation map (limited |
64 | * to the persistent bitmaps in dmaps) is guarded by (busy) buffers. | 64 | * to the persistent bitmaps in dmaps) is guarded by (busy) buffers. |
65 | */ | 65 | */ |
@@ -120,7 +120,7 @@ static int dbGetL2AGSize(s64 nblocks); | |||
120 | /* | 120 | /* |
121 | * buddy table | 121 | * buddy table |
122 | * | 122 | * |
123 | * table used for determining buddy sizes within characters of | 123 | * table used for determining buddy sizes within characters of |
124 | * dmap bitmap words. the characters themselves serve as indexes | 124 | * dmap bitmap words. the characters themselves serve as indexes |
125 | * into the table, with the table elements yielding the maximum | 125 | * into the table, with the table elements yielding the maximum |
126 | * binary buddy of free bits within the character. | 126 | * binary buddy of free bits within the character. |
@@ -146,7 +146,7 @@ static const s8 budtab[256] = { | |||
146 | 146 | ||
147 | 147 | ||
148 | /* | 148 | /* |
149 | * NAME: dbMount() | 149 | * NAME: dbMount() |
150 | * | 150 | * |
151 | * FUNCTION: initializate the block allocation map. | 151 | * FUNCTION: initializate the block allocation map. |
152 | * | 152 | * |
@@ -223,12 +223,12 @@ int dbMount(struct inode *ipbmap) | |||
223 | 223 | ||
224 | 224 | ||
225 | /* | 225 | /* |
226 | * NAME: dbUnmount() | 226 | * NAME: dbUnmount() |
227 | * | 227 | * |
228 | * FUNCTION: terminate the block allocation map in preparation for | 228 | * FUNCTION: terminate the block allocation map in preparation for |
229 | * file system unmount. | 229 | * file system unmount. |
230 | * | 230 | * |
231 | * the in-core bmap descriptor is written to disk and | 231 | * the in-core bmap descriptor is written to disk and |
232 | * the memory for this descriptor is freed. | 232 | * the memory for this descriptor is freed. |
233 | * | 233 | * |
234 | * PARAMETERS: | 234 | * PARAMETERS: |
@@ -311,7 +311,7 @@ int dbSync(struct inode *ipbmap) | |||
311 | 311 | ||
312 | 312 | ||
313 | /* | 313 | /* |
314 | * NAME: dbFree() | 314 | * NAME: dbFree() |
315 | * | 315 | * |
316 | * FUNCTION: free the specified block range from the working block | 316 | * FUNCTION: free the specified block range from the working block |
317 | * allocation map. | 317 | * allocation map. |
@@ -397,7 +397,7 @@ int dbFree(struct inode *ip, s64 blkno, s64 nblocks) | |||
397 | * | 397 | * |
398 | * FUNCTION: update the allocation state (free or allocate) of the | 398 | * FUNCTION: update the allocation state (free or allocate) of the |
399 | * specified block range in the persistent block allocation map. | 399 | * specified block range in the persistent block allocation map. |
400 | * | 400 | * |
401 | * the blocks will be updated in the persistent map one | 401 | * the blocks will be updated in the persistent map one |
402 | * dmap at a time. | 402 | * dmap at a time. |
403 | * | 403 | * |
@@ -475,7 +475,7 @@ dbUpdatePMap(struct inode *ipbmap, | |||
475 | /* update the bits of the dmap words. the first and last | 475 | /* update the bits of the dmap words. the first and last |
476 | * words may only have a subset of their bits updated. if | 476 | * words may only have a subset of their bits updated. if |
477 | * this is the case, we'll work against that word (i.e. | 477 | * this is the case, we'll work against that word (i.e. |
478 | * partial first and/or last) only in a single pass. a | 478 | * partial first and/or last) only in a single pass. a |
479 | * single pass will also be used to update all words that | 479 | * single pass will also be used to update all words that |
480 | * are to have all their bits updated. | 480 | * are to have all their bits updated. |
481 | */ | 481 | */ |
@@ -662,11 +662,11 @@ unlock: | |||
662 | * the block allocation policy uses hints and a multi-step | 662 | * the block allocation policy uses hints and a multi-step |
663 | * approach. | 663 | * approach. |
664 | * | 664 | * |
665 | * for allocation requests smaller than the number of blocks | 665 | * for allocation requests smaller than the number of blocks |
666 | * per dmap, we first try to allocate the new blocks | 666 | * per dmap, we first try to allocate the new blocks |
667 | * immediately following the hint. if these blocks are not | 667 | * immediately following the hint. if these blocks are not |
668 | * available, we try to allocate blocks near the hint. if | 668 | * available, we try to allocate blocks near the hint. if |
669 | * no blocks near the hint are available, we next try to | 669 | * no blocks near the hint are available, we next try to |
670 | * allocate within the same dmap as contains the hint. | 670 | * allocate within the same dmap as contains the hint. |
671 | * | 671 | * |
672 | * if no blocks are available in the dmap or the allocation | 672 | * if no blocks are available in the dmap or the allocation |
@@ -713,7 +713,7 @@ int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results) | |||
713 | #endif /* _STILL_TO_PORT */ | 713 | #endif /* _STILL_TO_PORT */ |
714 | 714 | ||
715 | /* get the log2 number of blocks to be allocated. | 715 | /* get the log2 number of blocks to be allocated. |
716 | * if the number of blocks is not a log2 multiple, | 716 | * if the number of blocks is not a log2 multiple, |
717 | * it will be rounded up to the next log2 multiple. | 717 | * it will be rounded up to the next log2 multiple. |
718 | */ | 718 | */ |
719 | l2nb = BLKSTOL2(nblocks); | 719 | l2nb = BLKSTOL2(nblocks); |
@@ -906,7 +906,7 @@ int dbAllocExact(struct inode *ip, s64 blkno, int nblocks) | |||
906 | * validate extent request: | 906 | * validate extent request: |
907 | * | 907 | * |
908 | * note: defragfs policy: | 908 | * note: defragfs policy: |
909 | * max 64 blocks will be moved. | 909 | * max 64 blocks will be moved. |
910 | * allocation request size must be satisfied from a single dmap. | 910 | * allocation request size must be satisfied from a single dmap. |
911 | */ | 911 | */ |
912 | if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) { | 912 | if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) { |
@@ -1333,7 +1333,7 @@ dbAllocNear(struct bmap * bmp, | |||
1333 | * or two sub-trees, depending on the allocation group size. | 1333 | * or two sub-trees, depending on the allocation group size. |
1334 | * we search the top nodes of these subtrees left to right for | 1334 | * we search the top nodes of these subtrees left to right for |
1335 | * sufficient free space. if sufficient free space is found, | 1335 | * sufficient free space. if sufficient free space is found, |
1336 | * the subtree is searched to find the leftmost leaf that | 1336 | * the subtree is searched to find the leftmost leaf that |
1337 | * has free space. once we have made it to the leaf, we | 1337 | * has free space. once we have made it to the leaf, we |
1338 | * move the search to the next lower level dmap control page | 1338 | * move the search to the next lower level dmap control page |
1339 | * corresponding to this leaf. we continue down the dmap control | 1339 | * corresponding to this leaf. we continue down the dmap control |
@@ -1398,7 +1398,7 @@ dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results) | |||
1398 | * that fully describes the allocation group since the allocation | 1398 | * that fully describes the allocation group since the allocation |
1399 | * group is already fully described by a dmap. in this case, we | 1399 | * group is already fully described by a dmap. in this case, we |
1400 | * just call dbAllocCtl() to search the dmap tree and allocate the | 1400 | * just call dbAllocCtl() to search the dmap tree and allocate the |
1401 | * required space if available. | 1401 | * required space if available. |
1402 | * | 1402 | * |
1403 | * if the allocation group is completely free, dbAllocCtl() is | 1403 | * if the allocation group is completely free, dbAllocCtl() is |
1404 | * also called to allocate the required space. this is done for | 1404 | * also called to allocate the required space. this is done for |
@@ -1450,7 +1450,7 @@ dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results) | |||
1450 | (1 << (L2LPERCTL - (bmp->db_agheigth << 1))) / bmp->db_agwidth; | 1450 | (1 << (L2LPERCTL - (bmp->db_agheigth << 1))) / bmp->db_agwidth; |
1451 | ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1)); | 1451 | ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1)); |
1452 | 1452 | ||
1453 | /* dmap control page trees fan-out by 4 and a single allocation | 1453 | /* dmap control page trees fan-out by 4 and a single allocation |
1454 | * group may be described by 1 or 2 subtrees within the ag level | 1454 | * group may be described by 1 or 2 subtrees within the ag level |
1455 | * dmap control page, depending upon the ag size. examine the ag's | 1455 | * dmap control page, depending upon the ag size. examine the ag's |
1456 | * subtrees for sufficient free space, starting with the leftmost | 1456 | * subtrees for sufficient free space, starting with the leftmost |
@@ -1633,7 +1633,7 @@ static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno) | |||
1633 | 1633 | ||
1634 | /* starting at the specified dmap control page level and block | 1634 | /* starting at the specified dmap control page level and block |
1635 | * number, search down the dmap control levels for the starting | 1635 | * number, search down the dmap control levels for the starting |
1636 | * block number of a dmap page that contains or starts off | 1636 | * block number of a dmap page that contains or starts off |
1637 | * sufficient free blocks. | 1637 | * sufficient free blocks. |
1638 | */ | 1638 | */ |
1639 | for (lev = level, b = *blkno; lev >= 0; lev--) { | 1639 | for (lev = level, b = *blkno; lev >= 0; lev--) { |
@@ -1677,7 +1677,7 @@ static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno) | |||
1677 | } | 1677 | } |
1678 | 1678 | ||
1679 | /* adjust the block number to reflect the location within | 1679 | /* adjust the block number to reflect the location within |
1680 | * the dmap control page (i.e. the leaf) at which free | 1680 | * the dmap control page (i.e. the leaf) at which free |
1681 | * space was found. | 1681 | * space was found. |
1682 | */ | 1682 | */ |
1683 | b += (((s64) leafidx) << budmin); | 1683 | b += (((s64) leafidx) << budmin); |
@@ -1700,12 +1700,12 @@ static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno) | |||
1700 | * NAME: dbAllocCtl() | 1700 | * NAME: dbAllocCtl() |
1701 | * | 1701 | * |
1702 | * FUNCTION: attempt to allocate a specified number of contiguous | 1702 | * FUNCTION: attempt to allocate a specified number of contiguous |
1703 | * blocks starting within a specific dmap. | 1703 | * blocks starting within a specific dmap. |
1704 | * | 1704 | * |
1705 | * this routine is called by higher level routines that search | 1705 | * this routine is called by higher level routines that search |
1706 | * the dmap control pages above the actual dmaps for contiguous | 1706 | * the dmap control pages above the actual dmaps for contiguous |
1707 | * free space. the result of successful searches by these | 1707 | * free space. the result of successful searches by these |
1708 | * routines are the starting block numbers within dmaps, with | 1708 | * routines are the starting block numbers within dmaps, with |
1709 | * the dmaps themselves containing the desired contiguous free | 1709 | * the dmaps themselves containing the desired contiguous free |
1710 | * space or starting a contiguous free space of desired size | 1710 | * space or starting a contiguous free space of desired size |
1711 | * that is made up of the blocks of one or more dmaps. these | 1711 | * that is made up of the blocks of one or more dmaps. these |
@@ -1872,14 +1872,14 @@ dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results) | |||
1872 | * | 1872 | * |
1873 | * FUNCTION: attempt to allocate a specified number of contiguous blocks | 1873 | * FUNCTION: attempt to allocate a specified number of contiguous blocks |
1874 | * from a specified dmap. | 1874 | * from a specified dmap. |
1875 | * | 1875 | * |
1876 | * this routine checks if the contiguous blocks are available. | 1876 | * this routine checks if the contiguous blocks are available. |
1877 | * if so, nblocks of blocks are allocated; otherwise, ENOSPC is | 1877 | * if so, nblocks of blocks are allocated; otherwise, ENOSPC is |
1878 | * returned. | 1878 | * returned. |
1879 | * | 1879 | * |
1880 | * PARAMETERS: | 1880 | * PARAMETERS: |
1881 | * mp - pointer to bmap descriptor | 1881 | * mp - pointer to bmap descriptor |
1882 | * dp - pointer to dmap to attempt to allocate blocks from. | 1882 | * dp - pointer to dmap to attempt to allocate blocks from. |
1883 | * l2nb - log2 number of contiguous block desired. | 1883 | * l2nb - log2 number of contiguous block desired. |
1884 | * nblocks - actual number of contiguous block desired. | 1884 | * nblocks - actual number of contiguous block desired. |
1885 | * results - on successful return, set to the starting block number | 1885 | * results - on successful return, set to the starting block number |
@@ -1890,7 +1890,7 @@ dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results) | |||
1890 | * -ENOSPC - insufficient disk resources | 1890 | * -ENOSPC - insufficient disk resources |
1891 | * -EIO - i/o error | 1891 | * -EIO - i/o error |
1892 | * | 1892 | * |
1893 | * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or | 1893 | * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or |
1894 | * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit; | 1894 | * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit; |
1895 | */ | 1895 | */ |
1896 | static int | 1896 | static int |
@@ -2032,7 +2032,7 @@ static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
2032 | 2032 | ||
2033 | /* root changed. bubble the change up to the dmap control pages. | 2033 | /* root changed. bubble the change up to the dmap control pages. |
2034 | * if the adjustment of the upper level control pages fails, | 2034 | * if the adjustment of the upper level control pages fails, |
2035 | * backout the deallocation. | 2035 | * backout the deallocation. |
2036 | */ | 2036 | */ |
2037 | if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) { | 2037 | if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) { |
2038 | word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; | 2038 | word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; |
@@ -2245,7 +2245,7 @@ static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
2245 | * words (i.e. partial first and/or last) on an individual basis | 2245 | * words (i.e. partial first and/or last) on an individual basis |
2246 | * (a single pass), freeing the bits of interest by hand and updating | 2246 | * (a single pass), freeing the bits of interest by hand and updating |
2247 | * the leaf corresponding to the dmap word. a single pass will be used | 2247 | * the leaf corresponding to the dmap word. a single pass will be used |
2248 | * for all dmap words fully contained within the specified range. | 2248 | * for all dmap words fully contained within the specified range. |
2249 | * within this pass, the bits of all fully contained dmap words will | 2249 | * within this pass, the bits of all fully contained dmap words will |
2250 | * be marked as free in a single shot and the leaves will be updated. a | 2250 | * be marked as free in a single shot and the leaves will be updated. a |
2251 | * single leaf may describe the free space of multiple dmap words, | 2251 | * single leaf may describe the free space of multiple dmap words, |
@@ -2267,7 +2267,7 @@ static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
2267 | */ | 2267 | */ |
2268 | if (nb < DBWORD) { | 2268 | if (nb < DBWORD) { |
2269 | /* free (zero) the appropriate bits within this | 2269 | /* free (zero) the appropriate bits within this |
2270 | * dmap word. | 2270 | * dmap word. |
2271 | */ | 2271 | */ |
2272 | dp->wmap[word] &= | 2272 | dp->wmap[word] &= |
2273 | cpu_to_le32(~(ONES << (DBWORD - nb) | 2273 | cpu_to_le32(~(ONES << (DBWORD - nb) |
@@ -2327,7 +2327,7 @@ static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
2327 | 2327 | ||
2328 | BMAP_LOCK(bmp); | 2328 | BMAP_LOCK(bmp); |
2329 | 2329 | ||
2330 | /* update the free count for the allocation group and | 2330 | /* update the free count for the allocation group and |
2331 | * map. | 2331 | * map. |
2332 | */ | 2332 | */ |
2333 | agno = blkno >> bmp->db_agl2size; | 2333 | agno = blkno >> bmp->db_agl2size; |
@@ -2378,7 +2378,7 @@ static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
2378 | * or deallocation resulted in the root change. this range | 2378 | * or deallocation resulted in the root change. this range |
2379 | * is respresented by a single leaf of the current dmapctl | 2379 | * is respresented by a single leaf of the current dmapctl |
2380 | * and the leaf will be updated with this value, possibly | 2380 | * and the leaf will be updated with this value, possibly |
2381 | * causing a binary buddy system within the leaves to be | 2381 | * causing a binary buddy system within the leaves to be |
2382 | * split or joined. the update may also cause the dmapctl's | 2382 | * split or joined. the update may also cause the dmapctl's |
2383 | * dmtree to be updated. | 2383 | * dmtree to be updated. |
2384 | * | 2384 | * |
@@ -2590,7 +2590,7 @@ static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval) | |||
2590 | } | 2590 | } |
2591 | } | 2591 | } |
2592 | 2592 | ||
2593 | /* adjust the dmap tree to reflect the specified leaf's new | 2593 | /* adjust the dmap tree to reflect the specified leaf's new |
2594 | * value. | 2594 | * value. |
2595 | */ | 2595 | */ |
2596 | dbAdjTree(tp, leafno, newval); | 2596 | dbAdjTree(tp, leafno, newval); |
@@ -2638,7 +2638,7 @@ static int dbBackSplit(dmtree_t * tp, int leafno) | |||
2638 | /* the back split is accomplished by iteratively finding the leaf | 2638 | /* the back split is accomplished by iteratively finding the leaf |
2639 | * that starts the buddy system that contains the specified leaf and | 2639 | * that starts the buddy system that contains the specified leaf and |
2640 | * splitting that system in two. this iteration continues until | 2640 | * splitting that system in two. this iteration continues until |
2641 | * the specified leaf becomes the start of a buddy system. | 2641 | * the specified leaf becomes the start of a buddy system. |
2642 | * | 2642 | * |
2643 | * determine maximum possible l2 size for the specified leaf. | 2643 | * determine maximum possible l2 size for the specified leaf. |
2644 | */ | 2644 | */ |
@@ -2853,7 +2853,7 @@ static void dbAdjTree(dmtree_t * tp, int leafno, int newval) | |||
2853 | * NAME: dbFindLeaf() | 2853 | * NAME: dbFindLeaf() |
2854 | * | 2854 | * |
2855 | * FUNCTION: search a dmtree_t for sufficient free blocks, returning | 2855 | * FUNCTION: search a dmtree_t for sufficient free blocks, returning |
2856 | * the index of a leaf describing the free blocks if | 2856 | * the index of a leaf describing the free blocks if |
2857 | * sufficient free blocks are found. | 2857 | * sufficient free blocks are found. |
2858 | * | 2858 | * |
2859 | * the search starts at the top of the dmtree_t tree and | 2859 | * the search starts at the top of the dmtree_t tree and |
@@ -2869,7 +2869,7 @@ static void dbAdjTree(dmtree_t * tp, int leafno, int newval) | |||
2869 | * | 2869 | * |
2870 | * RETURN VALUES: | 2870 | * RETURN VALUES: |
2871 | * 0 - success | 2871 | * 0 - success |
2872 | * -ENOSPC - insufficient free blocks. | 2872 | * -ENOSPC - insufficient free blocks. |
2873 | */ | 2873 | */ |
2874 | static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx) | 2874 | static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx) |
2875 | { | 2875 | { |
@@ -3090,7 +3090,7 @@ static int blkstol2(s64 nb) | |||
3090 | 3090 | ||
3091 | 3091 | ||
3092 | /* | 3092 | /* |
3093 | * NAME: dbAllocBottomUp() | 3093 | * NAME: dbAllocBottomUp() |
3094 | * | 3094 | * |
3095 | * FUNCTION: alloc the specified block range from the working block | 3095 | * FUNCTION: alloc the specified block range from the working block |
3096 | * allocation map. | 3096 | * allocation map. |
@@ -3241,7 +3241,7 @@ static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
3241 | BMAP_LOCK(bmp); | 3241 | BMAP_LOCK(bmp); |
3242 | 3242 | ||
3243 | /* if this allocation group is completely free, | 3243 | /* if this allocation group is completely free, |
3244 | * update the highest active allocation group number | 3244 | * update the highest active allocation group number |
3245 | * if this allocation group is the new max. | 3245 | * if this allocation group is the new max. |
3246 | */ | 3246 | */ |
3247 | agno = blkno >> bmp->db_agl2size; | 3247 | agno = blkno >> bmp->db_agl2size; |
@@ -3273,7 +3273,7 @@ static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
3273 | * NAME: dbExtendFS() | 3273 | * NAME: dbExtendFS() |
3274 | * | 3274 | * |
3275 | * FUNCTION: extend bmap from blkno for nblocks; | 3275 | * FUNCTION: extend bmap from blkno for nblocks; |
3276 | * dbExtendFS() updates bmap ready for dbAllocBottomUp(); | 3276 | * dbExtendFS() updates bmap ready for dbAllocBottomUp(); |
3277 | * | 3277 | * |
3278 | * L2 | 3278 | * L2 |
3279 | * | | 3279 | * | |
@@ -3284,7 +3284,7 @@ static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, | |||
3284 | * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm; | 3284 | * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm; |
3285 | * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm | 3285 | * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm |
3286 | * | 3286 | * |
3287 | * <---old---><----------------------------extend-----------------------> | 3287 | * <---old---><----------------------------extend-----------------------> |
3288 | */ | 3288 | */ |
3289 | int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) | 3289 | int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) |
3290 | { | 3290 | { |
@@ -3330,7 +3330,7 @@ int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) | |||
3330 | bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0; | 3330 | bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0; |
3331 | 3331 | ||
3332 | /* | 3332 | /* |
3333 | * reconfigure db_agfree[] | 3333 | * reconfigure db_agfree[] |
3334 | * from old AG configuration to new AG configuration; | 3334 | * from old AG configuration to new AG configuration; |
3335 | * | 3335 | * |
3336 | * coalesce contiguous k (newAGSize/oldAGSize) AGs; | 3336 | * coalesce contiguous k (newAGSize/oldAGSize) AGs; |
@@ -3491,7 +3491,7 @@ int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) | |||
3491 | } /* for each dmap in a L0 */ | 3491 | } /* for each dmap in a L0 */ |
3492 | 3492 | ||
3493 | /* | 3493 | /* |
3494 | * build current L0 page from its leaves, and | 3494 | * build current L0 page from its leaves, and |
3495 | * initialize corresponding parent L1 leaf | 3495 | * initialize corresponding parent L1 leaf |
3496 | */ | 3496 | */ |
3497 | *l1leaf = dbInitDmapCtl(l0dcp, 0, ++i); | 3497 | *l1leaf = dbInitDmapCtl(l0dcp, 0, ++i); |
@@ -3515,7 +3515,7 @@ int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) | |||
3515 | } /* for each L0 in a L1 */ | 3515 | } /* for each L0 in a L1 */ |
3516 | 3516 | ||
3517 | /* | 3517 | /* |
3518 | * build current L1 page from its leaves, and | 3518 | * build current L1 page from its leaves, and |
3519 | * initialize corresponding parent L2 leaf | 3519 | * initialize corresponding parent L2 leaf |
3520 | */ | 3520 | */ |
3521 | *l2leaf = dbInitDmapCtl(l1dcp, 1, ++j); | 3521 | *l2leaf = dbInitDmapCtl(l1dcp, 1, ++j); |
@@ -3570,7 +3570,7 @@ void dbFinalizeBmap(struct inode *ipbmap) | |||
3570 | * finalize bmap control page | 3570 | * finalize bmap control page |
3571 | */ | 3571 | */ |
3572 | //finalize: | 3572 | //finalize: |
3573 | /* | 3573 | /* |
3574 | * compute db_agpref: preferred ag to allocate from | 3574 | * compute db_agpref: preferred ag to allocate from |
3575 | * (the leftmost ag with average free space in it); | 3575 | * (the leftmost ag with average free space in it); |
3576 | */ | 3576 | */ |
@@ -3614,9 +3614,9 @@ void dbFinalizeBmap(struct inode *ipbmap) | |||
3614 | 3614 | ||
3615 | /* | 3615 | /* |
3616 | * compute db_aglevel, db_agheigth, db_width, db_agstart: | 3616 | * compute db_aglevel, db_agheigth, db_width, db_agstart: |
3617 | * an ag is covered in aglevel dmapctl summary tree, | 3617 | * an ag is covered in aglevel dmapctl summary tree, |
3618 | * at agheight level height (from leaf) with agwidth number of nodes | 3618 | * at agheight level height (from leaf) with agwidth number of nodes |
3619 | * each, which starts at agstart index node of the smmary tree node | 3619 | * each, which starts at agstart index node of the smmary tree node |
3620 | * array; | 3620 | * array; |
3621 | */ | 3621 | */ |
3622 | bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize); | 3622 | bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize); |
@@ -3635,13 +3635,13 @@ void dbFinalizeBmap(struct inode *ipbmap) | |||
3635 | 3635 | ||
3636 | /* | 3636 | /* |
3637 | * NAME: dbInitDmap()/ujfs_idmap_page() | 3637 | * NAME: dbInitDmap()/ujfs_idmap_page() |
3638 | * | 3638 | * |
3639 | * FUNCTION: initialize working/persistent bitmap of the dmap page | 3639 | * FUNCTION: initialize working/persistent bitmap of the dmap page |
3640 | * for the specified number of blocks: | 3640 | * for the specified number of blocks: |
3641 | * | 3641 | * |
3642 | * at entry, the bitmaps had been initialized as free (ZEROS); | 3642 | * at entry, the bitmaps had been initialized as free (ZEROS); |
3643 | * The number of blocks will only account for the actually | 3643 | * The number of blocks will only account for the actually |
3644 | * existing blocks. Blocks which don't actually exist in | 3644 | * existing blocks. Blocks which don't actually exist in |
3645 | * the aggregate will be marked as allocated (ONES); | 3645 | * the aggregate will be marked as allocated (ONES); |
3646 | * | 3646 | * |
3647 | * PARAMETERS: | 3647 | * PARAMETERS: |
@@ -3677,7 +3677,7 @@ static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks) | |||
3677 | 3677 | ||
3678 | /* | 3678 | /* |
3679 | * free the bits corresponding to the block range (ZEROS): | 3679 | * free the bits corresponding to the block range (ZEROS): |
3680 | * note: not all bits of the first and last words may be contained | 3680 | * note: not all bits of the first and last words may be contained |
3681 | * within the block range. | 3681 | * within the block range. |
3682 | */ | 3682 | */ |
3683 | for (r = nblocks; r > 0; r -= nb, blkno += nb) { | 3683 | for (r = nblocks; r > 0; r -= nb, blkno += nb) { |
@@ -3709,7 +3709,7 @@ static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks) | |||
3709 | } | 3709 | } |
3710 | 3710 | ||
3711 | /* | 3711 | /* |
3712 | * mark bits following the range to be freed (non-existing | 3712 | * mark bits following the range to be freed (non-existing |
3713 | * blocks) as allocated (ONES) | 3713 | * blocks) as allocated (ONES) |
3714 | */ | 3714 | */ |
3715 | 3715 | ||
@@ -3741,11 +3741,11 @@ static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks) | |||
3741 | 3741 | ||
3742 | /* | 3742 | /* |
3743 | * NAME: dbInitDmapTree()/ujfs_complete_dmap() | 3743 | * NAME: dbInitDmapTree()/ujfs_complete_dmap() |
3744 | * | 3744 | * |
3745 | * FUNCTION: initialize summary tree of the specified dmap: | 3745 | * FUNCTION: initialize summary tree of the specified dmap: |
3746 | * | 3746 | * |
3747 | * at entry, bitmap of the dmap has been initialized; | 3747 | * at entry, bitmap of the dmap has been initialized; |
3748 | * | 3748 | * |
3749 | * PARAMETERS: | 3749 | * PARAMETERS: |
3750 | * dp - dmap to complete | 3750 | * dp - dmap to complete |
3751 | * blkno - starting block number for this dmap | 3751 | * blkno - starting block number for this dmap |
@@ -3769,7 +3769,7 @@ static int dbInitDmapTree(struct dmap * dp) | |||
3769 | 3769 | ||
3770 | /* init each leaf from corresponding wmap word: | 3770 | /* init each leaf from corresponding wmap word: |
3771 | * note: leaf is set to NOFREE(-1) if all blocks of corresponding | 3771 | * note: leaf is set to NOFREE(-1) if all blocks of corresponding |
3772 | * bitmap word are allocated. | 3772 | * bitmap word are allocated. |
3773 | */ | 3773 | */ |
3774 | cp = tp->stree + le32_to_cpu(tp->leafidx); | 3774 | cp = tp->stree + le32_to_cpu(tp->leafidx); |
3775 | for (i = 0; i < LPERDMAP; i++) | 3775 | for (i = 0; i < LPERDMAP; i++) |
@@ -3782,10 +3782,10 @@ static int dbInitDmapTree(struct dmap * dp) | |||
3782 | 3782 | ||
3783 | /* | 3783 | /* |
3784 | * NAME: dbInitTree()/ujfs_adjtree() | 3784 | * NAME: dbInitTree()/ujfs_adjtree() |
3785 | * | 3785 | * |
3786 | * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl. | 3786 | * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl. |
3787 | * | 3787 | * |
3788 | * at entry, the leaves of the tree has been initialized | 3788 | * at entry, the leaves of the tree has been initialized |
3789 | * from corresponding bitmap word or root of summary tree | 3789 | * from corresponding bitmap word or root of summary tree |
3790 | * of the child control page; | 3790 | * of the child control page; |
3791 | * configure binary buddy system at the leaf level, then | 3791 | * configure binary buddy system at the leaf level, then |
@@ -3813,15 +3813,15 @@ static int dbInitTree(struct dmaptree * dtp) | |||
3813 | /* | 3813 | /* |
3814 | * configure the leaf levevl into binary buddy system | 3814 | * configure the leaf levevl into binary buddy system |
3815 | * | 3815 | * |
3816 | * Try to combine buddies starting with a buddy size of 1 | 3816 | * Try to combine buddies starting with a buddy size of 1 |
3817 | * (i.e. two leaves). At a buddy size of 1 two buddy leaves | 3817 | * (i.e. two leaves). At a buddy size of 1 two buddy leaves |
3818 | * can be combined if both buddies have a maximum free of l2min; | 3818 | * can be combined if both buddies have a maximum free of l2min; |
3819 | * the combination will result in the left-most buddy leaf having | 3819 | * the combination will result in the left-most buddy leaf having |
3820 | * a maximum free of l2min+1. | 3820 | * a maximum free of l2min+1. |
3821 | * After processing all buddies for a given size, process buddies | 3821 | * After processing all buddies for a given size, process buddies |
3822 | * at the next higher buddy size (i.e. current size * 2) and | 3822 | * at the next higher buddy size (i.e. current size * 2) and |
3823 | * the next maximum free (current free + 1). | 3823 | * the next maximum free (current free + 1). |
3824 | * This continues until the maximum possible buddy combination | 3824 | * This continues until the maximum possible buddy combination |
3825 | * yields maximum free. | 3825 | * yields maximum free. |
3826 | */ | 3826 | */ |
3827 | for (l2free = dtp->budmin, bsize = 1; l2free < l2max; | 3827 | for (l2free = dtp->budmin, bsize = 1; l2free < l2max; |
@@ -3845,10 +3845,10 @@ static int dbInitTree(struct dmaptree * dtp) | |||
3845 | * bubble summary information of leaves up the tree. | 3845 | * bubble summary information of leaves up the tree. |
3846 | * | 3846 | * |
3847 | * Starting at the leaf node level, the four nodes described by | 3847 | * Starting at the leaf node level, the four nodes described by |
3848 | * the higher level parent node are compared for a maximum free and | 3848 | * the higher level parent node are compared for a maximum free and |
3849 | * this maximum becomes the value of the parent node. | 3849 | * this maximum becomes the value of the parent node. |
3850 | * when all lower level nodes are processed in this fashion then | 3850 | * when all lower level nodes are processed in this fashion then |
3851 | * move up to the next level (parent becomes a lower level node) and | 3851 | * move up to the next level (parent becomes a lower level node) and |
3852 | * continue the process for that level. | 3852 | * continue the process for that level. |
3853 | */ | 3853 | */ |
3854 | for (child = le32_to_cpu(dtp->leafidx), | 3854 | for (child = le32_to_cpu(dtp->leafidx), |
@@ -3857,7 +3857,7 @@ static int dbInitTree(struct dmaptree * dtp) | |||
3857 | /* get index of 1st node of parent level */ | 3857 | /* get index of 1st node of parent level */ |
3858 | parent = (child - 1) >> 2; | 3858 | parent = (child - 1) >> 2; |
3859 | 3859 | ||
3860 | /* set the value of the parent node as the maximum | 3860 | /* set the value of the parent node as the maximum |
3861 | * of the four nodes of the current level. | 3861 | * of the four nodes of the current level. |
3862 | */ | 3862 | */ |
3863 | for (i = 0, cp = tp + child, cp1 = tp + parent; | 3863 | for (i = 0, cp = tp + child, cp1 = tp + parent; |
@@ -3885,8 +3885,8 @@ static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i) | |||
3885 | dcp->budmin = L2BPERDMAP + L2LPERCTL * level; | 3885 | dcp->budmin = L2BPERDMAP + L2LPERCTL * level; |
3886 | 3886 | ||
3887 | /* | 3887 | /* |
3888 | * initialize the leaves of current level that were not covered | 3888 | * initialize the leaves of current level that were not covered |
3889 | * by the specified input block range (i.e. the leaves have no | 3889 | * by the specified input block range (i.e. the leaves have no |
3890 | * low level dmapctl or dmap). | 3890 | * low level dmapctl or dmap). |
3891 | */ | 3891 | */ |
3892 | cp = &dcp->stree[CTLLEAFIND + i]; | 3892 | cp = &dcp->stree[CTLLEAFIND + i]; |
@@ -3900,9 +3900,9 @@ static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i) | |||
3900 | 3900 | ||
3901 | /* | 3901 | /* |
3902 | * NAME: dbGetL2AGSize()/ujfs_getagl2size() | 3902 | * NAME: dbGetL2AGSize()/ujfs_getagl2size() |
3903 | * | 3903 | * |
3904 | * FUNCTION: Determine log2(allocation group size) from aggregate size | 3904 | * FUNCTION: Determine log2(allocation group size) from aggregate size |
3905 | * | 3905 | * |
3906 | * PARAMETERS: | 3906 | * PARAMETERS: |
3907 | * nblocks - Number of blocks in aggregate | 3907 | * nblocks - Number of blocks in aggregate |
3908 | * | 3908 | * |
@@ -3935,8 +3935,8 @@ static int dbGetL2AGSize(s64 nblocks) | |||
3935 | 3935 | ||
3936 | /* | 3936 | /* |
3937 | * NAME: dbMapFileSizeToMapSize() | 3937 | * NAME: dbMapFileSizeToMapSize() |
3938 | * | 3938 | * |
3939 | * FUNCTION: compute number of blocks the block allocation map file | 3939 | * FUNCTION: compute number of blocks the block allocation map file |
3940 | * can cover from the map file size; | 3940 | * can cover from the map file size; |
3941 | * | 3941 | * |
3942 | * RETURNS: Number of blocks which can be covered by this block map file; | 3942 | * RETURNS: Number of blocks which can be covered by this block map file; |
@@ -3968,7 +3968,7 @@ s64 dbMapFileSizeToMapSize(struct inode * ipbmap) | |||
3968 | npages = nblocks >> JFS_SBI(sb)->l2nbperpage; | 3968 | npages = nblocks >> JFS_SBI(sb)->l2nbperpage; |
3969 | level = BMAPPGTOLEV(npages); | 3969 | level = BMAPPGTOLEV(npages); |
3970 | 3970 | ||
3971 | /* At each level, accumulate the number of dmap pages covered by | 3971 | /* At each level, accumulate the number of dmap pages covered by |
3972 | * the number of full child levels below it; | 3972 | * the number of full child levels below it; |
3973 | * repeat for the last incomplete child level. | 3973 | * repeat for the last incomplete child level. |
3974 | */ | 3974 | */ |
@@ -3990,7 +3990,7 @@ s64 dbMapFileSizeToMapSize(struct inode * ipbmap) | |||
3990 | npages--; | 3990 | npages--; |
3991 | } | 3991 | } |
3992 | 3992 | ||
3993 | /* convert the number of dmaps into the number of blocks | 3993 | /* convert the number of dmaps into the number of blocks |
3994 | * which can be covered by the dmaps; | 3994 | * which can be covered by the dmaps; |
3995 | */ | 3995 | */ |
3996 | nblocks = ndmaps << L2BPERDMAP; | 3996 | nblocks = ndmaps << L2BPERDMAP; |