On Thu, Jun 30, 2022 at 08:48:10AM -0700, Boris Burkov wrote:
> I was reading the XArray documentation and noticed a comment that there
> is potential support for searching by ANDs of multiple marks, but it was
> waiting for a use case. I think I might have such a use case, but I'm
> looking for some feedback on its validity.
>
> I'm working on some fragmentation issues in a space allocator in btrfs,
> so I'm attempting to categorize the allocation unit of this allocator
> (block group) by size class to help. I've got a branch where I migrated
> btrfs's storage of block groups from a linked list to an xarray, since
> marks felt like a really nice way for me to iterate by size class.
>
> e.g.:
> mark = get_size_class_mark(size);
> xa_for_each_marked(block_groups, index, block_group, mark) {
> // try to allocate in block_group
> }
>
> Further, this allocator already operates in passes, which try harder and
> harder to find a block_group, which also fits nicely, since eventually,
> I can make the mark XA_PRESENT.
>
> i.e.:
> while (pass < N) {
> mark = get_size_class_mark(size);
> if (pass > K)
> mark = XA_PRESENT;
> xa_for_each_marked(block_groups, index, block_group, mark) {
> // try to allocate in block_group
> }
> if (happy)
> break;
> pass++;
> }
>
> However, I do feel a bit short on marks! Currently, I use one for "not
> in any size class" which leaves just two size classes. Even a handful
> more would give me a lot of extra flexibility. So with that said, if I
> could use ANDs in the iteration to make it essentially 7 marks, that
> would be sweet. I don't yet see a strong need for ORs, in my case.
Unfortunately, I don't think doing this will work out really well for
you. The bits really are independent of each other, and the power of
the search marks lies in their ability to skip over vast swathes of
the array when they're not marked. But to do what you want, we'd end up
doing something like this:
leaf array 1:
entry 0 is in category 1
entry 1 is in category 2
entry 2 is in category 5
and now we have to set all three bits in the parent of leaf array 1,
so any search will have to traverse all of leaf array 1 in order to find
out whether there are any entries in the category we're looking for.
What you could do is keep one XArray per category. I think that's what
you're proposing below. It's a bit poor because each XArray has its
own lock, so to move a group from one size category to another, you have
to take two locks. On the other hand, that means that you can allocate
from two different size categories at the same time, so maybe that's a
good thing?
> Does this seem like a good enough justification to support finding by
> combination of marks? If not, my alternative, for what it's worth, is
> to have an array of my block group data structure indexed by size class.
> If you do think it's a good idea, I'm happy to help with implementing
> it or testing it, if that would be valuable.
>
> Thanks for your time,
> Boris
