| blob | 2d514c7affc2ab9382fa812bc173874f3b58b8e9 |
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 */
2266 /* update the leaf to reflect the allocation.
2267 * in addition to setting the leaf value to
2268 * NOFREE, dbSplit() will split the binary
2269 * system of the leaves to reflect the current
2270 * allocation (size).
2271 */
2274 /* get the number of dmap words handled */
2277 }
2278 }
2279 }
2281 /* update the free count for this dmap */
2286 /* if this allocation group is completely free,
2287 * update the maximum allocation group number if this allocation
2288 * group is the new max.
2289 */
2294 /* update the free count for the allocation group and map */
2299 }
2302 /*
2303 * NAME: dbFreeBits()
2304 *
2305 * FUNCTION: free a specified block range from a dmap.
2306 *
2307 * this routine updates the dmap to reflect the working
2308 * state allocation of the specified block range. it directly
2309 * updates the bits of the working map and causes the adjustment
2310 * of the binary buddy system described by the dmap's dmtree
2311 * leaves to reflect the bits freed. it also causes the dmap's
2312 * dmtree, as a whole, to reflect the deallocated range.
2313 *
2314 * PARAMETERS:
2315 * bmp - pointer to bmap descriptor
2316 * dp - pointer to dmap to free bits from.
2317 * blkno - starting block number of the bits to be freed.
2318 * nblocks - number of bits to be freed.
2319 *
2320 * RETURN VALUES: 0 for success
2321 *
2322 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2323 */
2326 {
2332 /* determine the bit number and word within the dmap of the
2333 * starting block.
2334 */
2338 /* block range better be within the dmap.
2339 */
2342 /* free the bits of the dmaps words corresponding to the block range.
2343 * not all bits of the first and last words may be contained within
2344 * the block range. if this is the case, we'll work against those
2345 * words (i.e. partial first and/or last) on an individual basis
2346 * (a single pass), freeing the bits of interest by hand and updating
2347 * the leaf corresponding to the dmap word. a single pass will be used
2348 * for all dmap words fully contained within the specified range.
2349 * within this pass, the bits of all fully contained dmap words will
2350 * be marked as free in a single shot and the leaves will be updated. a
2351 * single leaf may describe the free space of multiple dmap words,
2352 * so we may update only a subset of the actual leaves corresponding
2353 * to the dmap words of the block range.
2354 *
2355 * dbJoin() is used to update leaf values and will join the binary
2356 * buddy system of the leaves if the new leaf values indicate this
2357 * should be done.
2358 */
2360 /* determine the bit number within the word and
2361 * the number of bits within the word.
2362 */
2366 /* check if only part of a word is to be freed.
2367 */
2369 /* free (zero) the appropriate bits within this
2370 * dmap word.
2371 */
2376 /* update the leaf for this dmap word.
2377 */
2385 /* one or more dmap words are fully contained
2386 * within the block range. determine how many
2387 * words and free (zero) the bits of these words.
2388 */
2392 /* determine how many bits.
2393 */
2396 /* now update the appropriate leaves to reflect
2397 * the freed words.
2398 */
2400 /* determine what the leaf value should be
2401 * updated to as the minimum of the l2 number
2402 * of bits being freed and the l2 (max) number
2403 * of bits that can be described by this leaf.
2404 */
2405 size =
2410 /* update the leaf.
2411 */
2416 /* get the number of dmap words handled.
2417 */
2420 }
2421 }
2422 }
2424 /* update the free count for this dmap.
2425 */
2430 /* update the free count for the allocation group and
2431 * map.
2432 */
2437 /* check if this allocation group is not completely free and
2438 * if it is currently the maximum (rightmost) allocation group.
2439 * if so, establish the new maximum allocation group number by
2440 * searching left for the first allocation group with allocation.
2441 */
2450 }
2452 /* re-establish the allocation group preference if the
2453 * current preference is right of the maximum allocation
2454 * group.
2455 */
2458 }
2463 }
2466 /*
2467 * NAME: dbAdjCtl()
2468 *
2469 * FUNCTION: adjust a dmap control page at a specified level to reflect
2470 * the change in a lower level dmap or dmap control page's
2471 * maximum string of free blocks (i.e. a change in the root
2472 * of the lower level object's dmtree) due to the allocation
2473 * or deallocation of a range of blocks with a single dmap.
2474 *
2475 * on entry, this routine is provided with the new value of
2476 * the lower level dmap or dmap control page root and the
2477 * starting block number of the block range whose allocation
2478 * or deallocation resulted in the root change. this range
2479 * is respresented by a single leaf of the current dmapctl
2480 * and the leaf will be updated with this value, possibly
2481 * causing a binary buddy system within the leaves to be
2482 * split or joined. the update may also cause the dmapctl's
2483 * dmtree to be updated.
2484 *
2485 * if the adjustment of the dmap control page, itself, causes its
2486 * root to change, this change will be bubbled up to the next dmap
2487 * control level by a recursive call to this routine, specifying
2488 * the new root value and the next dmap control page level to
2489 * be adjusted.
2490 * PARAMETERS:
2491 * bmp - pointer to bmap descriptor
2492 * blkno - the first block of a block range within a dmap. it is
2493 * the allocation or deallocation of this block range that
2494 * requires the dmap control page to be adjusted.
2495 * newval - the new value of the lower level dmap or dmap control
2496 * page root.
2497 * alloc - 'true' if adjustment is due to an allocation.
2498 * level - current level of dmap control page (i.e. L0, L1, L2) to
2499 * be adjusted.
2500 *
2501 * RETURN VALUES:
2502 * 0 - success
2503 * -EIO - i/o error
2504 *
2505 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2506 */
2507 static int
2509 {
2511 s8 oldroot;
2513 s64 lblkno;
2517 /* get the buffer for the dmap control page for the specified
2518 * block number and control page level.
2519 */
2530 }
2532 /* determine the leaf number corresponding to the block and
2533 * the index within the dmap control tree.
2534 */
2538 /* save the current leaf value and the current root level (i.e.
2539 * maximum l2 free string described by this dmapctl).
2540 */
2544 /* check if this is a control page update for an allocation.
2545 * if so, update the leaf to reflect the new leaf value using
2546 * dbSplit(); otherwise (deallocation), use dbJoin() to update
2547 * the leaf with the new value. in addition to updating the
2548 * leaf, dbSplit() will also split the binary buddy system of
2549 * the leaves, if required, and bubble new values within the
2550 * dmapctl tree, if required. similarly, dbJoin() will join
2551 * the binary buddy system of leaves and bubble new values up
2552 * the dmapctl tree as required by the new leaf value.
2553 */
2555 /* check if we are in the middle of a binary buddy
2556 * system. this happens when we are performing the
2557 * first allocation out of an allocation group that
2558 * is part (not the first part) of a larger binary
2559 * buddy system. if we are in the middle, back split
2560 * the system prior to calling dbSplit() which assumes
2561 * that it is at the front of a binary buddy system.
2562 */
2568 }
2574 }
2576 /* check if the root of the current dmap control page changed due
2577 * to the update and if the current dmap control page is not at
2578 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2579 * root changed and this is not the top level), call this routine
2580 * again (recursion) for the next higher level of the mapping to
2581 * reflect the change in root for the current dmap control page.
2582 */
2584 /* are we below the top level of the map. if so,
2585 * bubble the root up to the next higher level.
2586 */
2588 /* bubble up the new root of this dmap control page to
2589 * the next level.
2590 */
2594 /* something went wrong in bubbling up the new
2595 * root value, so backout the changes to the
2596 * current dmap control page.
2597 */
2600 oldval);
2602 /* the dbJoin() above might have
2603 * caused a larger binary buddy system
2604 * to form and we may now be in the
2605 * middle of it. if this is the case,
2606 * back split the buddies.
2607 */
2613 }
2615 /* release the buffer and return the error.
2616 */
2619 }
2621 /* we're at the top level of the map. update
2622 * the bmap control page to reflect the size
2623 * of the maximum free buddy system.
2624 */
2629 }
2631 }
2632 }
2634 /* write the buffer.
2635 */
2639 }
2642 /*
2643 * NAME: dbSplit()
2644 *
2645 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2646 * the leaf from the binary buddy system of the dmtree's
2647 * leaves, as required.
2648 *
2649 * PARAMETERS:
2650 * tp - pointer to the tree containing the leaf.
2651 * leafno - the number of the leaf to be updated.
2652 * splitsz - the size the binary buddy system starting at the leaf
2653 * must be split to, specified as the log2 number of blocks.
2654 * newval - the new value for the leaf.
2655 *
2656 * RETURN VALUES: none
2657 *
2658 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2659 */
2661 {
2666 /* check if the leaf needs to be split.
2667 */
2669 /* the split occurs by cutting the buddy system in half
2670 * at the specified leaf until we reach the specified
2671 * size. pick up the starting split size (current size
2672 * - 1 in l2) and the corresponding buddy size.
2673 */
2677 /* split until we reach the specified size.
2678 */
2680 /* update the buddy's leaf with its new value.
2681 */
2684 /* on to the next size and buddy.
2685 */
2688 }
2689 }
2691 /* adjust the dmap tree to reflect the specified leaf's new
2692 * value.
2693 */
2695 }
2698 /*
2699 * NAME: dbBackSplit()
2700 *
2701 * FUNCTION: back split the binary buddy system of dmtree leaves
2702 * that hold a specified leaf until the specified leaf
2703 * starts its own binary buddy system.
2704 *
2705 * the allocators typically perform allocations at the start
2706 * of binary buddy systems and dbSplit() is used to accomplish
2707 * any required splits. in some cases, however, allocation
2708 * may occur in the middle of a binary system and requires a
2709 * back split, with the split proceeding out from the middle of
2710 * the system (less efficient) rather than the start of the
2711 * system (more efficient). the cases in which a back split
2712 * is required are rare and are limited to the first allocation
2713 * within an allocation group which is a part (not first part)
2714 * of a larger binary buddy system and a few exception cases
2715 * in which a previous join operation must be backed out.
2716 *
2717 * PARAMETERS:
2718 * tp - pointer to the tree containing the leaf.
2719 * leafno - the number of the leaf to be updated.
2720 *
2721 * RETURN VALUES: none
2722 *
2723 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2724 */
2726 {
2731 /* leaf should be part (not first part) of a binary
2732 * buddy system.
2733 */
2736 /* the back split is accomplished by iteratively finding the leaf
2737 * that starts the buddy system that contains the specified leaf and
2738 * splitting that system in two. this iteration continues until
2739 * the specified leaf becomes the start of a buddy system.
2740 *
2741 * determine maximum possible l2 size for the specified leaf.
2742 */
2743 size =
2747 /* determine the number of leaves covered by this size. this
2748 * is the buddy size that we will start with as we search for
2749 * the buddy system that contains the specified leaf.
2750 */
2753 /* back split.
2754 */
2756 /* find the leftmost buddy leaf.
2757 */
2763 }
2765 /* determine the buddy.
2766 */
2769 /* check if this buddy is the start of the system.
2770 */
2772 /* split the leaf at the start of the
2773 * system in two.
2774 */
2778 }
2779 }
2780 }
2785 }
2787 }
2790 /*
2791 * NAME: dbJoin()
2792 *
2793 * FUNCTION: update the leaf of a dmtree with a new value, joining
2794 * the leaf with other leaves of the dmtree into a multi-leaf
2795 * binary buddy system, as required.
2796 *
2797 * PARAMETERS:
2798 * tp - pointer to the tree containing the leaf.
2799 * leafno - the number of the leaf to be updated.
2800 * newval - the new value for the leaf.
2801 *
2802 * RETURN VALUES: none
2803 */
2805 {
2809 /* can the new leaf value require a join with other leaves ?
2810 */
2812 /* pickup a pointer to the leaves of the tree.
2813 */
2816 /* try to join the specified leaf into a large binary
2817 * buddy system. the join proceeds by attempting to join
2818 * the specified leafno with its buddy (leaf) at new value.
2819 * if the join occurs, we attempt to join the left leaf
2820 * of the joined buddies with its buddy at new value + 1.
2821 * we continue to join until we find a buddy that cannot be
2822 * joined (does not have a value equal to the size of the
2823 * last join) or until all leaves have been joined into a
2824 * single system.
2825 *
2826 * get the buddy size (number of words covered) of
2827 * the new value.
2828 */
2831 /* try to join.
2832 */
2834 /* get the buddy leaf.
2835 */
2838 /* if the leaf's new value is greater than its
2839 * buddy's value, we join no more.
2840 */
2844 /* It shouldn't be less */
2848 /* check which (leafno or buddy) is the left buddy.
2849 * the left buddy gets to claim the blocks resulting
2850 * from the join while the right gets to claim none.
2851 * the left buddy is also eligible to participate in
2852 * a join at the next higher level while the right
2853 * is not.
2854 *
2855 */
2857 /* leafno is the left buddy.
2858 */
2861 /* buddy is the left buddy and becomes
2862 * leafno.
2863 */
2866 }
2868 /* on to try the next join.
2869 */
2872 }
2873 }
2875 /* update the leaf value.
2876 */
2880 }
2883 /*
2884 * NAME: dbAdjTree()
2885 *
2886 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2887 * the dmtree, as required, to reflect the new leaf value.
2888 * the combination of any buddies must already be done before
2889 * this is called.
2890 *
2891 * PARAMETERS:
2892 * tp - pointer to the tree to be adjusted.
2893 * leafno - the number of the leaf to be updated.
2894 * newval - the new value for the leaf.
2895 *
2896 * RETURN VALUES: none
2897 */
2899 {
2903 /* pick up the index of the leaf for this leafno.
2904 */
2907 /* is the current value the same as the old value ? if so,
2908 * there is nothing to do.
2909 */
2913 /* set the new value.
2914 */
2917 /* bubble the new value up the tree as required.
2918 */
2920 /* get the index of the first leaf of the 4 leaf
2921 * group containing the specified leaf (leafno).
2922 */
2925 /* get the index of the parent of this 4 leaf group.
2926 */
2929 /* determine the maximum of the 4 leaves.
2930 */
2933 /* if the maximum of the 4 is the same as the
2934 * parent's value, we're done.
2935 */
2939 /* parent gets new value.
2940 */
2943 /* parent becomes leaf for next go-round.
2944 */
2946 }
2947 }
2950 /*
2951 * NAME: dbFindLeaf()
2952 *
2953 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2954 * the index of a leaf describing the free blocks if
2955 * sufficient free blocks are found.
2956 *
2957 * the search starts at the top of the dmtree_t tree and
2958 * proceeds down the tree to the leftmost leaf with sufficient
2959 * free space.
2960 *
2961 * PARAMETERS:
2962 * tp - pointer to the tree to be searched.
2963 * l2nb - log2 number of free blocks to search for.
2964 * leafidx - return pointer to be set to the index of the leaf
2965 * describing at least l2nb free blocks if sufficient
2966 * free blocks are found.
2967 *
2968 * RETURN VALUES:
2969 * 0 - success
2970 * -ENOSPC - insufficient free blocks.
2971 */
2973 {
2976 /* first check the root of the tree to see if there is
2977 * sufficient free space.
2978 */
2982 /* sufficient free space available. now search down the tree
2983 * starting at the next level for the leftmost leaf that
2984 * describes sufficient free space.
2985 */
2988 /* search the four nodes at this level, starting from
2989 * the left.
2990 */
2992 /* sufficient free space found. move to the next
2993 * level (or quit if this is the last level).
2994 */
2997 }
2999 /* better have found something since the higher
3000 * levels of the tree said it was here.
3001 */
3003 }
3005 /* set the return to the leftmost leaf describing sufficient
3006 * free space.
3007 */
3011 }
3014 /*
3015 * NAME: dbFindBits()
3016 *
3017 * FUNCTION: find a specified number of binary buddy free bits within a
3018 * dmap bitmap word value.
3019 *
3020 * this routine searches the bitmap value for (1 << l2nb) free
3021 * bits at (1 << l2nb) alignments within the value.
3022 *
3023 * PARAMETERS:
3024 * word - dmap bitmap word value.
3025 * l2nb - number of free bits specified as a log2 number.
3026 *
3027 * RETURN VALUES:
3028 * starting bit number of free bits.
3029 */
3031 {
3033 u32 mask;
3035 /* get the number of bits.
3036 */
3040 /* complement the word so we can use a mask (i.e. 0s represent
3041 * free bits) and compute the mask.
3042 */
3046 /* scan the word for nb free bits at nb alignments.
3047 */
3051 }
3055 /* return the bit number.
3056 */
3058 }
3061 /*
3062 * NAME: dbMaxBud(u8 *cp)
3063 *
3064 * FUNCTION: determine the largest binary buddy string of free
3065 * bits within 32-bits of the map.
3066 *
3067 * PARAMETERS:
3068 * cp - pointer to the 32-bit value.
3069 *
3070 * RETURN VALUES:
3071 * largest binary buddy of free bits within a dmap word.
3072 */
3074 {
3077 /* check if the wmap word is all free. if so, the
3078 * free buddy size is BUDMIN.
3079 */
3083 /* check if the wmap word is half free. if so, the
3084 * free buddy size is BUDMIN-1.
3085 */
3089 /* not all free or half free. determine the free buddy
3090 * size thru table lookup using quarters of the wmap word.
3091 */
3095 }
3098 /*
3099 * NAME: cnttz(uint word)
3100 *
3101 * FUNCTION: determine the number of trailing zeros within a 32-bit
3102 * value.
3103 *
3104 * PARAMETERS:
3105 * value - 32-bit value to be examined.
3106 *
3107 * RETURN VALUES:
3108 * count of trailing zeros
3109 */
3111 {
3117 }
3120 }
3123 /*
3124 * NAME: cntlz(u32 value)
3125 *
3126 * FUNCTION: determine the number of leading zeros within a 32-bit
3127 * value.
3128 *
3129 * PARAMETERS:
3130 * value - 32-bit value to be examined.
3131 *
3132 * RETURN VALUES:
3133 * count of leading zeros
3134 */
3136 {
3142 }
3144 }
3147 /*
3148 * NAME: blkstol2(s64 nb)
3149 *
3150 * FUNCTION: convert a block count to its log2 value. if the block
3151 * count is not a l2 multiple, it is rounded up to the next
3152 * larger l2 multiple.
3153 *
3154 * PARAMETERS:
3155 * nb - number of blocks
3156 *
3157 * RETURN VALUES:
3158 * log2 number of blocks
3159 */
3161 {
3167 /* count the leading bits.
3168 */
3170 /* leading bit found.
3171 */
3173 /* determine the l2 value.
3174 */
3177 /* check if we need to round up.
3178 */
3180 l2nb++;
3183 }
3184 }
3187 }
3190 /*
3191 * NAME: dbAllocBottomUp()
3192 *
3193 * FUNCTION: alloc the specified block range from the working block
3194 * allocation map.
3195 *
3196 * the blocks will be alloc from the working map one dmap
3197 * at a time.
3198 *
3199 * PARAMETERS:
3200 * ip - pointer to in-core inode;
3201 * blkno - starting block number to be freed.
3202 * nblocks - number of blocks to be freed.
3203 *
3204 * RETURN VALUES:
3205 * 0 - success
3206 * -EIO - i/o error
3207 */
3209 {
3219 /* block to be allocated better be within the mapsize. */
3222 /*
3223 * allocate the blocks a dmap at a time.
3224 */
3227 /* release previous dmap if any */
3230 }
3232 /* get the buffer for the current dmap. */
3238 }
3241 /* determine the number of blocks to be allocated from
3242 * this dmap.
3243 */
3246 /* allocate the blocks. */
3251 }
3252 }
3254 /* write the last buffer. */
3260 }
3265 {
3268 s8 oldroot;
3271 /* save the current value of the root (i.e. maximum free string)
3272 * of the dmap tree.
3273 */
3276 /* determine the bit number and word within the dmap of the
3277 * starting block.
3278 */
3282 /* block range better be within the dmap */
3285 /* allocate the bits of the dmap's words corresponding to the block
3286 * range. not all bits of the first and last words may be contained
3287 * within the block range. if this is the case, we'll work against
3288 * those words (i.e. partial first and/or last) on an individual basis
3289 * (a single pass), allocating the bits of interest by hand and
3290 * updating the leaf corresponding to the dmap word. a single pass
3291 * will be used for all dmap words fully contained within the
3292 * specified range. within this pass, the bits of all fully contained
3293 * dmap words will be marked as free in a single shot and the leaves
3294 * will be updated. a single leaf may describe the free space of
3295 * multiple dmap words, so we may update only a subset of the actual
3296 * leaves corresponding to the dmap words of the block range.
3297 */
3299 /* determine the bit number within the word and
3300 * the number of bits within the word.
3301 */
3305 /* check if only part of a word is to be allocated.
3306 */
3308 /* allocate (set to 1) the appropriate bits within
3309 * this dmap word.
3310 */
3314 word++;
3316 /* one or more dmap words are fully contained
3317 * within the block range. determine how many
3318 * words and allocate (set to 1) the bits of these
3319 * words.
3320 */
3324 /* determine how many bits */
3327 }
3328 }
3330 /* update the free count for this dmap */
3333 /* reconstruct summary tree */
3338 /* if this allocation group is completely free,
3339 * update the highest active allocation group number
3340 * if this allocation group is the new max.
3341 */
3346 /* update the free count for the allocation group and map */
3352 /* if the root has not changed, done. */
3356 /* root changed. bubble the change up to the dmap control pages.
3357 * if the adjustment of the upper level control pages fails,
3358 * backout the bit allocation (thus making everything consistent).
3359 */
3364 }
3367 /*
3368 * NAME: dbExtendFS()
3369 *
3370 * FUNCTION: extend bmap from blkno for nblocks;
3371 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3372 *
3373 * L2
3374 * |
3375 * L1---------------------------------L1
3376 * | |
3377 * L0---------L0---------L0 L0---------L0---------L0
3378 * | | | | | |
3379 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3380 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3381 *
3382 * <---old---><----------------------------extend----------------------->
3383 */
3385 {
3389 s64 newsize;
3390 s64 p;
3397 s64 ag_rem;
3404 /*
3405 * initialize bmap control page.
3406 *
3407 * all the data in bmap control page should exclude
3408 * the mkfs hidden dmap page.
3409 */
3411 /* update mapsize */
3415 /* compute new AG size */
3422 /* compute new number of AG */
3427 /*
3428 * reconfigure db_agfree[]
3429 * from old AG configuration to new AG configuration;
3430 *
3431 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3432 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3433 * note: new AG size = old AG size * (2**x).
3434 */
3442 /* coalesce contiguous k AGs; */
3444 /* merge AGi to AGn */
3446 }
3447 }
3453 /*
3454 * update highest active ag number
3455 */
3459 /*
3460 * extend bmap
3461 *
3462 * update bit maps and corresponding level control pages;
3463 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3464 */
3465 extend:
3466 /* get L2 page */
3472 }
3475 /* compute start L1 */
3480 /*
3481 * extend each L1 in L2
3482 */
3484 /* get L1 page */
3486 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3492 /* compute start L0 */
3498 /* assign/init L1 page */
3505 /* compute start L0 */
3509 }
3511 /*
3512 * extend each L0 in L1
3513 */
3515 /* get L0 page */
3517 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3524 /* compute start dmap */
3526 L2BPERDMAP;
3532 /* assign/init L0 page */
3539 /* compute start dmap */
3543 }
3545 /*
3546 * extend each dmap in L0
3547 */
3549 /*
3550 * reconstruct the dmap page, and
3551 * initialize corresponding parent L0 leaf
3552 */
3554 /* read in dmap page: */
3561 /* assign/init dmap page */
3568 }
3579 l0leaf++;
3588 /*
3589 * build current L0 page from its leaves, and
3590 * initialize corresponding parent L1 leaf
3591 */
3599 /* more than 1 L0 ? */
3603 /* summarize in global bmap page */
3608 }
3609 }
3612 /*
3613 * build current L1 page from its leaves, and
3614 * initialize corresponding parent L2 leaf
3615 */
3623 /* more than 1 L1 ? */
3627 /* summarize in global bmap page */
3631 }
3632 }
3636 errout:
3644 /*
3645 * finalize bmap control page
3646 */
3647 finalize:
3650 }
3653 /*
3654 * dbFinalizeBmap()
3655 */
3657 {
3663 /*
3664 * finalize bmap control page
3665 */
3666 //finalize:
3667 /*
3668 * compute db_agpref: preferred ag to allocate from
3669 * (the leftmost ag with average free space in it);
3670 */
3671 //agpref:
3672 /* get the number of active ags and inacitve ags */
3677 /* determine how many blocks are in the inactive allocation
3678 * groups. in doing this, we must account for the fact that
3679 * the rightmost group might be a partial group (i.e. file
3680 * system size is not a multiple of the group size).
3681 */
3686 /* determine how many free blocks are in the active
3687 * allocation groups plus the average number of free blocks
3688 * within the active ags.
3689 */
3693 /* if the preferred allocation group has not average free space.
3694 * re-establish the preferred group as the leftmost
3695 * group with average free space.
3696 */
3702 }
3706 }
3707 }
3709 /*
3710 * compute db_aglevel, db_agheight, db_width, db_agstart:
3711 * an ag is covered in aglevel dmapctl summary tree,
3712 * at agheight level height (from leaf) with agwidth number of nodes
3713 * each, which starts at agstart index node of the smmary tree node
3714 * array;
3715 */
3717 l2nl =
3722 i--) {
3725 }
3727 }
3730 /*
3731 * NAME: dbInitDmap()/ujfs_idmap_page()
3732 *
3733 * FUNCTION: initialize working/persistent bitmap of the dmap page
3734 * for the specified number of blocks:
3735 *
3736 * at entry, the bitmaps had been initialized as free (ZEROS);
3737 * The number of blocks will only account for the actually
3738 * existing blocks. Blocks which don't actually exist in
3739 * the aggregate will be marked as allocated (ONES);
3740 *
3741 * PARAMETERS:
3742 * dp - pointer to page of map
3743 * nblocks - number of blocks this page
3744 *
3745 * RETURNS: NONE
3746 */
3748 {
3751 /* starting block number within the dmap */
3762 }
3766 }
3768 /* word number containing start block number */
3771 /*
3772 * free the bits corresponding to the block range (ZEROS):
3773 * note: not all bits of the first and last words may be contained
3774 * within the block range.
3775 */
3777 /* number of bits preceding range to be freed in the word */
3779 /* number of bits to free in the word */
3782 /* is partial word to be freed ? */
3784 /* free (set to 0) from the bitmap word */
3790 /* skip the word freed */
3791 w++;
3793 /* free (set to 0) contiguous bitmap words */
3798 /* skip the words freed */
3801 }
3802 }
3804 /*
3805 * mark bits following the range to be freed (non-existing
3806 * blocks) as allocated (ONES)
3807 */
3812 /* the first word beyond the end of existing blocks */
3815 /* does nblocks fall on a 32-bit boundary ? */
3818 /* mark a partial word allocated */
3820 w++;
3821 }
3823 /* set the rest of the words in the page to allocated (ONES) */
3827 /*
3828 * init tree
3829 */
3830 initTree:
3832 }
3835 /*
3836 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3837 *
3838 * FUNCTION: initialize summary tree of the specified dmap:
3839 *
3840 * at entry, bitmap of the dmap has been initialized;
3841 *
3842 * PARAMETERS:
3843 * dp - dmap to complete
3844 * blkno - starting block number for this dmap
3845 * treemax - will be filled in with max free for this dmap
3846 *
3847 * RETURNS: max free string at the root of the tree
3848 */
3850 {
3855 /* init fixed info of tree */
3863 /* init each leaf from corresponding wmap word:
3864 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3865 * bitmap word are allocated.
3866 */
3871 /* build the dmap's binary buddy summary tree */
3873 }
3876 /*
3877 * NAME: dbInitTree()/ujfs_adjtree()
3878 *
3879 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3880 *
3881 * at entry, the leaves of the tree has been initialized
3882 * from corresponding bitmap word or root of summary tree
3883 * of the child control page;
3884 * configure binary buddy system at the leaf level, then
3885 * bubble up the values of the leaf nodes up the tree.
3886 *
3887 * PARAMETERS:
3888 * cp - Pointer to the root of the tree
3889 * l2leaves- Number of leaf nodes as a power of 2
3890 * l2min - Number of blocks that can be covered by a leaf
3891 * as a power of 2
3892 *
3893 * RETURNS: max free string at the root of the tree
3894 */
3896 {
3903 /* Determine the maximum free string possible for the leaves */
3906 /*
3907 * configure the leaf levevl into binary buddy system
3908 *
3909 * Try to combine buddies starting with a buddy size of 1
3910 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3911 * can be combined if both buddies have a maximum free of l2min;
3912 * the combination will result in the left-most buddy leaf having
3913 * a maximum free of l2min+1.
3914 * After processing all buddies for a given size, process buddies
3915 * at the next higher buddy size (i.e. current size * 2) and
3916 * the next maximum free (current free + 1).
3917 * This continues until the maximum possible buddy combination
3918 * yields maximum free.
3919 */
3922 /* get next buddy size == current buddy pair size */
3925 /* scan each adjacent buddy pair at current buddy size */
3929 /* coalesce if both adjacent buddies are max free */
3933 }
3934 }
3935 }
3937 /*
3938 * bubble summary information of leaves up the tree.
3939 *
3940 * Starting at the leaf node level, the four nodes described by
3941 * the higher level parent node are compared for a maximum free and
3942 * this maximum becomes the value of the parent node.
3943 * when all lower level nodes are processed in this fashion then
3944 * move up to the next level (parent becomes a lower level node) and
3945 * continue the process for that level.
3946 */
3950 /* get index of 1st node of parent level */
3953 /* set the value of the parent node as the maximum
3954 * of the four nodes of the current level.
3955 */
3959 }
3962 }
3965 /*
3966 * dbInitDmapCtl()
3967 *
3968 * function: initialize dmapctl page
3969 */
3980 /*
3981 * initialize the leaves of current level that were not covered
3982 * by the specified input block range (i.e. the leaves have no
3983 * low level dmapctl or dmap).
3984 */
3989 /* build the dmap's binary buddy summary tree */
3991 }
3994 /*
3995 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3996 *
3997 * FUNCTION: Determine log2(allocation group size) from aggregate size
3998 *
3999 * PARAMETERS:
4000 * nblocks - Number of blocks in aggregate
4001 *
4002 * RETURNS: log2(allocation group size) in aggregate blocks
4003 */
4005 {
4006 s64 sz;
4007 s64 m;
4013 /* round up aggregate size to power of 2 */
4018 }
4024 /* agsize = roundupSize/max_number_of_ag */
4026 }
4029 /*
4030 * NAME: dbMapFileSizeToMapSize()
4031 *
4032 * FUNCTION: compute number of blocks the block allocation map file
4033 * can cover from the map file size;
4034 *
4035 * RETURNS: Number of blocks which can be covered by this block map file;
4036 */
4038 /*
4039 * maximum number of map pages at each level including control pages
4040 */
4041 #define MAXL0PAGES (1 + LPERCTL)
4042 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
4043 #define MAXL2PAGES (1 + LPERCTL * MAXL1PAGES)
4045 /*
4046 * convert number of map pages to the zero origin top dmapctl level
4047 */
4048 #define BMAPPGTOLEV(npages) \
4049 (((npages) <= 3 + MAXL0PAGES) ? 0 : \
4050 ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4053 {
4055 s64 nblocks;
4064 /* At each level, accumulate the number of dmap pages covered by
4065 * the number of full child levels below it;
4066 * repeat for the last incomplete child level.
4067 */
4070 /* skip higher level control pages above top level covered by map */
4074 factor =
4080 /* pages in last/incomplete child */
4082 /* skip incomplete child's level control page */
4083 npages--;
4084 }
4086 /* convert the number of dmaps into the number of blocks
4087 * which can be covered by the dmaps;
4088 */
4092 }