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

From	Jason Wang <jasowang@redhat.com>
Newsgroups	linux.kernel
Subject	Re: [PATCH RFC] vhost: convert pre sorted vhost memory array to interval tree
Date	2016-01-20 04:00 +0100
Message-ID	<qSRa4-5e-63@gated-at.bofh.it> (permalink)
References	<qS83f-2Kh-1@gated-at.bofh.it> <qSGoh-1fW-5@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw


On 01/19/2016 11:24 PM, Igor Mammedov wrote:
> On Mon, 18 Jan 2016 10:42:29 +0800
> Jason Wang <jasowang@redhat.com> wrote:
>
>> > 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

Back to linux.kernel | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

[PATCH RFC] vhost: convert pre sorted vhost memory array to interval tree Jason Wang <jasowang@redhat.com> - 2016-01-18 03:50 +0100
  Re: [PATCH RFC] vhost: convert pre sorted vhost memory array to  interval tree Igor Mammedov <imammedo@redhat.com> - 2016-01-19 16:30 +0100
    Re: [PATCH RFC] vhost: convert pre sorted vhost memory array to  interval tree Jason Wang <jasowang@redhat.com> - 2016-01-20 04:00 +0100

csiph-web