Re: objrmap and vmtruncate

[Rik van Riel <riel@imladris.surriel.com>]

On Sat, 5 Apr 2003, Andrea Arcangeli wrote:

> 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. No difference in
> complexity.  I don't care how many cycles you spend to reach the 100x100
> pagetables, those are fixed cycles, the fact is that there are 100x100
> pagetables,

Umm no.  The fact that a VMA is "mapping" the page doesn't
mean the page is resident in any page tables.   For example,
think about the MAP_PRIVATE mapping of the relocation tables
from libc.so ... every process will have its own, modified,
copy of that data.  The original page might not be mapped by
the page tables of any processes.

> rmap won't change the complexity of the algorithm at all,

It will for some cases (as shown above), but I agree that for
most common situations objrmap and pte rmap should have very
similar algorithmic complexity in the pageout path.

> that's mandated by the hardware and by your application, we can't do
> better than O(N) with N the number of pagetables to unmap a single page.
> Even rmap has the O(N) complexity, it won't be allowed to reach only 100
> pagetables instead of 100000 pagetables.

There is one common situation where objrmap is O(N^2) while
pte rmap is only O(N).  However, this case isn't interesting
because this workload tends to run mlocked anyway.

This is, of course, Oracle on 32 bit systems with gazillions
of windows into the larger-than-virtual-memory shared memory
area.

This aspect of Oracle can be special-cased with remap_file_pages
and the reverse mapping can be skipped alltogether since Oracle's
shared memory area should (IMHO) be mlocked anyway.

In short, I agree with you that we probably want object rmap for
all the common cases.

cheers,

Rik
-- 
Engineers don't grow up, they grow sideways.
http://www.surriel.com/		http://kernelnewbies.org/
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"aart@kvack.org">aart@kvack.org</a>