objrmap-core-1 (rmap removal for file mappings to avoid 4:4 in <=16G machines)
A message that is not in the archive (sent off-list or not yet received): [email protected]
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
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).
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 withvma_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
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 withvma_split.Why do you have to fix up all page structs' PageDirect and as.vma fields when a
vma_splitorvma_mergeoccurs.Can't you do it lazily on the next
page_referencedorpage_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_vmausingas.vma->anon_vma.I understand that currenly your code assumes that if PageDirect is set, then there cannot be an
anon_vmacorresponding 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.
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
Re: anon_vma RFC2
Quoted 13 lines
The only problem is
mremap()after afork(), and hell, we know that's a special case anyway, and let's just add a few lines tocopy_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
Re: anon_vma RFC2
Quoted 13 lines · Rajesh Venkatasubramanian
Quoted 13 lines
The only problem is
mremap()after afork(), and hell, we know that's a special case anyway, and let's just add a few lines tocopy_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). Theprio_treeeasily 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.
Re: anon_vma RFC2
Quoted 5 lines
prio_treecan only sit on top ofanon_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 theanon_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
Re: anon_vma RFC2
Quoted 5 lines · Rajesh Venkatasubramanian
Agreed.
prio_treeis only useful foranon_vma. But, after linus-unshare-mremap, theanon_vmapatch 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 existingpage->mappingandpage->index, and aprio_treeof 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.
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_treetaking pgoff into account isn't needed there,find_vmais 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
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.
Butfind_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
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
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->lruas 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
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
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
Re: anon_vma RFC2
In reply to William Lee Irwin IIIQuoted 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