ext3-mballoc3-core.patch

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

+		if (i >= EXT3_BLOCKS_PER_GROUP(sb)) {
+			BUG_ON(free != 0);
+			break;
+		}
+
+		mb_find_extent(e3b, 0, i, ac->ac_g_ex.fe_len, &ex);
+		BUG_ON(ex.fe_len <= 0);
+		BUG_ON(free < ex.fe_len);
+
+		ext3_mb_measure_extent(ac, &ex, e3b);
+
+		i += ex.fe_len;
+		free -= ex.fe_len;
+	}
+
+	ext3_mb_check_limits(ac, e3b, 1);
+}
+
+/*
+ * This is a special case for storages like raid5
+ * we try to find stripe-aligned chunks for stripe-size requests
+ */
+static void ext3_mb_scan_aligned(struct ext3_allocation_context *ac,
+				 struct ext3_buddy *e3b)
+{
+	struct super_block *sb = ac->ac_sb;
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	void *bitmap = EXT3_MB_BITMAP(e3b);
+	struct ext3_free_extent ex;
+	unsigned long i, max;
+
+	BUG_ON(sbi->s_stripe == 0);
+
+	/* find first stripe-aligned block */
+	i = e3b->bd_group * EXT3_BLOCKS_PER_GROUP(sb)
+		+ le32_to_cpu(sbi->s_es->s_first_data_block);
+	i = ((i + sbi->s_stripe - 1) / sbi->s_stripe) * sbi->s_stripe;
+	i = (i - le32_to_cpu(sbi->s_es->s_first_data_block))
+			% EXT3_BLOCKS_PER_GROUP(sb);
+
+	while (i < EXT3_BLOCKS_PER_GROUP(sb)) {
+		if (!mb_test_bit(i, bitmap)) {
+			max = mb_find_extent(e3b, 0, i, sbi->s_stripe, &ex);
+			if (max >= sbi->s_stripe) {
+				ac->ac_found++;
+				ac->ac_b_ex = ex;
+				ext3_mb_use_best_found(ac, e3b);
+				break;
+			}
+		}
+		i += sbi->s_stripe;
+	}
+}
+
+static int ext3_mb_good_group(struct ext3_allocation_context *ac,
+				int group, int cr)
+{
+	struct ext3_group_info *grp = EXT3_GROUP_INFO(ac->ac_sb, group);
+	unsigned free, fragments, i, bits;
+
+	BUG_ON(cr < 0 || cr >= 4);
+	BUG_ON(EXT3_MB_GRP_NEED_INIT(grp));
+
+	free = grp->bb_free;
+	fragments = grp->bb_fragments;
+	if (free == 0)
+		return 0;
+	if (fragments == 0)
+		return 0;
+
+	switch (cr) {
+		case 0:
+			BUG_ON(ac->ac_2order == 0);
+			bits = ac->ac_sb->s_blocksize_bits + 1;
+			for (i = ac->ac_2order; i <= bits; i++)
+				if (grp->bb_counters[i] > 0)
+					return 1;
+			break;
+		case 1:
+			if ((free / fragments) >= ac->ac_g_ex.fe_len)
+				return 1;
+			break;
+		case 2:
+			if (free >= ac->ac_g_ex.fe_len)
+				return 1;
+			break;
+		case 3:
+			return 1;
+		default:
+			BUG();
+	}
+
+	return 0;
+}
+
+int ext3_mb_regular_allocator(struct ext3_allocation_context *ac)
+{
+	int group, i, cr, err = 0;
+	struct ext3_sb_info *sbi;
+	struct super_block *sb;
+	struct ext3_buddy e3b;
+
+	sb = ac->ac_sb;
+	sbi = EXT3_SB(sb);
+	BUG_ON(ac->ac_status == AC_STATUS_FOUND);
+
+	/* first, try the goal */
+	err = ext3_mb_find_by_goal(ac, &e3b);
+	if (err || ac->ac_status == AC_STATUS_FOUND)
+		goto out;
+
+	if (unlikely(ac->ac_flags & EXT3_MB_HINT_GOAL_ONLY))
+		goto out;
+
+	i = ffs(ac->ac_g_ex.fe_len);
+	ac->ac_2order = 0;
+	if (i >= sbi->s_mb_order2_reqs) {
+		i--;
+		if ((ac->ac_g_ex.fe_len & (~(1 << i))) == 0)
+			ac->ac_2order = i;
+	}
+
+	group = ac->ac_g_ex.fe_group;
+
+	/* Let's just scan groups to find more-less suitable blocks */
+	cr = ac->ac_2order ? 0 : 1;
+repeat:
+	for (; cr < 4 && ac->ac_status == AC_STATUS_CONTINUE; cr++) {
+		ac->ac_criteria = cr;
+		for (i = 0; i < EXT3_SB(sb)->s_groups_count; group++, i++) {
+			struct ext3_group_info *grp;
+
+			if (group == EXT3_SB(sb)->s_groups_count)
+				group = 0;
+
+			/* quick check to skip empty groups */
+			grp = EXT3_GROUP_INFO(ac->ac_sb, group);
+			if (grp->bb_free == 0)
+				continue;
+
+			if (EXT3_MB_GRP_NEED_INIT(EXT3_GROUP_INFO(sb, group))) {
+				/* we need full data about the group
+				 * to make a good selection */
+				err = ext3_mb_load_buddy(sb, group, &e3b);
+				if (err)
+					goto out;
+				ext3_mb_release_desc(&e3b);
+			}
+
+			/* check is group good for our criteries */
+			if (!ext3_mb_good_group(ac, group, cr))
+				continue;
+
+			err = ext3_mb_load_buddy(sb, group, &e3b);
+			if (err)
+				goto out;
+
+			ext3_lock_group(sb, group);
+			if (!ext3_mb_good_group(ac, group, cr)) {
+				/* someone did allocation from this group */
+				ext3_unlock_group(sb, group);
+				ext3_mb_release_desc(&e3b);
+				continue;
+			}
+
+			ac->ac_groups_scanned++;
+			if (cr == 0)
+				ext3_mb_simple_scan_group(ac, &e3b);
+			else if (cr == 1 && ac->ac_g_ex.fe_len == sbi->s_stripe)
+				ext3_mb_scan_aligned(ac, &e3b);
+			else
+				ext3_mb_complex_scan_group(ac, &e3b);
+
+			ext3_unlock_group(sb, group);
+			ext3_mb_release_desc(&e3b);
+
+			if (ac->ac_status != AC_STATUS_CONTINUE)
+				break;
+		}
+	}
+
+	if (ac->ac_b_ex.fe_len > 0 && ac->ac_status != AC_STATUS_FOUND &&
+	    !(ac->ac_flags & EXT3_MB_HINT_FIRST)) {
+		/*
+		 * We've been searching too long. Let's try to allocate
+		 * the best chunk we've found so far
+		 */
+
+		ext3_mb_try_best_found(ac, &e3b);
+		if (ac->ac_status != AC_STATUS_FOUND) {
+			/*
+			 * Someone more lucky has already allocated it.
+			 * The only thing we can do is just take first
+			 * found block(s)
+			printk(KERN_DEBUG "EXT3-fs: someone won our chunk\n");
+			 */
+			ac->ac_b_ex.fe_group = 0;
+			ac->ac_b_ex.fe_start = 0;
+			ac->ac_b_ex.fe_len = 0;
+			ac->ac_status = AC_STATUS_CONTINUE;
+			ac->ac_flags |= EXT3_MB_HINT_FIRST;
+			cr = 3;
+			atomic_inc(&sbi->s_mb_lost_chunks);
+			goto repeat;
+		}
+	}
+out:
+	return err;
+}
+
+#ifdef EXT3_MB_HISTORY
+struct ext3_mb_proc_session {
+	struct ext3_mb_history *history;
+	struct super_block *sb;
+	int start;
+	int max;
+};
+
+static void *ext3_mb_history_skip_empty(struct ext3_mb_proc_session *s,
+					struct ext3_mb_history *hs,
+					int first)
+{
+	if (hs == s->history + s->max)
+		hs = s->history;
+	if (!first && hs == s->history + s->start)
+		return NULL;
+	while (hs->orig.fe_len == 0) {
+		hs++;
+		if (hs == s->history + s->max)
+			hs = s->history;
+		if (hs == s->history + s->start)
+			return NULL;
+	}
+	return hs;
+}
+
+static void *ext3_mb_seq_history_start(struct seq_file *seq, loff_t *pos)
+{
+	struct ext3_mb_proc_session *s = seq->private;
+	struct ext3_mb_history *hs;
+	int l = *pos;
+
+	if (l == 0)
+		return SEQ_START_TOKEN;
+	hs = ext3_mb_history_skip_empty(s, s->history + s->start, 1);
+	if (!hs)
+		return NULL;
+	while (--l && (hs = ext3_mb_history_skip_empty(s, ++hs, 0)) != NULL);
+	return hs;
+}
+
+static void *ext3_mb_seq_history_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+	struct ext3_mb_proc_session *s = seq->private;
+	struct ext3_mb_history *hs = v;
+
+	++*pos;
+	if (v == SEQ_START_TOKEN)
+		return ext3_mb_history_skip_empty(s, s->history + s->start, 1);
+	else
+		return ext3_mb_history_skip_empty(s, ++hs, 0);
+}
+
+static int ext3_mb_seq_history_show(struct seq_file *seq, void *v)
+{
+	char buf[25], buf2[25], buf3[25], *fmt;
+	struct ext3_mb_history *hs = v;
+
+	if (v == SEQ_START_TOKEN) {
+		seq_printf(seq, "%-5s %-8s %-23s %-23s %-23s %-5s "
+				"%-5s %-2s %-5s %-5s %-5s %-6s\n",
+			   "pid", "inode", "original", "goal", "result","found",
+			   "grps", "cr", "flags", "merge", "tail", "broken");
+		return 0;
+	}
+
+	if (hs->op == EXT3_MB_HISTORY_ALLOC) {
+		fmt = "%-5u %-8u %-23s %-23s %-23s %-5u %-5u %-2u "
+			"%-5u %-5s %-5u %-6u\n";
+		sprintf(buf2, "%lu/%lu/%lu@%lu", hs->result.fe_group,
+			hs->result.fe_start, hs->result.fe_len,
+			hs->result.fe_logical);
+		sprintf(buf, "%lu/%lu/%lu@%lu", hs->orig.fe_group,
+			hs->orig.fe_start, hs->orig.fe_len,
+			hs->orig.fe_logical);
+		sprintf(buf3, "%lu/%lu/%lu@%lu", hs->goal.fe_group,
+			hs->goal.fe_start, hs->goal.fe_len,
+			hs->goal.fe_logical);
+		seq_printf(seq, fmt, hs->pid, hs->ino, buf, buf3, buf2,
+				hs->found, hs->groups, hs->cr, hs->flags,
+				hs->merged ? "M" : "", hs->tail,
+				hs->buddy ? 1 << hs->buddy : 0);
+	} else if (hs->op == EXT3_MB_HISTORY_PREALLOC) {
+		fmt = "%-5u %-8u %-23s %-23s %-23s\n";
+		sprintf(buf2, "%lu/%lu/%lu@%lu", hs->result.fe_group,
+			hs->result.fe_start, hs->result.fe_len,
+			hs->result.fe_logical);
+		sprintf(buf, "%lu/%lu/%lu@%lu", hs->orig.fe_group,
+			hs->orig.fe_start, hs->orig.fe_len,
+			hs->orig.fe_logical);
+		seq_printf(seq, fmt, hs->pid, hs->ino, buf, "", buf2);
+	} else if (hs->op == EXT3_MB_HISTORY_DISCARD) {
+		sprintf(buf2, "%lu/%lu/%lu", hs->result.fe_group,
+			hs->result.fe_start, hs->result.fe_len);
+		seq_printf(seq, "%-5u %-8u %-23s discard\n",
+				hs->pid, hs->ino, buf2);
+	} else if (hs->op == EXT3_MB_HISTORY_FREE) {
+		sprintf(buf2, "%lu/%lu/%lu", hs->result.fe_group,
+			hs->result.fe_start, hs->result.fe_len);
+		seq_printf(seq, "%-5u %-8u %-23s free\n",
+				hs->pid, hs->ino, buf2);
+	}
+	return 0;
+}
+
+static void ext3_mb_seq_history_stop(struct seq_file *seq, void *v)
+{
+}
+
+static struct seq_operations ext3_mb_seq_history_ops = {
+	.start  = ext3_mb_seq_history_start,
+	.next   = ext3_mb_seq_history_next,
+	.stop   = ext3_mb_seq_history_stop,
+	.show   = ext3_mb_seq_history_show,
+};
+
+static int ext3_mb_seq_history_open(struct inode *inode, struct file *file)
+{
+	struct super_block *sb = PDE(inode)->data;
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	struct ext3_mb_proc_session *s;
+	int rc, size;
+
+	s = kmalloc(sizeof(*s), GFP_KERNEL);
+	if (s == NULL)
+		return -ENOMEM;
+	s->sb = sb;
+	size = sizeof(struct ext3_mb_history) * sbi->s_mb_history_max;
+	s->history = kmalloc(size, GFP_KERNEL);
+	if (s->history == NULL) {
+		kfree(s);
+		return -ENOMEM;
+	}
+
+	spin_lock(&sbi->s_mb_history_lock);
+	memcpy(s->history, sbi->s_mb_history, size);
+	s->max = sbi->s_mb_history_max;
+	s->start = sbi->s_mb_history_cur % s->max;
+	spin_unlock(&sbi->s_mb_history_lock);
+
+	rc = seq_open(file, &ext3_mb_seq_history_ops);
+	if (rc == 0) {
+		struct seq_file *m = (struct seq_file *)file->private_data;
+		m->private = s;
+	} else {
+		kfree(s->history);
+		kfree(s);
+	}
+	return rc;
+
+}
+
+static int ext3_mb_seq_history_release(struct inode *inode, struct file *file)
+{
+	struct seq_file *seq = (struct seq_file *)file->private_data;
+	struct ext3_mb_proc_session *s = seq->private;
+	kfree(s->history);
+	kfree(s);
+	return seq_release(inode, file);
+}
+
+static ssize_t ext3_mb_seq_history_write(struct file *file,
+				const char __user *buffer,
+				size_t count, loff_t *ppos)
+{
+	struct seq_file *seq = (struct seq_file *)file->private_data;
+	struct ext3_mb_proc_session *s = seq->private;
+	struct super_block *sb = s->sb;
+	char str[32];
+	int value;
+
+	if (count >= sizeof(str)) {
+		printk(KERN_ERR "EXT3-fs: %s string too long, max %u bytes\n",
+				"mb_history", (int)sizeof(str));
+		return -EOVERFLOW;
+	}
+
+	if (copy_from_user(str, buffer, count))
+		return -EFAULT;
+
+	value = simple_strtol(str, NULL, 0);
+	if (value < 0)
+		return -ERANGE;
+	EXT3_SB(sb)->s_mb_history_filter = value;
+
+	return count;
+}
+
+static struct file_operations ext3_mb_seq_history_fops = {
+	.owner		= THIS_MODULE,
+	.open		= ext3_mb_seq_history_open,
+	.read		= seq_read,
+	.write		= ext3_mb_seq_history_write,
+	.llseek		= seq_lseek,
+	.release	= ext3_mb_seq_history_release,
+};
+
+static void *ext3_mb_seq_groups_start(struct seq_file *seq, loff_t *pos)
+{
+	struct super_block *sb = seq->private;
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	long group;
+
+	if (*pos < 0 || *pos >= sbi->s_groups_count)
+		return NULL;
+
+	group = *pos + 1;
+	return (void *) group;
+}
+
+static void *ext3_mb_seq_groups_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+	struct super_block *sb = seq->private;
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	long group;
+
+	++*pos;
+	if (*pos < 0 || *pos >= sbi->s_groups_count)
+		return NULL;
+	group = *pos + 1;
+	return (void *) group;;
+}
+
+static int ext3_mb_seq_groups_show(struct seq_file *seq, void *v)
+{
+	struct super_block *sb = seq->private;
+	long group = (long) v;
+	int i, err;
+	struct ext3_buddy e3b;
+	struct sg {
+		struct ext3_group_info info;
+		unsigned short counters[16];
+	} sg;
+
+	group--;
+	if (group == 0)
+		seq_printf(seq, "#%-5s: %-5s %-5s %-5s "
+				"[ %-5s %-5s %-5s %-5s %-5s %-5s %-5s "
+				  "%-5s %-5s %-5s %-5s %-5s %-5s %-5s ]\n",
+			   "group", "free", "frags", "first",
+			   "2^0", "2^1", "2^2", "2^3", "2^4", "2^5","2^6",
+			   "2^7", "2^8", "2^9", "2^10", "2^11", "2^12", "2^13");
+
+	i = (sb->s_blocksize_bits + 2) * sizeof(sg.info.bb_counters[0]) +
+		sizeof(struct ext3_group_info);
+	err = ext3_mb_load_buddy(sb, group, &e3b);
+	if (err) {
+		seq_printf(seq, "#%-5lu: I/O error\n", group);
+		return 0;
+	}
+	ext3_lock_group(sb, group);
+	memcpy(&sg, EXT