Re: bug #5493

Andrew Morton
2007-11-09T04:27:07Z

> On Thu, 8 Nov 2007 20:00:41 -0500 Rik van Riel <riel@redhat.com> wrote:
> On Thu, 8 Nov 2007 10:56:59 -0800
> Andrew Morton <akpm@linux-foundation.org> wrote:
> > > On Thu, 8 Nov 2007 13:15:18 -0500 Rik van Riel <riel@redhat.com> wrote:
> > > On Thu, 8 Nov 2007 09:57:04 -0800
>
> > > > No, it was due to linear traversal of very long reverse-mapping lists
> > > > (thousands of elements, irrc).
> > >
> > > Traversal at pageout time, or at mprotect time?
> > >
> >
> > pageout, iirc. For each page we were walking a linear list of I think
> > ~10,000 elements.
>
> Pageout scan complexity in this workload is O(P*M), where
> P is the number of pages scanned and M is the number of
> mappings.
>
> My code will, in the next iteration, reduce P by a fair
> amount for larger amounts of memory, but M is still very
> large...

That's yet to be proven - for the vast majority of workloads your P is
already very small.

> I might use this test case to play with the SEQ replacement
> of anonymous pages. Figuring out how to avoid some worst
> case that people really hit in practice is often educational.

I don't think we can anywhere near fix this without basic redesign of VM
data structures and the relationship between them.