Skip to contentSkip to conversation

objrmap-core-1 (rmap removal for file mappings to avoid 4:4 in <=16G machines)

lockup Rik van Riel 5 participants 16 messages Mar 10, 2004 – Mar 14, 2004 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 6 lines · Andrea Arcangeli
Quoted 1 line · Andrea Arcangeli

We've lot of room for improvements.

Rajesh has a smart idea on how to fix the complexity issue (for both truncate and vm) and it involes a new non trivial data structure.

Quoted 6 lines

I trust he will make it, but if there will be any trouble with his approch for safety I'm currently planning on a simpler fallback solution that I can manage without having to design a new tree data structure.

Sharing his "tree and sorting" idea, the fallback I propose is to simply index the vmas in a rbtree too.

That simply results in looking up less VMAs for low file indexes, but still needing to check all of them for high file indexes.

You really want to sort on both the start and end offset of the VMA, as can be done with a kd-tree or kdb-tree.

Signature · 3 lines
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
#2 lore raw
Quoted 14 lines · Rik van Riel
Quoted 6 lines · Andrea Arcangeli
Quoted 1 line · Andrea Arcangeli

We've lot of room for improvements.

Rajesh has a smart idea on how to fix the complexity issue (for both truncate and vm) and it involes a new non trivial data structure.

Quoted 6 lines

I trust he will make it, but if there will be any trouble with his approch for safety I'm currently planning on a simpler fallback solution that I can manage without having to design a new tree data structure.

Sharing his "tree and sorting" idea, the fallback I propose is to simply index the vmas in a rbtree too.

Quoted 6 lines

That simply results in looking up less VMAs for low file indexes, but still needing to check all of them for high file indexes.

You really want to sort on both the start and end offset of the VMA, as can be done with a kd-tree or kdb-tree.

yes. But the only single reason for me to even consider using the rbtree was to avoid having to introduce another data structure and to feel very safe in terms of risks of memory corruption in the short term ;). The rbtree is extremely well exercised, that's the only reason I suggested it. Rajesh is currently working on another data strucure that is efficient at finding a "range" (not sure if it is what you're suggesting, he called it a prio_tree, mix between hashes and raidx trees), that's optimal, though in practice the rbtree would work too (peraphs one could still work an exploit ;) but the the real life apps would be definitely covered by the rbtree too (since all vma are of the same size and they're all naturally aligned).

#3 lore raw

Re: anon_vma RFC2

Quoted 7 lines
Quoted 4 lines

have a devastating effect on vma usage, yes) issue of vma merging, but what about the (mandatory) vma splitting? ...[snip]

you're right about vma_split, the way I implemented it is wrong, basically the as.vma/PageDirect idea is falling apart with vma_split.

Why do you have to fix up all page structs' PageDirect and as.vma fields when a vma_split or vma_merge occurs.

Can't you do it lazily on the next page_referenced or page_add_rmap, etc. Anyway we can get to the anon_vma using as.vma->anon_vma.

I understand that currenly your code assumes that if PageDirect is set, then there cannot be an anon_vma corresponding to the page.

Rajesh

#4 lore raw

Re: anon_vma RFC2

Quoted 5 lines · Rajesh Venkatasubramanian
Quoted 4 lines
Quoted 4 lines

have a devastating effect on vma usage, yes) issue of vma merging, but what about the (mandatory) vma splitting? ...[snip]

Quoted 7 lines
Quoted 2 lines

you're right about vma_split, the way I implemented it is wrong, basically the as.vma/PageDirect idea is falling apart with vma_split.

Why do you have to fix up all page structs' PageDirect and as.vma fields when a vma_split or vma_merge occurs.

Can't you do it lazily on the next page_referenced or page_add_rmap,

I cannot do it lazily unfortunately because the paging routine will start from the page, so if the page is not uptodate it will go to read into nirvana.

Quoted 4 lines

etc. Anyway we can get to the anon_vma using as.vma->anon_vma.

I understand that currenly your code assumes that if PageDirect is set, then there cannot be an anon_vma corresponding to the page.

correct, though I will have to change that for the above problem ;(

Well, another way is to just do the pagetable walk and fixup the page->as.vma to be a page->as.anon_vma during split/merge (actually merge is already taken care of by forbidding merging in the interesting cases, what I missed was the split, oh well ;). But preallocating the anon_vma is such a little cost that it should be a lot better than slowing down the split.

#5 lore raw

Re: anon_vma RFC2

Quoted 7 lines
Quoted 6 lines

I think your approach could work (reverse map by having separate address
spaces for unrelated processes), but I don't see any good "page->index" allocation scheme that is implementable.

Quoted 7 lines
Quoted 1 line

Or did I totally mis-understand what you were proposing?

You're absolutely right. I am still trying to come up with a way to do this.
[snip]

I just can't think of any now ...

Atleast one solution exists. It may be just an academic solution, though.

Add a new prio_tree root "remap_address" to anonmm address_space structure.

struct anon_remap_address {
	unsigned long old_page_index_start;
	unsigned long old_page_index_end;
	unsigned long new_page_index;
	struct prio_tree_node prio_tree_node;
}

For each mremap that expands the area and moves the page tables, allocate a new anon_remap_address struct and add to remap_address tree.

The page->index does not change ever. Take the page->index and walk remap_address tree to find all remapped addresses. Once a list of all remapped addresses are found, it's easy to find the interesting vmas (again using a different prio_tree). Finding all remapped addresses may involve recursion, that's bad.

Rajesh

#6 lore raw

Re: anon_vma RFC2

Quoted 13 lines

The only problem is mremap() after a fork(), and hell, we know that's a special case anyway, and let's just add a few lines to copy_one_pte(), which basically does:

	if (PageAnonymous(page) && page->count > 1) {
		newpage = alloc_page();
		copy_page(page, newpage);
		page = newpage;
	}
	/* Move the page to the new address */
	page->index = address >> PAGE_SHIFT;
Quoted 1 line

and now we have zero special cases.

This part makes the problem so simple. If this is acceptable, then we have many choices. Since we won't have many mms in the anonmm list, I don't think we will have any search complexity problems. If we really worry again about search complexity, we can consider using prio_tree (adds 16 bytes per vma - we cannot share vma.shared.prio_tree_node). The prio_tree easily fits for anonmm after linus-mremap-simplification.

Rajesh

#7 lore raw

Re: anon_vma RFC2

Quoted 13 lines · Rajesh Venkatasubramanian
Quoted 13 lines

The only problem is mremap() after a fork(), and hell, we know that's a special case anyway, and let's just add a few lines to copy_one_pte(), which basically does:

	if (PageAnonymous(page) && page->count > 1) {
		newpage = alloc_page();
		copy_page(page, newpage);
		page = newpage;
	}
	/* Move the page to the new address */
	page->index = address >> PAGE_SHIFT;
Quoted 8 lines
Quoted 1 line

and now we have zero special cases.

This part makes the problem so simple. If this is acceptable, then we have many choices. Since we won't have many mms in the anonmm list, I don't think we will have any search complexity problems. If we really worry again about search complexity, we can consider using prio_tree (adds 16 bytes per vma - we cannot share vma.shared.prio_tree_node). The prio_tree easily fits for anonmm after linus-mremap-simplification.

prio_tree with linus-mremap-simplification makes no sense to me. You cannot avoid checking all the mm with the prio_tree and that is the only complexity issue introduced by anonmm vs anon_vma.

prio_tree can only sit on top of anon_vma, not on top of anonmm+linus-unshare-mremap (and yes, I cannot share vma.shared.prio_tree_node) but pratically it's not needed for the anon_vmas.

#8 lore raw

Re: anon_vma RFC2

Quoted 5 lines

prio_tree can only sit on top of anon_vma, not on top of anonmm+linus-unshare-mremap (and yes, I cannot share vma.shared.prio_tree_node) but pratically it's not needed for the anon_vmas.

Agreed. prio_tree is only useful for anon_vma. But, after linus-unshare-mremap, the anon_vma patch can be modified (simplified ?) a lot. You don't need any as.anon_vma, as.vma pointers in the page struct. You just need the already existing page->mapping and page->index, and a prio_tree of all anon vmas. The prio_tree can be used to get to the "interesting vmas" without walking all mms. However, the new prio_tree node adds 16 bytes per-vma. Considering there may not be much sharing of anon vmas in common case, I am not sure whether that is worthwhile. Maybe we can wait for someone to write a program that locks the machine :)

Rajesh

#9 lore raw

Re: anon_vma RFC2

Quoted 5 lines · Rajesh Venkatasubramanian

Agreed. prio_tree is only useful for anon_vma. But, after linus-unshare-mremap, the anon_vma patch can be modified (simplified ?) a lot. You don't need any as.anon_vma, as.vma pointers in the page struct. You just need the already existing page->mapping and page->index, and a prio_tree of all anon vmas.

what you are missing is that we don't need a prio_tree at all with anonmm+linus-unshare-mremap, prio tree can make sense only with anon_vma, not with anonmm. the vm_pgoff is meaningless with anonmm. find_vma (and the rbtree) already does the trick with anonmm. the linus-unshare-mremap guarantees that a certain physical page will be only at a certain virtual address in every mm, so prio_tree taking pgoff into account isn't needed there, find_vma is more than enough.

any prio_tree can't fix anyways the problem that anonmm will force the vm to scan all mm at the page->index address, even for a newly allocated malloc region. that is optimized away by anon_vma, plus anon_vma avoids the early-COW in mremap. the relevant downside of anon_vma is that it takes some more byte in the vma to provide those features.

#10 lore raw

Re: anon_vma RFC2

Quoted 4 lines · Andrea Arcangeli

linus-unshare-mremap guarantees that a certain physical page will be only at a certain virtual address in every mm, so prio_tree taking pgoff into account isn't needed there, find_vma is more than enough.

Yes. However, I'd at least personally hope that we don't even need the find_vma() all the time.

When removing a page using the reverse mapping, there really is very little reason to even look up the vma, although right now the "flush_tlb_page()" interface is done for vma only so we'd need to change that or at least add a "flush_tlb_page_mm(mm, virt)" flusher (and if any architecture wants to look up the vma, they could do so).

It would be silly to look up the vma if we don't actually need it, and I don't think we do. It's likely faster to just look up the page tables directly than to even worry about anything else.

But find_vma() certainly would be sufficient.

Linus

#11 lore raw

Re: anon_vma RFC2

Quoted 11 lines · Linus Torvalds

Yes. However, I'd at least personally hope that we don't even need the find_vma() all the time.
When removing a page using the reverse mapping, there really is very little reason to even look up the vma, although right now the "flush_tlb_page()" interface is done for vma only so we'd need to change that or at least add a "flush_tlb_page_mm(mm, virt)" flusher (and if any architecture wants to look up the vma, they could do so).
It would be silly to look up the vma if we don't actually need it, and I don't think we do. It's likely faster to just look up the page tables directly than to even worry about anything else.
But find_vma() certainly would be sufficient.

find_vma() is often necessary to determine whether the page is mlock()'d. In schemes where mm's that may not map the page appear in searches, it may also be necessary to determine if there's even a vma covering the area at all or otherwise a normal vma, since pagetables outside normal vmas may very well not be understood by the core (e.g. hugetlb).

-- wli

#12 lore raw

Re: anon_vma RFC2

Quoted 5 lines · William Lee Irwin III
Quoted 2 lines · Linus Torvalds

Yes. However, I'd at least personally hope that we don't even need the find_vma() all the time.

find_vma() is often necessary to determine whether the page is mlock()'d.

Alternatively, the mlock()d pages shouldn't appear on the LRU at all, reusing one of the variables inside page->lru as a counter to keep track of exactly how many times this page is mlock()d.

Quoted 4 lines

In schemes where mm's that may not map the page appear in searches, it may also be necessary to determine if there's even a vma covering the area at all or otherwise a normal vma, since pagetables outside normal vmas may very well not be understood by the core (e.g. hugetlb).

If the page is a normal page on the LRU, I suspect we don't need to find the VMA, with the exception of mlock()d pages...

Good thing Christoph was already looking at the mlock()d page counter idea.

Signature · 3 lines
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
#13 lore raw

Re: anon_vma RFC2

Quoted 1 line · William Lee Irwin III
Quoted 1 line

find_vma() is often necessary to determine whether the page is mlock()'d.

Quoted 4 lines · Rik van Riel

Alternatively, the mlock()d pages shouldn't appear on the LRU at all, reusing one of the variables inside page->lru as a counter to keep track of exactly how many times this page is mlock()d.

That would be the rare case where it's not necessary. =)

Quoted 4 lines · William Lee Irwin III
Quoted 4 lines

In schemes where mm's that may not map the page appear in searches, it may also be necessary to determine if there's even a vma covering the area at all or otherwise a normal vma, since pagetables outside normal vmas may very well not be understood by the core (e.g. hugetlb).

Quoted 4 lines · Rik van Riel

If the page is a normal page on the LRU, I suspect we don't need to find the VMA, with the exception of mlock()d pages... Good thing Christoph was already looking at the mlock()d page counter idea.

That's not quite where the issue happens. Suppose you have a COW sharing group (called variously struct anonmm, struct anon, and so on by various codebases) where a page you're trying to unmap occurs at some virtual address in several of them, but others may have hugetlb vmas where that page is otherwise expected. On i386 and potentially others, the core may not understand present pmd's that are not mere pointers to ptes and other machine-dependent hugetlb constructs, so there is trouble. Searching the COW sharing group isn't how everything works, but in those cases where additionally you can find mm's that don't map the page at that virtual address and may have different vmas cover it, this can arise.

-- wli

#14 lore raw

Re: anon_vma RFC2

Quoted 1 line · William Lee Irwin III

[hugetlb at same address]

Well, we can find this merely by looking at the page tables themselves, so that shouldn't be a problem.

Quoted 4 lines

Searching the COW sharing group isn't how everything works, but in those cases where additionally you can find mm's that don't map the page at that virtual address and may have different vmas cover it, this can arise.

This could only happen when you truncate a file that's been mapped by various nonlinear VMAs, so truncate can't get rid of the pages...

I suspect there are two ways to fix that:
1) on truncate, scan ALL the ptes inside nonlinear VMAs and remove the pages
2) don't allow truncate on a file that's mapped with nonlinear VMAs

Either would work.

Signature · 3 lines
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan
#15 lore raw

Re: anon_vma RFC2

Quoted 1 line · William Lee Irwin III
Quoted 1 line

[hugetlb at same address]

Quoted 2 lines · Rik van Riel

Well, we can find this merely by looking at the page tables themselves, so that shouldn't be a problem.

Pagetables of a kind the core understands may not be present there. On ia32 one could in theory have a pmd_huge() check, which would in turn not suffice for ia64 and sparc64 hugetlb. These were only examples. Other unusual forms of mappings, e.g. VM_RESERVED and VM_IO, may also be bad ideas to trip over by accident.

Quoted 4 lines · William Lee Irwin III
Quoted 4 lines

Searching the COW sharing group isn't how everything works, but in those cases where additionally you can find mm's that don't map the page at that virtual address and may have different vmas cover it, this can arise.

Quoted 9 lines · Rik van Riel

This could only happen when you truncate a file that's been mapped by various nonlinear VMAs, so truncate can't get rid of the pages...
I suspect there are two ways to fix that:
1) on truncate, scan ALL the ptes inside nonlinear VMAs and remove the pages
2) don't allow truncate on a file that's mapped with nonlinear VMAs
Either would work.

I'm not sure how that came in. The issue I had in mind was strictly a matter of tripping over things one can't make sense of from pagetables alone in try_to_unmap().

COW-shared anonymous pages not unmappable via anonymous COW sharing groups arising from truncate() vs. remap_file_pages() interactions and failures to check for nonlinearly-mapped pages in pagetable walkers are an issue in general of course, but they just aren't this issue.

-- wli

#16 lore raw

Re: anon_vma RFC2

In reply to William Lee Irwin III
Quoted 6 lines · William Lee Irwin III

find_vma() is often necessary to determine whether the page is mlock()'d. In schemes where mm's that may not map the page appear in searches, it may also be necessary to determine if there's even a vma covering the area at all or otherwise a normal vma, since pagetables outside normal vmas may very well not be understood by the core (e.g. hugetlb).

Both excellent points. I guess we'll need the extra few cache misses. Dang.

Linus