search for: xb_find_set

On Wed, Dec 20, 2017 at 04:13:16PM +0000, Wang, Wei W wrote: > On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > > unsigned long bit; > > xb_preload(GFP_KERNEL); > > xb_set_bit(xb, 700); > > xb_preload_end(); > > bit = xb_find_set(xb, ULONG_MAX, 0); > > assert(bit == 700); > > This above test will result in "!node with bitmap !=NULL", and it goes to the regular "if (bitmap)" path, which finds 700. > > A better test would be > ... > xb_set_bit(xb, 700); > assert(xb_find_set(xb...

On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > On Wed, Dec 20, 2017 at 06:34:36PM +0800, Wei Wang wrote: > > On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > > > I think xb_find_set() has a bug in !node path. > > > > I think we can probably remove the "!node" path for now. It would be > > good to get the fundamental part in first, and leave optimization to > > come as separate patches with corresponding test cases in the future. > > You...

On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > On Wed, Dec 20, 2017 at 06:34:36PM +0800, Wei Wang wrote: > > On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > > > I think xb_find_set() has a bug in !node path. > > > > I think we can probably remove the "!node" path for now. It would be > > good to get the fundamental part in first, and leave optimization to > > come as separate patches with corresponding test cases in the future. > > You...

On 12/22/2017 05:03 AM, Matthew Wilcox wrote: > OK, here's a rewrite of xbitmap. > > Compared to the version you sent: > - xb_find_set() is the rewrite I sent out yesterday. > - xb_find_clear() is a new implementation. I use the IDR_FREE tag to find > clear bits. This led to me finding a bug in radix_tree_for_each_tagged(). > - xb_zero() is also a new implementation (replacing xb_clear_bit_range). > It sh...

On 12/22/2017 05:03 AM, Matthew Wilcox wrote: > OK, here's a rewrite of xbitmap. > > Compared to the version you sent: > - xb_find_set() is the rewrite I sent out yesterday. > - xb_find_clear() is a new implementation. I use the IDR_FREE tag to find > clear bits. This led to me finding a bug in radix_tree_for_each_tagged(). > - xb_zero() is also a new implementation (replacing xb_clear_bit_range). > It sh...

...nline void xb_init(struct xb *xb) int xb_set_bit(struct xb *xb, unsigned long bit); bool xb_test_bit(const struct xb *xb, unsigned long bit); void xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits); +unsigned long xb_find_set(struct xb *xb, unsigned long size, + unsigned long offset); +unsigned long xb_find_zero(struct xb *xb, unsigned long size, + unsigned long offset); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index a1c0abd..1c99586 100644 --- a/lib/xbit...

...nline void xb_init(struct xb *xb) int xb_set_bit(struct xb *xb, unsigned long bit); bool xb_test_bit(const struct xb *xb, unsigned long bit); void xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits); +unsigned long xb_find_set(struct xb *xb, unsigned long size, + unsigned long offset); +unsigned long xb_find_zero(struct xb *xb, unsigned long size, + unsigned long offset); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index a1c0abd..1c99586 100644 --- a/lib/xbit...

...AX)) will take too long time. This can be optimized in >> the future. >> - remove the exceptional path; >> - remove xb_preload_and_set(); >> - reimplement xb_clear_bit_range to make its usage close to >> bitmap_clear; >> - rename xb_find_next_set_bit to xb_find_set, and re-implement it >> in a style close to find_next_bit; >> - rename xb_find_next_zero_bit to xb_find_clear, and re-implement >> it in a stytle close to find_next_zero_bit; >> - separate the implementation of xb_find_set and xb_find_clear for >> the conven...

...AX)) will take too long time. This can be optimized in >> the future. >> - remove the exceptional path; >> - remove xb_preload_and_set(); >> - reimplement xb_clear_bit_range to make its usage close to >> bitmap_clear; >> - rename xb_find_next_set_bit to xb_find_set, and re-implement it >> in a style close to find_next_bit; >> - rename xb_find_next_zero_bit to xb_find_clear, and re-implement >> it in a stytle close to find_next_zero_bit; >> - separate the implementation of xb_find_set and xb_find_clear for >> the conven...

...b_set_bit(struct xb *xb, unsigned long bit); +bool xb_test_bit(const struct xb *xb, unsigned long bit); +void xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_zero(struct xb *xb, unsigned long min, unsigned long max); +void xb_fill(struct xb *xb, unsigned long min, unsigned long max); +bool xb_find_set(const struct xb *xb, unsigned long max, unsigned long *bit); +bool xb_find_zero(const struct xb *xb, unsigned long max, unsigned long *bit); + +static inline bool xb_empty(const struct xb *xb) +{ + return radix_tree_empty(&xb->xbrt); +} + +int __must_check xb_preload(gfp_t); + +static inline...

OK, here's a rewrite of xbitmap. Compared to the version you sent: - xb_find_set() is the rewrite I sent out yesterday. - xb_find_clear() is a new implementation. I use the IDR_FREE tag to find clear bits. This led to me finding a bug in radix_tree_for_each_tagged(). - xb_zero() is also a new implementation (replacing xb_clear_bit_range). It should also be more effici...

On 12/21/2017 10:37 PM, Tetsuo Handa wrote: > Matthew Wilcox wrote: >>> +/** >>> + * xb_find_set - find the next set bit in a range of bits >>> + * @xb: the xbitmap to search from >>> + * @offset: the offset in the range to start searching >>> + * @size: the size of the range >>> + * >>> + * Returns: the found bit or, @size if no set bit is found. &...

...on extremely large ranges (e.g. [0, ULONG_MAX)) will take too long time. This can be optimized in the future. - remove the exceptional path; - remove xb_preload_and_set(); - reimplement xb_clear_bit_range to make its usage close to bitmap_clear; - rename xb_find_next_set_bit to xb_find_set, and re-implement it in a style close to find_next_bit; - rename xb_find_next_zero_bit to xb_find_clear, and re-implement it in a stytle close to find_next_zero_bit; - separate the implementation of xb_find_set and xb_find_clear for the convenience of future updates. 3) patch 4: virtio-b...

...ill take too long time. This can be optimized in > > the future. > > - remove the exceptional path; > > - remove xb_preload_and_set(); > > - reimplement xb_clear_bit_range to make its usage close to > > bitmap_clear; > > - rename xb_find_next_set_bit to xb_find_set, and re-implement it > > in a style close to find_next_bit; > > - rename xb_find_next_zero_bit to xb_find_clear, and re-implement > > it in a stytle close to find_next_zero_bit; > > - separate the implementation of xb_find_set and xb_find_clear for > > the c...

...te: > On Wed, Dec 20, 2017 at 04:13:16PM +0000, Wang, Wei W wrote: >> On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: >>> unsigned long bit; >>> xb_preload(GFP_KERNEL); >>> xb_set_bit(xb, 700); >>> xb_preload_end(); >>> bit = xb_find_set(xb, ULONG_MAX, 0); >>> assert(bit == 700); >> This above test will result in "!node with bitmap !=NULL", and it goes to the regular "if (bitmap)" path, which finds 700. >> >> A better test would be >> ... >> xb_set_bit(xb, 700); >> a...

...ill take too long time. This can be optimized in > > the future. > > - remove the exceptional path; > > - remove xb_preload_and_set(); > > - reimplement xb_clear_bit_range to make its usage close to > > bitmap_clear; > > - rename xb_find_next_set_bit to xb_find_set, and re-implement it > > in a style close to find_next_bit; > > - rename xb_find_next_zero_bit to xb_find_clear, and re-implement > > it in a stytle close to find_next_zero_bit; > > - separate the implementation of xb_find_set and xb_find_clear for > > the c...

On Wed, Dec 20, 2017 at 06:34:36PM +0800, Wei Wang wrote: > On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > > I think xb_find_set() has a bug in !node path. > > I think we can probably remove the "!node" path for now. It would be good to > get the fundamental part in first, and leave optimization to come as > separate patches with corresponding test cases in the future. You can't remove the !node p...

...on extremely large ranges (e.g. [0, ULONG_MAX)) will take too long time. This can be optimized in the future. - remove the exceptional path; - remove xb_preload_and_set(); - reimplement xb_clear_bit_range to make its usage close to bitmap_clear; - rename xb_find_next_set_bit to xb_find_set, and re-implement it in a style close to find_next_bit; - rename xb_find_next_zero_bit to xb_find_clear, and re-implement it in a stytle close to find_next_zero_bit; - separate the implementation of xb_find_set and xb_find_clear for the convenience of future updates. 3) patch 4: virtio-b...

...on extremely large ranges (e.g. [0, ULONG_MAX)) will take too long time. This can be optimized in the future. - remove the exceptional path; - remove xb_preload_and_set(); - reimplement xb_clear_bit_range to make its usage close to bitmap_clear; - rename xb_find_next_set_bit to xb_find_set, and re-implement it in a style close to find_next_bit; - rename xb_find_next_zero_bit to xb_find_clear, and re-implement it in a stytle close to find_next_zero_bit; - separate the implementation of xb_find_set and xb_find_clear for the convenience of future updates. 3) patch 4: virtio-b...

On Fri, Dec 15, 2017 at 10:49:15AM -0800, Matthew Wilcox wrote: > Here's the API I'm looking at right now. The user need take no lock; > the locking (spinlock) is handled internally to the implementation. I looked at the API some more and found some flaws: - how does xbit_alloc communicate back which bit it allocated? - What if xbit_find_set() is called on a completely empty