Michel Lespinasse | 6b2dbba | 2012-10-08 16:31:25 -0700 | [diff] [blame] | 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 | } |