ext3-mballoc3-core.patch

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

+		max = !mb_test_bit(first + count, EXT3_MB_BITMAP(e3b));
+	if (block && max)
+		e3b->bd_info->bb_fragments--;
+	else if (!block && !max)
+		e3b->bd_info->bb_fragments++;
+
+	/* let's maintain buddy itself */
+	while (count-- > 0) {
+		block = first++;
+		order = 0;
+
+		if (!mb_test_bit(block, EXT3_MB_BITMAP(e3b))) {
+			unsigned long blocknr;
+			blocknr = e3b->bd_group * EXT3_BLOCKS_PER_GROUP(sb);
+			blocknr += block;
+			blocknr +=
+			    le32_to_cpu(EXT3_SB(sb)->s_es->s_first_data_block);
+
+			ext3_error(sb, __FUNCTION__, "double-free of inode"
+				   " %lu's block %lu(bit %u in group %u)\n",
+				   inode ? inode->i_ino : 0, blocknr, block,
+				   e3b->bd_group);
+		}
+		mb_clear_bit(block, EXT3_MB_BITMAP(e3b));
+		e3b->bd_info->bb_counters[order]++;
+
+		/* start of the buddy */
+		buddy = mb_find_buddy(e3b, order, &max);
+
+		do {
+			block &= ~1UL;
+			if (mb_test_bit(block, buddy) ||
+					mb_test_bit(block + 1, buddy))
+				break;
+
+			/* both the buddies are free, try to coalesce them */
+			buddy2 = mb_find_buddy(e3b, order + 1, &max);
+
+			if (!buddy2)
+				break;
+
+			if (order > 0) {
+				/* for special purposes, we don't set
+				 * free bits in bitmap */
+				mb_set_bit(block, buddy);
+				mb_set_bit(block + 1, buddy);
+			}
+			e3b->bd_info->bb_counters[order]--;
+			e3b->bd_info->bb_counters[order]--;
+
+			block = block >> 1;
+			order++;
+			e3b->bd_info->bb_counters[order]++;
+
+			mb_clear_bit(block, buddy2);
+			buddy = buddy2;
+		} while (1);
+	}
+	mb_check_buddy(e3b);
+
+	return 0;
+}
+
+static int mb_find_extent(struct ext3_buddy *e3b, int order, int block,
+				int needed, struct ext3_free_extent *ex)
+{
+	int next = block, max, ord;
+	void *buddy;
+
+	BUG_ON(!ext3_is_group_locked(e3b->bd_sb, e3b->bd_group));
+	BUG_ON(ex == NULL);
+
+	buddy = mb_find_buddy(e3b, order, &max);
+	BUG_ON(buddy == NULL);
+	BUG_ON(block >= max);
+	if (mb_test_bit(block, buddy)) {
+		ex->fe_len = 0;
+		ex->fe_start = 0;
+		ex->fe_group = 0;
+		return 0;
+	}
+
+	if (likely(order == 0)) {
+		/* find actual order */
+		order = mb_find_order_for_block(e3b, block);
+		block = block >> order;
+	}
+
+	ex->fe_len = 1 << order;
+	ex->fe_start = block << order;
+	ex->fe_group = e3b->bd_group;
+
+	/* calc difference from given start */
+	next = next - ex->fe_start;
+	ex->fe_len -= next;
+	ex->fe_start += next;
+
+	while (needed > ex->fe_len && (buddy = mb_find_buddy(e3b, order, &max))) {
+
+		if (block + 1 >= max)
+			break;
+
+		next = (block + 1) * (1 << order);
+		if (mb_test_bit(next, EXT3_MB_BITMAP(e3b)))
+			break;
+
+		ord = mb_find_order_for_block(e3b, next);
+
+		order = ord;
+		block = next >> order;
+		ex->fe_len += 1 << order;
+	}
+
+	BUG_ON(ex->fe_start + ex->fe_len > (1 << (e3b->bd_blkbits + 3)));
+	return ex->fe_len;
+}
+
+static int mb_mark_used(struct ext3_buddy *e3b, struct ext3_free_extent *ex)
+{
+	int ord, mlen = 0, max = 0, cur;
+	int start = ex->fe_start;
+	int len = ex->fe_len;
+	unsigned ret = 0;
+	int len0 = len;
+	void *buddy;
+
+	BUG_ON(start + len > (e3b->bd_sb->s_blocksize << 3));
+	BUG_ON(e3b->bd_group != ex->fe_group);
+	BUG_ON(!ext3_is_group_locked(e3b->bd_sb, e3b->bd_group));
+	mb_check_buddy(e3b);
+	mb_mark_used_double(e3b, start, len);
+
+	e3b->bd_info->bb_free -= len;
+	if (e3b->bd_info->bb_first_free == start)
+		e3b->bd_info->bb_first_free += len;
+
+	/* let's maintain fragments counter */
+	if (start != 0)
+		mlen = !mb_test_bit(start - 1, EXT3_MB_BITMAP(e3b));
+	if (start + len < EXT3_SB(e3b->bd_sb)->s_mb_maxs[0])
+		max = !mb_test_bit(start + len, EXT3_MB_BITMAP(e3b));
+	if (mlen && max)
+		e3b->bd_info->bb_fragments++;
+	else if (!mlen && !max)
+		e3b->bd_info->bb_fragments--;
+
+	/* let's maintain buddy itself */
+	while (len) {
+		ord = mb_find_order_for_block(e3b, start);
+
+		if (((start >> ord) << ord) == start && len >= (1 << ord)) {
+			/* the whole chunk may be allocated at once! */
+			mlen = 1 << ord;
+			buddy = mb_find_buddy(e3b, ord, &max);
+			BUG_ON((start >> ord) >= max);
+			mb_set_bit(start >> ord, buddy);
+			e3b->bd_info->bb_counters[ord]--;
+			start += mlen;
+			len -= mlen;
+			BUG_ON(len < 0);
+			continue;
+		}
+
+		/* store for history */
+		if (ret == 0)
+			ret = len | (ord << 16);
+
+		/* we have to split large buddy */
+		BUG_ON(ord <= 0);
+		buddy = mb_find_buddy(e3b, ord, &max);
+		mb_set_bit(start >> ord, buddy);
+		e3b->bd_info->bb_counters[ord]--;
+
+		ord--;
+		cur = (start >> ord) & ~1U;
+		buddy = mb_find_buddy(e3b, ord, &max);
+		mb_clear_bit(cur, buddy);
+		mb_clear_bit(cur + 1, buddy);
+		e3b->bd_info->bb_counters[ord]++;
+		e3b->bd_info->bb_counters[ord]++;
+	}
+
+	mb_set_bits(sb_bgl_lock(EXT3_SB(e3b->bd_sb), ex->fe_group),
+		    EXT3_MB_BITMAP(e3b), ex->fe_start, len0);
+	mb_check_buddy(e3b);
+
+	return ret;
+}
+
+/*
+ * Must be called under group lock!
+ */
+static void ext3_mb_use_best_found(struct ext3_allocation_context *ac,
+					struct ext3_buddy *e3b)
+{
+	unsigned long ret;
+
+	BUG_ON(ac->ac_b_ex.fe_group != e3b->bd_group);
+	BUG_ON(ac->ac_status == AC_STATUS_FOUND);
+
+	ac->ac_b_ex.fe_len = min(ac->ac_b_ex.fe_len, ac->ac_g_ex.fe_len);
+	ac->ac_b_ex.fe_logical = ac->ac_g_ex.fe_logical;
+	ret = mb_mark_used(e3b, &ac->ac_b_ex);
+
+	/* preallocation can change ac_b_ex, thus we store actually
+	 * allocated blocks for history */
+	ac->ac_f_ex = ac->ac_b_ex;
+
+	ac->ac_status = AC_STATUS_FOUND;
+	ac->ac_tail = ret & 0xffff;
+	ac->ac_buddy = ret >> 16;
+
+	/* XXXXXXX: SUCH A HORRIBLE **CK */
+	ac->ac_bitmap_page = e3b->bd_bitmap_page;
+	get_page(ac->ac_bitmap_page);
+	ac->ac_buddy_page = e3b->bd_buddy_page;
+	get_page(ac->ac_buddy_page);
+}
+
+/*
+ * regular allocator, for general purposes allocation
+ */
+
+void ext3_mb_check_limits(struct ext3_allocation_context *ac,
+					struct ext3_buddy *e3b,
+					int finish_group)
+{
+	struct ext3_sb_info *sbi = EXT3_SB(ac->ac_sb);
+	struct ext3_free_extent *bex = &ac->ac_b_ex;
+	struct ext3_free_extent *gex = &ac->ac_g_ex;
+	struct ext3_free_extent ex;
+	int max;
+
+	/*
+	 * We don't want to scan for a whole year
+	 */
+	if (ac->ac_found > sbi->s_mb_max_to_scan &&
+			!(ac->ac_flags & EXT3_MB_HINT_FIRST)) {
+		ac->ac_status = AC_STATUS_BREAK;
+		return;
+	}
+
+	/*
+	 * Haven't found good chunk so far, let's continue
+	 */
+	if (bex->fe_len < gex->fe_len)
+		return;
+
+	if ((finish_group || ac->ac_found > sbi->s_mb_min_to_scan)
+			&& bex->fe_group == e3b->bd_group) {
+		/* recheck chunk's availability - we don't know
+		 * when it was found (within this lock-unlock
+		 * period or not) */
+		max = mb_find_extent(e3b, 0, bex->fe_start, gex->fe_len, &ex);
+		if (max >= gex->fe_len) {
+			ext3_mb_use_best_found(ac, e3b);
+			return;
+		}
+	}
+}
+
+/*
+ * The routine checks whether found extent is good enough. If it is,
+ * then the extent gets marked used and flag is set to the context
+ * to stop scanning. Otherwise, the extent is compared with the
+ * previous found extent and if new one is better, then it's stored
+ * in the context. Later, the best found extent will be used, if
+ * mballoc can't find good enough extent.
+ *
+ * FIXME: real allocation policy is to be designed yet!
+ */
+static void ext3_mb_measure_extent(struct ext3_allocation_context *ac,
+					struct ext3_free_extent *ex,
+					struct ext3_buddy *e3b)
+{
+	struct ext3_free_extent *bex = &ac->ac_b_ex;
+	struct ext3_free_extent *gex = &ac->ac_g_ex;
+
+	BUG_ON(ex->fe_len <= 0);
+	BUG_ON(ex->fe_len >= EXT3_BLOCKS_PER_GROUP(ac->ac_sb));
+	BUG_ON(ex->fe_start >= EXT3_BLOCKS_PER_GROUP(ac->ac_sb));
+	BUG_ON(ac->ac_status != AC_STATUS_CONTINUE);
+
+	ac->ac_found++;
+
+	/*
+	 * The special case - take what you catch first
+	 */
+	if (unlikely(ac->ac_flags & EXT3_MB_HINT_FIRST)) {
+		*bex = *ex;
+		ext3_mb_use_best_found(ac, e3b);
+		return;
+	}
+
+	/*
+	 * Let's check whether the chuck is good enough
+	 */
+	if (ex->fe_len == gex->fe_len) {
+		*bex = *ex;
+		ext3_mb_use_best_found(ac, e3b);
+		return;
+	}
+
+	/*
+	 * If this is first found extent, just store it in the context
+	 */
+	if (bex->fe_len == 0) {
+		*bex = *ex;
+		return;
+	}
+
+	/*
+	 * If new found extent is better, store it in the context
+	 */
+	if (bex->fe_len < gex->fe_len) {
+		/* if the request isn't satisfied, any found extent
+		 * larger than previous best one is better */
+		if (ex->fe_len > bex->fe_len)
+			*bex = *ex;
+	} else if (ex->fe_len > gex->fe_len) {
+		/* if the request is satisfied, then we try to find
+		 * an extent that still satisfy the request, but is
+		 * smaller than previous one */
+		*bex = *ex;
+	}
+
+	ext3_mb_check_limits(ac, e3b, 0);
+}
+
+static int ext3_mb_try_best_found(struct ext3_allocation_context *ac,
+					struct ext3_buddy *e3b)
+{
+	struct ext3_free_extent ex = ac->ac_b_ex;
+	int group = ex.fe_group, max, err;
+
+	BUG_ON(ex.fe_len <= 0);
+	err = ext3_mb_load_buddy(ac->ac_sb, group, e3b);
+	if (err)
+		return err;
+
+	ext3_lock_group(ac->ac_sb, group);
+	max = mb_find_extent(e3b, 0, ex.fe_start, ex.fe_len, &ex);
+
+	if (max > 0) {
+		ac->ac_b_ex = ex;
+		ext3_mb_use_best_found(ac, e3b);
+	}
+
+	ext3_unlock_group(ac->ac_sb, group);
+	ext3_mb_release_desc(e3b);
+
+	return 0;
+}
+
+static int ext3_mb_find_by_goal(struct ext3_allocation_context *ac,
+				struct ext3_buddy *e3b)
+{
+	int group = ac->ac_g_ex.fe_group, max, err;
+	struct ext3_sb_info *sbi = EXT3_SB(ac->ac_sb);
+	struct ext3_super_block *es = sbi->s_es;
+	struct ext3_free_extent ex;
+
+	err = ext3_mb_load_buddy(ac->ac_sb, group, e3b);
+	if (err)
+		return err;
+
+	ext3_lock_group(ac->ac_sb, group);
+	max = mb_find_extent(e3b, 0, ac->ac_g_ex.fe_start,
+			     ac->ac_g_ex.fe_len, &ex);
+
+	if (max >= ac->ac_g_ex.fe_len && ac->ac_g_ex.fe_len == sbi->s_stripe) {
+		unsigned long start;
+		start = (e3b->bd_group * EXT3_BLOCKS_PER_GROUP(ac->ac_sb) +
+			ex.fe_start + le32_to_cpu(es->s_first_data_block));
+		if (start % sbi->s_stripe == 0) {
+			ac->ac_found++;
+			ac->ac_b_ex = ex;
+			ext3_mb_use_best_found(ac, e3b);
+		}
+	} else if (max >= ac->ac_g_ex.fe_len) {
+		BUG_ON(ex.fe_len <= 0);
+		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
+		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
+		ac->ac_found++;
+		ac->ac_b_ex = ex;
+		ext3_mb_use_best_found(ac, e3b);
+	} else if (max > 0 && (ac->ac_flags & EXT3_MB_HINT_MERGE)) {
+		/* Sometimes, caller may want to merge even small
+		 * number of blocks to an existing extent */
+		BUG_ON(ex.fe_len <= 0);
+		BUG_ON(ex.fe_group != ac->ac_g_ex.fe_group);
+		BUG_ON(ex.fe_start != ac->ac_g_ex.fe_start);
+		ac->ac_found++;
+		ac->ac_b_ex = ex;
+		ext3_mb_use_best_found(ac, e3b);
+	}
+	ext3_unlock_group(ac->ac_sb, group);
+	ext3_mb_release_desc(e3b);
+
+	return 0;
+}
+
+/*
+ * The routine scans buddy structures (not bitmap!) from given order
+ * to max order and tries to find big enough chunk to satisfy the req
+ */
+static void ext3_mb_simple_scan_group(struct ext3_allocation_context *ac,
+					struct ext3_buddy *e3b)
+{
+	struct super_block *sb = ac->ac_sb;
+	struct ext3_group_info *grp = e3b->bd_info;
+	void *buddy;
+	int i, k, max;
+
+	BUG_ON(ac->ac_2order <= 0);
+	for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
+		if (grp->bb_counters[i] == 0)
+			continue;
+
+		buddy = mb_find_buddy(e3b, i, &max);
+		BUG_ON(buddy == NULL);
+
+		k = mb_find_next_zero_bit(buddy, max, 0);
+		BUG_ON(k >= max);
+
+		ac->ac_found++;
+
+		ac->ac_b_ex.fe_len = 1 << i;
+		ac->ac_b_ex.fe_start = k << i;
+		ac->ac_b_ex.fe_group = e3b->bd_group;
+
+		ext3_mb_use_best_found(ac, e3b);
+
+		BUG_ON(ac->ac_b_ex.fe_len != ac->ac_g_ex.fe_len);
+
+		if (EXT3_SB(sb)->s_mb_stats)
+			atomic_inc(&EXT3_SB(sb)->s_bal_2orders);
+
+		break;
+	}
+}
+
+/*
+ * The routine scans the group and measures all found extents.
+ * In order to optimize scanning, caller must pass number of
+ * free blocks in the group, so the routine can know upper limit.
+ */
+static void ext3_mb_complex_scan_group(struct ext3_allocation_context *ac,
+					struct ext3_buddy *e3b)
+{
+	struct super_block *sb = ac->ac_sb;
+	void *bitmap = EXT3_MB_BITMAP(e3b);
+	struct ext3_free_extent ex;
+	int i, free;
+
+	free = e3b->bd_info->bb_free;
+	BUG_ON(free <= 0);
+
+	i = e3b->bd_info->bb_first_free;
+
+	while (free && ac->ac_status == AC_STATUS_CONTINUE) {
+		i = mb_find_next_zero_bit(bitmap, EXT3_BLOCKS_PER_GROUP(sb), i);