drivers/block/drbd/drbd_interval.c

   1 #include "drbd_interval.h"
   2
   3 /**
   4  * interval_end  -  return end of @node
   5  */
   6 static inline
   7 sector_t interval_end(struct rb_node *node)
   8 {
   9         struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
  10         return this->end;
  11 }
  12
  13 /**
  14  * update_interval_end  -  recompute end of @node
  15  *
  16  * The end of an interval is the highest (start + (size >> 9)) value of this
  17  * node and of its children.  Called for @node and its parents whenever the end
  18  * may have changed.
  19  */
  20 static void
  21 update_interval_end(struct rb_node *node, void *__unused)
  22 {
  23         struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb);
  24         sector_t end;
  25
  26         end = this->sector + (this->size >> 9);
  27         if (node->rb_left) {
  28                 sector_t left = interval_end(node->rb_left);
  29                 if (left > end)
  30                         end = left;
  31         }
  32         if (node->rb_right) {
  33                 sector_t right = interval_end(node->rb_right);
  34                 if (right > end)
  35                         end = right;
  36         }
  37         this->end = end;
  38 }
  39
  40 /**
  41  * drbd_insert_interval  -  insert a new interval into a tree
  42  */
  43 bool
  44 drbd_insert_interval(struct rb_root *root, struct drbd_interval *this)
  45 {
  46         struct rb_node **new = &root->rb_node, *parent = NULL;
  47
  48         BUG_ON(!IS_ALIGNED(this->size, 512));
  49
  50         while (*new) {
  51                 struct drbd_interval *here =
  52                         rb_entry(*new, struct drbd_interval, rb);
  53
  54                 parent = *new;
  55                 if (this->sector < here->sector)
  56                         new = &(*new)->rb_left;
  57                 else if (this->sector > here->sector)
  58                         new = &(*new)->rb_right;
  59                 else if (this < here)
  60                         new = &(*new)->rb_left;
  61                 else if (this > here)
  62                         new = &(*new)->rb_right;
  63                 else
  64                         return false;
  65         }
  66
  67         rb_link_node(&this->rb, parent, new);
  68         rb_insert_color(&this->rb, root);
  69         rb_augment_insert(&this->rb, update_interval_end, NULL);
  70         return true;
  71 }
  72
  73 /**
  74  * drbd_contains_interval  -  check if a tree contains a given interval
  75  * @sector:     start sector of @interval
  76  * @interval:   may not be a valid pointer
  77  *
  78  * Returns if the tree contains the node @interval with start sector @start.
  79  * Does not dereference @interval until @interval is known to be a valid object
  80  * in @tree.  Returns %false if @interval is in the tree but with a different
  81  * sector number.
  82  */
  83 bool
  84 drbd_contains_interval(struct rb_root *root, sector_t sector,
  85                        struct drbd_interval *interval)
  86 {
  87         struct rb_node *node = root->rb_node;
  88
  89         while (node) {
  90                 struct drbd_interval *here =
  91                         rb_entry(node, struct drbd_interval, rb);
  92
  93                 if (sector < here->sector)
  94                         node = node->rb_left;
  95                 else if (sector > here->sector)
  96                         node = node->rb_right;
  97                 else if (interval < here)
  98                         node = node->rb_left;
  99                 else if (interval > here)
 100                         node = node->rb_right;
 101                 else
 102                         return true;
 103         }
 104         return false;
 105 }
 106
 107 /**
 108  * drbd_remove_interval  -  remove an interval from a tree
 109  */
 110 void
 111 drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
 112 {
 113         struct rb_node *deepest;
 114
 115         deepest = rb_augment_erase_begin(&this->rb);
 116         rb_erase(&this->rb, root);
 117         rb_augment_erase_end(deepest, update_interval_end, NULL);
 118 }
 119
 120 /**
 121  * drbd_find_overlap  - search for an interval overlapping with [sector, sector + size)
 122  * @sector:     start sector
 123  * @size:       size, aligned to 512 bytes
 124  *
 125  * Returns an interval overlapping with [sector, sector + size), or NULL if
 126  * there is none.  When there is more than one overlapping interval in the
 127  * tree, the interval with the lowest start sector is returned, and all other
 128  * overlapping intervals will be on the right side of the tree, reachable with
 129  * rb_next().
 130  */
 131 struct drbd_interval *
 132 drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
 133 {
 134         struct rb_node *node = root->rb_node;
 135         struct drbd_interval *overlap = NULL;
 136         sector_t end = sector + (size >> 9);
 137
 138         BUG_ON(!IS_ALIGNED(size, 512));
 139
 140         while (node) {
 141                 struct drbd_interval *here =
 142                         rb_entry(node, struct drbd_interval, rb);
 143
 144                 if (node->rb_left &&
 145                     sector < interval_end(node->rb_left)) {
 146                         /* Overlap if any must be on left side */
 147                         node = node->rb_left;
 148                 } else if (here->sector < end &&
 149                            sector < here->sector + (here->size >> 9)) {
 150                         overlap = here;
 151                         break;
 152                 } else if (sector >= here->sector) {
 153                         /* Overlap if any must be on right side */
 154                         node = node->rb_right;
 155                 } else
 156                         break;
 157         }
 158         return overlap;
 159 }
 160
 161 struct drbd_interval *
 162 drbd_next_overlap(struct drbd_interval *i, sector_t sector, unsigned int size)
 163 {
 164         sector_t end = sector + (size >> 9);
 165         struct rb_node *node;
 166
 167         for (;;) {
 168                 node = rb_next(&i->rb);
 169                 if (!node)
 170                         return NULL;
 171                 i = rb_entry(node, struct drbd_interval, rb);
 172                 if (i->sector >= end)
 173                         return NULL;
 174                 if (sector < i->sector + (i->size >> 9))
 175                         return i;
 176         }
 177 }