BACKPORT: vhost: convert pre sorted vhost memory array to interval tree

Current pre-sorted memory region array has some limitations for future
device IOTLB conversion:

1) need extra work for adding and removing a single region, and it's
   expected to be slow because of sorting or memory re-allocation.
2) need extra work of removing a large range which may intersect
   several regions with different size.
3) need trick for a replacement policy like LRU

To overcome the above shortcomings, this patch convert it to interval
tree which can easily address the above issue with almost no extra
work.

The patch could be used for:

- Extend the current API and only let the userspace to send diffs of
  memory table.
- Simplify Device IOTLB implementation.

Signed-off-by: Jason Wang <jasowang@redhat.com>
Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
(cherry picked from commit a9709d6874d55130663567577a9b05c35138cc6b)
[astrachan: Backported around stable backport 711df71 ("vhost_net: stop
            device during reset owner")]
Bug: 121166534
Test: Ran cuttlefish with android-4.4 + VSOCKETS, VMWARE_VMCI_VSOCKETS
Signed-off-by: Alistair Strachan <astrachan@google.com>
Change-Id: I51c7c7229908a5ce1f082a80eeda5a01e85c2234

0 files changed, 0 insertions, 0 deletions