2 * Copyright (C) 2009 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 * There are several types of function hooks:
20 * add_function_hook() - For any time a function is called.
21 * add_function_assign_hook() - foo = the_function().
22 * add_implied_return_hook() - Calculates the implied return value.
23 * add_macro_assign_hook() - foo = the_macro().
24 * return_implies_state() - For when a return value of 1 implies locked
25 * and 0 implies unlocked. etc. etc.
32 #include "smatch_slist.h"
33 #include "smatch_extra.h"
34 #include "smatch_function_hashtable.h"
38 struct data_range
*range
;
41 implication_hook
*ranged
;
42 implied_return_hook
*implied_return
;
47 ALLOCATOR(fcall_back
, "call backs");
48 DECLARE_PTR_LIST(call_back_list
, struct fcall_back
);
50 DEFINE_FUNCTION_HASHTABLE_STATIC(callback
, struct fcall_back
, struct call_back_list
);
51 static struct hashtable
*func_hash
;
53 int __in_fake_parameter_assign
;
66 struct param_key_data
{
67 param_key_hook
*call_back
;
73 struct return_implies_callback
{
77 return_implies_hook
*callback
;
78 param_key_hook
*pk_callback
;
81 ALLOCATOR(return_implies_callback
, "return_implies callbacks");
82 DECLARE_PTR_LIST(db_implies_list
, struct return_implies_callback
);
83 static struct db_implies_list
*db_return_states_list
;
85 typedef void (void_fn
)(void);
86 DECLARE_PTR_LIST(void_fn_list
, void_fn
*);
87 static struct void_fn_list
*return_states_before
;
88 static struct void_fn_list
*return_states_after
;
90 static struct fcall_back
*alloc_fcall_back(int type
, void *call_back
,
93 struct fcall_back
*cb
;
95 cb
= __alloc_fcall_back(0);
97 cb
->u
.call_back
= call_back
;
102 void add_function_hook(const char *look_for
, func_hook
*call_back
, void *info
)
104 struct fcall_back
*cb
;
106 cb
= alloc_fcall_back(REGULAR_CALL
, call_back
, info
);
107 add_callback(func_hash
, look_for
, cb
);
110 void add_function_hook_late(const char *look_for
, func_hook
*call_back
, void *info
)
112 struct fcall_back
*cb
;
114 cb
= alloc_fcall_back(REGULAR_CALL_LATE
, call_back
, info
);
115 add_callback(func_hash
, look_for
, cb
);
118 void add_function_assign_hook(const char *look_for
, func_hook
*call_back
,
121 struct fcall_back
*cb
;
123 cb
= alloc_fcall_back(ASSIGN_CALL
, call_back
, info
);
124 add_callback(func_hash
, look_for
, cb
);
127 static void register_funcs_from_file_helper(const char *file
,
128 func_hook
*call_back
, void *info
,
135 snprintf(name
, sizeof(name
), "%s.%s", option_project_str
, file
);
136 token
= get_tokens_file(name
);
139 if (token_type(token
) != TOKEN_STREAMBEGIN
)
142 while (token_type(token
) != TOKEN_STREAMEND
) {
143 if (token_type(token
) != TOKEN_IDENT
)
145 func
= show_ident(token
->ident
);
147 add_function_assign_hook(func
, call_back
, info
);
149 add_function_hook(func
, call_back
, info
);
155 void register_func_hooks_from_file(const char *file
,
156 func_hook
*call_back
, void *info
)
158 register_funcs_from_file_helper(file
, call_back
, info
, false);
161 void register_assign_hooks_from_file(const char *file
,
162 func_hook
*call_back
, void *info
)
164 register_funcs_from_file_helper(file
, call_back
, info
, true);
167 void add_implied_return_hook(const char *look_for
,
168 implied_return_hook
*call_back
,
171 struct fcall_back
*cb
;
173 cb
= alloc_fcall_back(IMPLIED_RETURN
, call_back
, info
);
174 add_callback(func_hash
, look_for
, cb
);
177 static void db_helper(struct expression
*expr
, param_key_hook
*call_back
, int param
, const char *key
, void *info
)
183 call_back(expr
, key
, NULL
, info
);
187 name
= get_name_sym_from_key(expr
, param
, key
, &sym
);
191 call_back(expr
, name
, sym
, info
);
196 static void param_key_function(const char *fn
, struct expression
*expr
, void *data
)
198 struct param_key_data
*pkd
= data
;
199 struct expression
*parent
;
204 parent
= expr_get_parent_expr(parent
);
205 if (!parent
|| ++cnt
>= 5)
207 if (parent
->type
== EXPR_CAST
)
209 if (parent
->type
== EXPR_PREOP
&& parent
->op
== '(')
214 if (parent
&& parent
->type
== EXPR_ASSIGNMENT
)
217 db_helper(expr
, pkd
->call_back
, pkd
->param
, pkd
->key
, pkd
->info
);
220 static void param_key_implies_function(const char *fn
, struct expression
*call_expr
,
221 struct expression
*assign_expr
, void *data
)
223 struct param_key_data
*pkd
= data
;
225 db_helper(assign_expr
?: call_expr
, pkd
->call_back
, pkd
->param
, pkd
->key
, pkd
->info
);
228 static struct param_key_data
*alloc_pkd(param_key_hook
*call_back
, int param
, const char *key
, void *info
)
230 struct param_key_data
*pkd
;
232 pkd
= malloc(sizeof(*pkd
));
233 pkd
->call_back
= call_back
;
235 pkd
->key
= alloc_string(key
);
241 void add_function_param_key_hook(const char *look_for
, param_key_hook
*call_back
,
242 int param
, const char *key
, void *info
)
244 struct param_key_data
*pkd
;
246 pkd
= alloc_pkd(call_back
, param
, key
, info
);
247 add_function_hook(look_for
, ¶m_key_function
, pkd
);
250 void return_implies_param_key(const char *look_for
, sval_t start
, sval_t end
,
251 param_key_hook
*call_back
,
252 int param
, const char *key
, void *info
)
254 struct param_key_data
*pkd
;
256 pkd
= alloc_pkd(call_back
, param
, key
, info
);
257 return_implies_state_sval(look_for
, start
, end
, ¶m_key_implies_function
, pkd
);
260 void return_implies_param_key_exact(const char *look_for
, sval_t start
, sval_t end
,
261 param_key_hook
*call_back
,
262 int param
, const char *key
, void *info
)
264 struct param_key_data
*pkd
;
266 pkd
= alloc_pkd(call_back
, param
, key
, info
);
267 return_implies_exact(look_for
, start
, end
, ¶m_key_implies_function
, pkd
);
270 void add_macro_assign_hook(const char *look_for
, func_hook
*call_back
,
273 struct fcall_back
*cb
;
275 cb
= alloc_fcall_back(MACRO_ASSIGN
, call_back
, info
);
276 add_callback(func_hash
, look_for
, cb
);
279 void add_macro_assign_hook_extra(const char *look_for
, func_hook
*call_back
,
282 struct fcall_back
*cb
;
284 cb
= alloc_fcall_back(MACRO_ASSIGN_EXTRA
, call_back
, info
);
285 add_callback(func_hash
, look_for
, cb
);
288 void return_implies_state(const char *look_for
, long long start
, long long end
,
289 implication_hook
*call_back
, void *info
)
291 struct fcall_back
*cb
;
293 cb
= alloc_fcall_back(RANGED_CALL
, call_back
, info
);
294 cb
->range
= alloc_range_perm(ll_to_sval(start
), ll_to_sval(end
));
295 add_callback(func_hash
, look_for
, cb
);
298 void return_implies_state_sval(const char *look_for
, sval_t start
, sval_t end
,
299 implication_hook
*call_back
, void *info
)
301 struct fcall_back
*cb
;
303 cb
= alloc_fcall_back(RANGED_CALL
, call_back
, info
);
304 cb
->range
= alloc_range_perm(start
, end
);
305 add_callback(func_hash
, look_for
, cb
);
308 void return_implies_exact(const char *look_for
, sval_t start
, sval_t end
,
309 implication_hook
*call_back
, void *info
)
311 struct fcall_back
*cb
;
313 cb
= alloc_fcall_back(RANGED_EXACT
, call_back
, info
);
314 cb
->range
= alloc_range_perm(start
, end
);
315 add_callback(func_hash
, look_for
, cb
);
318 static struct return_implies_callback
*alloc_db_return_callback(int type
, bool param_key
, void *callback
)
320 struct return_implies_callback
*cb
;
322 cb
= __alloc_return_implies_callback(0);
324 cb
->param_key
= param_key
;
325 cb
->callback
= callback
;
330 void select_return_states_hook(int type
, return_implies_hook
*callback
)
332 struct return_implies_callback
*cb
;
334 cb
= alloc_db_return_callback(type
, false, callback
);
335 add_ptr_list(&db_return_states_list
, cb
);
338 static void call_db_return_callback(struct return_implies_callback
*cb
,
339 struct expression
*expr
, int param
, char *key
, char *value
)
342 // FIXME check if cb->pk_callback was already called
343 db_helper(expr
, cb
->pk_callback
, param
, key
, NULL
);
345 cb
->callback(expr
, param
, key
, value
);
349 void select_return_param_key(int type
, param_key_hook
*callback
)
351 struct return_implies_callback
*cb
;
353 cb
= alloc_db_return_callback(type
, true, callback
);
354 add_ptr_list(&db_return_states_list
, cb
);
357 void select_return_states_before(void_fn
*fn
)
359 void_fn
**p
= malloc(sizeof(void_fn
*));
361 add_ptr_list(&return_states_before
, p
);
364 void select_return_states_after(void_fn
*fn
)
366 void_fn
**p
= malloc(sizeof(void_fn
*));
368 add_ptr_list(&return_states_after
, p
);
371 static void call_return_states_before_hooks(void)
375 FOR_EACH_PTR(return_states_before
, fn
) {
377 } END_FOR_EACH_PTR(fn
);
380 static int call_call_backs(struct call_back_list
*list
, int type
,
381 const char *fn
, struct expression
*expr
)
383 struct fcall_back
*tmp
;
386 FOR_EACH_PTR(list
, tmp
) {
387 if (tmp
->type
== type
) {
388 (tmp
->u
.call_back
)(fn
, expr
, tmp
->info
);
391 } END_FOR_EACH_PTR(tmp
);
396 static void call_function_hooks(struct expression
*expr
, enum fn_hook_type type
)
398 struct call_back_list
*call_backs
;
399 struct expression
*fn
;
401 while (expr
->type
== EXPR_ASSIGNMENT
)
402 expr
= strip_expr(expr
->right
);
403 if (expr
->type
!= EXPR_CALL
)
406 fn
= strip_expr(expr
->fn
);
407 if (fn
->type
!= EXPR_SYMBOL
|| !fn
->symbol
)
410 call_backs
= search_callback(func_hash
, (char *)fn
->symbol
->ident
->name
);
414 call_call_backs(call_backs
, type
, fn
->symbol
->ident
->name
, expr
);
417 static void call_return_states_after_hooks(struct expression
*expr
)
421 FOR_EACH_PTR(return_states_after
, fn
) {
423 } END_FOR_EACH_PTR(fn
);
424 __pass_to_client(expr
, FUNCTION_CALL_HOOK_AFTER_DB
);
425 call_function_hooks(expr
, REGULAR_CALL_LATE
);
428 static void call_ranged_call_backs(struct call_back_list
*list
,
429 const char *fn
, struct expression
*call_expr
,
430 struct expression
*assign_expr
)
432 struct fcall_back
*tmp
;
434 FOR_EACH_PTR(list
, tmp
) {
435 (tmp
->u
.ranged
)(fn
, call_expr
, assign_expr
, tmp
->info
);
436 } END_FOR_EACH_PTR(tmp
);
439 static struct call_back_list
*get_same_ranged_call_backs(struct call_back_list
*list
,
440 struct data_range
*drange
)
442 struct call_back_list
*ret
= NULL
;
443 struct fcall_back
*tmp
;
445 FOR_EACH_PTR(list
, tmp
) {
446 if (tmp
->type
!= RANGED_CALL
&&
447 tmp
->type
!= RANGED_EXACT
)
449 if (ranges_equiv(tmp
->range
, drange
))
450 add_ptr_list(&ret
, tmp
);
451 } END_FOR_EACH_PTR(tmp
);
455 static int in_list_exact_sval(struct range_list
*list
, struct data_range
*drange
)
457 struct data_range
*tmp
;
459 FOR_EACH_PTR(list
, tmp
) {
460 if (ranges_equiv(tmp
, drange
))
462 } END_FOR_EACH_PTR(tmp
);
466 static int assign_ranged_funcs(const char *fn
, struct expression
*expr
,
467 struct call_back_list
*call_backs
)
469 struct fcall_back
*tmp
;
473 struct smatch_state
*estate
;
474 struct stree
*tmp_stree
;
475 struct stree
*final_states
= NULL
;
476 struct range_list
*handled_ranges
= NULL
;
477 struct call_back_list
*same_range_call_backs
= NULL
;
478 struct range_list
*rl
;
484 var_name
= expr_to_var_sym(expr
->left
, &sym
);
485 if (!var_name
|| !sym
)
488 FOR_EACH_PTR(call_backs
, tmp
) {
489 if (tmp
->type
!= RANGED_CALL
&&
490 tmp
->type
!= RANGED_EXACT
)
493 if (in_list_exact_sval(handled_ranges
, tmp
->range
))
495 __push_fake_cur_stree();
496 tack_on(&handled_ranges
, tmp
->range
);
498 same_range_call_backs
= get_same_ranged_call_backs(call_backs
, tmp
->range
);
499 call_ranged_call_backs(same_range_call_backs
, fn
, expr
->right
, expr
);
500 __free_ptr_list((struct ptr_list
**)&same_range_call_backs
);
502 rl
= alloc_rl(tmp
->range
->min
, tmp
->range
->max
);
503 rl
= cast_rl(get_type(expr
->left
), rl
);
504 estate
= alloc_estate_rl(rl
);
505 set_extra_mod(var_name
, sym
, expr
->left
, estate
);
507 tmp_stree
= __pop_fake_cur_stree();
508 merge_fake_stree(&final_states
, tmp_stree
);
509 free_stree(&tmp_stree
);
511 } END_FOR_EACH_PTR(tmp
);
513 FOR_EACH_SM(final_states
, sm
) {
515 } END_FOR_EACH_SM(sm
);
517 free_stree(&final_states
);
519 free_string(var_name
);
523 static void call_implies_callbacks(int comparison
, struct expression
*expr
, sval_t sval
, int left
, struct stree
**implied_true
, struct stree
**implied_false
)
525 struct call_back_list
*call_backs
;
526 struct fcall_back
*tmp
;
528 struct data_range
*value_range
;
529 struct stree
*true_states
= NULL
;
530 struct stree
*false_states
= NULL
;
531 struct stree
*tmp_stree
;
533 *implied_true
= NULL
;
534 *implied_false
= NULL
;
535 if (expr
->fn
->type
!= EXPR_SYMBOL
|| !expr
->fn
->symbol
)
537 fn
= expr
->fn
->symbol
->ident
->name
;
538 call_backs
= search_callback(func_hash
, (char *)expr
->fn
->symbol
->ident
->name
);
541 value_range
= alloc_range(sval
, sval
);
543 /* set true states */
544 __push_fake_cur_stree();
545 FOR_EACH_PTR(call_backs
, tmp
) {
546 if (tmp
->type
!= RANGED_CALL
&&
547 tmp
->type
!= RANGED_EXACT
)
549 if (!true_comparison_range_LR(comparison
, tmp
->range
, value_range
, left
))
551 (tmp
->u
.ranged
)(fn
, expr
, NULL
, tmp
->info
);
552 } END_FOR_EACH_PTR(tmp
);
553 tmp_stree
= __pop_fake_cur_stree();
554 merge_fake_stree(&true_states
, tmp_stree
);
555 free_stree(&tmp_stree
);
557 /* set false states */
558 __push_fake_cur_stree();
559 FOR_EACH_PTR(call_backs
, tmp
) {
560 if (tmp
->type
!= RANGED_CALL
&&
561 tmp
->type
!= RANGED_EXACT
)
563 if (!false_comparison_range_LR(comparison
, tmp
->range
, value_range
, left
))
565 (tmp
->u
.ranged
)(fn
, expr
, NULL
, tmp
->info
);
566 } END_FOR_EACH_PTR(tmp
);
567 tmp_stree
= __pop_fake_cur_stree();
568 merge_fake_stree(&false_states
, tmp_stree
);
569 free_stree(&tmp_stree
);
571 *implied_true
= true_states
;
572 *implied_false
= false_states
;
575 struct db_callback_info
{
578 struct expression
*expr
;
579 struct range_list
*rl
;
582 struct stree
*implied
;
583 struct db_implies_list
*callbacks
;
588 struct smatch_state
*ret_state
;
589 struct expression
*var_expr
;
593 static void set_implied_states(struct db_callback_info
*db_info
)
597 FOR_EACH_SM(db_info
->implied
, sm
) {
599 } END_FOR_EACH_SM(sm
);
601 free_stree(&db_info
->implied
);
604 static void store_return_state(struct db_callback_info
*db_info
, const char *ret_str
, struct smatch_state
*state
)
606 db_info
->ret_str
= alloc_sname(ret_str
),
607 db_info
->ret_state
= state
;
610 static bool fake_a_param_assignment(struct expression
*expr
, const char *ret_str
, struct smatch_state
*orig
)
612 struct expression
*arg
, *left
, *right
, *tmp
, *fake_assign
;
618 if (expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
623 while (right
->type
== EXPR_ASSIGNMENT
)
624 right
= strip_expr(right
->right
);
625 if (!right
|| right
->type
!= EXPR_CALL
)
628 p
= strchr(ret_str
, '[');
633 if (p
[0] == '=' && p
[1] == '=')
638 snprintf(buf
, sizeof(buf
), "%s", p
);
642 param
= strtol(p
, &p
, 10);
649 arg
= get_argument_from_call_expr(right
->args
, param
);
653 /* There should be a get_other_name() function which returns an expr */
654 tmp
= get_assigned_expr(arg
);
659 * This is a sanity check to prevent side effects from evaluating stuff
662 str
= expr_to_chunk_sym_vsl(arg
, NULL
, NULL
);
667 right
= gen_expression_from_key(arg
, buf
);
668 if (!right
) /* Mostly fails for binops like [$0 + 4032] */
670 fake_assign
= assign_expression(left
, '=', right
);
671 __in_fake_parameter_assign
++;
672 __split_expr(fake_assign
);
673 __in_fake_parameter_assign
--;
676 * If the return is "0-65531[$0->nla_len - 4]" the faked expression
677 * is maybe (-4)-65531 but we know it is in the 0-65531 range so both
678 * parts have to be considered. We use _nomod() because it's not really
679 * another modification, it's just a clarification.
682 if (estate_rl(orig
)) {
683 struct smatch_state
*faked
;
684 struct range_list
*rl
;
686 faked
= get_extra_state(left
);
687 if (estate_rl(faked
)) {
688 rl
= rl_intersection(estate_rl(faked
), estate_rl(orig
));
690 set_extra_expr_nomod(expr
, alloc_estate_rl(rl
));
697 static void set_fresh_mtag_returns(struct db_callback_info
*db_info
)
699 struct expression
*expr
= db_info
->expr
->left
;
700 struct smatch_state
*state
;
702 if (!db_info
->ret_state
)
705 state
= alloc_estate_rl(cast_rl(get_type(expr
), clone_rl(estate_rl(db_info
->ret_state
))));
706 state
= get_mtag_return(db_info
->expr
, state
);
710 set_real_absolute(expr
, state
);
711 set_extra_expr_mod(expr
, state
);
713 db_info
->ret_state
= NULL
;
714 db_info
->ret_str
= NULL
;
717 static void set_return_assign_state(struct db_callback_info
*db_info
)
719 struct expression
*expr
= db_info
->expr
->left
;
720 struct smatch_state
*state
;
722 if (!db_info
->ret_state
)
725 state
= alloc_estate_rl(cast_rl(get_type(expr
), clone_rl(estate_rl(db_info
->ret_state
))));
726 if (!fake_a_param_assignment(db_info
->expr
, db_info
->ret_str
, state
))
727 set_extra_expr_mod(expr
, state
);
729 db_info
->ret_state
= NULL
;
730 db_info
->ret_str
= NULL
;
733 static void set_other_side_state(struct db_callback_info
*db_info
)
735 struct expression
*expr
= db_info
->var_expr
;
736 struct smatch_state
*state
;
738 if (!db_info
->ret_state
)
741 state
= alloc_estate_rl(cast_rl(get_type(expr
), clone_rl(estate_rl(db_info
->ret_state
))));
742 set_extra_expr_nomod(expr
, state
);
743 db_info
->ret_state
= NULL
;
744 db_info
->ret_str
= NULL
;
747 static void handle_ret_equals_param(char *ret_string
, struct range_list
*rl
, struct expression
*call
)
751 struct expression
*arg
;
752 struct range_list
*orig
;
754 str
= strstr(ret_string
, "==$");
758 param
= strtoll(str
, NULL
, 10);
759 arg
= get_argument_from_call_expr(call
->args
, param
);
762 get_absolute_rl(arg
, &orig
);
763 rl
= rl_intersection(orig
, rl
);
766 set_extra_expr_nomod(arg
, alloc_estate_rl(rl
));
769 static int impossible_limit(struct expression
*expr
, int param
, char *key
, char *value
)
771 struct expression
*arg
;
772 struct smatch_state
*state
;
773 struct range_list
*passed
;
774 struct range_list
*limit
;
775 struct symbol
*compare_type
;
777 while (expr
->type
== EXPR_ASSIGNMENT
)
778 expr
= strip_expr(expr
->right
);
779 if (expr
->type
!= EXPR_CALL
)
782 arg
= get_argument_from_call_expr(expr
->args
, param
);
786 if (strcmp(key
, "$") == 0) {
787 if (!get_implied_rl(arg
, &passed
))
790 compare_type
= get_arg_type(expr
->fn
, param
);
795 name
= get_variable_from_key(arg
, key
, &sym
);
799 state
= get_state(SMATCH_EXTRA
, name
, sym
);
804 passed
= estate_rl(state
);
805 if (!passed
|| is_whole_rl(passed
)) {
810 compare_type
= get_member_type_from_key(arg
, key
);
813 passed
= cast_rl(compare_type
, passed
);
814 call_results_to_rl(expr
, compare_type
, value
, &limit
);
815 if (!limit
|| is_whole_rl(limit
))
817 if (possibly_true_rl(passed
, SPECIAL_EQUAL
, limit
))
819 if (option_debug
|| local_debug
)
820 sm_msg("impossible: %d '%s' limit '%s' == '%s'", param
, key
, show_rl(passed
), value
);
824 static int is_impossible_data(int type
, struct expression
*expr
, int param
, char *key
, char *value
)
826 if (type
== PARAM_LIMIT
&& impossible_limit(expr
, param
, key
, value
))
828 if (type
== COMPARE_LIMIT
&& param_compare_limit_is_impossible(expr
, param
, key
, value
)) {
830 sm_msg("param_compare_limit_is_impossible: %d %s %s", param
, key
, value
);
836 static int func_type_mismatch(struct expression
*expr
, const char *value
)
840 /* This makes faking returns easier */
841 if (!value
|| value
[0] == '\0')
844 while (expr
->type
== EXPR_ASSIGNMENT
)
845 expr
= strip_expr(expr
->right
);
848 * Short cut: We only care about function pointers that are struct
852 if (expr
->fn
->type
== EXPR_SYMBOL
)
855 type
= get_type(expr
->fn
);
858 if (type
->type
== SYM_PTR
)
859 type
= get_real_base_type(type
);
861 if (strcmp(type_to_str(type
), value
) == 0)
867 static int db_compare_callback(void *_info
, int argc
, char **argv
, char **azColName
)
869 struct db_callback_info
*db_info
= _info
;
870 struct range_list
*var_rl
= db_info
->rl
;
871 struct range_list
*ret_range
;
873 char *ret_str
, *key
, *value
;
874 struct return_implies_callback
*tmp
;
882 return_id
= atoi(argv
[0]);
884 type
= atoi(argv
[2]);
885 param
= atoi(argv
[3]);
889 db_info
->has_states
= 1;
890 if (db_info
->prev_return_id
!= -1 && type
== INTERNAL
) {
891 set_other_side_state(db_info
);
892 set_implied_states(db_info
);
893 stree
= __pop_fake_cur_stree();
895 merge_fake_stree(&db_info
->stree
, stree
);
897 __push_fake_cur_stree();
900 db_info
->prev_return_id
= return_id
;
902 if (type
== INTERNAL
&& func_type_mismatch(db_info
->expr
, value
))
906 if (type
== CULL_PATH
) {
911 if (is_impossible_data(type
, db_info
->expr
, param
, key
, value
)) {
916 call_results_to_rl(db_info
->expr
, get_type(strip_expr(db_info
->expr
)), ret_str
, &ret_range
);
917 ret_range
= cast_rl(get_type(db_info
->expr
), ret_range
);
919 ret_range
= alloc_whole_rl(get_type(db_info
->expr
));
921 comparison
= db_info
->comparison
;
923 comparison
= flip_comparison(comparison
);
925 if (db_info
->true_side
) {
926 if (!possibly_true_rl(var_rl
, comparison
, ret_range
))
928 if (type
== PARAM_LIMIT
)
929 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
930 else if (type
> PARAM_LIMIT
)
931 set_implied_states(db_info
);
932 filter_by_comparison(&var_rl
, comparison
, ret_range
);
933 filter_by_comparison(&ret_range
, flip_comparison(comparison
), var_rl
);
935 if (!possibly_false_rl(var_rl
, comparison
, ret_range
))
937 if (type
== PARAM_LIMIT
)
938 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
939 else if (type
> PARAM_LIMIT
)
940 set_implied_states(db_info
);
941 filter_by_comparison(&var_rl
, negate_comparison(comparison
), ret_range
);
942 filter_by_comparison(&ret_range
, flip_comparison(negate_comparison(comparison
)), var_rl
);
945 handle_ret_equals_param(ret_str
, ret_range
, db_info
->expr
);
947 if (type
== INTERNAL
) {
948 set_state(-1, "unnull_path", NULL
, &true_state
);
949 __add_return_comparison(strip_expr(db_info
->expr
), ret_str
);
950 __add_return_to_param_mapping(db_info
->expr
, ret_str
);
951 store_return_state(db_info
, ret_str
, alloc_estate_rl(clone_rl(var_rl
)));
954 FOR_EACH_PTR(db_info
->callbacks
, tmp
) {
955 if (tmp
->type
== type
)
956 call_db_return_callback(tmp
, db_info
->expr
, param
, key
, value
);
957 } END_FOR_EACH_PTR(tmp
);
962 static void compare_db_return_states_callbacks(struct expression
*left
, int comparison
, struct expression
*right
, struct stree
*implied_true
, struct stree
*implied_false
)
964 struct stree
*orig_states
;
966 struct stree
*true_states
;
967 struct stree
*false_states
;
969 struct db_callback_info db_info
= {};
970 struct expression
*var_expr
;
971 struct expression
*call_expr
;
972 struct range_list
*rl
;
975 orig_states
= clone_stree(__get_cur_stree());
977 /* legacy cruft. need to fix call_implies_callbacks(). */
981 if (left
->type
!= EXPR_CALL
) {
987 get_absolute_rl(var_expr
, &rl
);
989 db_info
.comparison
= comparison
;
990 db_info
.expr
= call_expr
;
992 db_info
.left
= call_on_left
;
993 db_info
.callbacks
= db_return_states_list
;
994 db_info
.var_expr
= var_expr
;
996 call_return_states_before_hooks();
998 db_info
.true_side
= 1;
999 db_info
.stree
= NULL
;
1000 db_info
.prev_return_id
= -1;
1001 __push_fake_cur_stree();
1002 sql_select_return_states("return_id, return, type, parameter, key, value",
1003 call_expr
, db_compare_callback
, &db_info
);
1004 set_other_side_state(&db_info
);
1005 set_implied_states(&db_info
);
1006 stree
= __pop_fake_cur_stree();
1008 merge_fake_stree(&db_info
.stree
, stree
);
1010 true_states
= db_info
.stree
;
1011 if (!true_states
&& db_info
.has_states
) {
1012 __push_fake_cur_stree();
1013 set_path_impossible();
1014 true_states
= __pop_fake_cur_stree();
1019 FOR_EACH_SM(orig_states
, sm
) {
1020 __set_sm_cur_stree(sm
);
1021 } END_FOR_EACH_SM(sm
);
1023 db_info
.true_side
= 0;
1024 db_info
.stree
= NULL
;
1025 db_info
.prev_return_id
= -1;
1027 __push_fake_cur_stree();
1028 sql_select_return_states("return_id, return, type, parameter, key, value", call_expr
,
1029 db_compare_callback
, &db_info
);
1030 set_other_side_state(&db_info
);
1031 set_implied_states(&db_info
);
1032 stree
= __pop_fake_cur_stree();
1034 merge_fake_stree(&db_info
.stree
, stree
);
1036 false_states
= db_info
.stree
;
1037 if (!false_states
&& db_info
.has_states
) {
1038 __push_fake_cur_stree();
1039 set_path_impossible();
1040 false_states
= __pop_fake_cur_stree();
1045 FOR_EACH_SM(orig_states
, sm
) {
1046 __set_sm_cur_stree(sm
);
1047 } END_FOR_EACH_SM(sm
);
1049 free_stree(&orig_states
);
1051 FOR_EACH_SM(true_states
, sm
) {
1052 __set_true_false_sm(sm
, NULL
);
1053 } END_FOR_EACH_SM(sm
);
1054 FOR_EACH_SM(false_states
, sm
) {
1055 __set_true_false_sm(NULL
, sm
);
1056 } END_FOR_EACH_SM(sm
);
1058 free_stree(&true_states
);
1059 free_stree(&false_states
);
1061 call_return_states_after_hooks(call_expr
);
1063 FOR_EACH_SM(implied_true
, sm
) {
1064 __set_true_false_sm(sm
, NULL
);
1065 } END_FOR_EACH_SM(sm
);
1066 FOR_EACH_SM(implied_false
, sm
) {
1067 __set_true_false_sm(NULL
, sm
);
1068 } END_FOR_EACH_SM(sm
);
1071 void function_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
1073 struct expression
*var_expr
;
1074 struct expression
*call_expr
;
1075 struct stree
*implied_true
= NULL
;
1076 struct stree
*implied_false
= NULL
;
1077 struct range_list
*rl
;
1084 /* legacy cruft. need to fix call_implies_callbacks(). */
1088 if (left
->type
!= EXPR_CALL
) {
1094 get_absolute_rl(var_expr
, &rl
);
1096 if (rl_to_sval(rl
, &sval
))
1097 call_implies_callbacks(comparison
, call_expr
, sval
, call_on_left
, &implied_true
, &implied_false
);
1099 compare_db_return_states_callbacks(left
, comparison
, right
, implied_true
, implied_false
);
1100 free_stree(&implied_true
);
1101 free_stree(&implied_false
);
1104 static void call_ranged_return_hooks(struct db_callback_info
*db_info
)
1106 struct call_back_list
*call_backs
;
1107 struct range_list
*range_rl
;
1108 struct expression
*expr
;
1109 struct fcall_back
*tmp
;
1112 expr
= strip_expr(db_info
->expr
);
1113 while (expr
->type
== EXPR_ASSIGNMENT
)
1114 expr
= strip_expr(expr
->right
);
1115 if (expr
->type
!= EXPR_CALL
||
1116 expr
->fn
->type
!= EXPR_SYMBOL
)
1119 fn
= expr
->fn
->symbol_name
->name
;
1121 call_backs
= search_callback(func_hash
, fn
);
1122 FOR_EACH_PTR(call_backs
, tmp
) {
1123 if (tmp
->type
!= RANGED_CALL
)
1125 range_rl
= alloc_rl(tmp
->range
->min
, tmp
->range
->max
);
1126 range_rl
= cast_rl(estate_type(db_info
->ret_state
), range_rl
);
1127 if (possibly_true_rl(range_rl
, SPECIAL_EQUAL
, estate_rl(db_info
->ret_state
)))
1128 (tmp
->u
.ranged
)(fn
, expr
, db_info
->expr
, tmp
->info
);
1129 } END_FOR_EACH_PTR(tmp
);
1131 FOR_EACH_PTR(call_backs
, tmp
) {
1132 if (tmp
->type
!= RANGED_EXACT
)
1134 if (!estate_rl(db_info
->ret_state
))
1137 range_rl
= alloc_rl(tmp
->range
->min
, tmp
->range
->max
);
1138 range_rl
= cast_rl(estate_type(db_info
->ret_state
), range_rl
);
1141 * If there is an returned value out of range then this is not
1142 * an exact match. In other words, "0,4096-ptr_max" is not
1143 * necessarily a valid match.
1146 if (remove_range(estate_rl(db_info
->ret_state
),
1147 rl_min(range_rl
), rl_max(range_rl
)))
1149 (tmp
->u
.ranged
)(fn
, expr
, db_info
->expr
, tmp
->info
);
1150 } END_FOR_EACH_PTR(tmp
);
1153 static int db_assign_return_states_callback(void *_info
, int argc
, char **argv
, char **azColName
)
1155 struct db_callback_info
*db_info
= _info
;
1156 struct range_list
*ret_range
;
1158 char *ret_str
, *key
, *value
;
1159 struct return_implies_callback
*tmp
;
1160 struct stree
*stree
;
1166 return_id
= atoi(argv
[0]);
1168 type
= atoi(argv
[2]);
1169 param
= atoi(argv
[3]);
1173 if (db_info
->prev_return_id
!= -1 && type
== INTERNAL
) {
1174 call_ranged_return_hooks(db_info
);
1175 set_return_assign_state(db_info
);
1176 set_implied_states(db_info
);
1177 stree
= __pop_fake_cur_stree();
1179 merge_fake_stree(&db_info
->stree
, stree
);
1181 __push_fake_cur_stree();
1184 db_info
->prev_return_id
= return_id
;
1186 if (type
== INTERNAL
&& func_type_mismatch(db_info
->expr
, value
))
1190 if (type
== CULL_PATH
) {
1194 if (is_impossible_data(type
, db_info
->expr
, param
, key
, value
)) {
1199 if (type
== PARAM_LIMIT
)
1200 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
1201 else if (type
> PARAM_LIMIT
)
1202 set_implied_states(db_info
);
1204 db_info
->handled
= 1;
1205 call_results_to_rl(db_info
->expr
->right
, get_type(strip_expr(db_info
->expr
->right
)), ret_str
, &ret_range
);
1207 ret_range
= alloc_whole_rl(get_type(strip_expr(db_info
->expr
->right
)));
1208 ret_range
= cast_rl(get_type(db_info
->expr
->right
), ret_range
);
1210 if (type
== INTERNAL
) {
1211 set_state(-1, "unnull_path", NULL
, &true_state
);
1212 __add_return_comparison(strip_expr(db_info
->expr
->right
), ret_str
);
1213 __add_comparison_info(db_info
->expr
->left
, strip_expr(db_info
->expr
->right
), ret_str
);
1214 __add_return_to_param_mapping(db_info
->expr
, ret_str
);
1215 store_return_state(db_info
, ret_str
, alloc_estate_rl(ret_range
));
1216 set_fresh_mtag_returns(db_info
);
1219 FOR_EACH_PTR(db_return_states_list
, tmp
) {
1220 if (tmp
->type
== type
)
1221 call_db_return_callback(tmp
, db_info
->expr
, param
, key
, value
);
1222 } END_FOR_EACH_PTR(tmp
);
1227 static int db_return_states_assign(struct expression
*expr
)
1229 struct expression
*right
;
1230 struct sm_state
*sm
;
1231 struct stree
*stree
;
1232 struct db_callback_info db_info
= {};
1234 right
= strip_expr(expr
->right
);
1236 db_info
.prev_return_id
= -1;
1237 db_info
.expr
= expr
;
1238 db_info
.stree
= NULL
;
1239 db_info
.handled
= 0;
1241 call_return_states_before_hooks();
1243 __push_fake_cur_stree();
1244 sql_select_return_states("return_id, return, type, parameter, key, value",
1245 right
, db_assign_return_states_callback
, &db_info
);
1247 sm_msg("%s return_id %d return_ranges %s",
1248 db_info
.cull
? "culled" : "merging",
1249 db_info
.prev_return_id
,
1250 db_info
.ret_state
? db_info
.ret_state
->name
: "'<empty>'");
1252 if (db_info
.handled
)
1253 call_ranged_return_hooks(&db_info
);
1254 set_return_assign_state(&db_info
);
1255 set_implied_states(&db_info
);
1256 stree
= __pop_fake_cur_stree();
1258 merge_fake_stree(&db_info
.stree
, stree
);
1261 if (!db_info
.stree
&& db_info
.cull
) { /* this means we culled everything */
1262 set_extra_expr_mod(expr
->left
, alloc_estate_whole(get_type(expr
->left
)));
1263 set_path_impossible();
1265 FOR_EACH_SM(db_info
.stree
, sm
) {
1267 } END_FOR_EACH_SM(sm
);
1269 free_stree(&db_info
.stree
);
1270 call_return_states_after_hooks(right
);
1272 return db_info
.handled
;
1275 static int handle_implied_return(struct expression
*expr
)
1277 struct range_list
*rl
;
1279 if (!get_implied_return(expr
->right
, &rl
))
1281 rl
= cast_rl(get_type(expr
->left
), rl
);
1282 set_extra_expr_mod(expr
->left
, alloc_estate_rl(rl
));
1286 static void match_assign_call(struct expression
*expr
)
1288 struct call_back_list
*call_backs
;
1290 struct expression
*right
;
1292 struct range_list
*rl
;
1294 if (expr
->op
!= '=')
1297 right
= strip_expr(expr
->right
);
1298 if (right
->fn
->type
!= EXPR_SYMBOL
|| !right
->fn
->symbol
) {
1299 handled
|= db_return_states_assign(expr
);
1301 goto assigned_unknown
;
1304 if (is_fake_call(right
))
1307 fn
= right
->fn
->symbol
->ident
->name
;
1308 call_backs
= search_callback(func_hash
, (char *)fn
);
1311 * The ordering here is sort of important.
1312 * One example, of how this matters is that when we do:
1314 * len = strlen(str);
1316 * That is handled by smatch_common_functions.c and smatch_strlen.c.
1317 * They use implied_return and function_assign_hook respectively.
1318 * We want to get the implied return first before we do the function
1319 * assignment hook otherwise we end up writing the wrong thing for len
1320 * in smatch_extra.c because we assume that it already holds the
1321 * strlen() when we haven't set it yet.
1324 if (db_return_states_assign(expr
) == 1)
1327 handled
= assign_ranged_funcs(fn
, expr
, call_backs
);
1328 handled
|= handle_implied_return(expr
);
1331 call_call_backs(call_backs
, ASSIGN_CALL
, fn
, expr
);
1337 get_absolute_rl(expr
->right
, &rl
);
1338 rl
= cast_rl(get_type(expr
->left
), rl
);
1339 set_extra_expr_mod(expr
->left
, alloc_estate_rl(rl
));
1342 static int db_return_states_callback(void *_info
, int argc
, char **argv
, char **azColName
)
1344 struct db_callback_info
*db_info
= _info
;
1345 struct range_list
*ret_range
;
1347 char *ret_str
, *key
, *value
;
1348 struct return_implies_callback
*tmp
;
1349 struct stree
*stree
;
1356 return_id
= atoi(argv
[0]);
1358 type
= atoi(argv
[2]);
1359 param
= atoi(argv
[3]);
1363 if (db_info
->prev_return_id
!= -1 && type
== INTERNAL
) {
1364 call_ranged_return_hooks(db_info
);
1365 set_implied_states(db_info
);
1366 stree
= __pop_fake_cur_stree();
1368 merge_fake_stree(&db_info
->stree
, stree
);
1370 __push_fake_cur_stree();
1374 db_info
->prev_return_id
= return_id
;
1376 if (type
== INTERNAL
&& func_type_mismatch(db_info
->expr
, value
))
1380 if (type
== CULL_PATH
) {
1384 if (is_impossible_data(type
, db_info
->expr
, param
, key
, value
)) {
1389 if (type
== PARAM_LIMIT
)
1390 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
1391 else if (type
> PARAM_LIMIT
)
1392 set_implied_states(db_info
);
1394 call_results_to_rl(db_info
->expr
, get_type(strip_expr(db_info
->expr
)), ret_str
, &ret_range
);
1395 ret_range
= cast_rl(get_type(db_info
->expr
), ret_range
);
1397 if (type
== INTERNAL
) {
1398 struct smatch_state
*state
;
1400 set_state(-1, "unnull_path", NULL
, &true_state
);
1401 __add_return_comparison(strip_expr(db_info
->expr
), ret_str
);
1402 __add_return_to_param_mapping(db_info
->expr
, ret_str
);
1404 * We want to store the return values so that we can split the strees
1405 * in smatch_db.c. This uses set_state() directly because it's not a
1406 * real smatch_extra state.
1408 snprintf(buf
, sizeof(buf
), "return %p", db_info
->expr
);
1409 state
= alloc_estate_rl(ret_range
);
1410 set_state(SMATCH_EXTRA
, buf
, NULL
, state
);
1411 store_return_state(db_info
, ret_str
, state
);
1414 FOR_EACH_PTR(db_return_states_list
, tmp
) {
1415 if (tmp
->type
== type
)
1416 call_db_return_callback(tmp
, db_info
->expr
, param
, key
, value
);
1417 } END_FOR_EACH_PTR(tmp
);
1423 static void db_return_states(struct expression
*expr
)
1425 struct sm_state
*sm
;
1426 struct stree
*stree
;
1427 struct db_callback_info db_info
= {};
1429 if (!__get_cur_stree()) /* no return functions */
1432 db_info
.prev_return_id
= -1;
1433 db_info
.expr
= expr
;
1434 db_info
.stree
= NULL
;
1436 call_return_states_before_hooks();
1438 __push_fake_cur_stree();
1440 sql_select_return_states("return_id, return, type, parameter, key, value",
1441 expr
, db_return_states_callback
, &db_info
);
1442 call_ranged_return_hooks(&db_info
);
1443 set_implied_states(&db_info
);
1444 stree
= __pop_fake_cur_stree();
1446 merge_fake_stree(&db_info
.stree
, stree
);
1449 FOR_EACH_SM(db_info
.stree
, sm
) {
1451 } END_FOR_EACH_SM(sm
);
1453 free_stree(&db_info
.stree
);
1454 call_return_states_after_hooks(expr
);
1457 static int is_condition_call(struct expression
*expr
)
1459 struct expression
*tmp
;
1461 FOR_EACH_PTR_REVERSE(big_condition_stack
, tmp
) {
1462 if (expr
== tmp
|| expr_get_parent_expr(expr
) == tmp
)
1464 if (tmp
->pos
.line
< expr
->pos
.line
)
1466 } END_FOR_EACH_PTR_REVERSE(tmp
);
1471 static void db_return_states_call(struct expression
*expr
)
1476 if (is_assigned_call(expr
) || is_fake_assigned_call(expr
))
1478 if (is_condition_call(expr
))
1480 db_return_states(expr
);
1483 static void match_function_call(struct expression
*expr
)
1485 call_function_hooks(expr
, REGULAR_CALL
);
1486 db_return_states_call(expr
);
1489 static void match_macro_assign(struct expression
*expr
)
1491 struct call_back_list
*call_backs
;
1493 struct expression
*right
;
1495 right
= strip_expr(expr
->right
);
1496 macro
= get_macro_name(right
->pos
);
1497 call_backs
= search_callback(func_hash
, (char *)macro
);
1500 call_call_backs(call_backs
, MACRO_ASSIGN
, macro
, expr
);
1501 call_call_backs(call_backs
, MACRO_ASSIGN_EXTRA
, macro
, expr
);
1504 int get_implied_return(struct expression
*expr
, struct range_list
**rl
)
1506 struct call_back_list
*call_backs
;
1507 struct fcall_back
*tmp
;
1513 expr
= strip_expr(expr
);
1514 fn
= expr_to_var(expr
->fn
);
1518 call_backs
= search_callback(func_hash
, fn
);
1520 FOR_EACH_PTR(call_backs
, tmp
) {
1521 if (tmp
->type
== IMPLIED_RETURN
)
1522 handled
|= (tmp
->u
.implied_return
)(expr
, tmp
->info
, rl
);
1523 } END_FOR_EACH_PTR(tmp
);
1530 struct range_list
*get_range_implications(const char *fn
)
1532 struct call_back_list
*call_backs
;
1533 struct range_list
*ret
= NULL
;
1534 struct fcall_back
*tmp
;
1536 call_backs
= search_callback(func_hash
, (char *)fn
);
1538 FOR_EACH_PTR(call_backs
, tmp
) {
1539 if (tmp
->type
!= RANGED_CALL
&&
1540 tmp
->type
!= RANGED_EXACT
)
1542 add_ptr_list(&ret
, tmp
->range
);
1543 } END_FOR_EACH_PTR(tmp
);
1548 void create_function_hook_hash(void)
1550 func_hash
= create_function_hashtable(5000);
1553 void register_function_hooks(int id
)
1555 add_hook(&match_function_call
, CALL_HOOK_AFTER_INLINE
);
1556 add_hook(&match_assign_call
, CALL_ASSIGNMENT_HOOK
);
1557 add_hook(&match_macro_assign
, MACRO_ASSIGNMENT_HOOK
);