[PATCH 0/3] Create circular buffer list for every page instead of linear list.

[PATCH 0/3] Create circular buffer list for every page instead of linear list.

[Sean Fu]

1.Create circular buffer list in alloc_page_buffers.
Remove unnecessary traversal in link_dev_buffers to create circular buffer list.
Make nobh_write_begin and nobh_write_end to support circular buffer list.

2.fs/ntfs: Make ntfs to support circular buffer list.

3.md: bitmap: Support circular buffer list.
Modify write_page free_buffers and read_page to support circular buffer list.

Sean Fu (3):
  fs: buffer: Create circular buffer list for pages.
  fs/ntfs: Make ntfs to support circular buffer list.
  md: bitmap: Support circular buffer list.

 drivers/md/md-bitmap.c | 36 +++++++++++++++++++-----------------
 fs/buffer.c            | 48 +++++++++++++++++++++---------------------------
 fs/ntfs/aops.c         |  6 ++----
 fs/ntfs/mft.c          |  4 ----
 4 files changed, 42 insertions(+), 52 deletions(-)

-- 
2.6.2

[PATCH 1/3] fs: buffer: Create circular buffer list for pages.

[Sean Fu]

Make alloc_page_buffers to create circular buffer list instead linear
list.
Remove unnecessary traversal in link_dev_buffers to create circular
buffer list.
Make nobh_write_begin and nobh_write_end to support circular buffer list
traversal.

Signed-off-by: Sean Fu <fxinrong@gmail.com>
---
 fs/buffer.c | 48 +++++++++++++++++++++---------------------------
 1 file changed, 21 insertions(+), 27 deletions(-)

diff --git a/fs/buffer.c b/fs/buffer.c
index 0736a6a..7e62c75 100644
--- a/fs/buffer.c
+++ b/fs/buffer.c
@@ -842,29 +842,36 @@ int remove_inode_buffers(struct inode *inode)
 struct buffer_head *alloc_page_buffers(struct page *page, unsigned long size,
 		bool retry)
 {
-	struct buffer_head *bh, *head;
+	struct buffer_head *bh, *head, *tail;
 	gfp_t gfp = GFP_NOFS;
 	long offset;
 
 	if (retry)
 		gfp |= __GFP_NOFAIL;
 
-	head = NULL;
+	head = tail = NULL;
 	offset = PAGE_SIZE;
 	while ((offset -= size) >= 0) {
 		bh = alloc_buffer_head(gfp);
 		if (!bh)
 			goto no_grow;
 
-		bh->b_this_page = head;
+		if (unlikely(!head))
+			tail = bh;
+		else
+			bh->b_this_page = head;
+
 		bh->b_blocknr = -1;
 		head = bh;
-
 		bh->b_size = size;
 
 		/* Link the buffer to its page */
 		set_bh_page(bh, page, offset);
 	}
+
+	if (tail)
+		tail->b_this_page = head;
+
 	return head;
 /*
  * In case anything failed, we just free everything we got.
@@ -882,20 +889,6 @@ struct buffer_head *alloc_page_buffers(struct page *page, unsigned long size,
 }
 EXPORT_SYMBOL_GPL(alloc_page_buffers);
 
-static inline void
-link_dev_buffers(struct page *page, struct buffer_head *head)
-{
-	struct buffer_head *bh, *tail;
-
-	bh = head;
-	do {
-		tail = bh;
-		bh = bh->b_this_page;
-	} while (bh);
-	tail->b_this_page = head;
-	attach_page_buffers(page, head);
-}
-
 static sector_t blkdev_max_block(struct block_device *bdev, unsigned int size)
 {
 	sector_t retval = ~((sector_t)0);
@@ -993,7 +986,7 @@ grow_dev_page(struct block_device *bdev, sector_t block,
 	 * run under the page lock.
 	 */
 	spin_lock(&inode->i_mapping->private_lock);
-	link_dev_buffers(page, bh);
+	attach_page_buffers(page, bh);
 	end_block = init_page_buffers(page, bdev, (sector_t)index << sizebits,
 			size);
 	spin_unlock(&inode->i_mapping->private_lock);
@@ -1533,16 +1526,14 @@ EXPORT_SYMBOL(block_invalidatepage);
 void create_empty_buffers(struct page *page,
 			unsigned long blocksize, unsigned long b_state)
 {
-	struct buffer_head *bh, *head, *tail;
+	struct buffer_head *bh, *head;
 
 	head = alloc_page_buffers(page, blocksize, true);
 	bh = head;
 	do {
 		bh->b_state |= b_state;
-		tail = bh;
 		bh = bh->b_this_page;
-	} while (bh);
-	tail->b_this_page = head;
+	} while (bh != head);
 
 	spin_lock(&page->mapping->private_lock);
 	if (PageUptodate(page) || PageDirty(page)) {
@@ -2655,11 +2646,14 @@ int nobh_write_begin(struct address_space *mapping,
 		 * any VM or truncate activity.  Hence we don't need to care
 		 * for the buffer_head refcounts.
 		 */
-		for (bh = head; bh; bh = bh->b_this_page) {
+		bh = head;
+		do {
 			wait_on_buffer(bh);
 			if (!buffer_uptodate(bh))
 				ret = -EIO;
-		}
+			bh = bh->b_this_page;
+		} while (bh != head);
+
 		if (ret)
 			goto failed;
 	}
@@ -2717,11 +2711,11 @@ int nobh_write_end(struct file *file, struct address_space *mapping,
 	unlock_page(page);
 	put_page(page);
 
-	while (head) {
+	do {
 		bh = head;
 		head = head->b_this_page;
 		free_buffer_head(bh);
-	}
+	} while (head != fsdata);
 
 	return copied;
 }
-- 
2.6.2

[PATCH 2/3] fs/ntfs: Make ntfs to support circular buffer list.

[Sean Fu]

Modify mark_ntfs_record_dirty to support circular buffer list.
alloc_page_buffers created circular buffer list. So the circular list
linking in ntfs_sync_mft_mirror is unnecessary.

Signed-off-by: Sean Fu <fxinrong@gmail.com>
---
 fs/ntfs/aops.c | 6 ++----
 fs/ntfs/mft.c  | 4 ----
 2 files changed, 2 insertions(+), 8 deletions(-)

diff --git a/fs/ntfs/aops.c b/fs/ntfs/aops.c
index 3a2e509..4e69577 100644
--- a/fs/ntfs/aops.c
+++ b/fs/ntfs/aops.c
@@ -1746,10 +1746,8 @@ void mark_ntfs_record_dirty(struct page *page, const unsigned int ofs) {
 
 			do {
 				set_buffer_uptodate(bh);
-				tail = bh;
 				bh = bh->b_this_page;
-			} while (bh);
-			tail->b_this_page = head;
+			} while (bh != head);
 			attach_page_buffers(page, head);
 		} else
 			buffers_to_free = bh;
@@ -1771,7 +1769,7 @@ void mark_ntfs_record_dirty(struct page *page, const unsigned int ofs) {
 			bh = buffers_to_free->b_this_page;
 			free_buffer_head(buffers_to_free);
 			buffers_to_free = bh;
-		} while (buffers_to_free);
+		} while (buffers_to_free != head);
 	}
 }
 
diff --git a/fs/ntfs/mft.c b/fs/ntfs/mft.c
index ee8392a..26ba4f6 100644
--- a/fs/ntfs/mft.c
+++ b/fs/ntfs/mft.c
@@ -505,15 +505,11 @@ int ntfs_sync_mft_mirror(ntfs_volume *vol, const unsigned long mft_no,
 	memcpy(kmirr, m, vol->mft_record_size);
 	/* Create uptodate buffers if not present. */
 	if (unlikely(!page_has_buffers(page))) {
-		struct buffer_head *tail;
-
 		bh = head = alloc_page_buffers(page, blocksize, true);
 		do {
 			set_buffer_uptodate(bh);
-			tail = bh;
 			bh = bh->b_this_page;
 		} while (bh);
-		tail->b_this_page = head;
 		attach_page_buffers(page, head);
 	}
 	bh = head = page_buffers(page);
-- 
2.6.2

[PATCH 3/3] md: bitmap: Support circular buffer list.

[Sean Fu]

Modify write_page free_buffers and read_page to support circular buffer
list.

Signed-off-by: Sean Fu <fxinrong@gmail.com>
---
 drivers/md/md-bitmap.c | 36 +++++++++++++++++++-----------------
 1 file changed, 19 insertions(+), 17 deletions(-)

diff --git a/drivers/md/md-bitmap.c b/drivers/md/md-bitmap.c
index 239c7bb..b8412c2 100644
--- a/drivers/md/md-bitmap.c
+++ b/drivers/md/md-bitmap.c
@@ -286,7 +286,7 @@ static void bitmap_file_kick(struct bitmap *bitmap);
  */
 static void write_page(struct bitmap *bitmap, struct page *page, int wait)
 {
-	struct buffer_head *bh;
+	struct buffer_head *bh, *head;
 
 	if (bitmap->storage.file == NULL) {
 		switch (write_sb_page(bitmap, page, wait)) {
@@ -295,15 +295,16 @@ static void write_page(struct bitmap *bitmap, struct page *page, int wait)
 		}
 	} else {
 
-		bh = page_buffers(page);
+		bh = head = page_buffers(page);
 
-		while (bh && bh->b_blocknr) {
-			atomic_inc(&bitmap->pending_writes);
-			set_buffer_locked(bh);
-			set_buffer_mapped(bh);
-			submit_bh(REQ_OP_WRITE, REQ_SYNC, bh);
-			bh = bh->b_this_page;
-		}
+		do {
+			if (bh && bh->b_blocknr) {
+				atomic_inc(&bitmap->pending_writes);
+				set_buffer_locked(bh);
+				set_buffer_mapped(bh);
+				submit_bh(REQ_OP_WRITE, REQ_SYNC, bh);
+			}
+		} while ((bh = bh->b_this_page) != head);
 
 		if (wait)
 			wait_event(bitmap->write_wait,
@@ -333,17 +334,18 @@ __clear_page_buffers(struct page *page)
 }
 static void free_buffers(struct page *page)
 {
-	struct buffer_head *bh;
+	struct buffer_head *bh, *head;
 
 	if (!PagePrivate(page))
 		return;
 
-	bh = page_buffers(page);
-	while (bh) {
+	bh = head = page_buffers(page);
+	do {
 		struct buffer_head *next = bh->b_this_page;
 		free_buffer_head(bh);
 		bh = next;
-	}
+	} while (bh != head);
+
 	__clear_page_buffers(page);
 	put_page(page);
 }
@@ -362,20 +364,20 @@ static int read_page(struct file *file, unsigned long index,
 {
 	int ret = 0;
 	struct inode *inode = file_inode(file);
-	struct buffer_head *bh;
+	struct buffer_head *bh, *head;
 	sector_t block;
 
 	pr_debug("read bitmap file (%dB @ %llu)\n", (int)PAGE_SIZE,
 		 (unsigned long long)index << PAGE_SHIFT);
 
-	bh = alloc_page_buffers(page, 1<<inode->i_blkbits, false);
+	bh = head = alloc_page_buffers(page, 1<<inode->i_blkbits, false);
 	if (!bh) {
 		ret = -ENOMEM;
 		goto out;
 	}
 	attach_page_buffers(page, bh);
 	block = index << (PAGE_SHIFT - inode->i_blkbits);
-	while (bh) {
+	do {
 		if (count == 0)
 			bh->b_blocknr = 0;
 		else {
@@ -400,7 +402,7 @@ static int read_page(struct file *file, unsigned long index,
 		}
 		block++;
 		bh = bh->b_this_page;
-	}
+	} while (bh != head);
 	page->index = index;
 
 	wait_event(bitmap->write_wait,
-- 
2.6.2

Re: [PATCH 3/3] md: bitmap: Support circular buffer list.

[Sean Fu]

On Tue, Jan 02, 2018 at 02:54:49PM +0800, Sean Fu wrote:
> Modify write_page free_buffers and read_page to support circular buffer
> list.
> 
> Signed-off-by: Sean Fu <fxinrong@gmail.com>
> ---
>  drivers/md/md-bitmap.c | 36 +++++++++++++++++++-----------------
>  1 file changed, 19 insertions(+), 17 deletions(-)
> 
> diff --git a/drivers/md/md-bitmap.c b/drivers/md/md-bitmap.c
> index 239c7bb..b8412c2 100644
> --- a/drivers/md/md-bitmap.c
> +++ b/drivers/md/md-bitmap.c
> @@ -286,7 +286,7 @@ static void bitmap_file_kick(struct bitmap *bitmap);
>   */
>  static void write_page(struct bitmap *bitmap, struct page *page, int wait)
>  {
> -	struct buffer_head *bh;
> +	struct buffer_head *bh, *head;
>  
>  	if (bitmap->storage.file == NULL) {
>  		switch (write_sb_page(bitmap, page, wait)) {
> @@ -295,15 +295,16 @@ static void write_page(struct bitmap *bitmap, struct page *page, int wait)
>  		}
>  	} else {
>  
> -		bh = page_buffers(page);
> +		bh = head = page_buffers(page);
>  
> -		while (bh && bh->b_blocknr) {
> -			atomic_inc(&bitmap->pending_writes);
> -			set_buffer_locked(bh);
> -			set_buffer_mapped(bh);
> -			submit_bh(REQ_OP_WRITE, REQ_SYNC, bh);
> -			bh = bh->b_this_page;
> -		}
> +		do {
> +			if (bh && bh->b_blocknr) {
> +				atomic_inc(&bitmap->pending_writes);
> +				set_buffer_locked(bh);
> +				set_buffer_mapped(bh);
> +				submit_bh(REQ_OP_WRITE, REQ_SYNC, bh);
> +			}
> +		} while ((bh = bh->b_this_page) != head);
>  
>  		if (wait)
>  			wait_event(bitmap->write_wait,
> @@ -333,17 +334,18 @@ __clear_page_buffers(struct page *page)
>  }
>  static void free_buffers(struct page *page)
>  {
> -	struct buffer_head *bh;
> +	struct buffer_head *bh, *head;
>  
>  	if (!PagePrivate(page))
>  		return;
>  
> -	bh = page_buffers(page);
> -	while (bh) {
> +	bh = head = page_buffers(page);
> +	do {
>  		struct buffer_head *next = bh->b_this_page;
>  		free_buffer_head(bh);
>  		bh = next;
> -	}
> +	} while (bh != head);
> +
>  	__clear_page_buffers(page);
>  	put_page(page);
>  }
> @@ -362,20 +364,20 @@ static int read_page(struct file *file, unsigned long index,
>  {
>  	int ret = 0;
>  	struct inode *inode = file_inode(file);
> -	struct buffer_head *bh;
> +	struct buffer_head *bh, *head;
>  	sector_t block;
>  
>  	pr_debug("read bitmap file (%dB @ %llu)\n", (int)PAGE_SIZE,
>  		 (unsigned long long)index << PAGE_SHIFT);
>  
> -	bh = alloc_page_buffers(page, 1<<inode->i_blkbits, false);
> +	bh = head = alloc_page_buffers(page, 1<<inode->i_blkbits, false);
>  	if (!bh) {
>  		ret = -ENOMEM;
>  		goto out;
>  	}
>  	attach_page_buffers(page, bh);
>  	block = index << (PAGE_SHIFT - inode->i_blkbits);
> -	while (bh) {
> +	do {
>  		if (count == 0)
>  			bh->b_blocknr = 0;
>  		else {
> @@ -400,7 +402,7 @@ static int read_page(struct file *file, unsigned long index,
>  		}
>  		block++;
>  		bh = bh->b_this_page;
> -	}
> +	} while (bh != head);
>  	page->index = index;
>  
>  	wait_event(bitmap->write_wait,
> -- 
> 2.6.2
>
Before
sean@linux-zmni:~/sda5/source/linus_repo/linux> size fs/buffer.o
   text	   data	    bss	    dec	    hex	filename
  33693	   1466	     16	  35175	   8967	fs/buffer.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size drivers/md/md-bitmap.o
   text	   data	    bss	    dec	    hex	filename
  28149	   2168	      0	  30317	   766d	drivers/md/md-bitmap.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size fs/ntfs/mft.o 
   text	   data	    bss	    dec	    hex	filename
   2133	     36	      0	   2169	    879	fs/ntfs/mft.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size fs/ntfs/aops.o
   text	   data	    bss	    dec	    hex	filename
   6125	    168	      0	   6293	   1895	fs/ntfs/aops.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size vmlinux
   text	   data	    bss	    dec	    hex	filename
11480260	5730762	1646084	18857106	11fbc92	vmlinux
sean@linux-zmni:~/sda5/source/linus_repo/linux> size ./arch/x86/boot/bzImage
size: ./arch/x86/boot/bzImage: Warning: Ignoring section flag IMAGE_SCN_MEM_NOT_PAGED in section .bss
   text	   data	    bss	    dec	    hex	filename
6571744	      0	16975648	23547392	1674e00	./arch/x86/boot/bzImage


After
sean@linux-zmni:~/sda5/source/linus_repo/linux> size fs/buffer.o 
   text	   data	    bss	    dec	    hex	filename
  33687	   1466	     16	  35169	   8961	fs/buffer.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size drivers/md/md-bitmap.o 
   text	   data	    bss	    dec	    hex	filename
  28221	   2168	      0	  30389	   76b5	drivers/md/md-bitmap.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size fs/ntfs/mft.o 
   text	   data	    bss	    dec	    hex	filename
   2133	     36	      0	   2169	    879	fs/ntfs/mft.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size fs/ntfs/aops.o
   text	   data	    bss	    dec	    hex	filename
   6125	    168	      0	   6293	   1895	fs/ntfs/aops.o
sean@linux-zmni:~/sda5/source/linus_repo/linux> size vmlinux
   text	   data	    bss	    dec	    hex	filename
11480270	5730762	1646084	18857116	11fbc9c	vmlinux
sean@linux-zmni:~/sda5/source/linus_repo/linux> size ./arch/x86/boot/bzImage
size: ./arch/x86/boot/bzImage: Warning: Ignoring section flag IMAGE_SCN_MEM_NOT_PAGED in section .bss
   text	   data	    bss	    dec	    hex	filename
6571488	      0	16975904	23547392	1674e00	./arch/x86/boot/bzImage

Only patch #3 increases the text section size of drivers/md/md-bitmap.o
The actual text section increment should be several bytes. Duo to compiler align-functions option, the total increment is increased to 72 bytes.

Why is circular list traversal more complex than linear list traversal in this situation?  
How to optimize it?