user_data2: add skb_network_header()
[smatch.git] / smatch_implied.c
blob664c297fe365cbb83e4ae1b746080fbf44e11a24
1 /*
2 * Copyright (C) 2008 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * Imagine we have this code:
20 * foo = 1;
21 * if (bar)
22 * foo = 99;
23 * else
24 * frob();
25 * // <-- point #1
26 * if (foo == 99) // <-- point #2
27 * bar->baz; // <-- point #3
30 * At point #3 bar is non null and can be dereferenced.
32 * It's smatch_implied.c which sets bar to non null at point #2.
34 * At point #1 merge_slist() stores the list of states from both
35 * the true and false paths. On the true path foo == 99 and on
36 * the false path foo == 1. merge_slist() sets their pool
37 * list to show the other states which were there when foo == 99.
39 * When it comes to the if (foo == 99) the smatch implied hook
40 * looks for all the pools where foo was not 99. It makes a list
41 * of those.
43 * Then for bar (and all the other states) it says, ok bar is a
44 * merged state that came from these previous states. We'll
45 * chop out all the states where it came from a pool where
46 * foo != 99 and merge it all back together.
48 * That is the implied state of bar.
50 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
51 * that is the pool where it was first set. The my pool gets set when
52 * code paths merge. States that have been set since the last merge do
53 * not have a ->pool.
54 * merge_sm_state() sets ->left and ->right. (These are the states which were
55 * merged to form the current state.)
56 * a pool: a pool is an slist that has been merged with another slist.
59 #include <sys/time.h>
60 #include <time.h>
61 #include "smatch.h"
62 #include "smatch_slist.h"
63 #include "smatch_extra.h"
65 char *implied_debug_msg;
66 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
68 int option_debug_implied = 0;
69 int option_no_implied = 0;
71 #define RIGHT 0
72 #define LEFT 1
75 * tmp_range_list():
76 * It messes things up to free range list allocations. This helper fuction
77 * lets us reuse memory instead of doing new allocations.
79 static struct range_list *tmp_range_list(long long num)
81 static struct range_list *my_list = NULL;
82 static struct data_range *my_range;
84 __free_ptr_list((struct ptr_list **)&my_list);
85 my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
86 add_ptr_list(&my_list, my_range);
87 return my_list;
90 static void print_debug_tf(struct sm_state *s, int istrue, int isfalse)
92 if (!option_debug_implied && !option_debug)
93 return;
95 if (istrue && isfalse) {
96 printf("'%s = %s' from %d does not exist.\n", s->name,
97 show_state(s->state), s->line);
98 } else if (istrue) {
99 printf("'%s = %s' from %d is true. [stree %d]\n", s->name, show_state(s->state),
100 s->line, get_stree_id(s->pool));
101 } else if (isfalse) {
102 printf("'%s = %s' from %d is false. [stree %d]\n", s->name, show_state(s->state),
103 s->line, get_stree_id(s->pool));
104 } else {
105 printf("'%s = %s' from %d could be true or false. [stree %d]\n", s->name,
106 show_state(s->state), s->line, get_stree_id(s->pool));
111 * add_pool() adds a slist to *pools. If the slist has already been
112 * added earlier then it doesn't get added a second time.
114 void add_pool(struct stree_stack **pools, struct stree *new)
116 struct stree *tmp;
118 FOR_EACH_PTR(*pools, tmp) {
119 if (tmp < new)
120 continue;
121 else if (tmp == new) {
122 return;
123 } else {
124 INSERT_CURRENT(new, tmp);
125 return;
127 } END_FOR_EACH_PTR(tmp);
128 add_ptr_list(pools, new);
132 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
133 * the false pools. If we're not sure, then we don't add it to either.
135 static void do_compare(struct sm_state *sm_state, int comparison, struct range_list *vals,
136 int lr,
137 struct stree_stack **true_stack,
138 struct stree_stack **false_stack)
140 struct sm_state *s;
141 int istrue;
142 int isfalse;
144 if (!sm_state->pool)
145 return;
147 if (is_implied(sm_state)) {
148 s = get_sm_state_stree(sm_state->pool,
149 sm_state->owner, sm_state->name,
150 sm_state->sym);
151 } else {
152 s = sm_state;
155 if (!s) {
156 if (option_debug_implied || option_debug)
157 sm_msg("%s from %d, has borrowed implications.",
158 sm_state->name, sm_state->line);
159 return;
162 if (lr == LEFT) {
163 istrue = !possibly_false_rl(estate_rl(s->state), comparison, vals);
164 isfalse = !possibly_true_rl(estate_rl(s->state), comparison, vals);
165 } else {
166 istrue = !possibly_false_rl(vals, comparison, estate_rl(s->state));
167 isfalse = !possibly_true_rl(vals, comparison, estate_rl(s->state));
170 print_debug_tf(s, istrue, isfalse);
172 if (istrue)
173 add_pool(true_stack, s->pool);
175 if (isfalse)
176 add_pool(false_stack, s->pool);
179 static int pool_in_pools(struct stree *pool,
180 struct stree_stack *pools)
182 struct stree *tmp;
184 FOR_EACH_PTR(pools, tmp) {
185 if (tmp == pool)
186 return 1;
187 if (tmp > pool)
188 return 0;
189 } END_FOR_EACH_PTR(tmp);
190 return 0;
193 static int is_checked(struct state_list *checked, struct sm_state *sm)
195 struct sm_state *tmp;
197 FOR_EACH_PTR(checked, tmp) {
198 if (tmp == sm)
199 return 1;
200 } END_FOR_EACH_PTR(tmp);
201 return 0;
205 * separate_pools():
206 * Example code: if (foo == 99) {
208 * Say 'foo' is a merged state that has many possible values. It is the combination
209 * of merges. separate_pools() iterates through the pools recursively and calls
210 * do_compare() for each time 'foo' was set.
212 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
213 int lr,
214 struct stree_stack **true_stack,
215 struct stree_stack **false_stack,
216 struct state_list **checked)
218 int free_checked = 0;
219 struct state_list *checked_states = NULL;
221 if (!sm_state)
222 return;
225 Sometimes the implications are just too big to deal with
226 so we bail. Theoretically, bailing out here can cause more false
227 positives but won't hide actual bugs.
229 if (sm_state->nr_children > 4000) {
230 static char buf[1028];
231 snprintf(buf, sizeof(buf), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
232 sm_state->nr_children, sm_state->name, show_state(sm_state->state));
233 implied_debug_msg = buf;
234 return;
237 if (checked == NULL) {
238 checked = &checked_states;
239 free_checked = 1;
241 if (is_checked(*checked, sm_state))
242 return;
243 add_ptr_list(checked, sm_state);
245 do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
247 separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
248 separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
249 if (free_checked)
250 free_slist(checked);
253 struct sm_state *filter_pools(struct sm_state *sm,
254 struct stree_stack *remove_stack,
255 struct stree_stack *keep_stack,
256 int *modified)
258 struct sm_state *ret = NULL;
259 struct sm_state *left;
260 struct sm_state *right;
261 int removed = 0;
263 if (!sm)
264 return NULL;
266 if (sm->nr_children > 4000) {
267 static char buf[1028];
268 snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
269 __func__, sm->nr_children, sm->name, show_state(sm->state));
270 implied_debug_msg = buf;
271 return NULL;
274 if (pool_in_pools(sm->pool, remove_stack)) {
275 DIMPLIED("removed %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
276 *modified = 1;
277 return NULL;
280 if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack)) {
281 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
282 return sm;
285 DIMPLIED("checking %s from %d (%d) [stree %d] left = %s [stree %d] right = %s [stree %d]\n",
286 show_sm(sm), sm->line, sm->nr_children, get_stree_id(sm->pool),
287 sm->left ? show_sm(sm->left) : "<none>", sm->left ? get_stree_id(sm->left->pool) : -1,
288 sm->right ? show_sm(sm->right) : "<none>", sm->right ? get_stree_id(sm->right->pool) : -1);
289 left = filter_pools(sm->left, remove_stack, keep_stack, &removed);
290 right = filter_pools(sm->right, remove_stack, keep_stack, &removed);
291 if (!removed) {
292 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
293 return sm;
295 *modified = 1;
296 if (!left && !right) {
297 DIMPLIED("removed %s from %d <none> [stree %d]\n", show_sm(sm), sm->line, get_stree_id(sm->pool));
298 return NULL;
301 if (!left) {
302 ret = clone_sm(right);
303 ret->merged = 1;
304 ret->right = right;
305 ret->left = NULL;
306 ret->pool = sm->pool;
307 } else if (!right) {
308 ret = clone_sm(left);
309 ret->merged = 1;
310 ret->left = left;
311 ret->right = NULL;
312 ret->pool = sm->pool;
313 } else {
314 ret = merge_sm_states(left, right);
315 ret->pool = sm->pool;
317 ret->implied = 1;
318 DIMPLIED("partial %s => ", show_sm(sm));
319 DIMPLIED("%s from %d [stree %d]\n", show_sm(ret), sm->line, get_stree_id(sm->pool));
320 return ret;
323 static int highest_stree_id(struct sm_state *sm)
325 int left = 0;
326 int right = 0;
328 if (!sm->left && !sm->right)
329 return 0;
331 if (sm->left)
332 left = get_stree_id(sm->left->pool);
333 if (sm->right)
334 right = get_stree_id(sm->right->pool);
336 if (right > left)
337 return right;
338 return left;
341 static struct stree *filter_stack(struct sm_state *gate_sm,
342 struct stree *pre_stree,
343 struct stree_stack *remove_stack,
344 struct stree_stack *keep_stack)
346 struct stree *ret = NULL;
347 struct sm_state *tmp;
348 struct sm_state *filtered_sm;
349 int modified;
351 if (!remove_stack)
352 return NULL;
354 FOR_EACH_SM(pre_stree, tmp) {
355 if (highest_stree_id(tmp) < highest_stree_id(gate_sm)) {
356 DIMPLIED("skipping %s. set before. %d vs %d\n",
357 tmp->name, highest_stree_id(tmp),
358 highest_stree_id(gate_sm));
359 continue;
361 modified = 0;
362 filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified);
363 if (filtered_sm && modified) {
364 /* the assignments here are for borrowed implications */
365 filtered_sm->name = tmp->name;
366 filtered_sm->sym = tmp->sym;
367 avl_insert(&ret, filtered_sm);
368 if (out_of_memory())
369 return NULL;
372 } END_FOR_EACH_SM(tmp);
373 return ret;
376 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
377 int lr,
378 struct stree *pre_stree,
379 struct stree **true_states,
380 struct stree **false_states)
382 struct stree_stack *true_stack = NULL;
383 struct stree_stack *false_stack = NULL;
384 struct timeval time_before;
385 struct timeval time_after;
387 gettimeofday(&time_before, NULL);
389 if (!is_merged(sm_state)) {
390 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
391 return;
394 if (option_debug_implied || option_debug) {
395 if (lr == LEFT)
396 sm_msg("checking implications: (%s %s %s)",
397 sm_state->name, show_special(comparison), show_rl(vals));
398 else
399 sm_msg("checking implications: (%s %s %s)",
400 show_rl(vals), show_special(comparison), sm_state->name);
403 separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
405 DIMPLIED("filtering true stack.\n");
406 *true_states = filter_stack(sm_state, pre_stree, false_stack, true_stack);
407 DIMPLIED("filtering false stack.\n");
408 *false_states = filter_stack(sm_state, pre_stree, true_stack, false_stack);
409 free_stree_stack(&true_stack);
410 free_stree_stack(&false_stack);
411 if (option_debug_implied || option_debug) {
412 printf("These are the implied states for the true path:\n");
413 __print_stree(*true_states);
414 printf("These are the implied states for the false path:\n");
415 __print_stree(*false_states);
418 gettimeofday(&time_after, NULL);
419 if (time_after.tv_sec - time_before.tv_sec > 7)
420 __bail_on_rest_of_function = 1;
423 static struct expression *get_left_most_expr(struct expression *expr)
425 expr = strip_expr(expr);
426 if (expr->type == EXPR_ASSIGNMENT)
427 return get_left_most_expr(expr->left);
428 return expr;
431 static int is_merged_expr(struct expression *expr)
433 struct sm_state *sm;
434 sval_t dummy;
436 if (get_value(expr, &dummy))
437 return 0;
438 sm = get_sm_state_expr(SMATCH_EXTRA, expr);
439 if (!sm)
440 return 0;
441 if (is_merged(sm))
442 return 1;
443 return 0;
446 static void delete_equiv_stree(struct stree **stree, const char *name, struct symbol *sym)
448 struct smatch_state *state;
449 struct relation *rel;
451 state = get_state(SMATCH_EXTRA, name, sym);
452 if (!estate_related(state)) {
453 delete_state_stree(stree, SMATCH_EXTRA, name, sym);
454 return;
457 FOR_EACH_PTR(estate_related(state), rel) {
458 delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
459 } END_FOR_EACH_PTR(rel);
462 static void handle_comparison(struct expression *expr,
463 struct stree **implied_true,
464 struct stree **implied_false)
466 struct sm_state *sm = NULL;
467 struct range_list *ranges = NULL;
468 struct expression *left;
469 struct expression *right;
470 int lr;
472 left = get_left_most_expr(expr->left);
473 right = get_left_most_expr(expr->right);
475 if (is_merged_expr(left)) {
476 lr = LEFT;
477 sm = get_sm_state_expr(SMATCH_EXTRA, left);
478 get_implied_rl(right, &ranges);
479 } else if (is_merged_expr(right)) {
480 lr = RIGHT;
481 sm = get_sm_state_expr(SMATCH_EXTRA, right);
482 get_implied_rl(left, &ranges);
485 if (!ranges || !sm) {
486 free_rl(&ranges);
487 return;
490 separate_and_filter(sm, expr->op, ranges, lr, __get_cur_stree(), implied_true, implied_false);
491 free_rl(&ranges);
492 delete_equiv_stree(implied_true, sm->name, sm->sym);
493 delete_equiv_stree(implied_false, sm->name, sm->sym);
496 static void handle_zero_comparison(struct expression *expr,
497 struct stree **implied_true,
498 struct stree **implied_false)
500 struct symbol *sym;
501 char *name;
502 struct sm_state *sm;
504 if (expr->type == EXPR_POSTOP)
505 expr = strip_expr(expr->unop);
507 if (expr->type == EXPR_ASSIGNMENT) {
508 /* most of the time ->pools will be empty here because we
509 just set the state, but if have assigned a conditional
510 function there are implications. */
511 expr = expr->left;
514 name = expr_to_var_sym(expr, &sym);
515 if (!name || !sym)
516 goto free;
517 sm = get_sm_state(SMATCH_EXTRA, name, sym);
518 if (!sm)
519 goto free;
521 separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_stree(), implied_true, implied_false);
522 delete_equiv_stree(implied_true, name, sym);
523 delete_equiv_stree(implied_false, name, sym);
524 free:
525 free_string(name);
528 static int handled_by_implied_hook(struct expression *expr,
529 struct stree **implied_true,
530 struct stree **implied_false)
532 struct stree_stack *true_stack = NULL;
533 struct stree_stack *false_stack = NULL;
534 struct stree *pre_stree;
535 struct sm_state *sm;
537 sm = comparison_implication_hook(expr, &true_stack, &false_stack);
538 if (!sm)
539 return 0;
541 pre_stree = clone_stree(__get_cur_stree());
543 *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
544 *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
546 free_stree(&pre_stree);
547 free_stree_stack(&true_stack);
548 free_stree_stack(&false_stack);
550 return 1;
553 static void get_tf_states(struct expression *expr,
554 struct stree **implied_true,
555 struct stree **implied_false)
557 if (handled_by_implied_hook(expr, implied_true, implied_false))
558 return;
560 if (expr->type == EXPR_COMPARE)
561 handle_comparison(expr, implied_true, implied_false);
562 else
563 handle_zero_comparison(expr, implied_true, implied_false);
566 static struct stree *saved_implied_true;
567 static struct stree *saved_implied_false;
569 static void save_implications_hook(struct expression *expr)
571 if (option_no_implied)
572 return;
573 get_tf_states(expr, &saved_implied_true, &saved_implied_false);
576 static void set_implied_states(struct expression *expr)
578 struct sm_state *sm;
580 FOR_EACH_SM(saved_implied_true, sm) {
581 __set_true_false_sm(sm, NULL);
582 } END_FOR_EACH_SM(sm);
583 free_stree(&saved_implied_true);
585 FOR_EACH_SM(saved_implied_false, sm) {
586 __set_true_false_sm(NULL, sm);
587 } END_FOR_EACH_SM(sm);
588 free_stree(&saved_implied_false);
591 struct range_list *__get_implied_values(struct expression *switch_expr)
593 char *name;
594 struct symbol *sym;
595 struct smatch_state *state;
596 struct range_list *ret = NULL;
598 name = expr_to_var_sym(switch_expr, &sym);
599 if (!name || !sym)
600 goto free;
601 state = get_state(SMATCH_EXTRA, name, sym);
602 if (!state)
603 goto free;
604 ret = clone_rl(estate_rl(state));
605 free:
606 free_string(name);
607 if (!ret) {
608 struct symbol *type;
610 type = get_type(switch_expr);
611 ret = alloc_rl(sval_type_min(type), sval_type_max(type));
613 return ret;
616 struct stree *__implied_case_stree(struct expression *switch_expr,
617 struct expression *case_expr,
618 struct range_list_stack **remaining_cases,
619 struct stree **raw_stree)
621 char *name = NULL;
622 struct symbol *sym;
623 struct sm_state *sm;
624 struct stree *true_states = NULL;
625 struct stree *false_states = NULL;
626 struct stree *extra_states = NULL;
627 struct stree *ret = clone_stree(*raw_stree);
628 sval_t sval;
629 struct range_list *vals = NULL;
631 name = expr_to_var_sym(switch_expr, &sym);
632 if (!name || !sym)
633 goto free;
634 sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
636 if (case_expr) {
637 if (get_value(case_expr, &sval)) {
638 filter_top_rl(remaining_cases, sval);
639 add_range(&vals, sval, sval);
640 } else {
641 vals = clone_rl(top_rl(*remaining_cases));
643 } else {
644 vals = top_rl(*remaining_cases);
647 if (sm)
648 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_stree, &true_states, &false_states);
650 __push_fake_cur_stree();
651 __unnullify_path();
652 set_extra_nomod(name, sym, alloc_estate_rl(vals));
653 extra_states = __pop_fake_cur_stree();
654 overwrite_stree(extra_states, &true_states);
655 overwrite_stree(true_states, &ret);
656 free_stree(&extra_states);
657 free_stree(&true_states);
658 free_stree(&false_states);
659 free:
660 free_string(name);
661 return ret;
664 static void match_end_func(struct symbol *sym)
666 if (__inline_fn)
667 return;
668 implied_debug_msg = NULL;
671 static int sm_state_in_slist(struct sm_state *sm, struct state_list *slist)
673 struct sm_state *tmp;
675 FOR_EACH_PTR(slist, tmp) {
676 if (tmp == sm)
677 return 1;
678 } END_FOR_EACH_PTR(tmp);
679 return 0;
683 * The situation is we have a SMATCH_EXTRA state and we want to break it into
684 * each of the ->possible states and find the implications of each. The caller
685 * has to use __push_fake_cur_stree() to preserve the correct states so they
686 * can be restored later.
688 void overwrite_states_using_pool(struct sm_state *sm)
690 struct sm_state *old;
691 struct sm_state *new;
693 if (!sm->pool)
694 return;
696 FOR_EACH_SM(sm->pool, old) {
697 new = get_sm_state(old->owner, old->name, old->sym);
698 if (!new) /* the variable went out of scope */
699 continue;
700 if (sm_state_in_slist(old, new->possible))
701 set_state(old->owner, old->name, old->sym, old->state);
702 } END_FOR_EACH_SM(old);
705 void __extra_match_condition(struct expression *expr);
706 void __comparison_match_condition(struct expression *expr);
707 void register_implications(int id)
709 add_hook(&save_implications_hook, CONDITION_HOOK);
710 add_hook(&__extra_match_condition, CONDITION_HOOK);
711 add_hook(&__comparison_match_condition, CONDITION_HOOK);
712 add_hook(&set_implied_states, CONDITION_HOOK);
713 add_hook(&match_end_func, END_FUNC_HOOK);