On Tue, Nov 2, 2021 at 7:35 AM Jason Wang <jasow...@redhat.com> wrote:
>
>
> 在 2021/10/30 上午2:35, Eugenio Pérez 写道:
> > This iova tree function allows it to look for a hole in allocated
> > regions and return a totally new translation for a given translated
> > address.
> >
> > It's usage is mainly to allow devices to access qemu address space,
> > remapping guest's one into a new iova space where qemu can add chunks of
> > addresses.
> >
> > Signed-off-by: Eugenio Pérez <epere...@redhat.com>
> > ---
> > include/qemu/iova-tree.h | 17 +++++
> > util/iova-tree.c | 139 +++++++++++++++++++++++++++++++++++++++
> > 2 files changed, 156 insertions(+)
> >
> > diff --git a/include/qemu/iova-tree.h b/include/qemu/iova-tree.h
> > index 8249edd764..33f9b2e13f 100644
> > --- a/include/qemu/iova-tree.h
> > +++ b/include/qemu/iova-tree.h
> > @@ -29,6 +29,7 @@
> > #define IOVA_OK (0)
> > #define IOVA_ERR_INVALID (-1) /* Invalid parameters */
> > #define IOVA_ERR_OVERLAP (-2) /* IOVA range overlapped */
> > +#define IOVA_ERR_NOMEM (-3) /* Cannot allocate */
>
>
> I think we need a better name other than "NOMEM", since it's actually
> means there's no sufficient hole for the range?
>
Actually, yes. I'm totally fine with changing it, but "the
inspiration" is that ENOMEM is also the error that malloc sets in
errno if not enough contiguous VM can be allocated.
What would be a more descriptive name?
>
> >
> > typedef struct IOVATree IOVATree;
> > typedef struct DMAMap {
> > @@ -119,6 +120,22 @@ const DMAMap *iova_tree_find_address(const IOVATree
> > *tree, hwaddr iova);
> > */
> > void iova_tree_foreach(IOVATree *tree, iova_tree_iterator iterator);
> >
> > +/**
> > + * iova_tree_alloc:
> > + *
> > + * @tree: the iova tree to allocate from
> > + * @map: the new map (as translated addr & size) to allocate in iova region
> > + * @iova_begin: the minimum address of the allocation
> > + * @iova_end: the maximum addressable direction of the allocation
> > + *
> > + * Allocates a new region of a given size, between iova_min and iova_max.
> > + *
> > + * Return: Same as iova_tree_insert, but cannot overlap and can be out of
> > + * free contiguous range. Caller can get the assigned iova in map->iova.
> > + */
> > +int iova_tree_alloc(IOVATree *tree, DMAMap *map, hwaddr iova_begin,
> > + hwaddr iova_end);
> > +
>
>
> "iova_tree_alloc_map" seems better.
>
Right, I changed in vhost but I forgot to change here.
>
> > /**
> > * iova_tree_destroy:
> > *
> > diff --git a/util/iova-tree.c b/util/iova-tree.c
> > index 23ea35b7a4..27c921c4e2 100644
> > --- a/util/iova-tree.c
> > +++ b/util/iova-tree.c
> > @@ -16,6 +16,36 @@ struct IOVATree {
> > GTree *tree;
> > };
> >
> > +/* Args to pass to iova_tree_alloc foreach function. */
> > +struct IOVATreeAllocArgs {
> > + /* Size of the desired allocation */
> > + size_t new_size;
> > +
> > + /* The minimum address allowed in the allocation */
> > + hwaddr iova_begin;
> > +
> > + /* The last addressable allowed in the allocation */
> > + hwaddr iova_last;
> > +
> > + /* Previously-to-last iterated map, can be NULL in the first node */
> > + const DMAMap *hole_left;
> > +
> > + /* Last iterated map */
> > + const DMAMap *hole_right;
>
>
> Any reason we can move those to IOVATree structure, it can simplify a
> lot of things.
>
I can move for the next version for sure, but then it needs to be
clear enough that these fields are alloc arguments.
>
> > +};
> > +
> > +/**
> > + * Iterate args to tne next hole
s/tne/the/
> > + *
> > + * @args The alloc arguments
> > + * @next The next mapping in the tree. Can be NULL to signal the last one
> > + */
> > +static void iova_tree_alloc_args_iterate(struct IOVATreeAllocArgs *args,
> > + const DMAMap *next) {
> > + args->hole_left = args->hole_right;
> > + args->hole_right = next;
> > +}
> > +
> > static int iova_tree_compare(gconstpointer a, gconstpointer b, gpointer
> > data)
> > {
> > const DMAMap *m1 = a, *m2 = b;
> > @@ -107,6 +137,115 @@ int iova_tree_remove(IOVATree *tree, const DMAMap
> > *map)
> > return IOVA_OK;
> > }
> >
> > +/**
> > + * Try to accomodate a map of size ret->size in a hole between
> > + * max(end(hole_left), iova_start).
> > + *
> > + * @args Arguments to allocation
> > + */
> > +static bool iova_tree_alloc_map_in_hole(const struct IOVATreeAllocArgs
> > *args)
> > +{
> > + const DMAMap *left = args->hole_left, *right = args->hole_right;
> > + uint64_t hole_start, hole_last;
> > +
> > + if (right && right->iova + right->size < args->iova_begin) {
> > + return false;
> > + }
> > +
> > + if (left && left->iova > args->iova_last) {
> > + return false;
> > + }
> > +
> > + hole_start = MAX(left ? left->iova + left->size + 1 : 0,
> > args->iova_begin);
> > + hole_last = MIN(right ? right->iova : HWADDR_MAX, args->iova_last);
> > +
> > + if (hole_last - hole_start > args->new_size) {
> > + /* We found a valid hole. */
> > + return true;
> > + }
> > +
> > + /* Keep iterating */
> > + return false;
> > +}
> > +
> > +/**
> > + * Foreach dma node in the tree, compare if there is a hole wit its
> > previous
> > + * node (or minimum iova address allowed) and the node.
> > + *
> > + * @key Node iterating
> > + * @value Node iterating
> > + * @pargs Struct to communicate with the outside world
> > + *
> > + * Return: false to keep iterating, true if needs break.
> > + */
> > +static gboolean iova_tree_alloc_traverse(gpointer key, gpointer value,
> > + gpointer pargs)
> > +{
> > + struct IOVATreeAllocArgs *args = pargs;
> > + DMAMap *node = value;
> > +
> > + assert(key == value);
> > +
> > + iova_tree_alloc_args_iterate(args, node);
> > + if (args->hole_left && args->hole_left->iova > args->iova_last) {
> > + return true;
> > + }
> > +
> > + if (iova_tree_alloc_map_in_hole(args)) {
> > + return true;
> > + }
> > +
> > + return false;
> > +}
> > +
> > +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;
> > + }
> > +
> > + 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.
>
>
> To say the truth, the codes in iova_tree_alloc_traverse() is hard to be
> reviewed. I think it would be easy to use first/next/last. What we
> really need is to calculate the hole between two ranges with handmade
> first, last.
>
I totally agree on that, but we don't have first/next/last in GTree
until glib 2.68. Can we raise the minimum version required?
Another possibility that comes to my mind is to either have a list /
tree of free regions, or directly a custom allocator for this.
> Thanks
>
>
> > + *
> > + */
> > + 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);
> > +}
> > +
> > void iova_tree_destroy(IOVATree *tree)
> > {
> > g_tree_destroy(tree->tree);
>
