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

[Tim Deegan <tim@xen.org>]

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.

Tim.