| blob | 68000a50ceb60610e796e184ba6384af47e1cb7e |
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>
28 /*
29 * SERIALIZATION of the Block Allocation Map.
30 *
31 * the working state of the block allocation map is accessed in
32 * two directions:
33 *
34 * 1) allocation and free requests that start at the dmap
35 * level and move up through the dmap control pages (i.e.
36 * the vast majority of requests).
37 *
38 * 2) allocation requests that start at dmap control page
39 * level and work down towards the dmaps.
40 *
41 * the serialization scheme used here is as follows.
42 *
43 * requests which start at the bottom are serialized against each
44 * other through buffers and each requests holds onto its buffers
45 * as it works it way up from a single dmap to the required level
46 * of dmap control page.
47 * requests that start at the top are serialized against each other
48 * and request that start from the bottom by the multiple read/single
49 * write inode lock of the bmap inode. requests starting at the top
50 * take this lock in write mode while request starting at the bottom
51 * take the lock in read mode. a single top-down request may proceed
52 * exclusively while multiple bottoms-up requests may proceed
53 * simultaneously (under the protection of busy buffers).
54 *
55 * in addition to information found in dmaps and dmap control pages,
56 * the working state of the block allocation map also includes read/
57 * write information maintained in the bmap descriptor (i.e. total
58 * free block count, allocation group level free block counts).
59 * a single exclusive lock (BMAP_LOCK) is used to guard this information
60 * in the face of multiple-bottoms up requests.
61 * (lock ordering: IREAD_LOCK, BMAP_LOCK);
62 *
63 * accesses to the persistent state of the block allocation map (limited
64 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
65 */
67 #define BMAP_LOCK_INIT(bmp) init_MUTEX(&bmp->db_bmaplock)
68 #define BMAP_LOCK(bmp) down(&bmp->db_bmaplock)
69 #define BMAP_UNLOCK(bmp) up(&bmp->db_bmaplock)
71 /*
72 * forward references
73 */
120 /*
121 * buddy table
122 *
123 * table used for determining buddy sizes within characters of
124 * dmap bitmap words. the characters themselves serve as indexes
125 * into the table, with the table elements yielding the maximum
126 * binary buddy of free bits within the character.
127 */
145 };
148 /*
149 * NAME: dbMount()
150 *
151 * FUNCTION: initializate the block allocation map.
152 *
153 * memory is allocated for the in-core bmap descriptor and
154 * the in-core descriptor is initialized from disk.
155 *
156 * PARAMETERS:
157 * ipbmap - pointer to in-core inode for the block map.
158 *
159 * RETURN VALUES:
160 * 0 - success
161 * -ENOMEM - insufficient memory
162 * -EIO - i/o error
163 */
165 {
171 /*
172 * allocate/initialize the in-memory bmap descriptor
173 */
174 /* allocate memory for the in-memory bmap descriptor */
179 /* read the on-disk bmap descriptor. */
186 }
188 /* copy the on-disk bmap descriptor to its in-memory version. */
207 /* release the buffer. */
210 /* bind the bmap inode and the bmap descriptor to each other. */
216 /*
217 * allocate/initialize the bmap lock
218 */
222 }
225 /*
226 * NAME: dbUnmount()
227 *
228 * FUNCTION: terminate the block allocation map in preparation for
229 * file system unmount.
230 *
231 * the in-core bmap descriptor is written to disk and
232 * the memory for this descriptor is freed.
233 *
234 * PARAMETERS:
235 * ipbmap - pointer to in-core inode for the block map.
236 *
237 * RETURN VALUES:
238 * 0 - success
239 * -EIO - i/o error
240 */
242 {
248 /*
249 * Invalidate the page cache buffers
250 */
253 /* free the memory for the in-memory bmap. */
257 }
259 /*
260 * dbSync()
261 */
263 {
269 /*
270 * write bmap global control page
271 */
272 /* get the buffer for the on-disk bmap descriptor. */
279 }
280 /* copy the in-memory version of the bmap to the on-disk version */
299 /* write the buffer */
302 /*
303 * write out dirty pages of bmap
304 */
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 */
537 /* inherit older/smaller lsn */
543 /* move bp after tblock in logsync list */
545 }
547 /* inherit younger/larger clsn */
557 /* insert bp after tblock in logsync list */
565 }
566 }
568 /* write the last buffer. */
571 }
574 }
577 /*
578 * NAME: dbNextAG()
579 *
580 * FUNCTION: find the preferred allocation group for new allocations.
581 *
582 * Within the allocation groups, we maintain a preferred
583 * allocation group which consists of a group with at least
584 * average free space. It is the preferred group that we target
585 * new inode allocation towards. The tie-in between inode
586 * allocation and block allocation occurs as we allocate the
587 * first (data) block of an inode and specify the inode (block)
588 * as the allocation hint for this block.
589 *
590 * We try to avoid having more than one open file growing in
591 * an allocation group, as this will lead to fragmentation.
592 * This differs from the old OS/2 method of trying to keep
593 * empty ags around for large allocations.
594 *
595 * PARAMETERS:
596 * ipbmap - pointer to in-core inode for the block map.
597 *
598 * RETURN VALUES:
599 * the preferred allocation group number.
600 */
602 {
603 s64 avgfree;
612 /* determine the average number of free blocks within the ags. */
615 /*
616 * if the current preferred ag does not have an active allocator
617 * and has at least average freespace, return it
618 */
624 /* From the last preferred ag, find the next one with at least
625 * average free space.
626 */
632 /* open file is currently growing in this ag */
635 /* Return this one */
639 /* Less than avg. freespace, but best so far */
642 }
643 }
645 /*
646 * If no inactive ag was found with average freespace, use the
647 * next best
648 */
651 /* else leave db_agpref unchanged */
652 unlock:
655 /* return the preferred group.
656 */
658 }
660 /*
661 * NAME: dbAlloc()
662 *
663 * FUNCTION: attempt to allocate a specified number of contiguous free
664 * blocks from the working allocation block map.
665 *
666 * the block allocation policy uses hints and a multi-step
667 * approach.
668 *
669 * for allocation requests smaller than the number of blocks
670 * per dmap, we first try to allocate the new blocks
671 * immediately following the hint. if these blocks are not
672 * available, we try to allocate blocks near the hint. if
673 * no blocks near the hint are available, we next try to
674 * allocate within the same dmap as contains the hint.
675 *
676 * if no blocks are available in the dmap or the allocation
677 * request is larger than the dmap size, we try to allocate
678 * within the same allocation group as contains the hint. if
679 * this does not succeed, we finally try to allocate anywhere
680 * within the aggregate.
681 *
682 * we also try to allocate anywhere within the aggregate for
683 * for allocation requests larger than the allocation group
684 * size or requests that specify no hint value.
685 *
686 * PARAMETERS:
687 * ip - pointer to in-core inode;
688 * hint - allocation hint.
689 * nblocks - number of contiguous blocks in the range.
690 * results - on successful return, set to the starting block number
691 * of the newly allocated contiguous range.
692 *
693 * RETURN VALUES:
694 * 0 - success
695 * -ENOSPC - insufficient disk resources
696 * -EIO - i/o error
697 */
699 {
707 s64 mapSize;
710 /* assert that nblocks is valid */
713 #ifdef _STILL_TO_PORT
714 /* DASD limit check F226941 */
719 /* get the log2 number of blocks to be allocated.
720 * if the number of blocks is not a log2 multiple,
721 * it will be rounded up to the next log2 multiple.
722 */
727 //retry: /* serialize w.r.t.extendfs() */
730 /* the hint should be within the map */
734 }
736 /* if the number of blocks to be allocated is greater than the
737 * allocation group size, try to allocate anywhere.
738 */
745 }
747 /*
748 * If no hint, let dbNextAG recommend an allocation group
749 */
753 /* we would like to allocate close to the hint. adjust the
754 * hint to the block following the hint since the allocators
755 * will start looking for free space starting at this point.
756 */
764 /* check if blkno crosses over into a new allocation group.
765 * if so, check if we should allow allocations within this
766 * allocation group.
767 */
769 /* check if the AG is currenly being written to.
770 * if so, call dbNextAG() to find a non-busy
771 * AG with sufficient free space.
772 */
776 /* check if the allocation request size can be satisfied from a
777 * single dmap. if so, try to allocate from the dmap containing
778 * the hint using a tiered strategy.
779 */
783 /* get the buffer for the dmap containing the hint.
784 */
793 /* first, try to satisfy the allocation request with the
794 * blocks beginning at the hint.
795 */
801 }
805 }
810 /*
811 * Someone else is writing in this allocation
812 * group. To avoid fragmenting, try another ag
813 */
817 }
819 /* next, try to satisfy the allocation request with blocks
820 * near the hint.
821 */
830 }
832 /* try to satisfy the allocation request with blocks within
833 * the same dmap as the hint.
834 */
842 }
846 }
848 /* try to satisfy the allocation request with blocks within
849 * the same allocation group as the hint.
850 */
858 pref_ag:
859 /*
860 * Let dbNextAG recommend a preferred allocation group
861 */
865 /* Try to allocate within this allocation group. if that fails, try to
866 * allocate anywhere in the map.
867 */
871 write_unlock:
876 read_unlock:
880 }
882 #ifdef _NOTYET
883 /*
884 * NAME: dbAllocExact()
885 *
886 * FUNCTION: try to allocate the requested extent;
887 *
888 * PARAMETERS:
889 * ip - pointer to in-core inode;
890 * blkno - extent address;
891 * nblocks - extent length;
892 *
893 * RETURN VALUES:
894 * 0 - success
895 * -ENOSPC - insufficient disk resources
896 * -EIO - i/o error
897 */
899 {
904 s64 lblkno;
909 /*
910 * validate extent request:
911 *
912 * note: defragfs policy:
913 * max 64 blocks will be moved.
914 * allocation request size must be satisfied from a single dmap.
915 */
919 }
922 /* the free space is no longer available */
925 }
927 /* read in the dmap covering the extent */
933 }
936 /* try to allocate the requested extent */
947 }
950 /*
951 * NAME: dbReAlloc()
952 *
953 * FUNCTION: attempt to extend a current allocation by a specified
954 * number of blocks.
955 *
956 * this routine attempts to satisfy the allocation request
957 * by first trying to extend the existing allocation in
958 * place by allocating the additional blocks as the blocks
959 * immediately following the current allocation. if these
960 * blocks are not available, this routine will attempt to
961 * allocate a new set of contiguous blocks large enough
962 * to cover the existing allocation plus the additional
963 * number of blocks required.
964 *
965 * PARAMETERS:
966 * ip - pointer to in-core inode requiring allocation.
967 * blkno - starting block of the current allocation.
968 * nblocks - number of contiguous blocks within the current
969 * allocation.
970 * addnblocks - number of blocks to add to the allocation.
971 * results - on successful return, set to the starting block number
972 * of the existing allocation if the existing allocation
973 * was extended in place or to a newly allocated contiguous
974 * range if the existing allocation could not be extended
975 * in place.
976 *
977 * RETURN VALUES:
978 * 0 - success
979 * -ENOSPC - insufficient disk resources
980 * -EIO - i/o error
981 */
982 int
985 {
988 /* try to extend the allocation in place.
989 */
996 }
998 /* could not extend the allocation in place, so allocate a
999 * new set of blocks for the entire request (i.e. try to get
1000 * a range of contiguous blocks large enough to cover the
1001 * existing allocation plus the additional blocks.)
1002 */
1005 }
1008 /*
1009 * NAME: dbExtend()
1010 *
1011 * FUNCTION: attempt to extend a current allocation by a specified
1012 * number of blocks.
1013 *
1014 * this routine attempts to satisfy the allocation request
1015 * by first trying to extend the existing allocation in
1016 * place by allocating the additional blocks as the blocks
1017 * immediately following the current allocation.
1018 *
1019 * PARAMETERS:
1020 * ip - pointer to in-core inode requiring allocation.
1021 * blkno - starting block of the current allocation.
1022 * nblocks - number of contiguous blocks within the current
1023 * allocation.
1024 * addnblocks - number of blocks to add to the allocation.
1025 *
1026 * RETURN VALUES:
1027 * 0 - success
1028 * -ENOSPC - insufficient disk resources
1029 * -EIO - i/o error
1030 */
1032 {
1035 uint rel_block;
1042 /*
1043 * We don't want a non-aligned extent to cross a page boundary
1044 */
1049 /* get the last block of the current allocation */
1052 /* determine the block number of the block following
1053 * the existing allocation.
1054 */
1059 /* better be within the file system */
1066 }
1068 /* we'll attempt to extend the current allocation in place by
1069 * allocating the additional blocks as the blocks immediately
1070 * following the current allocation. we only try to extend the
1071 * current allocation in place if the number of additional blocks
1072 * can fit into a dmap, the last block of the current allocation
1073 * is not the last block of the file system, and the start of the
1074 * inplace extension is not on an allocation group boundary.
1075 */
1080 }
1082 /* get the buffer for the dmap containing the first block
1083 * of the extension.
1084 */
1090 }
1094 /* try to allocate the blocks immediately following the
1095 * current allocation.
1096 */
1101 /* were we successful ? */
1104 else
1105 /* we were not successful */
1110 }
1113 /*
1114 * NAME: dbAllocNext()
1115 *
1116 * FUNCTION: attempt to allocate the blocks of the specified block
1117 * range within a dmap.
1118 *
1119 * PARAMETERS:
1120 * bmp - pointer to bmap descriptor
1121 * dp - pointer to dmap.
1122 * blkno - starting block number of the range.
1123 * nblocks - number of contiguous free blocks of the range.
1124 *
1125 * RETURN VALUES:
1126 * 0 - success
1127 * -ENOSPC - insufficient disk resources
1128 * -EIO - i/o error
1129 *
1130 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1131 */
1134 {
1138 u32 mask;
1144 }
1146 /* pick up a pointer to the leaves of the dmap tree.
1147 */
1150 /* determine the bit number and word within the dmap of the
1151 * starting block.
1152 */
1156 /* check if the specified block range is contained within
1157 * this dmap.
1158 */
1162 /* check if the starting leaf indicates that anything
1163 * is free.
1164 */
1168 /* check the dmaps words corresponding to block range to see
1169 * if the block range is free. not all bits of the first and
1170 * last words may be contained within the block range. if this
1171 * is the case, we'll work against those words (i.e. partial first
1172 * and/or last) on an individual basis (a single pass) and examine
1173 * the actual bits to determine if they are free. a single pass
1174 * will be used for all dmap words fully contained within the
1175 * specified range. within this pass, the leaves of the dmap
1176 * tree will be examined to determine if the blocks are free. a
1177 * single leaf may describe the free space of multiple dmap
1178 * words, so we may visit only a subset of the actual leaves
1179 * corresponding to the dmap words of the block range.
1180 */
1182 /* determine the bit number within the word and
1183 * the number of bits within the word.
1184 */
1188 /* check if only part of the word is to be examined.
1189 */
1191 /* check if the bits are free.
1192 */
1199 /* one or more dmap words are fully contained
1200 * within the block range. determine how many
1201 * words and how many bits.
1202 */
1206 /* now examine the appropriate leaves to determine
1207 * if the blocks are free.
1208 */
1210 /* does the leaf describe any free space ?
1211 */
1215 /* determine the l2 number of bits provided
1216 * by this leaf.
1217 */
1218 l2size =
1221 /* determine how many words were handled.
1222 */
1227 }
1228 }
1229 }
1231 /* allocate the blocks.
1232 */
1234 }
1237 /*
1238 * NAME: dbAllocNear()
1239 *
1240 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1241 * a specified block (hint) within a dmap.
1242 *
1243 * starting with the dmap leaf that covers the hint, we'll
1244 * check the next four contiguous leaves for sufficient free
1245 * space. if sufficient free space is found, we'll allocate
1246 * the desired free space.
1247 *
1248 * PARAMETERS:
1249 * bmp - pointer to bmap descriptor
1250 * dp - pointer to dmap.
1251 * blkno - block number to allocate near.
1252 * nblocks - actual number of contiguous free blocks desired.
1253 * l2nb - log2 number of contiguous free blocks desired.
1254 * results - on successful return, set to the starting block number
1255 * of the newly allocated range.
1256 *
1257 * RETURN VALUES:
1258 * 0 - success
1259 * -ENOSPC - insufficient disk resources
1260 * -EIO - i/o error
1261 *
1262 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1263 */
1264 static int
1267 {
1275 }
1279 /* determine the word within the dmap that holds the hint
1280 * (i.e. blkno). also, determine the last word in the dmap
1281 * that we'll include in our examination.
1282 */
1286 /* examine the leaves for sufficient free space.
1287 */
1289 /* does the leaf describe sufficient free space ?
1290 */
1294 /* determine the block number within the file system
1295 * of the first block described by this dmap word.
1296 */
1299 /* if not all bits of the dmap word are free, get the
1300 * starting bit number within the dmap word of the required
1301 * string of free bits and adjust the block number with the
1302 * value.
1303 */
1305 blkno +=
1308 /* allocate the blocks.
1309 */
1314 }
1317 }
1320 /*
1321 * NAME: dbAllocAG()
1322 *
1323 * FUNCTION: attempt to allocate the specified number of contiguous
1324 * free blocks within the specified allocation group.
1325 *
1326 * unless the allocation group size is equal to the number
1327 * of blocks per dmap, the dmap control pages will be used to
1328 * find the required free space, if available. we start the
1329 * search at the highest dmap control page level which
1330 * distinctly describes the allocation group's free space
1331 * (i.e. the highest level at which the allocation group's
1332 * free space is not mixed in with that of any other group).
1333 * in addition, we start the search within this level at a
1334 * height of the dmapctl dmtree at which the nodes distinctly
1335 * describe the allocation group's free space. at this height,
1336 * the allocation group's free space may be represented by 1
1337 * or two sub-trees, depending on the allocation group size.
1338 * we search the top nodes of these subtrees left to right for
1339 * sufficient free space. if sufficient free space is found,
1340 * the subtree is searched to find the leftmost leaf that
1341 * has free space. once we have made it to the leaf, we
1342 * move the search to the next lower level dmap control page
1343 * corresponding to this leaf. we continue down the dmap control
1344 * pages until we find the dmap that contains or starts the
1345 * sufficient free space and we allocate at this dmap.
1346 *
1347 * if the allocation group size is equal to the dmap size,
1348 * we'll start at the dmap corresponding to the allocation
1349 * group and attempt the allocation at this level.
1350 *
1351 * the dmap control page search is also not performed if the
1352 * allocation group is completely free and we go to the first
1353 * dmap of the allocation group to do the allocation. this is
1354 * done because the allocation group may be part (not the first
1355 * part) of a larger binary buddy system, causing the dmap
1356 * control pages to indicate no free space (NOFREE) within
1357 * the allocation group.
1358 *
1359 * PARAMETERS:
1360 * bmp - pointer to bmap descriptor
1361 * agno - allocation group number.
1362 * nblocks - actual number of contiguous free blocks desired.
1363 * l2nb - log2 number of contiguous free blocks desired.
1364 * results - on successful return, set to the starting block number
1365 * of the newly allocated range.
1366 *
1367 * RETURN VALUES:
1368 * 0 - success
1369 * -ENOSPC - insufficient disk resources
1370 * -EIO - i/o error
1371 *
1372 * note: IWRITE_LOCK(ipmap) held on entry/exit;
1373 */
1374 static int
1376 {
1383 /* allocation request should not be for more than the
1384 * allocation group size.
1385 */
1388 "dbAllocAG: allocation request is larger than the "
1391 }
1393 /* determine the starting block number of the allocation
1394 * group.
1395 */
1398 /* check if the allocation group size is the minimum allocation
1399 * group size or if the allocation group is completely free. if
1400 * the allocation group size is the minimum size of BPERDMAP (i.e.
1401 * 1 dmap), there is no need to search the dmap control page (below)
1402 * that fully describes the allocation group since the allocation
1403 * group is already fully described by a dmap. in this case, we
1404 * just call dbAllocCtl() to search the dmap tree and allocate the
1405 * required space if available.
1406 *
1407 * if the allocation group is completely free, dbAllocCtl() is
1408 * also called to allocate the required space. this is done for
1409 * two reasons. first, it makes no sense searching the dmap control
1410 * pages for free space when we know that free space exists. second,
1411 * the dmap control pages may indicate that the allocation group
1412 * has no free space if the allocation group is part (not the first
1413 * part) of a larger binary buddy system.
1414 */
1425 }
1427 }
1429 /* the buffer for the dmap control page that fully describes the
1430 * allocation group.
1431 */
1444 }
1446 /* search the subtree(s) of the dmap control page that describes
1447 * the allocation group, looking for sufficient free space. to begin,
1448 * determine how many allocation groups are represented in a dmap
1449 * control page at the control page level (i.e. L0, L1, L2) that
1450 * fully describes an allocation group. next, determine the starting
1451 * tree index of this allocation group within the control page.
1452 */
1453 agperlev =
1457 /* dmap control page trees fan-out by 4 and a single allocation
1458 * group may be described by 1 or 2 subtrees within the ag level
1459 * dmap control page, depending upon the ag size. examine the ag's
1460 * subtrees for sufficient free space, starting with the leftmost
1461 * subtree.
1462 */
1464 /* is there sufficient free space ?
1465 */
1469 /* sufficient free space found in a subtree. now search down
1470 * the subtree to find the leftmost leaf that describes this
1471 * free space.
1472 */
1478 }
1479 }
1485 }
1486 }
1488 /* determine the block number within the file system
1489 * that corresponds to this leaf.
1490 */
1498 blkno +=
1501 /* release the buffer in preparation for going down
1502 * the next level of dmap control pages.
1503 */
1506 /* check if we need to continue to search down the lower
1507 * level dmap control pages. we need to if the number of
1508 * blocks required is less than maximum number of blocks
1509 * described at the next lower level.
1510 */
1513 /* search the lower level dmap control pages to get
1514 * the starting block number of the the dmap that
1515 * contains or starts off the free space.
1516 */
1522 "dbAllocAG: control page "
1525 }
1527 }
1528 }
1530 /* allocate the blocks.
1531 */
1537 }
1539 }
1541 /* no space in the allocation group. release the buffer and
1542 * return -ENOSPC.
1543 */
1547 }
1550 /*
1551 * NAME: dbAllocAny()
1552 *
1553 * FUNCTION: attempt to allocate the specified number of contiguous
1554 * free blocks anywhere in the file system.
1555 *
1556 * dbAllocAny() attempts to find the sufficient free space by
1557 * searching down the dmap control pages, starting with the
1558 * highest level (i.e. L0, L1, L2) control page. if free space
1559 * large enough to satisfy the desired free space is found, the
1560 * desired free space is allocated.
1561 *
1562 * PARAMETERS:
1563 * bmp - pointer to bmap descriptor
1564 * nblocks - actual number of contiguous free blocks desired.
1565 * l2nb - log2 number of contiguous free blocks desired.
1566 * results - on successful return, set to the starting block number
1567 * of the newly allocated range.
1568 *
1569 * RETURN VALUES:
1570 * 0 - success
1571 * -ENOSPC - insufficient disk resources
1572 * -EIO - i/o error
1573 *
1574 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1575 */
1577 {
1581 /* starting with the top level dmap control page, search
1582 * down the dmap control levels for sufficient free space.
1583 * if free space is found, dbFindCtl() returns the starting
1584 * block number of the dmap that contains or starts off the
1585 * range of free space.
1586 */
1590 /* allocate the blocks.
1591 */
1597 }
1599 }
1602 /*
1603 * NAME: dbFindCtl()
1604 *
1605 * FUNCTION: starting at a specified dmap control page level and block
1606 * number, search down the dmap control levels for a range of
1607 * contiguous free blocks large enough to satisfy an allocation
1608 * request for the specified number of free blocks.
1609 *
1610 * if sufficient contiguous free blocks are found, this routine
1611 * returns the starting block number within a dmap page that
1612 * contains or starts a range of contiqious free blocks that
1613 * is sufficient in size.
1614 *
1615 * PARAMETERS:
1616 * bmp - pointer to bmap descriptor
1617 * level - starting dmap control page level.
1618 * l2nb - log2 number of contiguous free blocks desired.
1619 * *blkno - on entry, starting block number for conducting the search.
1620 * on successful return, the first block within a dmap page
1621 * that contains or starts a range of contiguous free blocks.
1622 *
1623 * RETURN VALUES:
1624 * 0 - success
1625 * -ENOSPC - insufficient disk resources
1626 * -EIO - i/o error
1627 *
1628 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1629 */
1631 {
1638 /* starting at the specified dmap control page level and block
1639 * number, search down the dmap control levels for the starting
1640 * block number of a dmap page that contains or starts off
1641 * sufficient free blocks.
1642 */
1644 /* get the buffer of the dmap control page for the block
1645 * number and level (i.e. L0, L1, L2).
1646 */
1659 }
1661 /* search the tree within the dmap control page for
1662 * sufficent free space. if sufficient free space is found,
1663 * dbFindLeaf() returns the index of the leaf at which
1664 * free space was found.
1665 */
1668 /* release the buffer.
1669 */
1672 /* space found ?
1673 */
1679 }
1681 }
1683 /* adjust the block number to reflect the location within
1684 * the dmap control page (i.e. the leaf) at which free
1685 * space was found.
1686 */
1689 /* we stop the search at this dmap control page level if
1690 * the number of blocks required is greater than or equal
1691 * to the maximum number of blocks described at the next
1692 * (lower) level.
1693 */
1696 }
1700 }
1703 /*
1704 * NAME: dbAllocCtl()
1705 *
1706 * FUNCTION: attempt to allocate a specified number of contiguous
1707 * blocks starting within a specific dmap.
1708 *
1709 * this routine is called by higher level routines that search
1710 * the dmap control pages above the actual dmaps for contiguous
1711 * free space. the result of successful searches by these
1712 * routines are the starting block numbers within dmaps, with
1713 * the dmaps themselves containing the desired contiguous free
1714 * space or starting a contiguous free space of desired size
1715 * that is made up of the blocks of one or more dmaps. these
1716 * calls should not fail due to insufficent resources.
1717 *
1718 * this routine is called in some cases where it is not known
1719 * whether it will fail due to insufficient resources. more
1720 * specifically, this occurs when allocating from an allocation
1721 * group whose size is equal to the number of blocks per dmap.
1722 * in this case, the dmap control pages are not examined prior
1723 * to calling this routine (to save pathlength) and the call
1724 * might fail.
1725 *
1726 * for a request size that fits within a dmap, this routine relies
1727 * upon the dmap's dmtree to find the requested contiguous free
1728 * space. for request sizes that are larger than a dmap, the
1729 * requested free space will start at the first block of the
1730 * first dmap (i.e. blkno).
1731 *
1732 * PARAMETERS:
1733 * bmp - pointer to bmap descriptor
1734 * nblocks - actual number of contiguous free blocks to allocate.
1735 * l2nb - log2 number of contiguous free blocks to allocate.
1736 * blkno - starting block number of the dmap to start the allocation
1737 * from.
1738 * results - on successful return, set to the starting block number
1739 * of the newly allocated range.
1740 *
1741 * RETURN VALUES:
1742 * 0 - success
1743 * -ENOSPC - insufficient disk resources
1744 * -EIO - i/o error
1745 *
1746 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1747 */
1748 static int
1750 {
1756 /* check if the allocation request is confined to a single dmap.
1757 */
1759 /* get the buffer for the dmap.
1760 */
1767 /* try to allocate the blocks.
1768 */
1776 }
1778 /* allocation request involving multiple dmaps. it must start on
1779 * a dmap boundary.
1780 */
1783 /* allocate the blocks dmap by dmap.
1784 */
1786 /* get the buffer for the dmap.
1787 */
1793 }
1796 /* the dmap better be all free.
1797 */
1804 }
1806 /* determine how many blocks to allocate from this dmap.
1807 */
1810 /* allocate the blocks from the dmap.
1811 */
1815 }
1817 /* write the buffer.
1818 */
1820 }
1822 /* set the results (starting block number) and return.
1823 */
1827 /* something failed in handling an allocation request involving
1828 * multiple dmaps. we'll try to clean up by backing out any
1829 * allocation that has already happened for this request. if
1830 * we fail in backing out the allocation, we'll mark the file
1831 * system to indicate that blocks have been leaked.
1832 */
1833 backout:
1835 /* try to backout the allocations dmap by dmap.
1836 */
1839 /* get the buffer for this dmap.
1840 */
1844 /* could not back out. mark the file system
1845 * to indicate that we have leaked blocks.
1846 */
1850 }
1853 /* free the blocks is this dmap.
1854 */
1856 /* could not back out. mark the file system
1857 * to indicate that we have leaked blocks.
1858 */
1863 }
1865 /* write the buffer.
1866 */
1868 }
1871 }
1874 /*
1875 * NAME: dbAllocDmapLev()
1876 *
1877 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1878 * from a specified dmap.
1879 *
1880 * this routine checks if the contiguous blocks are available.
1881 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1882 * returned.
1883 *
1884 * PARAMETERS:
1885 * mp - pointer to bmap descriptor
1886 * dp - pointer to dmap to attempt to allocate blocks from.
1887 * l2nb - log2 number of contiguous block desired.
1888 * nblocks - actual number of contiguous block desired.
1889 * results - on successful return, set to the starting block number
1890 * of the newly allocated range.
1891 *
1892 * RETURN VALUES:
1893 * 0 - success
1894 * -ENOSPC - insufficient disk resources
1895 * -EIO - i/o error
1896 *
1897 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1898 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1899 */
1900 static int
1903 {
1904 s64 blkno;
1907 /* can't be more than a dmaps worth of blocks */
1910 /* search the tree within the dmap page for sufficient
1911 * free space. if sufficient free space is found, dbFindLeaf()
1912 * returns the index of the leaf at which free space was found.
1913 */
1917 /* determine the block number within the file system corresponding
1918 * to the leaf at which free space was found.
1919 */
1922 /* if not all bits of the dmap word are free, get the starting
1923 * bit number within the dmap word of the required string of free
1924 * bits and adjust the block number with this value.
1925 */
1929 /* allocate the blocks */
1934 }
1937 /*
1938 * NAME: dbAllocDmap()
1939 *
1940 * FUNCTION: adjust the disk allocation map to reflect the allocation
1941 * of a specified block range within a dmap.
1942 *
1943 * this routine allocates the specified blocks from the dmap
1944 * through a call to dbAllocBits(). if the allocation of the
1945 * block range causes the maximum string of free blocks within
1946 * the dmap to change (i.e. the value of the root of the dmap's
1947 * dmtree), this routine will cause this change to be reflected
1948 * up through the appropriate levels of the dmap control pages
1949 * by a call to dbAdjCtl() for the L0 dmap control page that
1950 * covers this dmap.
1951 *
1952 * PARAMETERS:
1953 * bmp - pointer to bmap descriptor
1954 * dp - pointer to dmap to allocate the block range from.
1955 * blkno - starting block number of the block to be allocated.
1956 * nblocks - number of blocks to be allocated.
1957 *
1958 * RETURN VALUES:
1959 * 0 - success
1960 * -EIO - i/o error
1961 *
1962 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
1963 */
1966 {
1967 s8 oldroot;
1970 /* save the current value of the root (i.e. maximum free string)
1971 * of the dmap tree.
1972 */
1975 /* allocate the specified (blocks) bits */
1978 /* if the root has not changed, done. */
1982 /* root changed. bubble the change up to the dmap control pages.
1983 * if the adjustment of the upper level control pages fails,
1984 * backout the bit allocation (thus making everything consistent).
1985 */
1990 }
1993 /*
1994 * NAME: dbFreeDmap()
1995 *
1996 * FUNCTION: adjust the disk allocation map to reflect the allocation
1997 * of a specified block range within a dmap.
1998 *
1999 * this routine frees the specified blocks from the dmap through
2000 * a call to dbFreeBits(). if the deallocation of the block range
2001 * causes the maximum string of free blocks within the dmap to
2002 * change (i.e. the value of the root of the dmap's dmtree), this
2003 * routine will cause this change to be reflected up through the
2004 * appropriate levels of the dmap control pages by a call to
2005 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
2006 *
2007 * PARAMETERS:
2008 * bmp - pointer to bmap descriptor
2009 * dp - pointer to dmap to free the block range from.
2010 * blkno - starting block number of the block to be freed.
2011 * nblocks - number of blocks to be freed.
2012 *
2013 * RETURN VALUES:
2014 * 0 - success
2015 * -EIO - i/o error
2016 *
2017 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2018 */
2021 {
2022 s8 oldroot;
2025 /* save the current value of the root (i.e. maximum free string)
2026 * of the dmap tree.
2027 */
2030 /* free the specified (blocks) bits */
2033 /* if error or the root has not changed, done. */
2037 /* root changed. bubble the change up to the dmap control pages.
2038 * if the adjustment of the upper level control pages fails,
2039 * backout the deallocation.
2040 */
2044 /* as part of backing out the deallocation, we will have
2045 * to back split the dmap tree if the deallocation caused
2046 * the freed blocks to become part of a larger binary buddy
2047 * system.
2048 */
2053 }
2056 }
2059 /*
2060 * NAME: dbAllocBits()
2061 *
2062 * FUNCTION: allocate a specified block range from a dmap.
2063 *
2064 * this routine updates the dmap to reflect the working
2065 * state allocation of the specified block range. it directly
2066 * updates the bits of the working map and causes the adjustment
2067 * of the binary buddy system described by the dmap's dmtree
2068 * leaves to reflect the bits allocated. it also causes the
2069 * dmap's dmtree, as a whole, to reflect the allocated range.
2070 *
2071 * PARAMETERS:
2072 * bmp - pointer to bmap descriptor
2073 * dp - pointer to dmap to allocate bits from.
2074 * blkno - starting block number of the bits to be allocated.
2075 * nblocks - number of bits to be allocated.
2076 *
2077 * RETURN VALUES: none
2078 *
2079 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2080 */
2083 {
2089 /* pick up a pointer to the leaves of the dmap tree */
2092 /* determine the bit number and word within the dmap of the
2093 * starting block.
2094 */
2098 /* block range better be within the dmap */
2101 /* allocate the bits of the dmap's words corresponding to the block
2102 * range. not all bits of the first and last words may be contained
2103 * within the block range. if this is the case, we'll work against
2104 * those words (i.e. partial first and/or last) on an individual basis
2105 * (a single pass), allocating the bits of interest by hand and
2106 * updating the leaf corresponding to the dmap word. a single pass
2107 * will be used for all dmap words fully contained within the
2108 * specified range. within this pass, the bits of all fully contained
2109 * dmap words will be marked as free in a single shot and the leaves
2110 * will be updated. a single leaf may describe the free space of
2111 * multiple dmap words, so we may update only a subset of the actual
2112 * leaves corresponding to the dmap words of the block range.
2113 */
2115 /* determine the bit number within the word and
2116 * the number of bits within the word.
2117 */
2121 /* check if only part of a word is to be allocated.
2122 */
2124 /* allocate (set to 1) the appropriate bits within
2125 * this dmap word.
2126 */
2130 /* update the leaf for this dmap word. in addition
2131 * to setting the leaf value to the binary buddy max
2132 * of the updated dmap word, dbSplit() will split
2133 * the binary system of the leaves if need be.
2134 */
2140 /* one or more dmap words are fully contained
2141 * within the block range. determine how many
2142 * words and allocate (set to 1) the bits of these
2143 * words.
2144 */
2148 /* determine how many bits.
2149 */
2152 /* now update the appropriate leaves to reflect
2153 * the allocated words.
2154 */
2158 "dbAllocBits: leaf page "
2161 }
2163 /* determine what the leaf value should be
2164 * updated to as the minimum of the l2 number
2165 * of bits being allocated and the l2 number
2166 * of bits currently described by this leaf.
2167 */
2170 /* update the leaf to reflect the allocation.
2171 * in addition to setting the leaf value to
2172 * NOFREE, dbSplit() will split the binary
2173 * system of the leaves to reflect the current
2174 * allocation (size).
2175 */
2178 /* get the number of dmap words handled */
2181 }
2182 }
2183 }
2185 /* update the free count for this dmap */
2190 /* if this allocation group is completely free,
2191 * update the maximum allocation group number if this allocation
2192 * group is the new max.
2193 */
2198 /* update the free count for the allocation group and map */
2203 }
2206 /*
2207 * NAME: dbFreeBits()
2208 *
2209 * FUNCTION: free a specified block range from a dmap.
2210 *
2211 * this routine updates the dmap to reflect the working
2212 * state allocation of the specified block range. it directly
2213 * updates the bits of the working map and causes the adjustment
2214 * of the binary buddy system described by the dmap's dmtree
2215 * leaves to reflect the bits freed. it also causes the dmap's
2216 * dmtree, as a whole, to reflect the deallocated range.
2217 *
2218 * PARAMETERS:
2219 * bmp - pointer to bmap descriptor
2220 * dp - pointer to dmap to free bits from.
2221 * blkno - starting block number of the bits to be freed.
2222 * nblocks - number of bits to be freed.
2223 *
2224 * RETURN VALUES: 0 for success
2225 *
2226 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2227 */
2230 {
2236 /* determine the bit number and word within the dmap of the
2237 * starting block.
2238 */
2242 /* block range better be within the dmap.
2243 */
2246 /* free the bits of the dmaps words corresponding to the block range.
2247 * not all bits of the first and last words may be contained within
2248 * the block range. if this is the case, we'll work against those
2249 * words (i.e. partial first and/or last) on an individual basis
2250 * (a single pass), freeing the bits of interest by hand and updating
2251 * the leaf corresponding to the dmap word. a single pass will be used
2252 * for all dmap words fully contained within the specified range.
2253 * within this pass, the bits of all fully contained dmap words will
2254 * be marked as free in a single shot and the leaves will be updated. a
2255 * single leaf may describe the free space of multiple dmap words,
2256 * so we may update only a subset of the actual leaves corresponding
2257 * to the dmap words of the block range.
2258 *
2259 * dbJoin() is used to update leaf values and will join the binary
2260 * buddy system of the leaves if the new leaf values indicate this
2261 * should be done.
2262 */
2264 /* determine the bit number within the word and
2265 * the number of bits within the word.
2266 */
2270 /* check if only part of a word is to be freed.
2271 */
2273 /* free (zero) the appropriate bits within this
2274 * dmap word.
2275 */
2280 /* update the leaf for this dmap word.
2281 */
2289 /* one or more dmap words are fully contained
2290 * within the block range. determine how many
2291 * words and free (zero) the bits of these words.
2292 */
2296 /* determine how many bits.
2297 */
2300 /* now update the appropriate leaves to reflect
2301 * the freed words.
2302 */
2304 /* determine what the leaf value should be
2305 * updated to as the minimum of the l2 number
2306 * of bits being freed and the l2 (max) number
2307 * of bits that can be described by this leaf.
2308 */
2309 size =
2314 /* update the leaf.
2315 */
2320 /* get the number of dmap words handled.
2321 */
2324 }
2325 }
2326 }
2328 /* update the free count for this dmap.
2329 */
2334 /* update the free count for the allocation group and
2335 * map.
2336 */
2341 /* check if this allocation group is not completely free and
2342 * if it is currently the maximum (rightmost) allocation group.
2343 * if so, establish the new maximum allocation group number by
2344 * searching left for the first allocation group with allocation.
2345 */
2354 }
2356 /* re-establish the allocation group preference if the
2357 * current preference is right of the maximum allocation
2358 * group.
2359 */
2362 }
2367 }
2370 /*
2371 * NAME: dbAdjCtl()
2372 *
2373 * FUNCTION: adjust a dmap control page at a specified level to reflect
2374 * the change in a lower level dmap or dmap control page's
2375 * maximum string of free blocks (i.e. a change in the root
2376 * of the lower level object's dmtree) due to the allocation
2377 * or deallocation of a range of blocks with a single dmap.
2378 *
2379 * on entry, this routine is provided with the new value of
2380 * the lower level dmap or dmap control page root and the
2381 * starting block number of the block range whose allocation
2382 * or deallocation resulted in the root change. this range
2383 * is respresented by a single leaf of the current dmapctl
2384 * and the leaf will be updated with this value, possibly
2385 * causing a binary buddy system within the leaves to be
2386 * split or joined. the update may also cause the dmapctl's
2387 * dmtree to be updated.
2388 *
2389 * if the adjustment of the dmap control page, itself, causes its
2390 * root to change, this change will be bubbled up to the next dmap
2391 * control level by a recursive call to this routine, specifying
2392 * the new root value and the next dmap control page level to
2393 * be adjusted.
2394 * PARAMETERS:
2395 * bmp - pointer to bmap descriptor
2396 * blkno - the first block of a block range within a dmap. it is
2397 * the allocation or deallocation of this block range that
2398 * requires the dmap control page to be adjusted.
2399 * newval - the new value of the lower level dmap or dmap control
2400 * page root.
2401 * alloc - TRUE if adjustment is due to an allocation.
2402 * level - current level of dmap control page (i.e. L0, L1, L2) to
2403 * be adjusted.
2404 *
2405 * RETURN VALUES:
2406 * 0 - success
2407 * -EIO - i/o error
2408 *
2409 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2410 */
2411 static int
2413 {
2415 s8 oldroot;
2417 s64 lblkno;
2421 /* get the buffer for the dmap control page for the specified
2422 * block number and control page level.
2423 */
2435 }
2437 /* determine the leaf number corresponding to the block and
2438 * the index within the dmap control tree.
2439 */
2443 /* save the current leaf value and the current root level (i.e.
2444 * maximum l2 free string described by this dmapctl).
2445 */
2449 /* check if this is a control page update for an allocation.
2450 * if so, update the leaf to reflect the new leaf value using
2451 * dbSplit(); otherwise (deallocation), use dbJoin() to udpate
2452 * the leaf with the new value. in addition to updating the
2453 * leaf, dbSplit() will also split the binary buddy system of
2454 * the leaves, if required, and bubble new values within the
2455 * dmapctl tree, if required. similarly, dbJoin() will join
2456 * the binary buddy system of leaves and bubble new values up
2457 * the dmapctl tree as required by the new leaf value.
2458 */
2460 /* check if we are in the middle of a binary buddy
2461 * system. this happens when we are performing the
2462 * first allocation out of an allocation group that
2463 * is part (not the first part) of a larger binary
2464 * buddy system. if we are in the middle, back split
2465 * the system prior to calling dbSplit() which assumes
2466 * that it is at the front of a binary buddy system.
2467 */
2473 }
2479 }
2481 /* check if the root of the current dmap control page changed due
2482 * to the update and if the current dmap control page is not at
2483 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2484 * root changed and this is not the top level), call this routine
2485 * again (recursion) for the next higher level of the mapping to
2486 * reflect the change in root for the current dmap control page.
2487 */
2489 /* are we below the top level of the map. if so,
2490 * bubble the root up to the next higher level.
2491 */
2493 /* bubble up the new root of this dmap control page to
2494 * the next level.
2495 */
2499 /* something went wrong in bubbling up the new
2500 * root value, so backout the changes to the
2501 * current dmap control page.
2502 */
2505 oldval);
2507 /* the dbJoin() above might have
2508 * caused a larger binary buddy system
2509 * to form and we may now be in the
2510 * middle of it. if this is the case,
2511 * back split the buddies.
2512 */
2518 }
2520 /* release the buffer and return the error.
2521 */
2524 }
2526 /* we're at the top level of the map. update
2527 * the bmap control page to reflect the size
2528 * of the maximum free buddy system.
2529 */
2533 "dbAdjCtl: the maximum free buddy is "
2535 }
2537 }
2538 }
2540 /* write the buffer.
2541 */
2545 }
2548 /*
2549 * NAME: dbSplit()
2550 *
2551 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2552 * the leaf from the binary buddy system of the dmtree's
2553 * leaves, as required.
2554 *
2555 * PARAMETERS:
2556 * tp - pointer to the tree containing the leaf.
2557 * leafno - the number of the leaf to be updated.
2558 * splitsz - the size the binary buddy system starting at the leaf
2559 * must be split to, specified as the log2 number of blocks.
2560 * newval - the new value for the leaf.
2561 *
2562 * RETURN VALUES: none
2563 *
2564 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2565 */
2567 {
2572 /* check if the leaf needs to be split.
2573 */
2575 /* the split occurs by cutting the buddy system in half
2576 * at the specified leaf until we reach the specified
2577 * size. pick up the starting split size (current size
2578 * - 1 in l2) and the corresponding buddy size.
2579 */
2583 /* split until we reach the specified size.
2584 */
2586 /* update the buddy's leaf with its new value.
2587 */
2590 /* on to the next size and buddy.
2591 */
2594 }
2595 }
2597 /* adjust the dmap tree to reflect the specified leaf's new
2598 * value.
2599 */
2601 }
2604 /*
2605 * NAME: dbBackSplit()
2606 *
2607 * FUNCTION: back split the binary buddy system of dmtree leaves
2608 * that hold a specified leaf until the specified leaf
2609 * starts its own binary buddy system.
2610 *
2611 * the allocators typically perform allocations at the start
2612 * of binary buddy systems and dbSplit() is used to accomplish
2613 * any required splits. in some cases, however, allocation
2614 * may occur in the middle of a binary system and requires a
2615 * back split, with the split proceeding out from the middle of
2616 * the system (less efficient) rather than the start of the
2617 * system (more efficient). the cases in which a back split
2618 * is required are rare and are limited to the first allocation
2619 * within an allocation group which is a part (not first part)
2620 * of a larger binary buddy system and a few exception cases
2621 * in which a previous join operation must be backed out.
2622 *
2623 * PARAMETERS:
2624 * tp - pointer to the tree containing the leaf.
2625 * leafno - the number of the leaf to be updated.
2626 *
2627 * RETURN VALUES: none
2628 *
2629 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2630 */
2632 {
2637 /* leaf should be part (not first part) of a binary
2638 * buddy system.
2639 */
2642 /* the back split is accomplished by iteratively finding the leaf
2643 * that starts the buddy system that contains the specified leaf and
2644 * splitting that system in two. this iteration continues until
2645 * the specified leaf becomes the start of a buddy system.
2646 *
2647 * determine maximum possible l2 size for the specified leaf.
2648 */
2649 size =
2653 /* determine the number of leaves covered by this size. this
2654 * is the buddy size that we will start with as we search for
2655 * the buddy system that contains the specified leaf.
2656 */
2659 /* back split.
2660 */
2662 /* find the leftmost buddy leaf.
2663 */
2669 }
2671 /* determine the buddy.
2672 */
2675 /* check if this buddy is the start of the system.
2676 */
2678 /* split the leaf at the start of the
2679 * system in two.
2680 */
2684 }
2685 }
2686 }
2691 }
2693 }
2696 /*
2697 * NAME: dbJoin()
2698 *
2699 * FUNCTION: update the leaf of a dmtree with a new value, joining
2700 * the leaf with other leaves of the dmtree into a multi-leaf
2701 * binary buddy system, as required.
2702 *
2703 * PARAMETERS:
2704 * tp - pointer to the tree containing the leaf.
2705 * leafno - the number of the leaf to be updated.
2706 * newval - the new value for the leaf.
2707 *
2708 * RETURN VALUES: none
2709 */
2711 {
2715 /* can the new leaf value require a join with other leaves ?
2716 */
2718 /* pickup a pointer to the leaves of the tree.
2719 */
2722 /* try to join the specified leaf into a large binary
2723 * buddy system. the join proceeds by attempting to join
2724 * the specified leafno with its buddy (leaf) at new value.
2725 * if the join occurs, we attempt to join the left leaf
2726 * of the joined buddies with its buddy at new value + 1.
2727 * we continue to join until we find a buddy that cannot be
2728 * joined (does not have a value equal to the size of the
2729 * last join) or until all leaves have been joined into a
2730 * single system.
2731 *
2732 * get the buddy size (number of words covered) of
2733 * the new value.
2734 */
2737 /* try to join.
2738 */
2740 /* get the buddy leaf.
2741 */
2744 /* if the leaf's new value is greater than its
2745 * buddy's value, we join no more.
2746 */
2750 /* It shouldn't be less */
2754 /* check which (leafno or buddy) is the left buddy.
2755 * the left buddy gets to claim the blocks resulting
2756 * from the join while the right gets to claim none.
2757 * the left buddy is also eligable to participate in
2758 * a join at the next higher level while the right
2759 * is not.
2760 *
2761 */
2763 /* leafno is the left buddy.
2764 */
2767 /* buddy is the left buddy and becomes
2768 * leafno.
2769 */
2772 }
2774 /* on to try the next join.
2775 */
2778 }
2779 }
2781 /* update the leaf value.
2782 */
2786 }
2789 /*
2790 * NAME: dbAdjTree()
2791 *
2792 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2793 * the dmtree, as required, to reflect the new leaf value.
2794 * the combination of any buddies must already be done before
2795 * this is called.
2796 *
2797 * PARAMETERS:
2798 * tp - pointer to the tree to be adjusted.
2799 * leafno - the number of the leaf to be updated.
2800 * newval - the new value for the leaf.
2801 *
2802 * RETURN VALUES: none
2803 */
2805 {
2809 /* pick up the index of the leaf for this leafno.
2810 */
2813 /* is the current value the same as the old value ? if so,
2814 * there is nothing to do.
2815 */
2819 /* set the new value.
2820 */
2823 /* bubble the new value up the tree as required.
2824 */
2826 /* get the index of the first leaf of the 4 leaf
2827 * group containing the specified leaf (leafno).
2828 */
2831 /* get the index of the parent of this 4 leaf group.
2832 */
2835 /* determine the maximum of the 4 leaves.
2836 */
2839 /* if the maximum of the 4 is the same as the
2840 * parent's value, we're done.
2841 */
2845 /* parent gets new value.
2846 */
2849 /* parent becomes leaf for next go-round.
2850 */
2852 }
2853 }
2856 /*
2857 * NAME: dbFindLeaf()
2858 *
2859 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2860 * the index of a leaf describing the free blocks if
2861 * sufficient free blocks are found.
2862 *
2863 * the search starts at the top of the dmtree_t tree and
2864 * proceeds down the tree to the leftmost leaf with sufficient
2865 * free space.
2866 *
2867 * PARAMETERS:
2868 * tp - pointer to the tree to be searched.
2869 * l2nb - log2 number of free blocks to search for.
2870 * leafidx - return pointer to be set to the index of the leaf
2871 * describing at least l2nb free blocks if sufficient
2872 * free blocks are found.
2873 *
2874 * RETURN VALUES:
2875 * 0 - success
2876 * -ENOSPC - insufficient free blocks.
2877 */
2879 {
2882 /* first check the root of the tree to see if there is
2883 * sufficient free space.
2884 */
2888 /* sufficient free space available. now search down the tree
2889 * starting at the next level for the leftmost leaf that
2890 * describes sufficient free space.
2891 */
2894 /* search the four nodes at this level, starting from
2895 * the left.
2896 */
2898 /* sufficient free space found. move to the next
2899 * level (or quit if this is the last level).
2900 */
2903 }
2905 /* better have found something since the higher
2906 * levels of the tree said it was here.
2907 */
2909 }
2911 /* set the return to the leftmost leaf describing sufficient
2912 * free space.
2913 */
2917 }
2920 /*
2921 * NAME: dbFindBits()
2922 *
2923 * FUNCTION: find a specified number of binary buddy free bits within a
2924 * dmap bitmap word value.
2925 *
2926 * this routine searches the bitmap value for (1 << l2nb) free
2927 * bits at (1 << l2nb) alignments within the value.
2928 *
2929 * PARAMETERS:
2930 * word - dmap bitmap word value.
2931 * l2nb - number of free bits specified as a log2 number.
2932 *
2933 * RETURN VALUES:
2934 * starting bit number of free bits.
2935 */
2937 {
2939 u32 mask;
2941 /* get the number of bits.
2942 */
2946 /* complement the word so we can use a mask (i.e. 0s represent
2947 * free bits) and compute the mask.
2948 */
2952 /* scan the word for nb free bits at nb alignments.
2953 */
2957 }
2961 /* return the bit number.
2962 */
2964 }
2967 /*
2968 * NAME: dbMaxBud(u8 *cp)
2969 *
2970 * FUNCTION: determine the largest binary buddy string of free
2971 * bits within 32-bits of the map.
2972 *
2973 * PARAMETERS:
2974 * cp - pointer to the 32-bit value.
2975 *
2976 * RETURN VALUES:
2977 * largest binary buddy of free bits within a dmap word.
2978 */
2980 {
2983 /* check if the wmap word is all free. if so, the
2984 * free buddy size is BUDMIN.
2985 */
2989 /* check if the wmap word is half free. if so, the
2990 * free buddy size is BUDMIN-1.
2991 */
2995 /* not all free or half free. determine the free buddy
2996 * size thru table lookup using quarters of the wmap word.
2997 */
3001 }
3004 /*
3005 * NAME: cnttz(uint word)
3006 *
3007 * FUNCTION: determine the number of trailing zeros within a 32-bit
3008 * value.
3009 *
3010 * PARAMETERS:
3011 * value - 32-bit value to be examined.
3012 *
3013 * RETURN VALUES:
3014 * count of trailing zeros
3015 */
3017 {
3023 }
3026 }
3029 /*
3030 * NAME: cntlz(u32 value)
3031 *
3032 * FUNCTION: determine the number of leading zeros within a 32-bit
3033 * value.
3034 *
3035 * PARAMETERS:
3036 * value - 32-bit value to be examined.
3037 *
3038 * RETURN VALUES:
3039 * count of leading zeros
3040 */
3042 {
3048 }
3050 }
3053 /*
3054 * NAME: blkstol2(s64 nb)
3055 *
3056 * FUNCTION: convert a block count to its log2 value. if the block
3057 * count is not a l2 multiple, it is rounded up to the next
3058 * larger l2 multiple.
3059 *
3060 * PARAMETERS:
3061 * nb - number of blocks
3062 *
3063 * RETURN VALUES:
3064 * log2 number of blocks
3065 */
3067 {
3073 /* count the leading bits.
3074 */
3076 /* leading bit found.
3077 */
3079 /* determine the l2 value.
3080 */
3083 /* check if we need to round up.
3084 */
3086 l2nb++;
3089 }
3090 }
3093 }
3096 /*
3097 * NAME: dbAllocBottomUp()
3098 *
3099 * FUNCTION: alloc the specified block range from the working block
3100 * allocation map.
3101 *
3102 * the blocks will be alloc from the working map one dmap
3103 * at a time.
3104 *
3105 * PARAMETERS:
3106 * ip - pointer to in-core inode;
3107 * blkno - starting block number to be freed.
3108 * nblocks - number of blocks to be freed.
3109 *
3110 * RETURN VALUES:
3111 * 0 - success
3112 * -EIO - i/o error
3113 */
3115 {
3125 /* block to be allocated better be within the mapsize. */
3128 /*
3129 * allocate the blocks a dmap at a time.
3130 */
3133 /* release previous dmap if any */
3136 }
3138 /* get the buffer for the current dmap. */
3144 }
3147 /* determine the number of blocks to be allocated from
3148 * this dmap.
3149 */
3152 /* allocate the blocks. */
3157 }
3158 }
3160 /* write the last buffer. */
3166 }
3171 {
3177 /* save the current value of the root (i.e. maximum free string)
3178 * of the dmap tree.
3179 */
3182 /* pick up a pointer to the leaves of the dmap tree */
3185 /* determine the bit number and word within the dmap of the
3186 * starting block.
3187 */
3191 /* block range better be within the dmap */
3194 /* allocate the bits of the dmap's words corresponding to the block
3195 * range. not all bits of the first and last words may be contained
3196 * within the block range. if this is the case, we'll work against
3197 * those words (i.e. partial first and/or last) on an individual basis
3198 * (a single pass), allocating the bits of interest by hand and
3199 * updating the leaf corresponding to the dmap word. a single pass
3200 * will be used for all dmap words fully contained within the
3201 * specified range. within this pass, the bits of all fully contained
3202 * dmap words will be marked as free in a single shot and the leaves
3203 * will be updated. a single leaf may describe the free space of
3204 * multiple dmap words, so we may update only a subset of the actual
3205 * leaves corresponding to the dmap words of the block range.
3206 */
3208 /* determine the bit number within the word and
3209 * the number of bits within the word.
3210 */
3214 /* check if only part of a word is to be allocated.
3215 */
3217 /* allocate (set to 1) the appropriate bits within
3218 * this dmap word.
3219 */
3223 word++;
3225 /* one or more dmap words are fully contained
3226 * within the block range. determine how many
3227 * words and allocate (set to 1) the bits of these
3228 * words.
3229 */
3233 /* determine how many bits */
3236 }
3237 }
3239 /* update the free count for this dmap */
3242 /* reconstruct summary tree */
3247 /* if this allocation group is completely free,
3248 * update the highest active allocation group number
3249 * if this allocation group is the new max.
3250 */
3255 /* update the free count for the allocation group and map */
3261 /* if the root has not changed, done. */
3265 /* root changed. bubble the change up to the dmap control pages.
3266 * if the adjustment of the upper level control pages fails,
3267 * backout the bit allocation (thus making everything consistent).
3268 */
3273 }
3276 /*
3277 * NAME: dbExtendFS()
3278 *
3279 * FUNCTION: extend bmap from blkno for nblocks;
3280 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3281 *
3282 * L2
3283 * |
3284 * L1---------------------------------L1
3285 * | |
3286 * L0---------L0---------L0 L0---------L0---------L0
3287 * | | | | | |
3288 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3289 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3290 *
3291 * <---old---><----------------------------extend----------------------->
3292 */
3294 {
3298 s64 newsize;
3299 s64 p;
3306 s64 ag_rem;
3313 /*
3314 * initialize bmap control page.
3315 *
3316 * all the data in bmap control page should exclude
3317 * the mkfs hidden dmap page.
3318 */
3320 /* update mapsize */
3324 /* compute new AG size */
3331 /* compute new number of AG */
3336 /*
3337 * reconfigure db_agfree[]
3338 * from old AG configuration to new AG configuration;
3339 *
3340 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3341 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3342 * note: new AG size = old AG size * (2**x).
3343 */
3351 /* coalesce cotiguous k AGs; */
3353 /* merge AGi to AGn */
3355 }
3356 }
3362 /*
3363 * update highest active ag number
3364 */
3368 /*
3369 * extend bmap
3370 *
3371 * update bit maps and corresponding level control pages;
3372 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3373 */
3374 extend:
3375 /* get L2 page */
3381 }
3384 /* compute start L1 */
3389 /*
3390 * extend each L1 in L2
3391 */
3393 /* get L1 page */
3395 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3401 /* compute start L0 */
3407 /* assign/init L1 page */
3414 /* compute start L0 */
3418 }
3420 /*
3421 * extend each L0 in L1
3422 */
3424 /* get L0 page */
3426 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3433 /* compute start dmap */
3435 L2BPERDMAP;
3441 /* assign/init L0 page */
3448 /* compute start dmap */
3452 }
3454 /*
3455 * extend each dmap in L0
3456 */
3458 /*
3459 * reconstruct the dmap page, and
3460 * initialize corresponding parent L0 leaf
3461 */
3463 /* read in dmap page: */
3470 /* assign/init dmap page */
3477 }
3488 l0leaf++;
3497 /*
3498 * build current L0 page from its leaves, and
3499 * initialize corresponding parent L1 leaf
3500 */
3508 /* more than 1 L0 ? */
3512 /* summarize in global bmap page */
3517 }
3518 }
3521 /*
3522 * build current L1 page from its leaves, and
3523 * initialize corresponding parent L2 leaf
3524 */
3532 /* more than 1 L1 ? */
3536 /* summarize in global bmap page */
3540 }
3541 }
3546 errout:
3554 /*
3555 * finalize bmap control page
3556 */
3557 finalize:
3560 }
3563 /*
3564 * dbFinalizeBmap()
3565 */
3567 {
3573 /*
3574 * finalize bmap control page
3575 */
3576 //finalize:
3577 /*
3578 * compute db_agpref: preferred ag to allocate from
3579 * (the leftmost ag with average free space in it);
3580 */
3581 //agpref:
3582 /* get the number of active ags and inacitve ags */
3587 /* determine how many blocks are in the inactive allocation
3588 * groups. in doing this, we must account for the fact that
3589 * the rightmost group might be a partial group (i.e. file
3590 * system size is not a multiple of the group size).
3591 */
3596 /* determine how many free blocks are in the active
3597 * allocation groups plus the average number of free blocks
3598 * within the active ags.
3599 */
3603 /* if the preferred allocation group has not average free space.
3604 * re-establish the preferred group as the leftmost
3605 * group with average free space.
3606 */
3612 }
3616 }
3617 }
3619 /*
3620 * compute db_aglevel, db_agheigth, db_width, db_agstart:
3621 * an ag is covered in aglevel dmapctl summary tree,
3622 * at agheight level height (from leaf) with agwidth number of nodes
3623 * each, which starts at agstart index node of the smmary tree node
3624 * array;
3625 */
3627 l2nl =
3632 i--) {
3635 }
3637 }
3640 /*
3641 * NAME: dbInitDmap()/ujfs_idmap_page()
3642 *
3643 * FUNCTION: initialize working/persistent bitmap of the dmap page
3644 * for the specified number of blocks:
3645 *
3646 * at entry, the bitmaps had been initialized as free (ZEROS);
3647 * The number of blocks will only account for the actually
3648 * existing blocks. Blocks which don't actually exist in
3649 * the aggregate will be marked as allocated (ONES);
3650 *
3651 * PARAMETERS:
3652 * dp - pointer to page of map
3653 * nblocks - number of blocks this page
3654 *
3655 * RETURNS: NONE
3656 */
3658 {
3661 /* starting block number within the dmap */
3672 }
3677 }
3679 /* word number containing start block number */
3682 /*
3683 * free the bits corresponding to the block range (ZEROS):
3684 * note: not all bits of the first and last words may be contained
3685 * within the block range.
3686 */
3688 /* number of bits preceding range to be freed in the word */
3690 /* number of bits to free in the word */
3693 /* is partial word to be freed ? */
3695 /* free (set to 0) from the bitmap word */
3701 /* skip the word freed */
3702 w++;
3704 /* free (set to 0) contiguous bitmap words */
3709 /* skip the words freed */
3712 }
3713 }
3715 /*
3716 * mark bits following the range to be freed (non-existing
3717 * blocks) as allocated (ONES)
3718 */
3723 /* the first word beyond the end of existing blocks */
3726 /* does nblocks fall on a 32-bit boundary ? */
3729 /* mark a partial word allocated */
3731 w++;
3732 }
3734 /* set the rest of the words in the page to allocated (ONES) */
3738 /*
3739 * init tree
3740 */
3741 initTree:
3743 }
3746 /*
3747 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3748 *
3749 * FUNCTION: initialize summary tree of the specified dmap:
3750 *
3751 * at entry, bitmap of the dmap has been initialized;
3752 *
3753 * PARAMETERS:
3754 * dp - dmap to complete
3755 * blkno - starting block number for this dmap
3756 * treemax - will be filled in with max free for this dmap
3757 *
3758 * RETURNS: max free string at the root of the tree
3759 */
3761 {
3766 /* init fixed info of tree */
3774 /* init each leaf from corresponding wmap word:
3775 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3776 * bitmap word are allocated.
3777 */
3782 /* build the dmap's binary buddy summary tree */
3784 }
3787 /*
3788 * NAME: dbInitTree()/ujfs_adjtree()
3789 *
3790 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3791 *
3792 * at entry, the leaves of the tree has been initialized
3793 * from corresponding bitmap word or root of summary tree
3794 * of the child control page;
3795 * configure binary buddy system at the leaf level, then
3796 * bubble up the values of the leaf nodes up the tree.
3797 *
3798 * PARAMETERS:
3799 * cp - Pointer to the root of the tree
3800 * l2leaves- Number of leaf nodes as a power of 2
3801 * l2min - Number of blocks that can be covered by a leaf
3802 * as a power of 2
3803 *
3804 * RETURNS: max free string at the root of the tree
3805 */
3807 {
3814 /* Determine the maximum free string possible for the leaves */
3817 /*
3818 * configure the leaf levevl into binary buddy system
3819 *
3820 * Try to combine buddies starting with a buddy size of 1
3821 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3822 * can be combined if both buddies have a maximum free of l2min;
3823 * the combination will result in the left-most buddy leaf having
3824 * a maximum free of l2min+1.
3825 * After processing all buddies for a given size, process buddies
3826 * at the next higher buddy size (i.e. current size * 2) and
3827 * the next maximum free (current free + 1).
3828 * This continues until the maximum possible buddy combination
3829 * yields maximum free.
3830 */
3833 /* get next buddy size == current buddy pair size */
3836 /* scan each adjacent buddy pair at current buddy size */
3840 /* coalesce if both adjacent buddies are max free */
3844 }
3845 }
3846 }
3848 /*
3849 * bubble summary information of leaves up the tree.
3850 *
3851 * Starting at the leaf node level, the four nodes described by
3852 * the higher level parent node are compared for a maximum free and
3853 * this maximum becomes the value of the parent node.
3854 * when all lower level nodes are processed in this fashion then
3855 * move up to the next level (parent becomes a lower level node) and
3856 * continue the process for that level.
3857 */
3861 /* get index of 1st node of parent level */
3864 /* set the value of the parent node as the maximum
3865 * of the four nodes of the current level.
3866 */
3870 }
3873 }
3876 /*
3877 * dbInitDmapCtl()
3878 *
3879 * function: initialize dmapctl page
3880 */
3891 /*
3892 * initialize the leaves of current level that were not covered
3893 * by the specified input block range (i.e. the leaves have no
3894 * low level dmapctl or dmap).
3895 */
3900 /* build the dmap's binary buddy summary tree */
3902 }
3905 /*
3906 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3907 *
3908 * FUNCTION: Determine log2(allocation group size) from aggregate size
3909 *
3910 * PARAMETERS:
3911 * nblocks - Number of blocks in aggregate
3912 *
3913 * RETURNS: log2(allocation group size) in aggregate blocks
3914 */
3916 {
3917 s64 sz;
3918 s64 m;
3924 /* round up aggregate size to power of 2 */
3929 }
3935 /* agsize = roundupSize/max_number_of_ag */
3937 }
3940 /*
3941 * NAME: dbMapFileSizeToMapSize()
3942 *
3943 * FUNCTION: compute number of blocks the block allocation map file
3944 * can cover from the map file size;
3945 *
3946 * RETURNS: Number of blocks which can be covered by this block map file;
3947 */
3949 /*
3950 * maximum number of map pages at each level including control pages
3951 */
3952 #define MAXL0PAGES (1 + LPERCTL)
3953 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
3954 #define MAXL2PAGES (1 + LPERCTL * MAXL1PAGES)
3956 /*
3957 * convert number of map pages to the zero origin top dmapctl level
3958 */
3959 #define BMAPPGTOLEV(npages) \
3960 (((npages) <= 3 + MAXL0PAGES) ? 0 \
3961 : ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
3964 {
3966 s64 nblocks;
3975 /* At each level, accumulate the number of dmap pages covered by
3976 * the number of full child levels below it;
3977 * repeat for the last incomplete child level.
3978 */
3981 /* skip higher level control pages above top level covered by map */
3985 factor =
3991 /* pages in last/incomplete child */
3993 /* skip incomplete child's level control page */
3994 npages--;
3995 }
3997 /* convert the number of dmaps into the number of blocks
3998 * which can be covered by the dmaps;
3999 */
4003 }