Multi-index entries, clarifying storage overhead with respect to range alignment

[Chris Goldsworthy]

Hi Matthew,

Consider the following excerpt from the Xarray documentation on multi-index
entries, summarizing the [2^N, 2^(N+1) - 1] alignment requirement for
utilizing multi-index entries [1]:

"The current implementation only allows tying ranges which are aligned powers of
two together; eg indices 64-127 may be tied together, but 2-6 may not be. This
may save substantial quantities of memory; for example tying 512 entries
together will save over 4kB."

Won't we still use multi-index entries for power-of-two ranges that are aligned
for the size of the range? That is, the range [i, j] satisfies:

	(A): j - i = 2^k for some k and i % 2^k == 0 .

This is more permissive than [2^N, 2^(N+1) - 1] . I'm basing this assumption
(calling it this as I'm not 100% certain yet) off of the following:

(1) Counting the number of kmem_cache_alloc_lru() calls using ranges satisfying (A)
whilst varying the starting position.

(2) Walking through xa_store_range(). The call to xas_set_range() [2] sets the
final xa_shift S that corresponds to the range we want to cover. When calling
xas_store() [3], inside of which is a call to xas_create() [4], the shift of the
lowest-level node [5] we allocate is no smaller than S - XA_CHUNK_SHIFT + 1,
i.e. the entry will still cover multiple entries so long as S is large enough
(though we still might need multiple entries to do this). This will happen
despite the alignment of things, based of what happens in xas_store_range(). Let
me know if I'm misinterpreting something.

Thanks,

Chris.

[1] https://docs.kernel.org/core-api/xarray.html#multi-index-entries
[2] https://elixir.bootlin.com/linux/latest/source/lib/xarray.c#L1740
[3] https://elixir.bootlin.com/linux/latest/source/lib/xarray.c#L1741
[4] https://elixir.bootlin.com/linux/latest/source/lib/xarray.c#L789
[5] https://elixir.bootlin.com/linux/latest/source/lib/xarray.c#L679