]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
98683650 PR |
2 | #include <asm/bug.h> |
3 | #include <linux/rbtree_augmented.h> | |
0939b0e5 AG |
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 | /** | |
98683650 | 17 | * compute_subtree_last - compute end of @node |
0939b0e5 AG |
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 | */ | |
98683650 PR |
23 | static inline sector_t |
24 | compute_subtree_last(struct drbd_interval *node) | |
0939b0e5 | 25 | { |
98683650 | 26 | sector_t max = node->sector + (node->size >> 9); |
0939b0e5 | 27 | |
98683650 PR |
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; | |
0939b0e5 | 37 | } |
98683650 PR |
38 | return max; |
39 | } | |
40 | ||
e9f05b4c LJ |
41 | RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb, |
42 | sector_t, end, compute_subtree_last); | |
98683650 | 43 | |
0939b0e5 AG |
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; | |
82cfb90b | 51 | sector_t this_end = this->sector + (this->size >> 9); |
0939b0e5 AG |
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; | |
82cfb90b LJ |
60 | if (here->end < this_end) |
61 | here->end = this_end; | |
0939b0e5 AG |
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; | |
6618bf16 | 68 | else if (this > here) |
0939b0e5 | 69 | new = &(*new)->rb_right; |
6618bf16 | 70 | else |
0939b0e5 AG |
71 | return false; |
72 | } | |
73 | ||
82cfb90b | 74 | this->end = this_end; |
0939b0e5 | 75 | rb_link_node(&this->rb, parent, new); |
98683650 | 76 | rb_insert_augmented(&this->rb, root, &augment_callbacks); |
0939b0e5 AG |
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 | |
3e05146f | 109 | return true; |
0939b0e5 AG |
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 | { | |
98683650 | 120 | rb_erase_augmented(&this->rb, root, &augment_callbacks); |
0939b0e5 AG |
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 | * | |
70b19876 AG |
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(). | |
0939b0e5 AG |
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 | } | |
d0e22a26 AG |
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 | } |