Re: [PATCH 21/31] util: Add iova_tree_alloc

[Eugenio Perez Martin <eperezma@redhat.com>]

On Mon, Jan 24, 2022 at 12:08 PM Peter Xu <peterx@redhat.com> wrote:
>
> On Mon, Jan 24, 2022 at 10:20:55AM +0100, Eugenio Perez Martin wrote:
> > On Mon, Jan 24, 2022 at 5:33 AM Peter Xu <peterx@redhat.com> wrote:
> > >
> > > On Fri, Jan 21, 2022 at 09:27:23PM +0100, Eugenio Pérez wrote:
> > > > +int iova_tree_alloc(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
> >
> > I forgot to s/iova_tree_alloc/iova_tree_alloc_map/ here.
> >
> > > > +                    hwaddr iova_last)
> > > > +{
> > > > +    const DMAMapInternal *last, *i;
> > > > +
> > > > +    assert(iova_begin < iova_last);
> > > > +
> > > > +    /*
> > > > +     * Find a valid hole for the mapping
> > > > +     *
> > > > +     * TODO: Replace all this with g_tree_node_first/next/last when available
> > > > +     * (from glib since 2.68). Using a sepparated QTAILQ complicates code.
> > > > +     *
> > > > +     * Try to allocate first at the end of the list.
> > > > +     */
> > > > +    last = QTAILQ_LAST(&tree->list);
> > > > +    if (iova_tree_alloc_map_in_hole(last, NULL, iova_begin, iova_last,
> > > > +                                    map->size)) {
> > > > +        goto alloc;
> > > > +    }
> > > > +
> > > > +    /* Look for inner hole */
> > > > +    last = NULL;
> > > > +    for (i = QTAILQ_FIRST(&tree->list); i;
> > > > +         last = i, i = QTAILQ_NEXT(i, entry)) {
> > > > +        if (iova_tree_alloc_map_in_hole(last, i, iova_begin, iova_last,
> > > > +                                        map->size)) {
> > > > +            goto alloc;
> > > > +        }
> > > > +    }
> > > > +
> > > > +    return IOVA_ERR_NOMEM;
> > > > +
> > > > +alloc:
> > > > +    map->iova = last ? last->map.iova + last->map.size + 1 : iova_begin;
> > > > +    return iova_tree_insert(tree, map);
> > > > +}
> > >
> > > Hi, Eugenio,
> > >
> > > Have you tried with what Jason suggested previously?
> > >
> > >   https://lore.kernel.org/qemu-devel/CACGkMEtZAPd9xQTP_R4w296N_Qz7VuV1FLnb544fEVoYO0of+g@mail.gmail.com/
> > >
> > > That solution still sounds very sensible to me even without the newly
> > > introduced list in previous two patches.
> > >
> > > IMHO we could move "DMAMap *previous, *this" into the IOVATreeAllocArgs*
> > > stucture that was passed into the traverse func though, so it'll naturally work
> > > with threading.
> > >
> > > Or is there any blocker for it?
> > >
> >
> > Hi Peter,
> >
> > I can try that solution again, but the main problem was the special
> > cases of the beginning and ending.
> >
> > For the function to locate a hole, DMAMap first = {.iova = 0, .size =
> > 0} means that it cannot account 0 for the hole.
> >
> > In other words, with that algorithm, if the only valid hole is [0, N)
> > and we try to allocate a block of size N, it would fail.
> >
> > Same happens with iova_end, although in practice it seems that IOMMU
> > hardware iova upper limit is never UINT64_MAX.
> >
> > Maybe we could treat .size = 0 as a special case? I see cleaner either
> > to build the list (but insert needs to take the list into account) or
> > to explicitly tell that prev == NULL means to use iova_first.
>
> Sounds good to me.  I didn't mean to copy-paste Jason's code, but IMHO what
> Jason wanted to show is the general concept - IOW, the fundamental idea (to me)
> is that the tree will be traversed in order, hence maintaining another list
> structure is redundant.
>

I agree.

My idea with this version was to easily delete all the custom code
once we have GTree with proper first/next/last, or _node functions.
That's why it's simply reimplementing GTree functions in the current
Glib version. I find old code way too complicated, and this one easier
to handle although way more verbose, but let's see if we can improve
the old one.

> >
> > Another solution that comes to my mind: to add both exceptions outside
> > of transverse function, and skip the first iteration with something
> > like:
> >
> > if (prev == NULL) {
> >   prev = this;
> >   return false /* continue */
> > }
> >
> > So the transverse callback has way less code paths. Would it work for
> > you if I send a separate RFC from SVQ only to validate this?
>
> Sure. :-)
>
> If you want, imho you can also attach the patch when reply, then the discussion
> context won't be lost too.
>

Sure,

So I think that the first step to remove complexity from the old one
is to remove iova_begin and iova_end.

As Jason points out, removing iova_end is easier. It has the drawback
of having to traverse all the list beyond iova_end, but a well formed
iova tree should contain none. If the guest can manipulate it, it's
only hurting itself adding nodes to it.

It's possible to extract the check for hole_right (or this in Jason's
proposal) as a special case too.

But removing the iova_begin parameter is more complicated. We cannot
know if it's a valid hole without knowing iova_begin, and we cannot
resume traversing. Could we assume iova_begin will always be 0? I
think not, the vdpa device can return anything through syscall.

Thanks!



> --
> Peter Xu
>