| blob | f9009e4f9ffd89c39e39ae4575a012d21919a36d |
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * Copyright (C) International Business Machines Corp., 2000-2004
4 * Portions Copyright (C) Tino Reichardt, 2012
5 */
7 #include <linux/fs.h>
8 #include <linux/slab.h>
18 /*
19 * SERIALIZATION of the Block Allocation Map.
20 *
21 * the working state of the block allocation map is accessed in
22 * two directions:
23 *
24 * 1) allocation and free requests that start at the dmap
25 * level and move up through the dmap control pages (i.e.
26 * the vast majority of requests).
27 *
28 * 2) allocation requests that start at dmap control page
29 * level and work down towards the dmaps.
30 *
31 * the serialization scheme used here is as follows.
32 *
33 * requests which start at the bottom are serialized against each
34 * other through buffers and each requests holds onto its buffers
35 * as it works it way up from a single dmap to the required level
36 * of dmap control page.
37 * requests that start at the top are serialized against each other
38 * and request that start from the bottom by the multiple read/single
39 * write inode lock of the bmap inode. requests starting at the top
40 * take this lock in write mode while request starting at the bottom
41 * take the lock in read mode. a single top-down request may proceed
42 * exclusively while multiple bottoms-up requests may proceed
43 * simultaneously (under the protection of busy buffers).
44 *
45 * in addition to information found in dmaps and dmap control pages,
46 * the working state of the block allocation map also includes read/
47 * write information maintained in the bmap descriptor (i.e. total
48 * free block count, allocation group level free block counts).
49 * a single exclusive lock (BMAP_LOCK) is used to guard this information
50 * in the face of multiple-bottoms up requests.
51 * (lock ordering: IREAD_LOCK, BMAP_LOCK);
52 *
53 * accesses to the persistent state of the block allocation map (limited
54 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
55 */
57 #define BMAP_LOCK_INIT(bmp) mutex_init(&bmp->db_bmaplock)
58 #define BMAP_LOCK(bmp) mutex_lock(&bmp->db_bmaplock)
59 #define BMAP_UNLOCK(bmp) mutex_unlock(&bmp->db_bmaplock)
61 /*
62 * forward references
63 */
109 /*
110 * buddy table
111 *
112 * table used for determining buddy sizes within characters of
113 * dmap bitmap words. the characters themselves serve as indexes
114 * into the table, with the table elements yielding the maximum
115 * binary buddy of free bits within the character.
116 */
134 };
136 /*
137 * NAME: dbMount()
138 *
139 * FUNCTION: initializate the block allocation map.
140 *
141 * memory is allocated for the in-core bmap descriptor and
142 * the in-core descriptor is initialized from disk.
143 *
144 * PARAMETERS:
145 * ipbmap - pointer to in-core inode for the block map.
146 *
147 * RETURN VALUES:
148 * 0 - success
149 * -ENOMEM - insufficient memory
150 * -EIO - i/o error
151 * -EINVAL - wrong bmap data
152 */
154 {
160 /*
161 * allocate/initialize the in-memory bmap descriptor
162 */
163 /* allocate memory for the in-memory bmap descriptor */
168 /* read the on-disk bmap descriptor. */
175 }
177 /* copy the on-disk bmap descriptor to its in-memory version. */
187 }
193 }
202 }
213 }
218 }
225 /* release the buffer. */
228 /* bind the bmap inode and the bmap descriptor to each other. */
234 /*
235 * allocate/initialize the bmap lock
236 */
241 err_release_metapage:
243 err_kfree_bmp:
246 }
249 /*
250 * NAME: dbUnmount()
251 *
252 * FUNCTION: terminate the block allocation map in preparation for
253 * file system unmount.
254 *
255 * the in-core bmap descriptor is written to disk and
256 * the memory for this descriptor is freed.
257 *
258 * PARAMETERS:
259 * ipbmap - pointer to in-core inode for the block map.
260 *
261 * RETURN VALUES:
262 * 0 - success
263 * -EIO - i/o error
264 */
266 {
272 /*
273 * Invalidate the page cache buffers
274 */
277 /* free the memory for the in-memory bmap. */
282 }
284 /*
285 * dbSync()
286 */
288 {
294 /*
295 * write bmap global control page
296 */
297 /* get the buffer for the on-disk bmap descriptor. */
304 }
305 /* copy the in-memory version of the bmap to the on-disk version */
324 /* write the buffer */
327 /*
328 * write out dirty pages of bmap
329 */
335 }
337 /*
338 * NAME: dbFree()
339 *
340 * FUNCTION: free the specified block range from the working block
341 * allocation map.
342 *
343 * the blocks will be free from the working map one dmap
344 * at a time.
345 *
346 * PARAMETERS:
347 * ip - pointer to in-core inode;
348 * blkno - starting block number to be freed.
349 * nblocks - number of blocks to be freed.
350 *
351 * RETURN VALUES:
352 * 0 - success
353 * -EIO - i/o error
354 */
356 {
367 /* block to be freed better be within the mapsize. */
375 }
377 /**
378 * TRIM the blocks, when mounted with discard option
379 */
384 /*
385 * free the blocks a dmap at a time.
386 */
389 /* release previous dmap if any */
392 }
394 /* get the buffer for the current dmap. */
400 }
403 /* determine the number of blocks to be freed from
404 * this dmap.
405 */
408 /* free the blocks. */
414 }
415 }
417 /* write the last buffer. */
424 }
427 /*
428 * NAME: dbUpdatePMap()
429 *
430 * FUNCTION: update the allocation state (free or allocate) of the
431 * specified block range in the persistent block allocation map.
432 *
433 * the blocks will be updated in the persistent map one
434 * dmap at a time.
435 *
436 * PARAMETERS:
437 * ipbmap - pointer to in-core inode for the block map.
438 * free - 'true' if block range is to be freed from the persistent
439 * map; 'false' if it is to be allocated.
440 * blkno - starting block number of the range.
441 * nblocks - number of contiguous blocks in the range.
442 * tblk - transaction block;
443 *
444 * RETURN VALUES:
445 * 0 - success
446 * -EIO - i/o error
447 */
448 int
451 {
456 u32 mask;
463 /* the blocks better be within the mapsize. */
470 }
472 /* compute delta of transaction lsn from log syncpt */
477 /*
478 * update the block state a dmap at a time.
479 */
483 /* get the buffer for the current dmap. */
488 }
495 }
498 /* determine the bit number and word within the dmap of
499 * the starting block. also determine how many blocks
500 * are to be updated within this dmap.
501 */
506 /* update the bits of the dmap words. the first and last
507 * words may only have a subset of their bits updated. if
508 * this is the case, we'll work against that word (i.e.
509 * partial first and/or last) only in a single pass. a
510 * single pass will also be used to update all words that
511 * are to have all their bits updated.
512 */
515 /* determine the bit number within the word and
516 * the number of bits within the word.
517 */
521 /* check if only part of the word is to be updated. */
523 /* update (free or allocate) the bits
524 * in this word.
525 */
526 mask =
531 else
537 /* one or more words are to have all
538 * their bits updated. determine how
539 * many words and how many bits.
540 */
544 /* update (free or allocate) the bits
545 * in these words.
546 */
550 else
555 }
556 }
558 /*
559 * update dmap lsn
560 */
568 /* inherit older/smaller lsn */
573 /* move bp after tblock in logsync list */
575 }
577 /* inherit younger/larger clsn */
586 /* insert bp after tblock in logsync list */
591 }
593 }
595 /* write the last buffer. */
598 }
601 }
604 /*
605 * NAME: dbNextAG()
606 *
607 * FUNCTION: find the preferred allocation group for new allocations.
608 *
609 * Within the allocation groups, we maintain a preferred
610 * allocation group which consists of a group with at least
611 * average free space. It is the preferred group that we target
612 * new inode allocation towards. The tie-in between inode
613 * allocation and block allocation occurs as we allocate the
614 * first (data) block of an inode and specify the inode (block)
615 * as the allocation hint for this block.
616 *
617 * We try to avoid having more than one open file growing in
618 * an allocation group, as this will lead to fragmentation.
619 * This differs from the old OS/2 method of trying to keep
620 * empty ags around for large allocations.
621 *
622 * PARAMETERS:
623 * ipbmap - pointer to in-core inode for the block map.
624 *
625 * RETURN VALUES:
626 * the preferred allocation group number.
627 */
629 {
630 s64 avgfree;
639 /* determine the average number of free blocks within the ags. */
642 /*
643 * if the current preferred ag does not have an active allocator
644 * and has at least average freespace, return it
645 */
651 /* From the last preferred ag, find the next one with at least
652 * average free space.
653 */
659 /* open file is currently growing in this ag */
662 /* Return this one */
666 /* Less than avg. freespace, but best so far */
669 }
670 }
672 /*
673 * If no inactive ag was found with average freespace, use the
674 * next best
675 */
678 /* else leave db_agpref unchanged */
679 unlock:
682 /* return the preferred group.
683 */
685 }
687 /*
688 * NAME: dbAlloc()
689 *
690 * FUNCTION: attempt to allocate a specified number of contiguous free
691 * blocks from the working allocation block map.
692 *
693 * the block allocation policy uses hints and a multi-step
694 * approach.
695 *
696 * for allocation requests smaller than the number of blocks
697 * per dmap, we first try to allocate the new blocks
698 * immediately following the hint. if these blocks are not
699 * available, we try to allocate blocks near the hint. if
700 * no blocks near the hint are available, we next try to
701 * allocate within the same dmap as contains the hint.
702 *
703 * if no blocks are available in the dmap or the allocation
704 * request is larger than the dmap size, we try to allocate
705 * within the same allocation group as contains the hint. if
706 * this does not succeed, we finally try to allocate anywhere
707 * within the aggregate.
708 *
709 * we also try to allocate anywhere within the aggregate
710 * for allocation requests larger than the allocation group
711 * size or requests that specify no hint value.
712 *
713 * PARAMETERS:
714 * ip - pointer to in-core inode;
715 * hint - allocation hint.
716 * nblocks - number of contiguous blocks in the range.
717 * results - on successful return, set to the starting block number
718 * of the newly allocated contiguous range.
719 *
720 * RETURN VALUES:
721 * 0 - success
722 * -ENOSPC - insufficient disk resources
723 * -EIO - i/o error
724 */
726 {
734 s64 mapSize;
737 /* assert that nblocks is valid */
740 /* get the log2 number of blocks to be allocated.
741 * if the number of blocks is not a log2 multiple,
742 * it will be rounded up to the next log2 multiple.
743 */
750 /* the hint should be within the map */
754 }
756 /* if the number of blocks to be allocated is greater than the
757 * allocation group size, try to allocate anywhere.
758 */
765 }
767 /*
768 * If no hint, let dbNextAG recommend an allocation group
769 */
773 /* we would like to allocate close to the hint. adjust the
774 * hint to the block following the hint since the allocators
775 * will start looking for free space starting at this point.
776 */
784 /* check if blkno crosses over into a new allocation group.
785 * if so, check if we should allow allocations within this
786 * allocation group.
787 */
789 /* check if the AG is currently being written to.
790 * if so, call dbNextAG() to find a non-busy
791 * AG with sufficient free space.
792 */
796 /* check if the allocation request size can be satisfied from a
797 * single dmap. if so, try to allocate from the dmap containing
798 * the hint using a tiered strategy.
799 */
803 /* get the buffer for the dmap containing the hint.
804 */
813 /* first, try to satisfy the allocation request with the
814 * blocks beginning at the hint.
815 */
821 }
825 }
830 /*
831 * Someone else is writing in this allocation
832 * group. To avoid fragmenting, try another ag
833 */
837 }
839 /* next, try to satisfy the allocation request with blocks
840 * near the hint.
841 */
850 }
852 /* try to satisfy the allocation request with blocks within
853 * the same dmap as the hint.
854 */
862 }
866 }
868 /* try to satisfy the allocation request with blocks within
869 * the same allocation group as the hint.
870 */
878 pref_ag:
879 /*
880 * Let dbNextAG recommend a preferred allocation group
881 */
885 /* Try to allocate within this allocation group. if that fails, try to
886 * allocate anywhere in the map.
887 */
891 write_unlock:
896 read_unlock:
900 }
902 /*
903 * NAME: dbReAlloc()
904 *
905 * FUNCTION: attempt to extend a current allocation by a specified
906 * number of blocks.
907 *
908 * this routine attempts to satisfy the allocation request
909 * by first trying to extend the existing allocation in
910 * place by allocating the additional blocks as the blocks
911 * immediately following the current allocation. if these
912 * blocks are not available, this routine will attempt to
913 * allocate a new set of contiguous blocks large enough
914 * to cover the existing allocation plus the additional
915 * number of blocks required.
916 *
917 * PARAMETERS:
918 * ip - pointer to in-core inode requiring allocation.
919 * blkno - starting block of the current allocation.
920 * nblocks - number of contiguous blocks within the current
921 * allocation.
922 * addnblocks - number of blocks to add to the allocation.
923 * results - on successful return, set to the starting block number
924 * of the existing allocation if the existing allocation
925 * was extended in place or to a newly allocated contiguous
926 * range if the existing allocation could not be extended
927 * in place.
928 *
929 * RETURN VALUES:
930 * 0 - success
931 * -ENOSPC - insufficient disk resources
932 * -EIO - i/o error
933 */
934 int
937 {
940 /* try to extend the allocation in place.
941 */
948 }
950 /* could not extend the allocation in place, so allocate a
951 * new set of blocks for the entire request (i.e. try to get
952 * a range of contiguous blocks large enough to cover the
953 * existing allocation plus the additional blocks.)
954 */
957 }
960 /*
961 * NAME: dbExtend()
962 *
963 * FUNCTION: attempt to extend a current allocation by a specified
964 * number of blocks.
965 *
966 * this routine attempts to satisfy the allocation request
967 * by first trying to extend the existing allocation in
968 * place by allocating the additional blocks as the blocks
969 * immediately following the current allocation.
970 *
971 * PARAMETERS:
972 * ip - pointer to in-core inode requiring allocation.
973 * blkno - starting block of the current allocation.
974 * nblocks - number of contiguous blocks within the current
975 * allocation.
976 * addnblocks - number of blocks to add to the allocation.
977 *
978 * RETURN VALUES:
979 * 0 - success
980 * -ENOSPC - insufficient disk resources
981 * -EIO - i/o error
982 */
984 {
987 uint rel_block;
994 /*
995 * We don't want a non-aligned extent to cross a page boundary
996 */
1001 /* get the last block of the current allocation */
1004 /* determine the block number of the block following
1005 * the existing allocation.
1006 */
1011 /* better be within the file system */
1017 }
1019 /* we'll attempt to extend the current allocation in place by
1020 * allocating the additional blocks as the blocks immediately
1021 * following the current allocation. we only try to extend the
1022 * current allocation in place if the number of additional blocks
1023 * can fit into a dmap, the last block of the current allocation
1024 * is not the last block of the file system, and the start of the
1025 * inplace extension is not on an allocation group boundary.
1026 */
1031 }
1033 /* get the buffer for the dmap containing the first block
1034 * of the extension.
1035 */
1041 }
1045 /* try to allocate the blocks immediately following the
1046 * current allocation.
1047 */
1052 /* were we successful ? */
1055 else
1056 /* we were not successful */
1060 }
1063 /*
1064 * NAME: dbAllocNext()
1065 *
1066 * FUNCTION: attempt to allocate the blocks of the specified block
1067 * range within a dmap.
1068 *
1069 * PARAMETERS:
1070 * bmp - pointer to bmap descriptor
1071 * dp - pointer to dmap.
1072 * blkno - starting block number of the range.
1073 * nblocks - number of contiguous free blocks of the range.
1074 *
1075 * RETURN VALUES:
1076 * 0 - success
1077 * -ENOSPC - insufficient disk resources
1078 * -EIO - i/o error
1079 *
1080 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1081 */
1084 {
1088 u32 mask;
1093 }
1095 /* pick up a pointer to the leaves of the dmap tree.
1096 */
1099 /* determine the bit number and word within the dmap of the
1100 * starting block.
1101 */
1105 /* check if the specified block range is contained within
1106 * this dmap.
1107 */
1111 /* check if the starting leaf indicates that anything
1112 * is free.
1113 */
1117 /* check the dmaps words corresponding to block range to see
1118 * if the block range is free. not all bits of the first and
1119 * last words may be contained within the block range. if this
1120 * is the case, we'll work against those words (i.e. partial first
1121 * and/or last) on an individual basis (a single pass) and examine
1122 * the actual bits to determine if they are free. a single pass
1123 * will be used for all dmap words fully contained within the
1124 * specified range. within this pass, the leaves of the dmap
1125 * tree will be examined to determine if the blocks are free. a
1126 * single leaf may describe the free space of multiple dmap
1127 * words, so we may visit only a subset of the actual leaves
1128 * corresponding to the dmap words of the block range.
1129 */
1131 /* determine the bit number within the word and
1132 * the number of bits within the word.
1133 */
1137 /* check if only part of the word is to be examined.
1138 */
1140 /* check if the bits are free.
1141 */
1148 /* one or more dmap words are fully contained
1149 * within the block range. determine how many
1150 * words and how many bits.
1151 */
1155 /* now examine the appropriate leaves to determine
1156 * if the blocks are free.
1157 */
1159 /* does the leaf describe any free space ?
1160 */
1164 /* determine the l2 number of bits provided
1165 * by this leaf.
1166 */
1167 l2size =
1170 /* determine how many words were handled.
1171 */
1176 }
1177 }
1178 }
1180 /* allocate the blocks.
1181 */
1183 }
1186 /*
1187 * NAME: dbAllocNear()
1188 *
1189 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1190 * a specified block (hint) within a dmap.
1191 *
1192 * starting with the dmap leaf that covers the hint, we'll
1193 * check the next four contiguous leaves for sufficient free
1194 * space. if sufficient free space is found, we'll allocate
1195 * the desired free space.
1196 *
1197 * PARAMETERS:
1198 * bmp - pointer to bmap descriptor
1199 * dp - pointer to dmap.
1200 * blkno - block number to allocate near.
1201 * nblocks - actual number of contiguous free blocks desired.
1202 * l2nb - log2 number of contiguous free blocks desired.
1203 * results - on successful return, set to the starting block number
1204 * of the newly allocated range.
1205 *
1206 * RETURN VALUES:
1207 * 0 - success
1208 * -ENOSPC - insufficient disk resources
1209 * -EIO - i/o error
1210 *
1211 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1212 */
1213 static int
1216 {
1223 }
1227 /* determine the word within the dmap that holds the hint
1228 * (i.e. blkno). also, determine the last word in the dmap
1229 * that we'll include in our examination.
1230 */
1234 /* examine the leaves for sufficient free space.
1235 */
1237 /* does the leaf describe sufficient free space ?
1238 */
1242 /* determine the block number within the file system
1243 * of the first block described by this dmap word.
1244 */
1247 /* if not all bits of the dmap word are free, get the
1248 * starting bit number within the dmap word of the required
1249 * string of free bits and adjust the block number with the
1250 * value.
1251 */
1253 blkno +=
1256 /* allocate the blocks.
1257 */
1262 }
1265 }
1268 /*
1269 * NAME: dbAllocAG()
1270 *
1271 * FUNCTION: attempt to allocate the specified number of contiguous
1272 * free blocks within the specified allocation group.
1273 *
1274 * unless the allocation group size is equal to the number
1275 * of blocks per dmap, the dmap control pages will be used to
1276 * find the required free space, if available. we start the
1277 * search at the highest dmap control page level which
1278 * distinctly describes the allocation group's free space
1279 * (i.e. the highest level at which the allocation group's
1280 * free space is not mixed in with that of any other group).
1281 * in addition, we start the search within this level at a
1282 * height of the dmapctl dmtree at which the nodes distinctly
1283 * describe the allocation group's free space. at this height,
1284 * the allocation group's free space may be represented by 1
1285 * or two sub-trees, depending on the allocation group size.
1286 * we search the top nodes of these subtrees left to right for
1287 * sufficient free space. if sufficient free space is found,
1288 * the subtree is searched to find the leftmost leaf that
1289 * has free space. once we have made it to the leaf, we
1290 * move the search to the next lower level dmap control page
1291 * corresponding to this leaf. we continue down the dmap control
1292 * pages until we find the dmap that contains or starts the
1293 * sufficient free space and we allocate at this dmap.
1294 *
1295 * if the allocation group size is equal to the dmap size,
1296 * we'll start at the dmap corresponding to the allocation
1297 * group and attempt the allocation at this level.
1298 *
1299 * the dmap control page search is also not performed if the
1300 * allocation group is completely free and we go to the first
1301 * dmap of the allocation group to do the allocation. this is
1302 * done because the allocation group may be part (not the first
1303 * part) of a larger binary buddy system, causing the dmap
1304 * control pages to indicate no free space (NOFREE) within
1305 * the allocation group.
1306 *
1307 * PARAMETERS:
1308 * bmp - pointer to bmap descriptor
1309 * agno - allocation group number.
1310 * nblocks - actual number of contiguous free blocks desired.
1311 * l2nb - log2 number of contiguous free blocks desired.
1312 * results - on successful return, set to the starting block number
1313 * of the newly allocated range.
1314 *
1315 * RETURN VALUES:
1316 * 0 - success
1317 * -ENOSPC - insufficient disk resources
1318 * -EIO - i/o error
1319 *
1320 * note: IWRITE_LOCK(ipmap) held on entry/exit;
1321 */
1322 static int
1324 {
1331 /* allocation request should not be for more than the
1332 * allocation group size.
1333 */
1338 }
1340 /* determine the starting block number of the allocation
1341 * group.
1342 */
1345 /* check if the allocation group size is the minimum allocation
1346 * group size or if the allocation group is completely free. if
1347 * the allocation group size is the minimum size of BPERDMAP (i.e.
1348 * 1 dmap), there is no need to search the dmap control page (below)
1349 * that fully describes the allocation group since the allocation
1350 * group is already fully described by a dmap. in this case, we
1351 * just call dbAllocCtl() to search the dmap tree and allocate the
1352 * required space if available.
1353 *
1354 * if the allocation group is completely free, dbAllocCtl() is
1355 * also called to allocate the required space. this is done for
1356 * two reasons. first, it makes no sense searching the dmap control
1357 * pages for free space when we know that free space exists. second,
1358 * the dmap control pages may indicate that the allocation group
1359 * has no free space if the allocation group is part (not the first
1360 * part) of a larger binary buddy system.
1361 */
1372 }
1374 }
1376 /* the buffer for the dmap control page that fully describes the
1377 * allocation group.
1378 */
1390 }
1392 /* search the subtree(s) of the dmap control page that describes
1393 * the allocation group, looking for sufficient free space. to begin,
1394 * determine how many allocation groups are represented in a dmap
1395 * control page at the control page level (i.e. L0, L1, L2) that
1396 * fully describes an allocation group. next, determine the starting
1397 * tree index of this allocation group within the control page.
1398 */
1399 agperlev =
1403 /* dmap control page trees fan-out by 4 and a single allocation
1404 * group may be described by 1 or 2 subtrees within the ag level
1405 * dmap control page, depending upon the ag size. examine the ag's
1406 * subtrees for sufficient free space, starting with the leftmost
1407 * subtree.
1408 */
1410 /* is there sufficient free space ?
1411 */
1415 /* sufficient free space found in a subtree. now search down
1416 * the subtree to find the leftmost leaf that describes this
1417 * free space.
1418 */
1424 }
1425 }
1431 }
1432 }
1434 /* determine the block number within the file system
1435 * that corresponds to this leaf.
1436 */
1444 blkno +=
1447 /* release the buffer in preparation for going down
1448 * the next level of dmap control pages.
1449 */
1452 /* check if we need to continue to search down the lower
1453 * level dmap control pages. we need to if the number of
1454 * blocks required is less than maximum number of blocks
1455 * described at the next lower level.
1456 */
1459 /* search the lower level dmap control pages to get
1460 * the starting block number of the dmap that
1461 * contains or starts off the free space.
1462 */
1470 }
1472 }
1473 }
1475 /* allocate the blocks.
1476 */
1482 }
1484 }
1486 /* no space in the allocation group. release the buffer and
1487 * return -ENOSPC.
1488 */
1492 }
1495 /*
1496 * NAME: dbAllocAny()
1497 *
1498 * FUNCTION: attempt to allocate the specified number of contiguous
1499 * free blocks anywhere in the file system.
1500 *
1501 * dbAllocAny() attempts to find the sufficient free space by
1502 * searching down the dmap control pages, starting with the
1503 * highest level (i.e. L0, L1, L2) control page. if free space
1504 * large enough to satisfy the desired free space is found, the
1505 * desired free space is allocated.
1506 *
1507 * PARAMETERS:
1508 * bmp - pointer to bmap descriptor
1509 * nblocks - actual number of contiguous free blocks desired.
1510 * l2nb - log2 number of contiguous free blocks desired.
1511 * results - on successful return, set to the starting block number
1512 * of the newly allocated range.
1513 *
1514 * RETURN VALUES:
1515 * 0 - success
1516 * -ENOSPC - insufficient disk resources
1517 * -EIO - i/o error
1518 *
1519 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1520 */
1522 {
1526 /* starting with the top level dmap control page, search
1527 * down the dmap control levels for sufficient free space.
1528 * if free space is found, dbFindCtl() returns the starting
1529 * block number of the dmap that contains or starts off the
1530 * range of free space.
1531 */
1535 /* allocate the blocks.
1536 */
1541 }
1543 }
1546 /*
1547 * NAME: dbDiscardAG()
1548 *
1549 * FUNCTION: attempt to discard (TRIM) all free blocks of specific AG
1550 *
1551 * algorithm:
1552 * 1) allocate blocks, as large as possible and save them
1553 * while holding IWRITE_LOCK on ipbmap
1554 * 2) trim all these saved block/length values
1555 * 3) mark the blocks free again
1556 *
1557 * benefit:
1558 * - we work only on one ag at some time, minimizing how long we
1559 * need to lock ipbmap
1560 * - reading / writing the fs is possible most time, even on
1561 * trimming
1562 *
1563 * downside:
1564 * - we write two times to the dmapctl and dmap pages
1565 * - but for me, this seems the best way, better ideas?
1566 * /TR 2012
1567 *
1568 * PARAMETERS:
1569 * ip - pointer to in-core inode
1570 * agno - ag to trim
1571 * minlen - minimum value of contiguous blocks
1572 *
1573 * RETURN VALUES:
1574 * s64 - actual number of blocks trimmed
1575 */
1577 {
1586 u64 blkno;
1587 u64 nblocks;
1590 /* max blkno / nblocks pairs to trim */
1592 u64 max_ranges;
1594 /* prevent others from writing new stuff here, while trimming */
1606 }
1612 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */
1619 /* the whole ag is free, trim now */
1623 /* give a hint for the next while */
1627 /* search for next smaller log2 block */
1633 /* Trim any already allocated blocks */
1636 }
1638 /* check, if our trim array is full */
1641 }
1646 /* when mounted with online discard, dbFree() will
1647 * call jfs_issue_discard() itself */
1652 }
1656 }
1658 /*
1659 * NAME: dbFindCtl()
1660 *
1661 * FUNCTION: starting at a specified dmap control page level and block
1662 * number, search down the dmap control levels for a range of
1663 * contiguous free blocks large enough to satisfy an allocation
1664 * request for the specified number of free blocks.
1665 *
1666 * if sufficient contiguous free blocks are found, this routine
1667 * returns the starting block number within a dmap page that
1668 * contains or starts a range of contiqious free blocks that
1669 * is sufficient in size.
1670 *
1671 * PARAMETERS:
1672 * bmp - pointer to bmap descriptor
1673 * level - starting dmap control page level.
1674 * l2nb - log2 number of contiguous free blocks desired.
1675 * *blkno - on entry, starting block number for conducting the search.
1676 * on successful return, the first block within a dmap page
1677 * that contains or starts a range of contiguous free blocks.
1678 *
1679 * RETURN VALUES:
1680 * 0 - success
1681 * -ENOSPC - insufficient disk resources
1682 * -EIO - i/o error
1683 *
1684 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1685 */
1687 {
1694 /* starting at the specified dmap control page level and block
1695 * number, search down the dmap control levels for the starting
1696 * block number of a dmap page that contains or starts off
1697 * sufficient free blocks.
1698 */
1700 /* get the buffer of the dmap control page for the block
1701 * number and level (i.e. L0, L1, L2).
1702 */
1715 }
1717 /* search the tree within the dmap control page for
1718 * sufficient free space. if sufficient free space is found,
1719 * dbFindLeaf() returns the index of the leaf at which
1720 * free space was found.
1721 */
1724 /* release the buffer.
1725 */
1728 /* space found ?
1729 */
1735 }
1737 }
1739 /* adjust the block number to reflect the location within
1740 * the dmap control page (i.e. the leaf) at which free
1741 * space was found.
1742 */
1745 /* we stop the search at this dmap control page level if
1746 * the number of blocks required is greater than or equal
1747 * to the maximum number of blocks described at the next
1748 * (lower) level.
1749 */
1752 }
1756 }
1759 /*
1760 * NAME: dbAllocCtl()
1761 *
1762 * FUNCTION: attempt to allocate a specified number of contiguous
1763 * blocks starting within a specific dmap.
1764 *
1765 * this routine is called by higher level routines that search
1766 * the dmap control pages above the actual dmaps for contiguous
1767 * free space. the result of successful searches by these
1768 * routines are the starting block numbers within dmaps, with
1769 * the dmaps themselves containing the desired contiguous free
1770 * space or starting a contiguous free space of desired size
1771 * that is made up of the blocks of one or more dmaps. these
1772 * calls should not fail due to insufficent resources.
1773 *
1774 * this routine is called in some cases where it is not known
1775 * whether it will fail due to insufficient resources. more
1776 * specifically, this occurs when allocating from an allocation
1777 * group whose size is equal to the number of blocks per dmap.
1778 * in this case, the dmap control pages are not examined prior
1779 * to calling this routine (to save pathlength) and the call
1780 * might fail.
1781 *
1782 * for a request size that fits within a dmap, this routine relies
1783 * upon the dmap's dmtree to find the requested contiguous free
1784 * space. for request sizes that are larger than a dmap, the
1785 * requested free space will start at the first block of the
1786 * first dmap (i.e. blkno).
1787 *
1788 * PARAMETERS:
1789 * bmp - pointer to bmap descriptor
1790 * nblocks - actual number of contiguous free blocks to allocate.
1791 * l2nb - log2 number of contiguous free blocks to allocate.
1792 * blkno - starting block number of the dmap to start the allocation
1793 * from.
1794 * results - on successful return, set to the starting block number
1795 * of the newly allocated range.
1796 *
1797 * RETURN VALUES:
1798 * 0 - success
1799 * -ENOSPC - insufficient disk resources
1800 * -EIO - i/o error
1801 *
1802 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1803 */
1804 static int
1806 {
1812 /* check if the allocation request is confined to a single dmap.
1813 */
1815 /* get the buffer for the dmap.
1816 */
1826 /* try to allocate the blocks.
1827 */
1835 }
1837 /* allocation request involving multiple dmaps. it must start on
1838 * a dmap boundary.
1839 */
1842 /* allocate the blocks dmap by dmap.
1843 */
1845 /* get the buffer for the dmap.
1846 */
1852 }
1855 /* the dmap better be all free.
1856 */
1863 }
1865 /* determine how many blocks to allocate from this dmap.
1866 */
1869 /* allocate the blocks from the dmap.
1870 */
1874 }
1876 /* write the buffer.
1877 */
1879 }
1881 /* set the results (starting block number) and return.
1882 */
1886 /* something failed in handling an allocation request involving
1887 * multiple dmaps. we'll try to clean up by backing out any
1888 * allocation that has already happened for this request. if
1889 * we fail in backing out the allocation, we'll mark the file
1890 * system to indicate that blocks have been leaked.
1891 */
1892 backout:
1894 /* try to backout the allocations dmap by dmap.
1895 */
1898 /* get the buffer for this dmap.
1899 */
1903 /* could not back out. mark the file system
1904 * to indicate that we have leaked blocks.
1905 */
1909 }
1912 /* free the blocks is this dmap.
1913 */
1915 /* could not back out. mark the file system
1916 * to indicate that we have leaked blocks.
1917 */
1921 }
1923 /* write the buffer.
1924 */
1926 }
1929 }
1932 /*
1933 * NAME: dbAllocDmapLev()
1934 *
1935 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1936 * from a specified dmap.
1937 *
1938 * this routine checks if the contiguous blocks are available.
1939 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1940 * returned.
1941 *
1942 * PARAMETERS:
1943 * mp - pointer to bmap descriptor
1944 * dp - pointer to dmap to attempt to allocate blocks from.
1945 * l2nb - log2 number of contiguous block desired.
1946 * nblocks - actual number of contiguous block desired.
1947 * results - on successful return, set to the starting block number
1948 * of the newly allocated range.
1949 *
1950 * RETURN VALUES:
1951 * 0 - success
1952 * -ENOSPC - insufficient disk resources
1953 * -EIO - i/o error
1954 *
1955 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1956 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1957 */
1958 static int
1961 {
1962 s64 blkno;
1965 /* can't be more than a dmaps worth of blocks */
1968 /* search the tree within the dmap page for sufficient
1969 * free space. if sufficient free space is found, dbFindLeaf()
1970 * returns the index of the leaf at which free space was found.
1971 */
1978 /* determine the block number within the file system corresponding
1979 * to the leaf at which free space was found.
1980 */
1983 /* if not all bits of the dmap word are free, get the starting
1984 * bit number within the dmap word of the required string of free
1985 * bits and adjust the block number with this value.
1986 */
1990 /* allocate the blocks */
1995 }
1998 /*
1999 * NAME: dbAllocDmap()
2000 *
2001 * FUNCTION: adjust the disk allocation map to reflect the allocation
2002 * of a specified block range within a dmap.
2003 *
2004 * this routine allocates the specified blocks from the dmap
2005 * through a call to dbAllocBits(). if the allocation of the
2006 * block range causes the maximum string of free blocks within
2007 * the dmap to change (i.e. the value of the root of the dmap's
2008 * dmtree), this routine will cause this change to be reflected
2009 * up through the appropriate levels of the dmap control pages
2010 * by a call to dbAdjCtl() for the L0 dmap control page that
2011 * covers this dmap.
2012 *
2013 * PARAMETERS:
2014 * bmp - pointer to bmap descriptor
2015 * dp - pointer to dmap to allocate the block range from.
2016 * blkno - starting block number of the block to be allocated.
2017 * nblocks - number of blocks to be allocated.
2018 *
2019 * RETURN VALUES:
2020 * 0 - success
2021 * -EIO - i/o error
2022 *
2023 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2024 */
2027 {
2028 s8 oldroot;
2031 /* save the current value of the root (i.e. maximum free string)
2032 * of the dmap tree.
2033 */
2036 /* allocate the specified (blocks) bits */
2039 /* if the root has not changed, done. */
2043 /* root changed. bubble the change up to the dmap control pages.
2044 * if the adjustment of the upper level control pages fails,
2045 * backout the bit allocation (thus making everything consistent).
2046 */
2051 }
2054 /*
2055 * NAME: dbFreeDmap()
2056 *
2057 * FUNCTION: adjust the disk allocation map to reflect the allocation
2058 * of a specified block range within a dmap.
2059 *
2060 * this routine frees the specified blocks from the dmap through
2061 * a call to dbFreeBits(). if the deallocation of the block range
2062 * causes the maximum string of free blocks within the dmap to
2063 * change (i.e. the value of the root of the dmap's dmtree), this
2064 * routine will cause this change to be reflected up through the
2065 * appropriate levels of the dmap control pages by a call to
2066 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
2067 *
2068 * PARAMETERS:
2069 * bmp - pointer to bmap descriptor
2070 * dp - pointer to dmap to free the block range from.
2071 * blkno - starting block number of the block to be freed.
2072 * nblocks - number of blocks to be freed.
2073 *
2074 * RETURN VALUES:
2075 * 0 - success
2076 * -EIO - i/o error
2077 *
2078 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2079 */
2082 {
2083 s8 oldroot;
2086 /* save the current value of the root (i.e. maximum free string)
2087 * of the dmap tree.
2088 */
2091 /* free the specified (blocks) bits */
2094 /* if error or the root has not changed, done. */
2098 /* root changed. bubble the change up to the dmap control pages.
2099 * if the adjustment of the upper level control pages fails,
2100 * backout the deallocation.
2101 */
2105 /* as part of backing out the deallocation, we will have
2106 * to back split the dmap tree if the deallocation caused
2107 * the freed blocks to become part of a larger binary buddy
2108 * system.
2109 */
2114 }
2117 }
2120 /*
2121 * NAME: dbAllocBits()
2122 *
2123 * FUNCTION: allocate a specified block range from a dmap.
2124 *
2125 * this routine updates the dmap to reflect the working
2126 * state allocation of the specified block range. it directly
2127 * updates the bits of the working map and causes the adjustment
2128 * of the binary buddy system described by the dmap's dmtree
2129 * leaves to reflect the bits allocated. it also causes the
2130 * dmap's dmtree, as a whole, to reflect the allocated range.
2131 *
2132 * PARAMETERS:
2133 * bmp - pointer to bmap descriptor
2134 * dp - pointer to dmap to allocate bits from.
2135 * blkno - starting block number of the bits to be allocated.
2136 * nblocks - number of bits to be allocated.
2137 *
2138 * RETURN VALUES: none
2139 *
2140 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2141 */
2144 {
2150 /* pick up a pointer to the leaves of the dmap tree */
2153 /* determine the bit number and word within the dmap of the
2154 * starting block.
2155 */
2159 /* block range better be within the dmap */
2162 /* allocate the bits of the dmap's words corresponding to the block
2163 * range. not all bits of the first and last words may be contained
2164 * within the block range. if this is the case, we'll work against
2165 * those words (i.e. partial first and/or last) on an individual basis
2166 * (a single pass), allocating the bits of interest by hand and
2167 * updating the leaf corresponding to the dmap word. a single pass
2168 * will be used for all dmap words fully contained within the
2169 * specified range. within this pass, the bits of all fully contained
2170 * dmap words will be marked as free in a single shot and the leaves
2171 * will be updated. a single leaf may describe the free space of
2172 * multiple dmap words, so we may update only a subset of the actual
2173 * leaves corresponding to the dmap words of the block range.
2174 */
2176 /* determine the bit number within the word and
2177 * the number of bits within the word.
2178 */
2182 /* check if only part of a word is to be allocated.
2183 */
2185 /* allocate (set to 1) the appropriate bits within
2186 * this dmap word.
2187 */
2191 /* update the leaf for this dmap word. in addition
2192 * to setting the leaf value to the binary buddy max
2193 * of the updated dmap word, dbSplit() will split
2194 * the binary system of the leaves if need be.
2195 */
2201 /* one or more dmap words are fully contained
2202 * within the block range. determine how many
2203 * words and allocate (set to 1) the bits of these
2204 * words.
2205 */
2209 /* determine how many bits.
2210 */
2213 /* now update the appropriate leaves to reflect
2214 * the allocated words.
2215 */
2221 }
2223 /* determine what the leaf value should be
2224 * updated to as the minimum of the l2 number
2225 * of bits being allocated and the l2 number
2226 * of bits currently described by this leaf.
2227 */
2231 /* update the leaf to reflect the allocation.
2232 * in addition to setting the leaf value to
2233 * NOFREE, dbSplit() will split the binary
2234 * system of the leaves to reflect the current
2235 * allocation (size).
2236 */
2239 /* get the number of dmap words handled */
2242 }
2243 }
2244 }
2246 /* update the free count for this dmap */
2251 /* if this allocation group is completely free,
2252 * update the maximum allocation group number if this allocation
2253 * group is the new max.
2254 */
2259 /* update the free count for the allocation group and map */
2264 }
2267 /*
2268 * NAME: dbFreeBits()
2269 *
2270 * FUNCTION: free a specified block range from a dmap.
2271 *
2272 * this routine updates the dmap to reflect the working
2273 * state allocation of the specified block range. it directly
2274 * updates the bits of the working map and causes the adjustment
2275 * of the binary buddy system described by the dmap's dmtree
2276 * leaves to reflect the bits freed. it also causes the dmap's
2277 * dmtree, as a whole, to reflect the deallocated range.
2278 *
2279 * PARAMETERS:
2280 * bmp - pointer to bmap descriptor
2281 * dp - pointer to dmap to free bits from.
2282 * blkno - starting block number of the bits to be freed.
2283 * nblocks - number of bits to be freed.
2284 *
2285 * RETURN VALUES: 0 for success
2286 *
2287 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2288 */
2291 {
2297 /* determine the bit number and word within the dmap of the
2298 * starting block.
2299 */
2303 /* block range better be within the dmap.
2304 */
2307 /* free the bits of the dmaps words corresponding to the block range.
2308 * not all bits of the first and last words may be contained within
2309 * the block range. if this is the case, we'll work against those
2310 * words (i.e. partial first and/or last) on an individual basis
2311 * (a single pass), freeing the bits of interest by hand and updating
2312 * the leaf corresponding to the dmap word. a single pass will be used
2313 * for all dmap words fully contained within the specified range.
2314 * within this pass, the bits of all fully contained dmap words will
2315 * be marked as free in a single shot and the leaves will be updated. a
2316 * single leaf may describe the free space of multiple dmap words,
2317 * so we may update only a subset of the actual leaves corresponding
2318 * to the dmap words of the block range.
2319 *
2320 * dbJoin() is used to update leaf values and will join the binary
2321 * buddy system of the leaves if the new leaf values indicate this
2322 * should be done.
2323 */
2325 /* determine the bit number within the word and
2326 * the number of bits within the word.
2327 */
2331 /* check if only part of a word is to be freed.
2332 */
2334 /* free (zero) the appropriate bits within this
2335 * dmap word.
2336 */
2341 /* update the leaf for this dmap word.
2342 */
2350 /* one or more dmap words are fully contained
2351 * within the block range. determine how many
2352 * words and free (zero) the bits of these words.
2353 */
2357 /* determine how many bits.
2358 */
2361 /* now update the appropriate leaves to reflect
2362 * the freed words.
2363 */
2365 /* determine what the leaf value should be
2366 * updated to as the minimum of the l2 number
2367 * of bits being freed and the l2 (max) number
2368 * of bits that can be described by this leaf.
2369 */
2370 size =
2375 /* update the leaf.
2376 */
2381 /* get the number of dmap words handled.
2382 */
2385 }
2386 }
2387 }
2389 /* update the free count for this dmap.
2390 */
2395 /* update the free count for the allocation group and
2396 * map.
2397 */
2402 /* check if this allocation group is not completely free and
2403 * if it is currently the maximum (rightmost) allocation group.
2404 * if so, establish the new maximum allocation group number by
2405 * searching left for the first allocation group with allocation.
2406 */
2415 }
2417 /* re-establish the allocation group preference if the
2418 * current preference is right of the maximum allocation
2419 * group.
2420 */
2423 }
2428 }
2431 /*
2432 * NAME: dbAdjCtl()
2433 *
2434 * FUNCTION: adjust a dmap control page at a specified level to reflect
2435 * the change in a lower level dmap or dmap control page's
2436 * maximum string of free blocks (i.e. a change in the root
2437 * of the lower level object's dmtree) due to the allocation
2438 * or deallocation of a range of blocks with a single dmap.
2439 *
2440 * on entry, this routine is provided with the new value of
2441 * the lower level dmap or dmap control page root and the
2442 * starting block number of the block range whose allocation
2443 * or deallocation resulted in the root change. this range
2444 * is respresented by a single leaf of the current dmapctl
2445 * and the leaf will be updated with this value, possibly
2446 * causing a binary buddy system within the leaves to be
2447 * split or joined. the update may also cause the dmapctl's
2448 * dmtree to be updated.
2449 *
2450 * if the adjustment of the dmap control page, itself, causes its
2451 * root to change, this change will be bubbled up to the next dmap
2452 * control level by a recursive call to this routine, specifying
2453 * the new root value and the next dmap control page level to
2454 * be adjusted.
2455 * PARAMETERS:
2456 * bmp - pointer to bmap descriptor
2457 * blkno - the first block of a block range within a dmap. it is
2458 * the allocation or deallocation of this block range that
2459 * requires the dmap control page to be adjusted.
2460 * newval - the new value of the lower level dmap or dmap control
2461 * page root.
2462 * alloc - 'true' if adjustment is due to an allocation.
2463 * level - current level of dmap control page (i.e. L0, L1, L2) to
2464 * be adjusted.
2465 *
2466 * RETURN VALUES:
2467 * 0 - success
2468 * -EIO - i/o error
2469 *
2470 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2471 */
2472 static int
2474 {
2476 s8 oldroot;
2478 s64 lblkno;
2482 /* get the buffer for the dmap control page for the specified
2483 * block number and control page level.
2484 */
2495 }
2497 /* determine the leaf number corresponding to the block and
2498 * the index within the dmap control tree.
2499 */
2503 /* save the current leaf value and the current root level (i.e.
2504 * maximum l2 free string described by this dmapctl).
2505 */
2509 /* check if this is a control page update for an allocation.
2510 * if so, update the leaf to reflect the new leaf value using
2511 * dbSplit(); otherwise (deallocation), use dbJoin() to update
2512 * the leaf with the new value. in addition to updating the
2513 * leaf, dbSplit() will also split the binary buddy system of
2514 * the leaves, if required, and bubble new values within the
2515 * dmapctl tree, if required. similarly, dbJoin() will join
2516 * the binary buddy system of leaves and bubble new values up
2517 * the dmapctl tree as required by the new leaf value.
2518 */
2520 /* check if we are in the middle of a binary buddy
2521 * system. this happens when we are performing the
2522 * first allocation out of an allocation group that
2523 * is part (not the first part) of a larger binary
2524 * buddy system. if we are in the middle, back split
2525 * the system prior to calling dbSplit() which assumes
2526 * that it is at the front of a binary buddy system.
2527 */
2533 }
2535 }
2542 }
2543 }
2545 /* check if the root of the current dmap control page changed due
2546 * to the update and if the current dmap control page is not at
2547 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2548 * root changed and this is not the top level), call this routine
2549 * again (recursion) for the next higher level of the mapping to
2550 * reflect the change in root for the current dmap control page.
2551 */
2553 /* are we below the top level of the map. if so,
2554 * bubble the root up to the next higher level.
2555 */
2557 /* bubble up the new root of this dmap control page to
2558 * the next level.
2559 */
2563 /* something went wrong in bubbling up the new
2564 * root value, so backout the changes to the
2565 * current dmap control page.
2566 */
2571 /* the dbJoin() above might have
2572 * caused a larger binary buddy system
2573 * to form and we may now be in the
2574 * middle of it. if this is the case,
2575 * back split the buddies.
2576 */
2582 }
2584 /* release the buffer and return the error.
2585 */
2588 }
2590 /* we're at the top level of the map. update
2591 * the bmap control page to reflect the size
2592 * of the maximum free buddy system.
2593 */
2598 }
2600 }
2601 }
2603 /* write the buffer.
2604 */
2608 }
2611 /*
2612 * NAME: dbSplit()
2613 *
2614 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2615 * the leaf from the binary buddy system of the dmtree's
2616 * leaves, as required.
2617 *
2618 * PARAMETERS:
2619 * tp - pointer to the tree containing the leaf.
2620 * leafno - the number of the leaf to be updated.
2621 * splitsz - the size the binary buddy system starting at the leaf
2622 * must be split to, specified as the log2 number of blocks.
2623 * newval - the new value for the leaf.
2624 *
2625 * RETURN VALUES: none
2626 *
2627 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2628 */
2630 {
2635 /* check if the leaf needs to be split.
2636 */
2638 /* the split occurs by cutting the buddy system in half
2639 * at the specified leaf until we reach the specified
2640 * size. pick up the starting split size (current size
2641 * - 1 in l2) and the corresponding buddy size.
2642 */
2646 /* split until we reach the specified size.
2647 */
2649 /* update the buddy's leaf with its new value.
2650 */
2653 /* on to the next size and buddy.
2654 */
2657 }
2658 }
2660 /* adjust the dmap tree to reflect the specified leaf's new
2661 * value.
2662 */
2664 }
2667 /*
2668 * NAME: dbBackSplit()
2669 *
2670 * FUNCTION: back split the binary buddy system of dmtree leaves
2671 * that hold a specified leaf until the specified leaf
2672 * starts its own binary buddy system.
2673 *
2674 * the allocators typically perform allocations at the start
2675 * of binary buddy systems and dbSplit() is used to accomplish
2676 * any required splits. in some cases, however, allocation
2677 * may occur in the middle of a binary system and requires a
2678 * back split, with the split proceeding out from the middle of
2679 * the system (less efficient) rather than the start of the
2680 * system (more efficient). the cases in which a back split
2681 * is required are rare and are limited to the first allocation
2682 * within an allocation group which is a part (not first part)
2683 * of a larger binary buddy system and a few exception cases
2684 * in which a previous join operation must be backed out.
2685 *
2686 * PARAMETERS:
2687 * tp - pointer to the tree containing the leaf.
2688 * leafno - the number of the leaf to be updated.
2689 *
2690 * RETURN VALUES: none
2691 *
2692 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2693 */
2695 {
2700 /* leaf should be part (not first part) of a binary
2701 * buddy system.
2702 */
2705 /* the back split is accomplished by iteratively finding the leaf
2706 * that starts the buddy system that contains the specified leaf and
2707 * splitting that system in two. this iteration continues until
2708 * the specified leaf becomes the start of a buddy system.
2709 *
2710 * determine maximum possible l2 size for the specified leaf.
2711 */
2712 size =
2716 /* determine the number of leaves covered by this size. this
2717 * is the buddy size that we will start with as we search for
2718 * the buddy system that contains the specified leaf.
2719 */
2722 /* back split.
2723 */
2725 /* find the leftmost buddy leaf.
2726 */
2732 }
2734 /* determine the buddy.
2735 */
2738 /* check if this buddy is the start of the system.
2739 */
2741 /* split the leaf at the start of the
2742 * system in two.
2743 */
2747 }
2748 }
2749 }
2754 }
2756 }
2759 /*
2760 * NAME: dbJoin()
2761 *
2762 * FUNCTION: update the leaf of a dmtree with a new value, joining
2763 * the leaf with other leaves of the dmtree into a multi-leaf
2764 * binary buddy system, as required.
2765 *
2766 * PARAMETERS:
2767 * tp - pointer to the tree containing the leaf.
2768 * leafno - the number of the leaf to be updated.
2769 * newval - the new value for the leaf.
2770 *
2771 * RETURN VALUES: none
2772 */
2774 {
2778 /* can the new leaf value require a join with other leaves ?
2779 */
2781 /* pickup a pointer to the leaves of the tree.
2782 */
2785 /* try to join the specified leaf into a large binary
2786 * buddy system. the join proceeds by attempting to join
2787 * the specified leafno with its buddy (leaf) at new value.
2788 * if the join occurs, we attempt to join the left leaf
2789 * of the joined buddies with its buddy at new value + 1.
2790 * we continue to join until we find a buddy that cannot be
2791 * joined (does not have a value equal to the size of the
2792 * last join) or until all leaves have been joined into a
2793 * single system.
2794 *
2795 * get the buddy size (number of words covered) of
2796 * the new value.
2797 */
2800 /* try to join.
2801 */
2803 /* get the buddy leaf.
2804 */
2807 /* if the leaf's new value is greater than its
2808 * buddy's value, we join no more.
2809 */
2813 /* It shouldn't be less */
2817 /* check which (leafno or buddy) is the left buddy.
2818 * the left buddy gets to claim the blocks resulting
2819 * from the join while the right gets to claim none.
2820 * the left buddy is also eligible to participate in
2821 * a join at the next higher level while the right
2822 * is not.
2823 *
2824 */
2826 /* leafno is the left buddy.
2827 */
2830 /* buddy is the left buddy and becomes
2831 * leafno.
2832 */
2835 }
2837 /* on to try the next join.
2838 */
2841 }
2842 }
2844 /* update the leaf value.
2845 */
2849 }
2852 /*
2853 * NAME: dbAdjTree()
2854 *
2855 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2856 * the dmtree, as required, to reflect the new leaf value.
2857 * the combination of any buddies must already be done before
2858 * this is called.
2859 *
2860 * PARAMETERS:
2861 * tp - pointer to the tree to be adjusted.
2862 * leafno - the number of the leaf to be updated.
2863 * newval - the new value for the leaf.
2864 *
2865 * RETURN VALUES: none
2866 */
2868 {
2874 /* pick up the index of the leaf for this leafno.
2875 */
2881 /* is the current value the same as the old value ? if so,
2882 * there is nothing to do.
2883 */
2887 /* set the new value.
2888 */
2891 /* bubble the new value up the tree as required.
2892 */
2897 /* get the index of the first leaf of the 4 leaf
2898 * group containing the specified leaf (leafno).
2899 */
2902 /* get the index of the parent of this 4 leaf group.
2903 */
2906 /* determine the maximum of the 4 leaves.
2907 */
2910 /* if the maximum of the 4 is the same as the
2911 * parent's value, we're done.
2912 */
2916 /* parent gets new value.
2917 */
2920 /* parent becomes leaf for next go-round.
2921 */
2923 }
2924 }
2927 /*
2928 * NAME: dbFindLeaf()
2929 *
2930 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2931 * the index of a leaf describing the free blocks if
2932 * sufficient free blocks are found.
2933 *
2934 * the search starts at the top of the dmtree_t tree and
2935 * proceeds down the tree to the leftmost leaf with sufficient
2936 * free space.
2937 *
2938 * PARAMETERS:
2939 * tp - pointer to the tree to be searched.
2940 * l2nb - log2 number of free blocks to search for.
2941 * leafidx - return pointer to be set to the index of the leaf
2942 * describing at least l2nb free blocks if sufficient
2943 * free blocks are found.
2944 * is_ctl - determines if the tree is of type ctl
2945 *
2946 * RETURN VALUES:
2947 * 0 - success
2948 * -ENOSPC - insufficient free blocks.
2949 */
2951 {
2958 /* first check the root of the tree to see if there is
2959 * sufficient free space.
2960 */
2964 /* sufficient free space available. now search down the tree
2965 * starting at the next level for the leftmost leaf that
2966 * describes sufficient free space.
2967 */
2970 /* search the four nodes at this level, starting from
2971 * the left.
2972 */
2974 /* sufficient free space found. move to the next
2975 * level (or quit if this is the last level).
2976 */
2981 }
2983 /* better have found something since the higher
2984 * levels of the tree said it was here.
2985 */
2987 }
2991 /* set the return to the leftmost leaf describing sufficient
2992 * free space.
2993 */
2997 }
3000 /*
3001 * NAME: dbFindBits()
3002 *
3003 * FUNCTION: find a specified number of binary buddy free bits within a
3004 * dmap bitmap word value.
3005 *
3006 * this routine searches the bitmap value for (1 << l2nb) free
3007 * bits at (1 << l2nb) alignments within the value.
3008 *
3009 * PARAMETERS:
3010 * word - dmap bitmap word value.
3011 * l2nb - number of free bits specified as a log2 number.
3012 *
3013 * RETURN VALUES:
3014 * starting bit number of free bits.
3015 */
3017 {
3019 u32 mask;
3021 /* get the number of bits.
3022 */
3026 /* complement the word so we can use a mask (i.e. 0s represent
3027 * free bits) and compute the mask.
3028 */
3032 /* scan the word for nb free bits at nb alignments.
3033 */
3037 }
3041 /* return the bit number.
3042 */
3044 }
3047 /*
3048 * NAME: dbMaxBud(u8 *cp)
3049 *
3050 * FUNCTION: determine the largest binary buddy string of free
3051 * bits within 32-bits of the map.
3052 *
3053 * PARAMETERS:
3054 * cp - pointer to the 32-bit value.
3055 *
3056 * RETURN VALUES:
3057 * largest binary buddy of free bits within a dmap word.
3058 */
3060 {
3063 /* check if the wmap word is all free. if so, the
3064 * free buddy size is BUDMIN.
3065 */
3069 /* check if the wmap word is half free. if so, the
3070 * free buddy size is BUDMIN-1.
3071 */
3075 /* not all free or half free. determine the free buddy
3076 * size thru table lookup using quarters of the wmap word.
3077 */
3081 }
3084 /*
3085 * NAME: cnttz(uint word)
3086 *
3087 * FUNCTION: determine the number of trailing zeros within a 32-bit
3088 * value.
3089 *
3090 * PARAMETERS:
3091 * value - 32-bit value to be examined.
3092 *
3093 * RETURN VALUES:
3094 * count of trailing zeros
3095 */
3097 {
3103 }
3106 }
3109 /*
3110 * NAME: cntlz(u32 value)
3111 *
3112 * FUNCTION: determine the number of leading zeros within a 32-bit
3113 * value.
3114 *
3115 * PARAMETERS:
3116 * value - 32-bit value to be examined.
3117 *
3118 * RETURN VALUES:
3119 * count of leading zeros
3120 */
3122 {
3128 }
3130 }
3133 /*
3134 * NAME: blkstol2(s64 nb)
3135 *
3136 * FUNCTION: convert a block count to its log2 value. if the block
3137 * count is not a l2 multiple, it is rounded up to the next
3138 * larger l2 multiple.
3139 *
3140 * PARAMETERS:
3141 * nb - number of blocks
3142 *
3143 * RETURN VALUES:
3144 * log2 number of blocks
3145 */
3147 {
3153 /* count the leading bits.
3154 */
3156 /* leading bit found.
3157 */
3159 /* determine the l2 value.
3160 */
3163 /* check if we need to round up.
3164 */
3166 l2nb++;
3169 }
3170 }
3173 }
3176 /*
3177 * NAME: dbAllocBottomUp()
3178 *
3179 * FUNCTION: alloc the specified block range from the working block
3180 * allocation map.
3181 *
3182 * the blocks will be alloc from the working map one dmap
3183 * at a time.
3184 *
3185 * PARAMETERS:
3186 * ip - pointer to in-core inode;
3187 * blkno - starting block number to be freed.
3188 * nblocks - number of blocks to be freed.
3189 *
3190 * RETURN VALUES:
3191 * 0 - success
3192 * -EIO - i/o error
3193 */
3195 {
3205 /* block to be allocated better be within the mapsize. */
3208 /*
3209 * allocate the blocks a dmap at a time.
3210 */
3213 /* release previous dmap if any */
3216 }
3218 /* get the buffer for the current dmap. */
3224 }
3227 /* determine the number of blocks to be allocated from
3228 * this dmap.
3229 */
3232 /* allocate the blocks. */
3237 }
3238 }
3240 /* write the last buffer. */
3246 }
3251 {
3254 s8 oldroot;
3257 /* save the current value of the root (i.e. maximum free string)
3258 * of the dmap tree.
3259 */
3262 /* determine the bit number and word within the dmap of the
3263 * starting block.
3264 */
3268 /* block range better be within the dmap */
3271 /* allocate the bits of the dmap's words corresponding to the block
3272 * range. not all bits of the first and last words may be contained
3273 * within the block range. if this is the case, we'll work against
3274 * those words (i.e. partial first and/or last) on an individual basis
3275 * (a single pass), allocating the bits of interest by hand and
3276 * updating the leaf corresponding to the dmap word. a single pass
3277 * will be used for all dmap words fully contained within the
3278 * specified range. within this pass, the bits of all fully contained
3279 * dmap words will be marked as free in a single shot and the leaves
3280 * will be updated. a single leaf may describe the free space of
3281 * multiple dmap words, so we may update only a subset of the actual
3282 * leaves corresponding to the dmap words of the block range.
3283 */
3285 /* determine the bit number within the word and
3286 * the number of bits within the word.
3287 */
3291 /* check if only part of a word is to be allocated.
3292 */
3294 /* allocate (set to 1) the appropriate bits within
3295 * this dmap word.
3296 */
3300 word++;
3302 /* one or more dmap words are fully contained
3303 * within the block range. determine how many
3304 * words and allocate (set to 1) the bits of these
3305 * words.
3306 */
3310 /* determine how many bits */
3313 }
3314 }
3316 /* update the free count for this dmap */
3319 /* reconstruct summary tree */
3324 /* if this allocation group is completely free,
3325 * update the highest active allocation group number
3326 * if this allocation group is the new max.
3327 */
3332 /* update the free count for the allocation group and map */
3338 /* if the root has not changed, done. */
3342 /* root changed. bubble the change up to the dmap control pages.
3343 * if the adjustment of the upper level control pages fails,
3344 * backout the bit allocation (thus making everything consistent).
3345 */
3350 }
3353 /*
3354 * NAME: dbExtendFS()
3355 *
3356 * FUNCTION: extend bmap from blkno for nblocks;
3357 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3358 *
3359 * L2
3360 * |
3361 * L1---------------------------------L1
3362 * | |
3363 * L0---------L0---------L0 L0---------L0---------L0
3364 * | | | | | |
3365 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3366 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3367 *
3368 * <---old---><----------------------------extend----------------------->
3369 */
3371 {
3375 s64 newsize;
3376 s64 p;
3383 s64 ag_rem;
3390 /*
3391 * initialize bmap control page.
3392 *
3393 * all the data in bmap control page should exclude
3394 * the mkfs hidden dmap page.
3395 */
3397 /* update mapsize */
3401 /* compute new AG size */
3408 /* compute new number of AG */
3413 /*
3414 * reconfigure db_agfree[]
3415 * from old AG configuration to new AG configuration;
3416 *
3417 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3418 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3419 * note: new AG size = old AG size * (2**x).
3420 */
3428 /* coalesce contiguous k AGs; */
3430 /* merge AGi to AGn */
3432 }
3433 }
3439 /*
3440 * update highest active ag number
3441 */
3445 /*
3446 * extend bmap
3447 *
3448 * update bit maps and corresponding level control pages;
3449 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3450 */
3451 extend:
3452 /* get L2 page */
3458 }
3461 /* compute start L1 */
3466 /*
3467 * extend each L1 in L2
3468 */
3470 /* get L1 page */
3472 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3478 /* compute start L0 */
3484 /* assign/init L1 page */
3491 /* compute start L0 */
3495 }
3497 /*
3498 * extend each L0 in L1
3499 */
3501 /* get L0 page */
3503 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3510 /* compute start dmap */
3512 L2BPERDMAP;
3518 /* assign/init L0 page */
3525 /* compute start dmap */
3529 }
3531 /*
3532 * extend each dmap in L0
3533 */
3535 /*
3536 * reconstruct the dmap page, and
3537 * initialize corresponding parent L0 leaf
3538 */
3540 /* read in dmap page: */
3547 /* assign/init dmap page */
3554 }
3565 l0leaf++;
3574 /*
3575 * build current L0 page from its leaves, and
3576 * initialize corresponding parent L1 leaf
3577 */
3585 /* more than 1 L0 ? */
3589 /* summarize in global bmap page */
3594 }
3595 }
3598 /*
3599 * build current L1 page from its leaves, and
3600 * initialize corresponding parent L2 leaf
3601 */
3609 /* more than 1 L1 ? */
3613 /* summarize in global bmap page */
3617 }
3618 }
3622 errout:
3630 /*
3631 * finalize bmap control page
3632 */
3633 finalize:
3636 }
3639 /*
3640 * dbFinalizeBmap()
3641 */
3643 {
3649 /*
3650 * finalize bmap control page
3651 */
3652 //finalize:
3653 /*
3654 * compute db_agpref: preferred ag to allocate from
3655 * (the leftmost ag with average free space in it);
3656 */
3657 //agpref:
3658 /* get the number of active ags and inactive ags */
3663 /* determine how many blocks are in the inactive allocation
3664 * groups. in doing this, we must account for the fact that
3665 * the rightmost group might be a partial group (i.e. file
3666 * system size is not a multiple of the group size).
3667 */
3672 /* determine how many free blocks are in the active
3673 * allocation groups plus the average number of free blocks
3674 * within the active ags.
3675 */
3679 /* if the preferred allocation group has not average free space.
3680 * re-establish the preferred group as the leftmost
3681 * group with average free space.
3682 */
3688 }
3692 }
3693 }
3695 /*
3696 * compute db_aglevel, db_agheight, db_width, db_agstart:
3697 * an ag is covered in aglevel dmapctl summary tree,
3698 * at agheight level height (from leaf) with agwidth number of nodes
3699 * each, which starts at agstart index node of the smmary tree node
3700 * array;
3701 */
3703 l2nl =
3708 i--) {
3711 }
3713 }
3716 /*
3717 * NAME: dbInitDmap()/ujfs_idmap_page()
3718 *
3719 * FUNCTION: initialize working/persistent bitmap of the dmap page
3720 * for the specified number of blocks:
3721 *
3722 * at entry, the bitmaps had been initialized as free (ZEROS);
3723 * The number of blocks will only account for the actually
3724 * existing blocks. Blocks which don't actually exist in
3725 * the aggregate will be marked as allocated (ONES);
3726 *
3727 * PARAMETERS:
3728 * dp - pointer to page of map
3729 * nblocks - number of blocks this page
3730 *
3731 * RETURNS: NONE
3732 */
3734 {
3737 /* starting block number within the dmap */
3748 }
3752 }
3754 /* word number containing start block number */
3757 /*
3758 * free the bits corresponding to the block range (ZEROS):
3759 * note: not all bits of the first and last words may be contained
3760 * within the block range.
3761 */
3763 /* number of bits preceding range to be freed in the word */
3765 /* number of bits to free in the word */
3768 /* is partial word to be freed ? */
3770 /* free (set to 0) from the bitmap word */
3776 /* skip the word freed */
3777 w++;
3779 /* free (set to 0) contiguous bitmap words */
3784 /* skip the words freed */
3787 }
3788 }
3790 /*
3791 * mark bits following the range to be freed (non-existing
3792 * blocks) as allocated (ONES)
3793 */
3798 /* the first word beyond the end of existing blocks */
3801 /* does nblocks fall on a 32-bit boundary ? */
3804 /* mark a partial word allocated */
3806 w++;
3807 }
3809 /* set the rest of the words in the page to allocated (ONES) */
3813 /*
3814 * init tree
3815 */
3816 initTree:
3818 }
3821 /*
3822 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3823 *
3824 * FUNCTION: initialize summary tree of the specified dmap:
3825 *
3826 * at entry, bitmap of the dmap has been initialized;
3827 *
3828 * PARAMETERS:
3829 * dp - dmap to complete
3830 * blkno - starting block number for this dmap
3831 * treemax - will be filled in with max free for this dmap
3832 *
3833 * RETURNS: max free string at the root of the tree
3834 */
3836 {
3841 /* init fixed info of tree */
3849 /* init each leaf from corresponding wmap word:
3850 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3851 * bitmap word are allocated.
3852 */
3857 /* build the dmap's binary buddy summary tree */
3859 }
3862 /*
3863 * NAME: dbInitTree()/ujfs_adjtree()
3864 *
3865 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3866 *
3867 * at entry, the leaves of the tree has been initialized
3868 * from corresponding bitmap word or root of summary tree
3869 * of the child control page;
3870 * configure binary buddy system at the leaf level, then
3871 * bubble up the values of the leaf nodes up the tree.
3872 *
3873 * PARAMETERS:
3874 * cp - Pointer to the root of the tree
3875 * l2leaves- Number of leaf nodes as a power of 2
3876 * l2min - Number of blocks that can be covered by a leaf
3877 * as a power of 2
3878 *
3879 * RETURNS: max free string at the root of the tree
3880 */
3882 {
3889 /* Determine the maximum free string possible for the leaves */
3892 /*
3893 * configure the leaf level into binary buddy system
3894 *
3895 * Try to combine buddies starting with a buddy size of 1
3896 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3897 * can be combined if both buddies have a maximum free of l2min;
3898 * the combination will result in the left-most buddy leaf having
3899 * a maximum free of l2min+1.
3900 * After processing all buddies for a given size, process buddies
3901 * at the next higher buddy size (i.e. current size * 2) and
3902 * the next maximum free (current free + 1).
3903 * This continues until the maximum possible buddy combination
3904 * yields maximum free.
3905 */
3908 /* get next buddy size == current buddy pair size */
3911 /* scan each adjacent buddy pair at current buddy size */
3915 /* coalesce if both adjacent buddies are max free */
3919 }
3920 }
3921 }
3923 /*
3924 * bubble summary information of leaves up the tree.
3925 *
3926 * Starting at the leaf node level, the four nodes described by
3927 * the higher level parent node are compared for a maximum free and
3928 * this maximum becomes the value of the parent node.
3929 * when all lower level nodes are processed in this fashion then
3930 * move up to the next level (parent becomes a lower level node) and
3931 * continue the process for that level.
3932 */
3936 /* get index of 1st node of parent level */
3939 /* set the value of the parent node as the maximum
3940 * of the four nodes of the current level.
3941 */
3945 }
3948 }
3951 /*
3952 * dbInitDmapCtl()
3953 *
3954 * function: initialize dmapctl page
3955 */
3966 /*
3967 * initialize the leaves of current level that were not covered
3968 * by the specified input block range (i.e. the leaves have no
3969 * low level dmapctl or dmap).
3970 */
3975 /* build the dmap's binary buddy summary tree */
3977 }
3980 /*
3981 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3982 *
3983 * FUNCTION: Determine log2(allocation group size) from aggregate size
3984 *
3985 * PARAMETERS:
3986 * nblocks - Number of blocks in aggregate
3987 *
3988 * RETURNS: log2(allocation group size) in aggregate blocks
3989 */
3991 {
3992 s64 sz;
3993 s64 m;
3999 /* round up aggregate size to power of 2 */
4004 }
4010 /* agsize = roundupSize/max_number_of_ag */
4012 }
4015 /*
4016 * NAME: dbMapFileSizeToMapSize()
4017 *
4018 * FUNCTION: compute number of blocks the block allocation map file
4019 * can cover from the map file size;
4020 *
4021 * RETURNS: Number of blocks which can be covered by this block map file;
4022 */
4024 /*
4025 * maximum number of map pages at each level including control pages
4026 */
4027 #define MAXL0PAGES (1 + LPERCTL)
4028 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
4030 /*
4031 * convert number of map pages to the zero origin top dmapctl level
4032 */
4033 #define BMAPPGTOLEV(npages) \
4034 (((npages) <= 3 + MAXL0PAGES) ? 0 : \
4035 ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4038 {
4040 s64 nblocks;
4049 /* At each level, accumulate the number of dmap pages covered by
4050 * the number of full child levels below it;
4051 * repeat for the last incomplete child level.
4052 */
4055 /* skip higher level control pages above top level covered by map */
4059 factor =
4065 /* pages in last/incomplete child */
4067 /* skip incomplete child's level control page */
4068 npages--;
4069 }
4071 /* convert the number of dmaps into the number of blocks
4072 * which can be covered by the dmaps;
4073 */
4077 }