Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

[Matthew Wilcox]

On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote:
> My understanding is that virtio-balloon wants to handle sparsely spreaded
> unsigned long values (which is PATCH 4/7) and wants to find all chunks of
> consecutive "1" bits efficiently. Therefore, I guess that holding the values
> in ascending order at store time is faster than sorting the values at read
> time. I don't know how to use radix tree API, but I think that B+ tree API
> suits for holding the values in ascending order.
> 
> We wait for Wei to post radix tree version combined into one patch and then
> compare performance between radix tree version and B+ tree version (shown
> below)?

Sure.  We all benefit from some friendly competition.  Even if a
competition between trees might remind one of the Entmoot ;-)

But let's not hold back -- let's figure out some good workloads to use
in our competition.  And we should also decide on the API / locking
constraints.  And of course we should compete based on not just speed,
but also memory consumption (both as a runtime overhead for a given set
of bits and as code size).  If you can replace the IDR, you get to count
that savings against the cost of your implementation.

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.

void xbit_init(struct xbitmap *xb);
int xbit_alloc(struct xbitmap *, unsigned long bit, gfp_t);
int xbit_alloc_range(struct xbitmap *, unsigned long start,
                        unsigned long nbits, gfp_t);
int xbit_set(struct xbitmap *, unsigned long bit, gfp_t);
bool xbit_test(struct xbitmap *, unsigned long bit);
int xbit_clear(struct xbitmap *, unsigned long bit);
int xbit_zero(struct xbitmap *, unsigned long start, unsigned long nbits);
int xbit_fill(struct xbitmap *, unsigned long start, unsigned long nbits,
                        gfp_t);
unsigned long xbit_find_clear(struct xbitmap *, unsigned long start,
                        unsigned long max);
unsigned long xbit_find_set(struct xbitmap *, unsigned long start,
                        unsigned long max);

> static bool set_ulong(struct ulong_list_head *head, const unsigned long value)
> {
>       if (!ptr) {
>               ptr = kzalloc(sizeof(*ptr), GFP_NOWAIT | __GFP_NOWARN);
>               if (!ptr)
>                       goto out1;
>               ptr->bitmap = kzalloc(BITMAP_LEN / 8,
>                                     GFP_NOWAIT | __GFP_NOWARN);
>               if (!ptr->bitmap)
>                       goto out2;
>               if (btree_insertl(&head->btree, ~segment, ptr,
>                                  GFP_NOWAIT | __GFP_NOWARN))
>                       goto out3;
> out3:
>       kfree(ptr->bitmap);
> out2:
>       kfree(ptr);
> out1:
>       return false;
> }

And what is the user supposed to do if this returns false?  How do they
make headway?  The xb_ API is clear -- you call xb_prealloc and that
ensures forward progress.