| blob | d2d278fb9819ee3da92577a367b79f0bdc18681f |
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>
49 #define NOT_ALLOC_NEW_GROUP 0
50 #define ALLOC_NEW_GROUP 1
52 #define OCFS2_MAX_INODES_TO_STEAL 1024
60 u64 group_blkno,
61 u16 my_chain,
78 u32 bits_wanted,
79 u32 min_bits,
103 u16 chain);
105 u32 wanted);
107 u64 bg_blkno,
108 u16 bg_bit_off);
110 u64 data_blkno,
115 {
126 }
130 }
131 }
134 {
137 }
140 {
142 }
144 /* somewhat more expensive than our other checks, so use sparingly. */
148 {
154 }
163 }
171 }
179 }
188 }
197 }
200 }
205 u64 group_blkno,
206 u16 my_chain,
208 {
222 }
225 alloc_inode,
226 bg_bh,
227 OCFS2_JOURNAL_ACCESS_CREATE);
231 }
242 /* set the 1st bit in the bitmap to account for the descriptor block */
250 /* There is no need to zero out or otherwise initialize the
251 * other blocks in a group - All valid FS metadata in a block
252 * group stores the superblock fs_generation value at
253 * allocation time. */
255 bail:
258 }
261 {
269 curr++;
270 }
272 }
274 /*
275 * We expect the block group allocator to already be locked.
276 */
280 {
287 u16 alloc_rec;
288 u64 bg_blkno;
304 }
314 }
317 handle,
318 ac,
326 }
330 /* setup the group */
340 }
344 alloc_inode,
345 bg_bh,
346 bg_blkno,
347 alloc_rec,
348 cl);
352 }
361 }
379 }
390 bail:
402 }
407 u32 slot,
409 {
415 u32 free_bits;
423 }
434 }
444 }
450 }
456 /* cluster bitmap never grows */
462 }
470 }
477 }
480 /* You should never ask for this much metadata */
484 }
488 bail:
494 }
499 {
501 u32 slot;
508 }
516 EXTENT_ALLOC_SYSTEM_INODE,
522 }
525 bail:
529 }
533 }
537 {
541 /* Start to steal inodes from the first slot after ours. */
553 INODE_ALLOC_SYSTEM_INODE,
558 }
561 }
564 }
568 {
577 }
584 /*
585 * slot is set when we successfully steal inode from other nodes.
586 * It is reset in 3 places:
587 * 1. when we flush the truncate log
588 * 2. when we complete local alloc recovery.
589 * 3. when we successfully allocate from our own slot.
590 * After it is set, we will go on stealing inodes until we find the
591 * need to check our slots to see whether there is some space for us.
592 */
599 INODE_ALLOC_SYSTEM_INODE,
604 /*
605 * Some inodes must be freed by us, so try to allocate
606 * from our own next time.
607 */
614 }
618 inode_steal:
625 }
628 bail:
632 }
636 }
638 /* local alloc code has to do the same thing, so rather than do this
639 * twice.. */
642 {
649 GLOBAL_BITMAP_SYSTEM_INODE,
650 OCFS2_INVALID_SLOT,
651 ALLOC_NEW_GROUP);
655 }
657 bail:
659 }
661 /* Callers don't need to care which bitmap (local alloc or main) to
662 * use so we figure it out for them, but unfortunately this clutters
663 * things a bit. */
665 u32 bits_wanted,
667 {
677 }
684 bits_wanted,
690 /* reserve_local_bits will return enospc with
691 * the local alloc inode still locked, so we
692 * can change this safely here. */
694 /* We set to OCFS2_LA_DISABLED so that umount
695 * can clean up what's left of the local
696 * allocation */
698 }
699 }
707 }
708 }
711 bail:
715 }
719 }
721 /*
722 * More or less lifted from ext3. I'll leave their description below:
723 *
724 * "For ext3 allocations, we must not reuse any blocks which are
725 * allocated in the bitmap buffer's "last committed data" copy. This
726 * prevents deletes from freeing up the page for reuse until we have
727 * committed the delete transaction.
728 *
729 * If we didn't do this, then deleting something and reallocating it as
730 * data would allow the old block to be overwritten before the
731 * transaction committed (because we force data to disk before commit).
732 * This would lead to corruption if we crashed between overwriting the
733 * data and committing the delete.
734 *
735 * @@@ We may want to make this allocation behaviour conditional on
736 * data-writes at some point, and disable it for metadata allocations or
737 * sync-data inodes."
738 *
739 * Note: OCFS2 already does this differently for metadata vs data
740 * allocations, as those bitmaps are separate and undo access is never
741 * called on a metadata group descriptor.
742 */
745 {
755 }
763 {
772 }
782 /* We found a zero, but we can't use it as it
783 * hasn't been put to disk yet! */
787 /* we found a zero */
788 found++;
789 /* move start to the next bit to test */
790 start++;
792 /* got a zero after some ones */
795 }
799 }
800 /* we got everything we needed */
802 /* mlog(0, "Found it all!\n"); */
804 }
805 }
807 /* XXX: I think the first clause is equivalent to the second
808 * - jlbec */
817 /* No error log here -- see the comment above
818 * ocfs2_test_bg_bit_allocatable */
819 }
822 }
830 {
841 }
845 num_bits);
851 alloc_inode,
852 group_bh,
853 journal_type);
857 }
865 group_bh);
869 }
871 bail:
874 }
876 /* find the one with the most empty bits */
878 {
888 curr++;
889 }
893 }
900 u16 chain)
901 {
903 /* there is a really tiny chance the journal calls could fail,
904 * but we wouldn't want inconsistent blocks in *any* case. */
914 }
919 }
924 }
936 OCFS2_JOURNAL_ACCESS_WRITE);
940 }
948 }
951 OCFS2_JOURNAL_ACCESS_WRITE);
955 }
963 }
966 OCFS2_JOURNAL_ACCESS_WRITE);
970 }
978 }
981 out_rollback:
986 }
987 out:
990 }
993 u32 wanted)
994 {
996 }
998 /* return 0 on success, -ENOSPC to keep searching and any other < 0
999 * value on error. */
1004 {
1016 /* Tail groups in cluster bitmaps which aren't cpg
1017 * aligned are prone to partial extention by a failed
1018 * fs resize. If the file system resize never got to
1019 * update the dinode cluster count, then we don't want
1020 * to trust any clusters past it, regardless of what
1021 * the group descriptor says. */
1031 }
1035 max_bits,
1040 /* ocfs2_block_group_find_clear_bits() might
1041 * return success, but we still want to return
1042 * -ENOSPC unless it found the minimum number
1043 * of bits. */
1048 }
1049 }
1052 }
1058 {
1072 }
1077 u32 num_bits,
1078 u16 chain)
1079 {
1081 u32 tmp_used;
1086 OCFS2_JOURNAL_ACCESS_WRITE);
1090 }
1100 out:
1102 }
1106 u32 bits_wanted,
1107 u32 min_bits,
1110 u64 gd_blkno,
1112 {
1114 u16 found;
1124 }
1131 }
1139 }
1149 }
1158 out:
1162 }
1166 u32 bits_wanted,
1167 u32 min_bits,
1172 {
1175 u32 tmp_used;
1176 u64 next_group;
1195 }
1201 }
1204 /* for now, the chain search is a bit simplistic. We just use
1205 * the 1st group with any empty bits. */
1215 }
1225 }
1231 }
1232 }
1237 }
1246 /*
1247 * Keep track of previous block descriptor read. When
1248 * we find a target, if we have read more than X
1249 * number of descriptors, and the target is reasonably
1250 * empty, relink him to top of his chain.
1251 *
1252 * We've read 0 extra blocks and only send one more to
1253 * the transaction, yet the next guy to search has a
1254 * much easier time.
1255 *
1256 * Do this *after* figuring out how many bits we're taking out
1257 * of our target group.
1258 */
1268 }
1269 }
1271 /* Ok, claim our bits now: set the info on dinode, chainlist
1272 * and then the group */
1274 alloc_inode,
1276 OCFS2_JOURNAL_ACCESS_WRITE);
1280 }
1291 }
1294 alloc_inode,
1295 bg,
1296 group_bh,
1302 }
1309 bail:
1317 }
1319 /* will give out up to bits_wanted contiguous bits. */
1323 u32 bits_wanted,
1324 u32 min_bits,
1328 {
1347 }
1357 }
1360 /* Attempt to short-circuit the usual search mechanism
1361 * by jumping straight to the most recently used
1362 * allocation group. This helps us mantain some
1363 * contiguousness across allocations. */
1368 /* Be careful to update *bg_blkno here as the
1369 * caller is expecting it to be filled in, and
1370 * ocfs2_search_one_group() won't do that for
1371 * us. */
1374 }
1378 }
1379 }
1394 }
1399 /* If we didn't pick a good victim, then just default to
1400 * searching each chain in order. Don't allow chain relinking
1401 * because we only calculate enough journal credits for one
1402 * relink per alloc. */
1419 }
1420 }
1422 set_hint:
1424 /* If the next search of this group is not likely to
1425 * yield a suitable extent, then we reset the last
1426 * group hint so as to not waste a disk read */
1429 else
1431 }
1433 bail:
1436 }
1441 u32 bits_wanted,
1445 {
1447 u64 bg_blkno;
1454 ac,
1455 handle,
1456 bits_wanted,
1458 suballoc_bit_start,
1459 num_bits,
1464 }
1470 bail:
1473 }
1480 {
1483 u64 bg_blkno;
1493 ac,
1494 handle,
1497 suballoc_bit,
1503 }
1511 bail:
1514 }
1516 /* translate a group desc. blkno and it's bitmap offset into
1517 * disk cluster offset. */
1519 u64 bg_blkno,
1520 u16 bg_bit_off)
1521 {
1531 }
1533 /* given a cluster offset, calculate which block group it belongs to
1534 * and return that block offset. */
1536 {
1538 u32 group_no;
1547 }
1549 /* given the block number of a cluster start, calculate which cluster
1550 * group and descriptor bitmap offset that corresponds to. */
1552 u64 data_blkno,
1555 {
1562 data_cluster);
1566 else
1569 }
1571 /*
1572 * min_bits - minimum contiguous chunk from this total allocation we
1573 * can handle. set to what we asked for originally for a full
1574 * contig. allocation, set to '1' to indicate we can deal with extents
1575 * of any size.
1576 */
1580 u32 min_clusters,
1581 u32 max_clusters,
1584 {
1588 u16 bg_bit_off;
1599 handle,
1600 ac,
1601 bits_wanted,
1602 cluster_start,
1603 num_clusters);
1608 /* The only paths asking for contiguousness
1609 * should know about this already. */
1615 }
1616 /* clamp the current request down to a realistic size. */
1621 ac,
1622 handle,
1623 bits_wanted,
1624 min_clusters,
1626 num_clusters,
1631 bg_blkno,
1632 bg_bit_off);
1634 }
1635 }
1640 }
1644 bail:
1647 }
1652 u32 min_clusters,
1655 {
1660 }
1668 {
1680 }
1688 journal_type);
1692 }
1704 }
1710 bail:
1712 }
1714 /*
1715 * expects the suballoc inode to already be locked.
1716 */
1721 u64 bg_blkno,
1723 {
1725 u32 tmp_used;
1738 }
1746 alloc_inode);
1750 }
1757 }
1766 }
1769 OCFS2_JOURNAL_ACCESS_WRITE);
1773 }
1776 count);
1784 }
1786 bail:
1792 }
1798 {
1805 }
1810 u64 start_blk,
1812 {
1814 u16 bg_start_bit;
1815 u64 bg_blkno;
1818 /* You can't ever have a contiguous set of clusters
1819 * bigger than a block group bitmap so we never have to worry
1820 * about looping on them. */
1824 /* This is expensive. We can safely remove once this stuff has
1825 * gotten tested really well. */
1826 BUG_ON(start_blk != ocfs2_clusters_to_blocks(bitmap_inode->i_sb, ocfs2_blocks_to_clusters(bitmap_inode->i_sb, start_blk)));
1840 num_clusters);
1846 }
1849 {
1863 }
1866 {
1892 }
1893 }