Re: [PATCH RFC] vhost: convert pre sorted vhost memory array to interval tree

On 01/19/2016 11:24 PM, Igor Mammedov wrote:

On Mon, 18 Jan 2016 10:42:29 +0800
Jason Wang [off-list ref] wrote:

quoted

quoted

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.

I'm curios how performance changes on translate_desc() hot-path in
default case and in the case of 256 memory regions?

Haven't measured this. But consider both methods are O(logN), should be
no noticeable difference. Will measure it in the future.

The main user is for the device IOTLB API[1], which:

- have thousands of userspace memory region sections
- may dynamically adding or removing one or some of the regions
- need a replacement algorithm like LRU

[1] https://lkml.org/lkml/2015/12/31/16