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

[Peter Xu]

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.

> 
> 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.

-- 
Peter Xu