2 * sparse/smatch_implied.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * Imagine we have this code:
18 * if (foo == 99) // <-- point #2
19 * bar->baz; // <-- point #3
22 * At point #3 bar is non null and can be dereferenced.
24 * It's smatch_implied.c which sets bar to non null at point #2.
26 * At point #1 merge_slist() stores the list of states from both
27 * the true and false paths. On the true path foo == 99 and on
28 * the false path foo == 1. merge_slist() sets their pool
29 * list to show the other states which were there when foo == 99.
31 * When it comes to the if (foo == 99) the smatch implied hook
32 * looks for all the pools where foo was not 99. It makes a list
35 * Then for bar (and all the other states) it says, ok bar is a
36 * merged state that came from these previous states. We'll
37 * chop out all the states where it came from a pool where
38 * foo != 99 and merge it all back together.
40 * That is the implied state of bar.
42 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
43 * that is the pool where it was first set. The my pool gets set when
44 * code paths merge. States that have been set since the last merge do
46 * merge_sm_state() sets ->left and ->right. (These are the states which were
47 * merged to form the current state.)
48 * a pool: a pool is an slist that has been merged with another slist.
54 #include "smatch_slist.h"
55 #include "smatch_extra.h"
57 char *implied_debug_msg
;
58 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
60 int option_debug_implied
= 0;
61 int option_no_implied
= 0;
68 * It messes things up to free range list allocations. This helper fuction
69 * lets us reuse memory instead of doing new allocations.
71 static struct range_list
*tmp_range_list(long long num
)
73 static struct range_list
*my_list
= NULL
;
74 static struct data_range
*my_range
;
76 __free_ptr_list((struct ptr_list
**)&my_list
);
77 my_range
= alloc_range(num
, num
);
80 add_ptr_list(&my_list
, my_range
);
84 static void print_debug_tf(struct sm_state
*s
, int istrue
, int isfalse
)
86 if (!option_debug_implied
&& !option_debug
)
89 if (istrue
&& isfalse
) {
90 printf("'%s = %s' from %d does not exist.\n", s
->name
,
91 show_state(s
->state
), s
->line
);
93 printf("'%s = %s' from %d is true.\n", s
->name
, show_state(s
->state
),
96 printf("'%s = %s' from %d is false.\n", s
->name
, show_state(s
->state
),
99 printf("'%s = %s' from %d could be true or false.\n", s
->name
,
100 show_state(s
->state
), s
->line
);
105 * add_pool() adds a slist to *pools. If the slist has already been
106 * added earlier then it doesn't get added a second time.
108 static void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
110 struct state_list
*tmp
;
112 FOR_EACH_PTR(*pools
, tmp
) {
115 else if (tmp
== new) {
118 INSERT_CURRENT(new, tmp
);
121 } END_FOR_EACH_PTR(tmp
);
122 add_ptr_list(pools
, new);
126 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
127 * the false pools. If we're not sure, then we don't add it to either.
129 static void do_compare(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
131 struct state_list_stack
**true_stack
,
132 struct state_list_stack
**false_stack
)
141 if (is_implied(sm_state
)) {
142 s
= get_sm_state_slist(sm_state
->pool
,
143 sm_state
->owner
, sm_state
->name
,
150 if (option_debug_implied
|| option_debug
)
151 sm_msg("%s from %d, has borrowed implications.",
152 sm_state
->name
, sm_state
->line
);
157 istrue
= !possibly_false_range_lists(estate_ranges(s
->state
), comparison
, vals
);
158 isfalse
= !possibly_true_range_lists(estate_ranges(s
->state
), comparison
, vals
);
160 istrue
= !possibly_false_range_lists(vals
, comparison
, estate_ranges(s
->state
));
161 isfalse
= !possibly_true_range_lists(vals
, comparison
, estate_ranges(s
->state
));
164 print_debug_tf(s
, istrue
, isfalse
);
167 add_pool(true_stack
, s
->pool
);
170 add_pool(false_stack
, s
->pool
);
173 static int pool_in_pools(struct state_list
*pool
,
174 struct state_list_stack
*pools
)
176 struct state_list
*tmp
;
178 FOR_EACH_PTR(pools
, tmp
) {
183 } END_FOR_EACH_PTR(tmp
);
187 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
189 struct sm_state
*tmp
;
191 FOR_EACH_PTR(checked
, tmp
) {
194 } END_FOR_EACH_PTR(tmp
);
200 * Example code: if (foo == 99) {
202 * Say 'foo' is a merged state that has many possible values. It is the combination
203 * of merges. separate_pools() iterates through the pools recursively and calls
204 * do_compare() for each time 'foo' was set.
206 static void separate_pools(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
208 struct state_list_stack
**true_stack
,
209 struct state_list_stack
**false_stack
,
210 struct state_list
**checked
)
212 int free_checked
= 0;
213 struct state_list
*checked_states
= NULL
;
219 Sometimes the implications are just too big to deal with
220 so we bail. Theoretically, bailing out here can cause more false
221 positives but won't hide actual bugs.
223 if (sm_state
->nr_children
> 4000) {
225 (char *) "debug: seperate_pools: nr_children over 4000.";
229 if (checked
== NULL
) {
230 checked
= &checked_states
;
233 if (is_checked(*checked
, sm_state
))
235 add_ptr_list(checked
, sm_state
);
237 do_compare(sm_state
, comparison
, vals
, lr
, true_stack
, false_stack
);
239 separate_pools(sm_state
->left
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
240 separate_pools(sm_state
->right
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
245 struct sm_state
*remove_pools(struct sm_state
*sm
,
246 struct state_list_stack
*pools
, int *modified
)
248 struct sm_state
*ret
= NULL
;
249 struct sm_state
*left
;
250 struct sm_state
*right
;
256 if (sm
->nr_children
> 4000) {
258 (char *) "debug: remove_pools: nr_children over 4000";
262 if (pool_in_pools(sm
->pool
, pools
)) {
263 DIMPLIED("removed %s from %d\n", show_sm(sm
), sm
->line
);
268 if (!is_merged(sm
)) {
269 DIMPLIED("kept %s from %d\n", show_sm(sm
), sm
->line
);
273 DIMPLIED("checking %s from %d\n", show_sm(sm
), sm
->line
);
274 left
= remove_pools(sm
->left
, pools
, &removed
);
275 right
= remove_pools(sm
->right
, pools
, &removed
);
277 DIMPLIED("kept %s from %d\n", show_sm(sm
), sm
->line
);
281 if (!left
&& !right
) {
282 DIMPLIED("removed %s from %d <none>\n", show_sm(sm
), sm
->line
);
287 ret
= clone_sm(right
);
291 ret
->pool
= sm
->pool
;
293 ret
= clone_sm(left
);
297 ret
->pool
= sm
->pool
;
299 ret
= merge_sm_states(left
, right
);
300 ret
->pool
= sm
->pool
;
303 DIMPLIED("partial %s => ", show_sm(sm
));
304 DIMPLIED("%s from %d\n", show_sm(ret
), sm
->line
);
308 static int highest_slist_id(struct sm_state
*sm
)
313 if (!sm
->left
&& !sm
->right
)
317 left
= get_slist_id(sm
->left
->pool
);
319 right
= get_slist_id(sm
->right
->pool
);
326 static struct state_list
*filter_stack(struct sm_state
*gate_sm
,
327 struct state_list
*pre_list
,
328 struct state_list_stack
*stack
)
330 struct state_list
*ret
= NULL
;
331 struct sm_state
*tmp
;
332 struct sm_state
*filtered_sm
;
338 FOR_EACH_PTR(pre_list
, tmp
) {
339 if (highest_slist_id(tmp
) < highest_slist_id(gate_sm
)) {
340 DIMPLIED("skipping %s. set before. %d vs %d",
341 tmp
->name
, highest_slist_id(tmp
),
342 highest_slist_id(gate_sm
));
346 filtered_sm
= remove_pools(tmp
, stack
, &modified
);
347 if (filtered_sm
&& modified
) {
348 filtered_sm
->name
= tmp
->name
;
349 filtered_sm
->sym
= tmp
->sym
;
350 add_ptr_list(&ret
, filtered_sm
);
355 } END_FOR_EACH_PTR(tmp
);
359 static void separate_and_filter(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
361 struct state_list
*pre_list
,
362 struct state_list
**true_states
,
363 struct state_list
**false_states
)
365 struct state_list_stack
*true_stack
= NULL
;
366 struct state_list_stack
*false_stack
= NULL
;
367 struct timeval time_before
;
368 struct timeval time_after
;
370 gettimeofday(&time_before
, NULL
);
372 if (!is_merged(sm_state
)) {
373 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state
->name
);
377 if (option_debug_implied
|| option_debug
) {
379 sm_msg("checking implications: (%s %s %s)",
380 sm_state
->name
, show_special(comparison
), show_ranges(vals
));
382 sm_msg("checking implications: (%s %s %s)",
383 show_ranges(vals
), show_special(comparison
), sm_state
->name
);
386 separate_pools(sm_state
, comparison
, vals
, lr
, &true_stack
, &false_stack
, NULL
);
388 DIMPLIED("filtering true stack.\n");
389 *true_states
= filter_stack(sm_state
, pre_list
, false_stack
);
390 DIMPLIED("filtering false stack.\n");
391 *false_states
= filter_stack(sm_state
, pre_list
, true_stack
);
392 free_stack(&true_stack
);
393 free_stack(&false_stack
);
394 if (option_debug_implied
|| option_debug
) {
395 printf("These are the implied states for the true path:\n");
396 __print_slist(*true_states
);
397 printf("These are the implied states for the false path:\n");
398 __print_slist(*false_states
);
401 gettimeofday(&time_after
, NULL
);
402 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
403 __bail_on_rest_of_function
= 1;
406 static struct expression
*get_left_most_expr(struct expression
*expr
)
408 expr
= strip_expr(expr
);
409 if (expr
->type
== EXPR_ASSIGNMENT
)
410 return get_left_most_expr(expr
->left
);
414 static int is_merged_expr(struct expression
*expr
)
419 if (get_value(expr
, &dummy
))
421 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
429 static void delete_equiv_slist(struct state_list
**slist
, const char *name
, struct symbol
*sym
)
431 struct smatch_state
*state
;
432 struct relation
*rel
;
434 state
= get_state(SMATCH_EXTRA
, name
, sym
);
435 if (!estate_related(state
)) {
436 delete_state_slist(slist
, SMATCH_EXTRA
, name
, sym
);
440 FOR_EACH_PTR(estate_related(state
), rel
) {
441 delete_state_slist(slist
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
442 } END_FOR_EACH_PTR(rel
);
445 static void handle_comparison(struct expression
*expr
,
446 struct state_list
**implied_true
,
447 struct state_list
**implied_false
)
449 struct sm_state
*sm
= NULL
;
450 struct range_list
*ranges
= NULL
;
451 struct expression
*left
;
452 struct expression
*right
;
455 left
= get_left_most_expr(expr
->left
);
456 right
= get_left_most_expr(expr
->right
);
458 if (is_merged_expr(left
)) {
460 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
461 get_implied_range_list(right
, &ranges
);
462 } else if (is_merged_expr(right
)) {
464 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
465 get_implied_range_list(left
, &ranges
);
468 if (!ranges
|| !sm
) {
469 free_range_list(&ranges
);
473 separate_and_filter(sm
, expr
->op
, ranges
, lr
, __get_cur_slist(), implied_true
, implied_false
);
474 free_range_list(&ranges
);
475 delete_equiv_slist(implied_true
, sm
->name
, sm
->sym
);
476 delete_equiv_slist(implied_false
, sm
->name
, sm
->sym
);
479 static void handle_zero_comparison(struct expression
*expr
,
480 struct state_list
**implied_true
,
481 struct state_list
**implied_false
)
487 if (expr
->type
== EXPR_POSTOP
)
488 expr
= strip_expr(expr
->unop
);
490 if (expr
->type
== EXPR_ASSIGNMENT
) {
491 /* most of the time ->pools will be empty here because we
492 just set the state, but if have assigned a conditional
493 function there are implications. */
497 name
= get_variable_from_expr(expr
, &sym
);
500 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
504 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_slist(), implied_true
, implied_false
);
505 delete_equiv_slist(implied_true
, name
, sym
);
506 delete_equiv_slist(implied_false
, name
, sym
);
511 static void get_tf_states(struct expression
*expr
,
512 struct state_list
**implied_true
,
513 struct state_list
**implied_false
)
515 if (expr
->type
== EXPR_COMPARE
)
516 handle_comparison(expr
, implied_true
, implied_false
);
518 handle_zero_comparison(expr
, implied_true
, implied_false
);
521 static void implied_states_hook(struct expression
*expr
)
524 struct state_list
*implied_true
= NULL
;
525 struct state_list
*implied_false
= NULL
;
527 if (option_no_implied
)
530 get_tf_states(expr
, &implied_true
, &implied_false
);
532 FOR_EACH_PTR(implied_true
, sm
) {
533 __set_true_false_sm(sm
, NULL
);
534 } END_FOR_EACH_PTR(sm
);
535 free_slist(&implied_true
);
537 FOR_EACH_PTR(implied_false
, sm
) {
538 __set_true_false_sm(NULL
, sm
);
539 } END_FOR_EACH_PTR(sm
);
540 free_slist(&implied_false
);
543 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
547 struct smatch_state
*state
;
548 struct range_list
*ret
= NULL
;
550 name
= get_variable_from_expr(switch_expr
, &sym
);
553 state
= get_state(SMATCH_EXTRA
, name
, sym
);
556 ret
= clone_range_list(estate_ranges(state
));
560 add_range(&ret
, whole_range
.min
, whole_range
.max
);
564 struct state_list
*__implied_case_slist(struct expression
*switch_expr
,
565 struct expression
*case_expr
,
566 struct range_list_stack
**remaining_cases
,
567 struct state_list
**raw_slist
)
572 struct sm_state
*true_sm
;
573 struct state_list
*true_states
= NULL
;
574 struct state_list
*false_states
= NULL
;
575 struct state_list
*ret
= clone_slist(*raw_slist
);
577 struct range_list
*vals
= NULL
;
579 name
= get_variable_from_expr(switch_expr
, &sym
);
582 sm
= get_sm_state_slist(*raw_slist
, SMATCH_EXTRA
, name
, sym
);
584 vals
= top_range_list(*remaining_cases
);
586 if (!get_value(case_expr
, &val
))
589 filter_top_range_list(remaining_cases
, val
);
590 add_range(&vals
, val
, val
);
593 separate_and_filter(sm
, SPECIAL_EQUAL
, vals
, LEFT
, *raw_slist
, &true_states
, &false_states
);
595 true_sm
= get_sm_state_slist(true_states
, SMATCH_EXTRA
, name
, sym
);
597 set_state_slist(&true_states
, SMATCH_EXTRA
, name
, sym
, alloc_estate_range_list(vals
));
598 overwrite_slist(true_states
, &ret
);
599 free_slist(&true_states
);
600 free_slist(&false_states
);
606 static void match_end_func(struct symbol
*sym
)
608 implied_debug_msg
= NULL
;
612 * get_implications() can be called by check_ scripts.
614 void get_implications(char *name
, struct symbol
*sym
, int comparison
, long long num
,
615 struct state_list
**true_states
,
616 struct state_list
**false_states
)
620 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
623 if (slist_has_state(sm
->possible
, &undefined
))
625 separate_and_filter(sm
, comparison
, tmp_range_list(num
), LEFT
, __get_cur_slist(), true_states
, false_states
);
628 void __extra_match_condition(struct expression
*expr
);
629 void register_implications(int id
)
631 add_hook(&implied_states_hook
, CONDITION_HOOK
);
632 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
633 add_hook(&match_end_func
, END_FUNC_HOOK
);