[Devel] [PATCH vz7] fuse: optimize writepages search

Konstantin Khorenko khorenko at virtuozzo.com
Fri Apr 7 03:26:06 PDT 2017


Kirill, please review the patch.

--
Best regards,

Konstantin Khorenko,
Virtuozzo Linux Kernel Team

On 04/07/2017 06:35 AM, Maxim Patlasov wrote:
> The patch re-works fi->writepages replacing list with rb-tree.
> This improves performance because kernel fuse iterates through
> fi->writepages for each writeback page and typical number of
> entries is about 800 (for 100MB of fuse writeback).
>
> Before patch:
>
> # dd if=/dev/zero of=/pcs2860/fil bs=1M count=10240
> 10240+0 records in
> 10240+0 records out
> 10737418240 bytes (11 GB) copied, 41.3473 s, 260 MB/s
>
> # vmstat 10
>  2  1      0 57445400  40416 6323676    0    0    33 374743 8633 19210  1  8 88  3  0
>
> # perf top
>   29.86%  [kernel]               [k] _raw_spin_lock
>   26.62%  [fuse]                 [k] fuse_page_is_writeback
>
> After patch:
>
> # dd if=/dev/zero of=/pcs2860/fil bs=1M count=10240
> 10240+0 records in
> 10240+0 records out
> 10737418240 bytes (11 GB) copied, 21.4954 s, 500 MB/s
>
> # vmstat 10
>  2  9      0 53676040  31744 10265984    0    0    64 854790 10956 48387  1  6 88  6  0
>
> # perf top
>   23.55%  [kernel]             [k] copy_user_enhanced_fast_string
>    9.87%  [kernel]             [k] __memcpy
>    3.10%  [kernel]             [k] _raw_spin_lock
>
> https://jira.sw.ru/browse/PSBM-59254
>
> Signed-off-by: Maxim Patlasov <mpatlasov at virtuozzo.com>
> ---
>  fs/fuse/file.c   |   83 ++++++++++++++++++++++++++++++++++++++++++++++--------
>  fs/fuse/fuse_i.h |    4 +--
>  fs/fuse/inode.c  |    2 +
>  3 files changed, 73 insertions(+), 16 deletions(-)
>
> diff --git a/fs/fuse/file.c b/fs/fuse/file.c
> index 41ed6f0..eab5030 100644
> --- a/fs/fuse/file.c
> +++ b/fs/fuse/file.c
> @@ -435,7 +435,7 @@ static int fuse_release(struct inode *inode, struct file *file)
>  		 * enqueued on this file and it is not going to get new one: it is closing.
>  		 */
>  		if (!ff->fc->close_wait)
> -			wait_event(fi->page_waitq, list_empty_careful(&fi->writepages));
> +			wait_event(fi->page_waitq, RB_EMPTY_ROOT(&fi->writepages));
>  		else
>  			wait_event(fi->page_waitq, atomic_read(&ff->count) == 1);
>
> @@ -501,17 +501,30 @@ static bool fuse_range_is_writeback(struct inode *inode, pgoff_t idx_from,
>  {
>  	struct fuse_conn *fc = get_fuse_conn(inode);
>  	struct fuse_inode *fi = get_fuse_inode(inode);
> -	struct fuse_req *req;
>  	bool found = false;
> +	struct rb_node *n;
>
>  	spin_lock(&fc->lock);
> -	list_for_each_entry(req, &fi->writepages, writepages_entry) {
> +
> +	n = fi->writepages.rb_node;
> +	if (!n) {
> +		spin_unlock(&fc->lock);
> +		return false;
> +	}
> +
> +	while (n) {
> +		struct fuse_req *req;
>  		pgoff_t curr_index;
>
> +		req = rb_entry(n, struct fuse_req, writepages_entry);
>  		BUG_ON(req->inode != inode);
>  		curr_index = req->misc.write.in.offset >> PAGE_CACHE_SHIFT;
> -		if (!(idx_from >= curr_index + req->num_pages ||
> -		      idx_to < curr_index)) {
> +
> +		if (idx_from >= curr_index + req->num_pages)
> +			n = n->rb_right;
> +		else if (idx_to < curr_index)
> +			n = n->rb_left;
> +		else {
>  			found = true;
>  			break;
>  		}
> @@ -531,17 +544,31 @@ static bool fuse_page_is_writeback(struct inode *inode, pgoff_t index)
>  {
>  	struct fuse_conn *fc = get_fuse_conn(inode);
>  	struct fuse_inode *fi = get_fuse_inode(inode);
> -	struct fuse_req *req;
>  	bool found = false;
> +	struct rb_node *n;
>
>  	spin_lock(&fc->lock);
> -	list_for_each_entry(req, &fi->writepages, writepages_entry) {
> +
> +	n = fi->writepages.rb_node;
> +	if (!n) {
> +		spin_unlock(&fc->lock);
> +		return false;
> +	}
> +
> +
> +	while (n) {
> +		struct fuse_req *req;
>  		pgoff_t curr_index;
>
> +		req = rb_entry(n, struct fuse_req, writepages_entry);
>  		BUG_ON(req->inode != inode);
>  		curr_index = req->misc.write.in.offset >> PAGE_CACHE_SHIFT;
> -		if (curr_index <= index &&
> -		    index < curr_index + req->num_pages) {
> +
> +		if (index >= curr_index + req->num_pages)
> +			n = n->rb_right;
> +		else if (index < curr_index)
> +			n = n->rb_left;
> +		else {
>  			found = true;
>  			break;
>  		}
> @@ -1868,7 +1895,7 @@ static void fuse_writepage_finish(struct fuse_conn *fc, struct fuse_req *req)
>  	struct backing_dev_info *bdi = inode->i_mapping->backing_dev_info;
>  	int i;
>
> -	list_del(&req->writepages_entry);
> +	rb_erase(&req->writepages_entry, &fi->writepages);
>  	if (fc->writeback_cache || fc->close_wait)
>  		__fuse_file_put(req->ff);
>  	for (i = 0; i < req->num_pages; i++) {
> @@ -1964,6 +1991,36 @@ static struct fuse_file *fuse_write_file(struct fuse_conn *fc,
>  	return ff;
>  }
>
> +static int tree_insert(struct rb_root *root, struct fuse_req *ins_req)
> +{
> +	unsigned i = ins_req->num_pages - 1;
> +	pgoff_t idx_from = ins_req->pages[0]->index;
> +	pgoff_t idx_to   = ins_req->pages[i]->index;
> +	struct rb_node **p = &root->rb_node;
> +	struct rb_node  *parent = NULL;
> +
> +	while (*p) {
> +		struct fuse_req *req;
> +		pgoff_t curr_index;
> +
> +		parent = *p;
> +		req = rb_entry(parent, struct fuse_req, writepages_entry);
> +		BUG_ON(req->inode != ins_req->inode);
> +		curr_index = req->misc.write.in.offset >> PAGE_CACHE_SHIFT;
> +
> +		if (idx_from >= curr_index + req->num_pages)
> +			p = &(*p)->rb_right;
> +		else if (idx_to < curr_index)
> +			p = &(*p)->rb_left;
> +		else
> +			BUG();
> +	}
> +
> +	rb_link_node(&ins_req->writepages_entry, parent, p);
> +	rb_insert_color(&ins_req->writepages_entry, root);
> +	return 0;
> +}
> +
>  static int fuse_writepage_locked(struct page *page,
>  				 struct writeback_control *wbc,
>  				 struct fuse_file **ff_pp)
> @@ -2034,7 +2091,7 @@ static int fuse_writepage_locked(struct page *page,
>  	inc_zone_page_state(tmp_page, NR_WRITEBACK_TEMP);
>
>  	spin_lock(&fc->lock);
> -	list_add(&req->writepages_entry, &fi->writepages);
> +	tree_insert(&fi->writepages, req);
>  	list_add_tail(&req->list, &fi->queued_writes);
>  	fuse_flush_writepages(inode);
>  	spin_unlock(&fc->lock);
> @@ -2110,7 +2167,7 @@ static int fuse_send_writepages(struct fuse_fill_data *data)
>  	req->misc.write.in.offset = page_offset(req->pages[0]);
>
>  	spin_lock(&fc->lock);
> -	list_add(&req->writepages_entry, &fi->writepages);
> +	tree_insert(&fi->writepages, req);
>  	spin_unlock(&fc->lock);
>
>  	for (i = 0; i < req->num_pages; i++) {
> @@ -2143,7 +2200,7 @@ static int fuse_send_writepages(struct fuse_fill_data *data)
>  		}
>
>  		spin_lock(&fc->lock);
> -		list_del(&req->writepages_entry);
> +		rb_erase(&req->writepages_entry, &fi->writepages);
>  		wake_up(&fi->page_waitq);
>  		spin_unlock(&fc->lock);
>
> diff --git a/fs/fuse/fuse_i.h b/fs/fuse/fuse_i.h
> index fefa8ff..4601571 100644
> --- a/fs/fuse/fuse_i.h
> +++ b/fs/fuse/fuse_i.h
> @@ -117,7 +117,7 @@ struct fuse_inode {
>  	wait_queue_head_t page_waitq;
>
>  	/** List of writepage requestst (pending or sent) */
> -	struct list_head writepages;
> +	struct rb_root writepages;
>
>  	/** Miscellaneous bits describing inode state */
>  	unsigned long state;
> @@ -404,7 +404,7 @@ struct fuse_req {
>  	struct fuse_io_priv *io;
>
>  	/** Link on fi->writepages */
> -	struct list_head writepages_entry;
> +	struct rb_node writepages_entry;
>
>  	/** Request completion callback */
>  	void (*end)(struct fuse_conn *, struct fuse_req *);
> diff --git a/fs/fuse/inode.c b/fs/fuse/inode.c
> index ddd858c..0da2623 100644
> --- a/fs/fuse/inode.c
> +++ b/fs/fuse/inode.c
> @@ -101,7 +101,7 @@ static struct inode *fuse_alloc_inode(struct super_block *sb)
>  	INIT_LIST_HEAD(&fi->write_files);
>  	INIT_LIST_HEAD(&fi->rw_files);
>  	INIT_LIST_HEAD(&fi->queued_writes);
> -	INIT_LIST_HEAD(&fi->writepages);
> +	fi->writepages = RB_ROOT;
>  	init_waitqueue_head(&fi->page_waitq);
>  	fi->forget = fuse_alloc_forget();
>  	if (!fi->forget) {
>
> .
>


More information about the Devel mailing list