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