| blob | d9c5c9fcb30fc300bb9132f54f0526156f5847b8 |
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>
55 u64 group_blkno,
56 u16 my_chain,
73 u32 bits_wanted,
74 u32 min_bits,
98 u16 chain);
100 u32 wanted);
102 u64 bg_blkno,
103 u16 bg_bit_off);
105 u32 cluster);
107 u64 data_blkno,
112 {
122 }
126 }
129 {
131 }
133 /* somewhat more expensive than our other checks, so use sparingly. */
137 {
143 }
152 }
160 }
168 }
177 }
186 }
189 }
194 u64 group_blkno,
195 u16 my_chain,
197 {
211 }
214 alloc_inode,
215 bg_bh,
216 OCFS2_JOURNAL_ACCESS_CREATE);
220 }
231 /* set the 1st bit in the bitmap to account for the descriptor block */
239 /* There is no need to zero out or otherwise initialize the
240 * other blocks in a group - All valid FS metadata in a block
241 * group stores the superblock fs_generation value at
242 * allocation time. */
244 bail:
247 }
250 {
258 curr++;
259 }
261 }
263 /*
264 * We expect the block group allocator to already be locked.
265 */
269 {
276 u16 alloc_rec;
277 u64 bg_blkno;
293 }
303 }
306 handle,
307 ac,
315 }
319 /* setup the group */
329 }
333 alloc_inode,
334 bg_bh,
335 bg_blkno,
336 alloc_rec,
337 cl);
341 }
350 }
368 }
379 bail:
391 }
396 u32 slot)
397 {
403 u32 free_bits;
411 }
422 }
431 }
437 }
443 /* cluster bitmap never grows */
449 }
456 }
459 /* You should never ask for this much metadata */
463 }
467 bail:
473 }
478 {
480 u32 slot;
487 }
500 }
503 bail:
507 }
511 }
515 {
523 }
531 INODE_ALLOC_SYSTEM_INODE,
537 }
540 bail:
544 }
548 }
550 /* local alloc code has to do the same thing, so rather than do this
551 * twice.. */
554 {
561 GLOBAL_BITMAP_SYSTEM_INODE,
562 OCFS2_INVALID_SLOT);
566 }
568 bail:
570 }
572 /* Callers don't need to care which bitmap (local alloc or main) to
573 * use so we figure it out for them, but unfortunately this clutters
574 * things a bit. */
576 u32 bits_wanted,
578 {
588 }
595 bits_wanted,
601 /* reserve_local_bits will return enospc with
602 * the local alloc inode still locked, so we
603 * can change this safely here. */
605 /* We set to OCFS2_LA_DISABLED so that umount
606 * can clean up what's left of the local
607 * allocation */
609 }
610 }
618 }
619 }
622 bail:
626 }
630 }
632 /*
633 * More or less lifted from ext3. I'll leave their description below:
634 *
635 * "For ext3 allocations, we must not reuse any blocks which are
636 * allocated in the bitmap buffer's "last committed data" copy. This
637 * prevents deletes from freeing up the page for reuse until we have
638 * committed the delete transaction.
639 *
640 * If we didn't do this, then deleting something and reallocating it as
641 * data would allow the old block to be overwritten before the
642 * transaction committed (because we force data to disk before commit).
643 * This would lead to corruption if we crashed between overwriting the
644 * data and committing the delete.
645 *
646 * @@@ We may want to make this allocation behaviour conditional on
647 * data-writes at some point, and disable it for metadata allocations or
648 * sync-data inodes."
649 *
650 * Note: OCFS2 already does this differently for metadata vs data
651 * allocations, as those bitmaps are seperate and undo access is never
652 * called on a metadata group descriptor.
653 */
656 {
666 }
674 {
683 }
693 /* We found a zero, but we can't use it as it
694 * hasn't been put to disk yet! */
698 /* we found a zero */
699 found++;
700 /* move start to the next bit to test */
701 start++;
703 /* got a zero after some ones */
706 }
710 }
711 /* we got everything we needed */
713 /* mlog(0, "Found it all!\n"); */
715 }
716 }
718 /* XXX: I think the first clause is equivalent to the second
719 * - jlbec */
728 /* No error log here -- see the comment above
729 * ocfs2_test_bg_bit_allocatable */
730 }
733 }
741 {
752 }
756 num_bits);
762 alloc_inode,
763 group_bh,
764 journal_type);
768 }
776 group_bh);
780 }
782 bail:
785 }
787 /* find the one with the most empty bits */
789 {
799 curr++;
800 }
804 }
811 u16 chain)
812 {
814 /* there is a really tiny chance the journal calls could fail,
815 * but we wouldn't want inconsistent blocks in *any* case. */
825 }
830 }
835 }
847 OCFS2_JOURNAL_ACCESS_WRITE);
851 }
859 }
862 OCFS2_JOURNAL_ACCESS_WRITE);
866 }
874 }
877 OCFS2_JOURNAL_ACCESS_WRITE);
881 }
889 }
892 out_rollback:
897 }
898 out:
901 }
904 u32 wanted)
905 {
907 }
909 /* return 0 on success, -ENOSPC to keep searching and any other < 0
910 * value on error. */
915 {
927 /* Tail groups in cluster bitmaps which aren't cpg
928 * aligned are prone to partial extention by a failed
929 * fs resize. If the file system resize never got to
930 * update the dinode cluster count, then we don't want
931 * to trust any clusters past it, regardless of what
932 * the group descriptor says. */
942 }
946 max_bits,
951 /* ocfs2_block_group_find_clear_bits() might
952 * return success, but we still want to return
953 * -ENOSPC unless it found the minimum number
954 * of bits. */
959 }
960 }
963 }
969 {
983 }
988 u32 num_bits,
989 u16 chain)
990 {
992 u32 tmp_used;
997 OCFS2_JOURNAL_ACCESS_WRITE);
1001 }
1011 out:
1013 }
1017 u32 bits_wanted,
1018 u32 min_bits,
1021 u64 gd_blkno,
1023 {
1025 u16 found;
1035 }
1042 }
1050 }
1060 }
1069 out:
1073 }
1077 u32 bits_wanted,
1078 u32 min_bits,
1083 {
1086 u32 tmp_used;
1087 u64 next_group;
1106 }
1112 }
1115 /* for now, the chain search is a bit simplistic. We just use
1116 * the 1st group with any empty bits. */
1126 }
1136 }
1142 }
1143 }
1148 }
1157 /*
1158 * Keep track of previous block descriptor read. When
1159 * we find a target, if we have read more than X
1160 * number of descriptors, and the target is reasonably
1161 * empty, relink him to top of his chain.
1162 *
1163 * We've read 0 extra blocks and only send one more to
1164 * the transaction, yet the next guy to search has a
1165 * much easier time.
1166 *
1167 * Do this *after* figuring out how many bits we're taking out
1168 * of our target group.
1169 */
1179 }
1180 }
1182 /* Ok, claim our bits now: set the info on dinode, chainlist
1183 * and then the group */
1185 alloc_inode,
1187 OCFS2_JOURNAL_ACCESS_WRITE);
1191 }
1202 }
1205 alloc_inode,
1206 bg,
1207 group_bh,
1213 }
1220 bail:
1228 }
1230 /* will give out up to bits_wanted contiguous bits. */
1234 u32 bits_wanted,
1235 u32 min_bits,
1239 {
1258 }
1268 }
1271 /* Attempt to short-circuit the usual search mechanism
1272 * by jumping straight to the most recently used
1273 * allocation group. This helps us mantain some
1274 * contiguousness across allocations. */
1279 /* Be careful to update *bg_blkno here as the
1280 * caller is expecting it to be filled in, and
1281 * ocfs2_search_one_group() won't do that for
1282 * us. */
1285 }
1289 }
1290 }
1305 }
1310 /* If we didn't pick a good victim, then just default to
1311 * searching each chain in order. Don't allow chain relinking
1312 * because we only calculate enough journal credits for one
1313 * relink per alloc. */
1330 }
1331 }
1333 set_hint:
1335 /* If the next search of this group is not likely to
1336 * yield a suitable extent, then we reset the last
1337 * group hint so as to not waste a disk read */
1340 else
1342 }
1344 bail:
1347 }
1352 u32 bits_wanted,
1356 {
1358 u64 bg_blkno;
1365 ac,
1366 handle,
1367 bits_wanted,
1369 suballoc_bit_start,
1370 num_bits,
1375 }
1381 bail:
1384 }
1391 {
1394 u64 bg_blkno;
1404 ac,
1405 handle,
1408 suballoc_bit,
1414 }
1422 bail:
1425 }
1427 /* translate a group desc. blkno and it's bitmap offset into
1428 * disk cluster offset. */
1430 u64 bg_blkno,
1431 u16 bg_bit_off)
1432 {
1442 }
1444 /* given a cluster offset, calculate which block group it belongs to
1445 * and return that block offset. */
1447 u32 cluster)
1448 {
1450 u32 group_no;
1459 }
1461 /* given the block number of a cluster start, calculate which cluster
1462 * group and descriptor bitmap offset that corresponds to. */
1464 u64 data_blkno,
1467 {
1474 data_cluster);
1478 else
1481 }
1483 /*
1484 * min_bits - minimum contiguous chunk from this total allocation we
1485 * can handle. set to what we asked for originally for a full
1486 * contig. allocation, set to '1' to indicate we can deal with extents
1487 * of any size.
1488 */
1492 u32 min_clusters,
1495 {
1499 u16 bg_bit_off;
1511 handle,
1512 ac,
1513 bits_wanted,
1514 cluster_start,
1515 num_clusters);
1520 /* The only paths asking for contiguousness
1521 * should know about this already. */
1526 }
1527 /* clamp the current request down to a realistic size. */
1532 ac,
1533 handle,
1534 bits_wanted,
1535 min_clusters,
1537 num_clusters,
1542 bg_blkno,
1543 bg_bit_off);
1545 }
1546 }
1551 }
1555 bail:
1558 }
1566 {
1578 }
1586 journal_type);
1590 }
1602 }
1608 bail:
1610 }
1612 /*
1613 * expects the suballoc inode to already be locked.
1614 */
1619 u64 bg_blkno,
1621 {
1623 u32 tmp_used;
1636 }
1644 alloc_inode);
1648 }
1655 }
1664 }
1667 OCFS2_JOURNAL_ACCESS_WRITE);
1671 }
1674 count);
1682 }
1684 bail:
1690 }
1696 {
1703 }
1708 u64 start_blk,
1710 {
1712 u16 bg_start_bit;
1713 u64 bg_blkno;
1716 /* You can't ever have a contiguous set of clusters
1717 * bigger than a block group bitmap so we never have to worry
1718 * about looping on them. */
1722 /* This is expensive. We can safely remove once this stuff has
1723 * gotten tested really well. */
1724 BUG_ON(start_blk != ocfs2_clusters_to_blocks(bitmap_inode->i_sb, ocfs2_blocks_to_clusters(bitmap_inode->i_sb, start_blk)));
1738 num_clusters);
1744 }
1747 {
1761 }
1764 {
1790 }
1791 }