On Mon, Jan 24, 2022 at 5:33 AM Peter Xu <pet...@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_qz7vuv1flnb544fevoyo0o...@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.
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
>
