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(&this->rb, parent, new); 53 rb_insert_augmented(&this->rb, root, &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(this)) 100 return; 101 102 rb_erase_augmented(&this->rb, root, &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->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