Re: [RFC 0/2] Identify aliased maps in vdpa SVQ iova_tree

[Eugenio Perez Martin]

On Tue, Jul 30, 2024 at 10:48 AM Jason Wang <jasowang@redhat.com> wrote:
>
> On Mon, Jul 29, 2024 at 6:05 PM Eugenio Perez Martin
> <eperezma@redhat.com> wrote:
> >
> > On Wed, Jul 24, 2024 at 7:00 PM Jonah Palmer <jonah.palmer@oracle.com> 
> > wrote:
> > >
> > >
> > >
> > > On 5/13/24 11:56 PM, Jason Wang wrote:
> > > > On Mon, May 13, 2024 at 5:58 PM Eugenio Perez Martin
> > > > <eperezma@redhat.com> wrote:
> > > >>
> > > >> On Mon, May 13, 2024 at 10:28 AM Jason Wang <jasowang@redhat.com> 
> > > >> wrote:
> > > >>>
> > > >>> On Mon, May 13, 2024 at 2:28 PM Eugenio Perez Martin
> > > >>> <eperezma@redhat.com> wrote:
> > > >>>>
> > > >>>> On Sat, May 11, 2024 at 6:07 AM Jason Wang <jasowang@redhat.com> 
> > > >>>> wrote:
> > > >>>>>
> > > >>>>> On Fri, May 10, 2024 at 3:16 PM Eugenio Perez Martin
> > > >>>>> <eperezma@redhat.com> wrote:
> > > >>>>>>
> > > >>>>>> On Fri, May 10, 2024 at 6:29 AM Jason Wang <jasowang@redhat.com> 
> > > >>>>>> wrote:
> > > >>>>>>>
> > > >>>>>>> On Thu, May 9, 2024 at 3:10 PM Eugenio Perez Martin 
> > > >>>>>>> <eperezma@redhat.com> wrote:
> > > >>>>>>>>
> > > >>>>>>>> On Thu, May 9, 2024 at 8:27 AM Jason Wang <jasowang@redhat.com> 
> > > >>>>>>>> wrote:
> > > >>>>>>>>>
> > > >>>>>>>>> On Thu, May 9, 2024 at 1:16 AM Eugenio Perez Martin 
> > > >>>>>>>>> <eperezma@redhat.com> wrote:
> > > >>>>>>>>>>
> > > >>>>>>>>>> On Wed, May 8, 2024 at 4:29 AM Jason Wang 
> > > >>>>>>>>>> <jasowang@redhat.com> wrote:
> > > >>>>>>>>>>>
> > > >>>>>>>>>>> On Tue, May 7, 2024 at 6:57 PM Eugenio Perez Martin 
> > > >>>>>>>>>>> <eperezma@redhat.com> wrote:
> > > >>>>>>>>>>>>
> > > >>>>>>>>>>>> On Tue, May 7, 2024 at 9:29 AM Jason Wang 
> > > >>>>>>>>>>>> <jasowang@redhat.com> wrote:
> > > >>>>>>>>>>>>>
> > > >>>>>>>>>>>>> On Fri, Apr 12, 2024 at 3:56 PM Eugenio Perez Martin
> > > >>>>>>>>>>>>> <eperezma@redhat.com> wrote:
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> On Fri, Apr 12, 2024 at 8:47 AM Jason Wang 
> > > >>>>>>>>>>>>>> <jasowang@redhat.com> wrote:
> > > >>>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>>> On Wed, Apr 10, 2024 at 6:03 PM Eugenio Pérez 
> > > >>>>>>>>>>>>>>> <eperezma@redhat.com> wrote:
> > > >>>>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>>>> The guest may have overlapped memory regions, where 
> > > >>>>>>>>>>>>>>>> different GPA leads
> > > >>>>>>>>>>>>>>>> to the same HVA.  This causes a problem when overlapped 
> > > >>>>>>>>>>>>>>>> regions
> > > >>>>>>>>>>>>>>>> (different GPA but same translated HVA) exists in the 
> > > >>>>>>>>>>>>>>>> tree, as looking
> > > >>>>>>>>>>>>>>>> them by HVA will return them twice.
> > > >>>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>>> I think I don't understand if there's any side effect for 
> > > >>>>>>>>>>>>>>> shadow virtqueue?
> > > >>>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> My bad, I totally forgot to put a reference to where this 
> > > >>>>>>>>>>>>>> comes from.
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> Si-Wei found that during initialization this sequences of 
> > > >>>>>>>>>>>>>> maps /
> > > >>>>>>>>>>>>>> unmaps happens [1]:
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> HVA                    GPA                IOVA
> > > >>>>>>>>>>>>>> -------------------------------------------------------------------------------------------------------------------------
> > > >>>>>>>>>>>>>> Map
> > > >>>>>>>>>>>>>> [0x7f7903e00000, 0x7f7983e00000)    [0x0, 0x80000000) 
> > > >>>>>>>>>>>>>> [0x1000, 0x80000000)
> > > >>>>>>>>>>>>>> [0x7f7983e00000, 0x7f9903e00000)    [0x100000000, 
> > > >>>>>>>>>>>>>> 0x2080000000)
> > > >>>>>>>>>>>>>> [0x80001000, 0x2000001000)
> > > >>>>>>>>>>>>>> [0x7f7903ea0000, 0x7f7903ec0000)    [0xfeda0000, 
> > > >>>>>>>>>>>>>> 0xfedc0000)
> > > >>>>>>>>>>>>>> [0x2000001000, 0x2000021000)
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> Unmap
> > > >>>>>>>>>>>>>> [0x7f7903ea0000, 0x7f7903ec0000)    [0xfeda0000, 
> > > >>>>>>>>>>>>>> 0xfedc0000) [0x1000,
> > > >>>>>>>>>>>>>> 0x20000) ???
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> The third HVA range is contained in the first one, but 
> > > >>>>>>>>>>>>>> exposed under a
> > > >>>>>>>>>>>>>> different GVA (aliased). This is not "flattened" by QEMU, 
> > > >>>>>>>>>>>>>> as GPA does
> > > >>>>>>>>>>>>>> not overlap, only HVA.
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> At the third chunk unmap, the current algorithm finds the 
> > > >>>>>>>>>>>>>> first chunk,
> > > >>>>>>>>>>>>>> not the second one. This series is the way to tell the 
> > > >>>>>>>>>>>>>> difference at
> > > >>>>>>>>>>>>>> unmap time.
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> [1] 
> > > >>>>>>>>>>>>>> https://urldefense.com/v3/__https://lists.nongnu.org/archive/html/qemu-devel/2024-04/msg00079.html__;!!ACWV5N9M2RV99hQ!MXbGSFHVbqRf0rzyWamOdnBLHP0FUh3r3BnTvGe6Mn5VzXTsajVp3BB7VqlklkRCr5aKazC5xxTCScuR_BY$
> > > >>>>>>>>>>>>>>
> > > >>>>>>>>>>>>>> Thanks!
> > > >>>>>>>>>>>>>
> > > >>>>>>>>>>>>> Ok, I was wondering if we need to store GPA(GIOVA) to HVA 
> > > >>>>>>>>>>>>> mappings in
> > > >>>>>>>>>>>>> the iova tree to solve this issue completely. Then there 
> > > >>>>>>>>>>>>> won't be
> > > >>>>>>>>>>>>> aliasing issues.
> > > >>>>>>>>>>>>>
> > > >>>>>>>>>>>>
> > > >>>>>>>>>>>> I'm ok to explore that route but this has another problem. 
> > > >>>>>>>>>>>> Both SVQ
> > > >>>>>>>>>>>> vrings and CVQ buffers also need to be addressable by 
> > > >>>>>>>>>>>> VhostIOVATree,
> > > >>>>>>>>>>>> and they do not have GPA.
> > > >>>>>>>>>>>>
> > > >>>>>>>>>>>> At this moment vhost_svq_translate_addr is able to handle 
> > > >>>>>>>>>>>> this
> > > >>>>>>>>>>>> transparently as we translate vaddr to SVQ IOVA. How can we 
> > > >>>>>>>>>>>> store
> > > >>>>>>>>>>>> these new entries? Maybe a (hwaddr)-1 GPA to signal it has 
> > > >>>>>>>>>>>> no GPA and
> > > >>>>>>>>>>>> then a list to go through other entries (SVQ vaddr and CVQ 
> > > >>>>>>>>>>>> buffers).
> > > >>>>>>>>>>>
> > > >>>>>>>>>>> This seems to be tricky.
> > > >>>>>>>>>>>
> > > >>>>>>>>>>> As discussed, it could be another iova tree.
> > > >>>>>>>>>>>
> > > >>>>>>>>>>
> > > >>>>>>>>>> Yes but there are many ways to add another IOVATree. Let me 
> > > >>>>>>>>>> expand & recap.
> > > >>>>>>>>>>
> > > >>>>>>>>>> Option 1 is to simply add another iova tree to 
> > > >>>>>>>>>> VhostShadowVirtqueue.
> > > >>>>>>>>>> Let's call it gpa_iova_tree, as opposed to the current 
> > > >>>>>>>>>> iova_tree that
> > > >>>>>>>>>> translates from vaddr to SVQ IOVA. To know which one to use is 
> > > >>>>>>>>>> easy at
> > > >>>>>>>>>> adding or removing, like in the memory listener, but how to 
> > > >>>>>>>>>> know at
> > > >>>>>>>>>> vhost_svq_translate_addr?
> > > >>>>>>>>>
> > > >>>>>>>>> Then we won't use virtqueue_pop() at all, we need a SVQ version 
> > > >>>>>>>>> of
> > > >>>>>>>>> virtqueue_pop() to translate GPA to SVQ IOVA directly?
> > > >>>>>>>>>
> > > >>>>>>>>
> > > >>>>>>>> The problem is not virtqueue_pop, that's out of the
> > > >>>>>>>> vhost_svq_translate_addr. The problem is the need of adding
> > > >>>>>>>> conditionals / complexity in all the callers of
> > > >>>>>>>>
> > > >>>>>>>>>>
> > > >>>>>>>>>> The easiest way for me is to rely on 
> > > >>>>>>>>>> memory_region_from_host(). When
> > > >>>>>>>>>> vaddr is from the guest, it returns a valid MemoryRegion. When 
> > > >>>>>>>>>> it is
> > > >>>>>>>>>> not, it returns NULL. I'm not sure if this is a valid use 
> > > >>>>>>>>>> case, it
> > > >>>>>>>>>> just worked in my tests so far.
> > > >>>>>>>>>>
> > > >>>>>>>>>> Now we have the second problem: The GPA values of the regions 
> > > >>>>>>>>>> of the
> > > >>>>>>>>>> two IOVA tree must be unique. We need to be able to find 
> > > >>>>>>>>>> unallocated
> > > >>>>>>>>>> regions in SVQ IOVA. At this moment there is only one 
> > > >>>>>>>>>> IOVATree, so
> > > >>>>>>>>>> this is done easily by vhost_iova_tree_map_alloc. But it is 
> > > >>>>>>>>>> very
> > > >>>>>>>>>> complicated with two trees.
> > > >>>>>>>>>
> > > >>>>>>>>> Would it be simpler if we decouple the IOVA allocator? For 
> > > >>>>>>>>> example, we
> > > >>>>>>>>> can have a dedicated gtree to track the allocated IOVA ranges. 
> > > >>>>>>>>> It is
> > > >>>>>>>>> shared by both
> > > >>>>>>>>>
> > > >>>>>>>>> 1) Guest memory (GPA)
> > > >>>>>>>>> 2) SVQ virtqueue and buffers
> > > >>>>>>>>>
> > > >>>>>>>>> And another gtree to track the GPA to IOVA.
> > > >>>>>>>>>
> > > >>>>>>>>> The SVQ code could use either
> > > >>>>>>>>>
> > > >>>>>>>>> 1) one linear mappings that contains both SVQ virtqueue and 
> > > >>>>>>>>> buffers
> > > >>>>>>>>>
> > > >>>>>>>>> or
> > > >>>>>>>>>
> > > >>>>>>>>> 2) dynamic IOVA allocation/deallocation helpers
> > > >>>>>>>>>
> > > >>>>>>>>> So we don't actually need the third gtree for SVQ HVA -> SVQ 
> > > >>>>>>>>> IOVA?
> > > >>>>>>>>>
> > > >>>>>>>>
> > > >>>>>>>> That's possible, but that scatters the IOVA handling code 
> > > >>>>>>>> instead of
> > > >>>>>>>> keeping it self-contained in VhostIOVATree.
> > > >>>>>>>
> > > >>>>>>> To me, the IOVA range/allocation is orthogonal to how IOVA is 
> > > >>>>>>> used.
> > > >>>>>>>
> > > >>>>>>> An example is the iova allocator in the kernel.
> > > >>>>>>>
> > > >>>>>>> Note that there's an even simpler IOVA "allocator" in NVME 
> > > >>>>>>> passthrough
> > > >>>>>>> code, not sure it is useful here though (haven't had a deep look 
> > > >>>>>>> at
> > > >>>>>>> that).
> > > >>>>>>>
> > > >>>>>>
> > > >>>>>> I don't know enough about them to have an opinion. I keep seeing 
> > > >>>>>> the
> > > >>>>>> drawback of needing to synchronize both allocation & adding in all 
> > > >>>>>> the
> > > >>>>>> places we want to modify the IOVATree. At this moment, these are 
> > > >>>>>> the
> > > >>>>>> vhost-vdpa memory listener, the SVQ vring creation and removal, and
> > > >>>>>> net CVQ buffers. But it may be more in the future.
> > > >>>>>>
> > > >>>>>> What are the advantages of keeping these separated that justifies
> > > >>>>>> needing to synchronize in all these places, compared with keeping 
> > > >>>>>> them
> > > >>>>>> synchronized in VhostIOVATree?
> > > >>>>>
> > > >>>>> It doesn't need to be synchronized.
> > > >>>>>
> > > >>>>> Assuming guest and SVQ shares IOVA range. IOVA only needs to track
> > > >>>>> which part of the range has been used.
> > > >>>>>
> > > >>>>
> > > >>>> Not sure if I follow, that is what I mean with "synchronized".
> > > >>>
> > > >>> Oh right.
> > > >>>
> > > >>>>
> > > >>>>> This simplifies things, we can store GPA->IOVA mappings and SVQ ->
> > > >>>>> IOVA mappings separately.
> > > >>>>>
> > > >>>>
> > > >>>> Sorry, I still cannot see the whole picture :).
> > > >>>>
> > > >>>> Let's assume we have all the GPA mapped to specific IOVA regions, so
> > > >>>> we have the first IOVA tree (GPA -> IOVA) filled. Now we enable SVQ
> > > >>>> because of the migration. How can we know where we can place SVQ
> > > >>>> vrings without having them synchronized?
> > > >>>
> > > >>> Just allocating a new IOVA range for SVQ?
> > > >>>
> > > >>>>
> > > >>>> At this moment we're using a tree. The tree nature of the current SVQ
> > > >>>> IOVA -> VA makes all nodes ordered so it is more or less easy to look
> > > >>>> for holes.
> > > >>>
> > > >>> Yes, iova allocate could still be implemented via a tree.
> > > >>>
> > > >>>>
> > > >>>> Now your proposal uses the SVQ IOVA as tree values. Should we iterate
> > > >>>> over all of them, order them, of the two trees, and then look for
> > > >>>> holes there?
> > > >>>
> > > >>> Let me clarify, correct me if I was wrong:
> > > >>>
> > > >>> 1) IOVA allocator is still implemented via a tree, we just don't need
> > > >>> to store how the IOVA is used
> > > >>> 2) A dedicated GPA -> IOVA tree, updated via listeners and is used in
> > > >>> the datapath SVQ translation
> > > >>> 3) A linear mapping or another SVQ -> IOVA tree used for SVQ
> > > >>>
> > > >>
> > > >> Ok, so the part I was missing is that now we have 3 whole trees, with
> > > >> somehow redundant information :).
> > > >
> > > > Somehow, it decouples the IOVA usage out of the IOVA allocator. This
> > > > might be simple as guests and SVQ may try to share a single IOVA
> > > > address space.
> > > >
> > >
> > > I'm working on implementing your three suggestions above but I'm a bit
> > > confused with some of the wording and I was hoping you could clarify
> > > some of it for me when you get the chance.
> > >
> > > ---
> > > For your first suggestion (1) you mention decoupling the IOVA allocator
> > > and "don't need to store how the IOVA is used."
> > >
> > > By this, do you mean to not save the IOVA->HVA mapping and instead only
> > > save the allocated IOVA ranges?
>
> Yes.
>
> > > In other words, are you suggesting to
> > > create a dedicated "IOVA->IOVA" tree like:
> > >
> > > struct VhostIOVATree {
> > >      uint64_t iova_first;
> > >      uint64_t iova_last;
> > >      IOVATree *iova_map;
> > > };
>
> It could be this or other. I think the point is the allocator is only
> used for IOVA allocation but it doesn't have any information about the
> mapping.
>
> > >
> > > Where the mapping might look something like (where translated_addr is
> > > given some kind of 0 value):
> > >
> > > iova_region = (DMAMap) {
> > >      .iova = iova_first,
> > >      .translated_addr = 0,
> > >      .size = region_size - 1,
> > >      .perm = IOMMU_ACCESS_FLAG(true, section->readonly),
> > > };
> > >
> > > Also, if this is what you mean by decoupling the IOVA allocator, what
> > > happens to the IOVA->HVA tree?
>
> We will have two structures:
>
> 1) IOVA domain (in charge of IOVA range allocation/deallocation)
> 2) How the IOVA is used, e.g an IOVA->HVA tree
>
> > Are we no longer saving these mappings in
> > > a tree?
> > >
> > > ---
> > > In your second suggestion (2) with a dedicated GPA->IOVA tree, were you
> > > thinking something like this? Just adding on to VhostIOVATree here:
> > >
> > > struct VhostIOVATree {
> > >      uint64_t iova_first;
> > >      uint64_t iova_last;
> > >      IOVATree *iova_map;
> > >      IOVATree *gpa_map;
> > > };
>
> I'd split the mappings if it's possible.
>
> > >
> > > Where the mapping might look something like:
> > >
> > > gpa_region = (DMAMap) {
> > >      .iova = iova_first,
> > >      .translated_addr = gpa_first,
> > >      .size = region_size - 1,
> > >      .perm = IOMMU_ACCESS_FLAG(true, section->readonly),
> > > };
> > >
> > > Also, when you say "used in the datapath SVQ translation", we still need
> > > to build the GPA->IOVA tree when vhost_vdpa_listener_region_add() is
> > > called, right?
>
> Right.
>
> > >
> > > ---
> > > Lastly, in your third suggestion (3) you mention implementing a
> > > SVQ->IOVA tree, making the total number of IOVATrees/GTrees 3: one for
> > > just IOVAs, one for GPA->IOVA, and the last one for SVQ->IOVA. E.g.
> > >
> > > struct VhostIOVATree {
> > >      uint64_t iova_first;
> > >      uint64_t iova_last;
> > >      IOVATree *iova_map;
> > >      IOVATree *gpa_map;
> > >      IOVATree *svq_map;
> > > };
> > >
> > > ---
> > >
> > > Let me know if I'm understanding this correctly. If I am, this would
> > > require a pretty good amount of refactoring on the IOVA allocation,
> > > searching, destroying, etc. code to account for these new trees.
> > >
> >
> > Ok I think I understand your previous question better, sorry for the delay 
> > :).
> >
> > If I'm not wrong, Jason did not enumerate these as alternatives but as
> > part of the same solution. Jason please correct me if I'm wrong here.
> >
> > His solution is composed of three trees:
> > 1) One for the IOVA allocations, so we know where to allocate new ranges
> > 2) One of the GPA -> SVQ IOVA translations.
> > 3) Another one for SVQ vrings translations.
> >
>
> Exactly.
>
> > In my opinion to use GPA this is problematic as we force all of the
> > callers to know if the address we want to translate comes from the
> > guest or not. Current code does now know it, as
> > vhost_svq_translate_addr is called to translate both buffer dataplane
> > addresses and control virtqueue buffers, which are also shadowed.  To
> > transmit that information to the caller code would require either
> > duplicate functions, to add a boolean, etc, as it is in a different
> > layer (net specific net/vhost-vdpa.c vs generic
> > hw/virtio/vhost-shadow-virtqueue.c).
> >
> > In my opinion is easier to keep just two trees (or similar structs):
> > 1) One for the IOVA allocations, so we know where to allocate new
> > ranges. We don't actually need to store the translations here.
> > 2) One for HVA -> SVQ IOVA translations.
> >
> > This way we can accommodate both SVQ vrings, CVQ buffers, and guest
> > memory buffers, all on the second tree, and take care of the HVA
> > duplications.
>
> Probably, but how to take care of HVA duplications (I may miss the
> context, sorry)?
>

What to do with the duplicated HVA is an added problem that deserves
more discussion, right. If a duplicated entry gets deleted, the other
one should take its place in both trees.

Store them in an ordered list and look for replacements on tree
deletion maybe? It would be great to locate a similar usage and see
what is done there.

> Thanks
>
> >
> > Thanks!
> >
> > > Thanks Jason!
> > >
> > > >>
> > > >> In some sense this is simpler than trying to get all the information
> > > >> from only two trees. On the bad side, all SVQ calls that allocate some
> > > >> region need to remember to add to one of the two other threes. That is
> > > >> what I mean by synchronized. But sure, we can go that way.
> > > >
> > > > Just a suggestion, if it turns out to complicate the issue, I'm fine
> > > > to go the other way.
> > > >
> > > > Thanks
> > > >
> > > >>
> > > >>> Thanks
> > > >>>
> > > >>>>
> > > >>>>> Thanks
> > > >>>>>
> > > >>>>>>
> > > >>>>>> Thanks!
> > > >>>>>>
> > > >>>>>
> > > >>>>
> > > >>>
> > > >>
> > > >>
> > > >
> > >
> >
>