^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #include <asm/bug.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) #include <linux/rbtree_augmented.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) #include "drbd_interval.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * interval_end - return end of @node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) static inline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) sector_t interval_end(struct rb_node *node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) return this->end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #define NODE_END(node) ((node)->sector + ((node)->size >> 9))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) struct drbd_interval, rb, sector_t, end, NODE_END);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * drbd_insert_interval - insert a new interval into a tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) bool
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) struct rb_node **new = &root->rb_node, *parent = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) sector_t this_end = this->sector + (this->size >> 9);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) BUG_ON(!IS_ALIGNED(this->size, 512));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) while (*new) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) struct drbd_interval *here =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) rb_entry(*new, struct drbd_interval, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) parent = *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) if (here->end < this_end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) here->end = this_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) if (this->sector < here->sector)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) new = &(*new)->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) else if (this->sector > here->sector)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) new = &(*new)->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) else if (this < here)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) new = &(*new)->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) else if (this > here)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) new = &(*new)->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) this->end = this_end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) rb_link_node(&this->rb, parent, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) rb_insert_augmented(&this->rb, root, &augment_callbacks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * drbd_contains_interval - check if a tree contains a given interval
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * @sector: start sector of @interval
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * @interval: may not be a valid pointer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) * Returns if the tree contains the node @interval with start sector @start.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) * Does not dereference @interval until @interval is known to be a valid object
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * in @tree. Returns %false if @interval is in the tree but with a different
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) * sector number.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) bool
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) drbd_contains_interval(struct rb_root *root, sector_t sector,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) struct drbd_interval *interval)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) struct rb_node *node = root->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) while (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) struct drbd_interval *here =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) rb_entry(node, struct drbd_interval, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) if (sector < here->sector)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) node = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) else if (sector > here->sector)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) node = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) else if (interval < here)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) node = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) else if (interval > here)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) node = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * drbd_remove_interval - remove an interval from a tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) void
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) rb_erase_augmented(&this->rb, root, &augment_callbacks);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) * drbd_find_overlap - search for an interval overlapping with [sector, sector + size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) * @sector: start sector
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) * @size: size, aligned to 512 bytes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) * Returns an interval overlapping with [sector, sector + size), or NULL if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) * there is none. When there is more than one overlapping interval in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) * tree, the interval with the lowest start sector is returned, and all other
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) * overlapping intervals will be on the right side of the tree, reachable with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) * rb_next().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) struct drbd_interval *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) struct rb_node *node = root->rb_node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) struct drbd_interval *overlap = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) sector_t end = sector + (size >> 9);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) BUG_ON(!IS_ALIGNED(size, 512));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) while (node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) struct drbd_interval *here =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) rb_entry(node, struct drbd_interval, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) if (node->rb_left &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) sector < interval_end(node->rb_left)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) /* Overlap if any must be on left side */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) node = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) } else if (here->sector < end &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) sector < here->sector + (here->size >> 9)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) overlap = here;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) } else if (sector >= here->sector) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) /* Overlap if any must be on right side */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) node = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) return overlap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) struct drbd_interval *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) sector_t end = sector + (size >> 9);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) struct rb_node *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) node = rb_next(&i->rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) i = rb_entry(node, struct drbd_interval, rb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) if (i->sector >= end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) if (sector < i->sector + (i->size >> 9))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) return i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags