[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Xen-devel] [PATCH 3 of 3] x86/mem_sharing: For shared pages with many references, use a hash table instead of a list
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
>>> store the rmap results in costly scans during unshare operations. To
>>> 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
>>> for a domain that points over 100 thousand pages to the same shared
>>> domain destruction dropped from over 7 minutes(!) to less than two
>> 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
> 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.
Xen-devel mailing list