| blob | 7e397e2c25dd219fd55e3f16c363488fb57223e6 |
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 u64 data_blkno,
110 {
120 }
124 }
127 {
129 }
131 /* somewhat more expensive than our other checks, so use sparingly. */
135 {
141 }
150 }
158 }
166 }
175 }
184 }
187 }
192 u64 group_blkno,
193 u16 my_chain,
195 {
209 }
212 alloc_inode,
213 bg_bh,
214 OCFS2_JOURNAL_ACCESS_CREATE);
218 }
229 /* set the 1st bit in the bitmap to account for the descriptor block */
237 /* There is no need to zero out or otherwise initialize the
238 * other blocks in a group - All valid FS metadata in a block
239 * group stores the superblock fs_generation value at
240 * allocation time. */
242 bail:
245 }
248 {
256 curr++;
257 }
259 }
261 /*
262 * We expect the block group allocator to already be locked.
263 */
267 {
274 u16 alloc_rec;
275 u64 bg_blkno;
291 }
301 }
304 handle,
305 ac,
313 }
317 /* setup the group */
327 }
331 alloc_inode,
332 bg_bh,
333 bg_blkno,
334 alloc_rec,
335 cl);
339 }
348 }
366 }
377 bail:
389 }
394 u32 slot)
395 {
401 u32 free_bits;
409 }
420 }
429 }
435 }
441 /* cluster bitmap never grows */
447 }
454 }
457 /* You should never ask for this much metadata */
461 }
465 bail:
471 }
476 {
478 u32 slot;
485 }
498 }
501 bail:
505 }
509 }
513 {
521 }
529 INODE_ALLOC_SYSTEM_INODE,
535 }
538 bail:
542 }
546 }
548 /* local alloc code has to do the same thing, so rather than do this
549 * twice.. */
552 {
559 GLOBAL_BITMAP_SYSTEM_INODE,
560 OCFS2_INVALID_SLOT);
564 }
566 bail:
568 }
570 /* Callers don't need to care which bitmap (local alloc or main) to
571 * use so we figure it out for them, but unfortunately this clutters
572 * things a bit. */
574 u32 bits_wanted,
576 {
586 }
593 bits_wanted,
599 /* reserve_local_bits will return enospc with
600 * the local alloc inode still locked, so we
601 * can change this safely here. */
603 /* We set to OCFS2_LA_DISABLED so that umount
604 * can clean up what's left of the local
605 * allocation */
607 }
608 }
616 }
617 }
620 bail:
624 }
628 }
630 /*
631 * More or less lifted from ext3. I'll leave their description below:
632 *
633 * "For ext3 allocations, we must not reuse any blocks which are
634 * allocated in the bitmap buffer's "last committed data" copy. This
635 * prevents deletes from freeing up the page for reuse until we have
636 * committed the delete transaction.
637 *
638 * If we didn't do this, then deleting something and reallocating it as
639 * data would allow the old block to be overwritten before the
640 * transaction committed (because we force data to disk before commit).
641 * This would lead to corruption if we crashed between overwriting the
642 * data and committing the delete.
643 *
644 * @@@ We may want to make this allocation behaviour conditional on
645 * data-writes at some point, and disable it for metadata allocations or
646 * sync-data inodes."
647 *
648 * Note: OCFS2 already does this differently for metadata vs data
649 * allocations, as those bitmaps are seperate and undo access is never
650 * called on a metadata group descriptor.
651 */
654 {
664 }
672 {
681 }
691 /* We found a zero, but we can't use it as it
692 * hasn't been put to disk yet! */
696 /* we found a zero */
697 found++;
698 /* move start to the next bit to test */
699 start++;
701 /* got a zero after some ones */
704 }
708 }
709 /* we got everything we needed */
711 /* mlog(0, "Found it all!\n"); */
713 }
714 }
716 /* XXX: I think the first clause is equivalent to the second
717 * - jlbec */
726 /* No error log here -- see the comment above
727 * ocfs2_test_bg_bit_allocatable */
728 }
731 }
739 {
750 }
754 num_bits);
760 alloc_inode,
761 group_bh,
762 journal_type);
766 }
774 group_bh);
778 }
780 bail:
783 }
785 /* find the one with the most empty bits */
787 {
797 curr++;
798 }
802 }
809 u16 chain)
810 {
812 /* there is a really tiny chance the journal calls could fail,
813 * but we wouldn't want inconsistent blocks in *any* case. */
823 }
828 }
833 }
845 OCFS2_JOURNAL_ACCESS_WRITE);
849 }
857 }
860 OCFS2_JOURNAL_ACCESS_WRITE);
864 }
872 }
875 OCFS2_JOURNAL_ACCESS_WRITE);
879 }
887 }
890 out_rollback:
895 }
896 out:
899 }
902 u32 wanted)
903 {
905 }
907 /* return 0 on success, -ENOSPC to keep searching and any other < 0
908 * value on error. */
913 {
925 /* Tail groups in cluster bitmaps which aren't cpg
926 * aligned are prone to partial extention by a failed
927 * fs resize. If the file system resize never got to
928 * update the dinode cluster count, then we don't want
929 * to trust any clusters past it, regardless of what
930 * the group descriptor says. */
940 }
944 max_bits,
949 /* ocfs2_block_group_find_clear_bits() might
950 * return success, but we still want to return
951 * -ENOSPC unless it found the minimum number
952 * of bits. */
957 }
958 }
961 }
967 {
981 }
986 u32 num_bits,
987 u16 chain)
988 {
990 u32 tmp_used;
995 OCFS2_JOURNAL_ACCESS_WRITE);
999 }
1009 out:
1011 }
1015 u32 bits_wanted,
1016 u32 min_bits,
1019 u64 gd_blkno,
1021 {
1023 u16 found;
1033 }
1040 }
1048 }
1058 }
1067 out:
1071 }
1075 u32 bits_wanted,
1076 u32 min_bits,
1081 {
1084 u32 tmp_used;
1085 u64 next_group;
1104 }
1110 }
1113 /* for now, the chain search is a bit simplistic. We just use
1114 * the 1st group with any empty bits. */
1124 }
1134 }
1140 }
1141 }
1146 }
1155 /*
1156 * Keep track of previous block descriptor read. When
1157 * we find a target, if we have read more than X
1158 * number of descriptors, and the target is reasonably
1159 * empty, relink him to top of his chain.
1160 *
1161 * We've read 0 extra blocks and only send one more to
1162 * the transaction, yet the next guy to search has a
1163 * much easier time.
1164 *
1165 * Do this *after* figuring out how many bits we're taking out
1166 * of our target group.
1167 */
1177 }
1178 }
1180 /* Ok, claim our bits now: set the info on dinode, chainlist
1181 * and then the group */
1183 alloc_inode,
1185 OCFS2_JOURNAL_ACCESS_WRITE);
1189 }
1200 }
1203 alloc_inode,
1204 bg,
1205 group_bh,
1211 }
1218 bail:
1226 }
1228 /* will give out up to bits_wanted contiguous bits. */
1232 u32 bits_wanted,
1233 u32 min_bits,
1237 {
1256 }
1266 }
1269 /* Attempt to short-circuit the usual search mechanism
1270 * by jumping straight to the most recently used
1271 * allocation group. This helps us mantain some
1272 * contiguousness across allocations. */
1277 /* Be careful to update *bg_blkno here as the
1278 * caller is expecting it to be filled in, and
1279 * ocfs2_search_one_group() won't do that for
1280 * us. */
1283 }
1287 }
1288 }
1303 }
1308 /* If we didn't pick a good victim, then just default to
1309 * searching each chain in order. Don't allow chain relinking
1310 * because we only calculate enough journal credits for one
1311 * relink per alloc. */
1328 }
1329 }
1331 set_hint:
1333 /* If the next search of this group is not likely to
1334 * yield a suitable extent, then we reset the last
1335 * group hint so as to not waste a disk read */
1338 else
1340 }
1342 bail:
1345 }
1350 u32 bits_wanted,
1354 {
1356 u64 bg_blkno;
1363 ac,
1364 handle,
1365 bits_wanted,
1367 suballoc_bit_start,
1368 num_bits,
1373 }
1379 bail:
1382 }
1389 {
1392 u64 bg_blkno;
1402 ac,
1403 handle,
1406 suballoc_bit,
1412 }
1420 bail:
1423 }
1425 /* translate a group desc. blkno and it's bitmap offset into
1426 * disk cluster offset. */
1428 u64 bg_blkno,
1429 u16 bg_bit_off)
1430 {
1440 }
1442 /* given a cluster offset, calculate which block group it belongs to
1443 * and return that block offset. */
1445 {
1447 u32 group_no;
1456 }
1458 /* given the block number of a cluster start, calculate which cluster
1459 * group and descriptor bitmap offset that corresponds to. */
1461 u64 data_blkno,
1464 {
1471 data_cluster);
1475 else
1478 }
1480 /*
1481 * min_bits - minimum contiguous chunk from this total allocation we
1482 * can handle. set to what we asked for originally for a full
1483 * contig. allocation, set to '1' to indicate we can deal with extents
1484 * of any size.
1485 */
1489 u32 min_clusters,
1490 u32 max_clusters,
1493 {
1497 u16 bg_bit_off;
1508 handle,
1509 ac,
1510 bits_wanted,
1511 cluster_start,
1512 num_clusters);
1517 /* The only paths asking for contiguousness
1518 * should know about this already. */
1524 }
1525 /* clamp the current request down to a realistic size. */
1530 ac,
1531 handle,
1532 bits_wanted,
1533 min_clusters,
1535 num_clusters,
1540 bg_blkno,
1541 bg_bit_off);
1543 }
1544 }
1549 }
1553 bail:
1556 }
1561 u32 min_clusters,
1564 {
1569 }
1577 {
1589 }
1597 journal_type);
1601 }
1613 }
1619 bail:
1621 }
1623 /*
1624 * expects the suballoc inode to already be locked.
1625 */
1630 u64 bg_blkno,
1632 {
1634 u32 tmp_used;
1647 }
1655 alloc_inode);
1659 }
1666 }
1675 }
1678 OCFS2_JOURNAL_ACCESS_WRITE);
1682 }
1685 count);
1693 }
1695 bail:
1701 }
1707 {
1714 }
1719 u64 start_blk,
1721 {
1723 u16 bg_start_bit;
1724 u64 bg_blkno;
1727 /* You can't ever have a contiguous set of clusters
1728 * bigger than a block group bitmap so we never have to worry
1729 * about looping on them. */
1733 /* This is expensive. We can safely remove once this stuff has
1734 * gotten tested really well. */
1735 BUG_ON(start_blk != ocfs2_clusters_to_blocks(bitmap_inode->i_sb, ocfs2_blocks_to_clusters(bitmap_inode->i_sb, start_blk)));
1749 num_clusters);
1755 }
1758 {
1772 }
1775 {
1801 }
1802 }