interval_tree.c 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * mm/interval_tree.c - interval tree for mapping->i_mmap
  4. *
  5. * Copyright (C) 2012, Michel Lespinasse <walken@google.com>
  6. */
  7. #include <linux/mm.h>
  8. #include <linux/fs.h>
  9. #include <linux/rmap.h>
  10. #include <linux/interval_tree_generic.h>
  11. static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)
  12. {
  13. return v->vm_pgoff;
  14. }
  15. static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)
  16. {
  17. return v->vm_pgoff + vma_pages(v) - 1;
  18. }
  19. INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,
  20. unsigned long, shared.rb_subtree_last,
  21. vma_start_pgoff, vma_last_pgoff,, vma_interval_tree)
  22. /* Insert node immediately after prev in the interval tree */
  23. void vma_interval_tree_insert_after(struct vm_area_struct *node,
  24. struct vm_area_struct *prev,
  25. struct rb_root_cached *root)
  26. {
  27. struct rb_node **link;
  28. struct vm_area_struct *parent;
  29. unsigned long last = vma_last_pgoff(node);
  30. VM_BUG_ON_VMA(vma_start_pgoff(node) != vma_start_pgoff(prev), node);
  31. if (!prev->shared.rb.rb_right) {
  32. parent = prev;
  33. link = &prev->shared.rb.rb_right;
  34. } else {
  35. parent = rb_entry(prev->shared.rb.rb_right,
  36. struct vm_area_struct, shared.rb);
  37. if (parent->shared.rb_subtree_last < last)
  38. parent->shared.rb_subtree_last = last;
  39. while (parent->shared.rb.rb_left) {
  40. parent = rb_entry(parent->shared.rb.rb_left,
  41. struct vm_area_struct, shared.rb);
  42. if (parent->shared.rb_subtree_last < last)
  43. parent->shared.rb_subtree_last = last;
  44. }
  45. link = &parent->shared.rb.rb_left;
  46. }
  47. node->shared.rb_subtree_last = last;
  48. rb_link_node(&node->shared.rb, &parent->shared.rb, link);
  49. rb_insert_augmented(&node->shared.rb, &root->rb_root,
  50. &vma_interval_tree_augment);
  51. }
  52. static inline unsigned long avc_start_pgoff(struct anon_vma_chain *avc)
  53. {
  54. return vma_start_pgoff(avc->vma);
  55. }
  56. static inline unsigned long avc_last_pgoff(struct anon_vma_chain *avc)
  57. {
  58. return vma_last_pgoff(avc->vma);
  59. }
  60. INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last,
  61. avc_start_pgoff, avc_last_pgoff,
  62. static inline, __anon_vma_interval_tree)
  63. void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
  64. struct rb_root_cached *root)
  65. {
  66. #ifdef CONFIG_DEBUG_VM_RB
  67. node->cached_vma_start = avc_start_pgoff(node);
  68. node->cached_vma_last = avc_last_pgoff(node);
  69. #endif
  70. __anon_vma_interval_tree_insert(node, root);
  71. }
  72. void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
  73. struct rb_root_cached *root)
  74. {
  75. __anon_vma_interval_tree_remove(node, root);
  76. }
  77. struct anon_vma_chain *
  78. anon_vma_interval_tree_iter_first(struct rb_root_cached *root,
  79. unsigned long first, unsigned long last)
  80. {
  81. return __anon_vma_interval_tree_iter_first(root, first, last);
  82. }
  83. struct anon_vma_chain *
  84. anon_vma_interval_tree_iter_next(struct anon_vma_chain *node,
  85. unsigned long first, unsigned long last)
  86. {
  87. return __anon_vma_interval_tree_iter_next(node, first, last);
  88. }
  89. #ifdef CONFIG_DEBUG_VM_RB
  90. void anon_vma_interval_tree_verify(struct anon_vma_chain *node)
  91. {
  92. WARN_ON_ONCE(node->cached_vma_start != avc_start_pgoff(node));
  93. WARN_ON_ONCE(node->cached_vma_last != avc_last_pgoff(node));
  94. }
  95. #endif