Re: objrmap and vmtruncate

Andrea Arcangeli
2003-04-05T22:06:21Z

On Sat, Apr 05, 2003 at 01:24:06PM -0800, Andrew Morton wrote:
> 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.

I see what you mean, you're right. That's because all the 10,000 vma
belongs to the same inode.

Andrea