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

[Jason Wang]

在 2022/1/24 下午5:20, Eugenio Perez Martin 写道:
> 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?


Yes, the pseudo-code I past is just to show the idea of using 
g_tree_foreach() instead of introducing new auxiliary data structures. 
That will simplify both the codes and the reviewers.

Down the road, we may start from an iova range specified during the 
creation of the iova tree. E.g for vtd, it's the GAW, for vhost-vdpa, 
it's the one that we get from VHOST_VDPA_GET_IOVA_RANGE.

Thanks


> 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.
>
> 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?
>
> Thanks!
>
> > Thanks,
> > --
> > Peter Xu