xfs: improve xfs_bitmap_empty()

From: Jie Liu <[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu <[email protected]>

---
 fs/xfs/xfs_bit.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

fs/xfs/xfs_bit.c +0 -1

index 0e8885a..ae0acc2 100644
@@ -32,13 +32,13 @@ int
 xfs_bitmap_empty(uint *map, uint size)
 {
 	uint i;
-	uint ret = 0;
 
 	for (i = 0; i < size; i++) {

Quoted 7 lines · Jeff Liu

From: Jie Liu <[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu <[email protected]>

Makes sense (and the long loop was my fault, I guess, but it's better than it was, see commit 24ad33f!)

Reviewed-by Eric Sandeen <[email protected]>

I wonder if something like:

return (find_first_set(map, size) == size);

would be faster (or if it'd be worth it)...?
Probably not. :)

Quoted 11 lines · Eric Sandeen

Quoted 7 lines · Jeff Liu

From: Jie Liu <[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu <[email protected]>

Makes sense (and the long loop was my fault, I guess, but it's better than it was, see commit 24ad33f!)

Ah, you have killed a lots code there! :)

Quoted 6 lines

Reviewed-by Eric Sandeen <[email protected]>

I wonder if something like:

return (find_first_set(map, size) == size);

Quoted 3 lines

would be faster (or if it'd be worth it)...?
Probably not. :)

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Otherwise, maybe some like find_first_bit(map, size) would be more convenient.

Thanks,
-Jeff

Quoted 25 lines · Jeff Liu

Quoted 11 lines · Eric Sandeen

Quoted 7 lines · Jeff Liu

From: Jie Liu <[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu <[email protected]>

Makes sense (and the long loop was my fault, I guess, but it's better than it was, see commit 24ad33f!)

Ah, you have killed a lots code there! :)

Quoted 9 lines

Reviewed-by Eric Sandeen <[email protected]>

I wonder if something like:

return (find_first_set(map, size) == size);

would be faster (or if it'd be worth it)...?
Probably not. :)

Quoted 3 lines

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Technically the unsigned long (pointer) is just the bitmap address, I think.

Quoted 26 lines · Eric Sandeen

Quoted 25 lines · Jeff Liu

Quoted 11 lines · Eric Sandeen

Quoted 7 lines · Jeff Liu

From: Jie Liu<[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu<[email protected]>

Makes sense (and the long loop was my fault, I guess, but it's better than it was, see commit 24ad33f!)

Ah, you have killed a lots code there! :)

Quoted 9 lines

Reviewed-by Eric Sandeen<[email protected]>

I wonder if something like:

return (find_first_set(map, size) == size);

would be faster (or if it'd be worth it)...?
Probably not. :)

Quoted 6 lines

Quoted 3 lines

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Technically the unsigned long (pointer) is just the bitmap address, I think.

Yeah, so this might worth to try on long terms.

Quoted 35 lines · Jeff Liu

Quoted 32 lines · Eric Sandeen

Quoted 21 lines · Jeff Liu

Quoted 11 lines · Eric Sandeen

Quoted 7 lines · Jeff Liu

From: Jie Liu<[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu<[email protected]>

Makes sense (and the long loop was my fault, I guess, but it's better than it was, see commit 24ad33f!)

Ah, you have killed a lots code there! :)

Quoted 6 lines

Reviewed-by Eric Sandeen<[email protected]>

I wonder if something like:

return (find_first_set(map, size) == size);

Quoted 7 lines

Quoted 3 lines

would be faster (or if it'd be worth it)...?
Probably not. :)

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Technically the unsigned long (pointer) is just the bitmap address, I think.

Quoted 2 lines

Yeah, so this might worth to try on long terms.

The blf_data_map[] is int aligned, not long aligned. You could reflect the alignment difference in the offset or change the alignment in the structure.

--Mark.

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Quoted 35 lines · Jeff Liu

Quoted 32 lines · Eric Sandeen

Quoted 21 lines · Jeff Liu

Quoted 11 lines · Eric Sandeen

Quoted 7 lines · Jeff Liu

From: Jie Liu<[email protected]>

There is no need to travel through the whole bitmap items to verify if the bitmap array is empty or not, instead, just return 0 directly if an item is detected in bitmap array.

Signed-off-by Jie Liu<[email protected]>

Makes sense (and the long loop was my fault, I guess, but it's better than it was, see commit 24ad33f!)

Ah, you have killed a lots code there! :)

Quoted 6 lines

Reviewed-by Eric Sandeen<[email protected]>

I wonder if something like:

return (find_first_set(map, size) == size);

Quoted 7 lines

Quoted 3 lines

would be faster (or if it'd be worth it)...?
Probably not. :)

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Technically the unsigned long (pointer) is just the bitmap address, I think.

Quoted 2 lines

Yeah, so this might worth to try on long terms.

The blf_data_map[] is int aligned, not long aligned. You could reflect the alignment difference in the offset or change the alignment in the structure.

Quoted 10 lines · Mark Tinguely

Quoted 9 lines · Jeff Liu

Quoted 7 lines · Eric Sandeen

Quoted 3 lines · Jeff Liu

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Technically the unsigned long (pointer) is just the bitmap address, I think.

Quoted 5 lines

Quoted 1 line

Yeah, so this might worth to try on long terms.

The blf_data_map[] is int aligned, not long aligned. You could reflect the alignment difference in the offset or change the alignment in the structure.

For now, I think we can not simply turn to generic bitmap just because of the alignment difference on 64-bits OS.

Quoted 11 lines · Jeff Liu

Quoted 10 lines · Mark Tinguely

Quoted 9 lines · Jeff Liu

Quoted 7 lines · Eric Sandeen

Quoted 3 lines · Jeff Liu

Well, when I looking through our bitmap source, I once thought if we can replace the current code with the generic bitmap library. However, our map is uint rather than unsigned long...

Technically the unsigned long (pointer) is just the bitmap address, I think.

Quoted 8 lines

Quoted 5 lines

Quoted 1 line

Yeah, so this might worth to try on long terms.

The blf_data_map[] is int aligned, not long aligned. You could reflect the alignment difference in the offset or change the alignment in the structure.

For now, I think we can not simply turn to generic bitmap just because of the alignment difference on 64-bits OS.

The bitmaps end up on disk (in the log), so replacing the implementation with a generic implementation is something we need to be very careful about.

IMO, we should be getting rid of the bitmaps from the xfs_buf_log_item first (by moving to a low byte/high byte offset range), then we only have to worry about bitmaps when doing log recovery after a kernel upgrade on a filesystem with a dirty log.

Getting rid of the bitmaps also solves a scalability problem with large block sizes tracking all the changes in buffer - we burn a huge amount of CPU walking bits when logging 64k directory buffers:

(quoted diff) +6 -0

+  21.19%  [kernel]  [k] xfs_dir3_leaf_check_int
+  12.20%  [kernel]  [k] memcpy
+   9.29%  [kernel]  [k] xfs_next_bit
+   5.04%  [kernel]  [k] xfs_buf_offset
+   3.63%  [kernel]  [k] xfs_buf_item_format
+   3.59%  [kernel]  [k] xfs_buf_item_size_segment

The logging of xfs_buf_log_items there is consuming >30% of the CPU being used under this workload (xfs_dir3_leaf_check_int() is high because this is from a debug kernel.)

IOWs, we should work to remove the bitmap code from general operations first, then replace the remaining legacy log recovery code with the generic bitmap implemention....