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 not be a valid 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 rb_erase_augmented(&this->rb, root, &augment_callbacks); 99 } 100 101 /** 102 * drbd_find_overlap - search for an interval overlapping with [sector, sector + size) 103 * @root: red black tree root 104 * @sector: start sector 105 * @size: size, aligned to 512 bytes 106 * 107 * Returns an interval overlapping with [sector, sector + size), or NULL if 108 * there is none. When there is more than one overlapping interval in the 109 * tree, the interval with the lowest start sector is returned, and all other 110 * overlapping intervals will be on the right side of the tree, reachable with 111 * rb_next(). 112 */ 113 struct drbd_interval * 114 drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size) 115 { 116 struct rb_node *node = root->rb_node; 117 struct drbd_interval *overlap = NULL; 118 sector_t end = sector + (size >> 9); 119 120 BUG_ON(!IS_ALIGNED(size, 512)); 121 122 while (node) { 123 struct drbd_interval *here = 124 rb_entry(node, struct drbd_interval, rb); 125 126 if (node->rb_left && 127 sector < interval_end(node->rb_left)) { 128 /* Overlap if any must be on left side */ 129 node = node->rb_left; 130 } else if (here->sector < end && 131 sector < here->sector + (here->size >> 9)) { 132 overlap = here; 133 break; 134 } else if (sector >= here->sector) { 135 /* Overlap if any must be on right side */ 136 node = node->rb_right; 137 } else 138 break; 139 } 140 return overlap; 141 } 142 143 struct drbd_interval * 144 drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size) 145 { 146 sector_t end = sector + (size >> 9); 147 struct rb_node *node; 148 149 for (;;) { 150 node = rb_next(&i->rb); 151 if (!node) 152 return NULL; 153 i = rb_entry(node, struct drbd_interval, rb); 154 if (i->sector >= end) 155 return NULL; 156 if (sector < i->sector + (i->size >> 9)) 157 return i; 158 } 159 } 160