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(((struct data_info
*)state
->data
)->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(((struct data_info
*)state
->data
)->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(((struct data_info
*)state
->data
)->value_ranges
);
102 struct smatch_state
*filter_range(struct smatch_state
*orig
,
103 long long filter_min
, long long filter_max
)
105 struct smatch_state
*ret
;
106 struct data_info
*orig_info
;
107 struct data_info
*ret_info
;
110 orig
= extra_undefined();
111 orig_info
= (struct data_info
*)orig
->data
;
112 ret
= alloc_extra_state_empty();
113 ret_info
= (struct data_info
*)ret
->data
;
114 ret_info
->value_ranges
= remove_range(orig_info
->value_ranges
, filter_min
, filter_max
);
115 ret
->name
= show_ranges(ret_info
->value_ranges
);
119 struct smatch_state
*add_filter(struct smatch_state
*orig
, long long num
)
121 return filter_range(orig
, num
, num
);
124 static struct smatch_state
*merge_func(const char *name
, struct symbol
*sym
,
125 struct smatch_state
*s1
,
126 struct smatch_state
*s2
)
128 struct data_info
*info1
= (struct data_info
*)s1
->data
;
129 struct data_info
*info2
= (struct data_info
*)s2
->data
;
130 struct data_info
*ret_info
;
131 struct smatch_state
*tmp
;
132 struct range_list
*value_ranges
;
134 value_ranges
= range_list_union(info1
->value_ranges
, info2
->value_ranges
);
135 tmp
= alloc_extra_state_empty();
136 ret_info
= (struct data_info
*)tmp
->data
;
137 ret_info
->value_ranges
= value_ranges
;
138 tmp
->name
= show_ranges(ret_info
->value_ranges
);
142 struct sm_state
*__extra_pre_loop_hook_before(struct statement
*iterator_pre_statement
)
144 struct expression
*expr
;
147 struct sm_state
*ret
= NULL
;
149 if (!iterator_pre_statement
)
151 if (iterator_pre_statement
->type
!= STMT_EXPRESSION
)
153 expr
= iterator_pre_statement
->expression
;
154 if (expr
->type
!= EXPR_ASSIGNMENT
)
156 name
= get_variable_from_expr(expr
->left
, &sym
);
159 ret
= get_sm_state(my_id
, name
, sym
);
165 static const char *get_iter_op(struct expression
*expr
)
167 if (expr
->type
!= EXPR_POSTOP
&& expr
->type
!= EXPR_PREOP
)
169 return show_special(expr
->op
);
172 int __iterator_unchanged(struct sm_state
*sm
, struct statement
*iterator
)
174 struct expression
*iter_expr
;
182 if (iterator
->type
!= STMT_EXPRESSION
)
184 iter_expr
= iterator
->expression
;
185 op
= get_iter_op(iter_expr
);
186 if (!op
|| (strcmp(op
, "--") && strcmp(op
, "++")))
188 name
= get_variable_from_expr(iter_expr
->unop
, &sym
);
191 if (get_sm_state(my_id
, name
, sym
) == sm
)
198 void __extra_pre_loop_hook_after(struct sm_state
*sm
,
199 struct statement
*iterator
,
200 struct expression
*condition
)
202 struct expression
*iter_expr
;
208 struct smatch_state
*state
;
209 struct data_info
*dinfo
;
212 iter_expr
= iterator
->expression
;
214 if (condition
->type
!= EXPR_COMPARE
)
216 if (!get_value(condition
->left
, &value
)) {
217 if (!get_value(condition
->right
, &value
))
222 name
= get_variable_from_expr(condition
->left
, &sym
);
224 name
= get_variable_from_expr(condition
->right
, &sym
);
227 if (sym
!= sm
->sym
|| strcmp(name
, sm
->name
))
229 op
= get_iter_op(iter_expr
);
230 state
= get_state(my_id
, name
, sym
);
231 dinfo
= (struct data_info
*)state
->data
;
232 min
= get_dinfo_min(dinfo
);
233 max
= get_dinfo_max(dinfo
);
234 if (!strcmp(op
, "++") && min
!= whole_range
.min
&& max
== whole_range
.max
) {
235 set_state(my_id
, name
, sym
, alloc_extra_state(min
));
236 } else if (min
== whole_range
.min
&& max
!= whole_range
.max
) {
237 set_state(my_id
, name
, sym
, alloc_extra_state(max
));
244 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
246 return extra_undefined();
249 static void match_function_call(struct expression
*expr
)
251 struct expression
*tmp
;
256 FOR_EACH_PTR(expr
->args
, tmp
) {
257 if (tmp
->op
== '&') {
258 name
= get_variable_from_expr(tmp
->unop
, &sym
);
260 set_state(my_id
, name
, sym
, extra_undefined());
265 } END_FOR_EACH_PTR(tmp
);
268 static void match_assign(struct expression
*expr
)
270 struct expression
*left
;
275 long long min
= whole_range
.min
;
276 long long max
= whole_range
.max
;
279 left
= strip_expr(expr
->left
);
280 name
= get_variable_from_expr(left
, &sym
);
283 known
= get_value(expr
->right
, &value
);
285 if (expr
->op
== '=') {
287 set_state(my_id
, name
, sym
, alloc_extra_state(value
));
289 set_state(my_id
, name
, sym
, extra_undefined());
292 if (expr
->op
== SPECIAL_ADD_ASSIGN
) {
293 if (get_implied_min(expr
->unop
, &tmp
)) {
301 if (expr
->op
== SPECIAL_SUB_ASSIGN
) {
302 if (get_implied_max(expr
->unop
, &tmp
)) {
310 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
315 static void undef_expr(struct expression
*expr
)
319 long long min
= whole_range
.min
;
320 long long max
= whole_range
.max
;
328 name
= get_variable_from_expr(expr
->unop
, &sym
);
331 if (!strcmp("++", show_special(expr
->op
))) {
332 if (get_implied_min(expr
->unop
, &val
))
335 if (!strcmp("--", show_special(expr
->op
))) {
336 if (get_implied_max(expr
->unop
, &val
))
339 set_state(my_id
, name
, sym
, alloc_extra_state_range(min
, max
));
344 static void match_declarations(struct symbol
*sym
)
350 name
= sym
->ident
->name
;
351 if (sym
->initializer
) {
352 if (get_value(sym
->initializer
, &val
))
353 set_state(my_id
, name
, sym
, alloc_extra_state(val
));
355 set_state(my_id
, name
, sym
, extra_undefined());
356 scoped_state(name
, my_id
, sym
);
358 set_state(my_id
, name
, sym
, extra_undefined());
359 scoped_state(name
, my_id
, sym
);
364 static void match_function_def(struct symbol
*sym
)
369 FOR_EACH_PTR(sym
->ctype
.base_type
->arguments
, arg
) {
373 set_state(my_id
, arg
->ident
->name
, arg
, extra_undefined());
374 } END_FOR_EACH_PTR(arg
);
381 static int get_implied_value_helper(struct expression
*expr
, long long *val
, int what
)
383 struct smatch_state
*state
;
387 if (get_value(expr
, val
))
390 name
= get_variable_from_expr(expr
, &sym
);
393 state
= get_state(my_id
, name
, sym
);
395 if (!state
|| !state
->data
)
397 if (what
== VAL_SINGLE
)
398 return get_single_value_from_range((struct data_info
*)state
->data
, val
);
399 if (what
== VAL_MAX
) {
400 *val
= get_dinfo_max((struct data_info
*)state
->data
);
401 if (*val
== whole_range
.max
) /* this means just guessing */
405 *val
= get_dinfo_min((struct data_info
*)state
->data
);
406 if (*val
== whole_range
.min
)
411 int get_implied_single_val(struct expression
*expr
, long long *val
)
413 return get_implied_value_helper(expr
, val
, VAL_SINGLE
);
416 int get_implied_max(struct expression
*expr
, long long *val
)
418 return get_implied_value_helper(expr
, val
, VAL_MAX
);
421 int get_implied_min(struct expression
*expr
, long long *val
)
423 return get_implied_value_helper(expr
, val
, VAL_MIN
);
426 static int last_stmt_val(struct statement
*stmt
, long long *val
)
428 struct expression
*expr
;
433 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
434 if (stmt
->type
!= STMT_EXPRESSION
)
436 expr
= stmt
->expression
;
437 return get_value(expr
, val
);
440 static void match_comparison(struct expression
*expr
)
445 struct smatch_state
*one_state
;
446 struct smatch_state
*two_state
;
447 struct smatch_state
*orig
;
449 int comparison
= expr
->op
;
450 struct expression
*varies
= expr
->right
;
452 if (!get_value(expr
->left
, &fixed
)) {
453 if (!get_value(expr
->right
, &fixed
))
458 if (varies
->type
== EXPR_PREOP
|| varies
->type
== EXPR_POSTOP
) {
459 varies
= varies
->unop
;
461 if (varies
->type
== EXPR_CALL
) {
462 function_comparison(comparison
, varies
, fixed
, left
);
465 name
= get_variable_from_expr(varies
, &sym
);
469 orig
= get_state(my_id
, name
, sym
);
471 orig
= extra_undefined();
475 case SPECIAL_UNSIGNED_LT
:
476 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
477 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
479 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
481 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
483 case SPECIAL_UNSIGNED_LTE
:
485 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
486 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
488 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
490 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
493 // todo. print a warning here for impossible conditions.
494 one_state
= alloc_extra_state(fixed
);
495 two_state
= filter_range(orig
, fixed
, fixed
);
496 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
498 case SPECIAL_UNSIGNED_GTE
:
500 one_state
= filter_range(orig
, whole_range
.min
, fixed
- 1);
501 two_state
= filter_range(orig
, fixed
, whole_range
.max
);
503 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
505 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
508 case SPECIAL_UNSIGNED_GT
:
509 one_state
= filter_range(orig
, whole_range
.min
, fixed
);
510 two_state
= filter_range(orig
, fixed
+ 1, whole_range
.max
);
512 set_true_false_states(my_id
, name
, sym
, one_state
, two_state
);
514 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
516 case SPECIAL_NOTEQUAL
:
517 one_state
= alloc_extra_state(fixed
);
518 two_state
= filter_range(orig
, fixed
, fixed
);
519 set_true_false_states(my_id
, name
, sym
, two_state
, one_state
);
522 sm_msg("unhandled comparison %d\n", comparison
);
530 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
531 void __extra_match_condition(struct expression
*expr
)
535 struct smatch_state
*pre_state
;
536 struct smatch_state
*true_state
;
537 struct smatch_state
*false_state
;
539 expr
= strip_expr(expr
);
542 function_comparison(SPECIAL_NOTEQUAL
, expr
, 0, 1);
547 name
= get_variable_from_expr(expr
, &sym
);
550 pre_state
= get_state(my_id
, name
, sym
);
551 true_state
= add_filter(pre_state
, 0);
552 false_state
= alloc_extra_state(0);
553 set_true_false_states(my_id
, name
, sym
, true_state
, false_state
);
557 match_comparison(expr
);
559 case EXPR_ASSIGNMENT
:
560 __extra_match_condition(expr
->right
);
561 __extra_match_condition(expr
->left
);
566 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
567 int implied_not_equal(struct expression
*expr
, long long val
)
571 struct smatch_state
*state
;
574 name
= get_variable_from_expr(expr
, &sym
);
577 state
= get_state(my_id
, name
, sym
);
578 if (!state
|| !state
->data
)
580 ret
= !possibly_false(SPECIAL_NOTEQUAL
, (struct data_info
*)state
->data
, val
, 1);
586 int known_condition_true(struct expression
*expr
)
593 if (get_value(expr
, &tmp
) && tmp
)
596 expr
= strip_expr(expr
);
599 if (expr
->op
== '!') {
600 if (known_condition_false(expr
->unop
))
611 int known_condition_false(struct expression
*expr
)
621 if (expr
->op
== '!') {
622 if (known_condition_true(expr
->unop
))
633 static int do_comparison_range(struct expression
*expr
)
637 struct smatch_state
*state
;
640 int poss_true
, poss_false
;
642 if (!get_value(expr
->left
, &value
)) {
643 if (!get_value(expr
->right
, &value
))
648 name
= get_variable_from_expr(expr
->left
, &sym
);
650 name
= get_variable_from_expr(expr
->right
, &sym
);
653 state
= get_state(SMATCH_EXTRA
, name
, sym
);
656 poss_true
= possibly_true(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
657 poss_false
= possibly_false(expr
->op
, (struct data_info
*)state
->data
, value
, left
);
658 if (!poss_true
&& !poss_false
)
660 if (poss_true
&& !poss_false
)
662 if (!poss_true
&& poss_false
)
664 if (poss_true
&& poss_false
)
671 int implied_condition_true(struct expression
*expr
)
673 struct statement
*stmt
;
680 if (get_value(expr
, &tmp
) && tmp
)
683 expr
= strip_expr(expr
);
686 if (do_comparison_range(expr
) == 1)
690 if (expr
->op
== '!') {
691 if (implied_condition_false(expr
->unop
))
695 stmt
= get_block_thing(expr
);
696 if (last_stmt_val(stmt
, &val
) && val
== 1)
700 if (implied_not_equal(expr
, 0) == 1)
707 int implied_condition_false(struct expression
*expr
)
709 struct statement
*stmt
;
710 struct expression
*tmp
;
721 if (do_comparison_range(expr
) == 2)
724 if (expr
->op
== '!') {
725 if (implied_condition_true(expr
->unop
))
729 stmt
= get_block_thing(expr
);
730 if (last_stmt_val(stmt
, &val
) && val
== 0)
732 tmp
= strip_expr(expr
);
734 return implied_condition_false(tmp
);
737 if (get_implied_value(expr
, &val
) && val
== 0)
744 void register_smatch_extra(int id
)
747 add_merge_hook(my_id
, &merge_func
);
748 add_unmatched_state_hook(my_id
, &unmatched_state
);
749 add_hook(&undef_expr
, OP_HOOK
);
750 add_hook(&match_function_def
, FUNC_DEF_HOOK
);
751 add_hook(&match_function_call
, FUNCTION_CALL_HOOK
);
752 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
753 add_hook(&match_declarations
, DECLARATION_HOOK
);
755 if (option_project
== PROJ_KERNEL
) {
756 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
757 add_function_hook("panic", &__match_nullify_path_hook
, NULL
);
758 add_function_hook("do_exit", &__match_nullify_path_hook
, NULL
);
759 add_function_hook("complete_and_exit", &__match_nullify_path_hook
, NULL
);
760 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook
, NULL
);
761 add_function_hook("do_group_exit", &__match_nullify_path_hook
, NULL
);