* [PATCH] xfs: improve xfs_bitmap_empty() @ 2014-01-31 14:13 Jeff Liu 2014-01-31 15:07 ` Eric Sandeen 0 siblings, 1 reply; 10+ messages in thread From: Jeff Liu @ 2014-01-31 14:13 UTC (permalink / raw) To: xfs@oss.sgi.com 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 ^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 14:13 [PATCH] xfs: improve xfs_bitmap_empty() Jeff Liu @ 2014-01-31 15:07 ` Eric Sandeen 2014-01-31 15:28 ` Jeff Liu 0 siblings, 1 reply; 10+ messages in thread From: Eric Sandeen @ 2014-01-31 15:07 UTC (permalink / raw) To: Jeff Liu, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 15:07 ` Eric Sandeen @ 2014-01-31 15:28 ` Jeff Liu 2014-01-31 15:30 ` Eric Sandeen 0 siblings, 1 reply; 10+ messages in thread From: Jeff Liu @ 2014-01-31 15:28 UTC (permalink / raw) To: Eric Sandeen, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 15:28 ` Jeff Liu @ 2014-01-31 15:30 ` Eric Sandeen 2014-01-31 15:51 ` Jeff Liu 0 siblings, 1 reply; 10+ messages in thread From: Eric Sandeen @ 2014-01-31 15:30 UTC (permalink / raw) To: Jeff Liu, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 15:30 ` Eric Sandeen @ 2014-01-31 15:51 ` Jeff Liu 2014-01-31 16:28 ` Mark Tinguely 0 siblings, 1 reply; 10+ messages in thread From: Jeff Liu @ 2014-01-31 15:51 UTC (permalink / raw) To: Eric Sandeen, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 15:51 ` Jeff Liu @ 2014-01-31 16:28 ` Mark Tinguely 2014-01-31 16:47 ` Eric Sandeen 2014-02-01 3:48 ` Jeff Liu 0 siblings, 2 replies; 10+ messages in thread From: Mark Tinguely @ 2014-01-31 16:28 UTC (permalink / raw) To: Jeff Liu; +Cc: Eric Sandeen, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 16:28 ` Mark Tinguely @ 2014-01-31 16:47 ` Eric Sandeen 2014-02-01 3:48 ` Jeff Liu 1 sibling, 0 replies; 10+ messages in thread From: Eric Sandeen @ 2014-01-31 16:47 UTC (permalink / raw) To: Mark Tinguely, Jeff Liu; +Cc: xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-01-31 16:28 ` Mark Tinguely 2014-01-31 16:47 ` Eric Sandeen @ 2014-02-01 3:48 ` Jeff Liu 2014-02-02 21:52 ` Dave Chinner 1 sibling, 1 reply; 10+ messages in thread From: Jeff Liu @ 2014-02-01 3:48 UTC (permalink / raw) To: Mark Tinguely; +Cc: Eric Sandeen, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-02-01 3:48 ` Jeff Liu @ 2014-02-02 21:52 ` Dave Chinner 2014-02-04 15:10 ` Jeff Liu 0 siblings, 1 reply; 10+ messages in thread From: Dave Chinner @ 2014-02-02 21:52 UTC (permalink / raw) To: Jeff Liu; +Cc: Eric Sandeen, Mark Tinguely, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] xfs: improve xfs_bitmap_empty() 2014-02-02 21:52 ` Dave Chinner @ 2014-02-04 15:10 ` Jeff Liu 0 siblings, 0 replies; 10+ messages in thread From: Jeff Liu @ 2014-02-04 15:10 UTC (permalink / raw) To: Dave Chinner; +Cc: Eric Sandeen, Mark Tinguely, xfs@oss.sgi.com 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2014-02-04 15:10 UTC | newest] Thread overview: 10+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2014-01-31 14:13 [PATCH] xfs: improve xfs_bitmap_empty() Jeff Liu 2014-01-31 15:07 ` Eric Sandeen 2014-01-31 15:28 ` Jeff Liu 2014-01-31 15:30 ` Eric Sandeen 2014-01-31 15:51 ` Jeff Liu 2014-01-31 16:28 ` Mark Tinguely 2014-01-31 16:47 ` Eric Sandeen 2014-02-01 3:48 ` Jeff Liu 2014-02-02 21:52 ` Dave Chinner 2014-02-04 15:10 ` Jeff Liu
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).