Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Thu, Jan 27, 2022 at 12:25 PM Peter Xu wrote:
>
> On Thu, Jan 27, 2022 at 11:09:44AM +0100, Eugenio Perez Martin wrote:
> > > > +/**
> > > > + * Try to accomodate a map of size ret->size in a hole between
> > > > + * max(end(hole_left), iova_start).
> > >
> > > I think this functions need the most comments, and above sentence is more
> > > or
> > > less not sounding correct... My try...
> > >
> > > /*
> > > * Try to find an unallocated IOVA range between LEFT and RIGHT elements.
> > > *
> > > * There're three cases:
> > > *
> > > * (1) When LEFT==NULL, RIGHT must be non-NULL and it means we're
> > > iterating at
> > > * the 1st element.
> > > *
> > > * (2) When RIGHT==NULL, LEFT must be non-NULL and it means we're
> > > iterating at
> > > * the last element.
> > > *
> > > * (3) When both LEFT and RIGHT are non-NULL, this is the most common
> > > case,
> > > * we'll try to find a hole between LEFT and RIGHT mapping.
> > > */
> > >
> >
> > This is also called with left == NULL and right == NULL in the first
> > allocation with an empty tree. This allows iova_tree_alloc to have the
> > same code path both if the three is empty or not.
> >
> > But I can add the use cases in the doc for sure.
>
> Ah, right.
>
> >
> > > > + *
> > > > + * @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);
> > >
> > > I assume these values should be always inclusive, hence
> > >
> > > s/right->iova/right->iova + 1/
> > >
> > > ?
> > >
> >
> > Right, it is confusing the way it's written. But I think it should be
> > right->iova - 1 in any case to make it the hole last element, isn't
> > it?
>
> I was thinking "-1" but I failed to make it coherent with the thought when
> typing.. Heh.
>
> >
> > Would it work better to rename variable hole_last to hole_end? If not,
> > we have a special case of the second allocation when iova_begin == 0:
> > - We successfully allocate a DMAMap of size N. By the way the
> > algorithm works, it starts at 0, so [0, N] is allocated.
>
> If we're always talking about inclusive ranges, shouldn't it be [0, N-1]?
>
I meant DMAMap size, which is already inclusive.
> > - We try to allocate a second one of size M. At the first iteration,
> > "right" is the previously allocated DMAMap.
> > Using the -1 trick we get hole_end == HWADDR_MAX.
>
> I'm not sure I get the point, but both naming look fine to me. As long as we
> use inclusive ranges, then hole_end/last will be limited to HWADDR_MAX.
>
Sorry, I think you were right from the beginning, because with _end we
cannot handle the case of right == NULL well. I'll rewrite with the
-1, taking into account the underflow.
Please let me know if you have more concerns or you come up with more
ideas to improve the patch.
Thanks!
> > > > +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) {
> > >
> > > IMHO this check is redundant and can be dropped, as it's already done in
> > > iova_tree_alloc_map_in_hole().
> > >
> >
> > Assuming we add "iova_found" to iova_tree_alloc_map_in_hole to
> > IOVATreeAllocArgs as you propose, it returns true if we are able to
> > allocate a DMAMap entry, so no more iterations are needed. But if it
> > returns false, it simply means that DMAMap cannot be allocated between
> > left (or iova_begin) and right (iova_end). It doesn't tell if you can
> > keep iterating or not. In other words, false == keep iterating if you
> > can.
> >
> > This other check signals the end of the available hole, and to avoid
> > iterating beyond iova_last in the (unlikely?) case we have more nodes
> > to iterate beyond that.
> >
> > I'll try to make it more explicit.
>
> Makes sense. Comment works.
>
> Thanks,
>
> --
> Peter Xu
>
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Thu, Jan 27, 2022 at 11:09:44AM +0100, Eugenio Perez Martin wrote:
> > > +/**
> > > + * Try to accomodate a map of size ret->size in a hole between
> > > + * max(end(hole_left), iova_start).
> >
> > I think this functions need the most comments, and above sentence is more or
> > less not sounding correct... My try...
> >
> > /*
> > * Try to find an unallocated IOVA range between LEFT and RIGHT elements.
> > *
> > * There're three cases:
> > *
> > * (1) When LEFT==NULL, RIGHT must be non-NULL and it means we're iterating
> > at
> > * the 1st element.
> > *
> > * (2) When RIGHT==NULL, LEFT must be non-NULL and it means we're iterating
> > at
> > * the last element.
> > *
> > * (3) When both LEFT and RIGHT are non-NULL, this is the most common case,
> > * we'll try to find a hole between LEFT and RIGHT mapping.
> > */
> >
>
> This is also called with left == NULL and right == NULL in the first
> allocation with an empty tree. This allows iova_tree_alloc to have the
> same code path both if the three is empty or not.
>
> But I can add the use cases in the doc for sure.
Ah, right.
>
> > > + *
> > > + * @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);
> >
> > I assume these values should be always inclusive, hence
> >
> > s/right->iova/right->iova + 1/
> >
> > ?
> >
>
> Right, it is confusing the way it's written. But I think it should be
> right->iova - 1 in any case to make it the hole last element, isn't
> it?
I was thinking "-1" but I failed to make it coherent with the thought when
typing.. Heh.
>
> Would it work better to rename variable hole_last to hole_end? If not,
> we have a special case of the second allocation when iova_begin == 0:
> - We successfully allocate a DMAMap of size N. By the way the
> algorithm works, it starts at 0, so [0, N] is allocated.
If we're always talking about inclusive ranges, shouldn't it be [0, N-1]?
> - We try to allocate a second one of size M. At the first iteration,
> "right" is the previously allocated DMAMap.
> Using the -1 trick we get hole_end == HWADDR_MAX.
I'm not sure I get the point, but both naming look fine to me. As long as we
use inclusive ranges, then hole_end/last will be limited to HWADDR_MAX.
> > > +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) {
> >
> > IMHO this check is redundant and can be dropped, as it's already done in
> > iova_tree_alloc_map_in_hole().
> >
>
> Assuming we add "iova_found" to iova_tree_alloc_map_in_hole to
> IOVATreeAllocArgs as you propose, it returns true if we are able to
> allocate a DMAMap entry, so no more iterations are needed. But if it
> returns false, it simply means that DMAMap cannot be allocated between
> left (or iova_begin) and right (iova_end). It doesn't tell if you can
> keep iterating or not. In other words, false == keep iterating if you
> can.
>
> This other check signals the end of the available hole, and to avoid
> iterating beyond iova_last in the (unlikely?) case we have more nodes
> to iterate beyond that.
>
> I'll try to make it more explicit.
Makes sense. Comment works.
Thanks,
--
Peter Xu
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Thu, Jan 27, 2022 at 9:57 AM Peter Xu wrote:
>
> On Fri, Oct 29, 2021 at 08:35:22PM +0200, Eugenio Pérez wrote:
> > 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
> > ---
> > 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 */
> >
> > 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_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;
>
> I slightly prefer having two more fields to cache the result:
>
>/* If found, we fill in the IOVA here */
>hwaddr iova_result;
>/* Whether have we found a valid IOVA */
>bool iova_found;
>
> IMHO they'll help on readability. More below.
>
Sure, this avoids an extra call.
> > +};
> > +
> > +/**
> > + * Iterate args to tne next hole
> > + *
> > + * @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).
>
> I think this functions need the most comments, and above sentence is more or
> less not sounding correct... My try...
>
> /*
> * Try to find an unallocated IOVA range between LEFT and RIGHT elements.
> *
> * There're three cases:
> *
> * (1) When LEFT==NULL, RIGHT must be non-NULL and it means we're iterating at
> * the 1st element.
> *
> * (2) When RIGHT==NULL, LEFT must be non-NULL and it means we're iterating at
> * the last element.
> *
> * (3) When both LEFT and RIGHT are non-NULL, this is the most common case,
> * we'll try to find a hole between LEFT and RIGHT mapping.
> */
>
This is also called with left == NULL and right == NULL in the first
allocation with an empty tree. This allows iova_tree_alloc to have the
same code path both if the three is empty or not.
But I can add the use cases in the doc for sure.
> > + *
> > + * @args Arguments to allocation
> > + */
> > +static bool iova_tree_alloc_map_in_hole(const struct IOVATreeAllocArgs
> > *args)
> > +{
> > +const DMAMap *left =
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Fri, Oct 29, 2021 at 08:35:22PM +0200, Eugenio Pérez wrote:
> 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
> ---
> 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 */
>
> 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_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;
I slightly prefer having two more fields to cache the result:
/* If found, we fill in the IOVA here */
hwaddr iova_result;
/* Whether have we found a valid IOVA */
bool iova_found;
IMHO they'll help on readability. More below.
> +};
> +
> +/**
> + * Iterate args to tne next hole
> + *
> + * @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).
I think this functions need the most comments, and above sentence is more or
less not sounding correct... My try...
/*
* Try to find an unallocated IOVA range between LEFT and RIGHT elements.
*
* There're three cases:
*
* (1) When LEFT==NULL, RIGHT must be non-NULL and it means we're iterating at
* the 1st element.
*
* (2) When RIGHT==NULL, LEFT must be non-NULL and it means we're iterating at
* the last element.
*
* (3) When both LEFT and RIGHT are non-NULL, this is the most common case,
* we'll try to find a hole between LEFT and RIGHT mapping.
*/
> + *
> + * @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);
I assume these values should be always inclusive, hence
s/right->iova/right->iova + 1/
?
> +
> +if (hole_last - hole_start > args->new_size) {
> +
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Tue, Nov 23, 2021 at 7:57 AM Peter Xu 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, );
> > +if (!iova_tree_alloc_map_in_hole()) {
> > +/*
> > + * 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(, NULL);
> > +if (!iova_tree_alloc_map_in_hole()) {
> > +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
>
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
Hi, Eugenio,
Sorry for the super late response.
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?
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..)
> +
> +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, );
> +if (!iova_tree_alloc_map_in_hole()) {
> +/*
> + * 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(, NULL);
> +if (!iova_tree_alloc_map_in_hole()) {
> +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.
Thanks,
--
Peter Xu
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Wed, Nov 3, 2021 at 4:10 AM Jason Wang wrote:
>
> On Tue, Nov 2, 2021 at 4:29 PM Eugenio Perez Martin
> wrote:
> >
> > On Tue, Nov 2, 2021 at 7:35 AM Jason Wang 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
> > > > ---
> > > > 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.
>
> Ok, then I think it's fine.
>
> >
> > 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.
>
> Sure.
>
> >
> > >
> > > > +};
> > > > +
> > > > +/**
> > > > + * 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
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Tue, Nov 2, 2021 at 4:29 PM Eugenio Perez Martin wrote:
>
> On Tue, Nov 2, 2021 at 7:35 AM Jason Wang 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
> > > ---
> > > 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.
Ok, then I think it's fine.
>
> 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.
Sure.
>
> >
> > > +};
> > > +
> > > +/**
> > > + * 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
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
On Tue, Nov 2, 2021 at 7:35 AM Jason Wang 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
> > ---
> > 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 -
Re: [RFC PATCH v5 23/26] util: Add iova_tree_alloc
在 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
---
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?
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.
/**
* 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.
+};
+
+/**
+ * Iterate args to tne next hole
+ *
+ * @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;
[RFC PATCH v5 23/26] util: Add iova_tree_alloc
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
---
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 */
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_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;
+};
+
+/**
+ * Iterate args to tne next hole
+ *
+ * @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
