From mboxrd@z Thu Jan 1 00:00:00 1970 From: Tim Deegan Subject: Re: [PATCH 3 of 3] x86/mem_sharing: For shared pages with many references, use a hash table instead of a list Date: Wed, 18 Apr 2012 16:35:30 +0100 Message-ID: <20120418153530.GM7013@ocelot.phlegethon.org> References: <7b606c043208d98d218b.1334240174@xdev.gridcentric.ca> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: Content-Disposition: inline In-Reply-To: <7b606c043208d98d218b.1334240174@xdev.gridcentric.ca> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Andres Lagar-Cavilla Cc: adin@gridcentric.ca, andres@gridcentric.ca, keir.xen@gmail.com, xen-devel@lists.xen.org List-Id: xen-devel@lists.xenproject.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.