ext3-mballoc3-core.patch

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

+		MB_CHECK_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))
+					MB_CHECK_ASSERT(mb_test_bit((i<<1)+1, buddy2));
+				else if (!mb_test_bit((i << 1) + 1, buddy2))
+					MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
+				continue;
+			}
+
+			/* both bits in buddy2 must be 0 */
+			MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
+			MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
+
+			for (j = 0; j < (1 << order); j++) {
+				k = (i * (1 << order)) + j;
+				MB_CHECK_ASSERT(!mb_test_bit(k, EXT3_MB_BITMAP(e3b)));
+			}
+			count++;
+		}
+		MB_CHECK_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)) {
+			MB_CHECK_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;
+			MB_CHECK_ASSERT(k < max2);
+			MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
+		}
+	}
+	MB_CHECK_ASSERT(!EXT3_MB_GRP_NEED_INIT(e3b->bd_info));
+	MB_CHECK_ASSERT(e3b->bd_info->bb_fragments == fragments);
+
+	grp = EXT3_GROUP_INFO(sb, e3b->bd_group);
+	buddy = mb_find_buddy(e3b, 0, &max);
+	list_for_each(cur, &grp->bb_prealloc_list) {
+		unsigned long groupnr;
+		struct ext3_prealloc_space *pa;
+		pa = list_entry(cur, struct ext3_prealloc_space, group_list);
+		ext3_get_group_no_and_offset(sb, pa->pstart, &groupnr, &k);
+		MB_CHECK_ASSERT(groupnr == e3b->bd_group);
+		for (i = 0; i < pa->len; i++)
+			MB_CHECK_ASSERT(mb_test_bit(k + i, buddy));
+	}
+	return 0;
+}
+#undef MB_CHECK_ASSERT
+#define mb_check_buddy(e3b) __mb_check_buddy(e3b,__FILE__,__FUNCTION__,__LINE__)
+#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;
+
+	BUG_ON(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);
+
+		if (max < min)
+			min = max;
+		chunk = 1 << min;
+
+		/* mark multiblock chunks only */
+		grp->bb_counters[min]++;
+		if (min > 0)
+			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();
+
+	/* initialize buddy from bitmap which is aggregation
+	 * of on-disk bitmap and preallocations */
+	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;
+
+	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;
+	}
+
+	clear_bit(EXT3_GROUP_INFO_NEED_INIT_BIT, &grp->bb_state);
+
+	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, char *incore)
+{
+	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 */
+			BUG_ON(incore == NULL);
+			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, incore, group);
+			incore = NULL;
+		} else {
+			/* this is block of bitmap */
+			BUG_ON(incore != NULL);
+			mb_debug("put bitmap for group %u in page %lu/%x\n",
+				group, page->index, i * blocksize);
+
+			/* see comments in ext3_mb_put_pa() */
+			ext3_lock_group(sb, group);
+			memcpy(data, bitmap, blocksize);
+
+			/* mark all preallocated blocks used in in-core bitmap */
+			ext3_mb_generate_from_pa(sb, data, group);
+			ext3_unlock_group(sb, group);
+
+			incore = data;
+		}
+	}
+	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;
+
+	e3b->bd_blkbits = sb->s_blocksize_bits;
+	e3b->bd_info = EXT3_GROUP_INFO(sb, group);
+	e3b->bd_sb = sb;
+	e3b->bd_group = group;
+	e3b->bd_buddy_page = NULL;
+	e3b->bd_bitmap_page = NULL;
+
+	block = group * 2;
+	pnum = block / blocks_per_page;
+	poff = block % blocks_per_page;
+
+	/* we could use find_or_create_page(), but it locks page
+	 * what we'd like to avoid in fast path ... */
+	page = find_get_page(inode->i_mapping, pnum);
+	if (page == NULL || !PageUptodate(page)) {
+		if (page)
+			page_cache_release(page);
+		page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
+		if (page) {
+			BUG_ON(page->mapping != inode->i_mapping);
+			if (!PageUptodate(page)) {
+				ext3_mb_init_cache(page, NULL);
+				mb_cmp_bitmaps(e3b, page_address(page) +
+					       (poff * sb->s_blocksize));
+			}
+			unlock_page(page);
+		}
+	}
+	if (page == NULL || !PageUptodate(page))
+		goto err;
+	e3b->bd_bitmap_page = page;
+	e3b->bd_bitmap = page_address(page) + (poff * sb->s_blocksize);
+	mark_page_accessed(page);
+
+	block++;
+	pnum = block / blocks_per_page;
+	poff = block % blocks_per_page;
+
+	page = find_get_page(inode->i_mapping, pnum);
+	if (page == NULL || !PageUptodate(page)) {
+		if (page)
+			page_cache_release(page);
+		page = find_or_create_page(inode->i_mapping, pnum, GFP_NOFS);
+		if (page) {
+			BUG_ON(page->mapping != inode->i_mapping);
+			if (!PageUptodate(page))
+				ext3_mb_init_cache(page, e3b->bd_bitmap);
+
+			unlock_page(page);
+		}
+	}
+	if (page == NULL || !PageUptodate(page))
+		goto err;
+	e3b->bd_buddy_page = page;
+	e3b->bd_buddy = page_address(page) + (poff * sb->s_blocksize);
+	mark_page_accessed(page);
+
+	BUG_ON(e3b->bd_bitmap_page == NULL);
+	BUG_ON(e3b->bd_buddy_page == NULL);
+
+	return 0;
+
+err:
+	if (e3b->bd_bitmap_page)
+		page_cache_release(e3b->bd_bitmap_page);
+	if (e3b->bd_buddy_page)
+		page_cache_release(e3b->bd_buddy_page);
+	e3b->bd_buddy = NULL;
+	e3b->bd_bitmap = NULL;
+	return -EIO;
+}
+
+static void ext3_mb_release_desc(struct ext3_buddy *e3b)
+{
+	if (e3b->bd_bitmap_page)
+		page_cache_release(e3b->bd_bitmap_page);
+	if (e3b->bd_buddy_page)
+		page_cache_release(e3b->bd_buddy_page);
+}
+
+
+static int mb_find_order_for_block(struct ext3_buddy *e3b, int block)
+{
+	int order = 1;
+	void *bb;
+
+	BUG_ON(EXT3_MB_BITMAP(e3b) == EXT3_MB_BUDDY(e3b));
+	BUG_ON(block >= (1 << (e3b->bd_blkbits + 3)));
+
+	bb = EXT3_MB_BUDDY(e3b);
+	while (order <= e3b->bd_blkbits + 1) {
+		block = block >> 1;
+		if (!mb_test_bit(block, bb)) {
+			/* this block is part of buddy of order 'order' */
+			return order;
+		}
+		bb += 1 << (e3b->bd_blkbits - order);
+		order++;
+	}
+	return 0;
+}
+
+static inline void mb_clear_bits(spinlock_t *lock, void *bm, int cur, int len)
+{
+	__u32 *addr;
+
+	len = cur + len;
+	while (cur < len) {
+		if ((cur & 31) == 0 && (len - cur) >= 32) {
+			/* fast path: clear whole word at once */
+			addr = bm + (cur >> 3);
+			*addr = 0;
+			cur += 32;
+			continue;
+		}
+		mb_clear_bit_atomic(lock, cur, bm);
+		cur++;
+	}
+}
+
+static inline void mb_set_bits(spinlock_t *lock, void *bm, int cur, int len)
+{
+	__u32 *addr;
+
+	len = cur + len;
+	while (cur < len) {
+		if ((cur & 31) == 0 && (len - cur) >= 32) {
+			/* fast path: clear whole word at once */
+			addr = bm + (cur >> 3);
+			*addr = 0xffffffff;
+			cur += 32;
+			continue;
+		}
+		mb_set_bit_atomic(lock, cur, bm);
+		cur++;
+	}
+}
+
+static int mb_free_blocks(struct inode *inode, struct ext3_buddy *e3b,
+			  int first, int count)
+{
+	int block = 0, max = 0, order;
+	void *buddy, *buddy2;
+	struct super_block *sb = e3b->bd_sb;
+
+	BUG_ON(first + count > (sb->s_blocksize << 3));
+	BUG_ON(!ext3_is_group_locked(sb, e3b->bd_group));
+	mb_check_buddy(e3b);
+	mb_free_blocks_double(inode, e3b, first, count);
+
+	e3b->bd_info->bb_free += count;
+	if (first < e3b->bd_info->bb_first_free)
+		e3b->bd_info->bb_first_free = first;
+
+	/* let's maintain fragments counter */
+	if (first != 0)
+		block = !mb_test_bit(first - 1, EXT3_MB_BITMAP(e3b));
+	if (first + count < EXT3_SB(sb)->s_mb_maxs[0])