193c68cc4SChristoph Böhmwalder // SPDX-License-Identifier: GPL-2.0-only
298683650SPhilipp Reisner #include <asm/bug.h>
398683650SPhilipp Reisner #include <linux/rbtree_augmented.h>
40939b0e5SAndreas Gruenbacher #include "drbd_interval.h"
50939b0e5SAndreas Gruenbacher
6b8b87103SLee Jones /*
70939b0e5SAndreas Gruenbacher * interval_end - return end of @node
80939b0e5SAndreas Gruenbacher */
90939b0e5SAndreas Gruenbacher static inline
interval_end(struct rb_node * node)100939b0e5SAndreas Gruenbacher sector_t interval_end(struct rb_node *node)
110939b0e5SAndreas Gruenbacher {
120939b0e5SAndreas Gruenbacher struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
130939b0e5SAndreas Gruenbacher return this->end;
140939b0e5SAndreas Gruenbacher }
150939b0e5SAndreas Gruenbacher
16315cc066SMichel Lespinasse #define NODE_END(node) ((node)->sector + ((node)->size >> 9))
170939b0e5SAndreas Gruenbacher
18315cc066SMichel Lespinasse RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
19315cc066SMichel Lespinasse struct drbd_interval, rb, sector_t, end, NODE_END);
2098683650SPhilipp Reisner
21b8b87103SLee Jones /*
220939b0e5SAndreas Gruenbacher * drbd_insert_interval - insert a new interval into a tree
230939b0e5SAndreas Gruenbacher */
240939b0e5SAndreas Gruenbacher bool
drbd_insert_interval(struct rb_root * root,struct drbd_interval * this)250939b0e5SAndreas Gruenbacher drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
260939b0e5SAndreas Gruenbacher {
270939b0e5SAndreas Gruenbacher struct rb_node **new = &root->rb_node, *parent = NULL;
2882cfb90bSLai Jiangshan sector_t this_end = this->sector + (this->size >> 9);
290939b0e5SAndreas Gruenbacher
300939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(this->size, 512));
310939b0e5SAndreas Gruenbacher
320939b0e5SAndreas Gruenbacher while (*new) {
330939b0e5SAndreas Gruenbacher struct drbd_interval *here =
340939b0e5SAndreas Gruenbacher rb_entry(*new, struct drbd_interval, rb);
350939b0e5SAndreas Gruenbacher
360939b0e5SAndreas Gruenbacher parent = *new;
3782cfb90bSLai Jiangshan if (here->end < this_end)
3882cfb90bSLai Jiangshan here->end = this_end;
390939b0e5SAndreas Gruenbacher if (this->sector < here->sector)
400939b0e5SAndreas Gruenbacher new = &(*new)->rb_left;
410939b0e5SAndreas Gruenbacher else if (this->sector > here->sector)
420939b0e5SAndreas Gruenbacher new = &(*new)->rb_right;
430939b0e5SAndreas Gruenbacher else if (this < here)
440939b0e5SAndreas Gruenbacher new = &(*new)->rb_left;
456618bf16SAndreas Gruenbacher else if (this > here)
460939b0e5SAndreas Gruenbacher new = &(*new)->rb_right;
476618bf16SAndreas Gruenbacher else
480939b0e5SAndreas Gruenbacher return false;
490939b0e5SAndreas Gruenbacher }
500939b0e5SAndreas Gruenbacher
5182cfb90bSLai Jiangshan this->end = this_end;
520939b0e5SAndreas Gruenbacher rb_link_node(&this->rb, parent, new);
5398683650SPhilipp Reisner rb_insert_augmented(&this->rb, root, &augment_callbacks);
540939b0e5SAndreas Gruenbacher return true;
550939b0e5SAndreas Gruenbacher }
560939b0e5SAndreas Gruenbacher
570939b0e5SAndreas Gruenbacher /**
580939b0e5SAndreas Gruenbacher * drbd_contains_interval - check if a tree contains a given interval
59b8b87103SLee Jones * @root: red black tree root
600939b0e5SAndreas Gruenbacher * @sector: start sector of @interval
61*2bb34fa6SAndreas Gruenbacher * @interval: may be an invalid pointer
620939b0e5SAndreas Gruenbacher *
630939b0e5SAndreas Gruenbacher * Returns if the tree contains the node @interval with start sector @start.
640939b0e5SAndreas Gruenbacher * Does not dereference @interval until @interval is known to be a valid object
650939b0e5SAndreas Gruenbacher * in @tree. Returns %false if @interval is in the tree but with a different
660939b0e5SAndreas Gruenbacher * sector number.
670939b0e5SAndreas Gruenbacher */
680939b0e5SAndreas Gruenbacher bool
drbd_contains_interval(struct rb_root * root,sector_t sector,struct drbd_interval * interval)690939b0e5SAndreas Gruenbacher drbd_contains_interval(struct rb_root *root, sector_t sector,
700939b0e5SAndreas Gruenbacher struct drbd_interval *interval)
710939b0e5SAndreas Gruenbacher {
720939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node;
730939b0e5SAndreas Gruenbacher
740939b0e5SAndreas Gruenbacher while (node) {
750939b0e5SAndreas Gruenbacher struct drbd_interval *here =
760939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb);
770939b0e5SAndreas Gruenbacher
780939b0e5SAndreas Gruenbacher if (sector < here->sector)
790939b0e5SAndreas Gruenbacher node = node->rb_left;
800939b0e5SAndreas Gruenbacher else if (sector > here->sector)
810939b0e5SAndreas Gruenbacher node = node->rb_right;
820939b0e5SAndreas Gruenbacher else if (interval < here)
830939b0e5SAndreas Gruenbacher node = node->rb_left;
840939b0e5SAndreas Gruenbacher else if (interval > here)
850939b0e5SAndreas Gruenbacher node = node->rb_right;
860939b0e5SAndreas Gruenbacher else
873e05146fSAndreas Gruenbacher return true;
880939b0e5SAndreas Gruenbacher }
890939b0e5SAndreas Gruenbacher return false;
900939b0e5SAndreas Gruenbacher }
910939b0e5SAndreas Gruenbacher
92b8b87103SLee Jones /*
930939b0e5SAndreas Gruenbacher * drbd_remove_interval - remove an interval from a tree
940939b0e5SAndreas Gruenbacher */
950939b0e5SAndreas Gruenbacher void
drbd_remove_interval(struct rb_root * root,struct drbd_interval * this)960939b0e5SAndreas Gruenbacher drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
970939b0e5SAndreas Gruenbacher {
982990ca29SLars Ellenberg /* avoid endless loop */
992990ca29SLars Ellenberg if (drbd_interval_empty(this))
1002990ca29SLars Ellenberg return;
1012990ca29SLars Ellenberg
10298683650SPhilipp Reisner rb_erase_augmented(&this->rb, root, &augment_callbacks);
1030939b0e5SAndreas Gruenbacher }
1040939b0e5SAndreas Gruenbacher
1050939b0e5SAndreas Gruenbacher /**
1060939b0e5SAndreas Gruenbacher * drbd_find_overlap - search for an interval overlapping with [sector, sector + size)
107b8b87103SLee Jones * @root: red black tree root
1080939b0e5SAndreas Gruenbacher * @sector: start sector
1090939b0e5SAndreas Gruenbacher * @size: size, aligned to 512 bytes
1100939b0e5SAndreas Gruenbacher *
11170b19876SAndreas Gruenbacher * Returns an interval overlapping with [sector, sector + size), or NULL if
11270b19876SAndreas Gruenbacher * there is none. When there is more than one overlapping interval in the
11370b19876SAndreas Gruenbacher * tree, the interval with the lowest start sector is returned, and all other
11470b19876SAndreas Gruenbacher * overlapping intervals will be on the right side of the tree, reachable with
11570b19876SAndreas Gruenbacher * rb_next().
1160939b0e5SAndreas Gruenbacher */
1170939b0e5SAndreas Gruenbacher struct drbd_interval *
drbd_find_overlap(struct rb_root * root,sector_t sector,unsigned int size)1180939b0e5SAndreas Gruenbacher drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
1190939b0e5SAndreas Gruenbacher {
1200939b0e5SAndreas Gruenbacher struct rb_node *node = root->rb_node;
1210939b0e5SAndreas Gruenbacher struct drbd_interval *overlap = NULL;
1220939b0e5SAndreas Gruenbacher sector_t end = sector + (size >> 9);
1230939b0e5SAndreas Gruenbacher
1240939b0e5SAndreas Gruenbacher BUG_ON(!IS_ALIGNED(size, 512));
1250939b0e5SAndreas Gruenbacher
1260939b0e5SAndreas Gruenbacher while (node) {
1270939b0e5SAndreas Gruenbacher struct drbd_interval *here =
1280939b0e5SAndreas Gruenbacher rb_entry(node, struct drbd_interval, rb);
1290939b0e5SAndreas Gruenbacher
1300939b0e5SAndreas Gruenbacher if (node->rb_left &&
1310939b0e5SAndreas Gruenbacher sector < interval_end(node->rb_left)) {
1320939b0e5SAndreas Gruenbacher /* Overlap if any must be on left side */
1330939b0e5SAndreas Gruenbacher node = node->rb_left;
1340939b0e5SAndreas Gruenbacher } else if (here->sector < end &&
1350939b0e5SAndreas Gruenbacher sector < here->sector + (here->size >> 9)) {
1360939b0e5SAndreas Gruenbacher overlap = here;
1370939b0e5SAndreas Gruenbacher break;
1380939b0e5SAndreas Gruenbacher } else if (sector >= here->sector) {
1390939b0e5SAndreas Gruenbacher /* Overlap if any must be on right side */
1400939b0e5SAndreas Gruenbacher node = node->rb_right;
1410939b0e5SAndreas Gruenbacher } else
1420939b0e5SAndreas Gruenbacher break;
1430939b0e5SAndreas Gruenbacher }
1440939b0e5SAndreas Gruenbacher return overlap;
1450939b0e5SAndreas Gruenbacher }
146d0e22a26SAndreas Gruenbacher
147d0e22a26SAndreas Gruenbacher struct drbd_interval *
drbd_next_overlap(struct drbd_interval * i,sector_t sector,unsigned int size)148d0e22a26SAndreas Gruenbacher drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
149d0e22a26SAndreas Gruenbacher {
150d0e22a26SAndreas Gruenbacher sector_t end = sector + (size >> 9);
151d0e22a26SAndreas Gruenbacher struct rb_node *node;
152d0e22a26SAndreas Gruenbacher
153d0e22a26SAndreas Gruenbacher for (;;) {
154d0e22a26SAndreas Gruenbacher node = rb_next(&i->rb);
155d0e22a26SAndreas Gruenbacher if (!node)
156d0e22a26SAndreas Gruenbacher return NULL;
157d0e22a26SAndreas Gruenbacher i = rb_entry(node, struct drbd_interval, rb);
158d0e22a26SAndreas Gruenbacher if (i->sector >= end)
159d0e22a26SAndreas Gruenbacher return NULL;
160d0e22a26SAndreas Gruenbacher if (sector < i->sector + (i->size >> 9))
161d0e22a26SAndreas Gruenbacher return i;
162d0e22a26SAndreas Gruenbacher }
163d0e22a26SAndreas Gruenbacher }
164