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);
49 state
->data
= (void *)alloc_dinfo_range(val
, val
);
53 /* We do this because ->value_ranges is a list */
54 struct smatch_state
*extra_undefined()
56 struct data_info
*dinfo
;
57 static struct smatch_state
*ret
;
58 static struct symbol
*prev_func
;
60 if (prev_func
== cur_func
)
64 dinfo
= alloc_dinfo_range(whole_range
.min
, whole_range
.max
);
65 ret
= __alloc_smatch_state(0);
66 ret
->name
= "unknown";
71 struct smatch_state
*alloc_extra_state(int val
)
73 struct smatch_state
*state
;
75 state
= alloc_extra_state_no_name(val
);
76 state
->name
= show_ranges(get_dinfo(state
)->value_ranges
);
80 struct smatch_state
*alloc_extra_state_range(long long min
, long long max
)
82 struct smatch_state
*state
;
84 if (min
== whole_range
.min
&& max
== whole_range
.max
)
85 return extra_undefined();
86 state
= __alloc_smatch_state(0);
87 state
->data
= (void *)alloc_dinfo_range(min
, max
);
88 state
->name
= show_ranges(get_dinfo(state
)->value_ranges
);
92 struct smatch_state
*alloc_extra_state_range_list(struct range_list
*rl
)
94 struct smatch_state
*state
;
96 state
= __alloc_smatch_state(0);
97 state
->data
= (void *)alloc_dinfo_range_list(rl
);
98 state
->name
= show_ranges(get_dinfo(state
)->value_ranges
);
102 struct data_info
*get_dinfo(struct smatch_state
*state
)
106 return (struct data_info
*)state
->data
;
110 struct smatch_state
*filter_range(struct smatch_state
*orig
,
111 long long filter_min
, long long filter_max
)
113 struct smatch_state
*ret
;
114 struct data_info
*orig_info
;
115 struct data_info
*ret_info
;
118 orig
= extra_undefined();
119 orig_info
= get_dinfo(orig
);
120 ret
= alloc_extra_state_empty();
121 ret_info
= get_dinfo(ret
);
122 ret_info
->value_ranges
= remove_range(orig_info
->value_ranges
, filter_min
, filter_max
);
123 ret
->name
= show_ranges(ret_info
->value_ranges
);
127 struct smatch_state
*add_filter(struct smatch_state
*orig
, long long num
)
129 return filter_range(orig
, num
, num
);
132 static struct smatch_state
*merge_func(const char *name
, struct symbol
*sym
,
133 struct smatch_state
*s1
,
134 struct smatch_state
*s2
)
136 struct data_info
*info1
= get_dinfo(s1
);
137 struct data_info
*info2
= get_dinfo(s2
);
138 struct data_info
*ret_info
;
139 struct smatch_state
*tmp
;
140 struct range_list
*value_ranges
;
142 value_ranges
= range_list_union(info1
->value_ranges
, info2
->value_ranges
);
143 tmp
= alloc_extra_state_empty();
144 ret_info
= get_dinfo(tmp
);
145 ret_info
->value_ranges
= value_ranges
;
146 tmp
->name
= show_ranges(ret_info
->value_ranges
);
150 struct sm_state
*__extra_pre_loop_hook_before(struct statement
*iterator_pre_statement
)
152 struct expression
*expr
;
155 struct sm_state
*ret
= NULL
;
157 if (!iterator_pre_statement
)
159 if (iterator_pre_statement
->type
!= STMT_EXPRESSION
)
161 expr
= iterator_pre_statement
->expression
;
162 if (expr
->type
!= EXPR_ASSIGNMENT
)
164 name
= get_variable_from_expr(expr
->left
, &sym
);
167 ret
= get_sm_state(my_id
, name
, sym
);
173 int __iterator_unchanged(struct sm_state
*sm
, struct statement
*iterator
)
175 struct expression
*iter_expr
;
182 if (iterator
->type
!= STMT_EXPRESSION
)
184 iter_expr
= iterator
->expression
;
185 if (iter_expr
->op
!= SPECIAL_INCREMENT
&& iter_expr
->op
!= SPECIAL_DECREMENT
)
187 name
= get_variable_from_expr(iter_expr
->unop
, &sym
);
190 if (get_sm_state(my_id
, name
, sym
) == sm
)
197 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
198 struct statement
*iterator
,
199 struct expression
*condition
)
201 struct expression
*iter_expr
;
206 struct smatch_state
*state
;
207 struct data_info
*dinfo
;
210 iter_expr
= iterator
->expression
;
212 if (condition
->type
!= EXPR_COMPARE
)
214 if (!get_value(condition
->left
, &value
)) {
215 if (!get_value(condition
->right
, &value
))
220 name
= get_variable_from_expr(condition
->left
, &sym
);
222 name
= get_variable_from_expr(condition
->right
, &sym
);
225 if (sym
!= sm
->sym
|| strcmp(name
, sm
->name
))
227 state
= get_state(my_id
, name
, sym
);
228 dinfo
= get_dinfo(state
);
229 min
= get_dinfo_min(dinfo
);
230 max
= get_dinfo_max(dinfo
);
231 if (iter_expr
->op
== SPECIAL_INCREMENT
&& min
!= whole_range
.min
&& max
== whole_range
.max
) {
232 set_state(my_id
, name
, sym
, alloc_extra_state(min
));
233 } else if (min
== whole_range
.min
&& max
!= whole_range
.max
) {
234 set_state(my_id
, name
, sym
, alloc_extra_state(max
));
241 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
243 return extra_undefined();
246 static void match_function_call(struct expression
*expr
)
248 struct expression
*tmp
;
253 FOR_EACH_PTR(expr
->args
, tmp
) {
254 if (tmp
->type
== EXPR_PREOP
&& tmp
->op
== '&') {
255 name
= get_variable_from_expr(tmp
->unop
, &sym
);
257 set_state(my_id
, name
, sym
, extra_undefined());
262 } END_FOR_EACH_PTR(tmp
);
265 static void match_assign(struct expression
*expr
)
267 struct expression
*left
;
268 struct expression
*right
;
273 long long min
= whole_range
.min
;
274 long long max
= whole_range
.max
;
276 struct range_list
*rl
= NULL
;
278 left
= strip_expr(expr
->left
);
279 name
= get_variable_from_expr(left
, &sym
);
282 right
= strip_expr(expr
->right
);
283 while (right
->type
== EXPR_ASSIGNMENT
&& right
->op
== '=')
284 right
= strip_expr(right
->left
);
286 known
= get_implied_range_list(right
, &rl
);
287 if (expr
->op
== '=') {
289 set_state(my_id
, name
, sym
, alloc_extra_state_range_list(rl
));
291 set_state(my_id
, name
, sym
, extra_undefined());
295 known
= get_implied_value(right
, &value
);
296 if (expr
->op
== SPECIAL_ADD_ASSIGN
) {
297 if (get_implied_min(left
, &tmp
)) {
305 if (expr
->op
== SPECIAL_SUB_ASSIGN
) {
306 if (get_implied_max(left
, &tmp
)) {
314 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
319 static void unop_expr(struct expression
*expr
)
323 long long min
= whole_range
.min
;
324 long long max
= whole_range
.max
;
332 name
= get_variable_from_expr(expr
->unop
, &sym
);
335 if (expr
->op
== SPECIAL_INCREMENT
) {
336 if (get_implied_min(expr
->unop
, &val
))
339 if (expr
->op
== SPECIAL_DECREMENT
) {
340 if (get_implied_max(expr
->unop
, &val
))
343 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
348 static void match_declarations(struct symbol
*sym
)
354 name
= sym
->ident
->name
;
355 if (sym
->initializer
) {
356 if (get_value(sym
->initializer
, &val
))
357 set_state(my_id
, name
, sym
, alloc_extra_state(val
));
359 set_state(my_id
, name
, sym
, extra_undefined());
360 scoped_state(my_id
, name
, sym
);
362 set_state(my_id
, name
, sym
, extra_undefined());
363 scoped_state(my_id
, name
, sym
);
368 static void match_function_def(struct symbol
*sym
)
373 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
377 set_state(my_id
, arg
->ident
->name
, arg
, extra_undefined());
378 } END_FOR_EACH_PTR(arg
);
385 static int get_implied_value_helper(struct expression
*expr
, long long *val
, int what
)
387 struct smatch_state
*state
;
391 if (get_value(expr
, val
))
394 name
= get_variable_from_expr(expr
, &sym
);
397 state
= get_state(my_id
, name
, sym
);
399 if (!state
|| !state
->data
)
401 if (what
== VAL_SINGLE
)
402 return get_single_value_from_range(get_dinfo(state
), val
);
403 if (what
== VAL_MAX
) {
404 *val
= get_dinfo_max(get_dinfo(state
));
405 if (*val
== whole_range
.max
) /* this means just guessing */
409 *val
= get_dinfo_min(get_dinfo(state
));
410 if (*val
== whole_range
.min
)
415 int get_implied_single_val(struct expression
*expr
, long long *val
)
417 return get_implied_value_helper(expr
, val
, VAL_SINGLE
);
420 int get_implied_max(struct expression
*expr
, long long *val
)
422 return get_implied_value_helper(expr
, val
, VAL_MAX
);
425 int get_implied_min(struct expression
*expr
, long long *val
)
427 return get_implied_value_helper(expr
, val
, VAL_MIN
);
430 int get_implied_single_fuzzy_max(struct expression
*expr
, long long *max
)
433 struct sm_state
*tmp
;
435 if (get_implied_max(expr
, max
))
438 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
442 *max
= whole_range
.min
;
443 FOR_EACH_PTR(sm
->possible
, tmp
) {
446 new_min
= get_dinfo_min(get_dinfo(tmp
->state
));
449 } END_FOR_EACH_PTR(tmp
);
451 if (*max
> whole_range
.min
)
456 static int last_stmt_val(struct statement
*stmt
, long long *val
)
458 struct expression
*expr
;
463 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
464 if (stmt
->type
!= STMT_EXPRESSION
)
466 expr
= stmt
->expression
;
467 return get_value(expr
, val
);
470 static void match_comparison(struct expression
*expr
)
475 struct smatch_state
*one_state
;
476 struct smatch_state
*two_state
;
477 struct smatch_state
*orig
;
479 int comparison
= expr
->op
;
480 struct expression
*varies
= expr
->right
;
482 if (!get_value(expr
->left
, &fixed
)) {
483 if (!get_value(expr
->right
, &fixed
))
488 if (varies
->op
== SPECIAL_INCREMENT
|| varies
->op
== SPECIAL_DECREMENT
)
489 varies
= varies
->unop
;
490 if (varies
->type
== EXPR_CALL
) {
491 function_comparison(comparison
, varies
, fixed
, left
);
495 name
= get_variable_from_expr(varies
, &sym
);
499 orig
= get_state(my_id
, name
, sym
);
501 orig
= extra_undefined();
503 switch (comparison
) {
505 case SPECIAL_UNSIGNED_LT
:
506 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
507 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
509 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
511 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
513 case SPECIAL_UNSIGNED_LTE
:
515 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
516 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
518 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
520 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
523 // todo. print a warning here for impossible conditions.
524 one_state
= alloc_extra_state(fixed
);
525 two_state
= filter_range(orig
, fixed
, fixed
);
526 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
528 case SPECIAL_UNSIGNED_GTE
:
530 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
531 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
533 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
535 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
538 case SPECIAL_UNSIGNED_GT
:
539 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
540 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
542 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
544 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
546 case SPECIAL_NOTEQUAL
:
547 one_state
= alloc_extra_state(fixed
);
548 two_state
= filter_range(orig
, fixed
, fixed
);
549 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
552 sm_msg("unhandled comparison %d\n", comparison
);
560 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
561 void __extra_match_condition(struct expression
*expr
)
565 struct smatch_state
*pre_state
;
566 struct smatch_state
*true_state
;
567 struct smatch_state
*false_state
;
569 expr
= strip_expr(expr
);
570 switch (expr
->type
) {
572 function_comparison(SPECIAL_NOTEQUAL
, expr
, 0, 1);
577 name
= get_variable_from_expr(expr
, &sym
);
580 pre_state
= get_state(my_id
, name
, sym
);
581 true_state
= add_filter(pre_state
, 0);
582 false_state
= alloc_extra_state(0);
583 set_true_false_states(my_id
, name
, sym
, true_state
, false_state
);
587 match_comparison(expr
);
589 case EXPR_ASSIGNMENT
:
590 __extra_match_condition(expr
->left
);
595 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
596 int implied_not_equal(struct expression
*expr
, long long val
)
600 struct smatch_state
*state
;
603 name
= get_variable_from_expr(expr
, &sym
);
606 state
= get_state(my_id
, name
, sym
);
607 if (!state
|| !state
->data
)
609 ret
= !possibly_false(SPECIAL_NOTEQUAL
, get_dinfo(state
), val
, 1);
615 int known_condition_true(struct expression
*expr
)
622 if (get_value(expr
, &tmp
) && tmp
)
625 expr
= strip_expr(expr
);
626 switch (expr
->type
) {
628 if (expr
->op
== '!') {
629 if (known_condition_false(expr
->unop
))
640 int known_condition_false(struct expression
*expr
)
648 switch (expr
->type
) {
650 if (expr
->op
== '!') {
651 if (known_condition_true(expr
->unop
))
662 static int do_comparison_range(struct expression
*expr
)
666 struct smatch_state
*state
;
669 int poss_true
, poss_false
;
671 if (!get_value(expr
->left
, &value
)) {
672 if (!get_value(expr
->right
, &value
))
677 name
= get_variable_from_expr(expr
->left
, &sym
);
679 name
= get_variable_from_expr(expr
->right
, &sym
);
682 state
= get_state(SMATCH_EXTRA
, name
, sym
);
685 poss_true
= possibly_true(expr
->op
, get_dinfo(state
), value
, left
);
686 poss_false
= possibly_false(expr
->op
, get_dinfo(state
), value
, left
);
687 if (!poss_true
&& !poss_false
)
689 if (poss_true
&& !poss_false
)
691 if (!poss_true
&& poss_false
)
693 if (poss_true
&& poss_false
)
700 int implied_condition_true(struct expression
*expr
)
702 struct statement
*stmt
;
709 if (get_value(expr
, &tmp
) && tmp
)
712 expr
= strip_expr(expr
);
713 switch (expr
->type
) {
715 if (do_comparison_range(expr
) == 1)
719 if (expr
->op
== '!') {
720 if (implied_condition_false(expr
->unop
))
724 stmt
= get_block_thing(expr
);
725 if (last_stmt_val(stmt
, &val
) && val
== 1)
729 if (implied_not_equal(expr
, 0) == 1)
736 int implied_condition_false(struct expression
*expr
)
738 struct statement
*stmt
;
739 struct expression
*tmp
;
748 switch (expr
->type
) {
750 if (do_comparison_range(expr
) == 2)
753 if (expr
->op
== '!') {
754 if (implied_condition_true(expr
->unop
))
758 stmt
= get_block_thing(expr
);
759 if (last_stmt_val(stmt
, &val
) && val
== 0)
761 tmp
= strip_expr(expr
);
763 return implied_condition_false(tmp
);
766 if (get_implied_value(expr
, &val
) && val
== 0)
773 int get_implied_range_list(struct expression
*expr
, struct range_list
**rl
)
776 struct smatch_state
*state
;
778 expr
= strip_expr(expr
);
780 state
= get_state_expr(my_id
, expr
);
782 *rl
= clone_range_list(get_dinfo(state
)->value_ranges
);
786 if (get_implied_value(expr
, &val
)) {
788 add_range(rl
, val
, val
);
792 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '%') {
793 if (!get_implied_value(expr
->right
, &val
))
796 add_range(rl
, 0, val
- 1);
803 void register_smatch_extra(int id
)
806 add_merge_hook(my_id
, &merge_func
);
807 add_unmatched_state_hook(my_id
, &unmatched_state
);
808 add_hook(&unop_expr
, OP_HOOK
);
809 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
810 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
811 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
812 add_hook(&match_declarations
, DECLARATION_HOOK
);
814 if (option_project
== PROJ_KERNEL
) {
815 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
816 add_function_hook("panic", &__match_nullify_path_hook
, NULL
);
817 add_function_hook("do_exit", &__match_nullify_path_hook
, NULL
);
818 add_function_hook("complete_and_exit", &__match_nullify_path_hook
, NULL
);
819 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook
, NULL
);
820 add_function_hook("do_group_exit", &__match_nullify_path_hook
, NULL
);