Hi Ackerley,
On Wed, 19 Feb 2025 at 23:33, Ackerley Tng <ackerleytng@xxxxxxxxxx> wrote:
>
> Fuad Tabba <tabba@xxxxxxxxxx> writes:
>
> This question should not block merging of this series since performance
> can be improved in a separate series:
>
> > <snip>
> >
> > +
> > +/*
> > + * Marks the range [start, end) as mappable by both the host and the guest.
> > + * Usually called when guest shares memory with the host.
> > + */
> > +static int gmem_set_mappable(struct inode *inode, pgoff_t start, pgoff_t end)
> > +{
> > + struct xarray *mappable_offsets = &kvm_gmem_private(inode)->mappable_offsets;
> > + void *xval = xa_mk_value(KVM_GMEM_ALL_MAPPABLE);
> > + pgoff_t i;
> > + int r = 0;
> > +
> > + filemap_invalidate_lock(inode->i_mapping);
> > + for (i = start; i < end; i++) {
>
> Were any alternative data structures considered, or does anyone have
> suggestions for alternatives? Doing xa_store() in a loop here will take
> a long time for large ranges.
>
> I looked into the following:
>
> Option 1: (preferred) Maple trees
>
> Maple tree has a nice API, though it would be better if it can combine
> ranges that have the same value.
>
> I will have to dig into performance, but I'm assuming that even large
> ranges are stored in a few nodes so this would be faster than iterating
> over indices in an xarray.
>
> void explore_maple_tree(void)
> {
> DEFINE_MTREE(mt);
>
> mt_init_flags(&mt, MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU);
>
> mtree_store_range(&mt, 0, 16, xa_mk_value(0x20), GFP_KERNEL);
> mtree_store_range(&mt, 8, 24, xa_mk_value(0x32), GFP_KERNEL);
> mtree_store_range(&mt, 5, 10, xa_mk_value(0x32), GFP_KERNEL);
>
> {
> void *entry;
> MA_STATE(mas, &mt, 0, 0);
>
> mas_for_each(&mas, entry, ULONG_MAX) {
> pr_err("[%ld, %ld]: 0x%lx\n", mas.index, mas.last, xa_to_value(entry));
> }
> }
>
> mtree_destroy(&mt);
> }
>
> stdout:
>
> [0, 4]: 0x20
> [5, 10]: 0x32
> [11, 24]: 0x32
>
> Option 2: Multi-index xarray
>
> The API is more complex than maple tree's, and IIUC multi-index xarrays
> are not generalizable to any range, so the range can't be 8 1G pages + 1
> 4K page for example. The size of the range has to be a power of 2 that
> is greater than 4K.
>
> Using multi-index xarrays would mean computing order to store
> multi-index entries. This can be computed from the size of the range to
> be added, but is an additional source of errors.
>
> Option 3: Interval tree, which is built on top of red-black trees
>
> The API is set up at a lower level. A macro is used to define interval
> trees, the user has to deal with nodes in the tree directly and
> separately define functions to override sub-ranges in larger ranges.
I didn't consider any other data structures, mainly out of laziness :)
What I mean by that is, xarrays is what is already used in guest_memfd
for tracking other gfn related items, even though many have talked
about in the future replacing it with something else.
I agree with you that it's not the ideal data structure, but also,
like you said, this isn't part of the interface, and it would be easy
to replace in the future. As you mention, one of the challenges is
figuring out the performance impact in practice, and once things have
settled down and the interface is more or less settled, some
benchmarking would be useful to guide us here.
Thanks!
/fuad
> > + r = xa_err(xa_store(mappable_offsets, i, xval, GFP_KERNEL));
> > + if (r)
> > + break;
> > + }
> > + filemap_invalidate_unlock(inode->i_mapping);
> > +
> > + return r;
> > +}
> > +
> > +/*
> > + * Marks the range [start, end) as not mappable by the host. If the host doesn't
> > + * have any references to a particular folio, then that folio is marked as
> > + * mappable by the guest.
> > + *
> > + * However, if the host still has references to the folio, then the folio is
> > + * marked and not mappable by anyone. Marking it is not mappable allows it to
> > + * drain all references from the host, and to ensure that the hypervisor does
> > + * not transition the folio to private, since the host still might access it.
> > + *
> > + * Usually called when guest unshares memory with the host.
> > + */
> > +static int gmem_clear_mappable(struct inode *inode, pgoff_t start, pgoff_t end)
> > +{
> > + struct xarray *mappable_offsets = &kvm_gmem_private(inode)->mappable_offsets;
> > + void *xval_guest = xa_mk_value(KVM_GMEM_GUEST_MAPPABLE);
> > + void *xval_none = xa_mk_value(KVM_GMEM_NONE_MAPPABLE);
> > + pgoff_t i;
> > + int r = 0;
> > +
> > + filemap_invalidate_lock(inode->i_mapping);
> > + for (i = start; i < end; i++) {
> > + struct folio *folio;
> > + int refcount = 0;
> > +
> > + folio = filemap_lock_folio(inode->i_mapping, i);
> > + if (!IS_ERR(folio)) {
> > + refcount = folio_ref_count(folio);
> > + } else {
> > + r = PTR_ERR(folio);
> > + if (WARN_ON_ONCE(r != -ENOENT))
> > + break;
> > +
> > + folio = NULL;
> > + }
> > +
> > + /* +1 references are expected because of filemap_lock_folio(). */
> > + if (folio && refcount > folio_nr_pages(folio) + 1) {
> > + /*
> > + * Outstanding references, the folio cannot be faulted
> > + * in by anyone until they're dropped.
> > + */
> > + r = xa_err(xa_store(mappable_offsets, i, xval_none, GFP_KERNEL));
> > + } else {
> > + /*
> > + * No outstanding references. Transition the folio to
> > + * guest mappable immediately.
> > + */
> > + r = xa_err(xa_store(mappable_offsets, i, xval_guest, GFP_KERNEL));
> > + }
> > +
> > + if (folio) {
> > + folio_unlock(folio);
> > + folio_put(folio);
> > + }
> > +
> > + if (WARN_ON_ONCE(r))
> > + break;
> > + }
> > + filemap_invalidate_unlock(inode->i_mapping);
> > +
> > + return r;
> > +}
> > +
> >
> > <snip>
