Bug Summary

File:tree.c
Location:line 21, column 9
Description:Access to field 'left' results in a dereference of a null pointer (loaded from variable 'right_child')

Annotated Source Code

1/* Splay tree implementation. */
2#include <string.h>
3#include <stdlib.h>
4#include <stdio.h>
5#include "lz4.h"
6#include "oleg.h"
7#include "tree.h"
8#include "logging.h"
9#include "stack.h"
10#include "errhandle.h"
11#include "cursor.h"
12
13static inline void _ols_left_rotate(ol_splay_tree *tree, ol_splay_tree_node *node) {
14 ol_splay_tree_node *right_child = node->right;
7
←
'right_child' initialized here
→
15
16 if (right_child != NULL((void *)0)) {
8
←
Assuming 'right_child' is equal to null
→
9
←
Taking false branch
→
17 node->right = right_child->left;
18 right_child->parent = node->parent;
19 }
20
21 if (right_child->left != NULL((void *)0))
10
←
Access to field 'left' results in a dereference of a null pointer (loaded from variable 'right_child')
22 right_child->left->parent = node;
23
24 if (!node->parent)
25 tree->root = right_child;
26 else if (node == node->parent->left)
27 node->parent->left = right_child;
28 else
29 node->parent->right = right_child;
30
31 right_child->left = node;
32 node->parent = right_child;
33}
34
35static inline void _ols_right_rotate(ol_splay_tree *tree, ol_splay_tree_node *node) {
36 ol_splay_tree_node *left_child = node->left;
37
38 if (left_child != NULL((void *)0)) {
39 node->left = left_child->right;
40 left_child->parent = node->parent;
41 }
42
43 if (left_child->right != NULL((void *)0))
44 left_child->right->parent = node;
45
46 if (!node->parent)
47 tree->root = left_child;
48 else if (node == node->parent->right)
49 node->parent->right = left_child;
50 else
51 node->parent->left = left_child;
52
53 left_child->right = node;
54 node->parent = left_child;
55}
56
57static inline void _ols_splay(ol_splay_tree *tree, ol_splay_tree_node *node) {
58 while (node->parent) {
4
←
Loop condition is true. Entering loop body
→
59 if (!node->parent->parent) {
5
←
Taking false branch
→
60 if (node->parent->left == node) _ols_right_rotate(tree, node->parent);
61 else _ols_left_rotate(tree, node->parent);
62 } else if (node->parent->left == node && node->parent->parent->left == node->parent) {
63 _ols_right_rotate(tree, node->parent->parent);
64 _ols_right_rotate(tree, node->parent);
65 } else if (node->parent->right == node && node->parent->parent->right == node->parent) {
66 _ols_left_rotate(tree, node->parent->parent);
67 _ols_left_rotate(tree, node->parent);
68 } else if (node->parent->left == node && node->parent->parent->right == node->parent) {
69 _ols_right_rotate(tree, node->parent);
70 _ols_left_rotate(tree, node->parent);
71 } else {
72 _ols_left_rotate(tree, node->parent);
6
←
Calling '_ols_left_rotate'
→
73 _ols_right_rotate(tree, node->parent);
74 }
75 }
76}
77
78static inline void _ols_replace(ol_splay_tree *tree,
79 ol_splay_tree_node *node_a, ol_splay_tree_node *node_b) {
80
81 if (!node_a->parent)
82 tree->root = node_b;
83 else if (node_a == node_a->parent->left)
84 node_a->parent->left = node_b;
85 else
86 node_a->parent->right = node_b;
87
88 if (node_b)
89 node_b->parent = node_a->parent;
90}
91
92ol_splay_tree_node *ols_subtree_minimum(ol_splay_tree_node *node) {
93 while (node->left != NULL((void *)0)) {
94 node = node->left;
95 }
96 return node;
97}
98
99ol_splay_tree_node *ols_subtree_maximum(ol_splay_tree_node *node) {
100 while (node->right != NULL((void *)0)) {
101 node = node->right;
102 }
103 return node;
104}
105
106ol_splay_tree_node *ols_insert(ol_splay_tree *tree, const char *key, const size_t klen, const void *ref_obj) {
107 check(klen < KEY_SIZE, "Key is too long.")if(!(klen < 250)){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Key is too long." "\n", "src/tree.c",107,((* __error()) == 0
? "None" : strerror((* __error())))); (* __error())=0; goto error
;};
108 check(key != NULL, "Key is null.")if(!(key != ((void *)0))){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Key is null." "\n", "src/tree.c",108,((* __error()) == 0 ? "None"
: strerror((* __error())))); (* __error())=0; goto error;};
109 ol_splay_tree_node *current_node = NULL((void *)0), *previous_node = NULL((void *)0);
110 current_node = tree->root;
111
112 while (current_node != NULL((void *)0)) {
113 size_t larger_key = 0;
114 previous_node = current_node;
115 larger_key = klen > current_node->klen ? klen : current_node->klen;
116 if (strncmp(current_node->key, key, larger_key) >= 0)
117 current_node = current_node->right;
118 else
119 current_node = current_node->left;
120 }
121
122 current_node = malloc(sizeof(ol_splay_tree_node));
123 current_node->left = NULL((void *)0);
124 current_node->right = NULL((void *)0);
125 current_node->parent = NULL((void *)0);
126 current_node->klen = 0;
127 memset(current_node->key, '\0', KEY_SIZE250);
128 if (strncpy(current_node->key, key, klen) != current_node->key) {
129 free(current_node);
130 return NULL((void *)0);
131 }
132 current_node->klen = klen;
133 current_node->ref_obj = ref_obj;
134 /* Put that shit into the tree */
135 current_node->parent = previous_node;
136
137 /* Figure out how current_node relates to previous_node */
138 if (previous_node == NULL((void *)0))
139 tree->root = current_node;
140 else {
141 size_t larger_key = 0;
142 larger_key = current_node->klen > previous_node->klen ?
143 current_node->klen : previous_node->klen;
144 if (strncmp(previous_node->key, current_node->key, larger_key) >= 0)
145 previous_node->right = current_node;
146 else
147 previous_node->left = current_node;
148 }
149
150 /* Splay the node to the top. */
151 _ols_splay(tree, current_node);
152 tree->rcrd_cnt++;
153
154 return current_node;
155
156error:
157 return NULL((void *)0);
158}
159int ols_find_and_delete(ol_splay_tree *tree, const char *key, const size_t klen) {
160 ol_splay_tree_node *node = ols_find(tree, key, klen);
161 return ols_delete(tree, node);
162}
163
164int ols_delete(ol_splay_tree *tree, ol_splay_tree_node *node) {
165 if (!node)
1
Assuming 'node' is non-null
→
2
←
Taking false branch
→
166 return 1;
167
168 _ols_splay(tree, node);
3
←
Calling '_ols_splay'
→
169
170 if (!node->left)
171 _ols_replace(tree, node, node->right);
172 else if (!node->right)
173 _ols_replace(tree, node, node->left);
174 else {
175 ol_splay_tree_node *minimum_node = ols_subtree_minimum(node->right);
176 if (minimum_node->parent != node) {
177 _ols_replace(tree, minimum_node, minimum_node->right);
178 minimum_node->right = node->right;
179 minimum_node->right->parent = minimum_node;
180 }
181 _ols_replace(tree, node, minimum_node);
182 minimum_node->left = node->left;
183 minimum_node->left->parent = minimum_node;
184 }
185
186 node->parent = NULL((void *)0);
187 node->left = NULL((void *)0);
188 node->right = NULL((void *)0);
189
190 free(node);
191 tree->rcrd_cnt--;
192 return 0;
193}
194
195ol_splay_tree_node *ols_find(ol_splay_tree *tree, const char *key, size_t klen) {
196 check(klen < KEY_SIZE, "Key is too long.")if(!(klen < 250)){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Key is too long." "\n", "src/tree.c",196,((* __error()) == 0
? "None" : strerror((* __error())))); (* __error())=0; goto error
;};
197 check(key != NULL, "Key is null.")if(!(key != ((void *)0))){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Key is null." "\n", "src/tree.c",197,((* __error()) == 0 ? "None"
: strerror((* __error())))); (* __error())=0; goto error;};
198 ol_splay_tree_node *current_node = tree->root;
199
200 while (current_node) {
201 size_t larger_key = 0;
202 larger_key = current_node->klen > klen ?
203 current_node->klen : klen;
204 const int result = strncmp(current_node->key, key, larger_key);
205 if (result > 0)
206 current_node = current_node->right;
207 else if (result < 0)
208 current_node = current_node->left;
209 else
210 return current_node;
211 }
212
213 return NULL((void *)0);
214
215error:
216 return NULL((void *)0);
217}
218
219static inline void _ols_free_node(ol_splay_tree_node *node) {
220 ol_stack *stack = NULL((void *)0);
221 stack = malloc(sizeof(ol_stack));
222 check_mem(stack)if(!((stack))){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Out of memory." "\n", "src/tree.c",222,((* __error()) == 0 ?
"None" : strerror((* __error())))); (* __error())=0; goto error
;};
223
224 stack->next = NULL((void *)0);
225 stack->data = NULL((void *)0);
226
227 spush(&stack, (void *)node);
228
229 int iters = 0;
230 ol_log_msg(LOG_INFO0, "Clearing tree.");
231 while (stack->next != NULL((void *)0)) {
232 iters++;
233 ol_splay_tree_node *cur_node = (ol_splay_tree_node *)spop(&stack);
234
235 if (cur_node->left != NULL((void *)0)) {
236 spush(&stack, (void *)cur_node->left);
237 }
238 if (cur_node->right != NULL((void *)0)) {
239 spush(&stack, (void *)cur_node->right);
240 }
241 free(cur_node);
242 }
243 ol_log_msg(LOG_INFO0, "Tree cleared. Iterations: %i", iters);
244 free(stack);
245
246error:
247 return;
248}
249
250void ols_close(ol_splay_tree *tree) {
251 if (tree->root == NULL((void *)0))
252 return;
253 _ols_free_node(tree->root);
254 tree->root = NULL((void *)0);
255}
256
257/* Defined in oleg.h */
258int ol_prefix_match(ol_database *db, const char *prefix, size_t plen, ol_val_array *data) {
259 if (!db->is_enabled(OL_F_SPLAYTREE, &db->feature_set))
260 return -1;
261 if (!prefix)
262 return -1;
263
264 ol_cursor cursor;
265 char **to_return = NULL((void *)0);
266 char *dest = NULL((void *)0);
267 ol_stack *matches = NULL((void *)0);
268
269 /* Build cursor */
270 check(olc_init(db, &cursor), "Could not init cursor.")if(!(olc_init(db, &cursor))){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Could not init cursor." "\n", "src/tree.c",270,((* __error(
)) == 0 ? "None" : strerror((* __error())))); (* __error())=0
; goto error;};
271
272 /* Get current node */
273 ol_splay_tree_node *current_node = _olc_get_node(&cursor);
274 /* Build up our matches stack */
275 matches = malloc(sizeof(ol_stack));
276 matches->data = NULL((void *)0);
277 matches->next = NULL((void *)0);
278
279 int imatches = 0;
280 int saw_bigger_value = 0;
281
282 while (current_node != NULL((void *)0)) {
283 const int match_result = strncmp(current_node->key, prefix, plen);
284 if (match_result == 0) {
285 spush(&matches, current_node);
286 imatches++;
287 } else if (saw_bigger_value && match_result > 0) {
288 /* We've previously seen a bigger value and now we see one
289 * again. Just quit. */
290 break;
291 }
292
293 if (match_result > 0) {
294 /* Flip the bit that says we saw a value bigger than the prefix. We
295 * should now only recurse to the current subtree minimum. */
296 saw_bigger_value = 1;
297 }
298
299
300 if (!olc_step(&cursor))
301 break;
302 current_node = _olc_get_node(&cursor);
303 }
304 debug("Found %i matches.", imatches);
305
306 /* No pointer in doing anything else if we don't have any matches. */
307 check(imatches > 0, "No matched keys.")if(!(imatches > 0)){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"No matched keys." "\n", "src/tree.c",307,((* __error()) == 0
? "None" : strerror((* __error())))); (* __error())=0; goto error
;};
308
309 /* Compute size of everything and malloc it here */
310 size_t total_size = sizeof(char *) * imatches;
311 to_return = malloc(total_size);
312 check_mem(to_return)if(!((to_return))){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Out of memory." "\n", "src/tree.c",312,((* __error()) == 0 ?
"None" : strerror((* __error())))); (* __error())=0; goto error
;};
313
314 int i;
315 for (i = 0;i < imatches; i++) {
316 ol_splay_tree_node *cur_node = (ol_splay_tree_node *)spop(&matches);
317 ol_bucket *deref = (ol_bucket *)cur_node->ref_obj;
318
319 unsigned char *data_ptr = db->values + deref->data_offset;
320 size_t data_len = 0;
321 data_len = deref->original_size;
322
323 dest = malloc(data_len);
324 check_mem(dest)if(!((dest))){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Out of memory." "\n", "src/tree.c",324,((* __error()) == 0 ?
"None" : strerror((* __error())))); (* __error())=0; goto error
;};
325 if (db->is_enabled(OL_F_LZ4, &db->feature_set)) {
326 int processed = 0;
327 processed = LZ4_decompress_fast((char *)data_ptr, dest, data_len);
328 check(processed == deref->data_size, "Could not decompress data.")if(!(processed == deref->data_size)){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Could not decompress data." "\n", "src/tree.c",328,((* __error
()) == 0 ? "None" : strerror((* __error())))); (* __error())=
0; goto error;};
329 } else {
330 unsigned char *to_check = memcpy(data_ptr, dest, data_len);
331 check(to_check == data_ptr, "Could not copy data to msgpuck buffer.")if(!(to_check == data_ptr)){fprintf(__stderrp,"[ERROR] (%s:%d: errno: %s) "
"Could not copy data to msgpuck buffer." "\n", "src/tree.c",
331,((* __error()) == 0 ? "None" : strerror((* __error()))));
(* __error())=0; goto error;};
332 }
333
334 to_return[i] = dest;
335 }
336
337 *data = to_return;
338 free(matches);
339 return imatches;
340
341error:
342 if (matches != NULL((void *)0))
343 free(matches);
344 if (*data != NULL((void *)0))
345 free(*data);
346 if (to_return != NULL((void *)0))
347 free(to_return);
348 if (dest != NULL((void *)0))
349 free(dest);
350
351 return -1;
352}