| blob | 370d7b6c5942ccedfa8dcd0c92c353badda41080 |
1 /*
2 * Copyright (C) International Business Machines Corp., 2000-2004
3 * Portions Copyright (C) Tino Reichardt, 2012
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
13 * the GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 */
20 #include <linux/fs.h>
21 #include <linux/slab.h>
31 /*
32 * SERIALIZATION of the Block Allocation Map.
33 *
34 * the working state of the block allocation map is accessed in
35 * two directions:
36 *
37 * 1) allocation and free requests that start at the dmap
38 * level and move up through the dmap control pages (i.e.
39 * the vast majority of requests).
40 *
41 * 2) allocation requests that start at dmap control page
42 * level and work down towards the dmaps.
43 *
44 * the serialization scheme used here is as follows.
45 *
46 * requests which start at the bottom are serialized against each
47 * other through buffers and each requests holds onto its buffers
48 * as it works it way up from a single dmap to the required level
49 * of dmap control page.
50 * requests that start at the top are serialized against each other
51 * and request that start from the bottom by the multiple read/single
52 * write inode lock of the bmap inode. requests starting at the top
53 * take this lock in write mode while request starting at the bottom
54 * take the lock in read mode. a single top-down request may proceed
55 * exclusively while multiple bottoms-up requests may proceed
56 * simultaneously (under the protection of busy buffers).
57 *
58 * in addition to information found in dmaps and dmap control pages,
59 * the working state of the block allocation map also includes read/
60 * write information maintained in the bmap descriptor (i.e. total
61 * free block count, allocation group level free block counts).
62 * a single exclusive lock (BMAP_LOCK) is used to guard this information
63 * in the face of multiple-bottoms up requests.
64 * (lock ordering: IREAD_LOCK, BMAP_LOCK);
65 *
66 * accesses to the persistent state of the block allocation map (limited
67 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
68 */
70 #define BMAP_LOCK_INIT(bmp) mutex_init(&bmp->db_bmaplock)
71 #define BMAP_LOCK(bmp) mutex_lock(&bmp->db_bmaplock)
72 #define BMAP_UNLOCK(bmp) mutex_unlock(&bmp->db_bmaplock)
74 /*
75 * forward references
76 */
122 /*
123 * buddy table
124 *
125 * table used for determining buddy sizes within characters of
126 * dmap bitmap words. the characters themselves serve as indexes
127 * into the table, with the table elements yielding the maximum
128 * binary buddy of free bits within the character.
129 */
147 };
149 /*
150 * NAME: dbMount()
151 *
152 * FUNCTION: initializate the block allocation map.
153 *
154 * memory is allocated for the in-core bmap descriptor and
155 * the in-core descriptor is initialized from disk.
156 *
157 * PARAMETERS:
158 * ipbmap - pointer to in-core inode for the block map.
159 *
160 * RETURN VALUES:
161 * 0 - success
162 * -ENOMEM - insufficient memory
163 * -EIO - i/o error
164 */
166 {
172 /*
173 * allocate/initialize the in-memory bmap descriptor
174 */
175 /* allocate memory for the in-memory bmap descriptor */
180 /* read the on-disk bmap descriptor. */
187 }
189 /* copy the on-disk bmap descriptor to its in-memory version. */
208 /* release the buffer. */
211 /* bind the bmap inode and the bmap descriptor to each other. */
217 /*
218 * allocate/initialize the bmap lock
219 */
223 }
226 /*
227 * NAME: dbUnmount()
228 *
229 * FUNCTION: terminate the block allocation map in preparation for
230 * file system unmount.
231 *
232 * the in-core bmap descriptor is written to disk and
233 * the memory for this descriptor is freed.
234 *
235 * PARAMETERS:
236 * ipbmap - pointer to in-core inode for the block map.
237 *
238 * RETURN VALUES:
239 * 0 - success
240 * -EIO - i/o error
241 */
243 {
249 /*
250 * Invalidate the page cache buffers
251 */
254 /* free the memory for the in-memory bmap. */
258 }
260 /*
261 * dbSync()
262 */
264 {
270 /*
271 * write bmap global control page
272 */
273 /* get the buffer for the on-disk bmap descriptor. */
280 }
281 /* copy the in-memory version of the bmap to the on-disk version */
300 /* write the buffer */
303 /*
304 * write out dirty pages of bmap
305 */
311 }
313 /*
314 * NAME: dbFree()
315 *
316 * FUNCTION: free the specified block range from the working block
317 * allocation map.
318 *
319 * the blocks will be free from the working map one dmap
320 * at a time.
321 *
322 * PARAMETERS:
323 * ip - pointer to in-core inode;
324 * blkno - starting block number to be freed.
325 * nblocks - number of blocks to be freed.
326 *
327 * RETURN VALUES:
328 * 0 - success
329 * -EIO - i/o error
330 */
332 {
343 /* block to be freed better be within the mapsize. */
351 }
353 /**
354 * TRIM the blocks, when mounted with discard option
355 */
360 /*
361 * free the blocks a dmap at a time.
362 */
365 /* release previous dmap if any */
368 }
370 /* get the buffer for the current dmap. */
376 }
379 /* determine the number of blocks to be freed from
380 * this dmap.
381 */
384 /* free the blocks. */
390 }
391 }
393 /* write the last buffer. */
399 }
402 /*
403 * NAME: dbUpdatePMap()
404 *
405 * FUNCTION: update the allocation state (free or allocate) of the
406 * specified block range in the persistent block allocation map.
407 *
408 * the blocks will be updated in the persistent map one
409 * dmap at a time.
410 *
411 * PARAMETERS:
412 * ipbmap - pointer to in-core inode for the block map.
413 * free - 'true' if block range is to be freed from the persistent
414 * map; 'false' if it is to be allocated.
415 * blkno - starting block number of the range.
416 * nblocks - number of contiguous blocks in the range.
417 * tblk - transaction block;
418 *
419 * RETURN VALUES:
420 * 0 - success
421 * -EIO - i/o error
422 */
423 int
426 {
431 u32 mask;
438 /* the blocks better be within the mapsize. */
445 }
447 /* compute delta of transaction lsn from log syncpt */
452 /*
453 * update the block state a dmap at a time.
454 */
458 /* get the buffer for the current dmap. */
463 }
470 }
473 /* determine the bit number and word within the dmap of
474 * the starting block. also determine how many blocks
475 * are to be updated within this dmap.
476 */
481 /* update the bits of the dmap words. the first and last
482 * words may only have a subset of their bits updated. if
483 * this is the case, we'll work against that word (i.e.
484 * partial first and/or last) only in a single pass. a
485 * single pass will also be used to update all words that
486 * are to have all their bits updated.
487 */
490 /* determine the bit number within the word and
491 * the number of bits within the word.
492 */
496 /* check if only part of the word is to be updated. */
498 /* update (free or allocate) the bits
499 * in this word.
500 */
501 mask =
506 else
512 /* one or more words are to have all
513 * their bits updated. determine how
514 * many words and how many bits.
515 */
519 /* update (free or allocate) the bits
520 * in these words.
521 */
525 else
530 }
531 }
533 /*
534 * update dmap lsn
535 */
543 /* inherit older/smaller lsn */
548 /* move bp after tblock in logsync list */
550 }
552 /* inherit younger/larger clsn */
561 /* insert bp after tblock in logsync list */
566 }
568 }
570 /* write the last buffer. */
573 }
576 }
579 /*
580 * NAME: dbNextAG()
581 *
582 * FUNCTION: find the preferred allocation group for new allocations.
583 *
584 * Within the allocation groups, we maintain a preferred
585 * allocation group which consists of a group with at least
586 * average free space. It is the preferred group that we target
587 * new inode allocation towards. The tie-in between inode
588 * allocation and block allocation occurs as we allocate the
589 * first (data) block of an inode and specify the inode (block)
590 * as the allocation hint for this block.
591 *
592 * We try to avoid having more than one open file growing in
593 * an allocation group, as this will lead to fragmentation.
594 * This differs from the old OS/2 method of trying to keep
595 * empty ags around for large allocations.
596 *
597 * PARAMETERS:
598 * ipbmap - pointer to in-core inode for the block map.
599 *
600 * RETURN VALUES:
601 * the preferred allocation group number.
602 */
604 {
605 s64 avgfree;
614 /* determine the average number of free blocks within the ags. */
617 /*
618 * if the current preferred ag does not have an active allocator
619 * and has at least average freespace, return it
620 */
626 /* From the last preferred ag, find the next one with at least
627 * average free space.
628 */
634 /* open file is currently growing in this ag */
637 /* Return this one */
641 /* Less than avg. freespace, but best so far */
644 }
645 }
647 /*
648 * If no inactive ag was found with average freespace, use the
649 * next best
650 */
653 /* else leave db_agpref unchanged */
654 unlock:
657 /* return the preferred group.
658 */
660 }
662 /*
663 * NAME: dbAlloc()
664 *
665 * FUNCTION: attempt to allocate a specified number of contiguous free
666 * blocks from the working allocation block map.
667 *
668 * the block allocation policy uses hints and a multi-step
669 * approach.
670 *
671 * for allocation requests smaller than the number of blocks
672 * per dmap, we first try to allocate the new blocks
673 * immediately following the hint. if these blocks are not
674 * available, we try to allocate blocks near the hint. if
675 * no blocks near the hint are available, we next try to
676 * allocate within the same dmap as contains the hint.
677 *
678 * if no blocks are available in the dmap or the allocation
679 * request is larger than the dmap size, we try to allocate
680 * within the same allocation group as contains the hint. if
681 * this does not succeed, we finally try to allocate anywhere
682 * within the aggregate.
683 *
684 * we also try to allocate anywhere within the aggregate for
685 * for allocation requests larger than the allocation group
686 * size or requests that specify no hint value.
687 *
688 * PARAMETERS:
689 * ip - pointer to in-core inode;
690 * hint - allocation hint.
691 * nblocks - number of contiguous blocks in the range.
692 * results - on successful return, set to the starting block number
693 * of the newly allocated contiguous range.
694 *
695 * RETURN VALUES:
696 * 0 - success
697 * -ENOSPC - insufficient disk resources
698 * -EIO - i/o error
699 */
701 {
709 s64 mapSize;
712 /* assert that nblocks is valid */
715 /* get the log2 number of blocks to be allocated.
716 * if the number of blocks is not a log2 multiple,
717 * it will be rounded up to the next log2 multiple.
718 */
725 /* the hint should be within the map */
729 }
731 /* if the number of blocks to be allocated is greater than the
732 * allocation group size, try to allocate anywhere.
733 */
740 }
742 /*
743 * If no hint, let dbNextAG recommend an allocation group
744 */
748 /* we would like to allocate close to the hint. adjust the
749 * hint to the block following the hint since the allocators
750 * will start looking for free space starting at this point.
751 */
759 /* check if blkno crosses over into a new allocation group.
760 * if so, check if we should allow allocations within this
761 * allocation group.
762 */
764 /* check if the AG is currently being written to.
765 * if so, call dbNextAG() to find a non-busy
766 * AG with sufficient free space.
767 */
771 /* check if the allocation request size can be satisfied from a
772 * single dmap. if so, try to allocate from the dmap containing
773 * the hint using a tiered strategy.
774 */
778 /* get the buffer for the dmap containing the hint.
779 */
788 /* first, try to satisfy the allocation request with the
789 * blocks beginning at the hint.
790 */
796 }
800 }
805 /*
806 * Someone else is writing in this allocation
807 * group. To avoid fragmenting, try another ag
808 */
812 }
814 /* next, try to satisfy the allocation request with blocks
815 * near the hint.
816 */
825 }
827 /* try to satisfy the allocation request with blocks within
828 * the same dmap as the hint.
829 */
837 }
841 }
843 /* try to satisfy the allocation request with blocks within
844 * the same allocation group as the hint.
845 */
853 pref_ag:
854 /*
855 * Let dbNextAG recommend a preferred allocation group
856 */
860 /* Try to allocate within this allocation group. if that fails, try to
861 * allocate anywhere in the map.
862 */
866 write_unlock:
871 read_unlock:
875 }
877 #ifdef _NOTYET
878 /*
879 * NAME: dbAllocExact()
880 *
881 * FUNCTION: try to allocate the requested extent;
882 *
883 * PARAMETERS:
884 * ip - pointer to in-core inode;
885 * blkno - extent address;
886 * nblocks - extent length;
887 *
888 * RETURN VALUES:
889 * 0 - success
890 * -ENOSPC - insufficient disk resources
891 * -EIO - i/o error
892 */
894 {
899 s64 lblkno;
904 /*
905 * validate extent request:
906 *
907 * note: defragfs policy:
908 * max 64 blocks will be moved.
909 * allocation request size must be satisfied from a single dmap.
910 */
914 }
917 /* the free space is no longer available */
920 }
922 /* read in the dmap covering the extent */
928 }
931 /* try to allocate the requested extent */
942 }
945 /*
946 * NAME: dbReAlloc()
947 *
948 * FUNCTION: attempt to extend a current allocation by a specified
949 * number of blocks.
950 *
951 * this routine attempts to satisfy the allocation request
952 * by first trying to extend the existing allocation in
953 * place by allocating the additional blocks as the blocks
954 * immediately following the current allocation. if these
955 * blocks are not available, this routine will attempt to
956 * allocate a new set of contiguous blocks large enough
957 * to cover the existing allocation plus the additional
958 * number of blocks required.
959 *
960 * PARAMETERS:
961 * ip - pointer to in-core inode requiring allocation.
962 * blkno - starting block of the current allocation.
963 * nblocks - number of contiguous blocks within the current
964 * allocation.
965 * addnblocks - number of blocks to add to the allocation.
966 * results - on successful return, set to the starting block number
967 * of the existing allocation if the existing allocation
968 * was extended in place or to a newly allocated contiguous
969 * range if the existing allocation could not be extended
970 * in place.
971 *
972 * RETURN VALUES:
973 * 0 - success
974 * -ENOSPC - insufficient disk resources
975 * -EIO - i/o error
976 */
977 int
980 {
983 /* try to extend the allocation in place.
984 */
991 }
993 /* could not extend the allocation in place, so allocate a
994 * new set of blocks for the entire request (i.e. try to get
995 * a range of contiguous blocks large enough to cover the
996 * existing allocation plus the additional blocks.)
997 */
1000 }
1003 /*
1004 * NAME: dbExtend()
1005 *
1006 * FUNCTION: attempt to extend a current allocation by a specified
1007 * number of blocks.
1008 *
1009 * this routine attempts to satisfy the allocation request
1010 * by first trying to extend the existing allocation in
1011 * place by allocating the additional blocks as the blocks
1012 * immediately following the current allocation.
1013 *
1014 * PARAMETERS:
1015 * ip - pointer to in-core inode requiring allocation.
1016 * blkno - starting block of the current allocation.
1017 * nblocks - number of contiguous blocks within the current
1018 * allocation.
1019 * addnblocks - number of blocks to add to the allocation.
1020 *
1021 * RETURN VALUES:
1022 * 0 - success
1023 * -ENOSPC - insufficient disk resources
1024 * -EIO - i/o error
1025 */
1027 {
1030 uint rel_block;
1037 /*
1038 * We don't want a non-aligned extent to cross a page boundary
1039 */
1044 /* get the last block of the current allocation */
1047 /* determine the block number of the block following
1048 * the existing allocation.
1049 */
1054 /* better be within the file system */
1060 }
1062 /* we'll attempt to extend the current allocation in place by
1063 * allocating the additional blocks as the blocks immediately
1064 * following the current allocation. we only try to extend the
1065 * current allocation in place if the number of additional blocks
1066 * can fit into a dmap, the last block of the current allocation
1067 * is not the last block of the file system, and the start of the
1068 * inplace extension is not on an allocation group boundary.
1069 */
1074 }
1076 /* get the buffer for the dmap containing the first block
1077 * of the extension.
1078 */
1084 }
1088 /* try to allocate the blocks immediately following the
1089 * current allocation.
1090 */
1095 /* were we successful ? */
1098 else
1099 /* we were not successful */
1103 }
1106 /*
1107 * NAME: dbAllocNext()
1108 *
1109 * FUNCTION: attempt to allocate the blocks of the specified block
1110 * range within a dmap.
1111 *
1112 * PARAMETERS:
1113 * bmp - pointer to bmap descriptor
1114 * dp - pointer to dmap.
1115 * blkno - starting block number of the range.
1116 * nblocks - number of contiguous free blocks of the range.
1117 *
1118 * RETURN VALUES:
1119 * 0 - success
1120 * -ENOSPC - insufficient disk resources
1121 * -EIO - i/o error
1122 *
1123 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1124 */
1127 {
1131 u32 mask;
1136 }
1138 /* pick up a pointer to the leaves of the dmap tree.
1139 */
1142 /* determine the bit number and word within the dmap of the
1143 * starting block.
1144 */
1148 /* check if the specified block range is contained within
1149 * this dmap.
1150 */
1154 /* check if the starting leaf indicates that anything
1155 * is free.
1156 */
1160 /* check the dmaps words corresponding to block range to see
1161 * if the block range is free. not all bits of the first and
1162 * last words may be contained within the block range. if this
1163 * is the case, we'll work against those words (i.e. partial first
1164 * and/or last) on an individual basis (a single pass) and examine
1165 * the actual bits to determine if they are free. a single pass
1166 * will be used for all dmap words fully contained within the
1167 * specified range. within this pass, the leaves of the dmap
1168 * tree will be examined to determine if the blocks are free. a
1169 * single leaf may describe the free space of multiple dmap
1170 * words, so we may visit only a subset of the actual leaves
1171 * corresponding to the dmap words of the block range.
1172 */
1174 /* determine the bit number within the word and
1175 * the number of bits within the word.
1176 */
1180 /* check if only part of the word is to be examined.
1181 */
1183 /* check if the bits are free.
1184 */
1191 /* one or more dmap words are fully contained
1192 * within the block range. determine how many
1193 * words and how many bits.
1194 */
1198 /* now examine the appropriate leaves to determine
1199 * if the blocks are free.
1200 */
1202 /* does the leaf describe any free space ?
1203 */
1207 /* determine the l2 number of bits provided
1208 * by this leaf.
1209 */
1210 l2size =
1213 /* determine how many words were handled.
1214 */
1219 }
1220 }
1221 }
1223 /* allocate the blocks.
1224 */
1226 }
1229 /*
1230 * NAME: dbAllocNear()
1231 *
1232 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1233 * a specified block (hint) within a dmap.
1234 *
1235 * starting with the dmap leaf that covers the hint, we'll
1236 * check the next four contiguous leaves for sufficient free
1237 * space. if sufficient free space is found, we'll allocate
1238 * the desired free space.
1239 *
1240 * PARAMETERS:
1241 * bmp - pointer to bmap descriptor
1242 * dp - pointer to dmap.
1243 * blkno - block number to allocate near.
1244 * nblocks - actual number of contiguous free blocks desired.
1245 * l2nb - log2 number of contiguous free blocks desired.
1246 * results - on successful return, set to the starting block number
1247 * of the newly allocated range.
1248 *
1249 * RETURN VALUES:
1250 * 0 - success
1251 * -ENOSPC - insufficient disk resources
1252 * -EIO - i/o error
1253 *
1254 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1255 */
1256 static int
1259 {
1266 }
1270 /* determine the word within the dmap that holds the hint
1271 * (i.e. blkno). also, determine the last word in the dmap
1272 * that we'll include in our examination.
1273 */
1277 /* examine the leaves for sufficient free space.
1278 */
1280 /* does the leaf describe sufficient free space ?
1281 */
1285 /* determine the block number within the file system
1286 * of the first block described by this dmap word.
1287 */
1290 /* if not all bits of the dmap word are free, get the
1291 * starting bit number within the dmap word of the required
1292 * string of free bits and adjust the block number with the
1293 * value.
1294 */
1296 blkno +=
1299 /* allocate the blocks.
1300 */
1305 }
1308 }
1311 /*
1312 * NAME: dbAllocAG()
1313 *
1314 * FUNCTION: attempt to allocate the specified number of contiguous
1315 * free blocks within the specified allocation group.
1316 *
1317 * unless the allocation group size is equal to the number
1318 * of blocks per dmap, the dmap control pages will be used to
1319 * find the required free space, if available. we start the
1320 * search at the highest dmap control page level which
1321 * distinctly describes the allocation group's free space
1322 * (i.e. the highest level at which the allocation group's
1323 * free space is not mixed in with that of any other group).
1324 * in addition, we start the search within this level at a
1325 * height of the dmapctl dmtree at which the nodes distinctly
1326 * describe the allocation group's free space. at this height,
1327 * the allocation group's free space may be represented by 1
1328 * or two sub-trees, depending on the allocation group size.
1329 * we search the top nodes of these subtrees left to right for
1330 * sufficient free space. if sufficient free space is found,
1331 * the subtree is searched to find the leftmost leaf that
1332 * has free space. once we have made it to the leaf, we
1333 * move the search to the next lower level dmap control page
1334 * corresponding to this leaf. we continue down the dmap control
1335 * pages until we find the dmap that contains or starts the
1336 * sufficient free space and we allocate at this dmap.
1337 *
1338 * if the allocation group size is equal to the dmap size,
1339 * we'll start at the dmap corresponding to the allocation
1340 * group and attempt the allocation at this level.
1341 *
1342 * the dmap control page search is also not performed if the
1343 * allocation group is completely free and we go to the first
1344 * dmap of the allocation group to do the allocation. this is
1345 * done because the allocation group may be part (not the first
1346 * part) of a larger binary buddy system, causing the dmap
1347 * control pages to indicate no free space (NOFREE) within
1348 * the allocation group.
1349 *
1350 * PARAMETERS:
1351 * bmp - pointer to bmap descriptor
1352 * agno - allocation group number.
1353 * nblocks - actual number of contiguous free blocks desired.
1354 * l2nb - log2 number of contiguous free blocks desired.
1355 * results - on successful return, set to the starting block number
1356 * of the newly allocated range.
1357 *
1358 * RETURN VALUES:
1359 * 0 - success
1360 * -ENOSPC - insufficient disk resources
1361 * -EIO - i/o error
1362 *
1363 * note: IWRITE_LOCK(ipmap) held on entry/exit;
1364 */
1365 static int
1367 {
1374 /* allocation request should not be for more than the
1375 * allocation group size.
1376 */
1381 }
1383 /* determine the starting block number of the allocation
1384 * group.
1385 */
1388 /* check if the allocation group size is the minimum allocation
1389 * group size or if the allocation group is completely free. if
1390 * the allocation group size is the minimum size of BPERDMAP (i.e.
1391 * 1 dmap), there is no need to search the dmap control page (below)
1392 * that fully describes the allocation group since the allocation
1393 * group is already fully described by a dmap. in this case, we
1394 * just call dbAllocCtl() to search the dmap tree and allocate the
1395 * required space if available.
1396 *
1397 * if the allocation group is completely free, dbAllocCtl() is
1398 * also called to allocate the required space. this is done for
1399 * two reasons. first, it makes no sense searching the dmap control
1400 * pages for free space when we know that free space exists. second,
1401 * the dmap control pages may indicate that the allocation group
1402 * has no free space if the allocation group is part (not the first
1403 * part) of a larger binary buddy system.
1404 */
1415 }
1417 }
1419 /* the buffer for the dmap control page that fully describes the
1420 * allocation group.
1421 */
1433 }
1435 /* search the subtree(s) of the dmap control page that describes
1436 * the allocation group, looking for sufficient free space. to begin,
1437 * determine how many allocation groups are represented in a dmap
1438 * control page at the control page level (i.e. L0, L1, L2) that
1439 * fully describes an allocation group. next, determine the starting
1440 * tree index of this allocation group within the control page.
1441 */
1442 agperlev =
1446 /* dmap control page trees fan-out by 4 and a single allocation
1447 * group may be described by 1 or 2 subtrees within the ag level
1448 * dmap control page, depending upon the ag size. examine the ag's
1449 * subtrees for sufficient free space, starting with the leftmost
1450 * subtree.
1451 */
1453 /* is there sufficient free space ?
1454 */
1458 /* sufficient free space found in a subtree. now search down
1459 * the subtree to find the leftmost leaf that describes this
1460 * free space.
1461 */
1467 }
1468 }
1474 }
1475 }
1477 /* determine the block number within the file system
1478 * that corresponds to this leaf.
1479 */
1487 blkno +=
1490 /* release the buffer in preparation for going down
1491 * the next level of dmap control pages.
1492 */
1495 /* check if we need to continue to search down the lower
1496 * level dmap control pages. we need to if the number of
1497 * blocks required is less than maximum number of blocks
1498 * described at the next lower level.
1499 */
1502 /* search the lower level dmap control pages to get
1503 * the starting block number of the dmap that
1504 * contains or starts off the free space.
1505 */
1513 }
1515 }
1516 }
1518 /* allocate the blocks.
1519 */
1525 }
1527 }
1529 /* no space in the allocation group. release the buffer and
1530 * return -ENOSPC.
1531 */
1535 }
1538 /*
1539 * NAME: dbAllocAny()
1540 *
1541 * FUNCTION: attempt to allocate the specified number of contiguous
1542 * free blocks anywhere in the file system.
1543 *
1544 * dbAllocAny() attempts to find the sufficient free space by
1545 * searching down the dmap control pages, starting with the
1546 * highest level (i.e. L0, L1, L2) control page. if free space
1547 * large enough to satisfy the desired free space is found, the
1548 * desired free space is allocated.
1549 *
1550 * PARAMETERS:
1551 * bmp - pointer to bmap descriptor
1552 * nblocks - actual number of contiguous free blocks desired.
1553 * l2nb - log2 number of contiguous free blocks desired.
1554 * results - on successful return, set to the starting block number
1555 * of the newly allocated range.
1556 *
1557 * RETURN VALUES:
1558 * 0 - success
1559 * -ENOSPC - insufficient disk resources
1560 * -EIO - i/o error
1561 *
1562 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1563 */
1565 {
1569 /* starting with the top level dmap control page, search
1570 * down the dmap control levels for sufficient free space.
1571 * if free space is found, dbFindCtl() returns the starting
1572 * block number of the dmap that contains or starts off the
1573 * range of free space.
1574 */
1578 /* allocate the blocks.
1579 */
1584 }
1586 }
1589 /*
1590 * NAME: dbDiscardAG()
1591 *
1592 * FUNCTION: attempt to discard (TRIM) all free blocks of specific AG
1593 *
1594 * algorithm:
1595 * 1) allocate blocks, as large as possible and save them
1596 * while holding IWRITE_LOCK on ipbmap
1597 * 2) trim all these saved block/length values
1598 * 3) mark the blocks free again
1599 *
1600 * benefit:
1601 * - we work only on one ag at some time, minimizing how long we
1602 * need to lock ipbmap
1603 * - reading / writing the fs is possible most time, even on
1604 * trimming
1605 *
1606 * downside:
1607 * - we write two times to the dmapctl and dmap pages
1608 * - but for me, this seems the best way, better ideas?
1609 * /TR 2012
1610 *
1611 * PARAMETERS:
1612 * ip - pointer to in-core inode
1613 * agno - ag to trim
1614 * minlen - minimum value of contiguous blocks
1615 *
1616 * RETURN VALUES:
1617 * s64 - actual number of blocks trimmed
1618 */
1620 {
1629 u64 blkno;
1630 u64 nblocks;
1633 /* max blkno / nblocks pairs to trim */
1635 u64 max_ranges;
1637 /* prevent others from writing new stuff here, while trimming */
1649 }
1655 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */
1662 /* the whole ag is free, trim now */
1666 /* give a hint for the next while */
1670 /* search for next smaller log2 block */
1674 /* Trim any already allocated blocks */
1677 }
1679 /* check, if our trim array is full */
1682 }
1687 /* when mounted with online discard, dbFree() will
1688 * call jfs_issue_discard() itself */
1693 }
1697 }
1699 /*
1700 * NAME: dbFindCtl()
1701 *
1702 * FUNCTION: starting at a specified dmap control page level and block
1703 * number, search down the dmap control levels for a range of
1704 * contiguous free blocks large enough to satisfy an allocation
1705 * request for the specified number of free blocks.
1706 *
1707 * if sufficient contiguous free blocks are found, this routine
1708 * returns the starting block number within a dmap page that
1709 * contains or starts a range of contiqious free blocks that
1710 * is sufficient in size.
1711 *
1712 * PARAMETERS:
1713 * bmp - pointer to bmap descriptor
1714 * level - starting dmap control page level.
1715 * l2nb - log2 number of contiguous free blocks desired.
1716 * *blkno - on entry, starting block number for conducting the search.
1717 * on successful return, the first block within a dmap page
1718 * that contains or starts a range of contiguous free blocks.
1719 *
1720 * RETURN VALUES:
1721 * 0 - success
1722 * -ENOSPC - insufficient disk resources
1723 * -EIO - i/o error
1724 *
1725 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1726 */
1728 {
1735 /* starting at the specified dmap control page level and block
1736 * number, search down the dmap control levels for the starting
1737 * block number of a dmap page that contains or starts off
1738 * sufficient free blocks.
1739 */
1741 /* get the buffer of the dmap control page for the block
1742 * number and level (i.e. L0, L1, L2).
1743 */
1756 }
1758 /* search the tree within the dmap control page for
1759 * sufficient free space. if sufficient free space is found,
1760 * dbFindLeaf() returns the index of the leaf at which
1761 * free space was found.
1762 */
1765 /* release the buffer.
1766 */
1769 /* space found ?
1770 */
1776 }
1778 }
1780 /* adjust the block number to reflect the location within
1781 * the dmap control page (i.e. the leaf) at which free
1782 * space was found.
1783 */
1786 /* we stop the search at this dmap control page level if
1787 * the number of blocks required is greater than or equal
1788 * to the maximum number of blocks described at the next
1789 * (lower) level.
1790 */
1793 }
1797 }
1800 /*
1801 * NAME: dbAllocCtl()
1802 *
1803 * FUNCTION: attempt to allocate a specified number of contiguous
1804 * blocks starting within a specific dmap.
1805 *
1806 * this routine is called by higher level routines that search
1807 * the dmap control pages above the actual dmaps for contiguous
1808 * free space. the result of successful searches by these
1809 * routines are the starting block numbers within dmaps, with
1810 * the dmaps themselves containing the desired contiguous free
1811 * space or starting a contiguous free space of desired size
1812 * that is made up of the blocks of one or more dmaps. these
1813 * calls should not fail due to insufficent resources.
1814 *
1815 * this routine is called in some cases where it is not known
1816 * whether it will fail due to insufficient resources. more
1817 * specifically, this occurs when allocating from an allocation
1818 * group whose size is equal to the number of blocks per dmap.
1819 * in this case, the dmap control pages are not examined prior
1820 * to calling this routine (to save pathlength) and the call
1821 * might fail.
1822 *
1823 * for a request size that fits within a dmap, this routine relies
1824 * upon the dmap's dmtree to find the requested contiguous free
1825 * space. for request sizes that are larger than a dmap, the
1826 * requested free space will start at the first block of the
1827 * first dmap (i.e. blkno).
1828 *
1829 * PARAMETERS:
1830 * bmp - pointer to bmap descriptor
1831 * nblocks - actual number of contiguous free blocks to allocate.
1832 * l2nb - log2 number of contiguous free blocks to allocate.
1833 * blkno - starting block number of the dmap to start the allocation
1834 * from.
1835 * results - on successful return, set to the starting block number
1836 * of the newly allocated range.
1837 *
1838 * RETURN VALUES:
1839 * 0 - success
1840 * -ENOSPC - insufficient disk resources
1841 * -EIO - i/o error
1842 *
1843 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1844 */
1845 static int
1847 {
1853 /* check if the allocation request is confined to a single dmap.
1854 */
1856 /* get the buffer for the dmap.
1857 */
1864 /* try to allocate the blocks.
1865 */
1873 }
1875 /* allocation request involving multiple dmaps. it must start on
1876 * a dmap boundary.
1877 */
1880 /* allocate the blocks dmap by dmap.
1881 */
1883 /* get the buffer for the dmap.
1884 */
1890 }
1893 /* the dmap better be all free.
1894 */
1901 }
1903 /* determine how many blocks to allocate from this dmap.
1904 */
1907 /* allocate the blocks from the dmap.
1908 */
1912 }
1914 /* write the buffer.
1915 */
1917 }
1919 /* set the results (starting block number) and return.
1920 */
1924 /* something failed in handling an allocation request involving
1925 * multiple dmaps. we'll try to clean up by backing out any
1926 * allocation that has already happened for this request. if
1927 * we fail in backing out the allocation, we'll mark the file
1928 * system to indicate that blocks have been leaked.
1929 */
1930 backout:
1932 /* try to backout the allocations dmap by dmap.
1933 */
1936 /* get the buffer for this dmap.
1937 */
1941 /* could not back out. mark the file system
1942 * to indicate that we have leaked blocks.
1943 */
1947 }
1950 /* free the blocks is this dmap.
1951 */
1953 /* could not back out. mark the file system
1954 * to indicate that we have leaked blocks.
1955 */
1959 }
1961 /* write the buffer.
1962 */
1964 }
1967 }
1970 /*
1971 * NAME: dbAllocDmapLev()
1972 *
1973 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1974 * from a specified dmap.
1975 *
1976 * this routine checks if the contiguous blocks are available.
1977 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1978 * returned.
1979 *
1980 * PARAMETERS:
1981 * mp - pointer to bmap descriptor
1982 * dp - pointer to dmap to attempt to allocate blocks from.
1983 * l2nb - log2 number of contiguous block desired.
1984 * nblocks - actual number of contiguous block desired.
1985 * results - on successful return, set to the starting block number
1986 * of the newly allocated range.
1987 *
1988 * RETURN VALUES:
1989 * 0 - success
1990 * -ENOSPC - insufficient disk resources
1991 * -EIO - i/o error
1992 *
1993 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1994 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1995 */
1996 static int
1999 {
2000 s64 blkno;
2003 /* can't be more than a dmaps worth of blocks */
2006 /* search the tree within the dmap page for sufficient
2007 * free space. if sufficient free space is found, dbFindLeaf()
2008 * returns the index of the leaf at which free space was found.
2009 */
2013 /* determine the block number within the file system corresponding
2014 * to the leaf at which free space was found.
2015 */
2018 /* if not all bits of the dmap word are free, get the starting
2019 * bit number within the dmap word of the required string of free
2020 * bits and adjust the block number with this value.
2021 */
2025 /* allocate the blocks */
2030 }
2033 /*
2034 * NAME: dbAllocDmap()
2035 *
2036 * FUNCTION: adjust the disk allocation map to reflect the allocation
2037 * of a specified block range within a dmap.
2038 *
2039 * this routine allocates the specified blocks from the dmap
2040 * through a call to dbAllocBits(). if the allocation of the
2041 * block range causes the maximum string of free blocks within
2042 * the dmap to change (i.e. the value of the root of the dmap's
2043 * dmtree), this routine will cause this change to be reflected
2044 * up through the appropriate levels of the dmap control pages
2045 * by a call to dbAdjCtl() for the L0 dmap control page that
2046 * covers this dmap.
2047 *
2048 * PARAMETERS:
2049 * bmp - pointer to bmap descriptor
2050 * dp - pointer to dmap to allocate the block range from.
2051 * blkno - starting block number of the block to be allocated.
2052 * nblocks - number of blocks to be allocated.
2053 *
2054 * RETURN VALUES:
2055 * 0 - success
2056 * -EIO - i/o error
2057 *
2058 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2059 */
2062 {
2063 s8 oldroot;
2066 /* save the current value of the root (i.e. maximum free string)
2067 * of the dmap tree.
2068 */
2071 /* allocate the specified (blocks) bits */
2074 /* if the root has not changed, done. */
2078 /* root changed. bubble the change up to the dmap control pages.
2079 * if the adjustment of the upper level control pages fails,
2080 * backout the bit allocation (thus making everything consistent).
2081 */
2086 }
2089 /*
2090 * NAME: dbFreeDmap()
2091 *
2092 * FUNCTION: adjust the disk allocation map to reflect the allocation
2093 * of a specified block range within a dmap.
2094 *
2095 * this routine frees the specified blocks from the dmap through
2096 * a call to dbFreeBits(). if the deallocation of the block range
2097 * causes the maximum string of free blocks within the dmap to
2098 * change (i.e. the value of the root of the dmap's dmtree), this
2099 * routine will cause this change to be reflected up through the
2100 * appropriate levels of the dmap control pages by a call to
2101 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
2102 *
2103 * PARAMETERS:
2104 * bmp - pointer to bmap descriptor
2105 * dp - pointer to dmap to free the block range from.
2106 * blkno - starting block number of the block to be freed.
2107 * nblocks - number of blocks to be freed.
2108 *
2109 * RETURN VALUES:
2110 * 0 - success
2111 * -EIO - i/o error
2112 *
2113 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2114 */
2117 {
2118 s8 oldroot;
2121 /* save the current value of the root (i.e. maximum free string)
2122 * of the dmap tree.
2123 */
2126 /* free the specified (blocks) bits */
2129 /* if error or the root has not changed, done. */
2133 /* root changed. bubble the change up to the dmap control pages.
2134 * if the adjustment of the upper level control pages fails,
2135 * backout the deallocation.
2136 */
2140 /* as part of backing out the deallocation, we will have
2141 * to back split the dmap tree if the deallocation caused
2142 * the freed blocks to become part of a larger binary buddy
2143 * system.
2144 */
2149 }
2152 }
2155 /*
2156 * NAME: dbAllocBits()
2157 *
2158 * FUNCTION: allocate a specified block range from a dmap.
2159 *
2160 * this routine updates the dmap to reflect the working
2161 * state allocation of the specified block range. it directly
2162 * updates the bits of the working map and causes the adjustment
2163 * of the binary buddy system described by the dmap's dmtree
2164 * leaves to reflect the bits allocated. it also causes the
2165 * dmap's dmtree, as a whole, to reflect the allocated range.
2166 *
2167 * PARAMETERS:
2168 * bmp - pointer to bmap descriptor
2169 * dp - pointer to dmap to allocate bits from.
2170 * blkno - starting block number of the bits to be allocated.
2171 * nblocks - number of bits to be allocated.
2172 *
2173 * RETURN VALUES: none
2174 *
2175 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2176 */
2179 {
2185 /* pick up a pointer to the leaves of the dmap tree */
2188 /* determine the bit number and word within the dmap of the
2189 * starting block.
2190 */
2194 /* block range better be within the dmap */
2197 /* allocate the bits of the dmap's words corresponding to the block
2198 * range. not all bits of the first and last words may be contained
2199 * within the block range. if this is the case, we'll work against
2200 * those words (i.e. partial first and/or last) on an individual basis
2201 * (a single pass), allocating the bits of interest by hand and
2202 * updating the leaf corresponding to the dmap word. a single pass
2203 * will be used for all dmap words fully contained within the
2204 * specified range. within this pass, the bits of all fully contained
2205 * dmap words will be marked as free in a single shot and the leaves
2206 * will be updated. a single leaf may describe the free space of
2207 * multiple dmap words, so we may update only a subset of the actual
2208 * leaves corresponding to the dmap words of the block range.
2209 */
2211 /* determine the bit number within the word and
2212 * the number of bits within the word.
2213 */
2217 /* check if only part of a word is to be allocated.
2218 */
2220 /* allocate (set to 1) the appropriate bits within
2221 * this dmap word.
2222 */
2226 /* update the leaf for this dmap word. in addition
2227 * to setting the leaf value to the binary buddy max
2228 * of the updated dmap word, dbSplit() will split
2229 * the binary system of the leaves if need be.
2230 */
2236 /* one or more dmap words are fully contained
2237 * within the block range. determine how many
2238 * words and allocate (set to 1) the bits of these
2239 * words.
2240 */
2244 /* determine how many bits.
2245 */
2248 /* now update the appropriate leaves to reflect
2249 * the allocated words.
2250 */
2256 }
2258 /* determine what the leaf value should be
2259 * updated to as the minimum of the l2 number
2260 * of bits being allocated and the l2 number
2261 * of bits currently described by this leaf.
2262 */
2265 /* update the leaf to reflect the allocation.
2266 * in addition to setting the leaf value to
2267 * NOFREE, dbSplit() will split the binary
2268 * system of the leaves to reflect the current
2269 * allocation (size).
2270 */
2273 /* get the number of dmap words handled */
2276 }
2277 }
2278 }
2280 /* update the free count for this dmap */
2285 /* if this allocation group is completely free,
2286 * update the maximum allocation group number if this allocation
2287 * group is the new max.
2288 */
2293 /* update the free count for the allocation group and map */
2298 }
2301 /*
2302 * NAME: dbFreeBits()
2303 *
2304 * FUNCTION: free a specified block range from a dmap.
2305 *
2306 * this routine updates the dmap to reflect the working
2307 * state allocation of the specified block range. it directly
2308 * updates the bits of the working map and causes the adjustment
2309 * of the binary buddy system described by the dmap's dmtree
2310 * leaves to reflect the bits freed. it also causes the dmap's
2311 * dmtree, as a whole, to reflect the deallocated range.
2312 *
2313 * PARAMETERS:
2314 * bmp - pointer to bmap descriptor
2315 * dp - pointer to dmap to free bits from.
2316 * blkno - starting block number of the bits to be freed.
2317 * nblocks - number of bits to be freed.
2318 *
2319 * RETURN VALUES: 0 for success
2320 *
2321 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2322 */
2325 {
2331 /* determine the bit number and word within the dmap of the
2332 * starting block.
2333 */
2337 /* block range better be within the dmap.
2338 */
2341 /* free the bits of the dmaps words corresponding to the block range.
2342 * not all bits of the first and last words may be contained within
2343 * the block range. if this is the case, we'll work against those
2344 * words (i.e. partial first and/or last) on an individual basis
2345 * (a single pass), freeing the bits of interest by hand and updating
2346 * the leaf corresponding to the dmap word. a single pass will be used
2347 * for all dmap words fully contained within the specified range.
2348 * within this pass, the bits of all fully contained dmap words will
2349 * be marked as free in a single shot and the leaves will be updated. a
2350 * single leaf may describe the free space of multiple dmap words,
2351 * so we may update only a subset of the actual leaves corresponding
2352 * to the dmap words of the block range.
2353 *
2354 * dbJoin() is used to update leaf values and will join the binary
2355 * buddy system of the leaves if the new leaf values indicate this
2356 * should be done.
2357 */
2359 /* determine the bit number within the word and
2360 * the number of bits within the word.
2361 */
2365 /* check if only part of a word is to be freed.
2366 */
2368 /* free (zero) the appropriate bits within this
2369 * dmap word.
2370 */
2375 /* update the leaf for this dmap word.
2376 */
2384 /* one or more dmap words are fully contained
2385 * within the block range. determine how many
2386 * words and free (zero) the bits of these words.
2387 */
2391 /* determine how many bits.
2392 */
2395 /* now update the appropriate leaves to reflect
2396 * the freed words.
2397 */
2399 /* determine what the leaf value should be
2400 * updated to as the minimum of the l2 number
2401 * of bits being freed and the l2 (max) number
2402 * of bits that can be described by this leaf.
2403 */
2404 size =
2409 /* update the leaf.
2410 */
2415 /* get the number of dmap words handled.
2416 */
2419 }
2420 }
2421 }
2423 /* update the free count for this dmap.
2424 */
2429 /* update the free count for the allocation group and
2430 * map.
2431 */
2436 /* check if this allocation group is not completely free and
2437 * if it is currently the maximum (rightmost) allocation group.
2438 * if so, establish the new maximum allocation group number by
2439 * searching left for the first allocation group with allocation.
2440 */
2449 }
2451 /* re-establish the allocation group preference if the
2452 * current preference is right of the maximum allocation
2453 * group.
2454 */
2457 }
2462 }
2465 /*
2466 * NAME: dbAdjCtl()
2467 *
2468 * FUNCTION: adjust a dmap control page at a specified level to reflect
2469 * the change in a lower level dmap or dmap control page's
2470 * maximum string of free blocks (i.e. a change in the root
2471 * of the lower level object's dmtree) due to the allocation
2472 * or deallocation of a range of blocks with a single dmap.
2473 *
2474 * on entry, this routine is provided with the new value of
2475 * the lower level dmap or dmap control page root and the
2476 * starting block number of the block range whose allocation
2477 * or deallocation resulted in the root change. this range
2478 * is respresented by a single leaf of the current dmapctl
2479 * and the leaf will be updated with this value, possibly
2480 * causing a binary buddy system within the leaves to be
2481 * split or joined. the update may also cause the dmapctl's
2482 * dmtree to be updated.
2483 *
2484 * if the adjustment of the dmap control page, itself, causes its
2485 * root to change, this change will be bubbled up to the next dmap
2486 * control level by a recursive call to this routine, specifying
2487 * the new root value and the next dmap control page level to
2488 * be adjusted.
2489 * PARAMETERS:
2490 * bmp - pointer to bmap descriptor
2491 * blkno - the first block of a block range within a dmap. it is
2492 * the allocation or deallocation of this block range that
2493 * requires the dmap control page to be adjusted.
2494 * newval - the new value of the lower level dmap or dmap control
2495 * page root.
2496 * alloc - 'true' if adjustment is due to an allocation.
2497 * level - current level of dmap control page (i.e. L0, L1, L2) to
2498 * be adjusted.
2499 *
2500 * RETURN VALUES:
2501 * 0 - success
2502 * -EIO - i/o error
2503 *
2504 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2505 */
2506 static int
2508 {
2510 s8 oldroot;
2512 s64 lblkno;
2516 /* get the buffer for the dmap control page for the specified
2517 * block number and control page level.
2518 */
2529 }
2531 /* determine the leaf number corresponding to the block and
2532 * the index within the dmap control tree.
2533 */
2537 /* save the current leaf value and the current root level (i.e.
2538 * maximum l2 free string described by this dmapctl).
2539 */
2543 /* check if this is a control page update for an allocation.
2544 * if so, update the leaf to reflect the new leaf value using
2545 * dbSplit(); otherwise (deallocation), use dbJoin() to update
2546 * the leaf with the new value. in addition to updating the
2547 * leaf, dbSplit() will also split the binary buddy system of
2548 * the leaves, if required, and bubble new values within the
2549 * dmapctl tree, if required. similarly, dbJoin() will join
2550 * the binary buddy system of leaves and bubble new values up
2551 * the dmapctl tree as required by the new leaf value.
2552 */
2554 /* check if we are in the middle of a binary buddy
2555 * system. this happens when we are performing the
2556 * first allocation out of an allocation group that
2557 * is part (not the first part) of a larger binary
2558 * buddy system. if we are in the middle, back split
2559 * the system prior to calling dbSplit() which assumes
2560 * that it is at the front of a binary buddy system.
2561 */
2567 }
2573 }
2575 /* check if the root of the current dmap control page changed due
2576 * to the update and if the current dmap control page is not at
2577 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2578 * root changed and this is not the top level), call this routine
2579 * again (recursion) for the next higher level of the mapping to
2580 * reflect the change in root for the current dmap control page.
2581 */
2583 /* are we below the top level of the map. if so,
2584 * bubble the root up to the next higher level.
2585 */
2587 /* bubble up the new root of this dmap control page to
2588 * the next level.
2589 */
2593 /* something went wrong in bubbling up the new
2594 * root value, so backout the changes to the
2595 * current dmap control page.
2596 */
2599 oldval);
2601 /* the dbJoin() above might have
2602 * caused a larger binary buddy system
2603 * to form and we may now be in the
2604 * middle of it. if this is the case,
2605 * back split the buddies.
2606 */
2612 }
2614 /* release the buffer and return the error.
2615 */
2618 }
2620 /* we're at the top level of the map. update
2621 * the bmap control page to reflect the size
2622 * of the maximum free buddy system.
2623 */
2628 }
2630 }
2631 }
2633 /* write the buffer.
2634 */
2638 }
2641 /*
2642 * NAME: dbSplit()
2643 *
2644 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2645 * the leaf from the binary buddy system of the dmtree's
2646 * leaves, as required.
2647 *
2648 * PARAMETERS:
2649 * tp - pointer to the tree containing the leaf.
2650 * leafno - the number of the leaf to be updated.
2651 * splitsz - the size the binary buddy system starting at the leaf
2652 * must be split to, specified as the log2 number of blocks.
2653 * newval - the new value for the leaf.
2654 *
2655 * RETURN VALUES: none
2656 *
2657 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2658 */
2660 {
2665 /* check if the leaf needs to be split.
2666 */
2668 /* the split occurs by cutting the buddy system in half
2669 * at the specified leaf until we reach the specified
2670 * size. pick up the starting split size (current size
2671 * - 1 in l2) and the corresponding buddy size.
2672 */
2676 /* split until we reach the specified size.
2677 */
2679 /* update the buddy's leaf with its new value.
2680 */
2683 /* on to the next size and buddy.
2684 */
2687 }
2688 }
2690 /* adjust the dmap tree to reflect the specified leaf's new
2691 * value.
2692 */
2694 }
2697 /*
2698 * NAME: dbBackSplit()
2699 *
2700 * FUNCTION: back split the binary buddy system of dmtree leaves
2701 * that hold a specified leaf until the specified leaf
2702 * starts its own binary buddy system.
2703 *
2704 * the allocators typically perform allocations at the start
2705 * of binary buddy systems and dbSplit() is used to accomplish
2706 * any required splits. in some cases, however, allocation
2707 * may occur in the middle of a binary system and requires a
2708 * back split, with the split proceeding out from the middle of
2709 * the system (less efficient) rather than the start of the
2710 * system (more efficient). the cases in which a back split
2711 * is required are rare and are limited to the first allocation
2712 * within an allocation group which is a part (not first part)
2713 * of a larger binary buddy system and a few exception cases
2714 * in which a previous join operation must be backed out.
2715 *
2716 * PARAMETERS:
2717 * tp - pointer to the tree containing the leaf.
2718 * leafno - the number of the leaf to be updated.
2719 *
2720 * RETURN VALUES: none
2721 *
2722 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2723 */
2725 {
2730 /* leaf should be part (not first part) of a binary
2731 * buddy system.
2732 */
2735 /* the back split is accomplished by iteratively finding the leaf
2736 * that starts the buddy system that contains the specified leaf and
2737 * splitting that system in two. this iteration continues until
2738 * the specified leaf becomes the start of a buddy system.
2739 *
2740 * determine maximum possible l2 size for the specified leaf.
2741 */
2742 size =
2746 /* determine the number of leaves covered by this size. this
2747 * is the buddy size that we will start with as we search for
2748 * the buddy system that contains the specified leaf.
2749 */
2752 /* back split.
2753 */
2755 /* find the leftmost buddy leaf.
2756 */
2762 }
2764 /* determine the buddy.
2765 */
2768 /* check if this buddy is the start of the system.
2769 */
2771 /* split the leaf at the start of the
2772 * system in two.
2773 */
2777 }
2778 }
2779 }
2784 }
2786 }
2789 /*
2790 * NAME: dbJoin()
2791 *
2792 * FUNCTION: update the leaf of a dmtree with a new value, joining
2793 * the leaf with other leaves of the dmtree into a multi-leaf
2794 * binary buddy system, as required.
2795 *
2796 * PARAMETERS:
2797 * tp - pointer to the tree containing the leaf.
2798 * leafno - the number of the leaf to be updated.
2799 * newval - the new value for the leaf.
2800 *
2801 * RETURN VALUES: none
2802 */
2804 {
2808 /* can the new leaf value require a join with other leaves ?
2809 */
2811 /* pickup a pointer to the leaves of the tree.
2812 */
2815 /* try to join the specified leaf into a large binary
2816 * buddy system. the join proceeds by attempting to join
2817 * the specified leafno with its buddy (leaf) at new value.
2818 * if the join occurs, we attempt to join the left leaf
2819 * of the joined buddies with its buddy at new value + 1.
2820 * we continue to join until we find a buddy that cannot be
2821 * joined (does not have a value equal to the size of the
2822 * last join) or until all leaves have been joined into a
2823 * single system.
2824 *
2825 * get the buddy size (number of words covered) of
2826 * the new value.
2827 */
2830 /* try to join.
2831 */
2833 /* get the buddy leaf.
2834 */
2837 /* if the leaf's new value is greater than its
2838 * buddy's value, we join no more.
2839 */
2843 /* It shouldn't be less */
2847 /* check which (leafno or buddy) is the left buddy.
2848 * the left buddy gets to claim the blocks resulting
2849 * from the join while the right gets to claim none.
2850 * the left buddy is also eligible to participate in
2851 * a join at the next higher level while the right
2852 * is not.
2853 *
2854 */
2856 /* leafno is the left buddy.
2857 */
2860 /* buddy is the left buddy and becomes
2861 * leafno.
2862 */
2865 }
2867 /* on to try the next join.
2868 */
2871 }
2872 }
2874 /* update the leaf value.
2875 */
2879 }
2882 /*
2883 * NAME: dbAdjTree()
2884 *
2885 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2886 * the dmtree, as required, to reflect the new leaf value.
2887 * the combination of any buddies must already be done before
2888 * this is called.
2889 *
2890 * PARAMETERS:
2891 * tp - pointer to the tree to be adjusted.
2892 * leafno - the number of the leaf to be updated.
2893 * newval - the new value for the leaf.
2894 *
2895 * RETURN VALUES: none
2896 */
2898 {
2902 /* pick up the index of the leaf for this leafno.
2903 */
2906 /* is the current value the same as the old value ? if so,
2907 * there is nothing to do.
2908 */
2912 /* set the new value.
2913 */
2916 /* bubble the new value up the tree as required.
2917 */
2919 /* get the index of the first leaf of the 4 leaf
2920 * group containing the specified leaf (leafno).
2921 */
2924 /* get the index of the parent of this 4 leaf group.
2925 */
2928 /* determine the maximum of the 4 leaves.
2929 */
2932 /* if the maximum of the 4 is the same as the
2933 * parent's value, we're done.
2934 */
2938 /* parent gets new value.
2939 */
2942 /* parent becomes leaf for next go-round.
2943 */
2945 }
2946 }
2949 /*
2950 * NAME: dbFindLeaf()
2951 *
2952 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2953 * the index of a leaf describing the free blocks if
2954 * sufficient free blocks are found.
2955 *
2956 * the search starts at the top of the dmtree_t tree and
2957 * proceeds down the tree to the leftmost leaf with sufficient
2958 * free space.
2959 *
2960 * PARAMETERS:
2961 * tp - pointer to the tree to be searched.
2962 * l2nb - log2 number of free blocks to search for.
2963 * leafidx - return pointer to be set to the index of the leaf
2964 * describing at least l2nb free blocks if sufficient
2965 * free blocks are found.
2966 *
2967 * RETURN VALUES:
2968 * 0 - success
2969 * -ENOSPC - insufficient free blocks.
2970 */
2972 {
2975 /* first check the root of the tree to see if there is
2976 * sufficient free space.
2977 */
2981 /* sufficient free space available. now search down the tree
2982 * starting at the next level for the leftmost leaf that
2983 * describes sufficient free space.
2984 */
2987 /* search the four nodes at this level, starting from
2988 * the left.
2989 */
2991 /* sufficient free space found. move to the next
2992 * level (or quit if this is the last level).
2993 */
2996 }
2998 /* better have found something since the higher
2999 * levels of the tree said it was here.
3000 */
3002 }
3004 /* set the return to the leftmost leaf describing sufficient
3005 * free space.
3006 */
3010 }
3013 /*
3014 * NAME: dbFindBits()
3015 *
3016 * FUNCTION: find a specified number of binary buddy free bits within a
3017 * dmap bitmap word value.
3018 *
3019 * this routine searches the bitmap value for (1 << l2nb) free
3020 * bits at (1 << l2nb) alignments within the value.
3021 *
3022 * PARAMETERS:
3023 * word - dmap bitmap word value.
3024 * l2nb - number of free bits specified as a log2 number.
3025 *
3026 * RETURN VALUES:
3027 * starting bit number of free bits.
3028 */
3030 {
3032 u32 mask;
3034 /* get the number of bits.
3035 */
3039 /* complement the word so we can use a mask (i.e. 0s represent
3040 * free bits) and compute the mask.
3041 */
3045 /* scan the word for nb free bits at nb alignments.
3046 */
3050 }
3054 /* return the bit number.
3055 */
3057 }
3060 /*
3061 * NAME: dbMaxBud(u8 *cp)
3062 *
3063 * FUNCTION: determine the largest binary buddy string of free
3064 * bits within 32-bits of the map.
3065 *
3066 * PARAMETERS:
3067 * cp - pointer to the 32-bit value.
3068 *
3069 * RETURN VALUES:
3070 * largest binary buddy of free bits within a dmap word.
3071 */
3073 {
3076 /* check if the wmap word is all free. if so, the
3077 * free buddy size is BUDMIN.
3078 */
3082 /* check if the wmap word is half free. if so, the
3083 * free buddy size is BUDMIN-1.
3084 */
3088 /* not all free or half free. determine the free buddy
3089 * size thru table lookup using quarters of the wmap word.
3090 */
3094 }
3097 /*
3098 * NAME: cnttz(uint word)
3099 *
3100 * FUNCTION: determine the number of trailing zeros within a 32-bit
3101 * value.
3102 *
3103 * PARAMETERS:
3104 * value - 32-bit value to be examined.
3105 *
3106 * RETURN VALUES:
3107 * count of trailing zeros
3108 */
3110 {
3116 }
3119 }
3122 /*
3123 * NAME: cntlz(u32 value)
3124 *
3125 * FUNCTION: determine the number of leading zeros within a 32-bit
3126 * value.
3127 *
3128 * PARAMETERS:
3129 * value - 32-bit value to be examined.
3130 *
3131 * RETURN VALUES:
3132 * count of leading zeros
3133 */
3135 {
3141 }
3143 }
3146 /*
3147 * NAME: blkstol2(s64 nb)
3148 *
3149 * FUNCTION: convert a block count to its log2 value. if the block
3150 * count is not a l2 multiple, it is rounded up to the next
3151 * larger l2 multiple.
3152 *
3153 * PARAMETERS:
3154 * nb - number of blocks
3155 *
3156 * RETURN VALUES:
3157 * log2 number of blocks
3158 */
3160 {
3166 /* count the leading bits.
3167 */
3169 /* leading bit found.
3170 */
3172 /* determine the l2 value.
3173 */
3176 /* check if we need to round up.
3177 */
3179 l2nb++;
3182 }
3183 }
3186 }
3189 /*
3190 * NAME: dbAllocBottomUp()
3191 *
3192 * FUNCTION: alloc the specified block range from the working block
3193 * allocation map.
3194 *
3195 * the blocks will be alloc from the working map one dmap
3196 * at a time.
3197 *
3198 * PARAMETERS:
3199 * ip - pointer to in-core inode;
3200 * blkno - starting block number to be freed.
3201 * nblocks - number of blocks to be freed.
3202 *
3203 * RETURN VALUES:
3204 * 0 - success
3205 * -EIO - i/o error
3206 */
3208 {
3218 /* block to be allocated better be within the mapsize. */
3221 /*
3222 * allocate the blocks a dmap at a time.
3223 */
3226 /* release previous dmap if any */
3229 }
3231 /* get the buffer for the current dmap. */
3237 }
3240 /* determine the number of blocks to be allocated from
3241 * this dmap.
3242 */
3245 /* allocate the blocks. */
3250 }
3251 }
3253 /* write the last buffer. */
3259 }
3264 {
3267 s8 oldroot;
3270 /* save the current value of the root (i.e. maximum free string)
3271 * of the dmap tree.
3272 */
3275 /* determine the bit number and word within the dmap of the
3276 * starting block.
3277 */
3281 /* block range better be within the dmap */
3284 /* allocate the bits of the dmap's words corresponding to the block
3285 * range. not all bits of the first and last words may be contained
3286 * within the block range. if this is the case, we'll work against
3287 * those words (i.e. partial first and/or last) on an individual basis
3288 * (a single pass), allocating the bits of interest by hand and
3289 * updating the leaf corresponding to the dmap word. a single pass
3290 * will be used for all dmap words fully contained within the
3291 * specified range. within this pass, the bits of all fully contained
3292 * dmap words will be marked as free in a single shot and the leaves
3293 * will be updated. a single leaf may describe the free space of
3294 * multiple dmap words, so we may update only a subset of the actual
3295 * leaves corresponding to the dmap words of the block range.
3296 */
3298 /* determine the bit number within the word and
3299 * the number of bits within the word.
3300 */
3304 /* check if only part of a word is to be allocated.
3305 */
3307 /* allocate (set to 1) the appropriate bits within
3308 * this dmap word.
3309 */
3313 word++;
3315 /* one or more dmap words are fully contained
3316 * within the block range. determine how many
3317 * words and allocate (set to 1) the bits of these
3318 * words.
3319 */
3323 /* determine how many bits */
3326 }
3327 }
3329 /* update the free count for this dmap */
3332 /* reconstruct summary tree */
3337 /* if this allocation group is completely free,
3338 * update the highest active allocation group number
3339 * if this allocation group is the new max.
3340 */
3345 /* update the free count for the allocation group and map */
3351 /* if the root has not changed, done. */
3355 /* root changed. bubble the change up to the dmap control pages.
3356 * if the adjustment of the upper level control pages fails,
3357 * backout the bit allocation (thus making everything consistent).
3358 */
3363 }
3366 /*
3367 * NAME: dbExtendFS()
3368 *
3369 * FUNCTION: extend bmap from blkno for nblocks;
3370 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3371 *
3372 * L2
3373 * |
3374 * L1---------------------------------L1
3375 * | |
3376 * L0---------L0---------L0 L0---------L0---------L0
3377 * | | | | | |
3378 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3379 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3380 *
3381 * <---old---><----------------------------extend----------------------->
3382 */
3384 {
3388 s64 newsize;
3389 s64 p;
3396 s64 ag_rem;
3403 /*
3404 * initialize bmap control page.
3405 *
3406 * all the data in bmap control page should exclude
3407 * the mkfs hidden dmap page.
3408 */
3410 /* update mapsize */
3414 /* compute new AG size */
3421 /* compute new number of AG */
3426 /*
3427 * reconfigure db_agfree[]
3428 * from old AG configuration to new AG configuration;
3429 *
3430 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3431 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3432 * note: new AG size = old AG size * (2**x).
3433 */
3441 /* coalesce contiguous k AGs; */
3443 /* merge AGi to AGn */
3445 }
3446 }
3452 /*
3453 * update highest active ag number
3454 */
3458 /*
3459 * extend bmap
3460 *
3461 * update bit maps and corresponding level control pages;
3462 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3463 */
3464 extend:
3465 /* get L2 page */
3471 }
3474 /* compute start L1 */
3479 /*
3480 * extend each L1 in L2
3481 */
3483 /* get L1 page */
3485 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3491 /* compute start L0 */
3497 /* assign/init L1 page */
3504 /* compute start L0 */
3508 }
3510 /*
3511 * extend each L0 in L1
3512 */
3514 /* get L0 page */
3516 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3523 /* compute start dmap */
3525 L2BPERDMAP;
3531 /* assign/init L0 page */
3538 /* compute start dmap */
3542 }
3544 /*
3545 * extend each dmap in L0
3546 */
3548 /*
3549 * reconstruct the dmap page, and
3550 * initialize corresponding parent L0 leaf
3551 */
3553 /* read in dmap page: */
3560 /* assign/init dmap page */
3567 }
3578 l0leaf++;
3587 /*
3588 * build current L0 page from its leaves, and
3589 * initialize corresponding parent L1 leaf
3590 */
3598 /* more than 1 L0 ? */
3602 /* summarize in global bmap page */
3607 }
3608 }
3611 /*
3612 * build current L1 page from its leaves, and
3613 * initialize corresponding parent L2 leaf
3614 */
3622 /* more than 1 L1 ? */
3626 /* summarize in global bmap page */
3630 }
3631 }
3635 errout:
3643 /*
3644 * finalize bmap control page
3645 */
3646 finalize:
3649 }
3652 /*
3653 * dbFinalizeBmap()
3654 */
3656 {
3662 /*
3663 * finalize bmap control page
3664 */
3665 //finalize:
3666 /*
3667 * compute db_agpref: preferred ag to allocate from
3668 * (the leftmost ag with average free space in it);
3669 */
3670 //agpref:
3671 /* get the number of active ags and inacitve ags */
3676 /* determine how many blocks are in the inactive allocation
3677 * groups. in doing this, we must account for the fact that
3678 * the rightmost group might be a partial group (i.e. file
3679 * system size is not a multiple of the group size).
3680 */
3685 /* determine how many free blocks are in the active
3686 * allocation groups plus the average number of free blocks
3687 * within the active ags.
3688 */
3692 /* if the preferred allocation group has not average free space.
3693 * re-establish the preferred group as the leftmost
3694 * group with average free space.
3695 */
3701 }
3705 }
3706 }
3708 /*
3709 * compute db_aglevel, db_agheight, db_width, db_agstart:
3710 * an ag is covered in aglevel dmapctl summary tree,
3711 * at agheight level height (from leaf) with agwidth number of nodes
3712 * each, which starts at agstart index node of the smmary tree node
3713 * array;
3714 */
3716 l2nl =
3721 i--) {
3724 }
3726 }
3729 /*
3730 * NAME: dbInitDmap()/ujfs_idmap_page()
3731 *
3732 * FUNCTION: initialize working/persistent bitmap of the dmap page
3733 * for the specified number of blocks:
3734 *
3735 * at entry, the bitmaps had been initialized as free (ZEROS);
3736 * The number of blocks will only account for the actually
3737 * existing blocks. Blocks which don't actually exist in
3738 * the aggregate will be marked as allocated (ONES);
3739 *
3740 * PARAMETERS:
3741 * dp - pointer to page of map
3742 * nblocks - number of blocks this page
3743 *
3744 * RETURNS: NONE
3745 */
3747 {
3750 /* starting block number within the dmap */
3761 }
3765 }
3767 /* word number containing start block number */
3770 /*
3771 * free the bits corresponding to the block range (ZEROS):
3772 * note: not all bits of the first and last words may be contained
3773 * within the block range.
3774 */
3776 /* number of bits preceding range to be freed in the word */
3778 /* number of bits to free in the word */
3781 /* is partial word to be freed ? */
3783 /* free (set to 0) from the bitmap word */
3789 /* skip the word freed */
3790 w++;
3792 /* free (set to 0) contiguous bitmap words */
3797 /* skip the words freed */
3800 }
3801 }
3803 /*
3804 * mark bits following the range to be freed (non-existing
3805 * blocks) as allocated (ONES)
3806 */
3811 /* the first word beyond the end of existing blocks */
3814 /* does nblocks fall on a 32-bit boundary ? */
3817 /* mark a partial word allocated */
3819 w++;
3820 }
3822 /* set the rest of the words in the page to allocated (ONES) */
3826 /*
3827 * init tree
3828 */
3829 initTree:
3831 }
3834 /*
3835 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3836 *
3837 * FUNCTION: initialize summary tree of the specified dmap:
3838 *
3839 * at entry, bitmap of the dmap has been initialized;
3840 *
3841 * PARAMETERS:
3842 * dp - dmap to complete
3843 * blkno - starting block number for this dmap
3844 * treemax - will be filled in with max free for this dmap
3845 *
3846 * RETURNS: max free string at the root of the tree
3847 */
3849 {
3854 /* init fixed info of tree */
3862 /* init each leaf from corresponding wmap word:
3863 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3864 * bitmap word are allocated.
3865 */
3870 /* build the dmap's binary buddy summary tree */
3872 }
3875 /*
3876 * NAME: dbInitTree()/ujfs_adjtree()
3877 *
3878 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3879 *
3880 * at entry, the leaves of the tree has been initialized
3881 * from corresponding bitmap word or root of summary tree
3882 * of the child control page;
3883 * configure binary buddy system at the leaf level, then
3884 * bubble up the values of the leaf nodes up the tree.
3885 *
3886 * PARAMETERS:
3887 * cp - Pointer to the root of the tree
3888 * l2leaves- Number of leaf nodes as a power of 2
3889 * l2min - Number of blocks that can be covered by a leaf
3890 * as a power of 2
3891 *
3892 * RETURNS: max free string at the root of the tree
3893 */
3895 {
3902 /* Determine the maximum free string possible for the leaves */
3905 /*
3906 * configure the leaf levevl into binary buddy system
3907 *
3908 * Try to combine buddies starting with a buddy size of 1
3909 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3910 * can be combined if both buddies have a maximum free of l2min;
3911 * the combination will result in the left-most buddy leaf having
3912 * a maximum free of l2min+1.
3913 * After processing all buddies for a given size, process buddies
3914 * at the next higher buddy size (i.e. current size * 2) and
3915 * the next maximum free (current free + 1).
3916 * This continues until the maximum possible buddy combination
3917 * yields maximum free.
3918 */
3921 /* get next buddy size == current buddy pair size */
3924 /* scan each adjacent buddy pair at current buddy size */
3928 /* coalesce if both adjacent buddies are max free */
3932 }
3933 }
3934 }
3936 /*
3937 * bubble summary information of leaves up the tree.
3938 *
3939 * Starting at the leaf node level, the four nodes described by
3940 * the higher level parent node are compared for a maximum free and
3941 * this maximum becomes the value of the parent node.
3942 * when all lower level nodes are processed in this fashion then
3943 * move up to the next level (parent becomes a lower level node) and
3944 * continue the process for that level.
3945 */
3949 /* get index of 1st node of parent level */
3952 /* set the value of the parent node as the maximum
3953 * of the four nodes of the current level.
3954 */
3958 }
3961 }
3964 /*
3965 * dbInitDmapCtl()
3966 *
3967 * function: initialize dmapctl page
3968 */
3979 /*
3980 * initialize the leaves of current level that were not covered
3981 * by the specified input block range (i.e. the leaves have no
3982 * low level dmapctl or dmap).
3983 */
3988 /* build the dmap's binary buddy summary tree */
3990 }
3993 /*
3994 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3995 *
3996 * FUNCTION: Determine log2(allocation group size) from aggregate size
3997 *
3998 * PARAMETERS:
3999 * nblocks - Number of blocks in aggregate
4000 *
4001 * RETURNS: log2(allocation group size) in aggregate blocks
4002 */
4004 {
4005 s64 sz;
4006 s64 m;
4012 /* round up aggregate size to power of 2 */
4017 }
4023 /* agsize = roundupSize/max_number_of_ag */
4025 }
4028 /*
4029 * NAME: dbMapFileSizeToMapSize()
4030 *
4031 * FUNCTION: compute number of blocks the block allocation map file
4032 * can cover from the map file size;
4033 *
4034 * RETURNS: Number of blocks which can be covered by this block map file;
4035 */
4037 /*
4038 * maximum number of map pages at each level including control pages
4039 */
4040 #define MAXL0PAGES (1 + LPERCTL)
4041 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
4042 #define MAXL2PAGES (1 + LPERCTL * MAXL1PAGES)
4044 /*
4045 * convert number of map pages to the zero origin top dmapctl level
4046 */
4047 #define BMAPPGTOLEV(npages) \
4048 (((npages) <= 3 + MAXL0PAGES) ? 0 : \
4049 ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4052 {
4054 s64 nblocks;
4063 /* At each level, accumulate the number of dmap pages covered by
4064 * the number of full child levels below it;
4065 * repeat for the last incomplete child level.
4066 */
4069 /* skip higher level control pages above top level covered by map */
4073 factor =
4079 /* pages in last/incomplete child */
4081 /* skip incomplete child's level control page */
4082 npages--;
4083 }
4085 /* convert the number of dmaps into the number of blocks
4086 * which can be covered by the dmaps;
4087 */
4091 }