Branch data Line data Source code
1 : : /*
2 : : * mm/interval_tree.c - interval tree for mapping->i_mmap
3 : : *
4 : : * Copyright (C) 2012, Michel Lespinasse <walken@google.com>
5 : : *
6 : : * This file is released under the GPL v2.
7 : : */
8 : :
9 : : #include <linux/mm.h>
10 : : #include <linux/fs.h>
11 : : #include <linux/rmap.h>
12 : : #include <linux/interval_tree_generic.h>
13 : :
14 : : static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)
15 : : {
16 : : return v->vm_pgoff;
17 : : }
18 : :
19 : : static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)
20 : : {
21 : 27801396 : return v->vm_pgoff + ((v->vm_end - v->vm_start) >> PAGE_SHIFT) - 1;
22 : : }
23 : :
24 [ + + ][ + - ]: 27310049 : INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.linear.rb,
[ + ][ + + ]
[ + + ][ - + ]
[ + - ][ + + ]
[ + + ][ + - ]
[ # # ][ - + ]
[ # # ][ # # ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + ]
[ + + ]
25 : : unsigned long, shared.linear.rb_subtree_last,
26 : : vma_start_pgoff, vma_last_pgoff,, vma_interval_tree)
27 : :
28 : : /* Insert node immediately after prev in the interval tree */
29 : 0 : void vma_interval_tree_insert_after(struct vm_area_struct *node,
30 : : struct vm_area_struct *prev,
31 : : struct rb_root *root)
32 : : {
33 : : struct rb_node **link;
34 : : struct vm_area_struct *parent;
35 : : unsigned long last = vma_last_pgoff(node);
36 : :
37 : : VM_BUG_ON(vma_start_pgoff(node) != vma_start_pgoff(prev));
38 : :
39 [ + + ]: 11491678 : if (!prev->shared.linear.rb.rb_right) {
40 : : parent = prev;
41 : 9766637 : link = &prev->shared.linear.rb.rb_right;
42 : : } else {
43 : 1725041 : parent = rb_entry(prev->shared.linear.rb.rb_right,
44 : : struct vm_area_struct, shared.linear.rb);
45 [ + + ]: 1725041 : if (parent->shared.linear.rb_subtree_last < last)
46 : 1725041 : parent->shared.linear.rb_subtree_last = last;
47 [ + + ]: 2648161 : while (parent->shared.linear.rb.rb_left) {
48 : 923120 : parent = rb_entry(parent->shared.linear.rb.rb_left,
49 : : struct vm_area_struct, shared.linear.rb);
50 [ + + ]: 923120 : if (parent->shared.linear.rb_subtree_last < last)
51 : 923120 : parent->shared.linear.rb_subtree_last = last;
52 : : }
53 : 1725041 : link = &parent->shared.linear.rb.rb_left;
54 : : }
55 : :
56 : 11491678 : node->shared.linear.rb_subtree_last = last;
57 : 11491678 : rb_link_node(&node->shared.linear.rb, &parent->shared.linear.rb, link);
58 : : rb_insert_augmented(&node->shared.linear.rb, root,
59 : : &vma_interval_tree_augment);
60 : 11491669 : }
61 : :
62 : : static inline unsigned long avc_start_pgoff(struct anon_vma_chain *avc)
63 : : {
64 : 51802629 : return vma_start_pgoff(avc->vma);
65 : : }
66 : :
67 : : static inline unsigned long avc_last_pgoff(struct anon_vma_chain *avc)
68 : : {
69 : : return vma_last_pgoff(avc->vma);
70 : : }
71 : :
72 [ + + ][ + - ]: 87036365 : INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last,
[ + ][ - + ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + - ][ # # ]
[ - + ][ # # ]
[ # # ][ + + ]
[ - + ][ + ]
[ + + ][ + + ]
[ + + ][ + + ]
[ + + ][ + ]
[ + + ]
73 : : avc_start_pgoff, avc_last_pgoff,
74 : : static inline, __anon_vma_interval_tree)
75 : :
76 : 0 : void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
77 : : struct rb_root *root)
78 : : {
79 : : #ifdef CONFIG_DEBUG_VM_RB
80 : : node->cached_vma_start = avc_start_pgoff(node);
81 : : node->cached_vma_last = avc_last_pgoff(node);
82 : : #endif
83 : : __anon_vma_interval_tree_insert(node, root);
84 : 27801432 : }
85 : :
86 : 0 : void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
87 : : struct rb_root *root)
88 : : {
89 : : __anon_vma_interval_tree_remove(node, root);
90 : 27800886 : }
91 : :
92 : : struct anon_vma_chain *
93 : 0 : anon_vma_interval_tree_iter_first(struct rb_root *root,
94 : : unsigned long first, unsigned long last)
95 : : {
96 : 0 : return __anon_vma_interval_tree_iter_first(root, first, last);
97 : : }
98 : :
99 : : struct anon_vma_chain *
100 : 0 : anon_vma_interval_tree_iter_next(struct anon_vma_chain *node,
101 : : unsigned long first, unsigned long last)
102 : : {
103 : 0 : return __anon_vma_interval_tree_iter_next(node, first, last);
104 : : }
105 : :
106 : : #ifdef CONFIG_DEBUG_VM_RB
107 : : void anon_vma_interval_tree_verify(struct anon_vma_chain *node)
108 : : {
109 : : WARN_ON_ONCE(node->cached_vma_start != avc_start_pgoff(node));
110 : : WARN_ON_ONCE(node->cached_vma_last != avc_last_pgoff(node));
111 : : }
112 : : #endif
|
