| blob | 19ba00f28547bcf0d31fc8bc69ed34c340660c85 |
1 /* -*- mode: c; c-basic-offset: 8; -*-
2 * vim: noexpandtab sw=8 ts=8 sts=0:
3 *
4 * suballoc.c
5 *
6 * metadata alloc and free
7 * Inspired by ext3 block groups.
8 *
9 * Copyright (C) 2002, 2004 Oracle. All rights reserved.
10 *
11 * This program is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU General Public
13 * License as published by the Free Software Foundation; either
14 * version 2 of the License, or (at your option) any later version.
15 *
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public
22 * License along with this program; if not, write to the
23 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24 * Boston, MA 021110-1307, USA.
25 */
27 #include <linux/fs.h>
28 #include <linux/types.h>
29 #include <linux/slab.h>
30 #include <linux/highmem.h>
32 #define MLOG_MASK_PREFIX ML_DISK_ALLOC
33 #include <cluster/masklog.h>
50 #define NOT_ALLOC_NEW_GROUP 0
51 #define ALLOC_NEW_GROUP 0x1
52 #define ALLOC_GROUPS_FROM_GLOBAL 0x2
54 #define OCFS2_MAX_TO_STEAL 1024
62 u64 group_blkno,
63 u16 my_chain,
68 u64 max_block,
75 u64 max_block,
80 u64 max_block,
85 u32 bits_wanted,
86 u32 min_bits,
103 u16 chain);
105 u32 wanted);
107 u64 bg_blkno,
108 u16 bg_bit_off);
110 u64 data_blkno,
119 {
130 }
133 }
136 {
139 }
142 {
144 }
146 #define do_error(fmt, ...) \
147 do{ \
148 if (resize) \
150 else \
151 ocfs2_error(sb, fmt, ##__VA_ARGS__); \
152 } while (0)
157 {
165 }
173 }
181 }
190 }
199 }
202 }
208 {
219 }
227 }
229 /* In resize, we may meet the case bg_chain == cl_next_free_rec. */
238 }
241 }
243 #undef do_error
245 /*
246 * This version only prints errors. It does not fail the filesystem, and
247 * exists only for resize.
248 */
252 {
258 /*
259 * If the ecc fails, we return the error but otherwise
260 * leave the filesystem running. We know any error is
261 * local to this block.
262 */
274 }
278 {
287 /*
288 * If the ecc fails, we return the error but otherwise
289 * leave the filesystem running. We know any error is
290 * local to this block.
291 */
296 /*
297 * Errors after here are fatal.
298 */
301 }
305 {
310 ocfs2_validate_group_descriptor);
318 }
320 /* If ocfs2_read_block() got us a new bh, pass it up. */
324 out:
326 }
331 u64 group_blkno,
332 u16 my_chain,
334 {
348 }
352 bg_bh,
353 OCFS2_JOURNAL_ACCESS_CREATE);
357 }
368 /* set the 1st bit in the bitmap to account for the descriptor block */
376 /* There is no need to zero out or otherwise initialize the
377 * other blocks in a group - All valid FS metadata in a block
378 * group stores the superblock fs_generation value at
379 * allocation time. */
381 bail:
384 }
387 {
395 curr++;
396 }
398 }
400 /*
401 * We expect the block group allocator to already be locked.
402 */
406 u64 max_block,
409 {
416 u16 alloc_rec;
417 u64 bg_blkno;
433 }
443 }
449 }
451 handle,
452 ac,
460 }
464 /* setup the group */
474 }
478 alloc_inode,
479 bg_bh,
480 bg_blkno,
481 alloc_rec,
482 cl);
486 }
495 }
513 }
525 /* save the new last alloc group so that the caller can cache it. */
529 bail:
540 }
545 u32 slot,
548 {
554 u32 free_bits;
562 }
573 }
580 /* The bh was validated by the inode read inside
581 * ocfs2_inode_lock(). Any corruption is a code bug. */
589 }
595 /* cluster bitmap never grows */
601 }
609 }
618 }
621 /* You should never ask for this much metadata */
625 }
629 bail:
634 }
637 {
642 }
645 {
650 }
653 {
656 }
659 {
666 }
669 {
680 }
683 {
685 }
688 {
690 }
695 {
699 /* Start to steal resource from the first slot after ours. */
711 type,
713 NOT_ALLOC_NEW_GROUP);
717 }
720 }
723 }
727 {
729 }
733 {
735 }
740 {
749 }
761 EXTENT_ALLOC_SYSTEM_INODE,
763 ALLOC_NEW_GROUP);
774 }
778 extent_steal:
785 }
788 bail:
792 }
796 }
801 {
804 ac);
805 }
809 {
812 u64 alloc_group;
819 }
826 /*
827 * stat(2) can't handle i_ino > 32bits, so we tell the
828 * lower levels not to allocate us a block group past that
829 * limit. The 'inode64' mount option avoids this behavior.
830 */
834 /*
835 * slot is set when we successfully steal inode from other nodes.
836 * It is reset in 3 places:
837 * 1. when we flush the truncate log
838 * 2. when we complete local alloc recovery.
839 * 3. when we successfully allocate from our own slot.
840 * After it is set, we will go on stealing inodes until we find the
841 * need to check our slots to see whether there is some space for us.
842 */
850 INODE_ALLOC_SYSTEM_INODE,
853 ALLOC_NEW_GROUP |
854 ALLOC_GROUPS_FROM_GLOBAL);
864 /*
865 * Some inodes must be freed by us, so try to allocate
866 * from our own next time.
867 */
874 }
878 inode_steal:
885 }
888 bail:
892 }
896 }
898 /* local alloc code has to do the same thing, so rather than do this
899 * twice.. */
902 {
909 GLOBAL_BITMAP_SYSTEM_INODE,
911 ALLOC_NEW_GROUP);
915 }
917 bail:
919 }
921 /* Callers don't need to care which bitmap (local alloc or main) to
922 * use so we figure it out for them, but unfortunately this clutters
923 * things a bit. */
928 {
938 }
947 bits_wanted,
950 /* The local alloc window is outside ac_max_block.
951 * use the main bitmap. */
956 }
957 }
965 }
966 }
969 bail:
973 }
977 }
980 u32 bits_wanted,
982 {
985 }
987 /*
988 * More or less lifted from ext3. I'll leave their description below:
989 *
990 * "For ext3 allocations, we must not reuse any blocks which are
991 * allocated in the bitmap buffer's "last committed data" copy. This
992 * prevents deletes from freeing up the page for reuse until we have
993 * committed the delete transaction.
994 *
995 * If we didn't do this, then deleting something and reallocating it as
996 * data would allow the old block to be overwritten before the
997 * transaction committed (because we force data to disk before commit).
998 * This would lead to corruption if we crashed between overwriting the
999 * data and committing the delete.
1000 *
1001 * @@@ We may want to make this allocation behaviour conditional on
1002 * data-writes at some point, and disable it for metadata allocations or
1003 * sync-data inodes."
1004 *
1005 * Note: OCFS2 already does this differently for metadata vs data
1006 * allocations, as those bitmaps are separate and undo access is never
1007 * called on a metadata group descriptor.
1008 */
1011 {
1025 else
1030 }
1038 {
1044 /* Callers got this descriptor from
1045 * ocfs2_read_group_descriptor(). Any corruption is a code bug. */
1056 /* We found a zero, but we can't use it as it
1057 * hasn't been put to disk yet! */
1061 /* we found a zero */
1062 found++;
1063 /* move start to the next bit to test */
1064 start++;
1066 /* got a zero after some ones */
1069 }
1073 }
1074 /* we got everything we needed */
1076 /* mlog(0, "Found it all!\n"); */
1078 }
1079 }
1081 /* XXX: I think the first clause is equivalent to the second
1082 * - jlbec */
1091 /* No error log here -- see the comment above
1092 * ocfs2_test_bg_bit_allocatable */
1093 }
1096 }
1104 {
1111 /* All callers get the descriptor via
1112 * ocfs2_read_group_descriptor(). Any corruption is a code bug. */
1117 num_bits);
1124 group_bh,
1125 journal_type);
1129 }
1137 group_bh);
1141 }
1143 bail:
1146 }
1148 /* find the one with the most empty bits */
1150 {
1160 curr++;
1161 }
1165 }
1172 u16 chain)
1173 {
1175 /* there is a really tiny chance the journal calls could fail,
1176 * but we wouldn't want inconsistent blocks in *any* case. */
1182 /* The caller got these descriptors from
1183 * ocfs2_read_group_descriptor(). Any corruption is a code bug. */
1197 prev_bg_bh,
1198 OCFS2_JOURNAL_ACCESS_WRITE);
1202 }
1210 }
1217 }
1225 }
1232 }
1240 }
1243 out_rollback:
1248 }
1252 }
1255 u32 wanted)
1256 {
1258 }
1260 /* return 0 on success, -ENOSPC to keep searching and any other < 0
1261 * value on error. */
1265 u64 max_block,
1267 {
1270 u64 blkoff;
1281 /* Tail groups in cluster bitmaps which aren't cpg
1282 * aligned are prone to partial extention by a failed
1283 * fs resize. If the file system resize never got to
1284 * update the dinode cluster count, then we don't want
1285 * to trust any clusters past it, regardless of what
1286 * the group descriptor says. */
1296 }
1300 max_bits,
1307 gd_cluster_off +
1314 }
1316 /* ocfs2_block_group_find_clear_bits() might
1317 * return success, but we still want to return
1318 * -ENOSPC unless it found the minimum number
1319 * of bits. */
1325 /*
1326 * Don't show bits which we'll be returning
1327 * for allocation to the local alloc bitmap.
1328 */
1330 }
1331 }
1334 }
1339 u64 max_block,
1341 {
1343 u64 blkoff;
1362 }
1363 }
1366 }
1371 u32 num_bits,
1372 u16 chain)
1373 {
1375 u32 tmp_used;
1380 OCFS2_JOURNAL_ACCESS_WRITE);
1384 }
1394 out:
1396 }
1400 u32 bits_wanted,
1401 u32 min_bits,
1404 u64 gd_blkno,
1406 {
1408 u16 found;
1419 }
1428 }
1438 }
1447 out:
1451 }
1455 u32 bits_wanted,
1456 u32 min_bits,
1461 {
1464 u32 tmp_used;
1465 u64 next_group;
1484 }
1488 /* for now, the chain search is a bit simplistic. We just use
1489 * the 1st group with any empty bits. */
1508 }
1510 }
1515 }
1524 /*
1525 * Keep track of previous block descriptor read. When
1526 * we find a target, if we have read more than X
1527 * number of descriptors, and the target is reasonably
1528 * empty, relink him to top of his chain.
1529 *
1530 * We've read 0 extra blocks and only send one more to
1531 * the transaction, yet the next guy to search has a
1532 * much easier time.
1533 *
1534 * Do this *after* figuring out how many bits we're taking out
1535 * of our target group.
1536 */
1546 }
1547 }
1549 /* Ok, claim our bits now: set the info on dinode, chainlist
1550 * and then the group */
1554 OCFS2_JOURNAL_ACCESS_WRITE);
1558 }
1569 }
1572 alloc_inode,
1573 bg,
1574 group_bh,
1580 }
1587 bail:
1593 }
1595 /* will give out up to bits_wanted contiguous bits. */
1599 u32 bits_wanted,
1600 u32 min_bits,
1604 {
1620 /* The bh was validated by the inode read during
1621 * ocfs2_reserve_suballoc_bits(). Any corruption is a code bug. */
1633 }
1636 /* Attempt to short-circuit the usual search mechanism
1637 * by jumping straight to the most recently used
1638 * allocation group. This helps us mantain some
1639 * contiguousness across allocations. */
1644 /* Be careful to update *bg_blkno here as the
1645 * caller is expecting it to be filled in, and
1646 * ocfs2_search_one_group() won't do that for
1647 * us. */
1650 }
1654 }
1655 }
1670 }
1675 /* If we didn't pick a good victim, then just default to
1676 * searching each chain in order. Don't allow chain relinking
1677 * because we only calculate enough journal credits for one
1678 * relink per alloc. */
1695 }
1696 }
1698 set_hint:
1700 /* If the next search of this group is not likely to
1701 * yield a suitable extent, then we reset the last
1702 * group hint so as to not waste a disk read */
1705 else
1707 }
1709 bail:
1712 }
1717 u32 bits_wanted,
1721 {
1723 u64 bg_blkno;
1730 ac,
1731 handle,
1732 bits_wanted,
1734 suballoc_bit_start,
1735 num_bits,
1740 }
1746 bail:
1749 }
1754 {
1756 /*
1757 * Try to allocate inodes from some specific group.
1758 *
1759 * If the parent dir has recorded the last group used in allocation,
1760 * cool, use it. Otherwise if we try to allocate new inode from the
1761 * same slot the parent dir belongs to, use the same chunk.
1762 *
1763 * We are very careful here to avoid the mistake of setting
1764 * ac_last_group to a group descriptor from a different (unlocked) slot.
1765 */
1773 }
1777 {
1780 }
1789 {
1792 u64 bg_blkno;
1804 ac,
1805 handle,
1808 suballoc_bit,
1814 }
1823 bail:
1826 }
1828 /* translate a group desc. blkno and it's bitmap offset into
1829 * disk cluster offset. */
1831 u64 bg_blkno,
1832 u16 bg_bit_off)
1833 {
1843 }
1845 /* given a cluster offset, calculate which block group it belongs to
1846 * and return that block offset. */
1848 {
1850 u32 group_no;
1859 }
1861 /* given the block number of a cluster start, calculate which cluster
1862 * group and descriptor bitmap offset that corresponds to. */
1864 u64 data_blkno,
1867 {
1874 data_cluster);
1878 else
1881 }
1883 /*
1884 * min_bits - minimum contiguous chunk from this total allocation we
1885 * can handle. set to what we asked for originally for a full
1886 * contig. allocation, set to '1' to indicate we can deal with extents
1887 * of any size.
1888 */
1892 u32 min_clusters,
1893 u32 max_clusters,
1896 {
1900 u16 bg_bit_off;
1911 handle,
1912 ac,
1913 bits_wanted,
1914 cluster_start,
1915 num_clusters);
1920 /* The only paths asking for contiguousness
1921 * should know about this already. */
1927 }
1928 /* clamp the current request down to a realistic size. */
1933 ac,
1934 handle,
1935 bits_wanted,
1936 min_clusters,
1938 num_clusters,
1943 bg_blkno,
1944 bg_bit_off);
1946 }
1947 }
1952 }
1956 bail:
1959 }
1964 u32 min_clusters,
1967 {
1972 }
1982 {
1989 /* The caller got this descriptor from
1990 * ocfs2_read_group_descriptor(). Any corruption is a code bug. */
1997 group_bh,
1998 undo_fn ?
1999 OCFS2_JOURNAL_ACCESS_UNDO :
2000 OCFS2_JOURNAL_ACCESS_WRITE);
2004 }
2011 }
2020 }
2029 bail:
2031 }
2033 /*
2034 * expects the suballoc inode to already be locked.
2035 */
2040 u64 bg_blkno,
2044 {
2046 u32 tmp_used;
2054 /* The alloc_bh comes from ocfs2_free_dinode() or
2055 * ocfs2_free_clusters(). The callers have all locked the
2056 * allocator and gotten alloc_bh from the lock call. This
2057 * validates the dinode buffer. Any corruption that has happended
2058 * is a code bug. */
2071 }
2082 }
2089 }
2092 count);
2100 }
2102 bail:
2107 }
2113 u64 bg_blkno,
2115 {
2118 }
2124 {
2131 }
2136 u64 start_blk,
2140 {
2142 u16 bg_start_bit;
2143 u64 bg_blkno;
2146 /* You can't ever have a contiguous set of clusters
2147 * bigger than a block group bitmap so we never have to worry
2148 * about looping on them. */
2152 /* This is expensive. We can safely remove once this stuff has
2153 * gotten tested really well. */
2154 BUG_ON(start_blk != ocfs2_clusters_to_blocks(bitmap_inode->i_sb, ocfs2_blocks_to_clusters(bitmap_inode->i_sb, start_blk)));
2172 }
2175 num_clusters);
2177 out:
2180 }
2185 u64 start_blk,
2187 {
2190 _ocfs2_set_bit);
2191 }
2193 /*
2194 * Give never-used clusters back to the global bitmap. We don't need
2195 * to protect these bits in the undo buffer.
2196 */
2200 u64 start_blk,
2202 {
2205 _ocfs2_clear_bit);
2206 }
2209 {
2223 }
2226 {
2252 }
2253 }
2255 /*
2256 * For a given allocation, determine which allocators will need to be
2257 * accessed, and lock them, reserving the appropriate number of bits.
2258 *
2259 * Sparse file systems call this from ocfs2_write_begin_nolock()
2260 * and ocfs2_allocate_unwritten_extents().
2261 *
2262 * File systems which don't support holes call this from
2263 * ocfs2_extend_allocation().
2264 */
2270 {
2286 }
2288 /*
2289 * Sparse allocation file systems need to be more conservative
2290 * with reserving room for expansion - the actual allocation
2291 * happens while we've got a journal handle open so re-taking
2292 * a cluster lock (because we ran out of room for another
2293 * extent) will violate ordering rules.
2294 *
2295 * Most of the time we'll only be seeing this 1 cluster at a time
2296 * anyway.
2297 *
2298 * Always lock for any unwritten extents - we might want to
2299 * add blocks during a split.
2300 */
2308 }
2309 }
2319 }
2321 out:
2326 }
2328 /*
2329 * We cannot have an error and a non null *data_ac.
2330 */
2331 }
2334 }
2336 /*
2337 * Read the inode specified by blkno to get suballoc_slot and
2338 * suballoc_bit.
2339 */
2342 {
2349 /* dirty read disk */
2355 }
2363 }
2372 }
2379 bail:
2384 }
2386 /*
2387 * test whether bit is SET in allocator bitmap or not. on success, 0
2388 * is returned and *res is 1 for SET; 0 otherwise. when fails, errno
2389 * is returned and *res is meaningless. Call this after you have
2390 * cluster locked against suballoc, or you may get a result based on
2391 * non-up2date contents
2392 */
2397 {
2401 u64 bg_blkno;
2414 }
2423 }
2428 bail:
2433 }
2435 /*
2436 * Test if the bit representing this inode (blkno) is set in the
2437 * suballocator.
2438 *
2439 * On success, 0 is returned and *res is 1 for SET; 0 otherwise.
2440 *
2441 * In the event of failure, a negative value is returned and *res is
2442 * meaningless.
2443 *
2444 * Callers must make sure to hold nfs_sync_lock to prevent
2445 * ocfs2_delete_inode() on another node from accessing the same
2446 * suballocator concurrently.
2447 */
2449 {
2462 }
2464 inode_alloc_inode =
2466 suballoc_slot);
2468 /* the error code could be inaccurate, but we are not able to
2469 * get the correct one. */
2474 }
2483 }
2495 bail:
2498 }