| blob | d86e467c6e421628a2f845668b5da630581bdf7e |
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 * Debug code for double-checking block map
30 */
31 /* #define _JFS_DEBUG_DMAP 1 */
33 #ifdef _JFS_DEBUG_DMAP
34 #define DBINITMAP(size,ipbmap,results) \
35 DBinitmap(size,ipbmap,results)
36 #define DBALLOC(dbmap,mapsize,blkno,nblocks) \
37 DBAlloc(dbmap,mapsize,blkno,nblocks)
38 #define DBFREE(dbmap,mapsize,blkno,nblocks) \
39 DBFree(dbmap,mapsize,blkno,nblocks)
40 #define DBALLOCCK(dbmap,mapsize,blkno,nblocks) \
41 DBAllocCK(dbmap,mapsize,blkno,nblocks)
42 #define DBFREECK(dbmap,mapsize,blkno,nblocks) \
43 DBFreeCK(dbmap,mapsize,blkno,nblocks)
50 #else
51 #define DBINITMAP(size,ipbmap,results)
52 #define DBALLOC(dbmap, mapsize, blkno, nblocks)
53 #define DBFREE(dbmap, mapsize, blkno, nblocks)
54 #define DBALLOCCK(dbmap, mapsize, blkno, nblocks)
55 #define DBFREECK(dbmap, mapsize, blkno, nblocks)
58 /*
59 * SERIALIZATION of the Block Allocation Map.
60 *
61 * the working state of the block allocation map is accessed in
62 * two directions:
63 *
64 * 1) allocation and free requests that start at the dmap
65 * level and move up through the dmap control pages (i.e.
66 * the vast majority of requests).
67 *
68 * 2) allocation requests that start at dmap control page
69 * level and work down towards the dmaps.
70 *
71 * the serialization scheme used here is as follows.
72 *
73 * requests which start at the bottom are serialized against each
74 * other through buffers and each requests holds onto its buffers
75 * as it works it way up from a single dmap to the required level
76 * of dmap control page.
77 * requests that start at the top are serialized against each other
78 * and request that start from the bottom by the multiple read/single
79 * write inode lock of the bmap inode. requests starting at the top
80 * take this lock in write mode while request starting at the bottom
81 * take the lock in read mode. a single top-down request may proceed
82 * exclusively while multiple bottoms-up requests may proceed
83 * simultaneously (under the protection of busy buffers).
84 *
85 * in addition to information found in dmaps and dmap control pages,
86 * the working state of the block allocation map also includes read/
87 * write information maintained in the bmap descriptor (i.e. total
88 * free block count, allocation group level free block counts).
89 * a single exclusive lock (BMAP_LOCK) is used to guard this information
90 * in the face of multiple-bottoms up requests.
91 * (lock ordering: IREAD_LOCK, BMAP_LOCK);
92 *
93 * accesses to the persistent state of the block allocation map (limited
94 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
95 */
97 #define BMAP_LOCK_INIT(bmp) init_MUTEX(&bmp->db_bmaplock)
98 #define BMAP_LOCK(bmp) down(&bmp->db_bmaplock)
99 #define BMAP_UNLOCK(bmp) up(&bmp->db_bmaplock)
101 /*
102 * forward references
103 */
150 /*
151 * buddy table
152 *
153 * table used for determining buddy sizes within characters of
154 * dmap bitmap words. the characters themselves serve as indexes
155 * into the table, with the table elements yielding the maximum
156 * binary buddy of free bits within the character.
157 */
175 };
178 /*
179 * NAME: dbMount()
180 *
181 * FUNCTION: initializate the block allocation map.
182 *
183 * memory is allocated for the in-core bmap descriptor and
184 * the in-core descriptor is initialized from disk.
185 *
186 * PARAMETERS:
187 * ipbmap - pointer to in-core inode for the block map.
188 *
189 * RETURN VALUES:
190 * 0 - success
191 * -ENOMEM - insufficient memory
192 * -EIO - i/o error
193 */
195 {
201 /*
202 * allocate/initialize the in-memory bmap descriptor
203 */
204 /* allocate memory for the in-memory bmap descriptor */
209 /* read the on-disk bmap descriptor. */
216 }
218 /* copy the on-disk bmap descriptor to its in-memory version. */
237 /* release the buffer. */
240 /* bind the bmap inode and the bmap descriptor to each other. */
247 /*
248 * allocate/initialize the bmap lock
249 */
253 }
256 /*
257 * NAME: dbUnmount()
258 *
259 * FUNCTION: terminate the block allocation map in preparation for
260 * file system unmount.
261 *
262 * the in-core bmap descriptor is written to disk and
263 * the memory for this descriptor is freed.
264 *
265 * PARAMETERS:
266 * ipbmap - pointer to in-core inode for the block map.
267 *
268 * RETURN VALUES:
269 * 0 - success
270 * -EIO - i/o error
271 */
273 {
280 /*
281 * Invalidate the page cache buffers
282 */
285 /*
286 * Sanity Check
287 */
293 /* free the memory for the in-memory bmap. */
297 }
299 /*
300 * dbSync()
301 */
303 {
309 /*
310 * write bmap global control page
311 */
312 /* get the buffer for the on-disk bmap descriptor. */
319 }
320 /* copy the in-memory version of the bmap to the on-disk version */
339 /* write the buffer */
342 /*
343 * write out dirty pages of bmap
344 */
352 }
355 /*
356 * NAME: dbFree()
357 *
358 * FUNCTION: free the specified block range from the working block
359 * allocation map.
360 *
361 * the blocks will be free from the working map one dmap
362 * at a time.
363 *
364 * PARAMETERS:
365 * ip - pointer to in-core inode;
366 * blkno - starting block number to be freed.
367 * nblocks - number of blocks to be freed.
368 *
369 * RETURN VALUES:
370 * 0 - success
371 * -EIO - i/o error
372 */
374 {
384 /* block to be freed better be within the mapsize. */
393 }
395 /*
396 * free the blocks a dmap at a time.
397 */
400 /* release previous dmap if any */
403 }
405 /* get the buffer for the current dmap. */
411 }
414 /* determine the number of blocks to be freed from
415 * this dmap.
416 */
421 /* free the blocks. */
426 }
429 }
431 /* write the last buffer. */
437 }
440 /*
441 * NAME: dbUpdatePMap()
442 *
443 * FUNCTION: update the allocation state (free or allocate) of the
444 * specified block range in the persistent block allocation map.
445 *
446 * the blocks will be updated in the persistent map one
447 * dmap at a time.
448 *
449 * PARAMETERS:
450 * ipbmap - pointer to in-core inode for the block map.
451 * free - TRUE if block range is to be freed from the persistent
452 * map; FALSE if it is to be allocated.
453 * blkno - starting block number of the range.
454 * nblocks - number of contiguous blocks in the range.
455 * tblk - transaction block;
456 *
457 * RETURN VALUES:
458 * 0 - success
459 * -EIO - i/o error
460 */
461 int
464 {
469 u32 mask;
475 /* the blocks better be within the mapsize. */
483 }
485 /* compute delta of transaction lsn from log syncpt */
490 /*
491 * update the block state a dmap at a time.
492 */
496 /* get the buffer for the current dmap. */
501 }
507 }
510 /* determine the bit number and word within the dmap of
511 * the starting block. also determine how many blocks
512 * are to be updated within this dmap.
513 */
518 /* update the bits of the dmap words. the first and last
519 * words may only have a subset of their bits updated. if
520 * this is the case, we'll work against that word (i.e.
521 * partial first and/or last) only in a single pass. a
522 * single pass will also be used to update all words that
523 * are to have all their bits updated.
524 */
527 /* determine the bit number within the word and
528 * the number of bits within the word.
529 */
533 /* check if only part of the word is to be updated. */
535 /* update (free or allocate) the bits
536 * in this word.
537 */
538 mask =
543 else
549 /* one or more words are to have all
550 * their bits updated. determine how
551 * many words and how many bits.
552 */
556 /* update (free or allocate) the bits
557 * in these words.
558 */
562 else
567 }
568 }
570 /*
571 * update dmap lsn
572 */
579 /* inherit older/smaller lsn */
584 /* move bp after tblock in logsync list */
588 }
590 /* inherit younger/larger clsn */
601 /* insert bp after tblock in logsync list */
609 }
610 }
612 /* write the last buffer. */
615 }
618 }
621 /*
622 * NAME: dbNextAG()
623 *
624 * FUNCTION: find the preferred allocation group for new allocations.
625 *
626 * Within the allocation groups, we maintain a preferred
627 * allocation group which consists of a group with at least
628 * average free space. It is the preferred group that we target
629 * new inode allocation towards. The tie-in between inode
630 * allocation and block allocation occurs as we allocate the
631 * first (data) block of an inode and specify the inode (block)
632 * as the allocation hint for this block.
633 *
634 * We try to avoid having more than one open file growing in
635 * an allocation group, as this will lead to fragmentation.
636 * This differs from the old OS/2 method of trying to keep
637 * empty ags around for large allocations.
638 *
639 * PARAMETERS:
640 * ipbmap - pointer to in-core inode for the block map.
641 *
642 * RETURN VALUES:
643 * the preferred allocation group number.
644 */
646 {
647 s64 avgfree;
656 /* determine the average number of free blocks within the ags. */
659 /*
660 * if the current preferred ag does not have an active allocator
661 * and has at least average freespace, return it
662 */
668 /* From the last preferred ag, find the next one with at least
669 * average free space.
670 */
676 /* open file is currently growing in this ag */
679 /* Return this one */
683 /* Less than avg. freespace, but best so far */
686 }
687 }
689 /*
690 * If no inactive ag was found with average freespace, use the
691 * next best
692 */
695 /* else leave db_agpref unchanged */
696 unlock:
699 /* return the preferred group.
700 */
702 }
704 /*
705 * NAME: dbAlloc()
706 *
707 * FUNCTION: attempt to allocate a specified number of contiguous free
708 * blocks from the working allocation block map.
709 *
710 * the block allocation policy uses hints and a multi-step
711 * approach.
712 *
713 * for allocation requests smaller than the number of blocks
714 * per dmap, we first try to allocate the new blocks
715 * immediately following the hint. if these blocks are not
716 * available, we try to allocate blocks near the hint. if
717 * no blocks near the hint are available, we next try to
718 * allocate within the same dmap as contains the hint.
719 *
720 * if no blocks are available in the dmap or the allocation
721 * request is larger than the dmap size, we try to allocate
722 * within the same allocation group as contains the hint. if
723 * this does not succeed, we finally try to allocate anywhere
724 * within the aggregate.
725 *
726 * we also try to allocate anywhere within the aggregate for
727 * for allocation requests larger than the allocation group
728 * size or requests that specify no hint value.
729 *
730 * PARAMETERS:
731 * ip - pointer to in-core inode;
732 * hint - allocation hint.
733 * nblocks - number of contiguous blocks in the range.
734 * results - on successful return, set to the starting block number
735 * of the newly allocated contiguous range.
736 *
737 * RETURN VALUES:
738 * 0 - success
739 * -ENOSPC - insufficient disk resources
740 * -EIO - i/o error
741 */
743 {
751 s64 mapSize;
754 /* assert that nblocks is valid */
757 #ifdef _STILL_TO_PORT
758 /* DASD limit check F226941 */
763 /* get the log2 number of blocks to be allocated.
764 * if the number of blocks is not a log2 multiple,
765 * it will be rounded up to the next log2 multiple.
766 */
771 //retry: /* serialize w.r.t.extendfs() */
774 /* the hint should be within the map */
778 }
780 /* if the number of blocks to be allocated is greater than the
781 * allocation group size, try to allocate anywhere.
782 */
789 nblocks);
790 }
793 }
795 /*
796 * If no hint, let dbNextAG recommend an allocation group
797 */
801 /* we would like to allocate close to the hint. adjust the
802 * hint to the block following the hint since the allocators
803 * will start looking for free space starting at this point.
804 */
812 /* check if blkno crosses over into a new allocation group.
813 * if so, check if we should allow allocations within this
814 * allocation group.
815 */
817 /* check if the AG is currenly being written to.
818 * if so, call dbNextAG() to find a non-busy
819 * AG with sufficient free space.
820 */
824 /* check if the allocation request size can be satisfied from a
825 * single dmap. if so, try to allocate from the dmap containing
826 * the hint using a tiered strategy.
827 */
831 /* get the buffer for the dmap containing the hint.
832 */
841 /* first, try to satisfy the allocation request with the
842 * blocks beginning at the hint.
843 */
851 }
855 }
860 /*
861 * Someone else is writing in this allocation
862 * group. To avoid fragmenting, try another ag
863 */
867 }
869 /* next, try to satisfy the allocation request with blocks
870 * near the hint.
871 */
879 }
883 }
885 /* try to satisfy the allocation request with blocks within
886 * the same dmap as the hint.
887 */
894 }
898 }
902 }
904 /* try to satisfy the allocation request with blocks within
905 * the same allocation group as the hint.
906 */
914 }
918 pref_ag:
919 /*
920 * Let dbNextAG recommend a preferred allocation group
921 */
925 /* Try to allocate within this allocation group. if that fails, try to
926 * allocate anywhere in the map.
927 */
932 }
934 write_unlock:
939 read_unlock:
943 }
945 #ifdef _NOTYET
946 /*
947 * NAME: dbAllocExact()
948 *
949 * FUNCTION: try to allocate the requested extent;
950 *
951 * PARAMETERS:
952 * ip - pointer to in-core inode;
953 * blkno - extent address;
954 * nblocks - extent length;
955 *
956 * RETURN VALUES:
957 * 0 - success
958 * -ENOSPC - insufficient disk resources
959 * -EIO - i/o error
960 */
962 {
967 s64 lblkno;
972 /*
973 * validate extent request:
974 *
975 * note: defragfs policy:
976 * max 64 blocks will be moved.
977 * allocation request size must be satisfied from a single dmap.
978 */
982 }
985 /* the free space is no longer available */
988 }
990 /* read in the dmap covering the extent */
996 }
999 /* try to allocate the requested extent */
1007 }
1011 }
1014 /*
1015 * NAME: dbReAlloc()
1016 *
1017 * FUNCTION: attempt to extend a current allocation by a specified
1018 * number of blocks.
1019 *
1020 * this routine attempts to satisfy the allocation request
1021 * by first trying to extend the existing allocation in
1022 * place by allocating the additional blocks as the blocks
1023 * immediately following the current allocation. if these
1024 * blocks are not available, this routine will attempt to
1025 * allocate a new set of contiguous blocks large enough
1026 * to cover the existing allocation plus the additional
1027 * number of blocks required.
1028 *
1029 * PARAMETERS:
1030 * ip - pointer to in-core inode requiring allocation.
1031 * blkno - starting block of the current allocation.
1032 * nblocks - number of contiguous blocks within the current
1033 * allocation.
1034 * addnblocks - number of blocks to add to the allocation.
1035 * results - on successful return, set to the starting block number
1036 * of the existing allocation if the existing allocation
1037 * was extended in place or to a newly allocated contiguous
1038 * range if the existing allocation could not be extended
1039 * in place.
1040 *
1041 * RETURN VALUES:
1042 * 0 - success
1043 * -ENOSPC - insufficient disk resources
1044 * -EIO - i/o error
1045 */
1046 int
1049 {
1052 /* try to extend the allocation in place.
1053 */
1060 }
1062 /* could not extend the allocation in place, so allocate a
1063 * new set of blocks for the entire request (i.e. try to get
1064 * a range of contiguous blocks large enough to cover the
1065 * existing allocation plus the additional blocks.)
1066 */
1069 }
1072 /*
1073 * NAME: dbExtend()
1074 *
1075 * FUNCTION: attempt to extend a current allocation by a specified
1076 * number of blocks.
1077 *
1078 * this routine attempts to satisfy the allocation request
1079 * by first trying to extend the existing allocation in
1080 * place by allocating the additional blocks as the blocks
1081 * immediately following the current allocation.
1082 *
1083 * PARAMETERS:
1084 * ip - pointer to in-core inode requiring allocation.
1085 * blkno - starting block of the current allocation.
1086 * nblocks - number of contiguous blocks within the current
1087 * allocation.
1088 * addnblocks - number of blocks to add to the allocation.
1089 *
1090 * RETURN VALUES:
1091 * 0 - success
1092 * -ENOSPC - insufficient disk resources
1093 * -EIO - i/o error
1094 */
1096 {
1099 uint rel_block;
1106 /*
1107 * We don't want a non-aligned extent to cross a page boundary
1108 */
1113 /* get the last block of the current allocation */
1116 /* determine the block number of the block following
1117 * the existing allocation.
1118 */
1123 /* better be within the file system */
1130 }
1132 /* we'll attempt to extend the current allocation in place by
1133 * allocating the additional blocks as the blocks immediately
1134 * following the current allocation. we only try to extend the
1135 * current allocation in place if the number of additional blocks
1136 * can fit into a dmap, the last block of the current allocation
1137 * is not the last block of the file system, and the start of the
1138 * inplace extension is not on an allocation group boundary.
1139 */
1144 }
1146 /* get the buffer for the dmap containing the first block
1147 * of the extension.
1148 */
1154 }
1159 /* try to allocate the blocks immediately following the
1160 * current allocation.
1161 */
1166 /* were we successful ? */
1169 addnblocks);
1172 /* we were not successful */
1177 }
1180 /*
1181 * NAME: dbAllocNext()
1182 *
1183 * FUNCTION: attempt to allocate the blocks of the specified block
1184 * range within a dmap.
1185 *
1186 * PARAMETERS:
1187 * bmp - pointer to bmap descriptor
1188 * dp - pointer to dmap.
1189 * blkno - starting block number of the range.
1190 * nblocks - number of contiguous free blocks of the range.
1191 *
1192 * RETURN VALUES:
1193 * 0 - success
1194 * -ENOSPC - insufficient disk resources
1195 * -EIO - i/o error
1196 *
1197 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1198 */
1201 {
1205 u32 mask;
1211 }
1213 /* pick up a pointer to the leaves of the dmap tree.
1214 */
1217 /* determine the bit number and word within the dmap of the
1218 * starting block.
1219 */
1223 /* check if the specified block range is contained within
1224 * this dmap.
1225 */
1229 /* check if the starting leaf indicates that anything
1230 * is free.
1231 */
1235 /* check the dmaps words corresponding to block range to see
1236 * if the block range is free. not all bits of the first and
1237 * last words may be contained within the block range. if this
1238 * is the case, we'll work against those words (i.e. partial first
1239 * and/or last) on an individual basis (a single pass) and examine
1240 * the actual bits to determine if they are free. a single pass
1241 * will be used for all dmap words fully contained within the
1242 * specified range. within this pass, the leaves of the dmap
1243 * tree will be examined to determine if the blocks are free. a
1244 * single leaf may describe the free space of multiple dmap
1245 * words, so we may visit only a subset of the actual leaves
1246 * corresponding to the dmap words of the block range.
1247 */
1249 /* determine the bit number within the word and
1250 * the number of bits within the word.
1251 */
1255 /* check if only part of the word is to be examined.
1256 */
1258 /* check if the bits are free.
1259 */
1266 /* one or more dmap words are fully contained
1267 * within the block range. determine how many
1268 * words and how many bits.
1269 */
1273 /* now examine the appropriate leaves to determine
1274 * if the blocks are free.
1275 */
1277 /* does the leaf describe any free space ?
1278 */
1282 /* determine the l2 number of bits provided
1283 * by this leaf.
1284 */
1285 l2size =
1288 /* determine how many words were handled.
1289 */
1294 }
1295 }
1296 }
1298 /* allocate the blocks.
1299 */
1301 }
1304 /*
1305 * NAME: dbAllocNear()
1306 *
1307 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1308 * a specified block (hint) within a dmap.
1309 *
1310 * starting with the dmap leaf that covers the hint, we'll
1311 * check the next four contiguous leaves for sufficient free
1312 * space. if sufficient free space is found, we'll allocate
1313 * the desired free space.
1314 *
1315 * PARAMETERS:
1316 * bmp - pointer to bmap descriptor
1317 * dp - pointer to dmap.
1318 * blkno - block number to allocate near.
1319 * nblocks - actual number of contiguous free blocks desired.
1320 * l2nb - log2 number of contiguous free blocks desired.
1321 * results - on successful return, set to the starting block number
1322 * of the newly allocated range.
1323 *
1324 * RETURN VALUES:
1325 * 0 - success
1326 * -ENOSPC - insufficient disk resources
1327 * -EIO - i/o error
1328 *
1329 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1330 */
1331 static int
1334 {
1342 }
1346 /* determine the word within the dmap that holds the hint
1347 * (i.e. blkno). also, determine the last word in the dmap
1348 * that we'll include in our examination.
1349 */
1353 /* examine the leaves for sufficient free space.
1354 */
1356 /* does the leaf describe sufficient free space ?
1357 */
1361 /* determine the block number within the file system
1362 * of the first block described by this dmap word.
1363 */
1366 /* if not all bits of the dmap word are free, get the
1367 * starting bit number within the dmap word of the required
1368 * string of free bits and adjust the block number with the
1369 * value.
1370 */
1372 blkno +=
1375 /* allocate the blocks.
1376 */
1381 }
1384 }
1387 /*
1388 * NAME: dbAllocAG()
1389 *
1390 * FUNCTION: attempt to allocate the specified number of contiguous
1391 * free blocks within the specified allocation group.
1392 *
1393 * unless the allocation group size is equal to the number
1394 * of blocks per dmap, the dmap control pages will be used to
1395 * find the required free space, if available. we start the
1396 * search at the highest dmap control page level which
1397 * distinctly describes the allocation group's free space
1398 * (i.e. the highest level at which the allocation group's
1399 * free space is not mixed in with that of any other group).
1400 * in addition, we start the search within this level at a
1401 * height of the dmapctl dmtree at which the nodes distinctly
1402 * describe the allocation group's free space. at this height,
1403 * the allocation group's free space may be represented by 1
1404 * or two sub-trees, depending on the allocation group size.
1405 * we search the top nodes of these subtrees left to right for
1406 * sufficient free space. if sufficient free space is found,
1407 * the subtree is searched to find the leftmost leaf that
1408 * has free space. once we have made it to the leaf, we
1409 * move the search to the next lower level dmap control page
1410 * corresponding to this leaf. we continue down the dmap control
1411 * pages until we find the dmap that contains or starts the
1412 * sufficient free space and we allocate at this dmap.
1413 *
1414 * if the allocation group size is equal to the dmap size,
1415 * we'll start at the dmap corresponding to the allocation
1416 * group and attempt the allocation at this level.
1417 *
1418 * the dmap control page search is also not performed if the
1419 * allocation group is completely free and we go to the first
1420 * dmap of the allocation group to do the allocation. this is
1421 * done because the allocation group may be part (not the first
1422 * part) of a larger binary buddy system, causing the dmap
1423 * control pages to indicate no free space (NOFREE) within
1424 * the allocation group.
1425 *
1426 * PARAMETERS:
1427 * bmp - pointer to bmap descriptor
1428 * agno - allocation group number.
1429 * nblocks - actual number of contiguous free blocks desired.
1430 * l2nb - log2 number of contiguous free blocks desired.
1431 * results - on successful return, set to the starting block number
1432 * of the newly allocated range.
1433 *
1434 * RETURN VALUES:
1435 * 0 - success
1436 * -ENOSPC - insufficient disk resources
1437 * -EIO - i/o error
1438 *
1439 * note: IWRITE_LOCK(ipmap) held on entry/exit;
1440 */
1441 static int
1443 {
1450 /* allocation request should not be for more than the
1451 * allocation group size.
1452 */
1455 "dbAllocAG: allocation request is larger than the "
1458 }
1460 /* determine the starting block number of the allocation
1461 * group.
1462 */
1465 /* check if the allocation group size is the minimum allocation
1466 * group size or if the allocation group is completely free. if
1467 * the allocation group size is the minimum size of BPERDMAP (i.e.
1468 * 1 dmap), there is no need to search the dmap control page (below)
1469 * that fully describes the allocation group since the allocation
1470 * group is already fully described by a dmap. in this case, we
1471 * just call dbAllocCtl() to search the dmap tree and allocate the
1472 * required space if available.
1473 *
1474 * if the allocation group is completely free, dbAllocCtl() is
1475 * also called to allocate the required space. this is done for
1476 * two reasons. first, it makes no sense searching the dmap control
1477 * pages for free space when we know that free space exists. second,
1478 * the dmap control pages may indicate that the allocation group
1479 * has no free space if the allocation group is part (not the first
1480 * part) of a larger binary buddy system.
1481 */
1492 }
1494 }
1496 /* the buffer for the dmap control page that fully describes the
1497 * allocation group.
1498 */
1511 }
1513 /* search the subtree(s) of the dmap control page that describes
1514 * the allocation group, looking for sufficient free space. to begin,
1515 * determine how many allocation groups are represented in a dmap
1516 * control page at the control page level (i.e. L0, L1, L2) that
1517 * fully describes an allocation group. next, determine the starting
1518 * tree index of this allocation group within the control page.
1519 */
1520 agperlev =
1524 /* dmap control page trees fan-out by 4 and a single allocation
1525 * group may be described by 1 or 2 subtrees within the ag level
1526 * dmap control page, depending upon the ag size. examine the ag's
1527 * subtrees for sufficient free space, starting with the leftmost
1528 * subtree.
1529 */
1531 /* is there sufficient free space ?
1532 */
1536 /* sufficient free space found in a subtree. now search down
1537 * the subtree to find the leftmost leaf that describes this
1538 * free space.
1539 */
1545 }
1546 }
1552 }
1553 }
1555 /* determine the block number within the file system
1556 * that corresponds to this leaf.
1557 */
1565 blkno +=
1568 /* release the buffer in preparation for going down
1569 * the next level of dmap control pages.
1570 */
1573 /* check if we need to continue to search down the lower
1574 * level dmap control pages. we need to if the number of
1575 * blocks required is less than maximum number of blocks
1576 * described at the next lower level.
1577 */
1580 /* search the lower level dmap control pages to get
1581 * the starting block number of the the dmap that
1582 * contains or starts off the free space.
1583 */
1589 "dbAllocAG: control page "
1592 }
1594 }
1595 }
1597 /* allocate the blocks.
1598 */
1604 }
1606 }
1608 /* no space in the allocation group. release the buffer and
1609 * return -ENOSPC.
1610 */
1614 }
1617 /*
1618 * NAME: dbAllocAny()
1619 *
1620 * FUNCTION: attempt to allocate the specified number of contiguous
1621 * free blocks anywhere in the file system.
1622 *
1623 * dbAllocAny() attempts to find the sufficient free space by
1624 * searching down the dmap control pages, starting with the
1625 * highest level (i.e. L0, L1, L2) control page. if free space
1626 * large enough to satisfy the desired free space is found, the
1627 * desired free space is allocated.
1628 *
1629 * PARAMETERS:
1630 * bmp - pointer to bmap descriptor
1631 * nblocks - actual number of contiguous free blocks desired.
1632 * l2nb - log2 number of contiguous free blocks desired.
1633 * results - on successful return, set to the starting block number
1634 * of the newly allocated range.
1635 *
1636 * RETURN VALUES:
1637 * 0 - success
1638 * -ENOSPC - insufficient disk resources
1639 * -EIO - i/o error
1640 *
1641 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1642 */
1644 {
1648 /* starting with the top level dmap control page, search
1649 * down the dmap control levels for sufficient free space.
1650 * if free space is found, dbFindCtl() returns the starting
1651 * block number of the dmap that contains or starts off the
1652 * range of free space.
1653 */
1657 /* allocate the blocks.
1658 */
1664 }
1666 }
1669 /*
1670 * NAME: dbFindCtl()
1671 *
1672 * FUNCTION: starting at a specified dmap control page level and block
1673 * number, search down the dmap control levels for a range of
1674 * contiguous free blocks large enough to satisfy an allocation
1675 * request for the specified number of free blocks.
1676 *
1677 * if sufficient contiguous free blocks are found, this routine
1678 * returns the starting block number within a dmap page that
1679 * contains or starts a range of contiqious free blocks that
1680 * is sufficient in size.
1681 *
1682 * PARAMETERS:
1683 * bmp - pointer to bmap descriptor
1684 * level - starting dmap control page level.
1685 * l2nb - log2 number of contiguous free blocks desired.
1686 * *blkno - on entry, starting block number for conducting the search.
1687 * on successful return, the first block within a dmap page
1688 * that contains or starts a range of contiguous free blocks.
1689 *
1690 * RETURN VALUES:
1691 * 0 - success
1692 * -ENOSPC - insufficient disk resources
1693 * -EIO - i/o error
1694 *
1695 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1696 */
1698 {
1705 /* starting at the specified dmap control page level and block
1706 * number, search down the dmap control levels for the starting
1707 * block number of a dmap page that contains or starts off
1708 * sufficient free blocks.
1709 */
1711 /* get the buffer of the dmap control page for the block
1712 * number and level (i.e. L0, L1, L2).
1713 */
1726 }
1728 /* search the tree within the dmap control page for
1729 * sufficent free space. if sufficient free space is found,
1730 * dbFindLeaf() returns the index of the leaf at which
1731 * free space was found.
1732 */
1735 /* release the buffer.
1736 */
1739 /* space found ?
1740 */
1746 }
1748 }
1750 /* adjust the block number to reflect the location within
1751 * the dmap control page (i.e. the leaf) at which free
1752 * space was found.
1753 */
1756 /* we stop the search at this dmap control page level if
1757 * the number of blocks required is greater than or equal
1758 * to the maximum number of blocks described at the next
1759 * (lower) level.
1760 */
1763 }
1767 }
1770 /*
1771 * NAME: dbAllocCtl()
1772 *
1773 * FUNCTION: attempt to allocate a specified number of contiguous
1774 * blocks starting within a specific dmap.
1775 *
1776 * this routine is called by higher level routines that search
1777 * the dmap control pages above the actual dmaps for contiguous
1778 * free space. the result of successful searches by these
1779 * routines are the starting block numbers within dmaps, with
1780 * the dmaps themselves containing the desired contiguous free
1781 * space or starting a contiguous free space of desired size
1782 * that is made up of the blocks of one or more dmaps. these
1783 * calls should not fail due to insufficent resources.
1784 *
1785 * this routine is called in some cases where it is not known
1786 * whether it will fail due to insufficient resources. more
1787 * specifically, this occurs when allocating from an allocation
1788 * group whose size is equal to the number of blocks per dmap.
1789 * in this case, the dmap control pages are not examined prior
1790 * to calling this routine (to save pathlength) and the call
1791 * might fail.
1792 *
1793 * for a request size that fits within a dmap, this routine relies
1794 * upon the dmap's dmtree to find the requested contiguous free
1795 * space. for request sizes that are larger than a dmap, the
1796 * requested free space will start at the first block of the
1797 * first dmap (i.e. blkno).
1798 *
1799 * PARAMETERS:
1800 * bmp - pointer to bmap descriptor
1801 * nblocks - actual number of contiguous free blocks to allocate.
1802 * l2nb - log2 number of contiguous free blocks to allocate.
1803 * blkno - starting block number of the dmap to start the allocation
1804 * from.
1805 * results - on successful return, set to the starting block number
1806 * of the newly allocated range.
1807 *
1808 * RETURN VALUES:
1809 * 0 - success
1810 * -ENOSPC - insufficient disk resources
1811 * -EIO - i/o error
1812 *
1813 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1814 */
1815 static int
1817 {
1823 /* check if the allocation request is confined to a single dmap.
1824 */
1826 /* get the buffer for the dmap.
1827 */
1834 /* try to allocate the blocks.
1835 */
1843 }
1845 /* allocation request involving multiple dmaps. it must start on
1846 * a dmap boundary.
1847 */
1850 /* allocate the blocks dmap by dmap.
1851 */
1853 /* get the buffer for the dmap.
1854 */
1860 }
1863 /* the dmap better be all free.
1864 */
1871 }
1873 /* determine how many blocks to allocate from this dmap.
1874 */
1877 /* allocate the blocks from the dmap.
1878 */
1882 }
1884 /* write the buffer.
1885 */
1887 }
1889 /* set the results (starting block number) and return.
1890 */
1894 /* something failed in handling an allocation request involving
1895 * multiple dmaps. we'll try to clean up by backing out any
1896 * allocation that has already happened for this request. if
1897 * we fail in backing out the allocation, we'll mark the file
1898 * system to indicate that blocks have been leaked.
1899 */
1900 backout:
1902 /* try to backout the allocations dmap by dmap.
1903 */
1906 /* get the buffer for this dmap.
1907 */
1911 /* could not back out. mark the file system
1912 * to indicate that we have leaked blocks.
1913 */
1917 }
1920 /* free the blocks is this dmap.
1921 */
1923 /* could not back out. mark the file system
1924 * to indicate that we have leaked blocks.
1925 */
1930 }
1932 /* write the buffer.
1933 */
1935 }
1938 }
1941 /*
1942 * NAME: dbAllocDmapLev()
1943 *
1944 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1945 * from a specified dmap.
1946 *
1947 * this routine checks if the contiguous blocks are available.
1948 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1949 * returned.
1950 *
1951 * PARAMETERS:
1952 * mp - pointer to bmap descriptor
1953 * dp - pointer to dmap to attempt to allocate blocks from.
1954 * l2nb - log2 number of contiguous block desired.
1955 * nblocks - actual number of contiguous block desired.
1956 * results - on successful return, set to the starting block number
1957 * of the newly allocated range.
1958 *
1959 * RETURN VALUES:
1960 * 0 - success
1961 * -ENOSPC - insufficient disk resources
1962 * -EIO - i/o error
1963 *
1964 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1965 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1966 */
1967 static int
1970 {
1971 s64 blkno;
1974 /* can't be more than a dmaps worth of blocks */
1977 /* search the tree within the dmap page for sufficient
1978 * free space. if sufficient free space is found, dbFindLeaf()
1979 * returns the index of the leaf at which free space was found.
1980 */
1984 /* determine the block number within the file system corresponding
1985 * to the leaf at which free space was found.
1986 */
1989 /* if not all bits of the dmap word are free, get the starting
1990 * bit number within the dmap word of the required string of free
1991 * bits and adjust the block number with this value.
1992 */
1996 /* allocate the blocks */
2001 }
2004 /*
2005 * NAME: dbAllocDmap()
2006 *
2007 * FUNCTION: adjust the disk allocation map to reflect the allocation
2008 * of a specified block range within a dmap.
2009 *
2010 * this routine allocates the specified blocks from the dmap
2011 * through a call to dbAllocBits(). if the allocation of the
2012 * block range causes the maximum string of free blocks within
2013 * the dmap to change (i.e. the value of the root of the dmap's
2014 * dmtree), this routine will cause this change to be reflected
2015 * up through the appropriate levels of the dmap control pages
2016 * by a call to dbAdjCtl() for the L0 dmap control page that
2017 * covers this dmap.
2018 *
2019 * PARAMETERS:
2020 * bmp - pointer to bmap descriptor
2021 * dp - pointer to dmap to allocate the block range from.
2022 * blkno - starting block number of the block to be allocated.
2023 * nblocks - number of blocks to be allocated.
2024 *
2025 * RETURN VALUES:
2026 * 0 - success
2027 * -EIO - i/o error
2028 *
2029 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2030 */
2033 {
2034 s8 oldroot;
2037 /* save the current value of the root (i.e. maximum free string)
2038 * of the dmap tree.
2039 */
2042 /* allocate the specified (blocks) bits */
2045 /* if the root has not changed, done. */
2049 /* root changed. bubble the change up to the dmap control pages.
2050 * if the adjustment of the upper level control pages fails,
2051 * backout the bit allocation (thus making everything consistent).
2052 */
2057 }
2060 /*
2061 * NAME: dbFreeDmap()
2062 *
2063 * FUNCTION: adjust the disk allocation map to reflect the allocation
2064 * of a specified block range within a dmap.
2065 *
2066 * this routine frees the specified blocks from the dmap through
2067 * a call to dbFreeBits(). if the deallocation of the block range
2068 * causes the maximum string of free blocks within the dmap to
2069 * change (i.e. the value of the root of the dmap's dmtree), this
2070 * routine will cause this change to be reflected up through the
2071 * appropriate levels of the dmap control pages by a call to
2072 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
2073 *
2074 * PARAMETERS:
2075 * bmp - pointer to bmap descriptor
2076 * dp - pointer to dmap to free the block range from.
2077 * blkno - starting block number of the block to be freed.
2078 * nblocks - number of blocks to be freed.
2079 *
2080 * RETURN VALUES:
2081 * 0 - success
2082 * -EIO - i/o error
2083 *
2084 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2085 */
2088 {
2089 s8 oldroot;
2092 /* save the current value of the root (i.e. maximum free string)
2093 * of the dmap tree.
2094 */
2097 /* free the specified (blocks) bits */
2100 /* if the root has not changed, done. */
2104 /* root changed. bubble the change up to the dmap control pages.
2105 * if the adjustment of the upper level control pages fails,
2106 * backout the deallocation.
2107 */
2111 /* as part of backing out the deallocation, we will have
2112 * to back split the dmap tree if the deallocation caused
2113 * the freed blocks to become part of a larger binary buddy
2114 * system.
2115 */
2120 }
2123 }
2126 /*
2127 * NAME: dbAllocBits()
2128 *
2129 * FUNCTION: allocate a specified block range from a dmap.
2130 *
2131 * this routine updates the dmap to reflect the working
2132 * state allocation of the specified block range. it directly
2133 * updates the bits of the working map and causes the adjustment
2134 * of the binary buddy system described by the dmap's dmtree
2135 * leaves to reflect the bits allocated. it also causes the
2136 * dmap's dmtree, as a whole, to reflect the allocated range.
2137 *
2138 * PARAMETERS:
2139 * bmp - pointer to bmap descriptor
2140 * dp - pointer to dmap to allocate bits from.
2141 * blkno - starting block number of the bits to be allocated.
2142 * nblocks - number of bits to be allocated.
2143 *
2144 * RETURN VALUES: none
2145 *
2146 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2147 */
2150 {
2156 /* pick up a pointer to the leaves of the dmap tree */
2159 /* determine the bit number and word within the dmap of the
2160 * starting block.
2161 */
2165 /* block range better be within the dmap */
2168 /* allocate the bits of the dmap's words corresponding to the block
2169 * range. not all bits of the first and last words may be contained
2170 * within the block range. if this is the case, we'll work against
2171 * those words (i.e. partial first and/or last) on an individual basis
2172 * (a single pass), allocating the bits of interest by hand and
2173 * updating the leaf corresponding to the dmap word. a single pass
2174 * will be used for all dmap words fully contained within the
2175 * specified range. within this pass, the bits of all fully contained
2176 * dmap words will be marked as free in a single shot and the leaves
2177 * will be updated. a single leaf may describe the free space of
2178 * multiple dmap words, so we may update only a subset of the actual
2179 * leaves corresponding to the dmap words of the block range.
2180 */
2182 /* determine the bit number within the word and
2183 * the number of bits within the word.
2184 */
2188 /* check if only part of a word is to be allocated.
2189 */
2191 /* allocate (set to 1) the appropriate bits within
2192 * this dmap word.
2193 */
2197 /* update the leaf for this dmap word. in addition
2198 * to setting the leaf value to the binary buddy max
2199 * of the updated dmap word, dbSplit() will split
2200 * the binary system of the leaves if need be.
2201 */
2207 /* one or more dmap words are fully contained
2208 * within the block range. determine how many
2209 * words and allocate (set to 1) the bits of these
2210 * words.
2211 */
2215 /* determine how many bits.
2216 */
2219 /* now update the appropriate leaves to reflect
2220 * the allocated words.
2221 */
2225 "dbAllocBits: leaf page "
2228 }
2230 /* determine what the leaf value should be
2231 * updated to as the minimum of the l2 number
2232 * of bits being allocated and the l2 number
2233 * of bits currently described by this leaf.
2234 */
2237 /* update the leaf to reflect the allocation.
2238 * in addition to setting the leaf value to
2239 * NOFREE, dbSplit() will split the binary
2240 * system of the leaves to reflect the current
2241 * allocation (size).
2242 */
2245 /* get the number of dmap words handled */
2248 }
2249 }
2250 }
2252 /* update the free count for this dmap */
2257 /* if this allocation group is completely free,
2258 * update the maximum allocation group number if this allocation
2259 * group is the new max.
2260 */
2265 /* update the free count for the allocation group and map */
2270 }
2273 /*
2274 * NAME: dbFreeBits()
2275 *
2276 * FUNCTION: free a specified block range from a dmap.
2277 *
2278 * this routine updates the dmap to reflect the working
2279 * state allocation of the specified block range. it directly
2280 * updates the bits of the working map and causes the adjustment
2281 * of the binary buddy system described by the dmap's dmtree
2282 * leaves to reflect the bits freed. it also causes the dmap's
2283 * dmtree, as a whole, to reflect the deallocated range.
2284 *
2285 * PARAMETERS:
2286 * bmp - pointer to bmap descriptor
2287 * dp - pointer to dmap to free bits from.
2288 * blkno - starting block number of the bits to be freed.
2289 * nblocks - number of bits to be freed.
2290 *
2291 * RETURN VALUES: none
2292 *
2293 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2294 */
2297 {
2302 /* determine the bit number and word within the dmap of the
2303 * starting block.
2304 */
2308 /* block range better be within the dmap.
2309 */
2312 /* free the bits of the dmaps words corresponding to the block range.
2313 * not all bits of the first and last words may be contained within
2314 * the block range. if this is the case, we'll work against those
2315 * words (i.e. partial first and/or last) on an individual basis
2316 * (a single pass), freeing the bits of interest by hand and updating
2317 * the leaf corresponding to the dmap word. a single pass will be used
2318 * for all dmap words fully contained within the specified range.
2319 * within this pass, the bits of all fully contained dmap words will
2320 * be marked as free in a single shot and the leaves will be updated. a
2321 * single leaf may describe the free space of multiple dmap words,
2322 * so we may update only a subset of the actual leaves corresponding
2323 * to the dmap words of the block range.
2324 *
2325 * dbJoin() is used to update leaf values and will join the binary
2326 * buddy system of the leaves if the new leaf values indicate this
2327 * should be done.
2328 */
2330 /* determine the bit number within the word and
2331 * the number of bits within the word.
2332 */
2336 /* check if only part of a word is to be freed.
2337 */
2339 /* free (zero) the appropriate bits within this
2340 * dmap word.
2341 */
2346 /* update the leaf for this dmap word.
2347 */
2353 /* one or more dmap words are fully contained
2354 * within the block range. determine how many
2355 * words and free (zero) the bits of these words.
2356 */
2360 /* determine how many bits.
2361 */
2364 /* now update the appropriate leaves to reflect
2365 * the freed words.
2366 */
2368 /* determine what the leaf value should be
2369 * updated to as the minimum of the l2 number
2370 * of bits being freed and the l2 (max) number
2371 * of bits that can be described by this leaf.
2372 */
2373 size =
2378 /* update the leaf.
2379 */
2382 /* get the number of dmap words handled.
2383 */
2386 }
2387 }
2388 }
2390 /* update the free count for this dmap.
2391 */
2396 /* update the free count for the allocation group and
2397 * map.
2398 */
2403 /* check if this allocation group is not completely free and
2404 * if it is currently the maximum (rightmost) allocation group.
2405 * if so, establish the new maximum allocation group number by
2406 * searching left for the first allocation group with allocation.
2407 */
2416 }
2418 /* re-establish the allocation group preference if the
2419 * current preference is right of the maximum allocation
2420 * group.
2421 */
2424 }
2427 }
2430 /*
2431 * NAME: dbAdjCtl()
2432 *
2433 * FUNCTION: adjust a dmap control page at a specified level to reflect
2434 * the change in a lower level dmap or dmap control page's
2435 * maximum string of free blocks (i.e. a change in the root
2436 * of the lower level object's dmtree) due to the allocation
2437 * or deallocation of a range of blocks with a single dmap.
2438 *
2439 * on entry, this routine is provided with the new value of
2440 * the lower level dmap or dmap control page root and the
2441 * starting block number of the block range whose allocation
2442 * or deallocation resulted in the root change. this range
2443 * is respresented by a single leaf of the current dmapctl
2444 * and the leaf will be updated with this value, possibly
2445 * causing a binary buddy system within the leaves to be
2446 * split or joined. the update may also cause the dmapctl's
2447 * dmtree to be updated.
2448 *
2449 * if the adjustment of the dmap control page, itself, causes its
2450 * root to change, this change will be bubbled up to the next dmap
2451 * control level by a recursive call to this routine, specifying
2452 * the new root value and the next dmap control page level to
2453 * be adjusted.
2454 * PARAMETERS:
2455 * bmp - pointer to bmap descriptor
2456 * blkno - the first block of a block range within a dmap. it is
2457 * the allocation or deallocation of this block range that
2458 * requires the dmap control page to be adjusted.
2459 * newval - the new value of the lower level dmap or dmap control
2460 * page root.
2461 * alloc - TRUE if adjustment is due to an allocation.
2462 * level - current level of dmap control page (i.e. L0, L1, L2) to
2463 * be adjusted.
2464 *
2465 * RETURN VALUES:
2466 * 0 - success
2467 * -EIO - i/o error
2468 *
2469 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2470 */
2471 static int
2473 {
2475 s8 oldroot;
2477 s64 lblkno;
2481 /* get the buffer for the dmap control page for the specified
2482 * block number and control page level.
2483 */
2495 }
2497 /* determine the leaf number corresponding to the block and
2498 * the index within the dmap control tree.
2499 */
2503 /* save the current leaf value and the current root level (i.e.
2504 * maximum l2 free string described by this dmapctl).
2505 */
2509 /* check if this is a control page update for an allocation.
2510 * if so, update the leaf to reflect the new leaf value using
2511 * dbSplit(); otherwise (deallocation), use dbJoin() to udpate
2512 * the leaf with the new value. in addition to updating the
2513 * leaf, dbSplit() will also split the binary buddy system of
2514 * the leaves, if required, and bubble new values within the
2515 * dmapctl tree, if required. similarly, dbJoin() will join
2516 * the binary buddy system of leaves and bubble new values up
2517 * the dmapctl tree as required by the new leaf value.
2518 */
2520 /* check if we are in the middle of a binary buddy
2521 * system. this happens when we are performing the
2522 * first allocation out of an allocation group that
2523 * is part (not the first part) of a larger binary
2524 * buddy system. if we are in the middle, back split
2525 * the system prior to calling dbSplit() which assumes
2526 * that it is at the front of a binary buddy system.
2527 */
2531 }
2535 }
2537 /* check if the root of the current dmap control page changed due
2538 * to the update and if the current dmap control page is not at
2539 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2540 * root changed and this is not the top level), call this routine
2541 * again (recursion) for the next higher level of the mapping to
2542 * reflect the change in root for the current dmap control page.
2543 */
2545 /* are we below the top level of the map. if so,
2546 * bubble the root up to the next higher level.
2547 */
2549 /* bubble up the new root of this dmap control page to
2550 * the next level.
2551 */
2555 /* something went wrong in bubbling up the new
2556 * root value, so backout the changes to the
2557 * current dmap control page.
2558 */
2561 oldval);
2563 /* the dbJoin() above might have
2564 * caused a larger binary buddy system
2565 * to form and we may now be in the
2566 * middle of it. if this is the case,
2567 * back split the buddies.
2568 */
2574 }
2576 /* release the buffer and return the error.
2577 */
2580 }
2582 /* we're at the top level of the map. update
2583 * the bmap control page to reflect the size
2584 * of the maximum free buddy system.
2585 */
2589 "dbAdjCtl: the maximum free buddy is "
2591 }
2593 }
2594 }
2596 /* write the buffer.
2597 */
2601 }
2604 /*
2605 * NAME: dbSplit()
2606 *
2607 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2608 * the leaf from the binary buddy system of the dmtree's
2609 * leaves, as required.
2610 *
2611 * PARAMETERS:
2612 * tp - pointer to the tree containing the leaf.
2613 * leafno - the number of the leaf to be updated.
2614 * splitsz - the size the binary buddy system starting at the leaf
2615 * must be split to, specified as the log2 number of blocks.
2616 * newval - the new value for the leaf.
2617 *
2618 * RETURN VALUES: none
2619 *
2620 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2621 */
2623 {
2628 /* check if the leaf needs to be split.
2629 */
2631 /* the split occurs by cutting the buddy system in half
2632 * at the specified leaf until we reach the specified
2633 * size. pick up the starting split size (current size
2634 * - 1 in l2) and the corresponding buddy size.
2635 */
2639 /* split until we reach the specified size.
2640 */
2642 /* update the buddy's leaf with its new value.
2643 */
2646 /* on to the next size and buddy.
2647 */
2650 }
2651 }
2653 /* adjust the dmap tree to reflect the specified leaf's new
2654 * value.
2655 */
2657 }
2660 /*
2661 * NAME: dbBackSplit()
2662 *
2663 * FUNCTION: back split the binary buddy system of dmtree leaves
2664 * that hold a specified leaf until the specified leaf
2665 * starts its own binary buddy system.
2666 *
2667 * the allocators typically perform allocations at the start
2668 * of binary buddy systems and dbSplit() is used to accomplish
2669 * any required splits. in some cases, however, allocation
2670 * may occur in the middle of a binary system and requires a
2671 * back split, with the split proceeding out from the middle of
2672 * the system (less efficient) rather than the start of the
2673 * system (more efficient). the cases in which a back split
2674 * is required are rare and are limited to the first allocation
2675 * within an allocation group which is a part (not first part)
2676 * of a larger binary buddy system and a few exception cases
2677 * in which a previous join operation must be backed out.
2678 *
2679 * PARAMETERS:
2680 * tp - pointer to the tree containing the leaf.
2681 * leafno - the number of the leaf to be updated.
2682 *
2683 * RETURN VALUES: none
2684 *
2685 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2686 */
2688 {
2693 /* leaf should be part (not first part) of a binary
2694 * buddy system.
2695 */
2698 /* the back split is accomplished by iteratively finding the leaf
2699 * that starts the buddy system that contains the specified leaf and
2700 * splitting that system in two. this iteration continues until
2701 * the specified leaf becomes the start of a buddy system.
2702 *
2703 * determine maximum possible l2 size for the specified leaf.
2704 */
2705 size =
2709 /* determine the number of leaves covered by this size. this
2710 * is the buddy size that we will start with as we search for
2711 * the buddy system that contains the specified leaf.
2712 */
2715 /* back split.
2716 */
2718 /* find the leftmost buddy leaf.
2719 */
2724 /* determine the buddy.
2725 */
2728 /* check if this buddy is the start of the system.
2729 */
2731 /* split the leaf at the start of the
2732 * system in two.
2733 */
2737 }
2738 }
2739 }
2742 }
2745 /*
2746 * NAME: dbJoin()
2747 *
2748 * FUNCTION: update the leaf of a dmtree with a new value, joining
2749 * the leaf with other leaves of the dmtree into a multi-leaf
2750 * binary buddy system, as required.
2751 *
2752 * PARAMETERS:
2753 * tp - pointer to the tree containing the leaf.
2754 * leafno - the number of the leaf to be updated.
2755 * newval - the new value for the leaf.
2756 *
2757 * RETURN VALUES: none
2758 */
2760 {
2764 /* can the new leaf value require a join with other leaves ?
2765 */
2767 /* pickup a pointer to the leaves of the tree.
2768 */
2771 /* try to join the specified leaf into a large binary
2772 * buddy system. the join proceeds by attempting to join
2773 * the specified leafno with its buddy (leaf) at new value.
2774 * if the join occurs, we attempt to join the left leaf
2775 * of the joined buddies with its buddy at new value + 1.
2776 * we continue to join until we find a buddy that cannot be
2777 * joined (does not have a value equal to the size of the
2778 * last join) or until all leaves have been joined into a
2779 * single system.
2780 *
2781 * get the buddy size (number of words covered) of
2782 * the new value.
2783 */
2786 /* try to join.
2787 */
2789 /* get the buddy leaf.
2790 */
2793 /* if the leaf's new value is greater than its
2794 * buddy's value, we join no more.
2795 */
2801 /* check which (leafno or buddy) is the left buddy.
2802 * the left buddy gets to claim the blocks resulting
2803 * from the join while the right gets to claim none.
2804 * the left buddy is also eligable to participate in
2805 * a join at the next higher level while the right
2806 * is not.
2807 *
2808 */
2810 /* leafno is the left buddy.
2811 */
2814 /* buddy is the left buddy and becomes
2815 * leafno.
2816 */
2819 }
2821 /* on to try the next join.
2822 */
2825 }
2826 }
2828 /* update the leaf value.
2829 */
2831 }
2834 /*
2835 * NAME: dbAdjTree()
2836 *
2837 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2838 * the dmtree, as required, to reflect the new leaf value.
2839 * the combination of any buddies must already be done before
2840 * this is called.
2841 *
2842 * PARAMETERS:
2843 * tp - pointer to the tree to be adjusted.
2844 * leafno - the number of the leaf to be updated.
2845 * newval - the new value for the leaf.
2846 *
2847 * RETURN VALUES: none
2848 */
2850 {
2854 /* pick up the index of the leaf for this leafno.
2855 */
2858 /* is the current value the same as the old value ? if so,
2859 * there is nothing to do.
2860 */
2864 /* set the new value.
2865 */
2868 /* bubble the new value up the tree as required.
2869 */
2871 /* get the index of the first leaf of the 4 leaf
2872 * group containing the specified leaf (leafno).
2873 */
2876 /* get the index of the parent of this 4 leaf group.
2877 */
2880 /* determine the maximum of the 4 leaves.
2881 */
2884 /* if the maximum of the 4 is the same as the
2885 * parent's value, we're done.
2886 */
2890 /* parent gets new value.
2891 */
2894 /* parent becomes leaf for next go-round.
2895 */
2897 }
2898 }
2901 /*
2902 * NAME: dbFindLeaf()
2903 *
2904 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2905 * the index of a leaf describing the free blocks if
2906 * sufficient free blocks are found.
2907 *
2908 * the search starts at the top of the dmtree_t tree and
2909 * proceeds down the tree to the leftmost leaf with sufficient
2910 * free space.
2911 *
2912 * PARAMETERS:
2913 * tp - pointer to the tree to be searched.
2914 * l2nb - log2 number of free blocks to search for.
2915 * leafidx - return pointer to be set to the index of the leaf
2916 * describing at least l2nb free blocks if sufficient
2917 * free blocks are found.
2918 *
2919 * RETURN VALUES:
2920 * 0 - success
2921 * -ENOSPC - insufficient free blocks.
2922 */
2924 {
2927 /* first check the root of the tree to see if there is
2928 * sufficient free space.
2929 */
2933 /* sufficient free space available. now search down the tree
2934 * starting at the next level for the leftmost leaf that
2935 * describes sufficient free space.
2936 */
2939 /* search the four nodes at this level, starting from
2940 * the left.
2941 */
2943 /* sufficient free space found. move to the next
2944 * level (or quit if this is the last level).
2945 */
2948 }
2950 /* better have found something since the higher
2951 * levels of the tree said it was here.
2952 */
2954 }
2956 /* set the return to the leftmost leaf describing sufficient
2957 * free space.
2958 */
2962 }
2965 /*
2966 * NAME: dbFindBits()
2967 *
2968 * FUNCTION: find a specified number of binary buddy free bits within a
2969 * dmap bitmap word value.
2970 *
2971 * this routine searches the bitmap value for (1 << l2nb) free
2972 * bits at (1 << l2nb) alignments within the value.
2973 *
2974 * PARAMETERS:
2975 * word - dmap bitmap word value.
2976 * l2nb - number of free bits specified as a log2 number.
2977 *
2978 * RETURN VALUES:
2979 * starting bit number of free bits.
2980 */
2982 {
2984 u32 mask;
2986 /* get the number of bits.
2987 */
2991 /* complement the word so we can use a mask (i.e. 0s represent
2992 * free bits) and compute the mask.
2993 */
2997 /* scan the word for nb free bits at nb alignments.
2998 */
3002 }
3006 /* return the bit number.
3007 */
3009 }
3012 /*
3013 * NAME: dbMaxBud(u8 *cp)
3014 *
3015 * FUNCTION: determine the largest binary buddy string of free
3016 * bits within 32-bits of the map.
3017 *
3018 * PARAMETERS:
3019 * cp - pointer to the 32-bit value.
3020 *
3021 * RETURN VALUES:
3022 * largest binary buddy of free bits within a dmap word.
3023 */
3025 {
3028 /* check if the wmap word is all free. if so, the
3029 * free buddy size is BUDMIN.
3030 */
3034 /* check if the wmap word is half free. if so, the
3035 * free buddy size is BUDMIN-1.
3036 */
3040 /* not all free or half free. determine the free buddy
3041 * size thru table lookup using quarters of the wmap word.
3042 */
3046 }
3049 /*
3050 * NAME: cnttz(uint word)
3051 *
3052 * FUNCTION: determine the number of trailing zeros within a 32-bit
3053 * value.
3054 *
3055 * PARAMETERS:
3056 * value - 32-bit value to be examined.
3057 *
3058 * RETURN VALUES:
3059 * count of trailing zeros
3060 */
3062 {
3068 }
3071 }
3074 /*
3075 * NAME: cntlz(u32 value)
3076 *
3077 * FUNCTION: determine the number of leading zeros within a 32-bit
3078 * value.
3079 *
3080 * PARAMETERS:
3081 * value - 32-bit value to be examined.
3082 *
3083 * RETURN VALUES:
3084 * count of leading zeros
3085 */
3087 {
3093 }
3095 }
3098 /*
3099 * NAME: blkstol2(s64 nb)
3100 *
3101 * FUNCTION: convert a block count to its log2 value. if the block
3102 * count is not a l2 multiple, it is rounded up to the next
3103 * larger l2 multiple.
3104 *
3105 * PARAMETERS:
3106 * nb - number of blocks
3107 *
3108 * RETURN VALUES:
3109 * log2 number of blocks
3110 */
3112 {
3118 /* count the leading bits.
3119 */
3121 /* leading bit found.
3122 */
3124 /* determine the l2 value.
3125 */
3128 /* check if we need to round up.
3129 */
3131 l2nb++;
3134 }
3135 }
3138 }
3141 /*
3142 * NAME: dbAllocBottomUp()
3143 *
3144 * FUNCTION: alloc the specified block range from the working block
3145 * allocation map.
3146 *
3147 * the blocks will be alloc from the working map one dmap
3148 * at a time.
3149 *
3150 * PARAMETERS:
3151 * ip - pointer to in-core inode;
3152 * blkno - starting block number to be freed.
3153 * nblocks - number of blocks to be freed.
3154 *
3155 * RETURN VALUES:
3156 * 0 - success
3157 * -EIO - i/o error
3158 */
3160 {
3170 /* block to be allocated better be within the mapsize. */
3173 /*
3174 * allocate the blocks a dmap at a time.
3175 */
3178 /* release previous dmap if any */
3181 }
3183 /* get the buffer for the current dmap. */
3189 }
3192 /* determine the number of blocks to be allocated from
3193 * this dmap.
3194 */
3199 /* allocate the blocks. */
3204 }
3207 }
3209 /* write the last buffer. */
3215 }
3220 {
3226 /* save the current value of the root (i.e. maximum free string)
3227 * of the dmap tree.
3228 */
3231 /* pick up a pointer to the leaves of the dmap tree */
3234 /* determine the bit number and word within the dmap of the
3235 * starting block.
3236 */
3240 /* block range better be within the dmap */
3243 /* allocate the bits of the dmap's words corresponding to the block
3244 * range. not all bits of the first and last words may be contained
3245 * within the block range. if this is the case, we'll work against
3246 * those words (i.e. partial first and/or last) on an individual basis
3247 * (a single pass), allocating the bits of interest by hand and
3248 * updating the leaf corresponding to the dmap word. a single pass
3249 * will be used for all dmap words fully contained within the
3250 * specified range. within this pass, the bits of all fully contained
3251 * dmap words will be marked as free in a single shot and the leaves
3252 * will be updated. a single leaf may describe the free space of
3253 * multiple dmap words, so we may update only a subset of the actual
3254 * leaves corresponding to the dmap words of the block range.
3255 */
3257 /* determine the bit number within the word and
3258 * the number of bits within the word.
3259 */
3263 /* check if only part of a word is to be allocated.
3264 */
3266 /* allocate (set to 1) the appropriate bits within
3267 * this dmap word.
3268 */
3272 word++;
3274 /* one or more dmap words are fully contained
3275 * within the block range. determine how many
3276 * words and allocate (set to 1) the bits of these
3277 * words.
3278 */
3282 /* determine how many bits */
3285 }
3286 }
3288 /* update the free count for this dmap */
3291 /* reconstruct summary tree */
3296 /* if this allocation group is completely free,
3297 * update the highest active allocation group number
3298 * if this allocation group is the new max.
3299 */
3304 /* update the free count for the allocation group and map */
3310 /* if the root has not changed, done. */
3314 /* root changed. bubble the change up to the dmap control pages.
3315 * if the adjustment of the upper level control pages fails,
3316 * backout the bit allocation (thus making everything consistent).
3317 */
3322 }
3325 /*
3326 * NAME: dbExtendFS()
3327 *
3328 * FUNCTION: extend bmap from blkno for nblocks;
3329 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3330 *
3331 * L2
3332 * |
3333 * L1---------------------------------L1
3334 * | |
3335 * L0---------L0---------L0 L0---------L0---------L0
3336 * | | | | | |
3337 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3338 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3339 *
3340 * <---old---><----------------------------extend----------------------->
3341 */
3343 {
3347 s64 newsize;
3348 s64 p;
3355 s64 ag_rem;
3362 /*
3363 * initialize bmap control page.
3364 *
3365 * all the data in bmap control page should exclude
3366 * the mkfs hidden dmap page.
3367 */
3369 /* update mapsize */
3373 /* compute new AG size */
3380 /* compute new number of AG */
3385 /*
3386 * reconfigure db_agfree[]
3387 * from old AG configuration to new AG configuration;
3388 *
3389 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3390 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3391 * note: new AG size = old AG size * (2**x).
3392 */
3400 /* coalesce cotiguous k AGs; */
3402 /* merge AGi to AGn */
3404 }
3405 }
3411 /*
3412 * update highest active ag number
3413 */
3417 /*
3418 * extend bmap
3419 *
3420 * update bit maps and corresponding level control pages;
3421 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3422 */
3423 extend:
3424 /* get L2 page */
3430 }
3433 /* compute start L1 */
3438 /*
3439 * extend each L1 in L2
3440 */
3442 /* get L1 page */
3444 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3450 /* compute start L0 */
3456 /* assign/init L1 page */
3463 /* compute start L0 */
3467 }
3469 /*
3470 * extend each L0 in L1
3471 */
3473 /* get L0 page */
3475 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3482 /* compute start dmap */
3484 L2BPERDMAP;
3490 /* assign/init L0 page */
3497 /* compute start dmap */
3501 }
3503 /*
3504 * extend each dmap in L0
3505 */
3507 /*
3508 * reconstruct the dmap page, and
3509 * initialize corresponding parent L0 leaf
3510 */
3512 /* read in dmap page: */
3519 /* assign/init dmap page */
3526 }
3537 l0leaf++;
3546 /*
3547 * build current L0 page from its leaves, and
3548 * initialize corresponding parent L1 leaf
3549 */
3557 /* more than 1 L0 ? */
3561 /* summarize in global bmap page */
3566 }
3567 }
3570 /*
3571 * build current L1 page from its leaves, and
3572 * initialize corresponding parent L2 leaf
3573 */
3581 /* more than 1 L1 ? */
3585 /* summarize in global bmap page */
3589 }
3590 }
3595 errout:
3603 /*
3604 * finalize bmap control page
3605 */
3606 finalize:
3609 }
3612 /*
3613 * dbFinalizeBmap()
3614 */
3616 {
3622 /*
3623 * finalize bmap control page
3624 */
3625 //finalize:
3626 /*
3627 * compute db_agpref: preferred ag to allocate from
3628 * (the leftmost ag with average free space in it);
3629 */
3630 //agpref:
3631 /* get the number of active ags and inacitve ags */
3636 /* determine how many blocks are in the inactive allocation
3637 * groups. in doing this, we must account for the fact that
3638 * the rightmost group might be a partial group (i.e. file
3639 * system size is not a multiple of the group size).
3640 */
3645 /* determine how many free blocks are in the active
3646 * allocation groups plus the average number of free blocks
3647 * within the active ags.
3648 */
3652 /* if the preferred allocation group has not average free space.
3653 * re-establish the preferred group as the leftmost
3654 * group with average free space.
3655 */
3661 }
3665 }
3666 }
3668 /*
3669 * compute db_aglevel, db_agheigth, db_width, db_agstart:
3670 * an ag is covered in aglevel dmapctl summary tree,
3671 * at agheight level height (from leaf) with agwidth number of nodes
3672 * each, which starts at agstart index node of the smmary tree node
3673 * array;
3674 */
3676 l2nl =
3681 i--) {
3684 }
3686 }
3689 /*
3690 * NAME: dbInitDmap()/ujfs_idmap_page()
3691 *
3692 * FUNCTION: initialize working/persistent bitmap of the dmap page
3693 * for the specified number of blocks:
3694 *
3695 * at entry, the bitmaps had been initialized as free (ZEROS);
3696 * The number of blocks will only account for the actually
3697 * existing blocks. Blocks which don't actually exist in
3698 * the aggregate will be marked as allocated (ONES);
3699 *
3700 * PARAMETERS:
3701 * dp - pointer to page of map
3702 * nblocks - number of blocks this page
3703 *
3704 * RETURNS: NONE
3705 */
3707 {
3710 /* starting block number within the dmap */
3721 }
3726 }
3728 /* word number containing start block number */
3731 /*
3732 * free the bits corresponding to the block range (ZEROS):
3733 * note: not all bits of the first and last words may be contained
3734 * within the block range.
3735 */
3737 /* number of bits preceding range to be freed in the word */
3739 /* number of bits to free in the word */
3742 /* is partial word to be freed ? */
3744 /* free (set to 0) from the bitmap word */
3750 /* skip the word freed */
3751 w++;
3753 /* free (set to 0) contiguous bitmap words */
3758 /* skip the words freed */
3761 }
3762 }
3764 /*
3765 * mark bits following the range to be freed (non-existing
3766 * blocks) as allocated (ONES)
3767 */
3772 /* the first word beyond the end of existing blocks */
3775 /* does nblocks fall on a 32-bit boundary ? */
3778 /* mark a partial word allocated */
3780 w++;
3781 }
3783 /* set the rest of the words in the page to allocated (ONES) */
3787 /*
3788 * init tree
3789 */
3790 initTree:
3792 }
3795 /*
3796 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3797 *
3798 * FUNCTION: initialize summary tree of the specified dmap:
3799 *
3800 * at entry, bitmap of the dmap has been initialized;
3801 *
3802 * PARAMETERS:
3803 * dp - dmap to complete
3804 * blkno - starting block number for this dmap
3805 * treemax - will be filled in with max free for this dmap
3806 *
3807 * RETURNS: max free string at the root of the tree
3808 */
3810 {
3815 /* init fixed info of tree */
3823 /* init each leaf from corresponding wmap word:
3824 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3825 * bitmap word are allocated.
3826 */
3831 /* build the dmap's binary buddy summary tree */
3833 }
3836 /*
3837 * NAME: dbInitTree()/ujfs_adjtree()
3838 *
3839 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3840 *
3841 * at entry, the leaves of the tree has been initialized
3842 * from corresponding bitmap word or root of summary tree
3843 * of the child control page;
3844 * configure binary buddy system at the leaf level, then
3845 * bubble up the values of the leaf nodes up the tree.
3846 *
3847 * PARAMETERS:
3848 * cp - Pointer to the root of the tree
3849 * l2leaves- Number of leaf nodes as a power of 2
3850 * l2min - Number of blocks that can be covered by a leaf
3851 * as a power of 2
3852 *
3853 * RETURNS: max free string at the root of the tree
3854 */
3856 {
3863 /* Determine the maximum free string possible for the leaves */
3866 /*
3867 * configure the leaf levevl into binary buddy system
3868 *
3869 * Try to combine buddies starting with a buddy size of 1
3870 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3871 * can be combined if both buddies have a maximum free of l2min;
3872 * the combination will result in the left-most buddy leaf having
3873 * a maximum free of l2min+1.
3874 * After processing all buddies for a given size, process buddies
3875 * at the next higher buddy size (i.e. current size * 2) and
3876 * the next maximum free (current free + 1).
3877 * This continues until the maximum possible buddy combination
3878 * yields maximum free.
3879 */
3882 /* get next buddy size == current buddy pair size */
3885 /* scan each adjacent buddy pair at current buddy size */
3889 /* coalesce if both adjacent buddies are max free */
3893 }
3894 }
3895 }
3897 /*
3898 * bubble summary information of leaves up the tree.
3899 *
3900 * Starting at the leaf node level, the four nodes described by
3901 * the higher level parent node are compared for a maximum free and
3902 * this maximum becomes the value of the parent node.
3903 * when all lower level nodes are processed in this fashion then
3904 * move up to the next level (parent becomes a lower level node) and
3905 * continue the process for that level.
3906 */
3910 /* get index of 1st node of parent level */
3913 /* set the value of the parent node as the maximum
3914 * of the four nodes of the current level.
3915 */
3919 }
3922 }
3925 /*
3926 * dbInitDmapCtl()
3927 *
3928 * function: initialize dmapctl page
3929 */
3940 /*
3941 * initialize the leaves of current level that were not covered
3942 * by the specified input block range (i.e. the leaves have no
3943 * low level dmapctl or dmap).
3944 */
3949 /* build the dmap's binary buddy summary tree */
3951 }
3954 /*
3955 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3956 *
3957 * FUNCTION: Determine log2(allocation group size) from aggregate size
3958 *
3959 * PARAMETERS:
3960 * nblocks - Number of blocks in aggregate
3961 *
3962 * RETURNS: log2(allocation group size) in aggregate blocks
3963 */
3965 {
3966 s64 sz;
3967 s64 m;
3973 /* round up aggregate size to power of 2 */
3978 }
3984 /* agsize = roundupSize/max_number_of_ag */
3986 }
3989 /*
3990 * NAME: dbMapFileSizeToMapSize()
3991 *
3992 * FUNCTION: compute number of blocks the block allocation map file
3993 * can cover from the map file size;
3994 *
3995 * RETURNS: Number of blocks which can be covered by this block map file;
3996 */
3998 /*
3999 * maximum number of map pages at each level including control pages
4000 */
4001 #define MAXL0PAGES (1 + LPERCTL)
4002 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
4003 #define MAXL2PAGES (1 + LPERCTL * MAXL1PAGES)
4005 /*
4006 * convert number of map pages to the zero origin top dmapctl level
4007 */
4008 #define BMAPPGTOLEV(npages) \
4009 (((npages) <= 3 + MAXL0PAGES) ? 0 \
4010 : ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4013 {
4015 s64 nblocks;
4024 /* At each level, accumulate the number of dmap pages covered by
4025 * the number of full child levels below it;
4026 * repeat for the last incomplete child level.
4027 */
4030 /* skip higher level control pages above top level covered by map */
4034 factor =
4040 /* pages in last/incomplete child */
4042 /* skip incomplete child's level control page */
4043 npages--;
4044 }
4046 /* convert the number of dmaps into the number of blocks
4047 * which can be covered by the dmaps;
4048 */
4052 }
4055 #ifdef _JFS_DEBUG_DMAP
4056 /*
4057 * DBinitmap()
4058 */
4060 {
4078 /* Need to initialize from disk map pages
4079 */
4084 db_l2nbperpage);
4090 }
4097 }
4100 }
4103 /*
4104 * DBAlloc()
4105 */
4107 {
4109 u32 mask;
4125 dbmap++;
4128 }
4129 }
4132 /*
4133 * DBFree()
4134 */
4136 {
4138 u32 mask;
4154 dbmap++;
4157 }
4158 }
4161 /*
4162 * DBAllocCK()
4163 */
4165 {
4167 u32 mask;
4182 dbmap++;
4185 }
4186 }
4189 /*
4190 * DBFreeCK()
4191 */
4193 {
4195 u32 mask;
4210 dbmap++;
4213 }
4214 }
4217 /*
4218 * dbPrtMap()
4219 */
4221 {
4235 }
4238 /*
4239 * dbPrtCtl()
4240 */
4242 {
4259 }
4270 }
4271 }