Bug Summary

File:obj/../kern/rbtree.c
Location:line 95, column 21
Description:Access to field 'parent' results in a dereference of a null pointer (loaded from variable 'node')

Annotated Source Code

1/*
2 * Copyright (c) 2010, 2012 Richard Braun.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include <kern/assert.h>
27#include <kern/rbtree.h>
28#include <kern/rbtree_i.h>
29#include <sys/types.h>
30
31#define unlikely(expr)__builtin_expect(!!(expr), 0) __builtin_expect(!!(expr), 0)
32
33/*
34 * Return the index of a node in the children array of its parent.
35 *
36 * The parent parameter must not be null, and must be the parent of the
37 * given node.
38 */
39static inline int rbtree_index(const struct rbtree_node *node,
40 const struct rbtree_node *parent)
41{
42 assert(parent != NULL)({ if (!(parent != ((void *) 0))) Assert("parent != NULL", "../kern/rbtree.c"
, 42); });
43 assert((node == NULL) || (rbtree_parent(node) == parent))({ if (!((node == ((void *) 0)) || (rbtree_parent(node) == parent
))) Assert("(node == NULL) || (rbtree_parent(node) == parent)"
, "../kern/rbtree.c", 43); });
44
45 if (parent->children[RBTREE_LEFT0] == node)
46 return RBTREE_LEFT0;
47
48 assert(parent->children[RBTREE_RIGHT] == node)({ if (!(parent->children[1] == node)) Assert("parent->children[RBTREE_RIGHT] == node"
, "../kern/rbtree.c", 48); });
49
50 return RBTREE_RIGHT1;
51}
52
53/*
54 * Return the color of a node.
55 */
56static inline int rbtree_color(const struct rbtree_node *node)
57{
58 return node->parent & RBTREE_COLOR_MASK0x1UL;
59}
60
61/*
62 * Return true if the node is red.
63 */
64static inline int rbtree_is_red(const struct rbtree_node *node)
65{
66 return rbtree_color(node) == RBTREE_COLOR_RED0;
67}
68
69/*
70 * Return true if the node is black.
71 */
72static inline int rbtree_is_black(const struct rbtree_node *node)
73{
74 return rbtree_color(node) == RBTREE_COLOR_BLACK1;
75}
76
77/*
78 * Set the parent of a node, retaining its current color.
79 */
80static inline void rbtree_set_parent(struct rbtree_node *node,
81 struct rbtree_node *parent)
82{
83 assert(rbtree_check_alignment(node))({ if (!(rbtree_check_alignment(node))) Assert("rbtree_check_alignment(node)"
, "../kern/rbtree.c", 83); });
84 assert(rbtree_check_alignment(parent))({ if (!(rbtree_check_alignment(parent))) Assert("rbtree_check_alignment(parent)"
, "../kern/rbtree.c", 84); });
85
86 node->parent = (unsigned long)parent | (node->parent & RBTREE_COLOR_MASK0x1UL);
87}
88
89/*
90 * Set the color of a node, retaining its current parent.
91 */
92static inline void rbtree_set_color(struct rbtree_node *node, int color)
93{
94 assert((color & ~RBTREE_COLOR_MASK) == 0)({ if (!((color & ~0x1UL) == 0)) Assert("(color & ~RBTREE_COLOR_MASK) == 0"
, "../kern/rbtree.c", 94); });
95 node->parent = (node->parent & RBTREE_PARENT_MASK(~0x3UL)) | color;
18
←
Access to field 'parent' results in a dereference of a null pointer (loaded from variable 'node')
96}
97
98/*
99 * Set the color of a node to red, retaining its current parent.
100 */
101static inline void rbtree_set_red(struct rbtree_node *node)
102{
103 rbtree_set_color(node, RBTREE_COLOR_RED0);
104}
105
106/*
107 * Set the color of a node to black, retaining its current parent.
108 */
109static inline void rbtree_set_black(struct rbtree_node *node)
110{
111 rbtree_set_color(node, RBTREE_COLOR_BLACK1);
16
←
Passing null pointer value via 1st parameter 'node'
→
17
←
Calling 'rbtree_set_color'
→
112}
113
114/*
115 * Perform a tree rotation, rooted at the given node.
116 *
117 * The direction parameter defines the rotation direction and is either
118 * RBTREE_LEFT or RBTREE_RIGHT.
119 */
120static void rbtree_rotate(struct rbtree *tree, struct rbtree_node *node,
121 int direction)
122{
123 struct rbtree_node *parent, *rnode;
124 int left, right;
125
126 left = direction;
127 right = 1 - left;
128 parent = rbtree_parent(node);
129 rnode = node->children[right];
130
131 node->children[right] = rnode->children[left];
132
133 if (rnode->children[left] != NULL((void *) 0))
134 rbtree_set_parent(rnode->children[left], node);
135
136 rnode->children[left] = node;
137 rbtree_set_parent(rnode, parent);
138
139 if (unlikely(parent == NULL)__builtin_expect(!!(parent == ((void *) 0)), 0))
140 tree->root = rnode;
141 else
142 parent->children[rbtree_index(node, parent)] = rnode;
143
144 rbtree_set_parent(node, rnode);
145}
146
147void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
148 int index, struct rbtree_node *node)
149{
150 struct rbtree_node *grand_parent, *uncle, *tmp;
151 int left, right;
152
153 assert(rbtree_check_alignment(parent))({ if (!(rbtree_check_alignment(parent))) Assert("rbtree_check_alignment(parent)"
, "../kern/rbtree.c", 153); });
154 assert(rbtree_check_alignment(node))({ if (!(rbtree_check_alignment(node))) Assert("rbtree_check_alignment(node)"
, "../kern/rbtree.c", 154); });
155
156 node->parent = (unsigned long)parent | RBTREE_COLOR_RED0;
157 node->children[RBTREE_LEFT0] = NULL((void *) 0);
158 node->children[RBTREE_RIGHT1] = NULL((void *) 0);
159
160 if (unlikely(parent == NULL)__builtin_expect(!!(parent == ((void *) 0)), 0))
161 tree->root = node;
162 else
163 parent->children[index] = node;
164
165 for (;;) {
166 if (parent == NULL((void *) 0)) {
167 rbtree_set_black(node);
168 break;
169 }
170
171 if (rbtree_is_black(parent))
172 break;
173
174 grand_parent = rbtree_parent(parent);
175 assert(grand_parent != NULL)({ if (!(grand_parent != ((void *) 0))) Assert("grand_parent != NULL"
, "../kern/rbtree.c", 175); });
176
177 left = rbtree_index(parent, grand_parent);
178 right = 1 - left;
179
180 uncle = grand_parent->children[right];
181
182 /*
183 * Uncle is red. Flip colors and repeat at grand parent.
184 */
185 if ((uncle != NULL((void *) 0)) && rbtree_is_red(uncle)) {
186 rbtree_set_black(uncle);
187 rbtree_set_black(parent);
188 rbtree_set_red(grand_parent);
189 node = grand_parent;
190 parent = rbtree_parent(node);
191 continue;
192 }
193
194 /*
195 * Node is the right child of its parent. Rotate left at parent.
196 */
197 if (parent->children[right] == node) {
198 rbtree_rotate(tree, parent, left);
199 tmp = node;
200 node = parent;
201 parent = tmp;
202 }
203
204 /*
205 * Node is the left child of its parent. Handle colors, rotate right
206 * at grand parent, and leave.
207 */
208 rbtree_set_black(parent);
209 rbtree_set_red(grand_parent);
210 rbtree_rotate(tree, grand_parent, right);
211 break;
212 }
213
214 assert(rbtree_is_black(tree->root))({ if (!(rbtree_is_black(tree->root))) Assert("rbtree_is_black(tree->root)"
, "../kern/rbtree.c", 214); });
215}
216
217void rbtree_remove(struct rbtree *tree, struct rbtree_node *node)
218{
219 struct rbtree_node *child, *parent, *brother;
220 int color, left, right;
221
222 if (node->children[RBTREE_LEFT0] == NULL((void *) 0))
1
Taking false branch
→
223 child = node->children[RBTREE_RIGHT1];
224 else if (node->children[RBTREE_RIGHT1] == NULL((void *) 0))
2
←
Taking false branch
→
225 child = node->children[RBTREE_LEFT0];
226 else {
227 struct rbtree_node *successor;
228
229 /*
230 * Two-children case: replace the node with its successor.
231 */
232
233 successor = node->children[RBTREE_RIGHT1];
234
235 while (successor->children[RBTREE_LEFT0] != NULL((void *) 0))
3
←
Loop condition is false. Execution continues on line 238
→
236 successor = successor->children[RBTREE_LEFT0];
237
238 color = rbtree_color(successor);
239 child = successor->children[RBTREE_RIGHT1];
240 parent = rbtree_parent(node);
241
242 if (unlikely(parent == NULL)__builtin_expect(!!(parent == ((void *) 0)), 0))
4
←
Taking false branch
→
243 tree->root = successor;
244 else
245 parent->children[rbtree_index(node, parent)] = successor;
246
247 parent = rbtree_parent(successor);
248
249 /*
250 * Set parent directly to keep the original color.
251 */
252 successor->parent = node->parent;
253 successor->children[RBTREE_LEFT0] = node->children[RBTREE_LEFT0];
254 rbtree_set_parent(successor->children[RBTREE_LEFT0], successor);
255
256 if (node == parent)
5
←
Taking false branch
→
257 parent = successor;
258 else {
259 successor->children[RBTREE_RIGHT1] = node->children[RBTREE_RIGHT1];
260 rbtree_set_parent(successor->children[RBTREE_RIGHT1], successor);
261 parent->children[RBTREE_LEFT0] = child;
262
263 if (child != NULL((void *) 0))
6
←
Assuming 'child' is equal to null
→
7
←
Taking false branch
→
264 rbtree_set_parent(child, parent);
265 }
266
267 goto update_color;
8
←
Control jumps to line 290
→
268 }
269
270 /*
271 * Node has at most one child.
272 */
273
274 color = rbtree_color(node);
275 parent = rbtree_parent(node);
276
277 if (child != NULL((void *) 0))
278 rbtree_set_parent(child, parent);
279
280 if (unlikely(parent == NULL)__builtin_expect(!!(parent == ((void *) 0)), 0))
281 tree->root = child;
282 else
283 parent->children[rbtree_index(node, parent)] = child;
284
285 /*
286 * The node has been removed, update the colors. The child pointer can
287 * be null, in which case it is considered a black leaf.
288 */
289update_color:
290 if (color == RBTREE_COLOR_RED0)
9
←
Assuming 'color' is not equal to 0
→
10
←
Taking false branch
→
291 return;
292
293 for (;;) {
11
←
Loop condition is true. Entering loop body
→
294 if ((child != NULL((void *) 0)) && rbtree_is_red(child)) {
295 rbtree_set_black(child);
296 break;
297 }
298
299 if (parent == NULL((void *) 0))
12
←
Taking false branch
→
300 break;
301
302 left = rbtree_index(child, parent);
303 right = 1 - left;
304
305 brother = parent->children[right];
306
307 /*
308 * Brother is red. Recolor and rotate left at parent so that brother
309 * becomes black.
310 */
311 if (rbtree_is_red(brother)) {
13
←
Taking false branch
→
312 rbtree_set_black(brother);
313 rbtree_set_red(parent);
314 rbtree_rotate(tree, parent, left);
315 brother = parent->children[right];
316 }
317
318 /*
319 * Brother has no red child. Recolor and repeat at parent.
320 */
321 if (((brother->children[RBTREE_LEFT0] == NULL((void *) 0))
322 || rbtree_is_black(brother->children[RBTREE_LEFT0]))
323 && ((brother->children[RBTREE_RIGHT1] == NULL((void *) 0))
324 || rbtree_is_black(brother->children[RBTREE_RIGHT1]))) {
325 rbtree_set_red(brother);
326 child = parent;
327 parent = rbtree_parent(child);
328 continue;
329 }
330
331 /*
332 * Brother's right child is black. Recolor and rotate right at brother.
333 */
334 if ((brother->children[right] == NULL((void *) 0))
335 || rbtree_is_black(brother->children[right])) {
336 rbtree_set_black(brother->children[left]);
337 rbtree_set_red(brother);
338 rbtree_rotate(tree, brother, right);
339 brother = parent->children[right];
340 }
341
342 /*
343 * Brother's left child is black. Exchange parent and brother colors
344 * (we already know brother is black), set brother's right child black,
345 * rotate left at parent and leave.
346 */
347 rbtree_set_color(brother, rbtree_color(parent));
348 rbtree_set_black(parent);
349 rbtree_set_black(brother->children[right]);
14
←
Passing null pointer value via 1st parameter 'node'
→
15
←
Calling 'rbtree_set_black'
→
350 rbtree_rotate(tree, parent, left);
351 break;
352 }
353
354 assert((tree->root == NULL) || rbtree_is_black(tree->root))({ if (!((tree->root == ((void *) 0)) || rbtree_is_black(tree
->root))) Assert("(tree->root == NULL) || rbtree_is_black(tree->root)"
, "../kern/rbtree.c", 354); });
355}
356
357struct rbtree_node * rbtree_nearest(struct rbtree_node *parent, int index,
358 int direction)
359{
360 assert(rbtree_check_index(direction))({ if (!(rbtree_check_index(direction))) Assert("rbtree_check_index(direction)"
, "../kern/rbtree.c", 360); });
361
362 if (parent == NULL((void *) 0))
363 return NULL((void *) 0);
364
365 assert(rbtree_check_index(index))({ if (!(rbtree_check_index(index))) Assert("rbtree_check_index(index)"
, "../kern/rbtree.c", 365); });
366
367 if (index != direction)
368 return parent;
369
370 return rbtree_walk(parent, direction);
371}
372
373struct rbtree_node * rbtree_firstlast(const struct rbtree *tree, int direction)
374{
375 struct rbtree_node *prev, *cur;
376
377 assert(rbtree_check_index(direction))({ if (!(rbtree_check_index(direction))) Assert("rbtree_check_index(direction)"
, "../kern/rbtree.c", 377); });
378
379 prev = NULL((void *) 0);
380
381 for (cur = tree->root; cur != NULL((void *) 0); cur = cur->children[direction])
382 prev = cur;
383
384 return prev;
385}
386
387struct rbtree_node * rbtree_walk(struct rbtree_node *node, int direction)
388{
389 int left, right;
390
391 assert(rbtree_check_index(direction))({ if (!(rbtree_check_index(direction))) Assert("rbtree_check_index(direction)"
, "../kern/rbtree.c", 391); });
392
393 left = direction;
394 right = 1 - left;
395
396 if (node == NULL((void *) 0))
397 return NULL((void *) 0);
398
399 if (node->children[left] != NULL((void *) 0)) {
400 node = node->children[left];
401
402 while (node->children[right] != NULL((void *) 0))
403 node = node->children[right];
404 } else {
405 struct rbtree_node *parent;
406 int index;
407
408 for (;;) {
409 parent = rbtree_parent(node);
410
411 if (parent == NULL((void *) 0))
412 return NULL((void *) 0);
413
414 index = rbtree_index(node, parent);
415 node = parent;
416
417 if (index == right)
418 break;
419 }
420 }
421
422 return node;
423}
424
425/*
426 * Return the left-most deepest child node of the given node.
427 */
428static struct rbtree_node * rbtree_find_deepest(struct rbtree_node *node)
429{
430 struct rbtree_node *parent;
431
432 assert(node != NULL)({ if (!(node != ((void *) 0))) Assert("node != NULL", "../kern/rbtree.c"
, 432); });
433
434 for (;;) {
435 parent = node;
436 node = node->children[RBTREE_LEFT0];
437
438 if (node == NULL((void *) 0)) {
439 node = parent->children[RBTREE_RIGHT1];
440
441 if (node == NULL((void *) 0))
442 return parent;
443 }
444 }
445}
446
447struct rbtree_node * rbtree_postwalk_deepest(const struct rbtree *tree)
448{
449 struct rbtree_node *node;
450
451 node = tree->root;
452
453 if (node == NULL((void *) 0))
454 return NULL((void *) 0);
455
456 return rbtree_find_deepest(node);
457}
458
459struct rbtree_node * rbtree_postwalk_unlink(struct rbtree_node *node)
460{
461 struct rbtree_node *parent;
462 int index;
463
464 if (node == NULL((void *) 0))
465 return NULL((void *) 0);
466
467 assert(node->children[RBTREE_LEFT] == NULL)({ if (!(node->children[0] == ((void *) 0))) Assert("node->children[RBTREE_LEFT] == NULL"
, "../kern/rbtree.c", 467); });
468 assert(node->children[RBTREE_RIGHT] == NULL)({ if (!(node->children[1] == ((void *) 0))) Assert("node->children[RBTREE_RIGHT] == NULL"
, "../kern/rbtree.c", 468); });
469
470 parent = rbtree_parent(node);
471
472 if (parent == NULL((void *) 0))
473 return NULL((void *) 0);
474
475 index = rbtree_index(node, parent);
476 parent->children[index] = NULL((void *) 0);
477 node = parent->children[RBTREE_RIGHT1];
478
479 if (node == NULL((void *) 0))
480 return parent;
481
482 return rbtree_find_deepest(node);
483}