1 // SPDX-License-Identifier: GPL-2.0-only
3  * mm/interval_tree.c - interval tree for mapping->i_mmap
15 	return v->vm_pgoff;  in vma_start_pgoff()
20 	return v->vm_pgoff + vma_pages(v) - 1;  in vma_last_pgoff()
27 /* Insert node immediately after prev in the interval tree */
28 void vma_interval_tree_insert_after(struct vm_area_struct *node,  in vma_interval_tree_insert_after()  argument
30 				    struct rb_root_cached *root)  in vma_interval_tree_insert_after()  argument
34 	unsigned long last = vma_last_pgoff(node);  in vma_interval_tree_insert_after()
36 	VM_BUG_ON_VMA(vma_start_pgoff(node) != vma_start_pgoff(prev), node);  in vma_interval_tree_insert_after()
38 	if (!prev->shared.rb.rb_right) {  in vma_interval_tree_insert_after()
40 		link = &prev->shared.rb.rb_right;  in vma_interval_tree_insert_after()
42 		parent = rb_entry(prev->shared.rb.rb_right,  in vma_interval_tree_insert_after()
44 		if (parent->shared.rb_subtree_last < last)  in vma_interval_tree_insert_after()
45 			parent->shared.rb_subtree_last = last;  in vma_interval_tree_insert_after()
46 		while (parent->shared.rb.rb_left) {  in vma_interval_tree_insert_after()
47 			parent = rb_entry(parent->shared.rb.rb_left,  in vma_interval_tree_insert_after()
49 			if (parent->shared.rb_subtree_last < last)  in vma_interval_tree_insert_after()
50 				parent->shared.rb_subtree_last = last;  in vma_interval_tree_insert_after()
52 		link = &parent->shared.rb.rb_left;  in vma_interval_tree_insert_after()
55 	node->shared.rb_subtree_last = last;  in vma_interval_tree_insert_after()
56 	rb_link_node(&node->shared.rb, &parent->shared.rb, link);  in vma_interval_tree_insert_after()
57 	rb_insert_augmented(&node->shared.rb, &root->rb_root,  in vma_interval_tree_insert_after()
63 	return vma_start_pgoff(avc->vma);  in avc_start_pgoff()
68 	return vma_last_pgoff(avc->vma);  in avc_last_pgoff()
75 void anon_vma_interval_tree_insert(struct anon_vma_chain *node,  in INTERVAL_TREE_DEFINE()
76 				   struct rb_root_cached *root)  in INTERVAL_TREE_DEFINE()
79 	node->cached_vma_start = avc_start_pgoff(node);  in INTERVAL_TREE_DEFINE()
80 	node->cached_vma_last = avc_last_pgoff(node);  in INTERVAL_TREE_DEFINE()
82 	__anon_vma_interval_tree_insert(node, root);  in INTERVAL_TREE_DEFINE()
85 void anon_vma_interval_tree_remove(struct anon_vma_chain *node,  in anon_vma_interval_tree_remove()  argument
86 				   struct rb_root_cached *root)  in anon_vma_interval_tree_remove()  argument
88 	__anon_vma_interval_tree_remove(node, root);  in anon_vma_interval_tree_remove()
92 anon_vma_interval_tree_iter_first(struct rb_root_cached *root,  in anon_vma_interval_tree_iter_first()  argument
95 	return __anon_vma_interval_tree_iter_first(root, first, last);  in anon_vma_interval_tree_iter_first()
99 anon_vma_interval_tree_iter_next(struct anon_vma_chain *node,  in anon_vma_interval_tree_iter_next()  argument
102 	return __anon_vma_interval_tree_iter_next(node, first, last);  in anon_vma_interval_tree_iter_next()
106 void anon_vma_interval_tree_verify(struct anon_vma_chain *node)  in anon_vma_interval_tree_verify()  argument
108 	WARN_ON_ONCE(node->cached_vma_start != avc_start_pgoff(node));  in anon_vma_interval_tree_verify()
109 	WARN_ON_ONCE(node->cached_vma_last != avc_last_pgoff(node));  in anon_vma_interval_tree_verify()