aboutsummaryrefslogtreecommitdiffstats
path: root/mm/memory.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 19:31:25 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:22:39 -0400
commit6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08 (patch)
tree422ed8d7ac2fe45069f20cfba84a9a097bf444af /mm/memory.c
parentfff3fd8a1210a165252cd7cd01206da7a90d3a06 (diff)
mm: replace vma prio_tree with an interval tree
Implement an interval tree as a replacement for the VMA prio_tree. The algorithms are similar to lib/interval_tree.c; however that code can't be directly reused as the interval endpoints are not explicitly stored in the VMA. So instead, the common algorithm is moved into a template and the details (node type, how to get interval endpoints from the node, etc) are filled in using the C preprocessor. Once the interval tree functions are available, using them as a replacement to the VMA prio tree is a relatively simple, mechanical job. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'mm/memory.c')
-rw-r--r--mm/memory.c9
1 files changed, 4 insertions, 5 deletions
diff --git a/mm/memory.c b/mm/memory.c
index e09c04813186..d205e4381a34 100644
--- a/mm/memory.c
+++ b/mm/memory.c
@@ -2801,14 +2801,13 @@ static void unmap_mapping_range_vma(struct vm_area_struct *vma,
2801 zap_page_range_single(vma, start_addr, end_addr - start_addr, details); 2801 zap_page_range_single(vma, start_addr, end_addr - start_addr, details);
2802} 2802}
2803 2803
2804static inline void unmap_mapping_range_tree(struct prio_tree_root *root, 2804static inline void unmap_mapping_range_tree(struct rb_root *root,
2805 struct zap_details *details) 2805 struct zap_details *details)
2806{ 2806{
2807 struct vm_area_struct *vma; 2807 struct vm_area_struct *vma;
2808 struct prio_tree_iter iter;
2809 pgoff_t vba, vea, zba, zea; 2808 pgoff_t vba, vea, zba, zea;
2810 2809
2811 vma_prio_tree_foreach(vma, &iter, root, 2810 vma_interval_tree_foreach(vma, root,
2812 details->first_index, details->last_index) { 2811 details->first_index, details->last_index) {
2813 2812
2814 vba = vma->vm_pgoff; 2813 vba = vma->vm_pgoff;
@@ -2839,7 +2838,7 @@ static inline void unmap_mapping_range_list(struct list_head *head,
2839 * across *all* the pages in each nonlinear VMA, not just the pages 2838 * across *all* the pages in each nonlinear VMA, not just the pages
2840 * whose virtual address lies outside the file truncation point. 2839 * whose virtual address lies outside the file truncation point.
2841 */ 2840 */
2842 list_for_each_entry(vma, head, shared.vm_set.list) { 2841 list_for_each_entry(vma, head, shared.nonlinear) {
2843 details->nonlinear_vma = vma; 2842 details->nonlinear_vma = vma;
2844 unmap_mapping_range_vma(vma, vma->vm_start, vma->vm_end, details); 2843 unmap_mapping_range_vma(vma, vma->vm_start, vma->vm_end, details);
2845 } 2844 }
@@ -2883,7 +2882,7 @@ void unmap_mapping_range(struct address_space *mapping,
2883 2882
2884 2883
2885 mutex_lock(&mapping->i_mmap_mutex); 2884 mutex_lock(&mapping->i_mmap_mutex);
2886 if (unlikely(!prio_tree_empty(&mapping->i_mmap))) 2885 if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap)))
2887 unmap_mapping_range_tree(&mapping->i_mmap, &details); 2886 unmap_mapping_range_tree(&mapping->i_mmap, &details);
2888 if (unlikely(!list_empty(&mapping->i_mmap_nonlinear))) 2887 if (unlikely(!list_empty(&mapping->i_mmap_nonlinear)))
2889 unmap_mapping_range_list(&mapping->i_mmap_nonlinear, &details); 2888 unmap_mapping_range_list(&mapping->i_mmap_nonlinear, &details);