search for: xb_clear_bit_range

...it(struct xb *xb, unsigned long bit); +void xb_clear_bit(struct xb *xb, unsigned long bit); +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, + unsigned long end); +unsigned long xb_find_next_zero_bit(struct xb *xb, unsigned long start, + unsigned long end); +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 182aa29..10df879 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -3,6 +3,13 @@ #include <linux/bitmap.h> #include <linux/slab....

...diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index ede1029b8a27..96e7e3560a0e 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -37,8 +37,7 @@ 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); +bool xb_find_set(struct xb *xb, unsigned long max, unsigned long *bit); unsigned long xb_find_zero(struct xb *xb, unsigned long size, uns...

On 12/13/2017 10:16 PM, Tetsuo Handa wrote: > Wei Wang wrote: >> On 12/12/2017 09:20 PM, Tetsuo Handa wrote: >>> Wei Wang wrote: >>>> +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) >>>> +{ >>>> + struct radix_tree_root *root = &xb->xbrt; >>>> + struct radix_tree_node *node; >>>> + void **slot; >>>> + struct ida_bitmap *bitmap; >>>> + unsigned i...

...9 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -35,6 +35,12 @@ static inline 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)...

...9 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -35,6 +35,12 @@ static inline 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)...

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

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

...: >> + * @start: the start of the bit range, inclusive >> + * @end: the end of the bit range, inclusive >> + * >> + * This function is used to clear a bit in the xbitmap. If all the bits of the >> + * bitmap are 0, the bitmap will be freed. >> + */ >> +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) >> +{ >> + struct radix_tree_root *root = &xb->xbrt; >> + struct radix_tree_node *node; >> + void **slot; >> + struct ida_bitmap *bitmap; >> + unsigned int nbits; >> + >> + for (; start &lt...

...+ * @end: the end of the bit range, inclusive > > >> + * > > >> + * This function is used to clear a bit in the xbitmap. If all the > > >> +bits of the > > >> + * bitmap are 0, the bitmap will be freed. > > >> + */ > > >> +void xb_clear_bit_range(struct xb *xb, unsigned long start, > > >> +unsigned long end) { > > >> + struct radix_tree_root *root = &xb->xbrt; > > >> + struct radix_tree_node *node; > > >> + void **slot; > > >> + struct ida_bitmap *bitmap; > > >>...

From: Matthew Wilcox <mawilcox at microsoft.com> The eXtensible Bitmap is a sparse bitmap representation which is efficient for set bits which tend to cluster. It supports up to 'unsigned long' worth of bits, and this commit adds the bare bones -- xb_set_bit(), xb_clear_bit(), xb_clear_bit_range(), xb_test_bit(), xb_find_next_set_bit(), xb_find_next_zero_bit(). More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add Tags to help searching. Signed-off...

...bit(bit, bitmap->bitmap); > + if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { Please write locking rules, in order to explain how double kfree() and/or use-after-free can be avoided. > + kfree(bitmap); > + __radix_tree_delete(root, node, slot); > + } > +} > +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) > +{ > + struct radix_tree_root *root = &xb->xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned int nbits; > + > + for (; start < end; start = (start | (IDA_BIT...

...bit(bit, bitmap->bitmap); > + if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { Please write locking rules, in order to explain how double kfree() and/or use-after-free can be avoided. > + kfree(bitmap); > + __radix_tree_delete(root, node, slot); > + } > +} > +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) > +{ > + struct radix_tree_root *root = &xb->xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned int nbits; > + > + for (; start < end; start = (start | (IDA_BIT...

...free pages in the 1st round. It is not concerned that the memory pages are used after they are given to the hypervisor as a hint of the free pages, because they will be tracked by the hypervisor and transferred in the next round if they are used and written. ChangeLog: v18->v19: 1) patch 3: - xb_clear_bit_range and xb_find_next_bit will deal with range [start, end), where end is changed to be exclusive of the range. - add overflow checks at the end of xb_clear_bit_range and xb_find_next_bit - add overflow related test cases 2) patch 4: - change back to the previous add_one_sg methond, which is b...

...free pages in the 1st round. It is not concerned that the memory pages are used after they are given to the hypervisor as a hint of the free pages, because they will be tracked by the hypervisor and transferred in the next round if they are used and written. ChangeLog: v18->v19: 1) patch 3: - xb_clear_bit_range and xb_find_next_bit will deal with range [start, end), where end is changed to be exclusive of the range. - add overflow checks at the end of xb_clear_bit_range and xb_find_next_bit - add overflow related test cases 2) patch 4: - change back to the previous add_one_sg methond, which is b...

...ap - DeveloperNotes: add an item to comment that the current bit range related APIs operating 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...

...ap - DeveloperNotes: add an item to comment that the current bit range related APIs operating 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...

...tree_delete(root, node, slot); + else + rcu_assign_pointer(*slot, (void *)tmp); + return; + } + + if (!bitmap) + return; + + __clear_bit(bit, bitmap->bitmap); + if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { + kfree(bitmap); + __radix_tree_delete(root, node, slot); + } +} + +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned int nbits; + + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { + unsigned long i...

On 12/15/2017 12:29 AM, Tetsuo Handa wrote: > Wei Wang wrote: >> I used the example of xb_clear_bit_range(), and xb_find_next_bit() is >> the same fundamentally. Please let me know if anywhere still looks fuzzy. > I don't think it is the same for xb_find_next_bit() with set == 0. > > + if (radix_tree_exception(bmap)) { > + unsigned long tmp = (unsigned long)bmap; > + unsig...

...t bit range > > related APIs operating 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_n...

...t bit range > > related APIs operating 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_n...