Messages in this thread | | | Date | Tue, 22 Apr 2003 11:26:21 -0400 (EDT) | From | Ingo Molnar <> | Subject | Re: objrmap and vmtruncate |
| |
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
- 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/
| |