| blob | 4496872cf4e7884b8f6d6b756c8854ed2e23991c |
1 /*
2 * Copyright (C) International Business Machines Corp., 2000-2004
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12 * the GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
19 #include <linux/fs.h>
20 #include <linux/slab.h>
29 /*
30 * SERIALIZATION of the Block Allocation Map.
31 *
32 * the working state of the block allocation map is accessed in
33 * two directions:
34 *
35 * 1) allocation and free requests that start at the dmap
36 * level and move up through the dmap control pages (i.e.
37 * the vast majority of requests).
38 *
39 * 2) allocation requests that start at dmap control page
40 * level and work down towards the dmaps.
41 *
42 * the serialization scheme used here is as follows.
43 *
44 * requests which start at the bottom are serialized against each
45 * other through buffers and each requests holds onto its buffers
46 * as it works it way up from a single dmap to the required level
47 * of dmap control page.
48 * requests that start at the top are serialized against each other
49 * and request that start from the bottom by the multiple read/single
50 * write inode lock of the bmap inode. requests starting at the top
51 * take this lock in write mode while request starting at the bottom
52 * take the lock in read mode. a single top-down request may proceed
53 * exclusively while multiple bottoms-up requests may proceed
54 * simultaneously (under the protection of busy buffers).
55 *
56 * in addition to information found in dmaps and dmap control pages,
57 * the working state of the block allocation map also includes read/
58 * write information maintained in the bmap descriptor (i.e. total
59 * free block count, allocation group level free block counts).
60 * a single exclusive lock (BMAP_LOCK) is used to guard this information
61 * in the face of multiple-bottoms up requests.
62 * (lock ordering: IREAD_LOCK, BMAP_LOCK);
63 *
64 * accesses to the persistent state of the block allocation map (limited
65 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
66 */
68 #define BMAP_LOCK_INIT(bmp) mutex_init(&bmp->db_bmaplock)
69 #define BMAP_LOCK(bmp) mutex_lock(&bmp->db_bmaplock)
70 #define BMAP_UNLOCK(bmp) mutex_unlock(&bmp->db_bmaplock)
72 /*
73 * forward references
74 */
121 /*
122 * buddy table
123 *
124 * table used for determining buddy sizes within characters of
125 * dmap bitmap words. the characters themselves serve as indexes
126 * into the table, with the table elements yielding the maximum
127 * binary buddy of free bits within the character.
128 */
146 };
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 }
314 /*
315 * NAME: dbFree()
316 *
317 * FUNCTION: free the specified block range from the working block
318 * allocation map.
319 *
320 * the blocks will be free from the working map one dmap
321 * at a time.
322 *
323 * PARAMETERS:
324 * ip - pointer to in-core inode;
325 * blkno - starting block number to be freed.
326 * nblocks - number of blocks to be freed.
327 *
328 * RETURN VALUES:
329 * 0 - success
330 * -EIO - i/o error
331 */
333 {
343 /* block to be freed better be within the mapsize. */
352 }
354 /*
355 * free the blocks a dmap at a time.
356 */
359 /* release previous dmap if any */
362 }
364 /* get the buffer for the current dmap. */
370 }
373 /* determine the number of blocks to be freed from
374 * this dmap.
375 */
378 /* free the blocks. */
384 }
385 }
387 /* write the last buffer. */
393 }
396 /*
397 * NAME: dbUpdatePMap()
398 *
399 * FUNCTION: update the allocation state (free or allocate) of the
400 * specified block range in the persistent block allocation map.
401 *
402 * the blocks will be updated in the persistent map one
403 * dmap at a time.
404 *
405 * PARAMETERS:
406 * ipbmap - pointer to in-core inode for the block map.
407 * free - 'true' if block range is to be freed from the persistent
408 * map; 'false' if it is to be allocated.
409 * blkno - starting block number of the range.
410 * nblocks - number of contiguous blocks in the range.
411 * tblk - transaction block;
412 *
413 * RETURN VALUES:
414 * 0 - success
415 * -EIO - i/o error
416 */
417 int
420 {
425 u32 mask;
432 /* the blocks better be within the mapsize. */
440 }
442 /* compute delta of transaction lsn from log syncpt */
447 /*
448 * update the block state a dmap at a time.
449 */
453 /* get the buffer for the current dmap. */
458 }
465 }
468 /* determine the bit number and word within the dmap of
469 * the starting block. also determine how many blocks
470 * are to be updated within this dmap.
471 */
476 /* update the bits of the dmap words. the first and last
477 * words may only have a subset of their bits updated. if
478 * this is the case, we'll work against that word (i.e.
479 * partial first and/or last) only in a single pass. a
480 * single pass will also be used to update all words that
481 * are to have all their bits updated.
482 */
485 /* determine the bit number within the word and
486 * the number of bits within the word.
487 */
491 /* check if only part of the word is to be updated. */
493 /* update (free or allocate) the bits
494 * in this word.
495 */
496 mask =
501 else
507 /* one or more words are to have all
508 * their bits updated. determine how
509 * many words and how many bits.
510 */
514 /* update (free or allocate) the bits
515 * in these words.
516 */
520 else
525 }
526 }
528 /*
529 * update dmap lsn
530 */
538 /* inherit older/smaller lsn */
543 /* move bp after tblock in logsync list */
545 }
547 /* inherit younger/larger clsn */
556 /* insert bp after tblock in logsync list */
561 }
563 }
565 /* write the last buffer. */
568 }
571 }
574 /*
575 * NAME: dbNextAG()
576 *
577 * FUNCTION: find the preferred allocation group for new allocations.
578 *
579 * Within the allocation groups, we maintain a preferred
580 * allocation group which consists of a group with at least
581 * average free space. It is the preferred group that we target
582 * new inode allocation towards. The tie-in between inode
583 * allocation and block allocation occurs as we allocate the
584 * first (data) block of an inode and specify the inode (block)
585 * as the allocation hint for this block.
586 *
587 * We try to avoid having more than one open file growing in
588 * an allocation group, as this will lead to fragmentation.
589 * This differs from the old OS/2 method of trying to keep
590 * empty ags around for large allocations.
591 *
592 * PARAMETERS:
593 * ipbmap - pointer to in-core inode for the block map.
594 *
595 * RETURN VALUES:
596 * the preferred allocation group number.
597 */
599 {
600 s64 avgfree;
609 /* determine the average number of free blocks within the ags. */
612 /*
613 * if the current preferred ag does not have an active allocator
614 * and has at least average freespace, return it
615 */
621 /* From the last preferred ag, find the next one with at least
622 * average free space.
623 */
629 /* open file is currently growing in this ag */
632 /* Return this one */
636 /* Less than avg. freespace, but best so far */
639 }
640 }
642 /*
643 * If no inactive ag was found with average freespace, use the
644 * next best
645 */
648 /* else leave db_agpref unchanged */
649 unlock:
652 /* return the preferred group.
653 */
655 }
657 /*
658 * NAME: dbAlloc()
659 *
660 * FUNCTION: attempt to allocate a specified number of contiguous free
661 * blocks from the working allocation block map.
662 *
663 * the block allocation policy uses hints and a multi-step
664 * approach.
665 *
666 * for allocation requests smaller than the number of blocks
667 * per dmap, we first try to allocate the new blocks
668 * immediately following the hint. if these blocks are not
669 * available, we try to allocate blocks near the hint. if
670 * no blocks near the hint are available, we next try to
671 * allocate within the same dmap as contains the hint.
672 *
673 * if no blocks are available in the dmap or the allocation
674 * request is larger than the dmap size, we try to allocate
675 * within the same allocation group as contains the hint. if
676 * this does not succeed, we finally try to allocate anywhere
677 * within the aggregate.
678 *
679 * we also try to allocate anywhere within the aggregate for
680 * for allocation requests larger than the allocation group
681 * size or requests that specify no hint value.
682 *
683 * PARAMETERS:
684 * ip - pointer to in-core inode;
685 * hint - allocation hint.
686 * nblocks - number of contiguous blocks in the range.
687 * results - on successful return, set to the starting block number
688 * of the newly allocated contiguous range.
689 *
690 * RETURN VALUES:
691 * 0 - success
692 * -ENOSPC - insufficient disk resources
693 * -EIO - i/o error
694 */
696 {
704 s64 mapSize;
707 /* assert that nblocks is valid */
710 /* get the log2 number of blocks to be allocated.
711 * if the number of blocks is not a log2 multiple,
712 * it will be rounded up to the next log2 multiple.
713 */
720 /* the hint should be within the map */
724 }
726 /* if the number of blocks to be allocated is greater than the
727 * allocation group size, try to allocate anywhere.
728 */
735 }
737 /*
738 * If no hint, let dbNextAG recommend an allocation group
739 */
743 /* we would like to allocate close to the hint. adjust the
744 * hint to the block following the hint since the allocators
745 * will start looking for free space starting at this point.
746 */
754 /* check if blkno crosses over into a new allocation group.
755 * if so, check if we should allow allocations within this
756 * allocation group.
757 */
759 /* check if the AG is currently being written to.
760 * if so, call dbNextAG() to find a non-busy
761 * AG with sufficient free space.
762 */
766 /* check if the allocation request size can be satisfied from a
767 * single dmap. if so, try to allocate from the dmap containing
768 * the hint using a tiered strategy.
769 */
773 /* get the buffer for the dmap containing the hint.
774 */
783 /* first, try to satisfy the allocation request with the
784 * blocks beginning at the hint.
785 */
791 }
795 }
800 /*
801 * Someone else is writing in this allocation
802 * group. To avoid fragmenting, try another ag
803 */
807 }
809 /* next, try to satisfy the allocation request with blocks
810 * near the hint.
811 */
820 }
822 /* try to satisfy the allocation request with blocks within
823 * the same dmap as the hint.
824 */
832 }
836 }
838 /* try to satisfy the allocation request with blocks within
839 * the same allocation group as the hint.
840 */
848 pref_ag:
849 /*
850 * Let dbNextAG recommend a preferred allocation group
851 */
855 /* Try to allocate within this allocation group. if that fails, try to
856 * allocate anywhere in the map.
857 */
861 write_unlock:
866 read_unlock:
870 }
872 #ifdef _NOTYET
873 /*
874 * NAME: dbAllocExact()
875 *
876 * FUNCTION: try to allocate the requested extent;
877 *
878 * PARAMETERS:
879 * ip - pointer to in-core inode;
880 * blkno - extent address;
881 * nblocks - extent length;
882 *
883 * RETURN VALUES:
884 * 0 - success
885 * -ENOSPC - insufficient disk resources
886 * -EIO - i/o error
887 */
889 {
894 s64 lblkno;
899 /*
900 * validate extent request:
901 *
902 * note: defragfs policy:
903 * max 64 blocks will be moved.
904 * allocation request size must be satisfied from a single dmap.
905 */
909 }
912 /* the free space is no longer available */
915 }
917 /* read in the dmap covering the extent */
923 }
926 /* try to allocate the requested extent */
937 }
940 /*
941 * NAME: dbReAlloc()
942 *
943 * FUNCTION: attempt to extend a current allocation by a specified
944 * number of blocks.
945 *
946 * this routine attempts to satisfy the allocation request
947 * by first trying to extend the existing allocation in
948 * place by allocating the additional blocks as the blocks
949 * immediately following the current allocation. if these
950 * blocks are not available, this routine will attempt to
951 * allocate a new set of contiguous blocks large enough
952 * to cover the existing allocation plus the additional
953 * number of blocks required.
954 *
955 * PARAMETERS:
956 * ip - pointer to in-core inode requiring allocation.
957 * blkno - starting block of the current allocation.
958 * nblocks - number of contiguous blocks within the current
959 * allocation.
960 * addnblocks - number of blocks to add to the allocation.
961 * results - on successful return, set to the starting block number
962 * of the existing allocation if the existing allocation
963 * was extended in place or to a newly allocated contiguous
964 * range if the existing allocation could not be extended
965 * in place.
966 *
967 * RETURN VALUES:
968 * 0 - success
969 * -ENOSPC - insufficient disk resources
970 * -EIO - i/o error
971 */
972 int
975 {
978 /* try to extend the allocation in place.
979 */
986 }
988 /* could not extend the allocation in place, so allocate a
989 * new set of blocks for the entire request (i.e. try to get
990 * a range of contiguous blocks large enough to cover the
991 * existing allocation plus the additional blocks.)
992 */
995 }
998 /*
999 * NAME: dbExtend()
1000 *
1001 * FUNCTION: attempt to extend a current allocation by a specified
1002 * number of blocks.
1003 *
1004 * this routine attempts to satisfy the allocation request
1005 * by first trying to extend the existing allocation in
1006 * place by allocating the additional blocks as the blocks
1007 * immediately following the current allocation.
1008 *
1009 * PARAMETERS:
1010 * ip - pointer to in-core inode requiring allocation.
1011 * blkno - starting block of the current allocation.
1012 * nblocks - number of contiguous blocks within the current
1013 * allocation.
1014 * addnblocks - number of blocks to add to the allocation.
1015 *
1016 * RETURN VALUES:
1017 * 0 - success
1018 * -ENOSPC - insufficient disk resources
1019 * -EIO - i/o error
1020 */
1022 {
1025 uint rel_block;
1032 /*
1033 * We don't want a non-aligned extent to cross a page boundary
1034 */
1039 /* get the last block of the current allocation */
1042 /* determine the block number of the block following
1043 * the existing allocation.
1044 */
1049 /* better be within the file system */
1056 }
1058 /* we'll attempt to extend the current allocation in place by
1059 * allocating the additional blocks as the blocks immediately
1060 * following the current allocation. we only try to extend the
1061 * current allocation in place if the number of additional blocks
1062 * can fit into a dmap, the last block of the current allocation
1063 * is not the last block of the file system, and the start of the
1064 * inplace extension is not on an allocation group boundary.
1065 */
1070 }
1072 /* get the buffer for the dmap containing the first block
1073 * of the extension.
1074 */
1080 }
1084 /* try to allocate the blocks immediately following the
1085 * current allocation.
1086 */
1091 /* were we successful ? */
1094 else
1095 /* we were not successful */
1100 }
1103 /*
1104 * NAME: dbAllocNext()
1105 *
1106 * FUNCTION: attempt to allocate the blocks of the specified block
1107 * range within a dmap.
1108 *
1109 * PARAMETERS:
1110 * bmp - pointer to bmap descriptor
1111 * dp - pointer to dmap.
1112 * blkno - starting block number of the range.
1113 * nblocks - number of contiguous free blocks of the range.
1114 *
1115 * RETURN VALUES:
1116 * 0 - success
1117 * -ENOSPC - insufficient disk resources
1118 * -EIO - i/o error
1119 *
1120 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1121 */
1124 {
1128 u32 mask;
1134 }
1136 /* pick up a pointer to the leaves of the dmap tree.
1137 */
1140 /* determine the bit number and word within the dmap of the
1141 * starting block.
1142 */
1146 /* check if the specified block range is contained within
1147 * this dmap.
1148 */
1152 /* check if the starting leaf indicates that anything
1153 * is free.
1154 */
1158 /* check the dmaps words corresponding to block range to see
1159 * if the block range is free. not all bits of the first and
1160 * last words may be contained within the block range. if this
1161 * is the case, we'll work against those words (i.e. partial first
1162 * and/or last) on an individual basis (a single pass) and examine
1163 * the actual bits to determine if they are free. a single pass
1164 * will be used for all dmap words fully contained within the
1165 * specified range. within this pass, the leaves of the dmap
1166 * tree will be examined to determine if the blocks are free. a
1167 * single leaf may describe the free space of multiple dmap
1168 * words, so we may visit only a subset of the actual leaves
1169 * corresponding to the dmap words of the block range.
1170 */
1172 /* determine the bit number within the word and
1173 * the number of bits within the word.
1174 */
1178 /* check if only part of the word is to be examined.
1179 */
1181 /* check if the bits are free.
1182 */
1189 /* one or more dmap words are fully contained
1190 * within the block range. determine how many
1191 * words and how many bits.
1192 */
1196 /* now examine the appropriate leaves to determine
1197 * if the blocks are free.
1198 */
1200 /* does the leaf describe any free space ?
1201 */
1205 /* determine the l2 number of bits provided
1206 * by this leaf.
1207 */
1208 l2size =
1211 /* determine how many words were handled.
1212 */
1217 }
1218 }
1219 }
1221 /* allocate the blocks.
1222 */
1224 }
1227 /*
1228 * NAME: dbAllocNear()
1229 *
1230 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1231 * a specified block (hint) within a dmap.
1232 *
1233 * starting with the dmap leaf that covers the hint, we'll
1234 * check the next four contiguous leaves for sufficient free
1235 * space. if sufficient free space is found, we'll allocate
1236 * the desired free space.
1237 *
1238 * PARAMETERS:
1239 * bmp - pointer to bmap descriptor
1240 * dp - pointer to dmap.
1241 * blkno - block number to allocate near.
1242 * nblocks - actual number of contiguous free blocks desired.
1243 * l2nb - log2 number of contiguous free blocks desired.
1244 * results - on successful return, set to the starting block number
1245 * of the newly allocated range.
1246 *
1247 * RETURN VALUES:
1248 * 0 - success
1249 * -ENOSPC - insufficient disk resources
1250 * -EIO - i/o error
1251 *
1252 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1253 */
1254 static int
1257 {
1265 }
1269 /* determine the word within the dmap that holds the hint
1270 * (i.e. blkno). also, determine the last word in the dmap
1271 * that we'll include in our examination.
1272 */
1276 /* examine the leaves for sufficient free space.
1277 */
1279 /* does the leaf describe sufficient free space ?
1280 */
1284 /* determine the block number within the file system
1285 * of the first block described by this dmap word.
1286 */
1289 /* if not all bits of the dmap word are free, get the
1290 * starting bit number within the dmap word of the required
1291 * string of free bits and adjust the block number with the
1292 * value.
1293 */
1295 blkno +=
1298 /* allocate the blocks.
1299 */
1304 }
1307 }
1310 /*
1311 * NAME: dbAllocAG()
1312 *
1313 * FUNCTION: attempt to allocate the specified number of contiguous
1314 * free blocks within the specified allocation group.
1315 *
1316 * unless the allocation group size is equal to the number
1317 * of blocks per dmap, the dmap control pages will be used to
1318 * find the required free space, if available. we start the
1319 * search at the highest dmap control page level which
1320 * distinctly describes the allocation group's free space
1321 * (i.e. the highest level at which the allocation group's
1322 * free space is not mixed in with that of any other group).
1323 * in addition, we start the search within this level at a
1324 * height of the dmapctl dmtree at which the nodes distinctly
1325 * describe the allocation group's free space. at this height,
1326 * the allocation group's free space may be represented by 1
1327 * or two sub-trees, depending on the allocation group size.
1328 * we search the top nodes of these subtrees left to right for
1329 * sufficient free space. if sufficient free space is found,
1330 * the subtree is searched to find the leftmost leaf that
1331 * has free space. once we have made it to the leaf, we
1332 * move the search to the next lower level dmap control page
1333 * corresponding to this leaf. we continue down the dmap control
1334 * pages until we find the dmap that contains or starts the
1335 * sufficient free space and we allocate at this dmap.
1336 *
1337 * if the allocation group size is equal to the dmap size,
1338 * we'll start at the dmap corresponding to the allocation
1339 * group and attempt the allocation at this level.
1340 *
1341 * the dmap control page search is also not performed if the
1342 * allocation group is completely free and we go to the first
1343 * dmap of the allocation group to do the allocation. this is
1344 * done because the allocation group may be part (not the first
1345 * part) of a larger binary buddy system, causing the dmap
1346 * control pages to indicate no free space (NOFREE) within
1347 * the allocation group.
1348 *
1349 * PARAMETERS:
1350 * bmp - pointer to bmap descriptor
1351 * agno - allocation group number.
1352 * nblocks - actual number of contiguous free blocks desired.
1353 * l2nb - log2 number of contiguous free blocks desired.
1354 * results - on successful return, set to the starting block number
1355 * of the newly allocated range.
1356 *
1357 * RETURN VALUES:
1358 * 0 - success
1359 * -ENOSPC - insufficient disk resources
1360 * -EIO - i/o error
1361 *
1362 * note: IWRITE_LOCK(ipmap) held on entry/exit;
1363 */
1364 static int
1366 {
1373 /* allocation request should not be for more than the
1374 * allocation group size.
1375 */
1378 "dbAllocAG: allocation request is larger than the "
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 */
1434 }
1436 /* search the subtree(s) of the dmap control page that describes
1437 * the allocation group, looking for sufficient free space. to begin,
1438 * determine how many allocation groups are represented in a dmap
1439 * control page at the control page level (i.e. L0, L1, L2) that
1440 * fully describes an allocation group. next, determine the starting
1441 * tree index of this allocation group within the control page.
1442 */
1443 agperlev =
1447 /* dmap control page trees fan-out by 4 and a single allocation
1448 * group may be described by 1 or 2 subtrees within the ag level
1449 * dmap control page, depending upon the ag size. examine the ag's
1450 * subtrees for sufficient free space, starting with the leftmost
1451 * subtree.
1452 */
1454 /* is there sufficient free space ?
1455 */
1459 /* sufficient free space found in a subtree. now search down
1460 * the subtree to find the leftmost leaf that describes this
1461 * free space.
1462 */
1468 }
1469 }
1475 }
1476 }
1478 /* determine the block number within the file system
1479 * that corresponds to this leaf.
1480 */
1488 blkno +=
1491 /* release the buffer in preparation for going down
1492 * the next level of dmap control pages.
1493 */
1496 /* check if we need to continue to search down the lower
1497 * level dmap control pages. we need to if the number of
1498 * blocks required is less than maximum number of blocks
1499 * described at the next lower level.
1500 */
1503 /* search the lower level dmap control pages to get
1504 * the starting block number of the dmap that
1505 * contains or starts off the free space.
1506 */
1512 "dbAllocAG: control page "
1515 }
1517 }
1518 }
1520 /* allocate the blocks.
1521 */
1527 }
1529 }
1531 /* no space in the allocation group. release the buffer and
1532 * return -ENOSPC.
1533 */
1537 }
1540 /*
1541 * NAME: dbAllocAny()
1542 *
1543 * FUNCTION: attempt to allocate the specified number of contiguous
1544 * free blocks anywhere in the file system.
1545 *
1546 * dbAllocAny() attempts to find the sufficient free space by
1547 * searching down the dmap control pages, starting with the
1548 * highest level (i.e. L0, L1, L2) control page. if free space
1549 * large enough to satisfy the desired free space is found, the
1550 * desired free space is allocated.
1551 *
1552 * PARAMETERS:
1553 * bmp - pointer to bmap descriptor
1554 * nblocks - actual number of contiguous free blocks desired.
1555 * l2nb - log2 number of contiguous free blocks desired.
1556 * results - on successful return, set to the starting block number
1557 * of the newly allocated range.
1558 *
1559 * RETURN VALUES:
1560 * 0 - success
1561 * -ENOSPC - insufficient disk resources
1562 * -EIO - i/o error
1563 *
1564 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1565 */
1567 {
1571 /* starting with the top level dmap control page, search
1572 * down the dmap control levels for sufficient free space.
1573 * if free space is found, dbFindCtl() returns the starting
1574 * block number of the dmap that contains or starts off the
1575 * range of free space.
1576 */
1580 /* allocate the blocks.
1581 */
1587 }
1589 }
1592 /*
1593 * NAME: dbFindCtl()
1594 *
1595 * FUNCTION: starting at a specified dmap control page level and block
1596 * number, search down the dmap control levels for a range of
1597 * contiguous free blocks large enough to satisfy an allocation
1598 * request for the specified number of free blocks.
1599 *
1600 * if sufficient contiguous free blocks are found, this routine
1601 * returns the starting block number within a dmap page that
1602 * contains or starts a range of contiqious free blocks that
1603 * is sufficient in size.
1604 *
1605 * PARAMETERS:
1606 * bmp - pointer to bmap descriptor
1607 * level - starting dmap control page level.
1608 * l2nb - log2 number of contiguous free blocks desired.
1609 * *blkno - on entry, starting block number for conducting the search.
1610 * on successful return, the first block within a dmap page
1611 * that contains or starts a range of contiguous free blocks.
1612 *
1613 * RETURN VALUES:
1614 * 0 - success
1615 * -ENOSPC - insufficient disk resources
1616 * -EIO - i/o error
1617 *
1618 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1619 */
1621 {
1628 /* starting at the specified dmap control page level and block
1629 * number, search down the dmap control levels for the starting
1630 * block number of a dmap page that contains or starts off
1631 * sufficient free blocks.
1632 */
1634 /* get the buffer of the dmap control page for the block
1635 * number and level (i.e. L0, L1, L2).
1636 */
1649 }
1651 /* search the tree within the dmap control page for
1652 * sufficient free space. if sufficient free space is found,
1653 * dbFindLeaf() returns the index of the leaf at which
1654 * free space was found.
1655 */
1658 /* release the buffer.
1659 */
1662 /* space found ?
1663 */
1669 }
1671 }
1673 /* adjust the block number to reflect the location within
1674 * the dmap control page (i.e. the leaf) at which free
1675 * space was found.
1676 */
1679 /* we stop the search at this dmap control page level if
1680 * the number of blocks required is greater than or equal
1681 * to the maximum number of blocks described at the next
1682 * (lower) level.
1683 */
1686 }
1690 }
1693 /*
1694 * NAME: dbAllocCtl()
1695 *
1696 * FUNCTION: attempt to allocate a specified number of contiguous
1697 * blocks starting within a specific dmap.
1698 *
1699 * this routine is called by higher level routines that search
1700 * the dmap control pages above the actual dmaps for contiguous
1701 * free space. the result of successful searches by these
1702 * routines are the starting block numbers within dmaps, with
1703 * the dmaps themselves containing the desired contiguous free
1704 * space or starting a contiguous free space of desired size
1705 * that is made up of the blocks of one or more dmaps. these
1706 * calls should not fail due to insufficent resources.
1707 *
1708 * this routine is called in some cases where it is not known
1709 * whether it will fail due to insufficient resources. more
1710 * specifically, this occurs when allocating from an allocation
1711 * group whose size is equal to the number of blocks per dmap.
1712 * in this case, the dmap control pages are not examined prior
1713 * to calling this routine (to save pathlength) and the call
1714 * might fail.
1715 *
1716 * for a request size that fits within a dmap, this routine relies
1717 * upon the dmap's dmtree to find the requested contiguous free
1718 * space. for request sizes that are larger than a dmap, the
1719 * requested free space will start at the first block of the
1720 * first dmap (i.e. blkno).
1721 *
1722 * PARAMETERS:
1723 * bmp - pointer to bmap descriptor
1724 * nblocks - actual number of contiguous free blocks to allocate.
1725 * l2nb - log2 number of contiguous free blocks to allocate.
1726 * blkno - starting block number of the dmap to start the allocation
1727 * from.
1728 * results - on successful return, set to the starting block number
1729 * of the newly allocated range.
1730 *
1731 * RETURN VALUES:
1732 * 0 - success
1733 * -ENOSPC - insufficient disk resources
1734 * -EIO - i/o error
1735 *
1736 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1737 */
1738 static int
1740 {
1746 /* check if the allocation request is confined to a single dmap.
1747 */
1749 /* get the buffer for the dmap.
1750 */
1757 /* try to allocate the blocks.
1758 */
1766 }
1768 /* allocation request involving multiple dmaps. it must start on
1769 * a dmap boundary.
1770 */
1773 /* allocate the blocks dmap by dmap.
1774 */
1776 /* get the buffer for the dmap.
1777 */
1783 }
1786 /* the dmap better be all free.
1787 */
1794 }
1796 /* determine how many blocks to allocate from this dmap.
1797 */
1800 /* allocate the blocks from the dmap.
1801 */
1805 }
1807 /* write the buffer.
1808 */
1810 }
1812 /* set the results (starting block number) and return.
1813 */
1817 /* something failed in handling an allocation request involving
1818 * multiple dmaps. we'll try to clean up by backing out any
1819 * allocation that has already happened for this request. if
1820 * we fail in backing out the allocation, we'll mark the file
1821 * system to indicate that blocks have been leaked.
1822 */
1823 backout:
1825 /* try to backout the allocations dmap by dmap.
1826 */
1829 /* get the buffer for this dmap.
1830 */
1834 /* could not back out. mark the file system
1835 * to indicate that we have leaked blocks.
1836 */
1840 }
1843 /* free the blocks is this dmap.
1844 */
1846 /* could not back out. mark the file system
1847 * to indicate that we have leaked blocks.
1848 */
1853 }
1855 /* write the buffer.
1856 */
1858 }
1861 }
1864 /*
1865 * NAME: dbAllocDmapLev()
1866 *
1867 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1868 * from a specified dmap.
1869 *
1870 * this routine checks if the contiguous blocks are available.
1871 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1872 * returned.
1873 *
1874 * PARAMETERS:
1875 * mp - pointer to bmap descriptor
1876 * dp - pointer to dmap to attempt to allocate blocks from.
1877 * l2nb - log2 number of contiguous block desired.
1878 * nblocks - actual number of contiguous block desired.
1879 * results - on successful return, set to the starting block number
1880 * of the newly allocated range.
1881 *
1882 * RETURN VALUES:
1883 * 0 - success
1884 * -ENOSPC - insufficient disk resources
1885 * -EIO - i/o error
1886 *
1887 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1888 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1889 */
1890 static int
1893 {
1894 s64 blkno;
1897 /* can't be more than a dmaps worth of blocks */
1900 /* search the tree within the dmap page for sufficient
1901 * free space. if sufficient free space is found, dbFindLeaf()
1902 * returns the index of the leaf at which free space was found.
1903 */
1907 /* determine the block number within the file system corresponding
1908 * to the leaf at which free space was found.
1909 */
1912 /* if not all bits of the dmap word are free, get the starting
1913 * bit number within the dmap word of the required string of free
1914 * bits and adjust the block number with this value.
1915 */
1919 /* allocate the blocks */
1924 }
1927 /*
1928 * NAME: dbAllocDmap()
1929 *
1930 * FUNCTION: adjust the disk allocation map to reflect the allocation
1931 * of a specified block range within a dmap.
1932 *
1933 * this routine allocates the specified blocks from the dmap
1934 * through a call to dbAllocBits(). if the allocation of the
1935 * block range causes the maximum string of free blocks within
1936 * the dmap to change (i.e. the value of the root of the dmap's
1937 * dmtree), this routine will cause this change to be reflected
1938 * up through the appropriate levels of the dmap control pages
1939 * by a call to dbAdjCtl() for the L0 dmap control page that
1940 * covers this dmap.
1941 *
1942 * PARAMETERS:
1943 * bmp - pointer to bmap descriptor
1944 * dp - pointer to dmap to allocate the block range from.
1945 * blkno - starting block number of the block to be allocated.
1946 * nblocks - number of blocks to be allocated.
1947 *
1948 * RETURN VALUES:
1949 * 0 - success
1950 * -EIO - i/o error
1951 *
1952 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
1953 */
1956 {
1957 s8 oldroot;
1960 /* save the current value of the root (i.e. maximum free string)
1961 * of the dmap tree.
1962 */
1965 /* allocate the specified (blocks) bits */
1968 /* if the root has not changed, done. */
1972 /* root changed. bubble the change up to the dmap control pages.
1973 * if the adjustment of the upper level control pages fails,
1974 * backout the bit allocation (thus making everything consistent).
1975 */
1980 }
1983 /*
1984 * NAME: dbFreeDmap()
1985 *
1986 * FUNCTION: adjust the disk allocation map to reflect the allocation
1987 * of a specified block range within a dmap.
1988 *
1989 * this routine frees the specified blocks from the dmap through
1990 * a call to dbFreeBits(). if the deallocation of the block range
1991 * causes the maximum string of free blocks within the dmap to
1992 * change (i.e. the value of the root of the dmap's dmtree), this
1993 * routine will cause this change to be reflected up through the
1994 * appropriate levels of the dmap control pages by a call to
1995 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
1996 *
1997 * PARAMETERS:
1998 * bmp - pointer to bmap descriptor
1999 * dp - pointer to dmap to free the block range from.
2000 * blkno - starting block number of the block to be freed.
2001 * nblocks - number of blocks to be freed.
2002 *
2003 * RETURN VALUES:
2004 * 0 - success
2005 * -EIO - i/o error
2006 *
2007 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2008 */
2011 {
2012 s8 oldroot;
2015 /* save the current value of the root (i.e. maximum free string)
2016 * of the dmap tree.
2017 */
2020 /* free the specified (blocks) bits */
2023 /* if error or the root has not changed, done. */
2027 /* root changed. bubble the change up to the dmap control pages.
2028 * if the adjustment of the upper level control pages fails,
2029 * backout the deallocation.
2030 */
2034 /* as part of backing out the deallocation, we will have
2035 * to back split the dmap tree if the deallocation caused
2036 * the freed blocks to become part of a larger binary buddy
2037 * system.
2038 */
2043 }
2046 }
2049 /*
2050 * NAME: dbAllocBits()
2051 *
2052 * FUNCTION: allocate a specified block range from a dmap.
2053 *
2054 * this routine updates the dmap to reflect the working
2055 * state allocation of the specified block range. it directly
2056 * updates the bits of the working map and causes the adjustment
2057 * of the binary buddy system described by the dmap's dmtree
2058 * leaves to reflect the bits allocated. it also causes the
2059 * dmap's dmtree, as a whole, to reflect the allocated range.
2060 *
2061 * PARAMETERS:
2062 * bmp - pointer to bmap descriptor
2063 * dp - pointer to dmap to allocate bits from.
2064 * blkno - starting block number of the bits to be allocated.
2065 * nblocks - number of bits to be allocated.
2066 *
2067 * RETURN VALUES: none
2068 *
2069 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2070 */
2073 {
2079 /* pick up a pointer to the leaves of the dmap tree */
2082 /* determine the bit number and word within the dmap of the
2083 * starting block.
2084 */
2088 /* block range better be within the dmap */
2091 /* allocate the bits of the dmap's words corresponding to the block
2092 * range. not all bits of the first and last words may be contained
2093 * within the block range. if this is the case, we'll work against
2094 * those words (i.e. partial first and/or last) on an individual basis
2095 * (a single pass), allocating the bits of interest by hand and
2096 * updating the leaf corresponding to the dmap word. a single pass
2097 * will be used for all dmap words fully contained within the
2098 * specified range. within this pass, the bits of all fully contained
2099 * dmap words will be marked as free in a single shot and the leaves
2100 * will be updated. a single leaf may describe the free space of
2101 * multiple dmap words, so we may update only a subset of the actual
2102 * leaves corresponding to the dmap words of the block range.
2103 */
2105 /* determine the bit number within the word and
2106 * the number of bits within the word.
2107 */
2111 /* check if only part of a word is to be allocated.
2112 */
2114 /* allocate (set to 1) the appropriate bits within
2115 * this dmap word.
2116 */
2120 /* update the leaf for this dmap word. in addition
2121 * to setting the leaf value to the binary buddy max
2122 * of the updated dmap word, dbSplit() will split
2123 * the binary system of the leaves if need be.
2124 */
2130 /* one or more dmap words are fully contained
2131 * within the block range. determine how many
2132 * words and allocate (set to 1) the bits of these
2133 * words.
2134 */
2138 /* determine how many bits.
2139 */
2142 /* now update the appropriate leaves to reflect
2143 * the allocated words.
2144 */
2148 "dbAllocBits: leaf page "
2151 }
2153 /* determine what the leaf value should be
2154 * updated to as the minimum of the l2 number
2155 * of bits being allocated and the l2 number
2156 * of bits currently described by this leaf.
2157 */
2160 /* update the leaf to reflect the allocation.
2161 * in addition to setting the leaf value to
2162 * NOFREE, dbSplit() will split the binary
2163 * system of the leaves to reflect the current
2164 * allocation (size).
2165 */
2168 /* get the number of dmap words handled */
2171 }
2172 }
2173 }
2175 /* update the free count for this dmap */
2180 /* if this allocation group is completely free,
2181 * update the maximum allocation group number if this allocation
2182 * group is the new max.
2183 */
2188 /* update the free count for the allocation group and map */
2193 }
2196 /*
2197 * NAME: dbFreeBits()
2198 *
2199 * FUNCTION: free a specified block range from a dmap.
2200 *
2201 * this routine updates the dmap to reflect the working
2202 * state allocation of the specified block range. it directly
2203 * updates the bits of the working map and causes the adjustment
2204 * of the binary buddy system described by the dmap's dmtree
2205 * leaves to reflect the bits freed. it also causes the dmap's
2206 * dmtree, as a whole, to reflect the deallocated range.
2207 *
2208 * PARAMETERS:
2209 * bmp - pointer to bmap descriptor
2210 * dp - pointer to dmap to free bits from.
2211 * blkno - starting block number of the bits to be freed.
2212 * nblocks - number of bits to be freed.
2213 *
2214 * RETURN VALUES: 0 for success
2215 *
2216 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2217 */
2220 {
2226 /* determine the bit number and word within the dmap of the
2227 * starting block.
2228 */
2232 /* block range better be within the dmap.
2233 */
2236 /* free the bits of the dmaps words corresponding to the block range.
2237 * not all bits of the first and last words may be contained within
2238 * the block range. if this is the case, we'll work against those
2239 * words (i.e. partial first and/or last) on an individual basis
2240 * (a single pass), freeing the bits of interest by hand and updating
2241 * the leaf corresponding to the dmap word. a single pass will be used
2242 * for all dmap words fully contained within the specified range.
2243 * within this pass, the bits of all fully contained dmap words will
2244 * be marked as free in a single shot and the leaves will be updated. a
2245 * single leaf may describe the free space of multiple dmap words,
2246 * so we may update only a subset of the actual leaves corresponding
2247 * to the dmap words of the block range.
2248 *
2249 * dbJoin() is used to update leaf values and will join the binary
2250 * buddy system of the leaves if the new leaf values indicate this
2251 * should be done.
2252 */
2254 /* determine the bit number within the word and
2255 * the number of bits within the word.
2256 */
2260 /* check if only part of a word is to be freed.
2261 */
2263 /* free (zero) the appropriate bits within this
2264 * dmap word.
2265 */
2270 /* update the leaf for this dmap word.
2271 */
2279 /* one or more dmap words are fully contained
2280 * within the block range. determine how many
2281 * words and free (zero) the bits of these words.
2282 */
2286 /* determine how many bits.
2287 */
2290 /* now update the appropriate leaves to reflect
2291 * the freed words.
2292 */
2294 /* determine what the leaf value should be
2295 * updated to as the minimum of the l2 number
2296 * of bits being freed and the l2 (max) number
2297 * of bits that can be described by this leaf.
2298 */
2299 size =
2304 /* update the leaf.
2305 */
2310 /* get the number of dmap words handled.
2311 */
2314 }
2315 }
2316 }
2318 /* update the free count for this dmap.
2319 */
2324 /* update the free count for the allocation group and
2325 * map.
2326 */
2331 /* check if this allocation group is not completely free and
2332 * if it is currently the maximum (rightmost) allocation group.
2333 * if so, establish the new maximum allocation group number by
2334 * searching left for the first allocation group with allocation.
2335 */
2344 }
2346 /* re-establish the allocation group preference if the
2347 * current preference is right of the maximum allocation
2348 * group.
2349 */
2352 }
2357 }
2360 /*
2361 * NAME: dbAdjCtl()
2362 *
2363 * FUNCTION: adjust a dmap control page at a specified level to reflect
2364 * the change in a lower level dmap or dmap control page's
2365 * maximum string of free blocks (i.e. a change in the root
2366 * of the lower level object's dmtree) due to the allocation
2367 * or deallocation of a range of blocks with a single dmap.
2368 *
2369 * on entry, this routine is provided with the new value of
2370 * the lower level dmap or dmap control page root and the
2371 * starting block number of the block range whose allocation
2372 * or deallocation resulted in the root change. this range
2373 * is respresented by a single leaf of the current dmapctl
2374 * and the leaf will be updated with this value, possibly
2375 * causing a binary buddy system within the leaves to be
2376 * split or joined. the update may also cause the dmapctl's
2377 * dmtree to be updated.
2378 *
2379 * if the adjustment of the dmap control page, itself, causes its
2380 * root to change, this change will be bubbled up to the next dmap
2381 * control level by a recursive call to this routine, specifying
2382 * the new root value and the next dmap control page level to
2383 * be adjusted.
2384 * PARAMETERS:
2385 * bmp - pointer to bmap descriptor
2386 * blkno - the first block of a block range within a dmap. it is
2387 * the allocation or deallocation of this block range that
2388 * requires the dmap control page to be adjusted.
2389 * newval - the new value of the lower level dmap or dmap control
2390 * page root.
2391 * alloc - 'true' if adjustment is due to an allocation.
2392 * level - current level of dmap control page (i.e. L0, L1, L2) to
2393 * be adjusted.
2394 *
2395 * RETURN VALUES:
2396 * 0 - success
2397 * -EIO - i/o error
2398 *
2399 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2400 */
2401 static int
2403 {
2405 s8 oldroot;
2407 s64 lblkno;
2411 /* get the buffer for the dmap control page for the specified
2412 * block number and control page level.
2413 */
2425 }
2427 /* determine the leaf number corresponding to the block and
2428 * the index within the dmap control tree.
2429 */
2433 /* save the current leaf value and the current root level (i.e.
2434 * maximum l2 free string described by this dmapctl).
2435 */
2439 /* check if this is a control page update for an allocation.
2440 * if so, update the leaf to reflect the new leaf value using
2441 * dbSplit(); otherwise (deallocation), use dbJoin() to update
2442 * the leaf with the new value. in addition to updating the
2443 * leaf, dbSplit() will also split the binary buddy system of
2444 * the leaves, if required, and bubble new values within the
2445 * dmapctl tree, if required. similarly, dbJoin() will join
2446 * the binary buddy system of leaves and bubble new values up
2447 * the dmapctl tree as required by the new leaf value.
2448 */
2450 /* check if we are in the middle of a binary buddy
2451 * system. this happens when we are performing the
2452 * first allocation out of an allocation group that
2453 * is part (not the first part) of a larger binary
2454 * buddy system. if we are in the middle, back split
2455 * the system prior to calling dbSplit() which assumes
2456 * that it is at the front of a binary buddy system.
2457 */
2463 }
2469 }
2471 /* check if the root of the current dmap control page changed due
2472 * to the update and if the current dmap control page is not at
2473 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2474 * root changed and this is not the top level), call this routine
2475 * again (recursion) for the next higher level of the mapping to
2476 * reflect the change in root for the current dmap control page.
2477 */
2479 /* are we below the top level of the map. if so,
2480 * bubble the root up to the next higher level.
2481 */
2483 /* bubble up the new root of this dmap control page to
2484 * the next level.
2485 */
2489 /* something went wrong in bubbling up the new
2490 * root value, so backout the changes to the
2491 * current dmap control page.
2492 */
2495 oldval);
2497 /* the dbJoin() above might have
2498 * caused a larger binary buddy system
2499 * to form and we may now be in the
2500 * middle of it. if this is the case,
2501 * back split the buddies.
2502 */
2508 }
2510 /* release the buffer and return the error.
2511 */
2514 }
2516 /* we're at the top level of the map. update
2517 * the bmap control page to reflect the size
2518 * of the maximum free buddy system.
2519 */
2523 "dbAdjCtl: the maximum free buddy is "
2525 }
2527 }
2528 }
2530 /* write the buffer.
2531 */
2535 }
2538 /*
2539 * NAME: dbSplit()
2540 *
2541 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2542 * the leaf from the binary buddy system of the dmtree's
2543 * leaves, as required.
2544 *
2545 * PARAMETERS:
2546 * tp - pointer to the tree containing the leaf.
2547 * leafno - the number of the leaf to be updated.
2548 * splitsz - the size the binary buddy system starting at the leaf
2549 * must be split to, specified as the log2 number of blocks.
2550 * newval - the new value for the leaf.
2551 *
2552 * RETURN VALUES: none
2553 *
2554 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2555 */
2557 {
2562 /* check if the leaf needs to be split.
2563 */
2565 /* the split occurs by cutting the buddy system in half
2566 * at the specified leaf until we reach the specified
2567 * size. pick up the starting split size (current size
2568 * - 1 in l2) and the corresponding buddy size.
2569 */
2573 /* split until we reach the specified size.
2574 */
2576 /* update the buddy's leaf with its new value.
2577 */
2580 /* on to the next size and buddy.
2581 */
2584 }
2585 }
2587 /* adjust the dmap tree to reflect the specified leaf's new
2588 * value.
2589 */
2591 }
2594 /*
2595 * NAME: dbBackSplit()
2596 *
2597 * FUNCTION: back split the binary buddy system of dmtree leaves
2598 * that hold a specified leaf until the specified leaf
2599 * starts its own binary buddy system.
2600 *
2601 * the allocators typically perform allocations at the start
2602 * of binary buddy systems and dbSplit() is used to accomplish
2603 * any required splits. in some cases, however, allocation
2604 * may occur in the middle of a binary system and requires a
2605 * back split, with the split proceeding out from the middle of
2606 * the system (less efficient) rather than the start of the
2607 * system (more efficient). the cases in which a back split
2608 * is required are rare and are limited to the first allocation
2609 * within an allocation group which is a part (not first part)
2610 * of a larger binary buddy system and a few exception cases
2611 * in which a previous join operation must be backed out.
2612 *
2613 * PARAMETERS:
2614 * tp - pointer to the tree containing the leaf.
2615 * leafno - the number of the leaf to be updated.
2616 *
2617 * RETURN VALUES: none
2618 *
2619 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2620 */
2622 {
2627 /* leaf should be part (not first part) of a binary
2628 * buddy system.
2629 */
2632 /* the back split is accomplished by iteratively finding the leaf
2633 * that starts the buddy system that contains the specified leaf and
2634 * splitting that system in two. this iteration continues until
2635 * the specified leaf becomes the start of a buddy system.
2636 *
2637 * determine maximum possible l2 size for the specified leaf.
2638 */
2639 size =
2643 /* determine the number of leaves covered by this size. this
2644 * is the buddy size that we will start with as we search for
2645 * the buddy system that contains the specified leaf.
2646 */
2649 /* back split.
2650 */
2652 /* find the leftmost buddy leaf.
2653 */
2659 }
2661 /* determine the buddy.
2662 */
2665 /* check if this buddy is the start of the system.
2666 */
2668 /* split the leaf at the start of the
2669 * system in two.
2670 */
2674 }
2675 }
2676 }
2681 }
2683 }
2686 /*
2687 * NAME: dbJoin()
2688 *
2689 * FUNCTION: update the leaf of a dmtree with a new value, joining
2690 * the leaf with other leaves of the dmtree into a multi-leaf
2691 * binary buddy system, as required.
2692 *
2693 * PARAMETERS:
2694 * tp - pointer to the tree containing the leaf.
2695 * leafno - the number of the leaf to be updated.
2696 * newval - the new value for the leaf.
2697 *
2698 * RETURN VALUES: none
2699 */
2701 {
2705 /* can the new leaf value require a join with other leaves ?
2706 */
2708 /* pickup a pointer to the leaves of the tree.
2709 */
2712 /* try to join the specified leaf into a large binary
2713 * buddy system. the join proceeds by attempting to join
2714 * the specified leafno with its buddy (leaf) at new value.
2715 * if the join occurs, we attempt to join the left leaf
2716 * of the joined buddies with its buddy at new value + 1.
2717 * we continue to join until we find a buddy that cannot be
2718 * joined (does not have a value equal to the size of the
2719 * last join) or until all leaves have been joined into a
2720 * single system.
2721 *
2722 * get the buddy size (number of words covered) of
2723 * the new value.
2724 */
2727 /* try to join.
2728 */
2730 /* get the buddy leaf.
2731 */
2734 /* if the leaf's new value is greater than its
2735 * buddy's value, we join no more.
2736 */
2740 /* It shouldn't be less */
2744 /* check which (leafno or buddy) is the left buddy.
2745 * the left buddy gets to claim the blocks resulting
2746 * from the join while the right gets to claim none.
2747 * the left buddy is also eligible to participate in
2748 * a join at the next higher level while the right
2749 * is not.
2750 *
2751 */
2753 /* leafno is the left buddy.
2754 */
2757 /* buddy is the left buddy and becomes
2758 * leafno.
2759 */
2762 }
2764 /* on to try the next join.
2765 */
2768 }
2769 }
2771 /* update the leaf value.
2772 */
2776 }
2779 /*
2780 * NAME: dbAdjTree()
2781 *
2782 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2783 * the dmtree, as required, to reflect the new leaf value.
2784 * the combination of any buddies must already be done before
2785 * this is called.
2786 *
2787 * PARAMETERS:
2788 * tp - pointer to the tree to be adjusted.
2789 * leafno - the number of the leaf to be updated.
2790 * newval - the new value for the leaf.
2791 *
2792 * RETURN VALUES: none
2793 */
2795 {
2799 /* pick up the index of the leaf for this leafno.
2800 */
2803 /* is the current value the same as the old value ? if so,
2804 * there is nothing to do.
2805 */
2809 /* set the new value.
2810 */
2813 /* bubble the new value up the tree as required.
2814 */
2816 /* get the index of the first leaf of the 4 leaf
2817 * group containing the specified leaf (leafno).
2818 */
2821 /* get the index of the parent of this 4 leaf group.
2822 */
2825 /* determine the maximum of the 4 leaves.
2826 */
2829 /* if the maximum of the 4 is the same as the
2830 * parent's value, we're done.
2831 */
2835 /* parent gets new value.
2836 */
2839 /* parent becomes leaf for next go-round.
2840 */
2842 }
2843 }
2846 /*
2847 * NAME: dbFindLeaf()
2848 *
2849 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2850 * the index of a leaf describing the free blocks if
2851 * sufficient free blocks are found.
2852 *
2853 * the search starts at the top of the dmtree_t tree and
2854 * proceeds down the tree to the leftmost leaf with sufficient
2855 * free space.
2856 *
2857 * PARAMETERS:
2858 * tp - pointer to the tree to be searched.
2859 * l2nb - log2 number of free blocks to search for.
2860 * leafidx - return pointer to be set to the index of the leaf
2861 * describing at least l2nb free blocks if sufficient
2862 * free blocks are found.
2863 *
2864 * RETURN VALUES:
2865 * 0 - success
2866 * -ENOSPC - insufficient free blocks.
2867 */
2869 {
2872 /* first check the root of the tree to see if there is
2873 * sufficient free space.
2874 */
2878 /* sufficient free space available. now search down the tree
2879 * starting at the next level for the leftmost leaf that
2880 * describes sufficient free space.
2881 */
2884 /* search the four nodes at this level, starting from
2885 * the left.
2886 */
2888 /* sufficient free space found. move to the next
2889 * level (or quit if this is the last level).
2890 */
2893 }
2895 /* better have found something since the higher
2896 * levels of the tree said it was here.
2897 */
2899 }
2901 /* set the return to the leftmost leaf describing sufficient
2902 * free space.
2903 */
2907 }
2910 /*
2911 * NAME: dbFindBits()
2912 *
2913 * FUNCTION: find a specified number of binary buddy free bits within a
2914 * dmap bitmap word value.
2915 *
2916 * this routine searches the bitmap value for (1 << l2nb) free
2917 * bits at (1 << l2nb) alignments within the value.
2918 *
2919 * PARAMETERS:
2920 * word - dmap bitmap word value.
2921 * l2nb - number of free bits specified as a log2 number.
2922 *
2923 * RETURN VALUES:
2924 * starting bit number of free bits.
2925 */
2927 {
2929 u32 mask;
2931 /* get the number of bits.
2932 */
2936 /* complement the word so we can use a mask (i.e. 0s represent
2937 * free bits) and compute the mask.
2938 */
2942 /* scan the word for nb free bits at nb alignments.
2943 */
2947 }
2951 /* return the bit number.
2952 */
2954 }
2957 /*
2958 * NAME: dbMaxBud(u8 *cp)
2959 *
2960 * FUNCTION: determine the largest binary buddy string of free
2961 * bits within 32-bits of the map.
2962 *
2963 * PARAMETERS:
2964 * cp - pointer to the 32-bit value.
2965 *
2966 * RETURN VALUES:
2967 * largest binary buddy of free bits within a dmap word.
2968 */
2970 {
2973 /* check if the wmap word is all free. if so, the
2974 * free buddy size is BUDMIN.
2975 */
2979 /* check if the wmap word is half free. if so, the
2980 * free buddy size is BUDMIN-1.
2981 */
2985 /* not all free or half free. determine the free buddy
2986 * size thru table lookup using quarters of the wmap word.
2987 */
2991 }
2994 /*
2995 * NAME: cnttz(uint word)
2996 *
2997 * FUNCTION: determine the number of trailing zeros within a 32-bit
2998 * value.
2999 *
3000 * PARAMETERS:
3001 * value - 32-bit value to be examined.
3002 *
3003 * RETURN VALUES:
3004 * count of trailing zeros
3005 */
3007 {
3013 }
3016 }
3019 /*
3020 * NAME: cntlz(u32 value)
3021 *
3022 * FUNCTION: determine the number of leading zeros within a 32-bit
3023 * value.
3024 *
3025 * PARAMETERS:
3026 * value - 32-bit value to be examined.
3027 *
3028 * RETURN VALUES:
3029 * count of leading zeros
3030 */
3032 {
3038 }
3040 }
3043 /*
3044 * NAME: blkstol2(s64 nb)
3045 *
3046 * FUNCTION: convert a block count to its log2 value. if the block
3047 * count is not a l2 multiple, it is rounded up to the next
3048 * larger l2 multiple.
3049 *
3050 * PARAMETERS:
3051 * nb - number of blocks
3052 *
3053 * RETURN VALUES:
3054 * log2 number of blocks
3055 */
3057 {
3063 /* count the leading bits.
3064 */
3066 /* leading bit found.
3067 */
3069 /* determine the l2 value.
3070 */
3073 /* check if we need to round up.
3074 */
3076 l2nb++;
3079 }
3080 }
3083 }
3086 /*
3087 * NAME: dbAllocBottomUp()
3088 *
3089 * FUNCTION: alloc the specified block range from the working block
3090 * allocation map.
3091 *
3092 * the blocks will be alloc from the working map one dmap
3093 * at a time.
3094 *
3095 * PARAMETERS:
3096 * ip - pointer to in-core inode;
3097 * blkno - starting block number to be freed.
3098 * nblocks - number of blocks to be freed.
3099 *
3100 * RETURN VALUES:
3101 * 0 - success
3102 * -EIO - i/o error
3103 */
3105 {
3115 /* block to be allocated better be within the mapsize. */
3118 /*
3119 * allocate the blocks a dmap at a time.
3120 */
3123 /* release previous dmap if any */
3126 }
3128 /* get the buffer for the current dmap. */
3134 }
3137 /* determine the number of blocks to be allocated from
3138 * this dmap.
3139 */
3142 /* allocate the blocks. */
3147 }
3148 }
3150 /* write the last buffer. */
3156 }
3161 {
3167 /* save the current value of the root (i.e. maximum free string)
3168 * of the dmap tree.
3169 */
3172 /* pick up a pointer to the leaves of the dmap tree */
3175 /* determine the bit number and word within the dmap of the
3176 * starting block.
3177 */
3181 /* block range better be within the dmap */
3184 /* allocate the bits of the dmap's words corresponding to the block
3185 * range. not all bits of the first and last words may be contained
3186 * within the block range. if this is the case, we'll work against
3187 * those words (i.e. partial first and/or last) on an individual basis
3188 * (a single pass), allocating the bits of interest by hand and
3189 * updating the leaf corresponding to the dmap word. a single pass
3190 * will be used for all dmap words fully contained within the
3191 * specified range. within this pass, the bits of all fully contained
3192 * dmap words will be marked as free in a single shot and the leaves
3193 * will be updated. a single leaf may describe the free space of
3194 * multiple dmap words, so we may update only a subset of the actual
3195 * leaves corresponding to the dmap words of the block range.
3196 */
3198 /* determine the bit number within the word and
3199 * the number of bits within the word.
3200 */
3204 /* check if only part of a word is to be allocated.
3205 */
3207 /* allocate (set to 1) the appropriate bits within
3208 * this dmap word.
3209 */
3213 word++;
3215 /* one or more dmap words are fully contained
3216 * within the block range. determine how many
3217 * words and allocate (set to 1) the bits of these
3218 * words.
3219 */
3223 /* determine how many bits */
3226 }
3227 }
3229 /* update the free count for this dmap */
3232 /* reconstruct summary tree */
3237 /* if this allocation group is completely free,
3238 * update the highest active allocation group number
3239 * if this allocation group is the new max.
3240 */
3245 /* update the free count for the allocation group and map */
3251 /* if the root has not changed, done. */
3255 /* root changed. bubble the change up to the dmap control pages.
3256 * if the adjustment of the upper level control pages fails,
3257 * backout the bit allocation (thus making everything consistent).
3258 */
3263 }
3266 /*
3267 * NAME: dbExtendFS()
3268 *
3269 * FUNCTION: extend bmap from blkno for nblocks;
3270 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3271 *
3272 * L2
3273 * |
3274 * L1---------------------------------L1
3275 * | |
3276 * L0---------L0---------L0 L0---------L0---------L0
3277 * | | | | | |
3278 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3279 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3280 *
3281 * <---old---><----------------------------extend----------------------->
3282 */
3284 {
3288 s64 newsize;
3289 s64 p;
3296 s64 ag_rem;
3303 /*
3304 * initialize bmap control page.
3305 *
3306 * all the data in bmap control page should exclude
3307 * the mkfs hidden dmap page.
3308 */
3310 /* update mapsize */
3314 /* compute new AG size */
3321 /* compute new number of AG */
3326 /*
3327 * reconfigure db_agfree[]
3328 * from old AG configuration to new AG configuration;
3329 *
3330 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3331 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3332 * note: new AG size = old AG size * (2**x).
3333 */
3341 /* coalesce contiguous k AGs; */
3343 /* merge AGi to AGn */
3345 }
3346 }
3352 /*
3353 * update highest active ag number
3354 */
3358 /*
3359 * extend bmap
3360 *
3361 * update bit maps and corresponding level control pages;
3362 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3363 */
3364 extend:
3365 /* get L2 page */
3371 }
3374 /* compute start L1 */
3379 /*
3380 * extend each L1 in L2
3381 */
3383 /* get L1 page */
3385 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3391 /* compute start L0 */
3397 /* assign/init L1 page */
3404 /* compute start L0 */
3408 }
3410 /*
3411 * extend each L0 in L1
3412 */
3414 /* get L0 page */
3416 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3423 /* compute start dmap */
3425 L2BPERDMAP;
3431 /* assign/init L0 page */
3438 /* compute start dmap */
3442 }
3444 /*
3445 * extend each dmap in L0
3446 */
3448 /*
3449 * reconstruct the dmap page, and
3450 * initialize corresponding parent L0 leaf
3451 */
3453 /* read in dmap page: */
3460 /* assign/init dmap page */
3467 }
3478 l0leaf++;
3487 /*
3488 * build current L0 page from its leaves, and
3489 * initialize corresponding parent L1 leaf
3490 */
3498 /* more than 1 L0 ? */
3502 /* summarize in global bmap page */
3507 }
3508 }
3511 /*
3512 * build current L1 page from its leaves, and
3513 * initialize corresponding parent L2 leaf
3514 */
3522 /* more than 1 L1 ? */
3526 /* summarize in global bmap page */
3530 }
3531 }
3536 errout:
3544 /*
3545 * finalize bmap control page
3546 */
3547 finalize:
3550 }
3553 /*
3554 * dbFinalizeBmap()
3555 */
3557 {
3563 /*
3564 * finalize bmap control page
3565 */
3566 //finalize:
3567 /*
3568 * compute db_agpref: preferred ag to allocate from
3569 * (the leftmost ag with average free space in it);
3570 */
3571 //agpref:
3572 /* get the number of active ags and inacitve ags */
3577 /* determine how many blocks are in the inactive allocation
3578 * groups. in doing this, we must account for the fact that
3579 * the rightmost group might be a partial group (i.e. file
3580 * system size is not a multiple of the group size).
3581 */
3586 /* determine how many free blocks are in the active
3587 * allocation groups plus the average number of free blocks
3588 * within the active ags.
3589 */
3593 /* if the preferred allocation group has not average free space.
3594 * re-establish the preferred group as the leftmost
3595 * group with average free space.
3596 */
3602 }
3606 }
3607 }
3609 /*
3610 * compute db_aglevel, db_agheight, db_width, db_agstart:
3611 * an ag is covered in aglevel dmapctl summary tree,
3612 * at agheight level height (from leaf) with agwidth number of nodes
3613 * each, which starts at agstart index node of the smmary tree node
3614 * array;
3615 */
3617 l2nl =
3622 i--) {
3625 }
3627 }
3630 /*
3631 * NAME: dbInitDmap()/ujfs_idmap_page()
3632 *
3633 * FUNCTION: initialize working/persistent bitmap of the dmap page
3634 * for the specified number of blocks:
3635 *
3636 * at entry, the bitmaps had been initialized as free (ZEROS);
3637 * The number of blocks will only account for the actually
3638 * existing blocks. Blocks which don't actually exist in
3639 * the aggregate will be marked as allocated (ONES);
3640 *
3641 * PARAMETERS:
3642 * dp - pointer to page of map
3643 * nblocks - number of blocks this page
3644 *
3645 * RETURNS: NONE
3646 */
3648 {
3651 /* starting block number within the dmap */
3662 }
3666 }
3668 /* word number containing start block number */
3671 /*
3672 * free the bits corresponding to the block range (ZEROS):
3673 * note: not all bits of the first and last words may be contained
3674 * within the block range.
3675 */
3677 /* number of bits preceding range to be freed in the word */
3679 /* number of bits to free in the word */
3682 /* is partial word to be freed ? */
3684 /* free (set to 0) from the bitmap word */
3690 /* skip the word freed */
3691 w++;
3693 /* free (set to 0) contiguous bitmap words */
3698 /* skip the words freed */
3701 }
3702 }
3704 /*
3705 * mark bits following the range to be freed (non-existing
3706 * blocks) as allocated (ONES)
3707 */
3712 /* the first word beyond the end of existing blocks */
3715 /* does nblocks fall on a 32-bit boundary ? */
3718 /* mark a partial word allocated */
3720 w++;
3721 }
3723 /* set the rest of the words in the page to allocated (ONES) */
3727 /*
3728 * init tree
3729 */
3730 initTree:
3732 }
3735 /*
3736 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3737 *
3738 * FUNCTION: initialize summary tree of the specified dmap:
3739 *
3740 * at entry, bitmap of the dmap has been initialized;
3741 *
3742 * PARAMETERS:
3743 * dp - dmap to complete
3744 * blkno - starting block number for this dmap
3745 * treemax - will be filled in with max free for this dmap
3746 *
3747 * RETURNS: max free string at the root of the tree
3748 */
3750 {
3755 /* init fixed info of tree */
3763 /* init each leaf from corresponding wmap word:
3764 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3765 * bitmap word are allocated.
3766 */
3771 /* build the dmap's binary buddy summary tree */
3773 }
3776 /*
3777 * NAME: dbInitTree()/ujfs_adjtree()
3778 *
3779 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3780 *
3781 * at entry, the leaves of the tree has been initialized
3782 * from corresponding bitmap word or root of summary tree
3783 * of the child control page;
3784 * configure binary buddy system at the leaf level, then
3785 * bubble up the values of the leaf nodes up the tree.
3786 *
3787 * PARAMETERS:
3788 * cp - Pointer to the root of the tree
3789 * l2leaves- Number of leaf nodes as a power of 2
3790 * l2min - Number of blocks that can be covered by a leaf
3791 * as a power of 2
3792 *
3793 * RETURNS: max free string at the root of the tree
3794 */
3796 {
3803 /* Determine the maximum free string possible for the leaves */
3806 /*
3807 * configure the leaf levevl into binary buddy system
3808 *
3809 * Try to combine buddies starting with a buddy size of 1
3810 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3811 * can be combined if both buddies have a maximum free of l2min;
3812 * the combination will result in the left-most buddy leaf having
3813 * a maximum free of l2min+1.
3814 * After processing all buddies for a given size, process buddies
3815 * at the next higher buddy size (i.e. current size * 2) and
3816 * the next maximum free (current free + 1).
3817 * This continues until the maximum possible buddy combination
3818 * yields maximum free.
3819 */
3822 /* get next buddy size == current buddy pair size */
3825 /* scan each adjacent buddy pair at current buddy size */
3829 /* coalesce if both adjacent buddies are max free */
3833 }
3834 }
3835 }
3837 /*
3838 * bubble summary information of leaves up the tree.
3839 *
3840 * Starting at the leaf node level, the four nodes described by
3841 * the higher level parent node are compared for a maximum free and
3842 * this maximum becomes the value of the parent node.
3843 * when all lower level nodes are processed in this fashion then
3844 * move up to the next level (parent becomes a lower level node) and
3845 * continue the process for that level.
3846 */
3850 /* get index of 1st node of parent level */
3853 /* set the value of the parent node as the maximum
3854 * of the four nodes of the current level.
3855 */
3859 }
3862 }
3865 /*
3866 * dbInitDmapCtl()
3867 *
3868 * function: initialize dmapctl page
3869 */
3880 /*
3881 * initialize the leaves of current level that were not covered
3882 * by the specified input block range (i.e. the leaves have no
3883 * low level dmapctl or dmap).
3884 */
3889 /* build the dmap's binary buddy summary tree */
3891 }
3894 /*
3895 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3896 *
3897 * FUNCTION: Determine log2(allocation group size) from aggregate size
3898 *
3899 * PARAMETERS:
3900 * nblocks - Number of blocks in aggregate
3901 *
3902 * RETURNS: log2(allocation group size) in aggregate blocks
3903 */
3905 {
3906 s64 sz;
3907 s64 m;
3913 /* round up aggregate size to power of 2 */
3918 }
3924 /* agsize = roundupSize/max_number_of_ag */
3926 }
3929 /*
3930 * NAME: dbMapFileSizeToMapSize()
3931 *
3932 * FUNCTION: compute number of blocks the block allocation map file
3933 * can cover from the map file size;
3934 *
3935 * RETURNS: Number of blocks which can be covered by this block map file;
3936 */
3938 /*
3939 * maximum number of map pages at each level including control pages
3940 */
3941 #define MAXL0PAGES (1 + LPERCTL)
3942 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
3943 #define MAXL2PAGES (1 + LPERCTL * MAXL1PAGES)
3945 /*
3946 * convert number of map pages to the zero origin top dmapctl level
3947 */
3948 #define BMAPPGTOLEV(npages) \
3949 (((npages) <= 3 + MAXL0PAGES) ? 0 : \
3950 ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
3953 {
3955 s64 nblocks;
3964 /* At each level, accumulate the number of dmap pages covered by
3965 * the number of full child levels below it;
3966 * repeat for the last incomplete child level.
3967 */
3970 /* skip higher level control pages above top level covered by map */
3974 factor =
3980 /* pages in last/incomplete child */
3982 /* skip incomplete child's level control page */
3983 npages--;
3984 }
3986 /* convert the number of dmaps into the number of blocks
3987 * which can be covered by the dmaps;
3988 */
3992 }