[PATCH] f2fs: add a rb tree for discard command

[Yunlei He <heyunlei@huawei.com>]

This patch add a rb tree for discard command.

Signed-off-by: Yunlei He <heyunlei@huawei.com>
---
 fs/f2fs/f2fs.h    |  2 ++
 fs/f2fs/segment.c | 35 ++++++++++++++++++++++++++++++-----
 2 files changed, 32 insertions(+), 5 deletions(-)

diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 5a2b8cd..5bc80dc 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -197,6 +197,7 @@ enum {
 
 struct discard_cmd {
 	struct list_head list;		/* command list */
+	struct rb_node rb_node;         /* rb node located in rb-tree */
 	struct completion wait;		/* compleation */
 	struct block_device *bdev;	/* bdev */
 	block_t lstart;			/* logical start address */
@@ -210,6 +211,7 @@ struct discard_cmd_control {
 	struct task_struct *f2fs_issue_discard;	/* discard thread */
 	struct list_head discard_entry_list;	/* 4KB discard entry list */
 	int nr_discards;			/* # of discards in the list */
+	struct rb_root root;            /* root of extent info rb-tree */
 	struct list_head discard_pend_list;	/* store pending entries */
 	struct list_head discard_wait_list;	/* store on-flushing entries */
 	wait_queue_head_t discard_wait_queue;	/* waiting queue for wake-up */
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index eedbed6..d96f11a 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -678,7 +678,9 @@ static void __add_discard_cmd(struct f2fs_sb_info *sbi,
 {
 	struct discard_cmd_control *dcc = SM_I(sbi)->dcc_info;
 	struct list_head *pend_list = &(dcc->discard_pend_list);
-	struct discard_cmd *dc;
+	struct discard_cmd *dc, *tmp;
+	struct rb_node **p = &dcc->root.rb_node;
+	struct rb_node *parent = NULL;
 
 	dc = f2fs_kmem_cache_alloc(discard_cmd_slab, GFP_NOFS);
 	INIT_LIST_HEAD(&dc->list);
@@ -691,6 +693,20 @@ static void __add_discard_cmd(struct f2fs_sb_info *sbi,
 	init_completion(&dc->wait);
 
 	mutex_lock(&dcc->cmd_lock);
+	while (*p) {
+		parent = *p;
+		tmp = rb_entry_safe(parent, struct discard_cmd, rb_node);
+
+		if (dc->lstart + dc->len <= tmp->lstart)
+			p = &(*p)->rb_left;
+		else if (dc->lstart >= tmp->lstart + tmp->len)
+			p = &(*p)->rb_right;
+		else
+			f2fs_bug_on(sbi, 1);
+	}
+
+	rb_link_node(&dc->rb_node, parent, p);
+	rb_insert_color(&dc->rb_node, &dcc->root);
 	list_add_tail(&dc->list, pend_list);
 	mutex_unlock(&dcc->cmd_lock);
 
@@ -709,6 +725,7 @@ static void __remove_discard_cmd(struct f2fs_sb_info *sbi, struct discard_cmd *d
 		f2fs_msg(sbi->sb, KERN_INFO,
 				"Issue discard failed, ret: %d", dc->error);
 	list_del(&dc->list);
+	rb_erase(&dc->rb_node, &(SM_I(sbi)->dcc_info->root));
 	kmem_cache_free(discard_cmd_slab, dc);
 	atomic_dec(&SM_I(sbi)->dcc_info->discard_cmd_cnt);
 }
@@ -794,16 +811,23 @@ static void __punch_discard_cmd(struct f2fs_sb_info *sbi,
 void f2fs_wait_discard_bio(struct f2fs_sb_info *sbi, block_t blkaddr)
 {
 	struct discard_cmd_control *dcc = SM_I(sbi)->dcc_info;
-	struct list_head *pend_list = &(dcc->discard_pend_list);
-	struct discard_cmd *dc, *tmp;
+	struct discard_cmd *dc;
+	struct rb_node *node = dcc->root.rb_node;
 
 	mutex_lock(&dcc->cmd_lock);
 
-	list_for_each_entry_safe(dc, tmp, pend_list, list) {
-		if (dc->lstart <= blkaddr && blkaddr < dc->lstart + dc->len) {
+	while (node) {
+		dc = rb_entry_safe(node, struct discard_cmd, rb_node);
+
+		if (blkaddr < dc->lstart) {
+			node = node->rb_left;
+		} else if (blkaddr >= dc->lstart + dc->len) {
+			node = node->rb_right;
+		} else {
 			if (dc->state == D_SUBMIT)
 				wait_for_completion_io(&dc->wait);
 			__punch_discard_cmd(sbi, dc, blkaddr);
+			break;
 		}
 	}
 
@@ -1165,6 +1189,7 @@ static int create_discard_cmd_control(struct f2fs_sb_info *sbi)
 	INIT_LIST_HEAD(&dcc->discard_entry_list);
 	INIT_LIST_HEAD(&dcc->discard_pend_list);
 	INIT_LIST_HEAD(&dcc->discard_wait_list);
+	dcc->root = RB_ROOT;
 	mutex_init(&dcc->cmd_lock);
 	atomic_set(&dcc->issued_discard, 0);
 	atomic_set(&dcc->issing_discard, 0);
-- 
2.10.1


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot