Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc

[Eugenio Perez Martin]

On Tue, Nov 23, 2021 at 7:57 AM Peter Xu <peterx@redhat.com> wrote:
>
> Hi, Eugenio,
>
> Sorry for the super late response.
>

No problem!

> On Fri, Oct 29, 2021 at 08:35:22PM +0200, Eugenio Pérez wrote:
>
> [...]
>
> > +int iova_tree_alloc(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
> > +                    hwaddr iova_last)
> > +{
> > +    struct IOVATreeAllocArgs args = {
> > +        .new_size = map->size,
> > +        .iova_begin = iova_begin,
> > +        .iova_last = iova_last,
> > +    };
> > +
> > +    if (iova_begin == 0) {
> > +        /* Some devices does not like addr 0 */
> > +        iova_begin += qemu_real_host_page_size;
> > +    }
>
> Any explanation of why zero is not welcomed?
>

I didn't investigate too much, but neither vhost-net or qemu device
accepted a ring with address 0. Probably it's because some test like:

if (!vq->desc) { return; }

That assumes 0 == not initialized. Even if we fix that issue in the
devices, the vdpa device backend could be an old version, and since
the iova range should be big anyway I think we should skip 0 anyway.

> It would be great if we can move this out of iova-tree.c, because that doesn't
> look like a good place to, e.g. reference qemu_real_host_page_size, anyways.
> The caller can simply pass in qemu_real_host_page_size as iova_begin when
> needed (and I highly doubt it'll be a must for all iova-tree users..)
>

I think yes, it can be included in iova_begin. I'll rework that part.

> > +
> > +    assert(iova_begin < iova_last);
> > +
> > +    /*
> > +     * Find a valid hole for the mapping
> > +     *
> > +     * Assuming low iova_begin, so no need to do a binary search to
> > +     * locate the first node.
> > +     *
> > +     * TODO: We can improve the search speed if we save the beginning and 
> > the
> > +     * end of holes, so we don't iterate over the previous saved ones.
> > +     *
> > +     * TODO: Replace all this with g_tree_node_first/next/last when 
> > available
> > +     * (from glib since 2.68). To do it with g_tree_foreach complicates the
> > +     * code a lot.
> > +     *
> > +     */
> > +    g_tree_foreach(tree->tree, iova_tree_alloc_traverse, &args);
> > +    if (!iova_tree_alloc_map_in_hole(&args)) {
> > +        /*
> > +         * 2nd try: Last iteration left args->right as the last DMAMap. But
> > +         * (right, end) hole needs to be checked too
> > +         */
> > +        iova_tree_alloc_args_iterate(&args, NULL);
> > +        if (!iova_tree_alloc_map_in_hole(&args)) {
> > +            return IOVA_ERR_NOMEM;
> > +        }
> > +    }
> > +
> > +    map->iova = MAX(iova_begin,
> > +                    args.hole_left ?
> > +                    args.hole_left->iova + args.hole_left->size + 1 : 0);
> > +    return iova_tree_insert(tree, map);
> > +}
>
> Re the algorithm - I totally agree Jason's version is much better.
>

I'll try to accommodate it, but (if I understood it correctly) it
needs to deal with deallocation and a few other things. But it should
be doable.

Thanks!

> Thanks,
>
> --
> Peter Xu
>