Re: objrmap and vmtruncate

[Ingo Molnar]

On Tue, 22 Apr 2003, William Lee Irwin III wrote:

> > just create a sparse enough memory layout (one page mapped every 2MB) and
> > pagetable overhead will dominate. Is it a problem in practice? I doubt it,
> > and you get what you asked for, and you can always offset it with RAM.
> 
> Actually it wasn't from sparse memory, it was from massive sharing.
> Basically 10000 processes whose virtualspace was dominated by shmem
> shared across all of them.
> 
> On some reflection I suspect a variety of techniques are needed here.

there are two main techniques to reduce per-context pagetable-alike
overhead: 1) the use of pagetable sharing via CLONE_VM 2) the use of
bigger MMU units with a much smaller pagetable hw cost [hugetlbs].

all of this is true, and still remains valid. None of this changes the
fact that objrmap, as proposed, introduces a quadratic component to a
central piece of code. If then we should simply abort any mmap() attempt
that increases the sharing factor above a certain level, or something like
that.

using nonlinear mappings adds the overhead of pte chains, which roughly
doubles the pagetable overhead. (or companion pagetables, which triple the
pagetable overhead) Purely RAM-wise the break-even point is at around 8
pages, 8 pte chain entries make up for 64 bytes of vma overhead.

the biggest problem i can see is that we (well, the kernel) has to make a
judgement of RAM footprint vs. algorithmic overhead, which is apples to
oranges. Nonlinear vmas [or just linear vmas with pte chains installed],
while being only O(N), double/triple the pagetable overhead. objrmap
linear vmas, while having only the pagetable overhead, are O(N^2). [well,
it's O(N*M)]

RAM-footprint wise the boundary is clear: above 8 pages of granularity,
vmas with objrmap cost less RAM than nonlinear mappings.

CPU-time-wise the nonlinear mappings with pte chains always beat objrmap.

	Ingo