[lkml]   [2003]   [Apr]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: objrmap and vmtruncate
Andrea Arcangeli <> wrote:
> On Sat, Apr 05, 2003 at 04:06:14AM -0800, Andrew Morton wrote:
> > Andrew Morton <> 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
> >
> >
> >
> > 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

> 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.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:34    [W:0.166 / U:16.820 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site