2 * sparse/smatch_extra.c
4 * Copyright (C) 2008 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * smatch_extra.c is supposed to track the value of every variable.
19 #include "smatch_slist.h"
20 #include "smatch_extra.h"
24 static struct symbol
*cur_func
;
26 struct data_range whole_range
= {
31 static struct smatch_state
*alloc_extra_state_empty()
33 struct smatch_state
*state
;
34 struct data_info
*dinfo
;
36 dinfo
= __alloc_data_info(0);
37 dinfo
->type
= DATA_RANGE
;
38 dinfo
->value_ranges
= NULL
;
39 state
= __alloc_smatch_state(0);
44 static struct smatch_state
*alloc_extra_state_no_name(int val
)
46 struct smatch_state
*state
;
48 state
= __alloc_smatch_state(0);
50 state
->data
= (void *)alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
52 state
->data
= (void *)alloc_dinfo_range(val
, val
);
56 /* We do this because ->value_ranges is a list */
57 struct smatch_state
*extra_undefined()
59 struct data_info
*dinfo
;
60 static struct smatch_state
*ret
;
61 static struct symbol
*prev_func
;
63 if (prev_func
== cur_func
)
67 dinfo
= alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
68 ret
= __alloc_smatch_state(0);
69 ret
->name
= "unknown";
74 struct smatch_state
*alloc_extra_state(int val
)
76 struct smatch_state
*state
;
79 return extra_undefined();
80 state
= alloc_extra_state_no_name(val
);
81 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
85 struct smatch_state
*alloc_extra_state_range(long long min
, long long max
)
87 struct smatch_state
*state
;
89 if (min
== whole_range
.min
&& max
== whole_range
.max
)
90 return extra_undefined();
91 state
= __alloc_smatch_state(0);
92 state
->data
= (void *)alloc_dinfo_range(min
, max
);
93 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
97 struct smatch_state
*alloc_extra_state_range_list(struct range_list
*rl
)
99 struct smatch_state
*state
;
101 state
= __alloc_smatch_state(0);
102 state
->data
= (void *)alloc_dinfo_range_list(rl
);
103 state
->name
= show_ranges(((struct data_info
*)state
->data
)->value_ranges
);
107 struct smatch_state
*filter_range(struct smatch_state
*orig
,
108 long long filter_min
, long long filter_max
)
110 struct smatch_state
*ret
;
111 struct data_info
*orig_info
;
112 struct data_info
*ret_info
;
115 orig
= extra_undefined();
116 orig_info
= (struct data_info
*)orig
->data
;
117 ret
= alloc_extra_state_empty();
118 ret_info
= (struct data_info
*)ret
->data
;
119 ret_info
->value_ranges
= remove_range(orig_info
->value_ranges
, filter_min
, filter_max
);
120 ret
->name
= show_ranges(ret_info
->value_ranges
);
124 struct smatch_state
*add_filter(struct smatch_state
*orig
, long long num
)
126 return filter_range(orig
, num
, num
);
129 static struct smatch_state
*merge_func(const char *name
, struct symbol
*sym
,
130 struct smatch_state
*s1
,
131 struct smatch_state
*s2
)
133 struct data_info
*info1
= (struct data_info
*)s1
->data
;
134 struct data_info
*info2
= (struct data_info
*)s2
->data
;
135 struct data_info
*ret_info
;
136 struct smatch_state
*tmp
;
137 struct range_list
*value_ranges
;
139 value_ranges
= range_list_union(info1
->value_ranges
, info2
->value_ranges
);
140 tmp
= alloc_extra_state_empty();
141 ret_info
= (struct data_info
*)tmp
->data
;
142 ret_info
->value_ranges
= value_ranges
;
143 tmp
->name
= show_ranges(ret_info
->value_ranges
);
147 struct sm_state
*__extra_pre_loop_hook_before(struct statement
*iterator_pre_statement
)
149 struct expression
*expr
;
152 struct sm_state
*ret
= NULL
;
154 if (!iterator_pre_statement
)
156 if (iterator_pre_statement
->type
!= STMT_EXPRESSION
)
158 expr
= iterator_pre_statement
->expression
;
159 if (expr
->type
!= EXPR_ASSIGNMENT
)
161 name
= get_variable_from_expr(expr
->left
, &sym
);
164 ret
= get_sm_state(my_id
, name
, sym
);
170 static const char *get_iter_op(struct expression
*expr
)
172 if (expr
->type
!= EXPR_POSTOP
&& expr
->type
!= EXPR_PREOP
)
174 return show_special(expr
->op
);
177 int __iterator_unchanged(struct sm_state
*sm
, struct statement
*iterator
)
179 struct expression
*iter_expr
;
187 if (iterator
->type
!= STMT_EXPRESSION
)
189 iter_expr
= iterator
->expression
;
190 op
= get_iter_op(iter_expr
);
191 if (!op
|| (strcmp(op
, "--") && strcmp(op
, "++")))
193 name
= get_variable_from_expr(iter_expr
->unop
, &sym
);
196 if (get_sm_state(my_id
, name
, sym
) == sm
)
203 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
204 struct statement
*iterator
,
205 struct expression
*condition
)
207 struct expression
*iter_expr
;
213 struct smatch_state
*state
;
214 struct data_info
*dinfo
;
217 iter_expr
= iterator
->expression
;
219 if (condition
->type
!= EXPR_COMPARE
)
221 value
= get_value(condition
->left
);
222 if (value
== UNDEFINED
) {
223 value
= get_value(condition
->right
);
224 if (value
== UNDEFINED
)
229 name
= get_variable_from_expr(condition
->left
, &sym
);
231 name
= get_variable_from_expr(condition
->right
, &sym
);
234 if (sym
!= sm
->sym
|| strcmp(name
, sm
->name
))
236 op
= get_iter_op(iter_expr
);
237 state
= get_state(my_id
, name
, sym
);
238 dinfo
= (struct data_info
*)state
->data
;
239 min
= get_dinfo_min(dinfo
);
240 max
= get_dinfo_max(dinfo
);
241 if (!strcmp(op
, "++") && min
!= whole_range
.min
&& max
== whole_range
.max
) {
242 set_state(my_id
, name
, sym
, alloc_extra_state(min
));
243 } else if (min
== whole_range
.min
&& max
!= whole_range
.max
) {
244 set_state(my_id
, name
, sym
, alloc_extra_state(max
));
251 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
253 return extra_undefined();
256 static void match_function_call(struct expression
*expr
)
258 struct expression
*tmp
;
263 FOR_EACH_PTR(expr
->args
, tmp
) {
264 if (tmp
->op
== '&') {
265 name
= get_variable_from_expr(tmp
->unop
, &sym
);
267 set_state(my_id
, name
, sym
, extra_undefined());
272 } END_FOR_EACH_PTR(tmp
);
275 static void match_assign(struct expression
*expr
)
277 struct expression
*left
;
281 left
= strip_expr(expr
->left
);
282 name
= get_variable_from_expr(left
, &sym
);
285 set_state(my_id
, name
, sym
, alloc_extra_state(get_value(expr
->right
)));
289 static void undef_expr(struct expression
*expr
)
293 long long min
= whole_range
.min
;
294 long long max
= whole_range
.max
;
302 name
= get_variable_from_expr(expr
->unop
, &sym
);
305 if (!strcmp("++", show_special(expr
->op
))) {
306 val
= get_implied_min(expr
);
307 if (val
!= UNDEFINED
)
310 if (!strcmp("--", show_special(expr
->op
))) {
311 val
= get_implied_max(expr
);
312 sm_msg("%lld implied max", val
);
313 if (val
!= UNDEFINED
)
316 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
321 static void match_declarations(struct symbol
*sym
)
326 name
= sym
->ident
->name
;
327 if (sym
->initializer
) {
328 set_state(my_id
, name
, sym
, alloc_extra_state(get_value(sym
->initializer
)));
329 scoped_state(name
, my_id
, sym
);
331 set_state(my_id
, name
, sym
, extra_undefined());
332 scoped_state(name
, my_id
, sym
);
337 static void match_function_def(struct symbol
*sym
)
342 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
346 set_state(my_id
, arg
->ident
->name
, arg
, extra_undefined());
347 } END_FOR_EACH_PTR(arg
);
354 static long long get_implied_value_helper(struct expression
*expr
, int what
)
356 struct smatch_state
*state
;
361 val
= get_value(expr
);
362 if (val
!= UNDEFINED
)
365 name
= get_variable_from_expr(expr
, &sym
);
368 state
= get_state(my_id
, name
, sym
);
370 if (!state
|| !state
->data
)
372 if (what
== VAL_SINGLE
)
373 return get_single_value_from_range((struct data_info
*)state
->data
);
375 return get_dinfo_max((struct data_info
*)state
->data
);
376 return get_dinfo_min((struct data_info
*)state
->data
);
379 int get_implied_single_val(struct expression
*expr
)
381 return get_implied_value_helper(expr
, VAL_SINGLE
);
384 int get_implied_max(struct expression
*expr
)
388 ret
= get_implied_value_helper(expr
, VAL_MAX
);
389 if (ret
== whole_range
.max
)
394 int get_implied_min(struct expression
*expr
)
398 ret
= get_implied_value_helper(expr
, VAL_MIN
);
399 if (ret
== whole_range
.min
)
404 int last_stmt_val(struct statement
*stmt
)
406 struct expression
*expr
;
408 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
409 if (stmt
->type
!= STMT_EXPRESSION
)
411 expr
= stmt
->expression
;
412 return get_value(expr
);
415 static void match_comparison(struct expression
*expr
)
420 struct smatch_state
*one_state
;
421 struct smatch_state
*two_state
;
422 struct smatch_state
*orig
;
424 int comparison
= expr
->op
;
425 struct expression
*varies
= expr
->right
;
427 fixed
= get_value(expr
->left
);
428 if (fixed
== UNDEFINED
) {
429 fixed
= get_value(expr
->right
);
430 if (fixed
== UNDEFINED
)
435 if (varies
->type
== EXPR_PREOP
|| varies
->type
== EXPR_POSTOP
) {
436 varies
= varies
->unop
;
438 if (varies
->type
== EXPR_CALL
) {
439 function_comparison(comparison
, varies
, fixed
, left
);
442 name
= get_variable_from_expr(varies
, &sym
);
446 orig
= get_state(my_id
, name
, sym
);
448 orig
= extra_undefined();
452 case SPECIAL_UNSIGNED_LT
:
453 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
454 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
456 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
458 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
460 case SPECIAL_UNSIGNED_LTE
:
462 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
463 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
465 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
467 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
470 // todo. print a warning here for impossible conditions.
471 one_state
= alloc_extra_state(fixed
);
472 two_state
= filter_range(orig
, fixed
, fixed
);
473 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
475 case SPECIAL_UNSIGNED_GTE
:
477 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
478 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
480 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
482 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
485 case SPECIAL_UNSIGNED_GT
:
486 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
487 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
489 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
491 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
493 case SPECIAL_NOTEQUAL
:
494 one_state
= alloc_extra_state(fixed
);
495 two_state
= filter_range(orig
, fixed
, fixed
);
496 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
499 sm_msg("unhandled comparison %d\n", comparison
);
507 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
508 void __extra_match_condition(struct expression
*expr
)
512 struct smatch_state
*pre_state
;
513 struct smatch_state
*true_state
;
514 struct smatch_state
*false_state
;
516 expr
= strip_expr(expr
);
519 function_comparison(SPECIAL_NOTEQUAL
, expr
, 0, 1);
524 name
= get_variable_from_expr(expr
, &sym
);
527 pre_state
= get_state(my_id
, name
, sym
);
528 true_state
= add_filter(pre_state
, 0);
529 false_state
= alloc_extra_state(0);
530 set_true_false_states(my_id
, name
, sym
, true_state
, false_state
);
534 match_comparison(expr
);
536 case EXPR_ASSIGNMENT
:
537 __extra_match_condition(expr
->right
);
538 __extra_match_condition(expr
->left
);
543 static int variable_non_zero(struct expression
*expr
)
547 struct smatch_state
*state
;
550 name
= get_variable_from_expr(expr
, &sym
);
553 state
= get_state(my_id
, name
, sym
);
554 if (!state
|| !state
->data
)
556 ret
= !possibly_false(SPECIAL_NOTEQUAL
, (struct data_info
*)state
->data
, 0, 1);
562 int known_condition_true(struct expression
*expr
)
569 tmp
= get_value(expr
);
570 if (tmp
&& tmp
!= UNDEFINED
)
573 expr
= strip_expr(expr
);
576 if (expr
->op
== '!') {
577 if (known_condition_false(expr
->unop
))
588 int known_condition_false(struct expression
*expr
)
598 if (expr
->op
== '!') {
599 if (known_condition_true(expr
->unop
))
610 static int do_comparison_range(struct expression
*expr
)
614 struct smatch_state
*state
;
617 int poss_true
, poss_false
;
619 value
= get_value(expr
->left
);
620 if (value
== UNDEFINED
) {
621 value
= get_value(expr
->right
);
622 if (value
== UNDEFINED
)
627 name
= get_variable_from_expr(expr
->left
, &sym
);
629 name
= get_variable_from_expr(expr
->right
, &sym
);
632 state
= get_state(SMATCH_EXTRA
, name
, sym
);
635 poss_true
= possibly_true(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
636 poss_false
= possibly_false(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
637 if (!poss_true
&& !poss_false
)
639 if (poss_true
&& !poss_false
)
641 if (!poss_true
&& poss_false
)
643 if (poss_true
&& poss_false
)
650 int implied_condition_true(struct expression
*expr
)
652 struct statement
*stmt
;
658 tmp
= get_value(expr
);
659 if (tmp
&& tmp
!= UNDEFINED
)
662 expr
= strip_expr(expr
);
665 if (do_comparison_range(expr
) == 1)
669 if (expr
->op
== '!') {
670 if (implied_condition_false(expr
->unop
))
674 stmt
= get_block_thing(expr
);
675 if (stmt
&& (last_stmt_val(stmt
) == 1))
679 if (variable_non_zero(expr
) == 1)
686 int implied_condition_false(struct expression
*expr
)
688 struct statement
*stmt
;
689 struct expression
*tmp
;
699 if (do_comparison_range(expr
) == 2)
702 if (expr
->op
== '!') {
703 if (implied_condition_true(expr
->unop
))
707 stmt
= get_block_thing(expr
);
708 if (stmt
&& (last_stmt_val(stmt
) == 0))
710 tmp
= strip_expr(expr
);
712 return implied_condition_false(tmp
);
715 if (variable_non_zero(expr
) == 0)
722 void register_smatch_extra(int id
)
725 add_merge_hook(my_id
, &merge_func
);
726 add_unmatched_state_hook(my_id
, &unmatched_state
);
727 add_hook(&undef_expr
, OP_HOOK
);
728 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
729 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
730 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
731 add_hook(&match_declarations
, DECLARATION_HOOK
);
734 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
735 add_function_hook("panic", &__match_nullify_path_hook
, NULL
);
736 add_function_hook("do_exit", &__match_nullify_path_hook
, NULL
);
737 add_function_hook("complete_and_exit", &__match_nullify_path_hook
, NULL
);
738 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook
, NULL
);
739 add_function_hook("do_group_exit", &__match_nullify_path_hook
, NULL
);