On Thu, Dec 3, 2020 at 2:26 AM Yury Norov <yury.norov@xxxxxxxxx> wrote: > Also look at lib/find_bit_benchmark.c Thanks. I'll see. > We need find_next_*_bit() because find_first_*_bit() can start searching only at word-aligned > bits. In the case of find_last_*_bit(), we can start at any bit. So, if my understanding is correct, > for the purpose of reverse traversing we can go with already existing find_last_bit(), Thank you. I haven't thought that way. But I think if we implement reverse traversing using find_last_bit(), we have a problem. Suppose the last bit 0, 1, 2, is set. If we start find_last_bit(bitmap, 3) ==> return 2; find_last_bit(bitmap, 2) ==> return 1; find_last_bit(bitmap, 1) ==> return 0; find_last_bit(bitmap, 0) ===> return 0? // here we couldn't distinguish size 0 input or 0 is set and the for_each traverse routine prevent above case by returning size (nbits) using find_next_bit. So, for compatibility and the same expected return value like next traversing, I think we need to find_prev_*_bit routine. if my understanding is correct. > I think this patch has some good catches. We definitely need to implement > find_last_zero_bit(), as it is used by fs/ufs, and their local implementation is not optimal. > > We also should consider adding reverse traversing macros based on find_last_*_bit(), > if there are proposed users. Not only this, I think 'steal_from_bitmap_to_front' can be improved using ffind_prev_zero_bit like diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c index af0013d3df63..9debb9707390 100644 --- a/fs/btrfs/free-space-cache.c +++ b/fs/btrfs/free-space-cache.c @@ -2372,7 +2372,6 @@ static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl, u64 bitmap_offset; unsigned long i; unsigned long j; - unsigned long prev_j; u64 bytes; bitmap_offset = offset_to_bitmap(ctl, info->offset); @@ -2388,20 +2387,15 @@ static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl, return false; i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1; - j = 0; - prev_j = (unsigned long)-1; - for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) { - if (j > i) - break; - prev_j = j; - } - if (prev_j == i) + j = find_prev_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i); + + if (j == i) return false; - if (prev_j == (unsigned long)-1) + if (j == BITS_PER_BITMAP) bytes = (i + 1) * ctl->unit; else - bytes = (i - prev_j) * ctl->unit; + bytes = (i - j) * ctl->unit; info->offset -= bytes; info->bytes += bytes; Thanks. HTH Levi.