1 // SPDX-License-Identifier: GPL-2.0
2 #include <asm/bug.h>
3 #include <linux/rbtree_augmented.h>
4 #include "drbd_interval.h"
5 
6 /**
7  * interval_end  -  return end of @node
8  */
9 static inline
10 sector_t interval_end(struct rb_node *node)
11 {
12 	struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
13 	return this->end;
14 }
15 
16 /**
17  * compute_subtree_last  -  compute end of @node
18  *
19  * The end of an interval is the highest (start + (size >> 9)) value of this
20  * node and of its children.  Called for @node and its parents whenever the end
21  * may have changed.
22  */
23 static inline sector_t
24 compute_subtree_last(struct drbd_interval *node)
25 {
26 	sector_t max = node->sector + (node->size >> 9);
27 
28 	if (node->rb.rb_left) {
29 		sector_t left = interval_end(node->rb.rb_left);
30 		if (left > max)
31 			max = left;
32 	}
33 	if (node->rb.rb_right) {
34 		sector_t right = interval_end(node->rb.rb_right);
35 		if (right > max)
36 			max = right;
37 	}
38 	return max;
39 }
40 
41 RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb,
42 		     sector_t, end, compute_subtree_last);
43 
44 /**
45  * drbd_insert_interval  -  insert a new interval into a tree
46  */
47 bool
48 drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
49 {
50 	struct rb_node **new = &root->rb_node, *parent = NULL;
51 	sector_t this_end = this->sector + (this->size >> 9);
52 
53 	BUG_ON(!IS_ALIGNED(this->size, 512));
54 
55 	while (*new) {
56 		struct drbd_interval *here =
57 			rb_entry(*new, struct drbd_interval, rb);
58 
59 		parent = *new;
60 		if (here->end < this_end)
61 			here->end = this_end;
62 		if (this->sector < here->sector)
63 			new = &(*new)->rb_left;
64 		else if (this->sector > here->sector)
65 			new = &(*new)->rb_right;
66 		else if (this < here)
67 			new = &(*new)->rb_left;
68 		else if (this > here)
69 			new = &(*new)->rb_right;
70 		else
71 			return false;
72 	}
73 
74 	this->end = this_end;
75 	rb_link_node(&this->rb, parent, new);
76 	rb_insert_augmented(&this->rb, root, &augment_callbacks);
77 	return true;
78 }
79 
80 /**
81  * drbd_contains_interval  -  check if a tree contains a given interval
82  * @sector:	start sector of @interval
83  * @interval:	may not be a valid pointer
84  *
85  * Returns if the tree contains the node @interval with start sector @start.
86  * Does not dereference @interval until @interval is known to be a valid object
87  * in @tree.  Returns %false if @interval is in the tree but with a different
88  * sector number.
89  */
90 bool
91 drbd_contains_interval(struct rb_root *root, sector_t sector,
92 		       struct drbd_interval *interval)
93 {
94 	struct rb_node *node = root->rb_node;
95 
96 	while (node) {
97 		struct drbd_interval *here =
98 			rb_entry(node, struct drbd_interval, rb);
99 
100 		if (sector < here->sector)
101 			node = node->rb_left;
102 		else if (sector > here->sector)
103 			node = node->rb_right;
104 		else if (interval < here)
105 			node = node->rb_left;
106 		else if (interval > here)
107 			node = node->rb_right;
108 		else
109 			return true;
110 	}
111 	return false;
112 }
113 
114 /**
115  * drbd_remove_interval  -  remove an interval from a tree
116  */
117 void
118 drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
119 {
120 	rb_erase_augmented(&this->rb, root, &augment_callbacks);
121 }
122 
123 /**
124  * drbd_find_overlap  - search for an interval overlapping with [sector, sector + size)
125  * @sector:	start sector
126  * @size:	size, aligned to 512 bytes
127  *
128  * Returns an interval overlapping with [sector, sector + size), or NULL if
129  * there is none.  When there is more than one overlapping interval in the
130  * tree, the interval with the lowest start sector is returned, and all other
131  * overlapping intervals will be on the right side of the tree, reachable with
132  * rb_next().
133  */
134 struct drbd_interval *
135 drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
136 {
137 	struct rb_node *node = root->rb_node;
138 	struct drbd_interval *overlap = NULL;
139 	sector_t end = sector + (size >> 9);
140 
141 	BUG_ON(!IS_ALIGNED(size, 512));
142 
143 	while (node) {
144 		struct drbd_interval *here =
145 			rb_entry(node, struct drbd_interval, rb);
146 
147 		if (node->rb_left &&
148 		    sector < interval_end(node->rb_left)) {
149 			/* Overlap if any must be on left side */
150 			node = node->rb_left;
151 		} else if (here->sector < end &&
152 			   sector < here->sector + (here->size >> 9)) {
153 			overlap = here;
154 			break;
155 		} else if (sector >= here->sector) {
156 			/* Overlap if any must be on right side */
157 			node = node->rb_right;
158 		} else
159 			break;
160 	}
161 	return overlap;
162 }
163 
164 struct drbd_interval *
165 drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
166 {
167 	sector_t end = sector + (size >> 9);
168 	struct rb_node *node;
169 
170 	for (;;) {
171 		node = rb_next(&i->rb);
172 		if (!node)
173 			return NULL;
174 		i = rb_entry(node, struct drbd_interval, rb);
175 		if (i->sector >= end)
176 			return NULL;
177 		if (sector < i->sector + (i->size >> 9))
178 			return i;
179 	}
180 }
181