Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

From: Matthew Wilcox
Date: Sat Dec 23 2017 - 10:00:07 EST


On Sat, Dec 23, 2017 at 11:33:45PM +0900, Tetsuo Handa wrote:
> Matthew Wilcox wrote:
> > On Sat, Dec 23, 2017 at 11:59:54AM +0900, Tetsuo Handa wrote:
> > > Matthew Wilcox wrote:
> > > > + bit %= IDA_BITMAP_BITS;
> > > > + radix_tree_iter_init(&iter, index);
> > > > + slot = idr_get_free_cmn(root, &iter, GFP_NOWAIT | __GFP_NOWARN, index);
> > > > + if (IS_ERR(slot)) {
> > > > + if (slot == ERR_PTR(-ENOSPC))
> > > > + return 0; /* Already set */
> > >
> > > Why already set? I guess something is there, but is it guaranteed that
> > > there is a bitmap with the "bit" set?
> >
> > Yes. For radix trees tagged with IDR_RT_MARKER, newly created slots
> > have the IDR_FREE tag set. We only clear the IDR_FREE tag once the
> > bitmap is full. So if we try to find a free slot and the tag is clear,
> > we know the bitmap is full.
> >
>
> OK. But does using IDR_FREE tag have more benefit than cost?
> You are doing
>
> if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
> radix_tree_iter_tag_clear(root, &iter, IDR_FREE);
>
> for each xb_set_bit() call. How likely do we hit ERR_PTR(-ENOSPC) path?
> Isn't removing both bitmap_full() and ERR_PTR(-ENOSPC) better?

You're assuming that the purpose of using IDR_FREE is to save xb_set_bit
from walking the tree unnecessarily. It isn't; that's just a happy
side-effect. Its main purpose is to make xb_find_zero() efficient. If
we have large ranges of set bits, xb_find_zero() will be able to skip them.

> > This is just a lazy test. We "know" that the bits in the range 1024-2047
> > will all land in the same bitmap, so there's no need to preload for each
> > of them.
>
> Testcases also serves as how to use that API.
> Assuming such thing leads to incorrect usage.

Sure. Would you like to submit a patch?

> > > If bitmap == NULL at this_cpu_xchg(ida_bitmap, NULL) is allowed,
> > > you can use kzalloc(sizeof(*bitmap), GFP_NOWAIT | __GFP_NOWARN)
> > > and get rid of xb_preload()/xb_preload_end().
> >
> > No, we can't. GFP_NOWAIT | __GFP_NOWARN won't try very hard to allocate
> > memory. There's no reason to fail the call if the user is in a context
> > where they can try harder to free memory.
>
> But there is no reason to use GFP_NOWAIT at idr_get_free_cmn() if it is
> safe to use GFP_KERNEL. If we don't require xb_preload() which forces
> idr_get_free_cmn() to use GFP_NOWAIT due to possibility of preemption
> disabled by xb_preload(), we can allow passing gfp flags to xb_set_bit().

The assumption is that the user has done:

xb_preload(GFP_KERNEL);
spin_lock(my_lock);
xb_set_bit(xb, bit);
spin_unlock(my_lock);
xb_preload_end();

This is not the world's greatest interface. Once I have the XArray
finished, we'll be able to ditch the external spinlock and the preload
interface and be able to call:

xb_set_bit(xb, bit, GFP_KERNEL);

> > xb_preload also preloads radix tree nodes.
>
> But it after all forces idr_get_free_cmn() to use GFP_NOWAIT, doesn't it?

I think you don't understand how the radix tree allocates nodes. preloading
means that it will be able to access the nodes which were allocated earlier.

> Speak of initial user (i.e. virtio-balloon), xb_preload() won't be able to
> use GFP_KERNEL in order to avoid OOM lockup. Therefore, I don't see
> advantages with using xb_preload(). If xb_set_bit() receives gfp flags,
> the caller can pass GFP_KERNEL if it is safe to use GFP_KERNEL.

I haven't reviewed how virtio-balloon is using the interfaces.