aboutsummaryrefslogtreecommitdiffstats
path: root/drivers/block/drbd
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/block/drbd')
-rw-r--r--drivers/block/drbd/Makefile1
-rw-r--r--drivers/block/drbd/drbd_interval.c156
-rw-r--r--drivers/block/drbd/drbd_interval.h31
3 files changed, 188 insertions, 0 deletions
diff --git a/drivers/block/drbd/Makefile b/drivers/block/drbd/Makefile
index 0d3f337ff5ff..cacbb04f285d 100644
--- a/drivers/block/drbd/Makefile
+++ b/drivers/block/drbd/Makefile
@@ -1,5 +1,6 @@
1drbd-y := drbd_bitmap.o drbd_proc.o 1drbd-y := drbd_bitmap.o drbd_proc.o
2drbd-y += drbd_worker.o drbd_receiver.o drbd_req.o drbd_actlog.o 2drbd-y += drbd_worker.o drbd_receiver.o drbd_req.o drbd_actlog.o
3drbd-y += drbd_main.o drbd_strings.o drbd_nl.o 3drbd-y += drbd_main.o drbd_strings.o drbd_nl.o
4drbd-y += drbd_interval.o
4 5
5obj-$(CONFIG_BLK_DEV_DRBD) += drbd.o 6obj-$(CONFIG_BLK_DEV_DRBD) += drbd.o
diff --git a/drivers/block/drbd/drbd_interval.c b/drivers/block/drbd/drbd_interval.c
new file mode 100644
index 000000000000..2511dd9993f3
--- /dev/null
+++ b/drivers/block/drbd/drbd_interval.c
@@ -0,0 +1,156 @@
1#include "drbd_interval.h"
2
3/**
4 * interval_end - return end of @node
5 */
6static inline
7sector_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 */
20static void
21update_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 */
43bool
44drbd_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->sector > here->sector)
62 new = &(*new)->rb_right;
63 return false;
64 }
65
66 rb_link_node(&this->rb, parent, new);
67 rb_insert_color(&this->rb, root);
68 rb_augment_insert(&this->rb, update_interval_end, NULL);
69 return true;
70}
71
72/**
73 * drbd_contains_interval - check if a tree contains a given interval
74 * @sector: start sector of @interval
75 * @interval: may not be a valid pointer
76 *
77 * Returns if the tree contains the node @interval with start sector @start.
78 * Does not dereference @interval until @interval is known to be a valid object
79 * in @tree. Returns %false if @interval is in the tree but with a different
80 * sector number.
81 */
82bool
83drbd_contains_interval(struct rb_root *root, sector_t sector,
84 struct drbd_interval *interval)
85{
86 struct rb_node *node = root->rb_node;
87
88 while (node) {
89 struct drbd_interval *here =
90 rb_entry(node, struct drbd_interval, rb);
91
92 if (sector < here->sector)
93 node = node->rb_left;
94 else if (sector > here->sector)
95 node = node->rb_right;
96 else if (interval < here)
97 node = node->rb_left;
98 else if (interval > here)
99 node = node->rb_right;
100 else
101 return interval->sector == sector;
102 }
103 return false;
104}
105
106/**
107 * drbd_remove_interval - remove an interval from a tree
108 */
109void
110drbd_remove_interval(struct rb_root *root, struct drbd_interval *this)
111{
112 struct rb_node *deepest;
113
114 deepest = rb_augment_erase_begin(&this->rb);
115 rb_erase(&this->rb, root);
116 rb_augment_erase_end(deepest, update_interval_end, NULL);
117}
118
119/**
120 * drbd_find_overlap - search for an interval overlapping with [sector, sector + size)
121 * @sector: start sector
122 * @size: size, aligned to 512 bytes
123 *
124 * Returns the interval overlapping with [sector, sector + size), or NULL.
125 * When there is more than one overlapping interval in the tree, the interval
126 * with the lowest start sector is returned.
127 */
128struct drbd_interval *
129drbd_find_overlap(struct rb_root *root, sector_t sector, unsigned int size)
130{
131 struct rb_node *node = root->rb_node;
132 struct drbd_interval *overlap = NULL;
133 sector_t end = sector + (size >> 9);
134
135 BUG_ON(!IS_ALIGNED(size, 512));
136
137 while (node) {
138 struct drbd_interval *here =
139 rb_entry(node, struct drbd_interval, rb);
140
141 if (node->rb_left &&
142 sector < interval_end(node->rb_left)) {
143 /* Overlap if any must be on left side */
144 node = node->rb_left;
145 } else if (here->sector < end &&
146 sector < here->sector + (here->size >> 9)) {
147 overlap = here;
148 break;
149 } else if (sector >= here->sector) {
150 /* Overlap if any must be on right side */
151 node = node->rb_right;
152 } else
153 break;
154 }
155 return overlap;
156}
diff --git a/drivers/block/drbd/drbd_interval.h b/drivers/block/drbd/drbd_interval.h
new file mode 100644
index 000000000000..bf8dcf7bab09
--- /dev/null
+++ b/drivers/block/drbd/drbd_interval.h
@@ -0,0 +1,31 @@
1#ifndef __DRBD_INTERVAL_H
2#define __DRBD_INTERVAL_H
3
4#include <linux/types.h>
5#include <linux/rbtree.h>
6
7struct drbd_interval {
8 struct rb_node rb;
9 sector_t sector; /* start sector of the interval */
10 unsigned int size; /* size in bytes */
11 sector_t end; /* highest interval end in subtree */
12};
13
14static inline void drbd_clear_interval(struct drbd_interval *i)
15{
16 RB_CLEAR_NODE(&i->rb);
17}
18
19static inline bool drbd_interval_empty(struct drbd_interval *i)
20{
21 return RB_EMPTY_NODE(&i->rb);
22}
23
24bool drbd_insert_interval(struct rb_root *, struct drbd_interval *);
25struct drbd_interval *drbd_find_interval(struct rb_root *, sector_t,
26 struct drbd_interval *);
27void drbd_remove_interval(struct rb_root *, struct drbd_interval *);
28struct drbd_interval *drbd_find_overlap(struct rb_root *, sector_t,
29 unsigned int);
30
31#endif /* __DRBD_INTERVAL_H */
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-23 11:13:51 -0500