Re: [PATCH 3 of 3] x86/mem_sharing: For shared pages with many references, use a hash table instead of a list

[Andres Lagar-Cavilla <andreslc@gridcentric.ca>]

On Apr 18, 2012, at 12:18 PM, Andres Lagar-Cavilla wrote:

>> At 10:16 -0400 on 12 Apr (1334225774), Andres Lagar-Cavilla wrote:
>>> xen/arch/x86/mm/mem_sharing.c     |  170
>>> +++++++++++++++++++++++++++++++++++--
>>> xen/include/asm-x86/mem_sharing.h |   13 ++-
>>> 2 files changed, 169 insertions(+), 14 deletions(-)
>>> 
>>> 
>>> For shared frames that have many references, the doubly-linked list used
>>> to
>>> store the rmap results in costly scans during unshare operations. To
>>> alleviate
>>> the overhead, replace the linked list by a hash table. However, hash
>>> tables are
>>> space-intensive, so only use them for pages that have "many" (arbitrary
>>> threshold) references.
>>> 
>>> Unsharing is heaviliy exercised during domain destroy. In experimental
>>> testing,
>>> for a domain that points over 100 thousand pages to the same shared
>>> frame,
>>> domain destruction dropped from over 7 minutes(!) to less than two
>>> seconds.
>> 
>> If you're adding a new datastructure, would it be better to use a tree,
>> since the keys are easily sorted?  Xen already has include/xen/rbtree.h.
>> It would have a higher per-entry overhead but you wouldn't need to keep
>> the list datastructure as well for the light-sharing case.
> 
> My main concern is space. A regular case we deal with is four hundred
> thousand shared frames, most with roughly a hundred <domid,gfn>s they
> back, some with over a hundred thousand, a few with less than ten
> thousand. That's a lot of heap memory for rb trees and nodes! I find O(n)
> on less than 256 to be easily tolerable, as well as spending an extra page
> only when we're saving thousands.

I've looked into rb and my initial opinion stands. I'm confident I'm getting a better space/search-big-O tradeoff with my hash table instead of an rb tree. I have not, however, conducted a thorough profiling, given the time constraints for 4.2. That is certainly doable after that window closes.

I will resubmit the series taking into account your comment about splitting the initial patch.

Thanks!
Andres

> 
> 
> Nevertheless I'll look into rb tree. Whose only consumer is tmem, if I'm
> not mistaken. It doesn't seem like pool objects grow to contain so many
> pages, but I could be wrong.
> 
> Andres
>> 
>> Tim.
>> 
>> 
> 
>