[PATCH 1/3] f2fs: add fast path for find_next_{zero}bit

[Jaegeuk Kim]

This patch adds checking the first two bits when searching zero or one bits to
avoid costly find_next_{zero}bit operations.

Signed-off-by: Jaegeuk Kim <jaegeuk@xxxxxxxxxx>
---
 fs/f2fs/dir.c     | 10 +++++-----
 fs/f2fs/f2fs.h    | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 fs/f2fs/gc.c      |  3 ++-
 fs/f2fs/inline.c  |  2 +-
 fs/f2fs/segment.c | 14 ++++++++------
 fs/f2fs/segment.h | 11 ++++++-----
 6 files changed, 70 insertions(+), 18 deletions(-)

diff --git a/fs/f2fs/dir.c b/fs/f2fs/dir.c
index 5f5678e..f3a4fce 100644
--- a/fs/f2fs/dir.c
+++ b/fs/f2fs/dir.c
@@ -480,11 +480,11 @@ int room_for_filename(const void *bitmap, int slots, int max_slots)
 	int bit_start = 0;
 	int zero_start, zero_end;
 next:
-	zero_start = find_next_zero_bit_le(bitmap, max_slots, bit_start);
+	zero_start = f2fs_find_next_zero_bit_le(bitmap, max_slots, bit_start);
 	if (zero_start >= max_slots)
 		return max_slots;
 
-	zero_end = find_next_bit_le(bitmap, max_slots, zero_start);
+	zero_end = f2fs_find_next_bit_le(bitmap, max_slots, zero_start);
 	if (zero_end - zero_start >= slots)
 		return zero_start;
 
@@ -724,7 +724,7 @@ void f2fs_delete_entry(struct f2fs_dir_entry *dentry, struct page *page,
 		clear_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap);
 
 	/* Let's check and deallocate this dentry page */
-	bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap,
+	bit_pos = f2fs_find_next_bit_le(&dentry_blk->dentry_bitmap,
 			NR_DENTRY_IN_BLOCK,
 			0);
 	kunmap(page); /* kunmap - pair of f2fs_find_entry */
@@ -772,7 +772,7 @@ bool f2fs_empty_dir(struct inode *dir)
 			bit_pos = 2;
 		else
 			bit_pos = 0;
-		bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap,
+		bit_pos = f2fs_find_next_bit_le(&dentry_blk->dentry_bitmap,
 						NR_DENTRY_IN_BLOCK,
 						bit_pos);
 		kunmap_atomic(dentry_blk);
@@ -796,7 +796,7 @@ bool f2fs_fill_dentries(struct dir_context *ctx, struct f2fs_dentry_ptr *d,
 	bit_pos = ((unsigned long)ctx->pos % d->max);
 
 	while (bit_pos < d->max) {
-		bit_pos = find_next_bit_le(d->bitmap, d->max, bit_pos);
+		bit_pos = f2fs_find_next_bit_le(d->bitmap, d->max, bit_pos);
 		if (bit_pos >= d->max)
 			break;
 
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index e6d057c..168f939 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -1912,6 +1912,54 @@ static inline void *f2fs_kvzalloc(size_t size, gfp_t flags)
 	return ret;
 }
 
+static inline unsigned long f2fs_find_next_zero_bit_le(const void *addr,
+		unsigned long size, unsigned long offset)
+{
+	if (!test_bit_le(offset, addr))
+		return offset;
+	if (offset + 1 >= size)
+		return size;
+	if (!test_bit_le(offset + 1, addr))
+		return offset + 1;
+	return find_next_zero_bit_le(addr, size, offset + 2);
+}
+
+static inline unsigned long f2fs_find_next_bit_le(const void *addr,
+		unsigned long size, unsigned long offset)
+{
+	if (test_bit_le(offset, addr))
+		return offset;
+	if (offset + 1 >= size)
+		return size;
+	if (test_bit_le(offset + 1, addr))
+		return offset + 1;
+	return find_next_bit_le(addr, size, offset + 2);
+}
+
+static inline unsigned long f2fs_find_next_zero_bit(const void *addr,
+		unsigned long size, unsigned long offset)
+{
+	if (!test_bit(offset, addr))
+		return offset;
+	if (offset + 1 >= size)
+		return size;
+	if (!test_bit(offset + 1, addr))
+		return offset + 1;
+	return find_next_zero_bit(addr, size, offset + 2);
+}
+
+static inline unsigned long f2fs_find_next_bit(const void *addr,
+		unsigned long size, unsigned long offset)
+{
+	if (test_bit(offset, addr))
+		return offset;
+	if (offset + 1 >= size)
+		return size;
+	if (test_bit(offset + 1, addr))
+		return offset + 1;
+	return find_next_bit(addr, size, offset + 2);
+}
+
 #define get_inode_mode(i) \
 	((is_inode_flag_set(i, FI_ACL_MODE)) ? \
 	 (F2FS_I(i)->i_acl_mode) : ((i)->i_mode))
diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
index 9c18917..f35fca5 100644
--- a/fs/f2fs/gc.c
+++ b/fs/f2fs/gc.c
@@ -301,7 +301,8 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 		unsigned long cost;
 		unsigned int segno;
 
-		segno = find_next_bit(p.dirty_segmap, last_segment, p.offset);
+		segno = f2fs_find_next_bit(p.dirty_segmap, last_segment,
+								p.offset);
 		if (segno >= last_segment) {
 			if (sbi->last_victim[p.gc_mode]) {
 				last_segment = sbi->last_victim[p.gc_mode];
diff --git a/fs/f2fs/inline.c b/fs/f2fs/inline.c
index 8cab5df..def731a 100644
--- a/fs/f2fs/inline.c
+++ b/fs/f2fs/inline.c
@@ -593,7 +593,7 @@ bool f2fs_empty_inline_dir(struct inode *dir)
 		return false;
 
 	dentry_blk = inline_data_addr(ipage);
-	bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap,
+	bit_pos = f2fs_find_next_bit_le(&dentry_blk->dentry_bitmap,
 					NR_INLINE_DENTRY,
 					bit_pos);
 
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index bbb9355..0d70155 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -785,10 +785,11 @@ void clear_prefree_segments(struct f2fs_sb_info *sbi, struct cp_control *cpc)
 
 	while (1) {
 		int i;
-		start = find_next_bit(prefree_map, MAIN_SEGS(sbi), end + 1);
+		start = f2fs_find_next_bit(prefree_map, MAIN_SEGS(sbi),
+								end + 1);
 		if (start >= MAIN_SEGS(sbi))
 			break;
-		end = find_next_zero_bit(prefree_map, MAIN_SEGS(sbi),
+		end = f2fs_find_next_zero_bit(prefree_map, MAIN_SEGS(sbi),
 								start + 1);
 
 		for (i = start; i < end; i++)
@@ -1078,16 +1079,17 @@ static void get_new_segment(struct f2fs_sb_info *sbi,
 	spin_lock(&free_i->segmap_lock);
 
 	if (!new_sec && ((*newseg + 1) % sbi->segs_per_sec)) {
-		segno = find_next_zero_bit(free_i->free_segmap,
+		segno = f2fs_find_next_zero_bit(free_i->free_segmap,
 				(hint + 1) * sbi->segs_per_sec, *newseg + 1);
 		if (segno < (hint + 1) * sbi->segs_per_sec)
 			goto got_it;
 	}
 find_other_zone:
-	secno = find_next_zero_bit(free_i->free_secmap, MAIN_SECS(sbi), hint);
+	secno = f2fs_find_next_zero_bit(free_i->free_secmap, MAIN_SECS(sbi),
+								hint);
 	if (secno >= MAIN_SECS(sbi)) {
 		if (dir == ALLOC_RIGHT) {
-			secno = find_next_zero_bit(free_i->free_secmap,
+			secno = f2fs_find_next_zero_bit(free_i->free_secmap,
 							MAIN_SECS(sbi), 0);
 			f2fs_bug_on(sbi, secno >= MAIN_SECS(sbi));
 		} else {
@@ -1103,7 +1105,7 @@ static void get_new_segment(struct f2fs_sb_info *sbi,
 			left_start--;
 			continue;
 		}
-		left_start = find_next_zero_bit(free_i->free_secmap,
+		left_start = f2fs_find_next_zero_bit(free_i->free_secmap,
 							MAIN_SECS(sbi), 0);
 		f2fs_bug_on(sbi, left_start >= MAIN_SECS(sbi));
 		break;
diff --git a/fs/f2fs/segment.h b/fs/f2fs/segment.h
index d8ff069..fb58925 100644
--- a/fs/f2fs/segment.h
+++ b/fs/f2fs/segment.h
@@ -336,7 +336,7 @@ static inline unsigned int find_next_inuse(struct free_segmap_info *free_i,
 {
 	unsigned int ret;
 	spin_lock(&free_i->segmap_lock);
-	ret = find_next_bit(free_i->free_segmap, max, segno);
+	ret = f2fs_find_next_bit(free_i->free_segmap, max, segno);
 	spin_unlock(&free_i->segmap_lock);
 	return ret;
 }
@@ -352,7 +352,7 @@ static inline void __set_free(struct f2fs_sb_info *sbi, unsigned int segno)
 	clear_bit(segno, free_i->free_segmap);
 	free_i->free_segments++;
 
-	next = find_next_bit(free_i->free_segmap,
+	next = f2fs_find_next_bit(free_i->free_segmap,
 			start_segno + sbi->segs_per_sec, start_segno);
 	if (next >= start_segno + sbi->segs_per_sec) {
 		clear_bit(secno, free_i->free_secmap);
@@ -384,7 +384,7 @@ static inline void __set_test_and_free(struct f2fs_sb_info *sbi,
 	if (test_and_clear_bit(segno, free_i->free_segmap)) {
 		free_i->free_segments++;
 
-		next = find_next_bit(free_i->free_segmap,
+		next = f2fs_find_next_bit(free_i->free_segmap,
 				start_segno + sbi->segs_per_sec, start_segno);
 		if (next >= start_segno + sbi->segs_per_sec) {
 			if (test_and_clear_bit(secno, free_i->free_secmap))
@@ -607,12 +607,13 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
 	/* check bitmap with valid block count */
 	do {
 		if (is_valid) {
-			next_pos = find_next_zero_bit_le(&raw_sit->valid_map,
+			next_pos = f2fs_find_next_zero_bit_le(
+					&raw_sit->valid_map,
 					sbi->blocks_per_seg,
 					cur_pos);
 			valid_blocks += next_pos - cur_pos;
 		} else
-			next_pos = find_next_bit_le(&raw_sit->valid_map,
+			next_pos = f2fs_find_next_bit_le(&raw_sit->valid_map,
 					sbi->blocks_per_seg,
 					cur_pos);
 		cur_pos = next_pos;
-- 
2.8.3