From: Yuexin Li <lyx1209@xxxxxxxxx>
This patch adds a new freespace tree allocator. The allocator
organizes free space regions in a couple of in-memory rbtrees, one
sorted by length and the other by offset. We use these per-flex-bg
level trees to quickly scan length sorted free space regions and
determine the best region for a given request. This feature can be
enabled by passing "-o freespace_tree" mount option.
Signed-off-by: Yuexin Li <lyx1209@xxxxxxxxx>
Co-developed-by: Harshad Shirwadkar <harshadshirwadkar@xxxxxxxxx>
Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@xxxxxxxxx>
---
fs/ext4/ext4.h | 45 +++
fs/ext4/mballoc.c | 984 ++++++++++++++++++++++++++++++++++++++++++++--
fs/ext4/mballoc.h | 61 ++-
fs/ext4/resize.c | 8 +
fs/ext4/super.c | 35 +-
5 files changed, 1084 insertions(+), 49 deletions(-)
diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 4df6f429de1a..3bb2675d4d40 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -363,6 +363,7 @@ struct flex_groups {
atomic64_t free_clusters;
atomic_t free_inodes;
atomic_t used_dirs;
+ struct ext4_frsp_tree *frsp_tree;
};
#define EXT4_BG_INODE_UNINIT 0x0001 /* Inode table/bitmap not in use */
@@ -1197,6 +1198,12 @@ struct ext4_inode_info {
#define EXT4_MOUNT2_EXPLICIT_JOURNAL_CHECKSUM 0x00000008 /* User explicitly
specified journal checksum */
+
+#define EXT4_MOUNT2_FREESPACE_TREE 0x00000020 /* Enable freespace tree
+ * allocator (turns buddy
+ * allocator off)
+ */
+
#define clear_opt(sb, opt) EXT4_SB(sb)->s_mount_opt &= \
~EXT4_MOUNT_##opt
#define set_opt(sb, opt) EXT4_SB(sb)->s_mount_opt |= \
@@ -1402,6 +1409,30 @@ struct ext4_super_block {
#define ext4_has_strict_mode(sbi) \
(sbi->s_encoding_flags & EXT4_ENC_STRICT_MODE_FL)
+/*
+ * Freespace tree structure
+ */
+struct ext4_frsp_tree {
+ struct rb_root_cached frsp_offset_root; /* Root for offset
+ * sorted tree
+ */
+ struct rb_root_cached frsp_len_root; /* Root for Length
+ * sorted tree
+ */
+ struct mutex frsp_lock;
+ __u8 frsp_flags;
+ __u32 frsp_max_free_len; /* Max free extent in
+ * this flex bg
+ */
+ __u32 frsp_index; /* Tree index (flex bg
+ * number)
+ */
+};
+
+/* Freespace tree flags */
+
+/* Tree is loaded in memory */
+#define EXT4_MB_FRSP_FLAG_LOADED 0x0001
/*
* fourth extended-fs super-block data in memory
*/
@@ -1539,6 +1570,9 @@ struct ext4_sb_info {
struct flex_groups * __rcu *s_flex_groups;
ext4_group_t s_flex_groups_allocated;
+ /* freespace trees stuff */
+ int s_mb_num_frsp_trees;
+
/* workqueue for reserved extent conversions (buffered io) */
struct workqueue_struct *rsv_conversion_wq;
@@ -2653,6 +2687,7 @@ extern int ext4_init_inode_table(struct super_block *sb,
extern void ext4_end_bitmap_read(struct buffer_head *bh, int uptodate);
/* mballoc.c */
+extern int ext4_mb_add_frsp_trees(struct super_block *sb, int ngroups);
extern const struct seq_operations ext4_mb_seq_groups_ops;
extern long ext4_mb_stats;
extern long ext4_mb_max_to_scan;
@@ -3084,6 +3119,16 @@ static inline ext4_group_t ext4_flex_group(struct ext4_sb_info *sbi,
return block_group >> sbi->s_log_groups_per_flex;
}
+static inline struct ext4_frsp_tree *
+ext4_get_frsp_tree(struct super_block *sb, ext4_group_t flex_bg)
+{
+ struct flex_groups *fg;
+
+ fg = sbi_array_rcu_deref(EXT4_SB(sb), s_flex_groups, flex_bg);
+
+ return fg->frsp_tree;
+}
+
static inline unsigned int ext4_flex_bg_size(struct ext4_sb_info *sbi)
{
return 1 << sbi->s_log_groups_per_flex;
diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index 2d8d3d9c7918..74bdc2dcb49c 100644
--- a/fs/ext4/mballoc.c
+++ b/fs/ext4/mballoc.c
@@ -333,6 +333,7 @@
static struct kmem_cache *ext4_pspace_cachep;
static struct kmem_cache *ext4_ac_cachep;
static struct kmem_cache *ext4_free_data_cachep;
+static struct kmem_cache *ext4_freespace_node_cachep;
/* We create slab caches for groupinfo data structures based on the
* superblock block size. There will be one per mounted filesystem for
@@ -352,6 +353,11 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
ext4_group_t group);
static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
+static int ext4_mb_load_allocator(struct super_block *sb, ext4_group_t group,
+ struct ext4_buddy *e4b, int flags);
+static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex);
+static void ext4_mb_unload_allocator(struct ext4_buddy *e4b);
+
/*
* The algorithm using this percpu seq counter goes below:
* 1. We sample the percpu discard_pa_seq counter before trying for block
@@ -395,6 +401,33 @@ static inline void *mb_correct_addr_and_bit(int *bit, void *addr)
return addr;
}
+static inline int ext4_blkno_to_flex_offset(struct super_block *sb,
+ ext4_fsblk_t blkno)
+{
+ return blkno % (ext4_flex_bg_size(EXT4_SB(sb)) *
+ EXT4_SB(sb)->s_blocks_per_group);
+}
+
+static inline ext4_fsblk_t ext4_flex_offset_to_blkno(struct super_block *sb,
+ int flex_bg, int flex_offset)
+{
+ return flex_bg * ext4_flex_bg_size(EXT4_SB(sb)) *
+ EXT4_SB(sb)->s_blocks_per_group + flex_offset;
+}
+
+static inline int ext4_mb_frsp_on(struct super_block *sb)
+{
+ return test_opt2(sb, FREESPACE_TREE) &&
+ EXT4_SB(sb)->s_es->s_log_groups_per_flex;
+}
+
+static inline unsigned int ext4_num_grps_to_flexbg(struct super_block *sb,
+ int ngroups)
+{
+ return (ngroups + ext4_flex_bg_size(EXT4_SB(sb)) - 1) >>
+ (EXT4_SB(sb)->s_es->s_log_groups_per_flex);
+}
+
static inline int mb_test_bit(int bit, void *addr)
{
/*
@@ -453,6 +486,7 @@ static void *mb_find_buddy(struct ext4_buddy *e4b, int order, int *max)
{
char *bb;
+ WARN_ON(ext4_mb_frsp_on(e4b->bd_sb));
BUG_ON(e4b->bd_bitmap == e4b->bd_buddy);
BUG_ON(max == NULL);
@@ -620,6 +654,9 @@ static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
void *buddy;
void *buddy2;
+ if (ext4_mb_frsp_on(sb))
+ return 0;
+
{
static int mb_check_counter;
if (mb_check_counter++ % 100 != 0)
@@ -706,6 +743,729 @@ static int __mb_check_buddy(struct ext4_buddy *e4b, char *file,
#define mb_check_buddy(e4b)
#endif
+/* Generic macro for inserting a new node in cached rbtree */
+#define ext4_mb_rb_insert(__root, __new, __node_t, __entry, __cmp) do { \
+ struct rb_node **iter = &((__root)->rb_root.rb_node), *parent = NULL; \
+ bool leftmost = true; \
+ __node_t *this = NULL; \
+ \
+ while (*iter) { \
+ this = rb_entry(*iter, __node_t, __entry); \
+ parent = *iter; \
+ if (__cmp((__new), this)) { \
+ iter = &((*iter)->rb_left); \
+ } else { \
+ iter = &((*iter)->rb_right); \
+ leftmost = false; \
+ } \
+ } \
+ rb_link_node(&(__new)->__entry, parent, iter); \
+ rb_insert_color_cached(&(__new)->__entry, __root, leftmost); \
+} while (0)
+
+static inline int ext4_mb_frsp_offset_cmp(struct ext4_frsp_node *arg1,
+ struct ext4_frsp_node *arg2)
+{
+ return (arg1->frsp_offset < arg2->frsp_offset);
+}
+
+/*
+ * Free space extents length sorting function, the nodes are sorted in
+ * decreasing order of length
+ */
+static inline int ext4_mb_frsp_len_cmp(struct ext4_frsp_node *arg1,
+ struct ext4_frsp_node *arg2)
+{
+ return (arg1->frsp_len > arg2->frsp_len);
+}
+
+/* insert to offset-indexed tree */
+static void ext4_mb_frsp_insert_off(struct ext4_frsp_tree *tree,
+ struct ext4_frsp_node *new_entry)
+{
+ memset(&new_entry->frsp_node, 0, sizeof(new_entry->frsp_node));
+ ext4_mb_rb_insert(&tree->frsp_offset_root, new_entry,
+ struct ext4_frsp_node, frsp_node, ext4_mb_frsp_offset_cmp);
+}
+
+/* insert to tree sorted by length */
+static void ext4_mb_frsp_insert_len(struct ext4_frsp_tree *tree,
+ struct ext4_frsp_node *new_entry)
+{
+ memset(&new_entry->frsp_len_node, 0, sizeof(new_entry->frsp_len_node));
+ ext4_mb_rb_insert(&tree->frsp_len_root, new_entry,
+ struct ext4_frsp_node, frsp_len_node,
+ ext4_mb_frsp_len_cmp);
+}
+
+#ifdef CONFIG_EXT4_DEBUG
+/* print freespace_tree in pre-order traversal */
+void ext4_mb_frsp_print_tree_len(struct super_block *sb,
+ struct ext4_frsp_tree *tree)
+{
+ unsigned int count = 0;
+ ext4_fsblk_t blk = 0, blk_end = 0;
+ ext4_group_t group = 0, group_end = 0;
+ struct ext4_frsp_node *entry = NULL;
+ struct ext4_sb_info *sbi = EXT4_SB(sb);
+ struct rb_node *cur;
+
+ cur = rb_first_cached(&tree->frsp_len_root);
+ mb_debug(sb, "\nTree\tNode\tlength\tblock\tgroup\n");
+
+ while (cur) {
+ entry = rb_entry(cur, struct ext4_frsp_node, frsp_len_node);
+ count++;
+ blk = ext4_flex_offset_to_blkno(sb, tree->frsp_index,
+ entry->frsp_offset);
+ blk_end = ext4_flex_offset_to_blkno(sb, tree->frsp_index,
+ entry->frsp_offset + entry->frsp_len - 1);
+ group = blk / sbi->s_blocks_per_group;
+ group_end = (blk_end-1) / sbi->s_blocks_per_group;
+ mb_debug(sb, "%u\t%u\t%u\t%u(%lld)--%llu\t%u--%u\n",
+ tree->frsp_index, count, entry->frsp_len,
+ entry->frsp_offset, blk, blk_end, group, group_end);
+ cur = rb_next(cur);
+ }
+}
+#endif
+
+static struct ext4_frsp_node *ext4_mb_frsp_alloc_node(struct super_block *sb)
+{
+ struct ext4_frsp_node *node;
+
+ node = kmem_cache_alloc(ext4_freespace_node_cachep, GFP_NOFS);
+ if (!node)
+ return NULL;
+
+ RB_CLEAR_NODE(&node->frsp_node);
+ RB_CLEAR_NODE(&node->frsp_len_node);
+
+ return node;
+}
+
+static void ext4_mb_frsp_free_node(struct super_block *sb,
+ struct ext4_frsp_node *node)
+{
+ kmem_cache_free(ext4_freespace_node_cachep, node);
+}
+
+/* Evict a tree from memory */
+void ext4_mb_frsp_free_tree(struct super_block *sb, struct ext4_frsp_tree *tree)
+{
+ struct ext4_frsp_node *frsp_node;
+ struct rb_node *node;
+
+ mb_debug(sb, "Evicting tree %d\n", tree->frsp_index);
+ mutex_lock(&tree->frsp_lock);
+ if (!(tree->frsp_flags & EXT4_MB_FRSP_FLAG_LOADED))
+ goto out;
+
+ node = rb_first_cached(&tree->frsp_offset_root);
+ while (node) {
+ frsp_node = rb_entry(node, struct ext4_frsp_node, frsp_node);
+ rb_erase_cached(node, &tree->frsp_offset_root);
+ rb_erase_cached(&frsp_node->frsp_len_node,
+ &tree->frsp_len_root);
+ ext4_mb_frsp_free_node(sb, frsp_node);
+ node = rb_first_cached(&tree->frsp_offset_root);
+ }
+ tree->frsp_flags &= ~EXT4_MB_FRSP_FLAG_LOADED;
+ tree->frsp_offset_root = RB_ROOT_CACHED;
+ tree->frsp_len_root = RB_ROOT_CACHED;
+out:
+ mutex_unlock(&tree->frsp_lock);
+}
+
+/*
+ * Search tree by flexbg offset. Returns the node containing "target". If
+ * no such node is present, returns NULL. Must be called with tree mutex held.
+ */
+struct ext4_frsp_node *ext4_mb_frsp_search_by_off(struct super_block *sb,
+ struct ext4_frsp_tree *tree,
+ ext4_grpblk_t target)
+{
+ struct rb_root *root = &tree->frsp_offset_root.rb_root;
+ struct rb_node *node = root->rb_node;
+ struct ext4_frsp_node *this = NULL;
+
+ while (node) {
+ this = rb_entry(node, struct ext4_frsp_node, frsp_node);
+ if (this->frsp_offset == target)
+ return this;
+ else if (target < this->frsp_offset)
+ node = node->rb_left;
+ else
+ node = node->rb_right;
+ }
+ return NULL;
+}
+
+/*
+ * Check if two entries in freespace tree can be merged together. Nodes
+ * can merge together only if they are physically contiguous and belong
+ * to the same block group.
+ */
+int ext4_mb_frsp_node_can_merge(struct super_block *sb,
+ struct ext4_frsp_node *prev_entry, struct ext4_frsp_node *cur_entry)
+{
+ if (prev_entry->frsp_offset + prev_entry->frsp_len !=
+ cur_entry->frsp_offset)
+ return 0;
+ if (prev_entry->frsp_offset / EXT4_SB(sb)->s_blocks_per_group !=
+ cur_entry->frsp_offset / EXT4_SB(sb)->s_blocks_per_group)
+ return 0;
+ return 1;
+}
+
+/*
+ * Add new free space region to tree. We insert the new node in both, the
+ * length sorted and the flex-bg offset sorted trees. Must be called with
+ * tree mutex held.
+ */
+int ext4_mb_frsp_add_region(struct super_block *sb, struct ext4_frsp_tree *tree,
+ ext4_grpblk_t offset, ext4_grpblk_t len)
+{
+ struct ext4_frsp_node *new_entry = NULL, *next_entry = NULL,
+ *prev_entry = NULL;
+ struct rb_node *left = NULL, *right = NULL;
+
+ new_entry = ext4_mb_frsp_alloc_node(sb);
+ if (!new_entry)
+ return -ENOMEM;
+
+ new_entry->frsp_offset = offset;
+ new_entry->frsp_len = len;
+
+ ext4_mb_frsp_insert_off(tree, new_entry);
+ /* try merge to left and right */
+ /* left */
+ left = rb_prev(&new_entry->frsp_node);
+ if (left) {
+ prev_entry = rb_entry(left, struct ext4_frsp_node, frsp_node);
+ if (ext4_mb_frsp_node_can_merge(sb, prev_entry, new_entry)) {
+ new_entry->frsp_offset = prev_entry->frsp_offset;
+ new_entry->frsp_len += prev_entry->frsp_len;
+ rb_erase_cached(left, &tree->frsp_offset_root);
+ rb_erase_cached(&prev_entry->frsp_len_node,
+ &tree->frsp_len_root);
+ ext4_mb_frsp_free_node(sb, prev_entry);
+ }
+ }
+
+ /* right */
+ right = rb_next(&new_entry->frsp_node);
+ if (right) {
+ next_entry = rb_entry(right, struct ext4_frsp_node, frsp_node);
+ if (ext4_mb_frsp_node_can_merge(sb, new_entry, next_entry)) {
+ new_entry->frsp_len += next_entry->frsp_len;
+ rb_erase_cached(right, &tree->frsp_offset_root);
+ rb_erase_cached(&next_entry->frsp_len_node,
+ &tree->frsp_len_root);
+ ext4_mb_frsp_free_node(sb, next_entry);
+ }
+ }
+ ext4_mb_frsp_insert_len(tree, new_entry);
+
+ return 0;
+}
+
+/*
+ * Free length number of blocks starting at block number block in free space
+ * tree.
+ */
+int ext4_mb_frsp_free_blocks(struct super_block *sb, ext4_group_t group,
+ ext4_grpblk_t block, ext4_grpblk_t length)
+{
+ struct ext4_sb_info *sbi = EXT4_SB(sb);
+ struct ext4_frsp_tree *tree =
+ ext4_get_frsp_tree(sb, ext4_flex_group(sbi, group));
+ int err = 0;
+
+ mutex_lock(&tree->frsp_lock);
+ err = ext4_mb_frsp_add_region(sb, tree,
+ ext4_blkno_to_flex_offset(sb, block), length);
+ mutex_unlock(&tree->frsp_lock);
+
+ return err;
+}
+
+/*
+ * Create freespace tree from on-disk bitmap. Must be called with tree mutex
+ * held. Returns 0 on success, error otherwise.
+ */
+int ext4_mb_frsp_bb_to_tree(struct ext4_buddy *e4b, ext4_group_t group,
+ struct buffer_head *bh)
+{
+ struct super_block *sb = e4b->bd_sb;
+ int length = 0, bit = 0, next;
+ int end = EXT4_SB(sb)->s_blocks_per_group;
+ ext4_fsblk_t block;
+ int ret = 0;
+
+ /* find all unused blocks in bitmap, convert them to new tree node */
+ while (bit < end) {
+ bit = mb_find_next_zero_bit(bh->b_data, end, bit);
+ if (bit >= end)
+ break;
+
+ next = mb_find_next_bit(bh->b_data, end, bit);
+ length = next - bit;
+ block = ext4_group_first_block_no(sb, group) + bit;
+
+ ret = ext4_mb_frsp_add_region(sb, e4b->frsp_tree,
+ ext4_blkno_to_flex_offset(sb, block), length);
+ if (ret)
+ break;
+ bit = next + 1;
+ }
+
+ return ret;
+}
+
+/*
+ * Load one freespace_tree from disk. Assume holding mutex lock on tree.
+ */
+int ext4_mb_frsp_load(struct ext4_buddy *e4b)
+{
+ ext4_group_t ngroups, group_start, group_end, grp;
+ struct ext4_sb_info *sbi = EXT4_SB(e4b->bd_sb);
+ int i, ret = 0;
+ struct buffer_head **bh = NULL;
+
+ if (e4b->frsp_tree->frsp_flags & EXT4_MB_FRSP_FLAG_LOADED)
+ return 0;
+
+ group_start = e4b->frsp_tree->frsp_index * ext4_flex_bg_size(sbi);
+ group_end = min(group_start + ext4_flex_bg_size(sbi),
+ ext4_get_groups_count(e4b->bd_sb)) - 1;
+ ngroups = group_end - group_start + 1;
+
+ bh = kcalloc(ngroups, sizeof(*bh), GFP_KERNEL);
+ if (!bh)
+ return -ENOMEM;
+ for (i = 0; i < ngroups; i++) {
+ grp = i + group_start;
+ bh[i] = ext4_read_block_bitmap_nowait(e4b->bd_sb, grp, false);
+ if (IS_ERR(bh[i])) {
+ ret = PTR_ERR(bh[i]);
+ goto out;
+ }
+ }
+ for (i = 0; i < ngroups; i++) {
+ grp = i + group_start;
+ if (!bitmap_uptodate(bh[i])) {
+ ret = ext4_wait_block_bitmap(e4b->bd_sb, grp, bh[i]);
+ if (ret)
+ goto out;
+ }
+ ret = ext4_mb_frsp_bb_to_tree(e4b, grp, bh[i]);
+ if (ret)
+ goto out;
+ }
+ e4b->frsp_tree->frsp_flags |= EXT4_MB_FRSP_FLAG_LOADED;
+out:
+ for (i = 0; i < ngroups; i++) {
+ if (!IS_ERR_OR_NULL(bh[i]))
+ put_bh(bh[i]);
+ if (!ret && IS_ERR(bh[i]))
+ ret = PTR_ERR(bh[i]);
+ }
+ kfree(bh);
+ return ret;
+
+}
+
+/*
+ * Determine if node with length len is better than what we have found until
+ * now. Return 1 if that is the case, 0 otherwise. If len is exact match,
+ * set *best = 1.
+ */
+static int ext4_mb_frsp_is_better(struct ext4_allocation_context *ac,
+ int len, int *best)
+{
+ struct ext4_tree_extent *btx = &ac->ac_b_tree_ex;
+ struct ext4_free_extent *gex = &ac->ac_g_ex;
+
+ if (best)
+ *best = 0;
+ if (len == gex->fe_len) {
+ if (best)
+ *best = 1;
+ return 1;
+ }
+ if (ac->ac_criteria == 0 && len < gex->fe_len)
+ return 0;
+ /*
+ * See if the new node is cloer to goal length than
+ * the best extent found so far
+ */
+ if (btx->te_len < gex->fe_len && len > btx->te_len)
+ return 1;
+ if (len > gex->fe_len && len < btx->te_len)
+ return 1;
+ return 0;
+}
+
+/*
+ * check if we have scanned sufficient freespace candidates
+ * stop scanning if reached/exceeded s_max_to_scan
+ */
+static void ext4_mb_frsp_check_limits(struct ext4_allocation_context *ac)
+{
+ struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
+
+ if (ac->ac_status == AC_STATUS_FOUND)
+ return;
+
+ /*
+ * Exceeded max number of nodes to scan
+ */
+ if (ac->ac_found > sbi->s_mb_max_to_scan &&
+ !(ac->ac_flags & EXT4_MB_HINT_FIRST))
+ ac->ac_status = AC_STATUS_BREAK;
+}
+
+/*
+ * Mark free space in selected tree node as used and update the tree.
+ * This must be called with tree lock.
+ */
+static void ext4_mb_frsp_use_best_found(struct ext4_allocation_context *ac,
+ ext4_group_t flex, struct ext4_frsp_node *selected)
+{
+ struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
+ struct ext4_tree_extent *btx = &ac->ac_b_tree_ex;
+ struct ext4_free_extent *bex;
+ unsigned int group_no;
+ struct ext4_buddy e4b;
+
+ WARN_ON(ac->ac_status == AC_STATUS_FOUND);
+ btx->te_len = min(btx->te_len, ac->ac_g_ex.fe_len);
+ ac->ac_status = AC_STATUS_FOUND;
+
+ /* update ac best-found-extent */
+ bex = &ac->ac_b_ex;
+ group_no = (btx->te_flex * ext4_flex_bg_size(sbi)) +
+ (btx->te_flex_start / sbi->s_blocks_per_group);
+ bex->fe_start = btx->te_flex_start % sbi->s_blocks_per_group;
+ bex->fe_group = group_no;
+ bex->fe_len = btx->te_len;
+ bex->fe_node = selected;
+
+ /* Add free blocks to our tree */
+ ext4_mb_load_allocator(ac->ac_sb, group_no, &e4b,
+ EXT4_ALLOCATOR_FRSP_NOLOAD);
+ mb_mark_used(&e4b, bex);
+ ext4_mb_unload_allocator(&e4b);
+}
+/*
+ * The routine checks whether found tree node is good enough. If it is,
+ * then the tree node gets marked used and flag is set to the context
+ * to stop scanning.
+ *
+ * Otherwise, the tree node is compared with the previous found extent and
+ * if new one is better, then it's stored in the context.
+ *
+ * Later, the best found tree node will be used, if mballoc can't find good
+ * enough extent.
+ */
+static int ext4_mb_frsp_measure_node(struct ext4_allocation_context *ac,
+ int tree_idx, struct ext4_frsp_node *cur,
+ int goal)
+{
+ struct ext4_tree_extent *btx = &ac->ac_b_tree_ex;
+ ext4_fsblk_t start;
+ int best_found = 0, max;
+
+ WARN_ON(btx->te_len < 0);
+ WARN_ON(ac->ac_status != AC_STATUS_CONTINUE);
+
+ if (goal) {
+ start = ext4_group_first_block_no(ac->ac_sb,
+ ac->ac_g_ex.fe_group) +
+ ac->ac_g_ex.fe_start;
+ if (cur->frsp_offset > ext4_blkno_to_flex_offset(ac->ac_sb,
+ start))
+ return 0;
+ max = cur->frsp_offset + cur->frsp_len -
+ ext4_blkno_to_flex_offset(ac->ac_sb, start);
+ if (max >= ac->ac_g_ex.fe_len &&
+ ac->ac_g_ex.fe_len == EXT4_SB(ac->ac_sb)->s_stripe) {
+ if (do_div(start, EXT4_SB(ac->ac_sb)->s_stripe) != 0)
+ return 0;
+ best_found = 1;
+ } else if (max >= ac->ac_g_ex.fe_len) {
+ best_found = 1;
+ } else if (max > 0 && (ac->ac_flags & EXT4_MB_HINT_MERGE)) {
+ /*
+ * Sometimes, caller may want to merge even small
+ * number of blocks to an existing extent
+ */
+ best_found = 1;
+
+ } else {
+ return 0;
+ }
+ ac->ac_found++;
+ goto use_extent;
+ }
+ ac->ac_found++;
+
+ /* The special case - take what you catch first */
+ if (unlikely(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
+ best_found = 1;
+ goto use_extent;
+ }
+
+ /*
+ * Prefer not allocating blocks in first group in flex bg for data
+ * blocks.
+ */
+ if (unlikely((ac->ac_criteria < 2) &&
+ (ac->ac_flags & EXT4_MB_HINT_DATA) &&
+ (cur->frsp_offset < EXT4_BLOCKS_PER_GROUP(ac->ac_sb))))
+ return 1;
+
+
+ /* If this is first found extent, just store it in the context */
+ if (btx->te_len == 0)
+ goto use_extent;
+
+ if (ext4_mb_frsp_is_better(ac, cur->frsp_len, &best_found))
+ goto use_extent;
+
+ ext4_mb_frsp_check_limits(ac);
+ return 0;
+
+use_extent:
+ btx->te_flex = tree_idx;
+ if (goal) {
+ btx->te_flex_start = ext4_blkno_to_flex_offset(ac->ac_sb,
+ start);
+ btx->te_len = max;
+ } else {
+ btx->te_flex_start = cur->frsp_offset;
+ btx->te_len = cur->frsp_len;
+ }
+ if (best_found)
+ ext4_mb_frsp_use_best_found(ac, tree_idx, cur);
+ ext4_mb_frsp_check_limits(ac);
+ return 1;
+}
+
+/* Search by goal */
+static noinline_for_stack
+void ext4_mb_frsp_find_by_goal(struct ext4_allocation_context *ac)
+{
+ struct ext4_frsp_node *cur = NULL;
+ unsigned int tree_blk;
+ ext4_fsblk_t blk;
+ struct ext4_buddy e4b;
+ int ret;
+
+ if (!(ac->ac_flags & EXT4_MB_HINT_TRY_GOAL))
+ return;
+
+ /* compute start node offset in tree */
+ blk = ext4_group_first_block_no(ac->ac_sb, ac->ac_g_ex.fe_group) +
+ ac->ac_g_ex.fe_start;
+ tree_blk = ext4_blkno_to_flex_offset(ac->ac_sb, blk);
+
+ ret = ext4_mb_load_allocator(ac->ac_sb, ac->ac_g_ex.fe_group, &e4b, 0);
+ if (ret)
+ return;
+
+ /* try goal block and its freespace_tree first */
+ mutex_lock(&e4b.frsp_tree->frsp_lock);
+ cur = ext4_mb_frsp_search_by_off(ac->ac_sb, e4b.frsp_tree, tree_blk);
+ if (cur && tree_blk < cur->frsp_offset + cur->frsp_len - 1)
+ ext4_mb_frsp_measure_node(ac, e4b.frsp_tree->frsp_index, cur,
+ 1 /* searching by goal */);
+
+ mutex_unlock(&e4b.frsp_tree->frsp_lock);
+ ext4_mb_unload_allocator(&e4b);
+}
+
+static void ext4_mb_frsp_process(struct ext4_allocation_context *ac,
+ struct ext4_frsp_tree *tree)
+{
+ struct ext4_frsp_node *cur = NULL;
+ struct rb_node *node = NULL;
+ int ret;
+
+ node = rb_first_cached(&tree->frsp_len_root);
+ mb_debug(ac->ac_sb, "Processing tree index %d, flags = %x\n",
+ tree->frsp_index, tree->frsp_flags);
+ /*
+ * In order to serve the "No data blocks in first group in a flexbg"
+ * requirement, we cannot do a O(Log N) search here. TODO: it's possible
+ * to that at CR=2, where that requirement doesn't apply.
+ */
+ while (node && ac->ac_status == AC_STATUS_CONTINUE) {
+ cur = rb_entry(node, struct ext4_frsp_node, frsp_len_node);
+ if (ac->ac_criteria == 0 && cur->frsp_len < ac->ac_g_ex.fe_len)
+ return;
+ ret = ext4_mb_frsp_measure_node(ac, tree->frsp_index, cur,
+ 0 /* searching by len */);
+ if (ret == 0)
+ return;
+ node = rb_next(node);
+ }
+}
+
+/* allocator for freespace_tree */
+static noinline_for_stack int
+ext4_mb_tree_allocator(struct ext4_allocation_context *ac)
+{
+ struct ext4_buddy e4b;
+ struct ext4_sb_info *sbi;
+ struct super_block *sb;
+ struct ext4_frsp_tree *tree = NULL;
+ struct ext4_frsp_node *cur = NULL;
+ struct ext4_tree_extent *btx = NULL;
+ int ret = 0, start_idx = 0, tree_idx, j;
+
+ sb = ac->ac_sb;
+ btx = &ac->ac_b_tree_ex;
+ sbi = EXT4_SB(sb);
+
+ start_idx = ext4_flex_group(sbi, ac->ac_g_ex.fe_group);
+ mb_debug(sb, "requested size %d\n", ac->ac_g_ex.fe_len);
+ /* First try searching from goal blk in start-idx-th freespace tree */
+ ext4_mb_frsp_find_by_goal(ac);
+ if (ac->ac_status == AC_STATUS_FOUND)
+ goto out;
+
+ if (unlikely(ac->ac_flags & EXT4_MB_HINT_GOAL_ONLY))
+ goto out;
+
+ ac->ac_criteria = 0;
+ ac->ac_groups_scanned = 0;
+repeat:
+
+ /* Loop through the rest of trees (flex_bg) */
+ for (j = start_idx;
+ (ac->ac_groups_scanned < sbi->s_mb_num_frsp_trees) &&
+ ac->ac_status == AC_STATUS_CONTINUE; j++) {
+ ac->ac_groups_scanned++;
+ tree_idx = (j % sbi->s_mb_num_frsp_trees);
+
+ ret = ext4_mb_load_allocator(sb,
+ tree_idx * ext4_flex_bg_size(sbi), &e4b, 0);
+ if (ret)
+ goto out;
+ mutex_lock(&e4b.frsp_tree->frsp_lock);
+ ext4_mb_frsp_process(ac, e4b.frsp_tree);
+ mutex_unlock(&e4b.frsp_tree->frsp_lock);
+ ext4_mb_unload_allocator(&e4b);
+ }
+
+ if (ac->ac_status != AC_STATUS_FOUND) {
+ if (ac->ac_criteria < 2) {
+ ac->ac_criteria++;
+ ac->ac_groups_scanned = 0;
+ mb_debug(sb, "Falling back to CR=%d", ac->ac_criteria);
+ goto repeat;
+ }
+ if (btx->te_len > 0 && !(ac->ac_flags & EXT4_MB_HINT_FIRST)) {
+ e4b.frsp_flags = 0;
+ ret = ext4_mb_load_allocator(sb, btx->te_flex *
+ ext4_flex_bg_size(sbi), &e4b, 0);
+ if (ret)
+ goto out;
+ tree = e4b.frsp_tree;
+ mutex_lock(&tree->frsp_lock);
+ cur = ext4_mb_frsp_search_by_off(sb, tree,
+ btx->te_flex_start);
+ if (cur) {
+ ext4_mb_frsp_use_best_found(ac, btx->te_flex,
+ cur);
+ mutex_unlock(&tree->frsp_lock);
+ ext4_mb_unload_allocator(&e4b);
+
+ } else {
+ /*
+ * Someone else took this freespace node before
+ * us. Reset the best-found tree extent, and
+ * turn on FIRST HINT (greedy).
+ */
+ mutex_unlock(&tree->frsp_lock);
+ ac->ac_b_tree_ex.te_flex_start = 0;
+ ac->ac_b_tree_ex.te_flex = 0;
+ ac->ac_b_tree_ex.te_len = 0;
+ ac->ac_status = AC_STATUS_CONTINUE;
+ ac->ac_flags |= EXT4_MB_HINT_FIRST;
+ ac->ac_groups_scanned = 0;
+ ext4_mb_unload_allocator(&e4b);
+ goto repeat;
+ }
+ }
+ }
+
+ ret = btx->te_len ? 0 : -ENOSPC;
+
+out:
+ return ret;
+}
+
+static void ext4_mb_frsp_init_tree(struct ext4_frsp_tree *tree, int index)
+{
+ tree->frsp_offset_root = RB_ROOT_CACHED;
+ tree->frsp_len_root = RB_ROOT_CACHED;
+ mutex_init(&(tree->frsp_lock));
+ tree->frsp_flags = 0;
+ tree->frsp_index = index;
+}
+
+int ext4_mb_init_freespace_trees(struct super_block *sb)
+{
+ struct ext4_sb_info *sbi = EXT4_SB(sb);
+ struct flex_groups *fg;
+ int i;
+
+ sbi->s_mb_num_frsp_trees =
+ ext4_num_grps_to_flexbg(sb, ext4_get_groups_count(sb));
+
+ for (i = 0; i < sbi->s_mb_num_frsp_trees; i++) {
+ fg = sbi_array_rcu_deref(sbi, s_flex_groups, i);
+ fg->frsp_tree = kzalloc(sizeof(struct ext4_frsp_tree),
+ GFP_KERNEL);
+ if (!fg->frsp_tree)
+ return -ENOMEM;
+ ext4_mb_frsp_init_tree(fg->frsp_tree, i);
+ }
+
+ return 0;
+}
+
+int ext4_mb_add_frsp_trees(struct super_block *sb, int ngroups)
+{
+ struct ext4_sb_info *sbi = EXT4_SB(sb);
+ int flex_bg_count, old_trees_count = sbi->s_mb_num_frsp_trees;
+ int i;
+
+ if (!ext4_mb_frsp_on(sb))
+ return 0;
+
+ flex_bg_count = ext4_num_grps_to_flexbg(sb, ngroups);
+ if (old_trees_count > 0)
+ ext4_mb_frsp_free_tree(sb, ext4_get_frsp_tree(sb,
+ old_trees_count - 1));
+
+ for (i = old_trees_count; i < flex_bg_count; i++) {
+ struct flex_groups *fg;
+
+ fg = sbi_array_rcu_deref(sbi, s_flex_groups, i);
+ fg->frsp_tree = kzalloc(sizeof(*fg->frsp_tree), GFP_KERNEL);
+ if (!fg->frsp_tree)
+ return -ENOMEM;
+ ext4_mb_frsp_init_tree(fg->frsp_tree, i);
+ }
+ sbi->s_mb_num_frsp_trees = flex_bg_count;
+
+ return 0;
+}
+
/*
* Divide blocks started from @first with length @len into
* smaller chunks with power of 2 blocks.
@@ -1042,6 +1802,9 @@ static int ext4_mb_get_buddy_page_lock(struct super_block *sb,
e4b->bd_buddy_page = NULL;
e4b->bd_bitmap_page = NULL;
+ if (ext4_mb_frsp_on(sb))
+ return 0;
+
blocks_per_page = PAGE_SIZE / sb->s_blocksize;
/*
* the buddy cache inode stores the block bitmap
@@ -1099,6 +1862,7 @@ int ext4_mb_init_group(struct super_block *sb, ext4_group_t group, gfp_t gfp)
struct page *page;
int ret = 0;
+ WARN_ON(ext4_mb_frsp_on(sb));
might_sleep();
mb_debug(sb, "init group %u\n", group);
this_grp = ext4_get_group_info(sb, group);
@@ -1156,6 +1920,11 @@ int ext4_mb_init_group(struct super_block *sb, ext4_group_t group, gfp_t gfp)
* Locking note: This routine calls ext4_mb_init_cache(), which takes the
* block group lock of all groups for this page; do not hold the BG lock when
* calling this routine!
+ *
+ * For freespace trees, do not hold tree mutex while calling this routine.
+ * It is okay to hold that mutex only if EXT4_ALLOCATOR_FRSP_NOLOAD flag is
+ * set in e4b->frsp_flags. If that flag is set, this function doesn't try
+ * to load an unloaded tree.
*/
static noinline_for_stack int
ext4_mb_load_allocator_gfp(struct super_block *sb, ext4_group_t group,
@@ -1166,7 +1935,7 @@ ext4_mb_load_allocator_gfp(struct super_block *sb, ext4_group_t group,
int pnum;
int poff;
struct page *page;
- int ret;
+ int ret = 0;
struct ext4_group_info *grp;
struct ext4_sb_info *sbi = EXT4_SB(sb);
struct inode *inode = sbi->s_buddy_cache;
@@ -1183,6 +1952,22 @@ ext4_mb_load_allocator_gfp(struct super_block *sb, ext4_group_t group,
e4b->bd_group = group;
e4b->bd_buddy_page = NULL;
e4b->bd_bitmap_page = NULL;
+ if (ext4_mb_frsp_on(sb)) {
+ e4b->frsp_tree = ext4_get_frsp_tree(sb,
+ ext4_flex_group(sbi, group));
+ e4b->frsp_flags = flags;
+ if (flags & EXT4_ALLOCATOR_FRSP_NOLOAD)
+ return 0;
+
+ mutex_lock(&e4b->frsp_tree->frsp_lock);
+ if (e4b->frsp_tree->frsp_flags & EXT4_MB_FRSP_FLAG_LOADED) {
+ mutex_unlock(&e4b->frsp_tree->frsp_lock);
+ return 0;
+ }
+ ret = ext4_mb_frsp_load(e4b);
+ mutex_unlock(&e4b->frsp_tree->frsp_lock);
+ return ret;
+ }
if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
/*
@@ -1305,6 +2090,8 @@ static int ext4_mb_load_allocator(struct super_block *sb, ext4_group_t group,
static void ext4_mb_unload_allocator(struct ext4_buddy *e4b)
{
+ if (ext4_mb_frsp_on(e4b->bd_sb))
+ return;
if (e4b->bd_bitmap_page)
put_page(e4b->bd_bitmap_page);
if (e4b->bd_buddy_page)
@@ -1497,6 +2284,16 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
if (first < e4b->bd_info->bb_first_free)
e4b->bd_info->bb_first_free = first;
+ if (ext4_mb_frsp_on(sb)) {
+ ext4_grpblk_t first_blk = EXT4_C2B(EXT4_SB(sb), first) +
+ ext4_group_first_block_no(sb, e4b->bd_group);
+
+ ext4_unlock_group(sb, e4b->bd_group);
+ ext4_mb_frsp_free_blocks(sb, e4b->bd_group, first_blk, count);
+ ext4_lock_group(sb, e4b->bd_group);
+ return;
+ }
+
/* access memory sequentially: check left neighbour,
* clear range and then check right neighbour
*/
@@ -1563,6 +2360,9 @@ static int mb_find_extent(struct ext4_buddy *e4b, int block,
assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
BUG_ON(ex == NULL);
+ if (ext4_mb_frsp_on(e4b->bd_sb))
+ return 0;
+
buddy = mb_find_buddy(e4b, 0, &max);
BUG_ON(buddy == NULL);
BUG_ON(block >= max);
@@ -1627,17 +2427,74 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
unsigned ret = 0;
int len0 = len;
void *buddy;
+ ext4_grpblk_t flex_offset;
BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
BUG_ON(e4b->bd_group != ex->fe_group);
+
+ e4b->bd_info->bb_free -= len;
+ if (e4b->bd_info->bb_first_free == start)
+ e4b->bd_info->bb_first_free += len;
+
+ if (ext4_mb_frsp_on(e4b->bd_sb)) {
+ struct ext4_frsp_node *new;
+
+ flex_offset = ext4_blkno_to_flex_offset(e4b->bd_sb,
+ ext4_group_first_block_no(e4b->bd_sb,
+ e4b->bd_group) + ex->fe_start);
+ if (!ex->fe_node) {
+ ex->fe_node = ext4_mb_frsp_search_by_off(e4b->bd_sb,
+ e4b->frsp_tree, flex_offset);
+ if (!ex->fe_node)
+ return 0;
+ }
+ /*
+ * Remove the node from the trees before we modify these since
+ * we will change the length and / or offset of this node.
+ */
+ rb_erase_cached(&ex->fe_node->frsp_node,
+ &e4b->frsp_tree->frsp_offset_root);
+ rb_erase_cached(&ex->fe_node->frsp_len_node,
+ &e4b->frsp_tree->frsp_len_root);
+ RB_CLEAR_NODE(&ex->fe_node->frsp_node);
+ RB_CLEAR_NODE(&ex->fe_node->frsp_len_node);
+ if (flex_offset > ex->fe_node->frsp_offset) {
+ if (flex_offset + ex->fe_len !=
+ ex->fe_node->frsp_offset +
+ ex->fe_node->frsp_len) {
+ /* Need to split the node */
+ new = ext4_mb_frsp_alloc_node(e4b->bd_sb);
+ if (!new)
+ return -ENOMEM;
+ new->frsp_offset = flex_offset + ex->fe_len;
+ new->frsp_len = (ex->fe_node->frsp_offset +
+ ex->fe_node->frsp_len) -
+ new->frsp_offset;
+ ext4_mb_frsp_insert_len(e4b->frsp_tree, new);
+ ext4_mb_frsp_insert_off(e4b->frsp_tree, new);
+ }
+ ex->fe_node->frsp_len = flex_offset -
+ ex->fe_node->frsp_offset;
+ } else if (ex->fe_len < ex->fe_node->frsp_len) {
+ /* used only a part: update node */
+ ex->fe_node->frsp_offset += ex->fe_len;
+ ex->fe_node->frsp_len -= ex->fe_len;
+ } else {
+ ext4_mb_frsp_free_node(e4b->bd_sb, ex->fe_node);
+ return 0;
+ }
+
+ ext4_mb_frsp_insert_len(e4b->frsp_tree, ex->fe_node);
+ ext4_mb_frsp_insert_off(e4b->frsp_tree, ex->fe_node);
+
+ return 0;
+ }
+
assert_spin_locked(ext4_group_lock_ptr(e4b->bd_sb, e4b->bd_group));
mb_check_buddy(e4b);
mb_mark_used_double(e4b, start, len);
this_cpu_inc(discard_pa_seq);
- e4b->bd_info->bb_free -= len;
- if (e4b->bd_info->bb_first_free == start)
- e4b->bd_info->bb_first_free += len;
/* let's maintain fragments counter */
if (start != 0)
@@ -2778,6 +3635,13 @@ static int ext4_mb_init_backend(struct super_block *sb)
rcu_read_lock();
kvfree(rcu_dereference(sbi->s_group_info));
rcu_read_unlock();
+ if (ext4_mb_frsp_on(sb)) {
+ for (i = 0; i < sbi->s_mb_num_frsp_trees; i++) {
+ struct ext4_frsp_tree *tree = ext4_get_frsp_tree(sb, i);
+
+ kfree(tree);
+ }
+ }
return -ENOMEM;
}
@@ -2874,6 +3738,13 @@ int ext4_mb_init(struct super_block *sb)
i++;
} while (i <= sb->s_blocksize_bits + 1);
+ /* init for freespace trees */
+ if (ext4_mb_frsp_on(sb)) {
+ ret = ext4_mb_init_freespace_trees(sb);
+ if (ret)
+ goto out;
+ }
+
spin_lock_init(&sbi->s_md_lock);
spin_lock_init(&sbi->s_bal_lock);
sbi->s_mb_free_pending = 0;
@@ -2940,6 +3811,13 @@ int ext4_mb_init(struct super_block *sb)
sbi->s_mb_offsets = NULL;
kfree(sbi->s_mb_maxs);
sbi->s_mb_maxs = NULL;
+ if (ext4_mb_frsp_on(sb)) {
+ for (i = 0; i < sbi->s_mb_num_frsp_trees; i++) {
+ struct ext4_frsp_tree *tree = ext4_get_frsp_tree(sb, i);
+
+ kfree(tree);
+ }
+ }
return ret;
}
@@ -3084,8 +3962,10 @@ static void ext4_free_data_in_buddy(struct super_block *sb,
/* No more items in the per group rb tree
* balance refcounts from ext4_mb_free_metadata()
*/
- put_page(e4b.bd_buddy_page);
- put_page(e4b.bd_bitmap_page);
+ if (!ext4_mb_frsp_on(sb)) {
+ put_page(e4b.bd_buddy_page);
+ put_page(e4b.bd_bitmap_page);
+ }
}
ext4_unlock_group(sb, entry->efd_group);
kmem_cache_free(ext4_free_data_cachep, entry);
@@ -3163,9 +4043,14 @@ int __init ext4_init_mballoc(void)
SLAB_RECLAIM_ACCOUNT);
if (ext4_free_data_cachep == NULL)
goto out_ac_free;
+ ext4_freespace_node_cachep = KMEM_CACHE(ext4_frsp_node,
+ SLAB_RECLAIM_ACCOUNT);
+ if (ext4_freespace_node_cachep == NULL)
+ goto out_frsp_free;
return 0;
-
+out_frsp_free:
+ kmem_cache_destroy(ext4_free_data_cachep);
out_ac_free:
kmem_cache_destroy(ext4_ac_cachep);
out_pa_free:
@@ -3184,6 +4069,7 @@ void ext4_exit_mballoc(void)
kmem_cache_destroy(ext4_pspace_cachep);
kmem_cache_destroy(ext4_ac_cachep);
kmem_cache_destroy(ext4_free_data_cachep);
+ kmem_cache_destroy(ext4_freespace_node_cachep);
ext4_groupinfo_destroy_slabs();
}
@@ -3686,6 +4572,9 @@ ext4_mb_use_preallocated(struct ext4_allocation_context *ac)
if (!(ac->ac_flags & EXT4_MB_HINT_DATA))
return false;
+ if (ext4_mb_frsp_on(ac->ac_sb))
+ return 0;
+
/* first, try per-file preallocation */
rcu_read_lock();
list_for_each_entry_rcu(pa, &ei->i_prealloc_list, pa_inode_list) {
@@ -4362,6 +5251,8 @@ static int ext4_mb_pa_alloc(struct ext4_allocation_context *ac)
struct ext4_prealloc_space *pa;
BUG_ON(ext4_pspace_cachep == NULL);
+ if (ext4_mb_frsp_on(ac->ac_sb))
+ return 0;
pa = kmem_cache_zalloc(ext4_pspace_cachep, GFP_NOFS);
if (!pa)
return -ENOMEM;
@@ -4374,6 +5265,8 @@ static void ext4_mb_pa_free(struct ext4_allocation_context *ac)
{
struct ext4_prealloc_space *pa = ac->ac_pa;
+ if (ext4_mb_frsp_on(ac->ac_sb))
+ return;
BUG_ON(!pa);
ac->ac_pa = NULL;
WARN_ON(!atomic_dec_and_test(&pa->pa_count));
@@ -4547,6 +5440,13 @@ ext4_mb_initialize_context(struct ext4_allocation_context *ac,
ac->ac_o_ex.fe_len = len;
ac->ac_g_ex = ac->ac_o_ex;
ac->ac_flags = ar->flags;
+ if (ext4_mb_frsp_on(sb))
+ ac->ac_flags |= EXT4_MB_HINT_NOPREALLOC;
+
+ /* set up best-found tree node */
+ ac->ac_b_tree_ex.te_flex_start = 0;
+ ac->ac_b_tree_ex.te_flex = 0;
+ ac->ac_b_tree_ex.te_len = 0;
/* we have to define context: we'll we work with a file or
* locality group. this is a policy, actually */
@@ -4867,7 +5767,11 @@ ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
goto errout;
repeat:
/* allocate space in core */
- *errp = ext4_mb_regular_allocator(ac);
+ if (ext4_mb_frsp_on(sb))
+ *errp = ext4_mb_tree_allocator(ac);
+ else
+ *errp = ext4_mb_regular_allocator(ac);
+
/*
* pa allocated above is added to grp->bb_prealloc_list only
* when we were able to allocate some block i.e. when
@@ -4880,8 +5784,13 @@ ext4_fsblk_t ext4_mb_new_blocks(handle_t *handle,
ext4_discard_allocated_blocks(ac);
goto errout;
}
- if (ac->ac_status == AC_STATUS_FOUND &&
- ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len)
+ /*
+ * Freespace trees should never return more than what was asked
+ * for.
+ */
+ if (!ext4_mb_frsp_on(sb) &&
+ (ac->ac_status == AC_STATUS_FOUND &&
+ ac->ac_o_ex.fe_len >= ac->ac_f_ex.fe_len))
ext4_mb_pa_free(ac);
}
if (likely(ac->ac_status == AC_STATUS_FOUND)) {
@@ -4972,13 +5881,12 @@ ext4_mb_free_metadata(handle_t *handle, struct ext4_buddy *e4b,
struct rb_node *parent = NULL, *new_node;
BUG_ON(!ext4_handle_valid(handle));
- BUG_ON(e4b->bd_bitmap_page == NULL);
- BUG_ON(e4b->bd_buddy_page == NULL);
+ BUG_ON(!ext4_mb_frsp_on(sb) && e4b->bd_bitmap_page == NULL);
new_node = &new_entry->efd_node;
cluster = new_entry->efd_start_cluster;
- if (!*n) {
+ if (!*n && !ext4_mb_frsp_on(sb)) {
/* first free block exent. We need to
protect buddy cache from being freed,
* otherwise we'll refresh it from
@@ -5457,6 +6365,7 @@ __acquires(bitlock)
ex.fe_start = start;
ex.fe_group = group;
ex.fe_len = count;
+ ex.fe_node = NULL;
/*
* Mark blocks used, so no one can reuse them while
@@ -5496,6 +6405,7 @@ ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
void *bitmap;
ext4_grpblk_t next, count = 0, free_count = 0;
struct ext4_buddy e4b;
+ struct buffer_head *bh = NULL;
int ret = 0;
trace_ext4_trim_all_free(sb, group, start, max);
@@ -5506,7 +6416,17 @@ ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
ret, group);
return ret;
}
- bitmap = e4b.bd_bitmap;
+
+ if (ext4_mb_frsp_on(sb)) {
+ bh = ext4_read_block_bitmap(sb, group);
+ if (IS_ERR(bh)) {
+ ret = PTR_ERR(bh);
+ goto out;
+ }
+ bitmap = bh->b_data;
+ } else {
+ bitmap = e4b.bd_bitmap;
+ }
ext4_lock_group(sb, group);
if (EXT4_MB_GRP_WAS_TRIMMED(e4b.bd_info) &&
@@ -5553,6 +6473,8 @@ ext4_trim_all_free(struct super_block *sb, ext4_group_t group,
EXT4_MB_GRP_SET_TRIMMED(e4b.bd_info);
}
out:
+ if (!IS_ERR_OR_NULL(bh))
+ brelse(bh);
ext4_unlock_group(sb, group);
ext4_mb_unload_allocator(&e4b);
@@ -5613,7 +6535,7 @@ int ext4_trim_fs(struct super_block *sb, struct fstrim_range *range)
for (group = first_group; group <= last_group; group++) {
grp = ext4_get_group_info(sb, group);
/* We only do this if the grp has never been initialized */
- if (unlikely(EXT4_MB_GRP_NEED_INIT(grp))) {
+ if (unlikely(!ext4_mb_frsp_on(sb) && EXT4_MB_GRP_NEED_INIT(grp))) {
ret = ext4_mb_init_group(sb, group, GFP_NOFS);
if (ret)
break;
@@ -5667,16 +6589,25 @@ ext4_mballoc_query_range(
ext4_grpblk_t next;
struct ext4_buddy e4b;
int error;
+ struct buffer_head *bh = NULL;
- error = ext4_mb_load_allocator(sb, group, &e4b, 0);
- if (error)
- return error;
- bitmap = e4b.bd_bitmap;
-
+ if (ext4_mb_frsp_on(sb)) {
+ bh = ext4_read_block_bitmap(sb, group);
+ if (IS_ERR(bh)) {
+ error = PTR_ERR(bh);
+ goto out_unload;
+ }
+ bitmap = bh->b_data;
+ } else {
+ error = ext4_mb_load_allocator(sb, group, &e4b, 0);
+ if (error)
+ return error;
+ bitmap = e4b.bd_bitmap;
+ }
ext4_lock_group(sb, group);
-
- start = (e4b.bd_info->bb_first_free > start) ?
- e4b.bd_info->bb_first_free : start;
+ if (!ext4_mb_frsp_on(sb))
+ start = (e4b.bd_info->bb_first_free > start) ?
+ e4b.bd_info->bb_first_free : start;
if (end >= EXT4_CLUSTERS_PER_GROUP(sb))
end = EXT4_CLUSTERS_PER_GROUP(sb) - 1;
@@ -5685,19 +6616,20 @@ ext4_mballoc_query_range(
if (start > end)
break;
next = mb_find_next_bit(bitmap, end + 1, start);
-
ext4_unlock_group(sb, group);
error = formatter(sb, group, start, next - start, priv);
if (error)
goto out_unload;
ext4_lock_group(sb, group);
-
start = next + 1;
}
ext4_unlock_group(sb, group);
out_unload:
- ext4_mb_unload_allocator(&e4b);
+ if (!IS_ERR_OR_NULL(bh))
+ brelse(bh);
+ if (!ext4_mb_frsp_on(sb))
+ ext4_mb_unload_allocator(&e4b);
return error;
}
diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
index 6b4d17c2935d..32b9ee452de7 100644
--- a/fs/ext4/mballoc.h
+++ b/fs/ext4/mballoc.h
@@ -74,6 +74,20 @@
#define MB_DEFAULT_GROUP_PREALLOC 512
+/*
+ * Struct for tree node in freespace_tree
+ */
+struct ext4_frsp_node {
+ ext4_grpblk_t frsp_offset; /* Start block offset inside
+ * current flexible group
+ */
+ ext4_grpblk_t frsp_len; /*
+ * Length of the free space in
+ * number of clusters
+ */
+ struct rb_node frsp_node;
+ struct rb_node frsp_len_node;
+};
struct ext4_free_data {
/* this links the free block information from sb_info */
struct list_head efd_list;
@@ -121,6 +135,7 @@ struct ext4_free_extent {
ext4_grpblk_t fe_start; /* In cluster units */
ext4_group_t fe_group;
ext4_grpblk_t fe_len; /* In cluster units */
+ struct ext4_frsp_node *fe_node;
};
/*
@@ -141,7 +156,14 @@ struct ext4_locality_group {
spinlock_t lg_prealloc_lock;
};
+struct ext4_tree_extent {
+ ext4_group_t te_flex; /* flex_bg index (tree index) */
+ ext4_grpblk_t te_flex_start; /* block offset w.r.t flex bg */
+ ext4_grpblk_t te_len; /* length */
+};
+
struct ext4_allocation_context {
+ __u32 ac_id;
struct inode *ac_inode;
struct super_block *ac_sb;
@@ -154,8 +176,16 @@ struct ext4_allocation_context {
/* the best found extent */
struct ext4_free_extent ac_b_ex;
- /* copy of the best found extent taken before preallocation efforts */
- struct ext4_free_extent ac_f_ex;
+ /* With freespace trees, we don't use preallocation anymore. */
+ union {
+ /*
+ * copy of the best found extent taken before
+ * preallocation efforts
+ */
+ struct ext4_free_extent ac_f_ex;
+ /* the best found tree extent */
+ struct ext4_tree_extent ac_b_tree_ex;
+ };
__u16 ac_groups_scanned;
__u16 ac_found;
@@ -177,14 +207,31 @@ struct ext4_allocation_context {
#define AC_STATUS_FOUND 2
#define AC_STATUS_BREAK 3
+/*
+ * Freespace tree flags
+ */
+#define EXT4_ALLOCATOR_FRSP_NOLOAD 0x0001 /*
+ * Don't load freespace
+ * tree, if it's not
+ * in memory.
+ */
+
struct ext4_buddy {
- struct page *bd_buddy_page;
- void *bd_buddy;
- struct page *bd_bitmap_page;
- void *bd_bitmap;
+ union {
+ struct {
+ struct page *bd_buddy_page;
+ void *bd_buddy;
+ struct page *bd_bitmap_page;
+ void *bd_bitmap;
+ __u16 bd_blkbits;
+ };
+ struct {
+ struct ext4_frsp_tree *frsp_tree;
+ __u32 frsp_flags;
+ };
+ };
struct ext4_group_info *bd_info;
struct super_block *bd_sb;
- __u16 bd_blkbits;
ext4_group_t bd_group;
};
diff --git a/fs/ext4/resize.c b/fs/ext4/resize.c
index a50b51270ea9..6a0e1fc18e95 100644
--- a/fs/ext4/resize.c
+++ b/fs/ext4/resize.c
@@ -1679,6 +1679,10 @@ int ext4_group_add(struct super_block *sb, struct ext4_new_group_data *input)
if (err)
goto out;
+ err = ext4_mb_add_frsp_trees(sb, input->group + 1);
+ if (err)
+ goto out;
+
flex_gd.count = 1;
flex_gd.groups = input;
flex_gd.bg_flags = &bg_flags;
@@ -2051,6 +2055,10 @@ int ext4_resize_fs(struct super_block *sb, ext4_fsblk_t n_blocks_count)
if (err)
goto out;
+ err = ext4_mb_add_frsp_trees(sb, n_group + 1);
+ if (err)
+ goto out;
+
flex_gd = alloc_flex_gd(flexbg_size);
if (flex_gd == NULL) {
err = -ENOMEM;
diff --git a/fs/ext4/super.c b/fs/ext4/super.c
index 98aa12602b68..2f4b7061365f 100644
--- a/fs/ext4/super.c
+++ b/fs/ext4/super.c
@@ -1521,7 +1521,7 @@ enum {
Opt_dioread_nolock, Opt_dioread_lock,
Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
- Opt_prefetch_block_bitmaps,
+ Opt_prefetch_block_bitmaps, Opt_freespace_tree,
};
static const match_table_t tokens = {
@@ -1608,6 +1608,7 @@ static const match_table_t tokens = {
{Opt_init_itable, "init_itable=%u"},
{Opt_init_itable, "init_itable"},
{Opt_noinit_itable, "noinit_itable"},
+ {Opt_freespace_tree, "freespace_tree"},
{Opt_max_dir_size_kb, "max_dir_size_kb=%u"},
{Opt_test_dummy_encryption, "test_dummy_encryption=%s"},
{Opt_test_dummy_encryption, "test_dummy_encryption"},
@@ -1834,6 +1835,8 @@ static const struct mount_opts {
{Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
{Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
MOPT_SET},
+ {Opt_freespace_tree, EXT4_MOUNT2_FREESPACE_TREE,
+ MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
{Opt_err, 0, 0}
};
@@ -4740,12 +4743,19 @@ static int ext4_fill_super(struct super_block *sb, void *data, int silent)
goto failed_mount4a;
}
+ if (ext4_has_feature_flex_bg(sb))
+ if (!ext4_fill_flex_info(sb)) {
+ ext4_msg(sb, KERN_ERR,
+ "unable to initialize flex_bg meta info!");
+ goto failed_mount5;
+ }
+
ext4_ext_init(sb);
err = ext4_mb_init(sb);
if (err) {
ext4_msg(sb, KERN_ERR, "failed to initialize mballoc (%d)",
err);
- goto failed_mount5;
+ goto failed_mount6;
}
block = ext4_count_free_clusters(sb);
@@ -4775,14 +4785,6 @@ static int ext4_fill_super(struct super_block *sb, void *data, int silent)
goto failed_mount6;
}
- if (ext4_has_feature_flex_bg(sb))
- if (!ext4_fill_flex_info(sb)) {
- ext4_msg(sb, KERN_ERR,
- "unable to initialize "
- "flex_bg meta info!");
- goto failed_mount6;
- }
-
err = ext4_register_li_request(sb, first_not_zeroed);
if (err)
goto failed_mount6;
@@ -4856,7 +4858,14 @@ static int ext4_fill_super(struct super_block *sb, void *data, int silent)
ext4_unregister_li_request(sb);
failed_mount6:
ext4_mb_release(sb);
+ percpu_counter_destroy(&sbi->s_freeclusters_counter);
+ percpu_counter_destroy(&sbi->s_freeinodes_counter);
+ percpu_counter_destroy(&sbi->s_dirs_counter);
+ percpu_counter_destroy(&sbi->s_dirtyclusters_counter);
+ percpu_free_rwsem(&sbi->s_writepages_rwsem);
rcu_read_lock();
+
+failed_mount5:
flex_groups = rcu_dereference(sbi->s_flex_groups);
if (flex_groups) {
for (i = 0; i < sbi->s_flex_groups_allocated; i++)
@@ -4864,12 +4873,6 @@ static int ext4_fill_super(struct super_block *sb, void *data, int silent)
kvfree(flex_groups);
}
rcu_read_unlock();
- percpu_counter_destroy(&sbi->s_freeclusters_counter);
- percpu_counter_destroy(&sbi->s_freeinodes_counter);
- percpu_counter_destroy(&sbi->s_dirs_counter);
- percpu_counter_destroy(&sbi->s_dirtyclusters_counter);
- percpu_free_rwsem(&sbi->s_writepages_rwsem);
-failed_mount5:
ext4_ext_release(sb);
ext4_release_system_zone(sb);
failed_mount4a:
--
2.28.0.220.ged08abb693-goog
