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 */
  9static inline
 10sector_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 */
 23static inline sector_t
 24compute_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
 41RB_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 */
 47bool
 48drbd_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 */
 90bool
 91drbd_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 */
117void
118drbd_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 */
134struct drbd_interval *
135drbd_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
164struct drbd_interval *
165drbd_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}