On Mon, Jan 24, 2022 at 10:20:55AM +0100, Eugenio Perez Martin wrote:
> On Mon, Jan 24, 2022 at 5:33 AM Peter Xu <peterx@xxxxxxxxxx> 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_Qz7VuV1FLnb544fEVoYO0of+g@xxxxxxxxxxxxxx/
> >
> > 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.
Sounds good to me. I didn't mean to copy-paste Jason's code, but IMHO what
Jason wanted to show is the general concept - IOW, the fundamental idea (to me)
is that the tree will be traversed in order, hence maintaining another list
structure is redundant.
>
> 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?
Sure. :-)
If you want, imho you can also attach the patch when reply, then the discussion
context won't be lost too.
--
Peter Xu
_______________________________________________
Virtualization mailing list
Virtualization@xxxxxxxxxxxxxxxxxxxxxxxxxx
https://lists.linuxfoundation.org/mailman/listinfo/virtualization
