From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Andres Lagar-Cavilla" 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 09:18:44 -0700 Message-ID: <1278bd7674af27a3858dae12a5f16d65.squirrel@webmail.lagarcavilla.org> References: <7b606c043208d98d218b.1334240174@xdev.gridcentric.ca> <20120418153530.GM7013@ocelot.phlegethon.org> Reply-To: andres@lagarcavilla.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: In-Reply-To: <20120418153530.GM7013@ocelot.phlegethon.org> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Tim Deegan 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. My main concern is space. A regular case we deal with is four hundred thousand shared frames, most with roughly a hundred 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. 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. > >