XArray multiple marks support

[Boris Burkov <boris@bur.io>]

Hi Matthew,

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.

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