Re: objrmap-core-1 (rmap removal for file mappings to avoid 4:4 in <=16G machines)

From: Ingo Molnar <mingo@elte.hu>
To: Andrea Arcangeli <andrea@suse.de>
Cc: Andrew Morton <akpm@osdl.org>,
	torvalds@osdl.org, linux-kernel@vger.kernel.org
Subject: Re: objrmap-core-1 (rmap removal for file mappings to avoid 4:4 in <=16G machines)
Date: Tue, 9 Mar 2004 09:31:03 +0100	[thread overview]
Message-ID: <20040309083103.GB8021@elte.hu> (raw)
In-Reply-To: <20040308234014.GG12612@dualathlon.random>

* Andrea Arcangeli <andrea@suse.de> wrote:

> btw (for completeness), about the cpu consumption concerns about
> objrmap w.r.t. security (that was Ingo's only argument against
> objrmap),

ugh? This is not my main argument against 'objrmap'. My main (and pretty
much only) argument against it is the linear searching it reintroduces.
I.e. in your patch you do this, in 3 key areas:

 +int page_convert_anon(struct page *page)
 ...
 +       list_for_each_entry(vma, &mapping->i_mmap, shared) {
 ...
 +       list_for_each_entry(vma, &mapping->i_mmap_shared, shared) {
 ...

 +static int
 +page_referenced_obj(struct page *page)
 ...
 +       list_for_each_entry(vma, &mapping->i_mmap, shared)
 ...
 +       list_for_each_entry(vma, &mapping->i_mmap_shared, shared)
 ...

 +static int
 +try_to_unmap_obj(struct page *page)
 ...
 +       list_for_each_entry(vma, &mapping->i_mmap, shared) {
 ...
 +       list_for_each_entry(vma, &mapping->i_mmap_shared, shared) {
 ...

the length of these lists ~equals to the number of processes mapping
said inode (the 'sharing factor'). I.e. the more processes, the bigger
box, the longer lists. The more advanced computers get, the longer the
lists get too. A scalability nightmare in the making.

with rmap we do have the ability to make it truly O(1) all across, by
making the pte chains a double linked list. Moreover, we can freely
reduce the rmap overhead (both the memory, algorithmic and locking
overhead) by increasing the page size - a natural thing to do on big
boxes anyway. The increasing of the page size also linearly _reduces_
the RAM footprint of rmap. So rmap and pgcl are a natural fit and the
thing of the future.

now, the linear searching of vmas does not reduce with increased
page-size. In fact, it will increase in time as the sharing factor
increases.

do you see what i'm worried about?

	Ingo