Greg Kroah-Hartman | b244131 | 2017-11-01 15:07:57 +0100 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0 |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 2 | #include <asm/bug.h> |
| 3 | #include <linux/rbtree_augmented.h> |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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 | /** |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 17 | * compute_subtree_last - compute end of @node |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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 | */ |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 23 | static inline sector_t |
| 24 | compute_subtree_last(struct drbd_interval *node) |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 25 | { |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 26 | sector_t max = node->sector + (node->size >> 9); |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 27 | |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 28 | if (node->rb.rb_left) { |
| 29 | sector_t left = interval_end(node->rb.rb_left); |
| 30 | if (left > max) |
| 31 | max = left; |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 32 | } |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 33 | if (node->rb.rb_right) { |
| 34 | sector_t right = interval_end(node->rb.rb_right); |
| 35 | if (right > max) |
| 36 | max = right; |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 37 | } |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 38 | return max; |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 39 | } |
| 40 | |
Lai Jiangshan | e9f05b4 | 2014-09-18 16:49:42 +0200 | [diff] [blame] | 41 | RB_DECLARE_CALLBACKS(static, augment_callbacks, struct drbd_interval, rb, |
| 42 | sector_t, end, compute_subtree_last); |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 43 | |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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; |
Lai Jiangshan | 82cfb90 | 2014-09-18 16:49:41 +0200 | [diff] [blame] | 51 | sector_t this_end = this->sector + (this->size >> 9); |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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; |
Lai Jiangshan | 82cfb90 | 2014-09-18 16:49:41 +0200 | [diff] [blame] | 60 | if (here->end < this_end) |
| 61 | here->end = this_end; |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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; |
Andreas Gruenbacher | 6618bf1 | 2011-01-26 13:06:08 +0100 | [diff] [blame] | 68 | else if (this > here) |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 69 | new = &(*new)->rb_right; |
Andreas Gruenbacher | 6618bf1 | 2011-01-26 13:06:08 +0100 | [diff] [blame] | 70 | else |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 71 | return false; |
| 72 | } |
| 73 | |
Lai Jiangshan | 82cfb90 | 2014-09-18 16:49:41 +0200 | [diff] [blame] | 74 | this->end = this_end; |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 75 | rb_link_node(&this->rb, parent, new); |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 76 | rb_insert_augmented(&this->rb, root, &augment_callbacks); |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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 |
Andreas Gruenbacher | 3e05146 | 2011-01-27 16:20:57 +0100 | [diff] [blame] | 109 | return true; |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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 | { |
Philipp Reisner | 9868365 | 2012-11-09 14:18:43 +0100 | [diff] [blame] | 120 | rb_erase_augmented(&this->rb, root, &augment_callbacks); |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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 | * |
Andreas Gruenbacher | 70b1987 | 2011-02-04 12:11:05 +0100 | [diff] [blame] | 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(). |
Andreas Gruenbacher | 0939b0e | 2011-01-03 17:42:00 +0100 | [diff] [blame] | 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 | } |
Andreas Gruenbacher | d0e22a2 | 2011-02-17 18:11:24 +0100 | [diff] [blame] | 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 | } |