Commit | Line | Data |
---|---|---|
6b2dbba8 ML |
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 | ||
12 | #define ITSTRUCT struct vm_area_struct | |
13 | #define ITRB shared.linear.rb | |
14 | #define ITTYPE unsigned long | |
15 | #define ITSUBTREE shared.linear.rb_subtree_last | |
16 | #define ITSTART(n) ((n)->vm_pgoff) | |
17 | #define ITLAST(n) ((n)->vm_pgoff + \ | |
18 | (((n)->vm_end - (n)->vm_start) >> PAGE_SHIFT) - 1) | |
19 | #define ITSTATIC | |
20 | #define ITPREFIX vma_interval_tree | |
21 | ||
22 | #include <linux/interval_tree_tmpl.h> | |
23 | ||
24 | /* Insert old immediately after vma in the interval tree */ | |
25 | void vma_interval_tree_add(struct vm_area_struct *vma, | |
26 | struct vm_area_struct *old, | |
27 | struct address_space *mapping) | |
28 | { | |
29 | struct rb_node **link; | |
30 | struct vm_area_struct *parent; | |
31 | unsigned long last; | |
32 | ||
33 | if (unlikely(vma->vm_flags & VM_NONLINEAR)) { | |
34 | list_add(&vma->shared.nonlinear, &old->shared.nonlinear); | |
35 | return; | |
36 | } | |
37 | ||
38 | last = ITLAST(vma); | |
39 | ||
40 | if (!old->shared.linear.rb.rb_right) { | |
41 | parent = old; | |
42 | link = &old->shared.linear.rb.rb_right; | |
43 | } else { | |
44 | parent = rb_entry(old->shared.linear.rb.rb_right, | |
45 | struct vm_area_struct, shared.linear.rb); | |
46 | if (parent->shared.linear.rb_subtree_last < last) | |
47 | parent->shared.linear.rb_subtree_last = last; | |
48 | while (parent->shared.linear.rb.rb_left) { | |
49 | parent = rb_entry(parent->shared.linear.rb.rb_left, | |
50 | struct vm_area_struct, shared.linear.rb); | |
51 | if (parent->shared.linear.rb_subtree_last < last) | |
52 | parent->shared.linear.rb_subtree_last = last; | |
53 | } | |
54 | link = &parent->shared.linear.rb.rb_left; | |
55 | } | |
56 | ||
57 | vma->shared.linear.rb_subtree_last = last; | |
58 | rb_link_node(&vma->shared.linear.rb, &parent->shared.linear.rb, link); | |
59 | rb_insert_augmented(&vma->shared.linear.rb, &mapping->i_mmap, | |
60 | &vma_interval_tree_augment_callbacks); | |
61 | } |