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

[Peter Xu]

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,
> +                    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?

Thanks,

-- 
Peter Xu