From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>

Hi,
  This is an experimental set that reworks the way the vhost
code handles changes in physical address space layout that
came from a discussion with Igor.

Instead of updating and trying to merge sections of address
space on each add/remove callback, we wait until the commit phase
and go through and rebuild a list by walking the Flatview of
memory and end up producing an ordered list.
We compare the list to the old list to trigger updates.

Note, only very lightly tested so far, I'm just trying to see if it's
the right shape.

Igor, is this what you were intending?

Dave

Dr. David Alan Gilbert (7):
  memory: address_space_iterate
  vhost: Move log_dirty check
  vhost: New memory update functions
  vhost: update_mem_cb implementation
  vhost: Compare new and old memory lists
  vhost: Copy updated region data into device state
  vhost: Remove vhost_set_memory and children

 hw/virtio/trace-events |   8 +
 hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
 include/exec/memory.h  |  23 +++
 memory.c               |  22 +++
 4 files changed, 241 insertions(+), 236 deletions(-)

-- 
2.14.3

On Wed, 29 Nov 2017 18:50:19 +0000
"Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:

> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> 
> Hi,
>   This is an experimental set that reworks the way the vhost
> code handles changes in physical address space layout that
> came from a discussion with Igor.
Thanks for looking into it.

 
> Instead of updating and trying to merge sections of address
> space on each add/remove callback, we wait until the commit phase
> and go through and rebuild a list by walking the Flatview of
> memory and end up producing an ordered list.
> We compare the list to the old list to trigger updates.
> 
> Note, only very lightly tested so far, I'm just trying to see if it's
> the right shape.
> 
> Igor, is this what you were intending?

I was thinking about a little less intrusive approach

where vhost_region_add/del are modified to maintain
sorted by GPA array of mem_sections, vhost_dev::mem is dropped
altogether and vhost_memory_region array is build/used/freed
on every vhost_commit().
Maintaining sorted array should roughly cost us O(2 log n) if
binary search is used.

However I like your idea with iterator even more as it have
potential to make it even faster O(n) if we get rid of
quadratic and relatively complex vhost_update_compare_list().

Pls, see comments on individual patches.

> Dave
> 
> Dr. David Alan Gilbert (7):
>   memory: address_space_iterate
>   vhost: Move log_dirty check
>   vhost: New memory update functions
>   vhost: update_mem_cb implementation
>   vhost: Compare new and old memory lists
>   vhost: Copy updated region data into device state
>   vhost: Remove vhost_set_memory and children
> 
>  hw/virtio/trace-events |   8 +
>  hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
>  include/exec/memory.h  |  23 +++
>  memory.c               |  22 +++
>  4 files changed, 241 insertions(+), 236 deletions(-)
> 

* Igor Mammedov (imammedo@redhat.com) wrote:
> On Wed, 29 Nov 2017 18:50:19 +0000
> "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> 
> > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > 
> > Hi,
> >   This is an experimental set that reworks the way the vhost
> > code handles changes in physical address space layout that
> > came from a discussion with Igor.
> Thanks for looking into it.
> 
>  
> > Instead of updating and trying to merge sections of address
> > space on each add/remove callback, we wait until the commit phase
> > and go through and rebuild a list by walking the Flatview of
> > memory and end up producing an ordered list.
> > We compare the list to the old list to trigger updates.
> > 
> > Note, only very lightly tested so far, I'm just trying to see if it's
> > the right shape.
> > 
> > Igor, is this what you were intending?
> 
> I was thinking about a little less intrusive approach
> 
> where vhost_region_add/del are modified to maintain
> sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> altogether and vhost_memory_region array is build/used/freed
> on every vhost_commit().
> Maintaining sorted array should roughly cost us O(2 log n) if
> binary search is used.
> 
> However I like your idea with iterator even more as it have
> potential to make it even faster O(n) if we get rid of
> quadratic and relatively complex vhost_update_compare_list().

Note vhost_update_compare_list is complex, but it is O(n) - it's
got nested loops, but the inner loop moves forward and oldi never
gets reset back to zero.

> Pls, see comments on individual patches.

Thanks; I have fixed a couple of bugs since I posted, so I'm
more interested in structure/shape.  Any good ideas how to test
it are welcome.

Dave

> 
> > Dave
> > 
> > Dr. David Alan Gilbert (7):
> >   memory: address_space_iterate
> >   vhost: Move log_dirty check
> >   vhost: New memory update functions
> >   vhost: update_mem_cb implementation
> >   vhost: Compare new and old memory lists
> >   vhost: Copy updated region data into device state
> >   vhost: Remove vhost_set_memory and children
> > 
> >  hw/virtio/trace-events |   8 +
> >  hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
> >  include/exec/memory.h  |  23 +++
> >  memory.c               |  22 +++
> >  4 files changed, 241 insertions(+), 236 deletions(-)
> > 
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

On Thu, 30 Nov 2017 12:08:06 +0000
"Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:

> * Igor Mammedov (imammedo@redhat.com) wrote:
> > On Wed, 29 Nov 2017 18:50:19 +0000
> > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> >   
> > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > 
> > > Hi,
> > >   This is an experimental set that reworks the way the vhost
> > > code handles changes in physical address space layout that
> > > came from a discussion with Igor.  
> > Thanks for looking into it.
> > 
> >    
> > > Instead of updating and trying to merge sections of address
> > > space on each add/remove callback, we wait until the commit phase
> > > and go through and rebuild a list by walking the Flatview of
> > > memory and end up producing an ordered list.
> > > We compare the list to the old list to trigger updates.
> > > 
> > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > the right shape.
> > > 
> > > Igor, is this what you were intending?  
> > 
> > I was thinking about a little less intrusive approach
> > 
> > where vhost_region_add/del are modified to maintain
> > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > altogether and vhost_memory_region array is build/used/freed
> > on every vhost_commit().
> > Maintaining sorted array should roughly cost us O(2 log n) if
> > binary search is used.
> > 
> > However I like your idea with iterator even more as it have
> > potential to make it even faster O(n) if we get rid of
> > quadratic and relatively complex vhost_update_compare_list().  
> 
> Note vhost_update_compare_list is complex,
> but it is O(n) - it's
> got nested loops, but the inner loop moves forward and oldi never
> gets reset back to zero.
While skimming through patches I've overlooked it.

Anyways,
why memcmp(old_arr, new_arr) is not sufficient
to detect a change in memory map?

> 
> > Pls, see comments on individual patches.  
> 
> Thanks; I have fixed a couple of bugs since I posted, so I'm
> more interested in structure/shape.  Any good ideas how to test
> it are welcome.
> 
> Dave
> 
> >   
> > > Dave
> > > 
> > > Dr. David Alan Gilbert (7):
> > >   memory: address_space_iterate
> > >   vhost: Move log_dirty check
> > >   vhost: New memory update functions
> > >   vhost: update_mem_cb implementation
> > >   vhost: Compare new and old memory lists
> > >   vhost: Copy updated region data into device state
> > >   vhost: Remove vhost_set_memory and children
> > > 
> > >  hw/virtio/trace-events |   8 +
> > >  hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
> > >  include/exec/memory.h  |  23 +++
> > >  memory.c               |  22 +++
> > >  4 files changed, 241 insertions(+), 236 deletions(-)
> > >   
> >   
> --
> Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

* Igor Mammedov (imammedo@redhat.com) wrote:
> On Thu, 30 Nov 2017 12:08:06 +0000
> "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> 
> > * Igor Mammedov (imammedo@redhat.com) wrote:
> > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > >   
> > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > 
> > > > Hi,
> > > >   This is an experimental set that reworks the way the vhost
> > > > code handles changes in physical address space layout that
> > > > came from a discussion with Igor.  
> > > Thanks for looking into it.
> > > 
> > >    
> > > > Instead of updating and trying to merge sections of address
> > > > space on each add/remove callback, we wait until the commit phase
> > > > and go through and rebuild a list by walking the Flatview of
> > > > memory and end up producing an ordered list.
> > > > We compare the list to the old list to trigger updates.
> > > > 
> > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > the right shape.
> > > > 
> > > > Igor, is this what you were intending?  
> > > 
> > > I was thinking about a little less intrusive approach
> > > 
> > > where vhost_region_add/del are modified to maintain
> > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > altogether and vhost_memory_region array is build/used/freed
> > > on every vhost_commit().
> > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > binary search is used.
> > > 
> > > However I like your idea with iterator even more as it have
> > > potential to make it even faster O(n) if we get rid of
> > > quadratic and relatively complex vhost_update_compare_list().  
> > 
> > Note vhost_update_compare_list is complex,
> > but it is O(n) - it's
> > got nested loops, but the inner loop moves forward and oldi never
> > gets reset back to zero.
> While skimming through patches I've overlooked it.
> 
> Anyways,
> why memcmp(old_arr, new_arr) is not sufficient
> to detect a change in memory map?

It tells you that you've got a change, but doesn't give
the start/end of the range that's changed, and those
are used by vhost_commit to limit the work of
vhost_verify_ring_mappings.

Dave

> > 
> > > Pls, see comments on individual patches.  
> > 
> > Thanks; I have fixed a couple of bugs since I posted, so I'm
> > more interested in structure/shape.  Any good ideas how to test
> > it are welcome.
> > 
> > Dave
> > 
> > >   
> > > > Dave
> > > > 
> > > > Dr. David Alan Gilbert (7):
> > > >   memory: address_space_iterate
> > > >   vhost: Move log_dirty check
> > > >   vhost: New memory update functions
> > > >   vhost: update_mem_cb implementation
> > > >   vhost: Compare new and old memory lists
> > > >   vhost: Copy updated region data into device state
> > > >   vhost: Remove vhost_set_memory and children
> > > > 
> > > >  hw/virtio/trace-events |   8 +
> > > >  hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
> > > >  include/exec/memory.h  |  23 +++
> > > >  memory.c               |  22 +++
> > > >  4 files changed, 241 insertions(+), 236 deletions(-)
> > > >   
> > >   
> > --
> > Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

On Thu, 30 Nov 2017 12:47:20 +0000
"Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:

> * Igor Mammedov (imammedo@redhat.com) wrote:
> > On Thu, 30 Nov 2017 12:08:06 +0000
> > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> >   
> > > * Igor Mammedov (imammedo@redhat.com) wrote:  
> > > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > > >     
> > > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > > 
> > > > > Hi,
> > > > >   This is an experimental set that reworks the way the vhost
> > > > > code handles changes in physical address space layout that
> > > > > came from a discussion with Igor.    
> > > > Thanks for looking into it.
> > > > 
> > > >      
> > > > > Instead of updating and trying to merge sections of address
> > > > > space on each add/remove callback, we wait until the commit phase
> > > > > and go through and rebuild a list by walking the Flatview of
> > > > > memory and end up producing an ordered list.
> > > > > We compare the list to the old list to trigger updates.
> > > > > 
> > > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > > the right shape.
> > > > > 
> > > > > Igor, is this what you were intending?    
> > > > 
> > > > I was thinking about a little less intrusive approach
> > > > 
> > > > where vhost_region_add/del are modified to maintain
> > > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > > altogether and vhost_memory_region array is build/used/freed
> > > > on every vhost_commit().
> > > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > > binary search is used.
> > > > 
> > > > However I like your idea with iterator even more as it have
> > > > potential to make it even faster O(n) if we get rid of
> > > > quadratic and relatively complex vhost_update_compare_list().    
> > > 
> > > Note vhost_update_compare_list is complex,
> > > but it is O(n) - it's
> > > got nested loops, but the inner loop moves forward and oldi never
> > > gets reset back to zero.  
> > While skimming through patches I've overlooked it.
> > 
> > Anyways,
> > why memcmp(old_arr, new_arr) is not sufficient
> > to detect a change in memory map?  
> 
> It tells you that you've got a change, but doesn't give
> the start/end of the range that's changed, and those
> are used by vhost_commit to limit the work of
> vhost_verify_ring_mappings.
Isn't memmap list a sorted and
 dev->mem_changed_[start|end]_addr are the lowest|highest
addresses of whole map?

If it's, so wouldn't getting values directly from 
the 1st/last entries of array be sufficient?



> 
> Dave
> 
> > >   
> > > > Pls, see comments on individual patches.    
> > > 
> > > Thanks; I have fixed a couple of bugs since I posted, so I'm
> > > more interested in structure/shape.  Any good ideas how to test
> > > it are welcome.
> > > 
> > > Dave
> > >   
> > > >     
> > > > > Dave
> > > > > 
> > > > > Dr. David Alan Gilbert (7):
> > > > >   memory: address_space_iterate
> > > > >   vhost: Move log_dirty check
> > > > >   vhost: New memory update functions
> > > > >   vhost: update_mem_cb implementation
> > > > >   vhost: Compare new and old memory lists
> > > > >   vhost: Copy updated region data into device state
> > > > >   vhost: Remove vhost_set_memory and children
> > > > > 
> > > > >  hw/virtio/trace-events |   8 +
> > > > >  hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
> > > > >  include/exec/memory.h  |  23 +++
> > > > >  memory.c               |  22 +++
> > > > >  4 files changed, 241 insertions(+), 236 deletions(-)
> > > > >     
> > > >     
> > > --
> > > Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK  
> >   
> --
> Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

* Igor Mammedov (imammedo@redhat.com) wrote:
> On Thu, 30 Nov 2017 12:47:20 +0000
> "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> 
> > * Igor Mammedov (imammedo@redhat.com) wrote:
> > > On Thu, 30 Nov 2017 12:08:06 +0000
> > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > >   
> > > > * Igor Mammedov (imammedo@redhat.com) wrote:  
> > > > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > > > >     
> > > > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > > > 
> > > > > > Hi,
> > > > > >   This is an experimental set that reworks the way the vhost
> > > > > > code handles changes in physical address space layout that
> > > > > > came from a discussion with Igor.    
> > > > > Thanks for looking into it.
> > > > > 
> > > > >      
> > > > > > Instead of updating and trying to merge sections of address
> > > > > > space on each add/remove callback, we wait until the commit phase
> > > > > > and go through and rebuild a list by walking the Flatview of
> > > > > > memory and end up producing an ordered list.
> > > > > > We compare the list to the old list to trigger updates.
> > > > > > 
> > > > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > > > the right shape.
> > > > > > 
> > > > > > Igor, is this what you were intending?    
> > > > > 
> > > > > I was thinking about a little less intrusive approach
> > > > > 
> > > > > where vhost_region_add/del are modified to maintain
> > > > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > > > altogether and vhost_memory_region array is build/used/freed
> > > > > on every vhost_commit().
> > > > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > > > binary search is used.
> > > > > 
> > > > > However I like your idea with iterator even more as it have
> > > > > potential to make it even faster O(n) if we get rid of
> > > > > quadratic and relatively complex vhost_update_compare_list().    
> > > > 
> > > > Note vhost_update_compare_list is complex,
> > > > but it is O(n) - it's
> > > > got nested loops, but the inner loop moves forward and oldi never
> > > > gets reset back to zero.  
> > > While skimming through patches I've overlooked it.
> > > 
> > > Anyways,
> > > why memcmp(old_arr, new_arr) is not sufficient
> > > to detect a change in memory map?  
> > 
> > It tells you that you've got a change, but doesn't give
> > the start/end of the range that's changed, and those
> > are used by vhost_commit to limit the work of
> > vhost_verify_ring_mappings.
> Isn't memmap list a sorted and
>  dev->mem_changed_[start|end]_addr are the lowest|highest
> addresses of whole map?
> 
> If it's, so wouldn't getting values directly from 
> the 1st/last entries of array be sufficient?

THat wasn't my understanding from the existing code;
my understanding was that changed_start_addr is set by
vhost_region_add->vhost_set_memory when a new region is added
(or removed) and is set to the limit of the section added.
But perhaps I'm misunderstanding.

(The logic in vhost_verify_ring_mappings doesn't make sense
to me either though; if vhost_verify_ring_part_mapping returns 0
on success, why is it doing   if (!r) { break; }  surely it
should be  if (r) { break; })

Dave

> 
> 
> > 
> > Dave
> > 
> > > >   
> > > > > Pls, see comments on individual patches.    
> > > > 
> > > > Thanks; I have fixed a couple of bugs since I posted, so I'm
> > > > more interested in structure/shape.  Any good ideas how to test
> > > > it are welcome.
> > > > 
> > > > Dave
> > > >   
> > > > >     
> > > > > > Dave
> > > > > > 
> > > > > > Dr. David Alan Gilbert (7):
> > > > > >   memory: address_space_iterate
> > > > > >   vhost: Move log_dirty check
> > > > > >   vhost: New memory update functions
> > > > > >   vhost: update_mem_cb implementation
> > > > > >   vhost: Compare new and old memory lists
> > > > > >   vhost: Copy updated region data into device state
> > > > > >   vhost: Remove vhost_set_memory and children
> > > > > > 
> > > > > >  hw/virtio/trace-events |   8 +
> > > > > >  hw/virtio/vhost.c      | 424 ++++++++++++++++++++++---------------------------
> > > > > >  include/exec/memory.h  |  23 +++
> > > > > >  memory.c               |  22 +++
> > > > > >  4 files changed, 241 insertions(+), 236 deletions(-)
> > > > > >     
> > > > >     
> > > > --
> > > > Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK  
> > >   
> > --
> > Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

On Thu, 30 Nov 2017 13:06:29 +0000
"Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:

> * Igor Mammedov (imammedo@redhat.com) wrote:
> > On Thu, 30 Nov 2017 12:47:20 +0000
> > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> >   
> > > * Igor Mammedov (imammedo@redhat.com) wrote:  
> > > > On Thu, 30 Nov 2017 12:08:06 +0000
> > > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > > >     
> > > > > * Igor Mammedov (imammedo@redhat.com) wrote:    
> > > > > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > > > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > > > > >       
> > > > > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > > > > 
> > > > > > > Hi,
> > > > > > >   This is an experimental set that reworks the way the vhost
> > > > > > > code handles changes in physical address space layout that
> > > > > > > came from a discussion with Igor.      
> > > > > > Thanks for looking into it.
> > > > > > 
> > > > > >        
> > > > > > > Instead of updating and trying to merge sections of address
> > > > > > > space on each add/remove callback, we wait until the commit phase
> > > > > > > and go through and rebuild a list by walking the Flatview of
> > > > > > > memory and end up producing an ordered list.
> > > > > > > We compare the list to the old list to trigger updates.
> > > > > > > 
> > > > > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > > > > the right shape.
> > > > > > > 
> > > > > > > Igor, is this what you were intending?      
> > > > > > 
> > > > > > I was thinking about a little less intrusive approach
> > > > > > 
> > > > > > where vhost_region_add/del are modified to maintain
> > > > > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > > > > altogether and vhost_memory_region array is build/used/freed
> > > > > > on every vhost_commit().
> > > > > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > > > > binary search is used.
> > > > > > 
> > > > > > However I like your idea with iterator even more as it have
> > > > > > potential to make it even faster O(n) if we get rid of
> > > > > > quadratic and relatively complex vhost_update_compare_list().      
> > > > > 
> > > > > Note vhost_update_compare_list is complex,
> > > > > but it is O(n) - it's
> > > > > got nested loops, but the inner loop moves forward and oldi never
> > > > > gets reset back to zero.    
> > > > While skimming through patches I've overlooked it.
> > > > 
> > > > Anyways,
> > > > why memcmp(old_arr, new_arr) is not sufficient
> > > > to detect a change in memory map?    
> > > 
> > > It tells you that you've got a change, but doesn't give
> > > the start/end of the range that's changed, and those
> > > are used by vhost_commit to limit the work of
> > > vhost_verify_ring_mappings.  
> > Isn't memmap list a sorted and
> >  dev->mem_changed_[start|end]_addr are the lowest|highest
> > addresses of whole map?
> > 
> > If it's, so wouldn't getting values directly from 
> > the 1st/last entries of array be sufficient?  
> 
> THat wasn't my understanding from the existing code;
> my understanding was that changed_start_addr is set by
> vhost_region_add->vhost_set_memory when a new region is added
> (or removed) and is set to the limit of the section added.
> But perhaps I'm misunderstanding.
changed_*_addr is actually lower/upper bound of memory transaction
and in practice it often includes several memory sections that
get mapped during transaction (between begin - commit).

but then again,
  - how expensive vhost_verify_ring_mappings() is?
  - do we really need optimization here (perhaps finding out changed range is more expensive)?
  - how about calling vhost_verify_ring_mappings() unconditionally?

> (The logic in vhost_verify_ring_mappings doesn't make sense
> to me either though; if vhost_verify_ring_part_mapping returns 0
> on success, why is it doing   if (!r) { break; }  surely it
> should be  if (r) { break; })
it looks like a bug (CCing Greg)

before (f1f9e6c5 vhost: adapt vhost_verify_ring_mappings() to virtio 1 ring layout)
logic used to be

   if changed_*_addr doesn't contain ring
      "IGNORE as we don't care"
   
   if changed_*_addr contain ring AND ring can't be mapped at the same place
      ABORT

with f1f9e6c5 we have 3 rings so on any of them following could happen
   if "IGNORE as we don't care"
     break => false success 
     since it's possible that the remaining rings in vq do overlap and didn't get checked

* Igor Mammedov (imammedo@redhat.com) wrote:
> On Thu, 30 Nov 2017 13:06:29 +0000
> "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> 
> > * Igor Mammedov (imammedo@redhat.com) wrote:
> > > On Thu, 30 Nov 2017 12:47:20 +0000
> > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > >   
> > > > * Igor Mammedov (imammedo@redhat.com) wrote:  
> > > > > On Thu, 30 Nov 2017 12:08:06 +0000
> > > > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > > > >     
> > > > > > * Igor Mammedov (imammedo@redhat.com) wrote:    
> > > > > > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > > > > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > > > > > >       
> > > > > > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > > > > > 
> > > > > > > > Hi,
> > > > > > > >   This is an experimental set that reworks the way the vhost
> > > > > > > > code handles changes in physical address space layout that
> > > > > > > > came from a discussion with Igor.      
> > > > > > > Thanks for looking into it.
> > > > > > > 
> > > > > > >        
> > > > > > > > Instead of updating and trying to merge sections of address
> > > > > > > > space on each add/remove callback, we wait until the commit phase
> > > > > > > > and go through and rebuild a list by walking the Flatview of
> > > > > > > > memory and end up producing an ordered list.
> > > > > > > > We compare the list to the old list to trigger updates.
> > > > > > > > 
> > > > > > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > > > > > the right shape.
> > > > > > > > 
> > > > > > > > Igor, is this what you were intending?      
> > > > > > > 
> > > > > > > I was thinking about a little less intrusive approach
> > > > > > > 
> > > > > > > where vhost_region_add/del are modified to maintain
> > > > > > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > > > > > altogether and vhost_memory_region array is build/used/freed
> > > > > > > on every vhost_commit().
> > > > > > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > > > > > binary search is used.
> > > > > > > 
> > > > > > > However I like your idea with iterator even more as it have
> > > > > > > potential to make it even faster O(n) if we get rid of
> > > > > > > quadratic and relatively complex vhost_update_compare_list().      
> > > > > > 
> > > > > > Note vhost_update_compare_list is complex,
> > > > > > but it is O(n) - it's
> > > > > > got nested loops, but the inner loop moves forward and oldi never
> > > > > > gets reset back to zero.    
> > > > > While skimming through patches I've overlooked it.
> > > > > 
> > > > > Anyways,
> > > > > why memcmp(old_arr, new_arr) is not sufficient
> > > > > to detect a change in memory map?    
> > > > 
> > > > It tells you that you've got a change, but doesn't give
> > > > the start/end of the range that's changed, and those
> > > > are used by vhost_commit to limit the work of
> > > > vhost_verify_ring_mappings.  
> > > Isn't memmap list a sorted and
> > >  dev->mem_changed_[start|end]_addr are the lowest|highest
> > > addresses of whole map?
> > > 
> > > If it's, so wouldn't getting values directly from 
> > > the 1st/last entries of array be sufficient?  
> > 
> > THat wasn't my understanding from the existing code;
> > my understanding was that changed_start_addr is set by
> > vhost_region_add->vhost_set_memory when a new region is added
> > (or removed) and is set to the limit of the section added.
> > But perhaps I'm misunderstanding.
> changed_*_addr is actually lower/upper bound of memory transaction
> and in practice it often includes several memory sections that
> get mapped during transaction (between begin - commit).
> 
> but then again,
>   - how expensive vhost_verify_ring_mappings() is?
>   - do we really need optimization here (perhaps finding out changed range is more expensive)?
>   - how about calling vhost_verify_ring_mappings() unconditionally?

My worry is that:
    vhost_verify_ring_mappings
       vhost_verify_ring_part_mapping
          vhost_verify_ring_part_mapping
             vhost_memory_map & vhost_memory_unmap
               (non-iommu case...)
               cpu_physical_memory_map & cpu_physical_memory_unmap
                 address_space_map/address_space_unmap
                    flatview_translate etc

so it's not cheap at all - I *think* it should end up doing very little
after it's gone all the way through that because it should already be
mapped; but still it's not trivial.

Dave

> 
> > (The logic in vhost_verify_ring_mappings doesn't make sense
> > to me either though; if vhost_verify_ring_part_mapping returns 0
> > on success, why is it doing   if (!r) { break; }  surely it
> > should be  if (r) { break; })
> it looks like a bug (CCing Greg)
> 
> before (f1f9e6c5 vhost: adapt vhost_verify_ring_mappings() to virtio 1 ring layout)
> logic used to be
> 
>    if changed_*_addr doesn't contain ring
>       "IGNORE as we don't care"
>    
>    if changed_*_addr contain ring AND ring can't be mapped at the same place
>       ABORT
> 
> with f1f9e6c5 we have 3 rings so on any of them following could happen
>    if "IGNORE as we don't care"
>      break => false success 
>      since it's possible that the remaining rings in vq do overlap and didn't get checked
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

On Thu, 30 Nov 2017 15:18:55 +0000
"Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:

> * Igor Mammedov (imammedo@redhat.com) wrote:
> > On Thu, 30 Nov 2017 13:06:29 +0000
> > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> >   
> > > * Igor Mammedov (imammedo@redhat.com) wrote:  
> > > > On Thu, 30 Nov 2017 12:47:20 +0000
> > > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > > >     
> > > > > * Igor Mammedov (imammedo@redhat.com) wrote:    
> > > > > > On Thu, 30 Nov 2017 12:08:06 +0000
> > > > > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > > > > >       
> > > > > > > * Igor Mammedov (imammedo@redhat.com) wrote:      
> > > > > > > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > > > > > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > > > > > > >         
> > > > > > > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > > > > > > 
> > > > > > > > > Hi,
> > > > > > > > >   This is an experimental set that reworks the way the vhost
> > > > > > > > > code handles changes in physical address space layout that
> > > > > > > > > came from a discussion with Igor.        
> > > > > > > > Thanks for looking into it.
> > > > > > > > 
> > > > > > > >          
> > > > > > > > > Instead of updating and trying to merge sections of address
> > > > > > > > > space on each add/remove callback, we wait until the commit phase
> > > > > > > > > and go through and rebuild a list by walking the Flatview of
> > > > > > > > > memory and end up producing an ordered list.
> > > > > > > > > We compare the list to the old list to trigger updates.
> > > > > > > > > 
> > > > > > > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > > > > > > the right shape.
> > > > > > > > > 
> > > > > > > > > Igor, is this what you were intending?        
> > > > > > > > 
> > > > > > > > I was thinking about a little less intrusive approach
> > > > > > > > 
> > > > > > > > where vhost_region_add/del are modified to maintain
> > > > > > > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > > > > > > altogether and vhost_memory_region array is build/used/freed
> > > > > > > > on every vhost_commit().
> > > > > > > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > > > > > > binary search is used.
> > > > > > > > 
> > > > > > > > However I like your idea with iterator even more as it have
> > > > > > > > potential to make it even faster O(n) if we get rid of
> > > > > > > > quadratic and relatively complex vhost_update_compare_list().        
> > > > > > > 
> > > > > > > Note vhost_update_compare_list is complex,
> > > > > > > but it is O(n) - it's
> > > > > > > got nested loops, but the inner loop moves forward and oldi never
> > > > > > > gets reset back to zero.      
> > > > > > While skimming through patches I've overlooked it.
> > > > > > 
> > > > > > Anyways,
> > > > > > why memcmp(old_arr, new_arr) is not sufficient
> > > > > > to detect a change in memory map?      
> > > > > 
> > > > > It tells you that you've got a change, but doesn't give
> > > > > the start/end of the range that's changed, and those
> > > > > are used by vhost_commit to limit the work of
> > > > > vhost_verify_ring_mappings.    
> > > > Isn't memmap list a sorted and
> > > >  dev->mem_changed_[start|end]_addr are the lowest|highest
> > > > addresses of whole map?
> > > > 
> > > > If it's, so wouldn't getting values directly from 
> > > > the 1st/last entries of array be sufficient?    
> > > 
> > > THat wasn't my understanding from the existing code;
> > > my understanding was that changed_start_addr is set by
> > > vhost_region_add->vhost_set_memory when a new region is added
> > > (or removed) and is set to the limit of the section added.
> > > But perhaps I'm misunderstanding.  
> > changed_*_addr is actually lower/upper bound of memory transaction
> > and in practice it often includes several memory sections that
> > get mapped during transaction (between begin - commit).
> > 
> > but then again,
> >   - how expensive vhost_verify_ring_mappings() is?
> >   - do we really need optimization here (perhaps finding out changed range is more expensive)?
> >   - how about calling vhost_verify_ring_mappings() unconditionally?  
> 
> My worry is that:
>     vhost_verify_ring_mappings
>        vhost_verify_ring_part_mapping
>           vhost_verify_ring_part_mapping
>              vhost_memory_map & vhost_memory_unmap
>                (non-iommu case...)
>                cpu_physical_memory_map & cpu_physical_memory_unmap
>                  address_space_map/address_space_unmap
>                     flatview_translate etc
> 
> so it's not cheap at all - I *think* it should end up doing very little
> after it's gone all the way through that because it should already be
> mapped; but still it's not trivial.
neither trivial finding out changed range.
How often it will be called and what actual time it takes
for vhost_verify_ring_mappings and vhost_update_compare_list to complete.

note 
vhost_memory_map() would be run only on ranges that
overlap with rings (typically 1), while vhost_update_compare_list()
would go over all ranges.
So question is does optimization really saves us anything?


> 
> Dave
> 
> >   
> > > (The logic in vhost_verify_ring_mappings doesn't make sense
> > > to me either though; if vhost_verify_ring_part_mapping returns 0
> > > on success, why is it doing   if (!r) { break; }  surely it
> > > should be  if (r) { break; })  
> > it looks like a bug (CCing Greg)
> > 
> > before (f1f9e6c5 vhost: adapt vhost_verify_ring_mappings() to virtio 1 ring layout)
> > logic used to be
> > 
> >    if changed_*_addr doesn't contain ring
> >       "IGNORE as we don't care"
> >    
> >    if changed_*_addr contain ring AND ring can't be mapped at the same place
> >       ABORT
> > 
> > with f1f9e6c5 we have 3 rings so on any of them following could happen
> >    if "IGNORE as we don't care"
> >      break => false success 
> >      since it's possible that the remaining rings in vq do overlap and didn't get checked
> >   
> --
> Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

* Igor Mammedov (imammedo@redhat.com) wrote:
> On Thu, 30 Nov 2017 15:18:55 +0000
> "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> 
> > * Igor Mammedov (imammedo@redhat.com) wrote:
> > > On Thu, 30 Nov 2017 13:06:29 +0000
> > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > >   
> > > > * Igor Mammedov (imammedo@redhat.com) wrote:  
> > > > > On Thu, 30 Nov 2017 12:47:20 +0000
> > > > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > > > >     
> > > > > > * Igor Mammedov (imammedo@redhat.com) wrote:    
> > > > > > > On Thu, 30 Nov 2017 12:08:06 +0000
> > > > > > > "Dr. David Alan Gilbert" <dgilbert@redhat.com> wrote:
> > > > > > >       
> > > > > > > > * Igor Mammedov (imammedo@redhat.com) wrote:      
> > > > > > > > > On Wed, 29 Nov 2017 18:50:19 +0000
> > > > > > > > > "Dr. David Alan Gilbert (git)" <dgilbert@redhat.com> wrote:
> > > > > > > > >         
> > > > > > > > > > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > > > > > > > > > 
> > > > > > > > > > Hi,
> > > > > > > > > >   This is an experimental set that reworks the way the vhost
> > > > > > > > > > code handles changes in physical address space layout that
> > > > > > > > > > came from a discussion with Igor.        
> > > > > > > > > Thanks for looking into it.
> > > > > > > > > 
> > > > > > > > >          
> > > > > > > > > > Instead of updating and trying to merge sections of address
> > > > > > > > > > space on each add/remove callback, we wait until the commit phase
> > > > > > > > > > and go through and rebuild a list by walking the Flatview of
> > > > > > > > > > memory and end up producing an ordered list.
> > > > > > > > > > We compare the list to the old list to trigger updates.
> > > > > > > > > > 
> > > > > > > > > > Note, only very lightly tested so far, I'm just trying to see if it's
> > > > > > > > > > the right shape.
> > > > > > > > > > 
> > > > > > > > > > Igor, is this what you were intending?        
> > > > > > > > > 
> > > > > > > > > I was thinking about a little less intrusive approach
> > > > > > > > > 
> > > > > > > > > where vhost_region_add/del are modified to maintain
> > > > > > > > > sorted by GPA array of mem_sections, vhost_dev::mem is dropped
> > > > > > > > > altogether and vhost_memory_region array is build/used/freed
> > > > > > > > > on every vhost_commit().
> > > > > > > > > Maintaining sorted array should roughly cost us O(2 log n) if
> > > > > > > > > binary search is used.
> > > > > > > > > 
> > > > > > > > > However I like your idea with iterator even more as it have
> > > > > > > > > potential to make it even faster O(n) if we get rid of
> > > > > > > > > quadratic and relatively complex vhost_update_compare_list().        
> > > > > > > > 
> > > > > > > > Note vhost_update_compare_list is complex,
> > > > > > > > but it is O(n) - it's
> > > > > > > > got nested loops, but the inner loop moves forward and oldi never
> > > > > > > > gets reset back to zero.      
> > > > > > > While skimming through patches I've overlooked it.
> > > > > > > 
> > > > > > > Anyways,
> > > > > > > why memcmp(old_arr, new_arr) is not sufficient
> > > > > > > to detect a change in memory map?      
> > > > > > 
> > > > > > It tells you that you've got a change, but doesn't give
> > > > > > the start/end of the range that's changed, and those
> > > > > > are used by vhost_commit to limit the work of
> > > > > > vhost_verify_ring_mappings.    
> > > > > Isn't memmap list a sorted and
> > > > >  dev->mem_changed_[start|end]_addr are the lowest|highest
> > > > > addresses of whole map?
> > > > > 
> > > > > If it's, so wouldn't getting values directly from 
> > > > > the 1st/last entries of array be sufficient?    
> > > > 
> > > > THat wasn't my understanding from the existing code;
> > > > my understanding was that changed_start_addr is set by
> > > > vhost_region_add->vhost_set_memory when a new region is added
> > > > (or removed) and is set to the limit of the section added.
> > > > But perhaps I'm misunderstanding.  
> > > changed_*_addr is actually lower/upper bound of memory transaction
> > > and in practice it often includes several memory sections that
> > > get mapped during transaction (between begin - commit).
> > > 
> > > but then again,
> > >   - how expensive vhost_verify_ring_mappings() is?
> > >   - do we really need optimization here (perhaps finding out changed range is more expensive)?
> > >   - how about calling vhost_verify_ring_mappings() unconditionally?  
> > 
> > My worry is that:
> >     vhost_verify_ring_mappings
> >        vhost_verify_ring_part_mapping
> >           vhost_verify_ring_part_mapping
> >              vhost_memory_map & vhost_memory_unmap
> >                (non-iommu case...)
> >                cpu_physical_memory_map & cpu_physical_memory_unmap
> >                  address_space_map/address_space_unmap
> >                     flatview_translate etc
> > 
> > so it's not cheap at all - I *think* it should end up doing very little
> > after it's gone all the way through that because it should already be
> > mapped; but still it's not trivial.
> neither trivial finding out changed range.
> How often it will be called and what actual time it takes
> for vhost_verify_ring_mappings and vhost_update_compare_list to complete.
> 
> note 
> vhost_memory_map() would be run only on ranges that
> overlap with rings (typically 1), while vhost_update_compare_list()
> would go over all ranges.
> So question is does optimization really saves us anything?

Frankly I don't know - I mean what causes and how often are these
changes anyway?  In my setup here I don't normally see any.
vhost_update_compare_list is a bit complex - but it is O(n) and none of
the things it does are actually expensive - they're just simple min/max;
so it should be pretty cheap.  The case where the entries match is
especially cheap.

Dave

> 
> > 
> > Dave
> > 
> > >   
> > > > (The logic in vhost_verify_ring_mappings doesn't make sense
> > > > to me either though; if vhost_verify_ring_part_mapping returns 0
> > > > on success, why is it doing   if (!r) { break; }  surely it
> > > > should be  if (r) { break; })  
> > > it looks like a bug (CCing Greg)
> > > 
> > > before (f1f9e6c5 vhost: adapt vhost_verify_ring_mappings() to virtio 1 ring layout)
> > > logic used to be
> > > 
> > >    if changed_*_addr doesn't contain ring
> > >       "IGNORE as we don't care"
> > >    
> > >    if changed_*_addr contain ring AND ring can't be mapped at the same place
> > >       ABORT
> > > 
> > > with f1f9e6c5 we have 3 rings so on any of them following could happen
> > >    if "IGNORE as we don't care"
> > >      break => false success 
> > >      since it's possible that the remaining rings in vq do overlap and didn't get checked
> > >   
> > --
> > Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK
> 
--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK

On Thu, 30 Nov 2017 16:08:44 +0100
Igor Mammedov <imammedo@redhat.com> wrote:
[...]
> > (The logic in vhost_verify_ring_mappings doesn't make sense
> > to me either though; if vhost_verify_ring_part_mapping returns 0
> > on success, why is it doing   if (!r) { break; }  surely it
> > should be  if (r) { break; })  
> it looks like a bug (CCing Greg)
> 

Wow! It's obviously a bug indeed and I'm amazed it didn't get caught
during the review :-\

I'll send a patch ASAP.

> before (f1f9e6c5 vhost: adapt vhost_verify_ring_mappings() to virtio 1 ring layout)
> logic used to be
> 
>    if changed_*_addr doesn't contain ring
>       "IGNORE as we don't care"
>    
>    if changed_*_addr contain ring AND ring can't be mapped at the same place
>       ABORT
> 
> with f1f9e6c5 we have 3 rings so on any of them following could happen
>    if "IGNORE as we don't care"
>      break => false success 
>      since it's possible that the remaining rings in vq do overlap and didn't get checked
> 

On Wed, Nov 29, 2017 at 06:50:19PM +0000, Dr. David Alan Gilbert (git) wrote:
> From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> 
> Hi,
>   This is an experimental set that reworks the way the vhost
> code handles changes in physical address space layout that
> came from a discussion with Igor.
> 
> Instead of updating and trying to merge sections of address
> space on each add/remove callback, we wait until the commit phase
> and go through and rebuild a list by walking the Flatview of
> memory and end up producing an ordered list.
> We compare the list to the old list to trigger updates.
> 
> Note, only very lightly tested so far, I'm just trying to see if it's
> the right shape.

The cover letter doesn't mention why this change is necessary.  It would
be helpful to know :).

Stefan

* Stefan Hajnoczi (stefanha@gmail.com) wrote:
> On Wed, Nov 29, 2017 at 06:50:19PM +0000, Dr. David Alan Gilbert (git) wrote:
> > From: "Dr. David Alan Gilbert" <dgilbert@redhat.com>
> > 
> > Hi,
> >   This is an experimental set that reworks the way the vhost
> > code handles changes in physical address space layout that
> > came from a discussion with Igor.
> > 
> > Instead of updating and trying to merge sections of address
> > space on each add/remove callback, we wait until the commit phase
> > and go through and rebuild a list by walking the Flatview of
> > memory and end up producing an ordered list.
> > We compare the list to the old list to trigger updates.
> > 
> > Note, only very lightly tested so far, I'm just trying to see if it's
> > the right shape.
> 
> The cover letter doesn't mention why this change is necessary.  It would
> be helpful to know :).

The hope was to simplify it, and in particular make it easier for me
to add the bits I needed for postcopy support;  in the current code it
does a fairly complex merge procedure on each section ad/del call and
doesn't keep the structures in order.   Trying to add any more rules to
that just makes it more and more complex.

The hope is that this is simpler because we just do a linear walk of the
set of sections, which means any merging just happens with the top
element, and also the list is in order that's easier to work with.
Then it should be easier for me to add the postcopy stuff which needs
to do some hugepage merging.

(Bizarrely, after having rewritten the code from scratch completely
differently, the LoC is within a few lines of each other)

Dave

> Stefan


--
Dr. David Alan Gilbert / dgilbert@redhat.com / Manchester, UK