| Message ID | 1503914913-28893-3-git-send-email-wei.w.wang@intel.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Mon, Aug 28, 2017 at 06:08:30PM +0800, Wei Wang wrote: > +/** > + * xb_zero - zero a range of bits in the xbitmap > + * @xb: the xbitmap that the bits reside in > + * @start: the start of the range, inclusive > + * @end: the end of the range, inclusive > + */ > +void xb_zero(struct xb *xb, unsigned long start, unsigned long end) > +{ > + unsigned long i; > + > + for (i = start; i <= end; i++) > + xb_clear_bit(xb, i); > +} > +EXPORT_SYMBOL(xb_zero); Um. This is not exactly going to be quick if you're clearing a range of bits. I think it needs to be more along the lines of this: void xb_clear(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; for (; end < start; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { unsigned long index = start / IDA_BITMAP_BITS; unsigned long bit = start % IDA_BITMAP_BITS; bitmap = __radix_tree_lookup(root, index, &node, &slot); if (radix_tree_exception(bitmap)) { unsigned long ebit = bit + 2; unsigned long tmp = (unsigned long)bitmap; if (ebit >= BITS_PER_LONG) continue; tmp &= ... something ...; if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY) __radix_tree_delete(root, node, slot); else rcu_assign_pointer(*slot, (void *)tmp); } else if (bitmap) { unsigned int nbits = end - start + 1; if (nbits + bit > IDA_BITMAP_BITS) nbits = IDA_BITMAP_BITS - bit; bitmap_clear(bitmap->bitmap, bit, nbits); if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { kfree(bitmap); __radix_tree_delete(root, node, slot); } } } } Also note that this should be called xb_clear(), not xb_zero() to fit in with bitmap_clear(). And this needs a thorough test suite testing all values for 'start' and 'end' between 0 and at least 1024; probably much higher. And a variable number of bits need to be set before calling xb_clear() in the test suite. Also, this implementation above is missing a few tricks. For example, if 'bit' is 0 and 'nbits' == IDA_BITMAP_BITS, we can simply call kfree without first zeroing out the bits and then checking if the whole thing is zero. Another missing optimisation above is that we always restart the radix tree walk from the top instead of simply moving on to the next bitmap. This is still a thousand times faster than the implementation you posted, but I'd be keen to add that optimisation too. > +/** > + * xb_find_next_bit - find next 1 or 0 in the give range of bits > + * @xb: the xbitmap that the bits reside in > + * @start: the start of the range, inclusive > + * @end: the end of the range, inclusive > + * @set: the polarity (1 or 0) of the next bit to find > + * > + * Return the index of the found bit in the xbitmap. If the returned index > + * exceeds @end, it indicates that no such bit is found in the given range. > + */ > +unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, > + unsigned long end, bool set) > +{ > + unsigned long i; > + > + for (i = start; i <= end; i++) { > + if (xb_test_bit(xb, i) == set) > + break; > + } > + > + return i; > +} > +EXPORT_SYMBOL(xb_find_next_bit); Similar comments ... this is going to be very slow. You can use the tags in the tree to help you find set and clear bits so performance doesn't fall apart in big trees. I'd like to see this be two functions, xb_find_next_zero_bit() and xb_find_next_set_bit().
On Monday, September 11, 2017 9:27 PM, Matthew Wilcox wrote > On Mon, Aug 28, 2017 at 06:08:30PM +0800, Wei Wang wrote: > > +/** > > + * xb_zero - zero a range of bits in the xbitmap > > + * @xb: the xbitmap that the bits reside in > > + * @start: the start of the range, inclusive > > + * @end: the end of the range, inclusive */ void xb_zero(struct xb > > +*xb, unsigned long start, unsigned long end) { > > + unsigned long i; > > + > > + for (i = start; i <= end; i++) > > + xb_clear_bit(xb, i); > > +} > > +EXPORT_SYMBOL(xb_zero); > > Um. This is not exactly going to be quick if you're clearing a range of bits. > I think it needs to be more along the lines of this: > > void xb_clear(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; > > for (; end < start; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { > unsigned long index = start / IDA_BITMAP_BITS; > unsigned long bit = start % IDA_BITMAP_BITS; > > bitmap = __radix_tree_lookup(root, index, &node, &slot); > if (radix_tree_exception(bitmap)) { > unsigned long ebit = bit + 2; > unsigned long tmp = (unsigned long)bitmap; > if (ebit >= BITS_PER_LONG) > continue; > tmp &= ... something ...; > if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY) > __radix_tree_delete(root, node, slot); > else > rcu_assign_pointer(*slot, (void *)tmp); > } else if (bitmap) { > unsigned int nbits = end - start + 1; > if (nbits + bit > IDA_BITMAP_BITS) > nbits = IDA_BITMAP_BITS - bit; > bitmap_clear(bitmap->bitmap, bit, nbits); > if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { > kfree(bitmap); > __radix_tree_delete(root, node, slot); > } > } > } > } > > Also note that this should be called xb_clear(), not xb_zero() to fit in with > bitmap_clear(). And this needs a thorough test suite testing all values for 'start' > and 'end' between 0 and at least 1024; probably much higher. And a variable > number of bits need to be set before calling > xb_clear() in the test suite. > > Also, this implementation above is missing a few tricks. For example, if 'bit' is 0 > and 'nbits' == IDA_BITMAP_BITS, we can simply call kfree without first zeroing > out the bits and then checking if the whole thing is zero. Thanks for the optimization suggestions. We've seen significant improvement of the ballooning time. Some other optimizations (stated in the changelog) haven't been included in the new version. If possible, we can leave that to a second step optimization outside this patch series. Best, Wei
diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index 25b05ff..0061f7a 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -38,6 +38,9 @@ static inline void xb_init(struct xb *xb) int xb_set_bit(struct xb *xb, unsigned long bit); bool xb_test_bit(struct xb *xb, unsigned long bit); void xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_zero(struct xb *xb, unsigned long start, unsigned long end); +unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set); /* Check if the xb tree is empty */ static inline bool xb_is_empty(const struct xb *xb) diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 8c55296..b9e2a0c 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -174,3 +174,42 @@ void xb_preload(gfp_t gfp) } } EXPORT_SYMBOL(xb_preload); + +/** + * xb_zero - zero a range of bits in the xbitmap + * @xb: the xbitmap that the bits reside in + * @start: the start of the range, inclusive + * @end: the end of the range, inclusive + */ +void xb_zero(struct xb *xb, unsigned long start, unsigned long end) +{ + unsigned long i; + + for (i = start; i <= end; i++) + xb_clear_bit(xb, i); +} +EXPORT_SYMBOL(xb_zero); + +/** + * xb_find_next_bit - find next 1 or 0 in the give range of bits + * @xb: the xbitmap that the bits reside in + * @start: the start of the range, inclusive + * @end: the end of the range, inclusive + * @set: the polarity (1 or 0) of the next bit to find + * + * Return the index of the found bit in the xbitmap. If the returned index + * exceeds @end, it indicates that no such bit is found in the given range. + */ +unsigned long xb_find_next_bit(struct xb *xb, unsigned long start, + unsigned long end, bool set) +{ + unsigned long i; + + for (i = start; i <= end; i++) { + if (xb_test_bit(xb, i) == set) + break; + } + + return i; +} +EXPORT_SYMBOL(xb_find_next_bit);
xb_find_next_bit() is used to find the next "1" or "0" bit in the given range. xb_zero() is used to zero the given range of bits. Signed-off-by: Wei Wang <wei.w.wang@intel.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Matthew Wilcox <mawilcox@microsoft.com> Cc: Michal Hocko <mhocko@kernel.org> Cc: Michael S. Tsirkin <mst@redhat.com> --- include/linux/xbitmap.h | 3 +++ lib/xbitmap.c | 39 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 42 insertions(+)