Skip to contentSkip to conversation

f2fs: check all ones or zeros bitmap with bitops for better mount performance

PATCH Superseded Chao Yu 3 participants 6 messages Oct 24, 2013 – Oct 28, 2013

Subsystems (2)
lore
Share & tools
lore

Chao Yu

author
#0 lore raw

PATCH v2 1/1 f2fs: check all ones or zeros bitmap with bitops for better mount performance

Previously, check_block_count check valid_map with bit data type in common scenario that sit has all ones or zeros bitmap, it makes low mount performance. So let's check the special bitmap with integer data type instead of the bit one.

v2:
use find_next_bit_le/find_next_zero_bit_le for better performance and readable as Jaegeuk suggested.

---
 fs/f2fs/segment.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)
fs/f2fs/segment.h +17 -0
index 7f94d78..d25b6af 100644
@@ -552,6 +552,23 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
 	/* check boundary of a given segment number */
 	BUG_ON(segno > end_segno);
 
+	/* check all ones or zeros valid_map */
+	if (GET_SIT_VBLOCKS(raw_sit) == 0) {
+		int pos = find_next_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	} else if (GET_SIT_VBLOCKS(raw_sit) == sbi->blocks_per_seg) {
+		int pos = find_next_zero_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	}
+
 	/* check bitmap with valid block count */
 	for (i = 0; i < sbi->blocks_per_seg; i++)
 		if (f2fs_test_bit(i, raw_sit->valid_map))
Signature · 9 lines
1.7.9.5


------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance.
Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from 
the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
#1 lore raw

Hi Yu,

Quoted 5 lines · Chao Yu

Previously, check_block_count check valid_map with bit data type in common scenario that sit has all ones or zeros bitmap, it makes low mount performance. So let's check the special bitmap with integer data type instead of the bit one.

v2:
use find_next_bit_le/find_next_zero_bit_le for better performance and readable as Jaegeuk suggested.

If so, how about using find_first_{zero_}bit_le instead? It's more neat.

Regards,
Gu

Quoted 36 lines
---
 fs/f2fs/segment.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)
fs/f2fs/segment.h +17 -0
index 7f94d78..d25b6af 100644
@@ -552,6 +552,23 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
 	/* check boundary of a given segment number */
 	BUG_ON(segno > end_segno);
 
+	/* check all ones or zeros valid_map */
+	if (GET_SIT_VBLOCKS(raw_sit) == 0) {
+		int pos = find_next_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	} else if (GET_SIT_VBLOCKS(raw_sit) == sbi->blocks_per_seg) {
+		int pos = find_next_zero_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	}
+
 	/* check bitmap with valid block count */
 	for (i = 0; i < sbi->blocks_per_seg; i++)
 		if (f2fs_test_bit(i, raw_sit->valid_map))
author
#2 lore raw

Hi Gu,

Quoted 15 lines

-----Original Message-----
From: Gu Zheng [mailto:[email protected]]
Sent: Thursday, October 24, 2013 6:04 PM
To: Chao Yu
Cc: [email protected]; [email protected]; [email protected]; [email protected]; '谭姝'
Subject: Re: [f2fs-dev] [PATCH V2] f2fs: check all ones or zeros bitmap with bitops for better mount performance

Hi Yu,

Quoted 1 line · Chao Yu

Previously, check_block_count check valid_map with bit data type in common

scenario that sit has all ones or zeros bitmap, it makes low mount performance.

Quoted 7 lines
Quoted 4 lines

So let's check the special bitmap with integer data type instead of the bit one.

v2:
use find_next_bit_le/find_next_zero_bit_le for better performance and

readable as Jaegeuk suggested.

If so, how about using find_first_{zero_}bit_le instead? It's more neat.

It seems more neat. I will take it, thanks.

Quoted 33 lines

Regards,
Gu

fs/f2fs/segment.h static inline void check_block_count(struct

Quoted 13 lines
---
 fs/f2fs/segment.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)
fs/f2fs/segment.h index renamed from fs/f2fs/segment.h +0 -0

7f94d78..d25b6af 100644

fs/f2fs/segment.h +0 -0
@@ -552,6 +552,23 @@ static inline void check_block_count(struct

f2fs_sb_info *sbi,

Quoted 15 lines
fs/f2fs/segment.h +12 -0
 	/* check boundary of a given segment number */
 	BUG_ON(segno > end_segno);
 
+	/* check all ones or zeros valid_map */
+	if (GET_SIT_VBLOCKS(raw_sit) == 0) {
+		int pos = find_next_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	} else if (GET_SIT_VBLOCKS(raw_sit) == sbi->blocks_per_seg) {
+		int pos = find_next_zero_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
Quoted 8 lines

fs/f2fs/segment.h static inline void check_block_count(struct f2fs_sb_info *sbi, · line 574

Quoted 8 lines
fs/f2fs/segment.h +5 -0
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	}
+
 	/* check bitmap with valid block count */
 	for (i = 0; i < sbi->blocks_per_seg; i++)
 		if (f2fs_test_bit(i, raw_sit->valid_map))

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

#3 lore raw
In reply to Chao Yu

To check whether bitmap are all zeros or all ones, I think memcmp is more neat. But I don't know exactly performance gap between memcmp and find_next_bit.

-----Original Message-----
From: Chao Yu [mailto:[email protected]]
Sent: Thursday, October 24, 2013 5:21 PM
To: [email protected]
Cc: [email protected]; '谭姝'; [email protected]; [email protected]
Subject: [f2fs-dev] [PATCH V2] f2fs: check all ones or zeros bitmap with bitops for better mount performance

Previously, check_block_count check valid_map with bit data type in common scenario that sit has all ones or zeros bitmap, it makes low mount performance. So let's check the special bitmap with integer data type instead of the bit one.

v2:
use find_next_bit_le/find_next_zero_bit_le for better performance and readable as Jaegeuk suggested.

---
 fs/f2fs/segment.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)
fs/f2fs/segment.h +17 -0
@@ -552,6 +552,23 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
 	/* check boundary of a given segment number */
 	BUG_ON(segno > end_segno);
 
+	/* check all ones or zeros valid_map */
+	if (GET_SIT_VBLOCKS(raw_sit) == 0) {
+		int pos = find_next_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	} else if (GET_SIT_VBLOCKS(raw_sit) == sbi->blocks_per_seg) {
+		int pos = find_next_zero_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	}
+
 	/* check bitmap with valid block count */
 	for (i = 0; i < sbi->blocks_per_seg; i++)
 		if (f2fs_test_bit(i, raw_sit->valid_map))

--
1.7.9.5

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

#4 lore raw
Quoted 2 lines · 이창만

To check whether bitmap are all zeros or all ones, I think memcmp is more neat. But I don't know exactly performance gap between memcmp and find_next_bit.

According to my understanding,
memcmp: one by one search,
find_next_bit: binary search.

Regards,
Gu

Quoted 64 lines

-----Original Message-----
From: Chao Yu [mailto:[email protected]]
Sent: Thursday, October 24, 2013 5:21 PM
To: [email protected]
Cc: [email protected]; '谭姝'; [email protected]; [email protected]
Subject: [f2fs-dev] [PATCH V2] f2fs: check all ones or zeros bitmap with bitops for better mount performance

Previously, check_block_count check valid_map with bit data type in common scenario that sit has all ones or zeros bitmap, it makes low mount performance. So let's check the special bitmap with integer data type instead of the bit one.

v2:
use find_next_bit_le/find_next_zero_bit_le for better performance and readable as Jaegeuk suggested.

---
 fs/f2fs/segment.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)
fs/f2fs/segment.h +17 -1
@@ -552,6 +552,23 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
 	/* check boundary of a given segment number */
 	BUG_ON(segno > end_segno);
 
+	/* check all ones or zeros valid_map */
+	if (GET_SIT_VBLOCKS(raw_sit) == 0) {
+		int pos = find_next_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	} else if (GET_SIT_VBLOCKS(raw_sit) == sbi->blocks_per_seg) {
+		int pos = find_next_zero_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	}
+
 	/* check bitmap with valid block count */
 	for (i = 0; i < sbi->blocks_per_seg; i++)
 		if (f2fs_test_bit(i, raw_sit->valid_map))
--

1.7.9.5

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

Quoted 6 lines

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

author
#5 lore raw
In reply to 이창만

Hi Lee,

Quoted 9 lines

-----Original Message-----
From: 이창만 [mailto:[email protected]]
Sent: Monday, October 28, 2013 10:20 AM
To: 'Chao Yu'; [email protected]
Cc: [email protected]; '谭姝'; [email protected]; [email protected]
Subject: RE: [f2fs-dev] [PATCH V2] f2fs: check all ones or zeros bitmap with bitops for better mount performance

Quoted 4 lines

To check whether bitmap are all zeros or all ones, I think memcmp is more neat.
But I don't know exactly performance gap between memcmp and find_next_bit.

With the result of my test, find_next_bit takes less time than memcmp.
If we could use {test, set, clear}_bit_le intead of f2fs_{test, set, clear}_bit, the following patch could be used for better performance.
This one is better than the V2 patch for performance with mixed bitmap in my test.

fs/f2fs/segment.h +17 -4
index 7f94d78..32153eb
@@ -544,7 +544,8 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
        struct f2fs_sm_info *sm_info = SM_I(sbi);
        unsigned int end_segno = sm_info->segment_count - 1;
        int valid_blocks = 0;
-       int i;
+       int i, cur_pos = 0, next_pos;
+       bool is_valid;
 
        /* check segment usage */
        BUG_ON(GET_SIT_VBLOCKS(raw_sit) > sbi->blocks_per_seg);
@@ -553,9 +554,21 @@ static inline void check_block_count(struct f2fs_sb_info *sbi,
        BUG_ON(segno > end_segno);
 
        /* check bitmap with valid block count */
-       for (i = 0; i < sbi->blocks_per_seg; i++)
-               if (f2fs_test_bit(i, raw_sit->valid_map))
-                       valid_blocks++;
+       cur_pos = 0;
+       is_valid = test_bit_le(0, raw_sit->valid_map) ? true : false;
+       do {
+               if (is_valid) {
+                       next_pos = 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,
+                                       sbi->blocks_per_seg,
+                                       cur_pos);
+               cur_pos = next_pos;
+               is_valid = !is_valid;
+       } while (cur_pos < sbi->blocks_per_seg);
        BUG_ON(GET_SIT_VBLOCKS(raw_sit) != valid_blocks);
 }
Quoted 60 lines

-----Original Message-----
From: Chao Yu [mailto:[email protected]]
Sent: Thursday, October 24, 2013 5:21 PM
To: [email protected]
Cc: [email protected]; '谭姝'; [email protected]; [email protected]
Subject: [f2fs-dev] [PATCH V2] f2fs: check all ones or zeros bitmap with bitops for better mount performance

Previously, check_block_count check valid_map with bit data type in common scenario that sit has all ones or zeros bitmap, it makes low mount performance.
So let's check the special bitmap with integer data type instead of the bit one.

v2:
use find_next_bit_le/find_next_zero_bit_le for better performance and
readable as Jaegeuk suggested.

---
 fs/f2fs/segment.h |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)
fs/f2fs/segment.h index 7f94d78..d25b6af renamed from fs/f2fs/segment.h +0 -0

100644

fs/f2fs/segment.h +17 -0
@@ -552,6 +552,23 @@ static inline void check_block_count(struct
 f2fs_sb_info *sbi,
 	/* check boundary of a given segment number */
 	BUG_ON(segno > end_segno);
 
+	/* check all ones or zeros valid_map */
+	if (GET_SIT_VBLOCKS(raw_sit) == 0) {
+		int pos = find_next_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	} else if (GET_SIT_VBLOCKS(raw_sit) == sbi->blocks_per_seg) {
+		int pos = find_next_zero_bit_le(&raw_sit->valid_map,
+					sbi->blocks_per_seg,
+					0);
+		if (pos != sbi->blocks_per_seg)
+			BUG();
+		return;
+	}
+
 	/* check bitmap with valid block count */
 	for (i = 0; i < sbi->blocks_per_seg; i++)

if (f2fs_test_bit(i, raw_sit->valid_map))
--
1.7.9.5

Quoted 11 lines

------------------------------------------------------------------------------
October Webinars: Code for Performance
Free Intel webinars can help you accelerate application performance. Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most from the latest Intel processors and coprocessors. See abstracts and register >
http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktr
k
_______________________________________________
Linux-f2fs-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html