1 /** Copyright (C) 2010. See COPYRIGHT in top-level directory.
2 *
3 * Conflict Tree -- James Dinan <dinan@mcs.anl.gov>
4 *
5 * Conflict trees are used by ARMCI-MPI to detect conflicting accesses due to
6 * overlapping memory regions.
7 *
8 * This implementation uses an AVL tree which is a self-balancing binary tree.
9 * In contrast with interval and segment trees which can store mutiple
10 * overlapping regions and support stabbing queries, the conflict tree does
11 * not allow any overlap among elements in the tree. If an overlapping insert
12 * is performed, it will fail. Thus, objects in the tree are totally ordered
13 * and a standard binary tree (in this case, the AVL tree) is sufficient for
14 * detecting conflicts.
15 */
16
17 #include <stdio.h>
18 #include <stdlib.h>
19
20 #include <debug.h>
21 #include <conflict_tree.h>
22
23 #define MAX(A,B) (((A) > (B)) ? A : B)
24
25 static ctree_t ctree_balance(ctree_t node);
26 static void ctree_destroy_rec(ctree_t root);
27 static inline int ctree_node_height(ctree_t node);
28 static inline void ctree_rotate_left(ctree_t node);
29 static inline void ctree_rotate_right(ctree_t node);
30
31 const ctree_t CTREE_EMPTY = NULL;
32
33
34 /** Locate the node that conflicts with the given address range.
35 *
36 * @param[in] root Root of the ctree.
37 * @param[in] lo Low end of the range.
38 * @param[in] hi High end of the range.
39 * @return Pointer to the ctree node or NULL if not found.
40 */
ctree_locate(ctree_t root,uint8_t * lo,uint8_t * hi)41 ctree_t ctree_locate(ctree_t root, uint8_t *lo, uint8_t *hi) {
42 ctree_t cur = root;
43
44 while (cur != NULL) {
45 if ( (lo >= cur->lo && lo <= cur->hi)
46 || (hi >= cur->lo && hi <= cur->hi)
47 || (lo < cur->lo && hi > cur->hi))
48 break;
49
50 else if (lo < cur->lo)
51 cur = cur->left;
52
53 else /* lo > cur->hi */
54 cur = cur->right;
55 }
56
57 return cur;
58 }
59
60
61 /** Insert an address range into the conflict detection tree.
62 *
63 * @param[inout] root The root of the tree
64 * @param[in] lo Lower bound of the address range
65 * @param[in] hi Upper bound of the address range
66 * @return Zero on success, nonzero when a conflict is detected.
67 * When a conflict exists, the range is not added.
68 */
ctree_insert(ctree_t * root,uint8_t * lo,uint8_t * hi)69 int ctree_insert(ctree_t *root, uint8_t *lo, uint8_t *hi) {
70 ctree_t cur;
71 ctree_t new_node = (ctree_t) malloc(sizeof(struct ctree_node_s));
72
73 new_node->lo = lo;
74 new_node->hi = hi;
75 new_node->height = 1;
76 new_node->parent = NULL;
77 new_node->left = NULL;
78 new_node->right = NULL;
79
80 cur = *root;
81
82 // CASE: Empty tree
83 if (cur == NULL) {
84 *root = new_node;
85 return 0;
86 }
87
88 for (;;) {
89
90 // Check for conflicts as we go
91 if ( (lo >= cur->lo && lo <= cur->hi)
92 || (hi >= cur->lo && hi <= cur->hi)
93 || (lo < cur->lo && hi > cur->hi)) {
94 ARMCII_Dbg_print(DEBUG_CAT_CTREE, "Conflict inserting [%p, %p] with [%p, %p]\n", lo, hi, cur->lo, cur->hi);
95 free(new_node);
96 return 1;
97 }
98
99 // Place in left subtree
100 else if (lo < cur->lo) {
101 if (cur->left == NULL) {
102 new_node->parent = cur;
103 cur->left = new_node;
104 *root = ctree_balance(cur);
105 return 0;
106 } else {
107 cur = cur->left;
108 }
109 }
110
111 // Place in right subtree
112 else /* lo > cur->hi */ {
113 if (cur->right == NULL) {
114 new_node->parent = cur;
115 cur->right = new_node;
116 *root = ctree_balance(cur);
117 return 0;
118 } else {
119 cur = cur->right;
120 }
121 }
122 }
123 }
124
125
126 /** Rotate the given pivot node to the left.
127 *
128 * @param[in] node This is the pivot node, it will be the new subtree root
129 * after the rotation is performed.
130 */
ctree_rotate_left(ctree_t node)131 static inline void ctree_rotate_left(ctree_t node) {
132 ctree_t old_root = node->parent;
133
134 //ARMCII_Dbg_print(DEBUG_CAT_CTREE, "[%10p, %10p] l=%d r=%d\n", node->lo, node->hi,
135 // ctree_node_height(node->left), ctree_node_height(node->right));
136
137 ARMCII_Assert(old_root->right == node);
138
139 // Set the parent pointer
140 node->parent = old_root->parent;
141
142 // Set the parent's child pointer
143 if (node->parent != NULL) {
144 if (node->parent->left == old_root)
145 node->parent->left = node;
146 else
147 node->parent->right = node;
148 }
149
150 // Set child pointers and their parents
151 old_root->right = node->left;
152 if (old_root->right != NULL)
153 old_root->right->parent = old_root;
154
155 node->left = old_root;
156 node->left->parent = node;
157
158 old_root->height = MAX(ctree_node_height(old_root->left), ctree_node_height(old_root->right)) + 1;
159 node->height = MAX(ctree_node_height(node->left), ctree_node_height(node->right)) + 1;
160 }
161
162
163 /** Rotate the given pivot node to the right.
164 *
165 * @param[in] node This is the pivot node, it will be the new subtree root
166 * after the rotation is performed.
167 */
ctree_rotate_right(ctree_t node)168 static inline void ctree_rotate_right(ctree_t node) {
169 ctree_t old_root = node->parent;
170
171 //ARMCII_Dbg_print(DEBUG_CAT_CTREE, "[%10p, %10p] l=%d r=%d\n", node->lo, node->hi,
172 // ctree_node_height(node->left), ctree_node_height(node->right));
173
174 ARMCII_Assert(old_root->left == node);
175
176 // Set the parent pointer
177 node->parent = old_root->parent;
178
179 // Set the parent's child pointer
180 if (node->parent != NULL) {
181 if (node->parent->left == old_root)
182 node->parent->left = node;
183 else
184 node->parent->right = node;
185 }
186
187 // Set child pointers and their parents
188 old_root->left = node->right;
189 if (old_root->left != NULL)
190 old_root->left->parent = old_root;
191
192 node->right = old_root;
193 node->right->parent = node;
194
195 old_root->height = MAX(ctree_node_height(old_root->left), ctree_node_height(old_root->right)) + 1;
196 node->height = MAX(ctree_node_height(node->left), ctree_node_height(node->right)) + 1;
197 }
198
199
200 /** Fetch the height of a given node.
201 */
ctree_node_height(ctree_t node)202 static inline int ctree_node_height(ctree_t node) {
203 if (node == NULL)
204 return 0;
205 else
206 return node->height;
207 }
208
209
210 /** Rebalance the tree starting with the current node and proceeding
211 * upwards towards the root.
212 */
ctree_balance(ctree_t node)213 static ctree_t ctree_balance(ctree_t node) {
214 ctree_t root = node;
215
216 while (node != NULL) {
217 int height_l = ctree_node_height(node->left);
218 int height_r = ctree_node_height(node->right);
219
220 node->height = MAX(ctree_node_height(node->left), ctree_node_height(node->right)) + 1;
221
222 // Rebalance to preserve the property that right and left heights
223 // differ by at most 1.
224 if (abs(height_l - height_r) >= 2) {
225
226 // CASE: Right is heavy
227 if (height_l - height_r == -2) {
228 int height_r_l = ctree_node_height(node->right->left);
229 int height_r_r = ctree_node_height(node->right->right);
230
231 // CASE: Right, right
232 if (height_r_l - height_r_r <= 0) {
233 node = node->right;
234 ctree_rotate_left(node);
235 }
236 // CASE: Right, left
237 else {
238 ctree_rotate_right(node->right->left);
239 node = node->right;
240 ctree_rotate_left(node);
241 }
242
243 // CASE: Left is heavy
244 } else if (height_l - height_r == 2) {
245 int height_l_l = ctree_node_height(node->left->left);
246 int height_l_r = ctree_node_height(node->left->right);
247
248 // CASE: Left, left
249 if (height_l_l - height_l_r >= 0) {
250 node = node->left;
251 ctree_rotate_right(node);
252 }
253 // CASE: Left, right
254 else {
255 ctree_rotate_left(node->left->right);
256 node = node->left;
257 ctree_rotate_right(node);
258 }
259
260 } else {
261 ARMCII_Error("CTree invariant violated, height difference of %d is too large", height_l - height_r);
262 }
263 }
264
265 root = node;
266 node = node->parent;
267 }
268
269 return root;
270 }
271
272
273 /** Recursive function to traverse a tree and destroy all its nodes.
274 */
ctree_destroy_rec(ctree_t root)275 static void ctree_destroy_rec(ctree_t root) {
276 if (root == NULL) return;
277
278 ctree_destroy_rec(root->left);
279 ctree_destroy_rec(root->right);
280
281 free(root);
282 }
283
284
285 /** Destroy a conflict tree.
286 */
ctree_destroy(ctree_t * root)287 void ctree_destroy(ctree_t *root) {
288 ctree_destroy_rec(*root);
289
290 *root = NULL;
291 }
292
293
294 /** Print out the contents of the conflict detection tree.
295 */
ctree_print(ctree_t root)296 void ctree_print(ctree_t root) {
297 if (root != NULL) {
298 int i,idx;
299 char s[32] = "";
300
301 ctree_print(root->left);
302
303 for (i = 1, idx = 0; i < 32-1 && i < root->height; i++)
304 idx += sprintf(s+idx, "\t");
305
306 printf("%10p:%s[%p, %p] p=%p h=%d\n", (void*)root, s, root->lo, root->hi, (void*)(root->parent), root->height);
307
308 ctree_print(root->right);
309 }
310 }
311