Re: objrmap and vmtruncate

[Andrew Morton]

Andrea Arcangeli <[e-mail]> wrote:
>
> On Sat, Apr 05, 2003 at 04:06:14AM -0800, Andrew Morton wrote:
> > Andrew Morton <[e-mail]> wrote:
> > >
> > > Nobody has written an "exploit" for this yet, but it's there.
> > 
> > Here we go.  The test app is called `rmap-test'.  It is in ext3 CVS.  See
> > 
> > 	http://www.zip.com.au/~akpm/linux/ext3/
> > 
> > It sets up N MAP_SHARED VMA's and N tasks touching them in various access
> > patterns.
> 
> I'm not questioning during paging rmap is more efficient than objrmap,
> but your argument about rmap having lower complexity of objrmap and that
> rmap is needed is wrong. The fact is that with your 100 mappings per
> each of the 100 tasks case, both algorithms works in O(N) where N is
> the number of the pagetables mapping the page.

Nope.  To unmap a page, full rmap has to scan 100 pte_chain slots, which is 3
cachelines worth.  objrmap has to scan 10,000 vma's, 9,900 of which do not map
that page at all.

(Actually, there's a recent optimisation in objrmap which will on average
halve these figures).

> And objrmap can't avoided, it's needed for the truncate semantics
> against mmap.

What do you mean by this?  vmtruncate continues to use the 2.4 algorithm for
that.

> Check all other important benchmarks not testing the paging load like
> page faults, kernel compile from Martin, fork, AIM etc... Those are IMHO
> an order of magnitude of more interest than your rmap-test paging load
> with some hundred thousand of vmas.

Andrea, I whine about rmap as much as anyone ;) I'm the guy who halved both
its speed and space overhead shortly after it was merged.

But the fact is that it is not completely useless overhead.  It provides a
very robust VM which is stable and predictable under extreme and unusual
loads.  That is valuable.

Yes, rmap adds a few% speed overhead - up to 10% for things which are
admittedly already very inefficient.

objrmap will reclaim a lot of that common-case overhead.  But the cost of
that is apparently unviability for certain workloads on certain machines. 
Once you hit 100k VMA's it's time to find a new operating system.

Maybe that is a tradeoff we want to make.  I'm adding some balance here.

The space consumption of rmap is a much more serious problem than the speed
overhead.  It makes some workloads on huge ia32 machines unviable.

Me, I have never seen any evidence that we need any of it.  I have never seen
a demonstration of the alleged failure modes of 2.4's virtual scan.  But then
I haven't tried very hard.

The extreme stability and scalability of full rmap is good.  The space
consumption on highmem is bad.  The CPU cost is much less important than
these things.