Re: [PATCH v18 05/10] xbitmap: add more operations
From: Tetsuo Handa
Date: Sat Dec 02 2017 - 20:44:44 EST
Matthew Wilcox wrote:
> On Thu, Nov 30, 2017 at 10:35:03PM +0900, Tetsuo Handa wrote:
> > According to xb_set_bit(), it seems to me that we are trying to avoid memory allocation
> > for "struct ida_bitmap" when all set bits within a 1024-bits bitmap reside in the first
> > 61 bits.
> >
> > But does such saving help? Is there characteristic bias that majority of set bits resides
> > in the first 61 bits, for "bit" is "unsigned long" which holds a page number (isn't it)?
> > If no such bias, wouldn't eliminating radix_tree_exception() case and always storing
> > "struct ida_bitmap" simplifies the code (and make the processing faster)?
>
> It happens all the time. The vast majority of users of the IDA set
> low bits. Also, it's the first 62 bits -- going up to 63 bits with the
> XArray rewrite.
Oops, 0...61 is 62 bits.
What I meant is below (untested) patch. If correct, it can save lines and make
the code easier to read.
lib/radix-tree.c | 20 +------------
lib/xbitmap.c | 88 +++++---------------------------------------------------
2 files changed, 8 insertions(+), 100 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index a039588..fb84b91 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -2152,25 +2152,7 @@ int ida_pre_get(struct ida *ida, gfp_t gfp)
*/
__must_check bool xb_preload(gfp_t gfp)
{
- if (!this_cpu_read(ida_bitmap)) {
- struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp);
-
- if (!bitmap)
- return false;
- /*
- * The per-CPU variable is updated with preemption enabled.
- * If the calling task is unlucky to be scheduled to another
- * CPU which has no ida_bitmap allocation, it will be detected
- * when setting a bit (i.e. __xb_set_bit()).
- */
- bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap);
- kfree(bitmap);
- }
-
- if (__radix_tree_preload(gfp, XB_PRELOAD_SIZE) < 0)
- return false;
-
- return true;
+ return __radix_tree_preload(gfp, XB_PRELOAD_SIZE) == 0;
}
EXPORT_SYMBOL(xb_preload);
diff --git a/lib/xbitmap.c b/lib/xbitmap.c
index 816dd3e..426d168 100644
--- a/lib/xbitmap.c
+++ b/lib/xbitmap.c
@@ -18,7 +18,7 @@
* This function is used to set a bit in the xbitmap. If the bitmap that @bit
* resides in is not there, the per-cpu ida_bitmap will be taken.
*
- * Returns: 0 on success. %-EAGAIN indicates that @bit was not set.
+ * Returns: 0 on success. Negative value on failure.
*/
int xb_set_bit(struct xb *xb, unsigned long bit)
{
@@ -28,46 +28,19 @@ int xb_set_bit(struct xb *xb, unsigned long bit)
struct radix_tree_node *node;
void **slot;
struct ida_bitmap *bitmap;
- unsigned long ebit;
bit %= IDA_BITMAP_BITS;
- ebit = bit + 2;
err = __radix_tree_create(root, index, 0, &node, &slot);
if (err)
return err;
bitmap = rcu_dereference_raw(*slot);
- if (radix_tree_exception(bitmap)) {
- unsigned long tmp = (unsigned long)bitmap;
-
- if (ebit < BITS_PER_LONG) {
- tmp |= 1UL << ebit;
- rcu_assign_pointer(*slot, (void *)tmp);
- return 0;
- }
- bitmap = this_cpu_xchg(ida_bitmap, NULL);
- if (!bitmap) {
- __radix_tree_delete(root, node, slot);
- return -EAGAIN;
- }
- memset(bitmap, 0, sizeof(*bitmap));
- bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT;
- rcu_assign_pointer(*slot, bitmap);
- }
-
if (!bitmap) {
- if (ebit < BITS_PER_LONG) {
- bitmap = (void *)((1UL << ebit) |
- RADIX_TREE_EXCEPTIONAL_ENTRY);
- __radix_tree_replace(root, node, slot, bitmap, NULL);
- return 0;
- }
- bitmap = this_cpu_xchg(ida_bitmap, NULL);
+ bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT | __GFP_NOWARN);
if (!bitmap) {
__radix_tree_delete(root, node, slot);
- return -EAGAIN;
+ return -ENOMEM;
}
- memset(bitmap, 0, sizeof(*bitmap));
__radix_tree_replace(root, node, slot, bitmap, NULL);
}
@@ -82,7 +55,7 @@ int xb_set_bit(struct xb *xb, unsigned long bit)
* @bit: index of the bit to set
*
* A wrapper of the xb_preload() and xb_set_bit().
- * Returns: 0 on success; -EAGAIN or -ENOMEM on error.
+ * Returns: 0 on success; -ENOMEM on error.
*/
int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp)
{
@@ -113,25 +86,10 @@ void xb_clear_bit(struct xb *xb, unsigned long bit)
struct radix_tree_node *node;
void **slot;
struct ida_bitmap *bitmap;
- unsigned long ebit;
bit %= IDA_BITMAP_BITS;
- ebit = bit + 2;
bitmap = __radix_tree_lookup(root, index, &node, &slot);
- if (radix_tree_exception(bitmap)) {
- unsigned long tmp = (unsigned long)bitmap;
-
- if (ebit >= BITS_PER_LONG)
- return;
- tmp &= ~(1UL << ebit);
- if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY)
- __radix_tree_delete(root, node, slot);
- else
- rcu_assign_pointer(*slot, (void *)tmp);
- return;
- }
-
if (!bitmap)
return;
@@ -164,20 +122,7 @@ void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end)
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;
-
- nbits = min(end - start + 1, BITS_PER_LONG - ebit);
-
- if (ebit >= BITS_PER_LONG)
- continue;
- bitmap_clear(&tmp, ebit, nbits);
- if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY)
- __radix_tree_delete(root, node, slot);
- else
- rcu_assign_pointer(*slot, (void *)tmp);
- } else if (bitmap) {
+ if (bitmap) {
nbits = min(end - start + 1, IDA_BITMAP_BITS - bit);
if (nbits != IDA_BITMAP_BITS)
@@ -212,12 +157,6 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit)
if (!bitmap)
return false;
- if (radix_tree_exception(bitmap)) {
- bit += RADIX_TREE_EXCEPTIONAL_SHIFT;
- if (bit >= BITS_PER_LONG)
- return false;
- return (unsigned long)bitmap & (1UL << bit);
- }
return test_bit(bit, bitmap->bitmap);
}
EXPORT_SYMBOL(xb_test_bit);
@@ -236,20 +175,7 @@ static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start,
unsigned long bit = start % IDA_BITMAP_BITS;
bmap = __radix_tree_lookup(root, index, &node, &slot);
- if (radix_tree_exception(bmap)) {
- unsigned long tmp = (unsigned long)bmap;
- unsigned long ebit = bit + 2;
-
- if (ebit >= BITS_PER_LONG)
- continue;
- if (set)
- ret = find_next_bit(&tmp, BITS_PER_LONG, ebit);
- else
- ret = find_next_zero_bit(&tmp, BITS_PER_LONG,
- ebit);
- if (ret < BITS_PER_LONG)
- return ret - 2 + IDA_BITMAP_BITS * index;
- } else if (bmap) {
+ if (bmap) {
if (set)
ret = find_next_bit(bmap->bitmap,
IDA_BITMAP_BITS, bit);
@@ -258,7 +184,7 @@ static unsigned long xb_find_next_bit(struct xb *xb, unsigned long start,
IDA_BITMAP_BITS, bit);
if (ret < IDA_BITMAP_BITS)
return ret + index * IDA_BITMAP_BITS;
- } else if (!bmap && !set) {
+ } else if (!set) {
return start;
}
}
--