[PATCH] xfs: improve xfs_bitmap_empty()

[PATCH] xfs: improve xfs_bitmap_empty()

[Jeff Liu]

From: Jie Liu <jeff.liu@oracle.com>

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 <jeff.liu@oracle.com>
---
 fs/xfs/xfs_bit.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/fs/xfs/xfs_bit.c b/fs/xfs/xfs_bit.c
index 0e8885a..ae0acc2 100644
--- a/fs/xfs/xfs_bit.c
+++ b/fs/xfs/xfs_bit.c
@@ -32,13 +32,13 @@ int
 xfs_bitmap_empty(uint *map, uint size)
 {
 	uint i;
-	uint ret = 0;
 
 	for (i = 0; i < size; i++) {
-		ret |= map[i];
+		if (map[i])
+			return 0;
 	}
 
-	return (ret == 0);
+	return 1;
 }
 
 /*
-- 
1.8.3.2

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Eric Sandeen]

On 1/31/14, 8:13 AM, Jeff Liu wrote:
> From: Jie Liu <jeff.liu@oracle.com>
> 
> 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 <jeff.liu@oracle.com>

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 <sandeen@redhat.com>

I wonder if something like:

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

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

> ---
>  fs/xfs/xfs_bit.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/xfs/xfs_bit.c b/fs/xfs/xfs_bit.c
> index 0e8885a..ae0acc2 100644
> --- a/fs/xfs/xfs_bit.c
> +++ b/fs/xfs/xfs_bit.c
> @@ -32,13 +32,13 @@ int
>  xfs_bitmap_empty(uint *map, uint size)
>  {
>  	uint i;
> -	uint ret = 0;
>  
>  	for (i = 0; i < size; i++) {
> -		ret |= map[i];
> +		if (map[i])
> +			return 0;
>  	}
>  
> -	return (ret == 0);
> +	return 1;
>  }
>  
>  /*
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Jeff Liu]

On 01/31 2014 23:07 PM, Eric Sandeen wrote:
> On 1/31/14, 8:13 AM, Jeff Liu wrote:
>> From: Jie Liu <jeff.liu@oracle.com>
>>
>> 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 <jeff.liu@oracle.com>
> 
> 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! :)
> Reviewed-by: Eric Sandeen <sandeen@redhat.com>
> 
> I wonder if something like:
> 
> return (find_first_set(map, size) == size);
> 
> 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

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Eric Sandeen]

On 1/31/14, 9:28 AM, Jeff Liu wrote:
> 
> On 01/31 2014 23:07 PM, Eric Sandeen wrote:
>> On 1/31/14, 8:13 AM, Jeff Liu wrote:
>>> From: Jie Liu <jeff.liu@oracle.com>
>>>
>>> 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 <jeff.liu@oracle.com>
>>
>> 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! :)
>> Reviewed-by: Eric Sandeen <sandeen@redhat.com>
>>
>> I wonder if something like:
>>
>> return (find_first_set(map, size) == size);
>>
>> 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.

-Eric

> Otherwise, maybe some like find_first_bit(map, size) would be
> more convenient.
> 
> Thanks,
> -Jeff
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Jeff Liu]

On 01/31 2014 23:30 PM, Eric Sandeen wrote:
> On 1/31/14, 9:28 AM, Jeff Liu wrote:
>>
>> On 01/31 2014 23:07 PM, Eric Sandeen wrote:
>>> On 1/31/14, 8:13 AM, Jeff Liu wrote:
>>>> From: Jie Liu <jeff.liu@oracle.com>
>>>>
>>>> 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 <jeff.liu@oracle.com>
>>>
>>> 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! :)
>>> Reviewed-by: Eric Sandeen <sandeen@redhat.com>
>>>
>>> I wonder if something like:
>>>
>>> return (find_first_set(map, size) == size);
>>>
>>> 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.

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

Thanks,
-Jeff

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Mark Tinguely]

On 01/31/14 09:51, Jeff Liu wrote:
>
> On 01/31 2014 23:30 PM, Eric Sandeen wrote:
>> On 1/31/14, 9:28 AM, Jeff Liu wrote:
>>>
>>> On 01/31 2014 23:07 PM, Eric Sandeen wrote:
>>>> On 1/31/14, 8:13 AM, Jeff Liu wrote:
>>>>> From: Jie Liu<jeff.liu@oracle.com>
>>>>>
>>>>> 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<jeff.liu@oracle.com>
>>>>
>>>> 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! :)
>>>> Reviewed-by: Eric Sandeen<sandeen@redhat.com>
>>>>
>>>> I wonder if something like:
>>>>
>>>> return (find_first_set(map, size) == size);
>>>>
>>>> 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.
>
> 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
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Eric Sandeen]

On 1/31/14, 10:28 AM, Mark Tinguely wrote:
> On 01/31/14 09:51, Jeff Liu wrote:
>>
>> On 01/31 2014 23:30 PM, Eric Sandeen wrote:
>>> On 1/31/14, 9:28 AM, Jeff Liu wrote:
>>>>
>>>> On 01/31 2014 23:07 PM, Eric Sandeen wrote:
>>>>> On 1/31/14, 8:13 AM, Jeff Liu wrote:
>>>>>> From: Jie Liu<jeff.liu@oracle.com>
>>>>>>
>>>>>> 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<jeff.liu@oracle.com>
>>>>>
>>>>> 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! :)
>>>>> Reviewed-by: Eric Sandeen<sandeen@redhat.com>
>>>>>
>>>>> I wonder if something like:
>>>>>
>>>>> return (find_first_set(map, size) == size);
>>>>>
>>>>> 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.
>>
>> 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.

Oh, I guess it does matter.  Sometimes C escapes me...

probably not worth messing with.  I'll stop thinking
out loud in front of everybody, now.  ;)

Thanks,
-Eric
 
> --Mark.
> 
> _______________________________________________
> xfs mailing list
> xfs@oss.sgi.com
> http://oss.sgi.com/mailman/listinfo/xfs
> 

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Jeff Liu]

On 02/01 2014 00:28 AM, Mark Tinguely wrote:
> On 01/31/14 09:51, Jeff Liu wrote:
>>
>> On 01/31 2014 23:30 PM, Eric Sandeen wrote:
>>> On 1/31/14, 9:28 AM, Jeff Liu wrote:
>>>>
>>>> On 01/31 2014 23:07 PM, Eric Sandeen wrote:
>>>>> On 1/31/14, 8:13 AM, Jeff Liu wrote:
>>>>>> From: Jie Liu<jeff.liu@oracle.com>
>>>>>>
>>>>>> 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<jeff.liu@oracle.com>
>>>>>
>>>>> 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! :)
>>>>> Reviewed-by: Eric Sandeen<sandeen@redhat.com>
>>>>>
>>>>> I wonder if something like:
>>>>>
>>>>> return (find_first_set(map, size) == size);
>>>>>
>>>>> 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.
>>
>> 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.

Thanks,
-Jeff

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Dave Chinner]

On Sat, Feb 01, 2014 at 11:48:48AM +0800, Jeff Liu wrote:
> On 02/01 2014 00:28 AM, Mark Tinguely wrote:
> > On 01/31/14 09:51, Jeff Liu wrote:
> >> On 01/31 2014 23:30 PM, Eric Sandeen wrote:
> >>> On 1/31/14, 9:28 AM, Jeff Liu wrote:
> >>>> 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.
> > 
> > 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:

+  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....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

Re: [PATCH] xfs: improve xfs_bitmap_empty()

[Jeff Liu]

On 02/03 2014 05:52 AM, Dave Chinner wrote:
> On Sat, Feb 01, 2014 at 11:48:48AM +0800, Jeff Liu wrote:
>> On 02/01 2014 00:28 AM, Mark Tinguely wrote:
>>> On 01/31/14 09:51, Jeff Liu wrote:
>>>> On 01/31 2014 23:30 PM, Eric Sandeen wrote:
>>>>> On 1/31/14, 9:28 AM, Jeff Liu wrote:
>>>>>> 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.
>>>
>>> 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:
> 
> +  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....

Sorry for my too late response as I was on vacations.

I only moved a little progress after a quick hacking, but I can see the point
in getting rid of the bitmap, just give me yet a week once I was totally return
to work.


Thanks,
-Jeff

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs