ext3-mballoc2-2.6-fc5.patch

非常经典的一个分布式系统

+
+
+#define EXT3_GROUP_INFO_NEED_INIT_BIT	0
+#define EXT3_GROUP_INFO_LOCKED_BIT	1
+
+#define EXT3_MB_GRP_NEED_INIT(grp)	\
+	(test_bit(EXT3_GROUP_INFO_NEED_INIT_BIT, &(grp)->bb_state))
+
+struct ext3_free_extent {
+	__u16 fe_start;
+	__u16 fe_len;
+	__u16 fe_group;
+};
+
+struct ext3_allocation_context {
+	struct super_block *ac_sb;
+
+	/* search goals */
+	struct ext3_free_extent ac_g_ex;
+
+	/* the best found extent */
+	struct ext3_free_extent ac_b_ex;
+
+	/* number of iterations done. we have to track to limit searching */
+	unsigned long ac_ex_scanned;
+	__u16 ac_groups_scanned;
+	__u16 ac_found;
+	__u16 ac_tail;
+	__u16 ac_buddy;
+	__u8 ac_status;	
+	__u8 ac_flags;		/* allocation hints */
+	__u8 ac_criteria;
+	__u8 ac_repeats;
+	__u8 ac_2order;		/* if request is to allocate 2^N blocks and
+				 * N > 0, the field stores N, otherwise 0 */
+
+	struct page *ac_buddy_page;
+	struct page *ac_bitmap_page;
+};
+
+#define AC_STATUS_CONTINUE	1
+#define AC_STATUS_FOUND		2
+#define AC_STATUS_BREAK		3
+
+struct ext3_mb_history {
+	struct ext3_free_extent goal;	/* goal allocation */
+	struct ext3_free_extent result;	/* result allocation */
+	unsigned pid;
+	unsigned ino;
+	__u16 found;	/* how many extents have been found */
+	__u16 groups;	/* how many groups have been scanned */
+	__u16 tail;	/* what tail broke some buddy */
+	__u16 buddy;	/* buddy the tail ^^^ broke */
+	__u8 cr;	/* which phase the result extent was found at */
+	__u8 merged;
+};
+
+struct ext3_buddy {
+	struct page *bd_buddy_page;
+	void *bd_buddy;
+	struct page *bd_bitmap_page;
+	void *bd_bitmap;
+	struct ext3_group_info *bd_info;
+	struct super_block *bd_sb;
+	__u16 bd_blkbits;
+	__u16 bd_group;
+};
+#define EXT3_MB_BITMAP(e3b)	((e3b)->bd_bitmap)
+#define EXT3_MB_BUDDY(e3b)	((e3b)->bd_buddy)
+
+#ifndef EXT3_MB_HISTORY
+#define ext3_mb_store_history(sb,ino,ac)
+#else
+static void ext3_mb_store_history(struct super_block *, unsigned ino,
+				struct ext3_allocation_context *ac);
+#endif
+
+#define in_range(b, first, len)	((b) >= (first) && (b) <= (first) + (len) - 1)
+
+static struct proc_dir_entry *proc_root_ext3;
+
+struct buffer_head *read_block_bitmap(struct super_block *, unsigned int);
+void ext3_mb_poll_new_transaction(struct super_block *, handle_t *);
+void ext3_mb_free_committed_blocks(struct super_block *);
+
+#if BITS_PER_LONG == 64
+#define mb_correct_addr_and_bit(bit,addr)		\
+{							\
+	bit += ((unsigned long) addr & 7UL) << 3;	\
+	addr = (void *) ((unsigned long) addr & ~7UL);	\
+}
+#elif BITS_PER_LONG == 32
+#define mb_correct_addr_and_bit(bit,addr)		\
+{							\
+	bit += ((unsigned long) addr & 3UL) << 3;	\
+	addr = (void *) ((unsigned long) addr & ~3UL);	\
+}
+#else
+#error "how many bits you are?!"
+#endif
+
+static inline int mb_test_bit(int bit, void *addr)
+{
+	mb_correct_addr_and_bit(bit,addr);
+	return ext2_test_bit(bit, addr);
+}
+
+static inline void mb_set_bit(int bit, void *addr)
+{
+	mb_correct_addr_and_bit(bit,addr);
+	ext2_set_bit(bit, addr);
+}
+
+static inline void mb_set_bit_atomic(int bit, void *addr)
+{
+	mb_correct_addr_and_bit(bit,addr);
+	ext2_set_bit_atomic(NULL, bit, addr);
+}
+
+static inline void mb_clear_bit(int bit, void *addr)
+{
+	mb_correct_addr_and_bit(bit,addr);
+	ext2_clear_bit(bit, addr);
+}
+
+static inline void mb_clear_bit_atomic(int bit, void *addr)
+{
+	mb_correct_addr_and_bit(bit,addr);
+	ext2_clear_bit_atomic(NULL, bit, addr);
+}
+
+static inline int mb_find_next_zero_bit(void *addr, int max, int start)
+{
+	int fix;
+#if BITS_PER_LONG == 64
+	fix = ((unsigned long) addr & 7UL) << 3;
+	addr = (void *) ((unsigned long) addr & ~7UL);
+#elif BITS_PER_LONG == 32
+	fix = ((unsigned long) addr & 3UL) << 3;
+	addr = (void *) ((unsigned long) addr & ~3UL);
+#else
+#error "how many bits you are?!"
+#endif
+	max += fix;
+	start += fix;
+	return ext2_find_next_zero_bit(addr, max, start) - fix;
+}
+
+static inline void *mb_find_buddy(struct ext3_buddy *e3b, int order, int *max)
+{
+	char *bb;
+
+	J_ASSERT(EXT3_MB_BITMAP(e3b) != EXT3_MB_BUDDY(e3b));
+	J_ASSERT(max != NULL);
+
+	if (order > e3b->bd_blkbits + 1) {
+		*max = 0;
+		return NULL;
+	}
+
+	/* at order 0 we see each particular block */
+	*max = 1 << (e3b->bd_blkbits + 3);
+	if (order == 0)
+		return EXT3_MB_BITMAP(e3b);
+
+	bb = EXT3_MB_BUDDY(e3b) + EXT3_SB(e3b->bd_sb)->s_mb_offsets[order];
+	*max = EXT3_SB(e3b->bd_sb)->s_mb_maxs[order];
+
+	return bb;
+}
+
+#ifdef AGGRESSIVE_CHECK
+
+static void mb_check_buddy(struct ext3_buddy *e3b)
+{
+	int order = e3b->bd_blkbits + 1;
+	int max, max2, i, j, k, count;
+	int fragments = 0, fstart;
+	void *buddy, *buddy2;
+
+	if (!test_opt(e3b->bd_sb, MBALLOC))
+		return;
+
+	{
+		static int mb_check_counter = 0;
+		if (mb_check_counter++ % 300 != 0)
+			return;
+	}
+
+	while (order > 1) {
+		buddy = mb_find_buddy(e3b, order, &max);
+		J_ASSERT(buddy);
+		buddy2 = mb_find_buddy(e3b, order - 1, &max2);
+		J_ASSERT(buddy2);
+		J_ASSERT(buddy != buddy2);
+		J_ASSERT(max * 2 == max2);
+
+		count = 0;
+		for (i = 0; i < max; i++) {
+
+			if (mb_test_bit(i, buddy)) {
+				/* only single bit in buddy2 may be 1 */
+				if (!mb_test_bit(i << 1, buddy2))
+					J_ASSERT(mb_test_bit((i<<1)+1, buddy2));
+				else if (!mb_test_bit((i << 1) + 1, buddy2))
+					J_ASSERT(mb_test_bit(i << 1, buddy2));
+				continue;
+			}
+
+			/* both bits in buddy2 must be 0 */
+			J_ASSERT(mb_test_bit(i << 1, buddy2));
+			J_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
+
+			for (j = 0; j < (1 << order); j++) {
+				k = (i * (1 << order)) + j;
+				J_ASSERT(!mb_test_bit(k, EXT3_MB_BITMAP(e3b)));
+			}
+			count++;
+		}
+		J_ASSERT(e3b->bd_info->bb_counters[order] == count);
+		order--;
+	}
+
+	fstart = -1;
+	buddy = mb_find_buddy(e3b, 0, &max);
+	for (i = 0; i < max; i++) {
+		if (!mb_test_bit(i, buddy)) {
+			J_ASSERT(i >= e3b->bd_info->bb_first_free);
+			if (fstart == -1) {
+				fragments++;
+				fstart = i;
+			}
+			continue;
+		}
+		fstart = -1;
+		/* check used bits only */
+		for (j = 0; j < e3b->bd_blkbits + 1; j++) {
+			buddy2 = mb_find_buddy(e3b, j, &max2);
+			k = i >> j;
+			J_ASSERT(k < max2);
+			J_ASSERT(mb_test_bit(k, buddy2));
+		}
+	}
+	J_ASSERT(!EXT3_MB_GRP_NEED_INIT(e3b->bd_info));
+	J_ASSERT(e3b->bd_info->bb_fragments == fragments);
+}
+
+#else
+#define mb_check_buddy(e3b)
+#endif
+
+/* find most significant bit */
+static int inline fmsb(unsigned short word)
+{
+	int order;
+
+	if (word > 255) {
+		order = 7;
+		word >>= 8;
+	} else {
+		order = -1;
+	}
+
+	do {
+		order++;
+		word >>= 1;
+	} while (word != 0);
+
+	return order;
+}
+
+static void inline
+ext3_mb_mark_free_simple(struct super_block *sb, void *buddy, unsigned first,
+				int len, struct ext3_group_info *grp)
+{
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	unsigned short min, max, chunk, border;
+
+	mb_debug("mark %u/%u free\n", first, len);
+	J_ASSERT(len < EXT3_BLOCKS_PER_GROUP(sb));
+
+	border = 2 << sb->s_blocksize_bits;
+
+	while (len > 0) {
+		/* find how many blocks can be covered since this position */
+		max = ffs(first | border) - 1;
+
+		/* find how many blocks of power 2 we need to mark */
+		min = fmsb(len);
+
+		mb_debug("  %u/%u -> max %u, min %u\n",
+			first & ((2 << sb->s_blocksize_bits) - 1),
+			len, max, min);
+
+		if (max < min)
+			min = max;
+		chunk = 1 << min;
+
+		/* mark multiblock chunks only */
+		grp->bb_counters[min]++;
+		if (min > 0) {
+			mb_debug("    set %u at %u \n", first >> min,
+				sbi->s_mb_offsets[min]);
+			mb_clear_bit(first >> min, buddy + sbi->s_mb_offsets[min]);
+		}
+
+		len -= chunk;
+		first += chunk;
+	}
+}
+
+static void
+ext3_mb_generate_buddy(struct super_block *sb, void *buddy, void *bitmap,
+			int group)
+{
+	struct ext3_group_info *grp = EXT3_GROUP_INFO(sb, group);
+	unsigned short max = EXT3_BLOCKS_PER_GROUP(sb);
+	unsigned short i = 0, first, len;
+	unsigned free = 0, fragments = 0;
+	unsigned long long period = get_cycles();
+
+	i = mb_find_next_zero_bit(bitmap, max, 0);
+	grp->bb_first_free = i;
+	while (i < max) {
+		fragments++;
+		first = i;
+		i = ext2_find_next_le_bit(bitmap, max, i);
+		len = i - first;
+		free += len;
+		if (len > 1)
+			ext3_mb_mark_free_simple(sb, buddy, first, len, grp);
+		else
+			grp->bb_counters[0]++;
+		if (i < max)
+			i = mb_find_next_zero_bit(bitmap, max, i);
+	}
+	grp->bb_fragments = fragments;
+
+	/* bb_state shouldn't being modified because all
+	 * others waits for init completion on page lock */
+	clear_bit(EXT3_GROUP_INFO_NEED_INIT_BIT, &grp->bb_state);
+	if (free != grp->bb_free) {
+		printk("EXT3-fs: group %u: %u blocks in bitmap, %u in gd\n",
+			group, free, grp->bb_free);
+		grp->bb_free = free;
+	}
+
+	period = get_cycles() - period;
+	spin_lock(&EXT3_SB(sb)->s_bal_lock);
+	EXT3_SB(sb)->s_mb_buddies_generated++;
+	EXT3_SB(sb)->s_mb_generation_time += period;
+	spin_unlock(&EXT3_SB(sb)->s_bal_lock);
+}
+
+static int ext3_mb_init_cache(struct page *page)
+{
+	int blocksize, blocks_per_page, groups_per_page;
+	int err = 0, i, first_group, first_block;
+	struct super_block *sb;
+	struct buffer_head *bhs;
+	struct buffer_head **bh;
+	struct inode *inode;
+	char *data, *bitmap;
+
+	mb_debug("init page %lu\n", page->index);
+
+	inode = page->mapping->host;
+	sb = inode->i_sb;
+	blocksize = 1 << inode->i_blkbits;
+	blocks_per_page = PAGE_CACHE_SIZE / blocksize;
+
+	groups_per_page = blocks_per_page >> 1;
+	if (groups_per_page == 0)
+		groups_per_page = 1;
+
+	/* allocate buffer_heads to read bitmaps */
+	if (groups_per_page > 1) {
+		err = -ENOMEM;
+		i = sizeof(struct buffer_head *) * groups_per_page;
+		bh = kmalloc(i, GFP_NOFS);
+		if (bh == NULL)
+			goto out;
+		memset(bh, 0, i);
+	} else
+		bh = &bhs;
+
+	first_group = page->index * blocks_per_page / 2;
+
+	/* read all groups the page covers into the cache */
+	for (i = 0; i < groups_per_page; i++) {
+		struct ext3_group_desc * desc;
+
+		if (first_group + i >= EXT3_SB(sb)->s_groups_count)
+			break;
+
+		err = -EIO;
+		desc = ext3_get_group_desc(sb, first_group + i, NULL);
+		if (desc == NULL)
+			goto out;
+
+		err = -ENOMEM;
+		bh[i] = sb_getblk(sb, le32_to_cpu(desc->bg_block_bitmap));
+		if (bh[i] == NULL)
+			goto out;
+
+		if (buffer_uptodate(bh[i]))
+			continue;
+
+		lock_buffer(bh[i]);
+		if (buffer_uptodate(bh[i])) {
+			unlock_buffer(bh[i]);
+			continue;
+		}
+
+		get_bh(bh[i]);
+		bh[i]->b_end_io = end_buffer_read_sync;
+		submit_bh(READ, bh[i]);
+		mb_debug("read bitmap for group %u\n", first_group + i);
+	}
+
+	/* wait for I/O completion */
+	for (i = 0; i < groups_per_page && bh[i]; i++)
+		wait_on_buffer(bh[i]);
+
+	err = -EIO;
+	for (i = 0; i < groups_per_page && bh[i]; i++)
+		if (!buffer_uptodate(bh[i]))
+			goto out;
+
+	first_block = page->index * blocks_per_page;
+	for (i = 0; i < blocks_per_page; i++) {
+		int group;
+
+		group = (first_block + i) >> 1;
+		if (group >= EXT3_SB(sb)->s_groups_count)
+			break;
+
+		data = page_address(page) + (i * blocksize);
+		bitmap = bh[group - first_group]->b_data;
+
+		if ((first_block + i) & 1) {
+			/* this is block of buddy */
+			mb_debug("put buddy for group %u in page %lu/%x\n",
+				group, page->index, i * blocksize);
+			memset(data, 0xff, blocksize);
+			EXT3_GROUP_INFO(sb, group)->bb_fragments = 0;
+			memset(EXT3_GROUP_INFO(sb, group)->bb_counters, 0,
+			       sizeof(unsigned short)*(sb->s_blocksize_bits+2));
+			ext3_mb_generate_buddy(sb, data, bitmap, group);
+		} else {
+			/* this is block of bitmap */
+			mb_debug("put bitmap for group %u in page %lu/%x\n",
+				group, page->index, i * blocksize);
+			memcpy(data, bitmap, blocksize);
+		}
+	}
+	SetPageUptodate(page);
+
+out:
+	if (bh) {
+		for (i = 0; i < groups_per_page && bh[i]; i++)
+			brelse(bh[i]);
+		if (bh != &bhs)
+			kfree(bh);
+	}
+	return err;
+}
+
+static int ext3_mb_load_buddy(struct super_block *sb, int group,
+		struct ext3_buddy *e3b)
+{
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	struct inode *inode = sbi->s_buddy_cache;
+	int blocks_per_page, block, pnum, poff;
+	struct page *page;
+
+	mb_debug("load group %u\n", group);
+
+	blocks_per_page = PAGE_CACHE_SIZE / sb->s_blocksize;