lkml.org 
[lkml]   [2003]   [Apr]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: objrmap and vmtruncate
    Andrea Arcangeli <andrea@suse.de> wrote:
    >
    > On Sat, Apr 05, 2003 at 04:06:14AM -0800, Andrew Morton wrote:
    > > Andrew Morton <akpm@digeo.com> 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.

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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