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
;
55 #define REGULAR_CALL 0
58 #define IMPLIED_RETURN 3
59 #define MACRO_ASSIGN 4
60 #define MACRO_ASSIGN_EXTRA 5
62 struct return_implies_callback
{
64 return_implies_hook
*callback
;
66 ALLOCATOR(return_implies_callback
, "return_implies callbacks");
67 DECLARE_PTR_LIST(db_implies_list
, struct return_implies_callback
);
68 static struct db_implies_list
*db_return_states_list
;
70 typedef void (void_fn
)(void);
71 DECLARE_PTR_LIST(void_fn_list
, void_fn
*);
72 static struct void_fn_list
*return_states_before
;
73 static struct void_fn_list
*return_states_after
;
75 static struct fcall_back
*alloc_fcall_back(int type
, void *call_back
,
78 struct fcall_back
*cb
;
80 cb
= __alloc_fcall_back(0);
82 cb
->u
.call_back
= call_back
;
87 void add_function_hook(const char *look_for
, func_hook
*call_back
, void *info
)
89 struct fcall_back
*cb
;
91 cb
= alloc_fcall_back(REGULAR_CALL
, call_back
, info
);
92 add_callback(func_hash
, look_for
, cb
);
95 void add_function_assign_hook(const char *look_for
, func_hook
*call_back
,
98 struct fcall_back
*cb
;
100 cb
= alloc_fcall_back(ASSIGN_CALL
, call_back
, info
);
101 add_callback(func_hash
, look_for
, cb
);
104 static void register_funcs_from_file_helper(const char *file
,
105 func_hook
*call_back
, void *info
,
112 snprintf(name
, sizeof(name
), "%s.%s", option_project_str
, file
);
113 token
= get_tokens_file(name
);
116 if (token_type(token
) != TOKEN_STREAMBEGIN
)
119 while (token_type(token
) != TOKEN_STREAMEND
) {
120 if (token_type(token
) != TOKEN_IDENT
)
122 func
= show_ident(token
->ident
);
124 add_function_assign_hook(func
, call_back
, info
);
126 add_function_hook(func
, call_back
, info
);
132 void register_func_hooks_from_file(const char *file
,
133 func_hook
*call_back
, void *info
)
135 register_funcs_from_file_helper(file
, call_back
, info
, false);
138 void register_assign_hooks_from_file(const char *file
,
139 func_hook
*call_back
, void *info
)
141 register_funcs_from_file_helper(file
, call_back
, info
, true);
144 void add_implied_return_hook(const char *look_for
,
145 implied_return_hook
*call_back
,
148 struct fcall_back
*cb
;
150 cb
= alloc_fcall_back(IMPLIED_RETURN
, call_back
, info
);
151 add_callback(func_hash
, look_for
, cb
);
154 void add_macro_assign_hook(const char *look_for
, func_hook
*call_back
,
157 struct fcall_back
*cb
;
159 cb
= alloc_fcall_back(MACRO_ASSIGN
, call_back
, info
);
160 add_callback(func_hash
, look_for
, cb
);
163 void add_macro_assign_hook_extra(const char *look_for
, func_hook
*call_back
,
166 struct fcall_back
*cb
;
168 cb
= alloc_fcall_back(MACRO_ASSIGN_EXTRA
, call_back
, info
);
169 add_callback(func_hash
, look_for
, cb
);
172 void return_implies_state(const char *look_for
, long long start
, long long end
,
173 implication_hook
*call_back
, void *info
)
175 struct fcall_back
*cb
;
177 cb
= alloc_fcall_back(RANGED_CALL
, call_back
, info
);
178 cb
->range
= alloc_range_perm(ll_to_sval(start
), ll_to_sval(end
));
179 add_callback(func_hash
, look_for
, cb
);
182 void return_implies_state_sval(const char *look_for
, sval_t start
, sval_t end
,
183 implication_hook
*call_back
, void *info
)
185 struct fcall_back
*cb
;
187 cb
= alloc_fcall_back(RANGED_CALL
, call_back
, info
);
188 cb
->range
= alloc_range_perm(start
, end
);
189 add_callback(func_hash
, look_for
, cb
);
192 void select_return_states_hook(int type
, return_implies_hook
*callback
)
194 struct return_implies_callback
*cb
= __alloc_return_implies_callback(0);
197 cb
->callback
= callback
;
198 add_ptr_list(&db_return_states_list
, cb
);
201 void select_return_states_before(void_fn
*fn
)
203 void_fn
**p
= malloc(sizeof(void_fn
*));
205 add_ptr_list(&return_states_before
, p
);
208 void select_return_states_after(void_fn
*fn
)
210 void_fn
**p
= malloc(sizeof(void_fn
*));
212 add_ptr_list(&return_states_after
, p
);
215 static void call_return_states_before_hooks(void)
219 FOR_EACH_PTR(return_states_before
, fn
) {
221 } END_FOR_EACH_PTR(fn
);
224 static void call_return_states_after_hooks(struct expression
*expr
)
228 FOR_EACH_PTR(return_states_after
, fn
) {
230 } END_FOR_EACH_PTR(fn
);
231 __pass_to_client(expr
, FUNCTION_CALL_HOOK_AFTER_DB
);
234 static int call_call_backs(struct call_back_list
*list
, int type
,
235 const char *fn
, struct expression
*expr
)
237 struct fcall_back
*tmp
;
240 FOR_EACH_PTR(list
, tmp
) {
241 if (tmp
->type
== type
) {
242 (tmp
->u
.call_back
)(fn
, expr
, tmp
->info
);
245 } END_FOR_EACH_PTR(tmp
);
250 static void call_ranged_call_backs(struct call_back_list
*list
,
251 const char *fn
, struct expression
*call_expr
,
252 struct expression
*assign_expr
)
254 struct fcall_back
*tmp
;
256 FOR_EACH_PTR(list
, tmp
) {
257 (tmp
->u
.ranged
)(fn
, call_expr
, assign_expr
, tmp
->info
);
258 } END_FOR_EACH_PTR(tmp
);
261 static struct call_back_list
*get_same_ranged_call_backs(struct call_back_list
*list
,
262 struct data_range
*drange
)
264 struct call_back_list
*ret
= NULL
;
265 struct fcall_back
*tmp
;
267 FOR_EACH_PTR(list
, tmp
) {
268 if (tmp
->type
!= RANGED_CALL
)
270 if (ranges_equiv(tmp
->range
, drange
))
271 add_ptr_list(&ret
, tmp
);
272 } END_FOR_EACH_PTR(tmp
);
276 static int in_list_exact_sval(struct range_list
*list
, struct data_range
*drange
)
278 struct data_range
*tmp
;
280 FOR_EACH_PTR(list
, tmp
) {
281 if (ranges_equiv(tmp
, drange
))
283 } END_FOR_EACH_PTR(tmp
);
287 static int assign_ranged_funcs(const char *fn
, struct expression
*expr
,
288 struct call_back_list
*call_backs
)
290 struct fcall_back
*tmp
;
294 struct smatch_state
*estate
;
295 struct stree
*tmp_stree
;
296 struct stree
*final_states
= NULL
;
297 struct range_list
*handled_ranges
= NULL
;
298 struct call_back_list
*same_range_call_backs
= NULL
;
299 struct range_list
*rl
;
305 var_name
= expr_to_var_sym(expr
->left
, &sym
);
306 if (!var_name
|| !sym
)
309 FOR_EACH_PTR(call_backs
, tmp
) {
310 if (tmp
->type
!= RANGED_CALL
)
313 if (in_list_exact_sval(handled_ranges
, tmp
->range
))
315 __push_fake_cur_stree();
316 tack_on(&handled_ranges
, tmp
->range
);
318 same_range_call_backs
= get_same_ranged_call_backs(call_backs
, tmp
->range
);
319 call_ranged_call_backs(same_range_call_backs
, fn
, expr
->right
, expr
);
320 __free_ptr_list((struct ptr_list
**)&same_range_call_backs
);
322 rl
= alloc_rl(tmp
->range
->min
, tmp
->range
->max
);
323 rl
= cast_rl(get_type(expr
->left
), rl
);
324 estate
= alloc_estate_rl(rl
);
325 set_extra_mod(var_name
, sym
, expr
->left
, estate
);
327 tmp_stree
= __pop_fake_cur_stree();
328 merge_fake_stree(&final_states
, tmp_stree
);
329 free_stree(&tmp_stree
);
331 } END_FOR_EACH_PTR(tmp
);
333 FOR_EACH_SM(final_states
, sm
) {
335 } END_FOR_EACH_SM(sm
);
337 free_stree(&final_states
);
339 free_string(var_name
);
343 static void call_implies_callbacks(int comparison
, struct expression
*expr
, sval_t sval
, int left
, struct stree
**implied_true
, struct stree
**implied_false
)
345 struct call_back_list
*call_backs
;
346 struct fcall_back
*tmp
;
348 struct data_range
*value_range
;
349 struct stree
*true_states
= NULL
;
350 struct stree
*false_states
= NULL
;
351 struct stree
*tmp_stree
;
353 *implied_true
= NULL
;
354 *implied_false
= NULL
;
355 if (expr
->fn
->type
!= EXPR_SYMBOL
|| !expr
->fn
->symbol
)
357 fn
= expr
->fn
->symbol
->ident
->name
;
358 call_backs
= search_callback(func_hash
, (char *)expr
->fn
->symbol
->ident
->name
);
361 value_range
= alloc_range(sval
, sval
);
363 /* set true states */
364 __push_fake_cur_stree();
365 FOR_EACH_PTR(call_backs
, tmp
) {
366 if (tmp
->type
!= RANGED_CALL
)
368 if (!true_comparison_range_LR(comparison
, tmp
->range
, value_range
, left
))
370 (tmp
->u
.ranged
)(fn
, expr
, NULL
, tmp
->info
);
371 } END_FOR_EACH_PTR(tmp
);
372 tmp_stree
= __pop_fake_cur_stree();
373 merge_fake_stree(&true_states
, tmp_stree
);
374 free_stree(&tmp_stree
);
376 /* set false states */
377 __push_fake_cur_stree();
378 FOR_EACH_PTR(call_backs
, tmp
) {
379 if (tmp
->type
!= RANGED_CALL
)
381 if (!false_comparison_range_LR(comparison
, tmp
->range
, value_range
, left
))
383 (tmp
->u
.ranged
)(fn
, expr
, NULL
, tmp
->info
);
384 } END_FOR_EACH_PTR(tmp
);
385 tmp_stree
= __pop_fake_cur_stree();
386 merge_fake_stree(&false_states
, tmp_stree
);
387 free_stree(&tmp_stree
);
389 *implied_true
= true_states
;
390 *implied_false
= false_states
;
393 struct db_callback_info
{
396 struct expression
*expr
;
397 struct range_list
*rl
;
400 struct stree
*implied
;
401 struct db_implies_list
*callbacks
;
406 struct smatch_state
*ret_state
;
407 struct expression
*var_expr
;
411 static void set_implied_states(struct db_callback_info
*db_info
)
415 FOR_EACH_SM(db_info
->implied
, sm
) {
417 } END_FOR_EACH_SM(sm
);
419 free_stree(&db_info
->implied
);
422 static void store_return_state(struct db_callback_info
*db_info
, const char *ret_str
, struct smatch_state
*state
)
424 db_info
->ret_str
= alloc_sname(ret_str
),
425 db_info
->ret_state
= state
;
428 static bool fake_a_param_assignment(struct expression
*expr
, const char *ret_str
, struct smatch_state
*orig
)
430 struct expression
*arg
, *left
, *right
, *tmp
, *fake_assign
;
436 if (expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
441 while (right
->type
== EXPR_ASSIGNMENT
)
442 right
= strip_expr(right
->right
);
443 if (!right
|| right
->type
!= EXPR_CALL
)
446 p
= strchr(ret_str
, '[');
451 if (p
[0] == '=' && p
[1] == '=')
456 snprintf(buf
, sizeof(buf
), "%s", p
);
460 param
= strtol(p
, &p
, 10);
467 arg
= get_argument_from_call_expr(right
->args
, param
);
471 /* There should be a get_other_name() function which returns an expr */
472 tmp
= get_assigned_expr(arg
);
477 * This is a sanity check to prevent side effects from evaluating stuff
480 str
= expr_to_chunk_sym_vsl(arg
, NULL
, NULL
);
485 right
= gen_expression_from_key(arg
, buf
);
486 if (!right
) /* Mostly fails for binops like [$0 + 4032] */
488 fake_assign
= assign_expression(left
, '=', right
);
489 __in_fake_parameter_assign
++;
490 __split_expr(fake_assign
);
491 __in_fake_parameter_assign
--;
494 * If the return is "0-65531[$0->nla_len - 4]" the faked expression
495 * is maybe (-4)-65531 but we know it is in the 0-65531 range so both
496 * parts have to be considered. We use _nomod() because it's not really
497 * another modification, it's just a clarification.
500 if (estate_rl(orig
)) {
501 struct smatch_state
*faked
;
502 struct range_list
*rl
;
504 faked
= get_extra_state(left
);
505 if (estate_rl(faked
)) {
506 rl
= rl_intersection(estate_rl(faked
), estate_rl(orig
));
508 set_extra_expr_nomod(expr
, alloc_estate_rl(rl
));
515 static void set_fresh_mtag_returns(struct db_callback_info
*db_info
)
517 struct expression
*expr
= db_info
->expr
->left
;
518 struct smatch_state
*state
;
520 if (!db_info
->ret_state
)
523 state
= alloc_estate_rl(cast_rl(get_type(expr
), clone_rl(estate_rl(db_info
->ret_state
))));
524 state
= get_mtag_return(db_info
->expr
, state
);
528 set_real_absolute(expr
, state
);
529 set_extra_expr_mod(expr
, state
);
531 db_info
->ret_state
= NULL
;
532 db_info
->ret_str
= NULL
;
535 static void set_return_assign_state(struct db_callback_info
*db_info
)
537 struct expression
*expr
= db_info
->expr
->left
;
538 struct smatch_state
*state
;
540 if (!db_info
->ret_state
)
543 state
= alloc_estate_rl(cast_rl(get_type(expr
), clone_rl(estate_rl(db_info
->ret_state
))));
544 if (!fake_a_param_assignment(db_info
->expr
, db_info
->ret_str
, state
))
545 set_extra_expr_mod(expr
, state
);
547 db_info
->ret_state
= NULL
;
548 db_info
->ret_str
= NULL
;
551 static void set_other_side_state(struct db_callback_info
*db_info
)
553 struct expression
*expr
= db_info
->var_expr
;
554 struct smatch_state
*state
;
556 if (!db_info
->ret_state
)
559 state
= alloc_estate_rl(cast_rl(get_type(expr
), clone_rl(estate_rl(db_info
->ret_state
))));
560 set_extra_expr_nomod(expr
, state
);
561 db_info
->ret_state
= NULL
;
562 db_info
->ret_str
= NULL
;
565 static void handle_ret_equals_param(char *ret_string
, struct range_list
*rl
, struct expression
*call
)
569 struct expression
*arg
;
570 struct range_list
*orig
;
572 str
= strstr(ret_string
, "==$");
576 param
= strtoll(str
, NULL
, 10);
577 arg
= get_argument_from_call_expr(call
->args
, param
);
580 get_absolute_rl(arg
, &orig
);
581 rl
= rl_intersection(orig
, rl
);
584 set_extra_expr_nomod(arg
, alloc_estate_rl(rl
));
587 static int impossible_limit(struct expression
*expr
, int param
, char *key
, char *value
)
589 struct expression
*arg
;
590 struct smatch_state
*state
;
591 struct range_list
*passed
;
592 struct range_list
*limit
;
593 struct symbol
*compare_type
;
595 while (expr
->type
== EXPR_ASSIGNMENT
)
596 expr
= strip_expr(expr
->right
);
597 if (expr
->type
!= EXPR_CALL
)
600 arg
= get_argument_from_call_expr(expr
->args
, param
);
604 if (strcmp(key
, "$") == 0) {
605 if (!get_implied_rl(arg
, &passed
))
608 compare_type
= get_arg_type(expr
->fn
, param
);
613 name
= get_variable_from_key(arg
, key
, &sym
);
617 state
= get_state(SMATCH_EXTRA
, name
, sym
);
622 passed
= estate_rl(state
);
623 if (!passed
|| is_whole_rl(passed
)) {
628 compare_type
= get_member_type_from_key(arg
, key
);
631 passed
= cast_rl(compare_type
, passed
);
632 call_results_to_rl(expr
, compare_type
, value
, &limit
);
633 if (!limit
|| is_whole_rl(limit
))
635 if (possibly_true_rl(passed
, SPECIAL_EQUAL
, limit
))
637 if (option_debug
|| local_debug
)
638 sm_msg("impossible: %d '%s' limit '%s' == '%s'", param
, key
, show_rl(passed
), value
);
642 static int is_impossible_data(int type
, struct expression
*expr
, int param
, char *key
, char *value
)
644 if (type
== PARAM_LIMIT
&& impossible_limit(expr
, param
, key
, value
))
646 if (type
== COMPARE_LIMIT
&& param_compare_limit_is_impossible(expr
, param
, key
, value
)) {
648 sm_msg("param_compare_limit_is_impossible: %d %s %s", param
, key
, value
);
654 static int func_type_mismatch(struct expression
*expr
, const char *value
)
658 /* This makes faking returns easier */
659 if (!value
|| value
[0] == '\0')
662 while (expr
->type
== EXPR_ASSIGNMENT
)
663 expr
= strip_expr(expr
->right
);
666 * Short cut: We only care about function pointers that are struct
670 if (expr
->fn
->type
== EXPR_SYMBOL
)
673 type
= get_type(expr
->fn
);
676 if (type
->type
== SYM_PTR
)
677 type
= get_real_base_type(type
);
679 if (strcmp(type_to_str(type
), value
) == 0)
685 static int db_compare_callback(void *_info
, int argc
, char **argv
, char **azColName
)
687 struct db_callback_info
*db_info
= _info
;
688 struct range_list
*var_rl
= db_info
->rl
;
689 struct range_list
*ret_range
;
691 char *ret_str
, *key
, *value
;
692 struct return_implies_callback
*tmp
;
700 return_id
= atoi(argv
[0]);
702 type
= atoi(argv
[2]);
703 param
= atoi(argv
[3]);
707 db_info
->has_states
= 1;
708 if (db_info
->prev_return_id
!= -1 && type
== INTERNAL
) {
709 set_other_side_state(db_info
);
710 set_implied_states(db_info
);
711 stree
= __pop_fake_cur_stree();
713 merge_fake_stree(&db_info
->stree
, stree
);
715 __push_fake_cur_stree();
718 db_info
->prev_return_id
= return_id
;
720 if (type
== INTERNAL
&& func_type_mismatch(db_info
->expr
, value
))
724 if (type
== CULL_PATH
) {
729 if (is_impossible_data(type
, db_info
->expr
, param
, key
, value
)) {
734 call_results_to_rl(db_info
->expr
, get_type(strip_expr(db_info
->expr
)), ret_str
, &ret_range
);
735 ret_range
= cast_rl(get_type(db_info
->expr
), ret_range
);
737 ret_range
= alloc_whole_rl(get_type(db_info
->expr
));
739 comparison
= db_info
->comparison
;
741 comparison
= flip_comparison(comparison
);
743 if (db_info
->true_side
) {
744 if (!possibly_true_rl(var_rl
, comparison
, ret_range
))
746 if (type
== PARAM_LIMIT
)
747 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
748 filter_by_comparison(&var_rl
, comparison
, ret_range
);
749 filter_by_comparison(&ret_range
, flip_comparison(comparison
), var_rl
);
751 if (!possibly_false_rl(var_rl
, comparison
, ret_range
))
753 if (type
== PARAM_LIMIT
)
754 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
755 filter_by_comparison(&var_rl
, negate_comparison(comparison
), ret_range
);
756 filter_by_comparison(&ret_range
, flip_comparison(negate_comparison(comparison
)), var_rl
);
759 handle_ret_equals_param(ret_str
, ret_range
, db_info
->expr
);
761 if (type
== INTERNAL
) {
762 set_state(-1, "unnull_path", NULL
, &true_state
);
763 __add_return_comparison(strip_expr(db_info
->expr
), ret_str
);
764 __add_return_to_param_mapping(db_info
->expr
, ret_str
);
765 store_return_state(db_info
, ret_str
, alloc_estate_rl(clone_rl(var_rl
)));
768 FOR_EACH_PTR(db_info
->callbacks
, tmp
) {
769 if (tmp
->type
== type
)
770 tmp
->callback(db_info
->expr
, param
, key
, value
);
771 } END_FOR_EACH_PTR(tmp
);
776 static void compare_db_return_states_callbacks(struct expression
*left
, int comparison
, struct expression
*right
, struct stree
*implied_true
, struct stree
*implied_false
)
778 struct stree
*orig_states
;
780 struct stree
*true_states
;
781 struct stree
*false_states
;
783 struct db_callback_info db_info
= {};
784 struct expression
*var_expr
;
785 struct expression
*call_expr
;
786 struct range_list
*rl
;
789 orig_states
= clone_stree(__get_cur_stree());
791 /* legacy cruft. need to fix call_implies_callbacks(). */
795 if (left
->type
!= EXPR_CALL
) {
801 get_absolute_rl(var_expr
, &rl
);
803 db_info
.comparison
= comparison
;
804 db_info
.expr
= call_expr
;
806 db_info
.left
= call_on_left
;
807 db_info
.callbacks
= db_return_states_list
;
808 db_info
.var_expr
= var_expr
;
810 call_return_states_before_hooks();
812 db_info
.true_side
= 1;
813 db_info
.stree
= NULL
;
814 db_info
.prev_return_id
= -1;
815 __push_fake_cur_stree();
816 sql_select_return_states("return_id, return, type, parameter, key, value",
817 call_expr
, db_compare_callback
, &db_info
);
818 set_other_side_state(&db_info
);
819 set_implied_states(&db_info
);
820 stree
= __pop_fake_cur_stree();
822 merge_fake_stree(&db_info
.stree
, stree
);
824 true_states
= db_info
.stree
;
825 if (!true_states
&& db_info
.has_states
) {
826 __push_fake_cur_stree();
827 set_path_impossible();
828 true_states
= __pop_fake_cur_stree();
833 FOR_EACH_SM(orig_states
, sm
) {
834 __set_sm_cur_stree(sm
);
835 } END_FOR_EACH_SM(sm
);
837 db_info
.true_side
= 0;
838 db_info
.stree
= NULL
;
839 db_info
.prev_return_id
= -1;
841 __push_fake_cur_stree();
842 sql_select_return_states("return_id, return, type, parameter, key, value", call_expr
,
843 db_compare_callback
, &db_info
);
844 set_other_side_state(&db_info
);
845 set_implied_states(&db_info
);
846 stree
= __pop_fake_cur_stree();
848 merge_fake_stree(&db_info
.stree
, stree
);
850 false_states
= db_info
.stree
;
851 if (!false_states
&& db_info
.has_states
) {
852 __push_fake_cur_stree();
853 set_path_impossible();
854 false_states
= __pop_fake_cur_stree();
859 FOR_EACH_SM(orig_states
, sm
) {
860 __set_sm_cur_stree(sm
);
861 } END_FOR_EACH_SM(sm
);
863 free_stree(&orig_states
);
865 FOR_EACH_SM(true_states
, sm
) {
866 __set_true_false_sm(sm
, NULL
);
867 } END_FOR_EACH_SM(sm
);
868 FOR_EACH_SM(false_states
, sm
) {
869 __set_true_false_sm(NULL
, sm
);
870 } END_FOR_EACH_SM(sm
);
872 free_stree(&true_states
);
873 free_stree(&false_states
);
875 call_return_states_after_hooks(call_expr
);
877 FOR_EACH_SM(implied_true
, sm
) {
878 __set_true_false_sm(sm
, NULL
);
879 } END_FOR_EACH_SM(sm
);
880 FOR_EACH_SM(implied_false
, sm
) {
881 __set_true_false_sm(NULL
, sm
);
882 } END_FOR_EACH_SM(sm
);
885 void function_comparison(struct expression
*left
, int comparison
, struct expression
*right
)
887 struct expression
*var_expr
;
888 struct expression
*call_expr
;
889 struct stree
*implied_true
= NULL
;
890 struct stree
*implied_false
= NULL
;
891 struct range_list
*rl
;
898 /* legacy cruft. need to fix call_implies_callbacks(). */
902 if (left
->type
!= EXPR_CALL
) {
908 get_absolute_rl(var_expr
, &rl
);
910 if (rl_to_sval(rl
, &sval
))
911 call_implies_callbacks(comparison
, call_expr
, sval
, call_on_left
, &implied_true
, &implied_false
);
913 compare_db_return_states_callbacks(left
, comparison
, right
, implied_true
, implied_false
);
914 free_stree(&implied_true
);
915 free_stree(&implied_false
);
918 static void call_ranged_return_hooks(struct db_callback_info
*db_info
)
920 struct call_back_list
*call_backs
;
921 struct expression
*expr
;
922 struct fcall_back
*tmp
;
925 expr
= strip_expr(db_info
->expr
);
926 while (expr
->type
== EXPR_ASSIGNMENT
)
927 expr
= strip_expr(expr
->right
);
928 if (expr
->type
!= EXPR_CALL
||
929 expr
->fn
->type
!= EXPR_SYMBOL
)
932 fn
= expr
->fn
->symbol_name
->name
;
934 call_backs
= search_callback(func_hash
, fn
);
935 FOR_EACH_PTR(call_backs
, tmp
) {
936 struct range_list
*range_rl
;
938 if (tmp
->type
!= RANGED_CALL
)
940 range_rl
= alloc_rl(tmp
->range
->min
, tmp
->range
->max
);
941 range_rl
= cast_rl(estate_type(db_info
->ret_state
), range_rl
);
942 if (possibly_true_rl(range_rl
, SPECIAL_EQUAL
, estate_rl(db_info
->ret_state
)))
943 (tmp
->u
.ranged
)(fn
, expr
, db_info
->expr
, tmp
->info
);
944 } END_FOR_EACH_PTR(tmp
);
947 static int db_assign_return_states_callback(void *_info
, int argc
, char **argv
, char **azColName
)
949 struct db_callback_info
*db_info
= _info
;
950 struct range_list
*ret_range
;
952 char *ret_str
, *key
, *value
;
953 struct return_implies_callback
*tmp
;
960 return_id
= atoi(argv
[0]);
962 type
= atoi(argv
[2]);
963 param
= atoi(argv
[3]);
967 if (db_info
->prev_return_id
!= -1 && type
== INTERNAL
) {
968 call_ranged_return_hooks(db_info
);
969 set_return_assign_state(db_info
);
970 set_implied_states(db_info
);
971 stree
= __pop_fake_cur_stree();
973 merge_fake_stree(&db_info
->stree
, stree
);
975 __push_fake_cur_stree();
978 db_info
->prev_return_id
= return_id
;
980 if (type
== INTERNAL
&& func_type_mismatch(db_info
->expr
, value
))
984 if (type
== CULL_PATH
) {
988 if (is_impossible_data(type
, db_info
->expr
, param
, key
, value
)) {
993 if (type
== PARAM_LIMIT
)
994 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
996 db_info
->handled
= 1;
997 call_results_to_rl(db_info
->expr
->right
, get_type(strip_expr(db_info
->expr
->right
)), ret_str
, &ret_range
);
999 ret_range
= alloc_whole_rl(get_type(strip_expr(db_info
->expr
->right
)));
1000 ret_range
= cast_rl(get_type(db_info
->expr
->right
), ret_range
);
1002 if (type
== INTERNAL
) {
1003 set_state(-1, "unnull_path", NULL
, &true_state
);
1004 __add_return_comparison(strip_expr(db_info
->expr
->right
), ret_str
);
1005 __add_comparison_info(db_info
->expr
->left
, strip_expr(db_info
->expr
->right
), ret_str
);
1006 __add_return_to_param_mapping(db_info
->expr
, ret_str
);
1007 store_return_state(db_info
, ret_str
, alloc_estate_rl(ret_range
));
1008 set_fresh_mtag_returns(db_info
);
1011 FOR_EACH_PTR(db_return_states_list
, tmp
) {
1012 if (tmp
->type
== type
)
1013 tmp
->callback(db_info
->expr
, param
, key
, value
);
1014 } END_FOR_EACH_PTR(tmp
);
1019 static int db_return_states_assign(struct expression
*expr
)
1021 struct expression
*right
;
1022 struct sm_state
*sm
;
1023 struct stree
*stree
;
1024 struct db_callback_info db_info
= {};
1026 right
= strip_expr(expr
->right
);
1028 db_info
.prev_return_id
= -1;
1029 db_info
.expr
= expr
;
1030 db_info
.stree
= NULL
;
1031 db_info
.handled
= 0;
1033 call_return_states_before_hooks();
1035 __push_fake_cur_stree();
1036 sql_select_return_states("return_id, return, type, parameter, key, value",
1037 right
, db_assign_return_states_callback
, &db_info
);
1039 sm_msg("%s return_id %d return_ranges %s",
1040 db_info
.cull
? "culled" : "merging",
1041 db_info
.prev_return_id
,
1042 db_info
.ret_state
? db_info
.ret_state
->name
: "'<empty>'");
1044 if (db_info
.handled
)
1045 call_ranged_return_hooks(&db_info
);
1046 set_return_assign_state(&db_info
);
1047 set_implied_states(&db_info
);
1048 stree
= __pop_fake_cur_stree();
1050 merge_fake_stree(&db_info
.stree
, stree
);
1053 if (!db_info
.stree
&& db_info
.cull
) { /* this means we culled everything */
1054 set_extra_expr_mod(expr
->left
, alloc_estate_whole(get_type(expr
->left
)));
1055 set_path_impossible();
1057 FOR_EACH_SM(db_info
.stree
, sm
) {
1059 } END_FOR_EACH_SM(sm
);
1061 free_stree(&db_info
.stree
);
1062 call_return_states_after_hooks(right
);
1064 return db_info
.handled
;
1067 static int handle_implied_return(struct expression
*expr
)
1069 struct range_list
*rl
;
1071 if (!get_implied_return(expr
->right
, &rl
))
1073 rl
= cast_rl(get_type(expr
->left
), rl
);
1074 set_extra_expr_mod(expr
->left
, alloc_estate_rl(rl
));
1078 static void match_assign_call(struct expression
*expr
)
1080 struct call_back_list
*call_backs
;
1082 struct expression
*right
;
1084 struct range_list
*rl
;
1086 if (expr
->op
!= '=')
1089 right
= strip_expr(expr
->right
);
1090 if (right
->fn
->type
!= EXPR_SYMBOL
|| !right
->fn
->symbol
) {
1091 handled
|= db_return_states_assign(expr
);
1093 goto assigned_unknown
;
1096 if (is_fake_call(right
)) {
1097 set_extra_expr_mod(expr
->left
, alloc_estate_whole(get_type(expr
->left
)));
1101 fn
= right
->fn
->symbol
->ident
->name
;
1102 call_backs
= search_callback(func_hash
, (char *)fn
);
1105 * The ordering here is sort of important.
1106 * One example, of how this matters is that when we do:
1108 * len = strlen(str);
1110 * That is handled by smatch_common_functions.c and smatch_strlen.c.
1111 * They use implied_return and function_assign_hook respectively.
1112 * We want to get the implied return first before we do the function
1113 * assignment hook otherwise we end up writing the wrong thing for len
1114 * in smatch_extra.c because we assume that it already holds the
1115 * strlen() when we haven't set it yet.
1118 if (db_return_states_assign(expr
) == 1)
1121 handled
= assign_ranged_funcs(fn
, expr
, call_backs
);
1122 handled
|= handle_implied_return(expr
);
1125 call_call_backs(call_backs
, ASSIGN_CALL
, fn
, expr
);
1131 get_absolute_rl(expr
->right
, &rl
);
1132 rl
= cast_rl(get_type(expr
->left
), rl
);
1133 set_extra_expr_mod(expr
->left
, alloc_estate_rl(rl
));
1136 static int db_return_states_callback(void *_info
, int argc
, char **argv
, char **azColName
)
1138 struct db_callback_info
*db_info
= _info
;
1139 struct range_list
*ret_range
;
1141 char *ret_str
, *key
, *value
;
1142 struct return_implies_callback
*tmp
;
1143 struct stree
*stree
;
1150 return_id
= atoi(argv
[0]);
1152 type
= atoi(argv
[2]);
1153 param
= atoi(argv
[3]);
1157 if (db_info
->prev_return_id
!= -1 && type
== INTERNAL
) {
1158 call_ranged_return_hooks(db_info
);
1159 set_implied_states(db_info
);
1160 stree
= __pop_fake_cur_stree();
1162 merge_fake_stree(&db_info
->stree
, stree
);
1164 __push_fake_cur_stree();
1168 db_info
->prev_return_id
= return_id
;
1170 if (type
== INTERNAL
&& func_type_mismatch(db_info
->expr
, value
))
1174 if (type
== CULL_PATH
) {
1178 if (is_impossible_data(type
, db_info
->expr
, param
, key
, value
)) {
1183 if (type
== PARAM_LIMIT
)
1184 param_limit_implications(db_info
->expr
, param
, key
, value
, &db_info
->implied
);
1186 call_results_to_rl(db_info
->expr
, get_type(strip_expr(db_info
->expr
)), ret_str
, &ret_range
);
1187 ret_range
= cast_rl(get_type(db_info
->expr
), ret_range
);
1189 if (type
== INTERNAL
) {
1190 struct smatch_state
*state
;
1192 set_state(-1, "unnull_path", NULL
, &true_state
);
1193 __add_return_comparison(strip_expr(db_info
->expr
), ret_str
);
1194 __add_return_to_param_mapping(db_info
->expr
, ret_str
);
1196 * We want to store the return values so that we can split the strees
1197 * in smatch_db.c. This uses set_state() directly because it's not a
1198 * real smatch_extra state.
1200 snprintf(buf
, sizeof(buf
), "return %p", db_info
->expr
);
1201 state
= alloc_estate_rl(ret_range
);
1202 set_state(SMATCH_EXTRA
, buf
, NULL
, state
);
1203 store_return_state(db_info
, ret_str
, state
);
1206 FOR_EACH_PTR(db_return_states_list
, tmp
) {
1207 if (tmp
->type
== type
)
1208 tmp
->callback(db_info
->expr
, param
, key
, value
);
1209 } END_FOR_EACH_PTR(tmp
);
1215 static void db_return_states(struct expression
*expr
)
1217 struct sm_state
*sm
;
1218 struct stree
*stree
;
1219 struct db_callback_info db_info
= {};
1221 if (!__get_cur_stree()) /* no return functions */
1224 db_info
.prev_return_id
= -1;
1225 db_info
.expr
= expr
;
1226 db_info
.stree
= NULL
;
1228 call_return_states_before_hooks();
1230 __push_fake_cur_stree();
1232 sql_select_return_states("return_id, return, type, parameter, key, value",
1233 expr
, db_return_states_callback
, &db_info
);
1234 call_ranged_return_hooks(&db_info
);
1235 set_implied_states(&db_info
);
1236 stree
= __pop_fake_cur_stree();
1238 merge_fake_stree(&db_info
.stree
, stree
);
1241 FOR_EACH_SM(db_info
.stree
, sm
) {
1243 } END_FOR_EACH_SM(sm
);
1245 free_stree(&db_info
.stree
);
1246 call_return_states_after_hooks(expr
);
1249 static int is_condition_call(struct expression
*expr
)
1251 struct expression
*tmp
;
1253 FOR_EACH_PTR_REVERSE(big_condition_stack
, tmp
) {
1254 if (expr
== tmp
|| expr_get_parent_expr(expr
) == tmp
)
1256 if (tmp
->pos
.line
< expr
->pos
.line
)
1258 } END_FOR_EACH_PTR_REVERSE(tmp
);
1263 static void db_return_states_call(struct expression
*expr
)
1268 if (is_assigned_call(expr
) || is_fake_assigned_call(expr
))
1270 if (is_condition_call(expr
))
1272 db_return_states(expr
);
1275 static void match_function_call(struct expression
*expr
)
1277 struct call_back_list
*call_backs
;
1278 struct expression
*fn
;
1280 fn
= strip_expr(expr
->fn
);
1281 if (fn
->type
== EXPR_SYMBOL
&& fn
->symbol
) {
1282 call_backs
= search_callback(func_hash
, (char *)fn
->symbol
->ident
->name
);
1284 call_call_backs(call_backs
, REGULAR_CALL
,
1285 fn
->symbol
->ident
->name
, expr
);
1287 db_return_states_call(expr
);
1290 static void match_macro_assign(struct expression
*expr
)
1292 struct call_back_list
*call_backs
;
1294 struct expression
*right
;
1296 right
= strip_expr(expr
->right
);
1297 macro
= get_macro_name(right
->pos
);
1298 call_backs
= search_callback(func_hash
, (char *)macro
);
1301 call_call_backs(call_backs
, MACRO_ASSIGN
, macro
, expr
);
1302 call_call_backs(call_backs
, MACRO_ASSIGN_EXTRA
, macro
, expr
);
1305 int get_implied_return(struct expression
*expr
, struct range_list
**rl
)
1307 struct call_back_list
*call_backs
;
1308 struct fcall_back
*tmp
;
1314 expr
= strip_expr(expr
);
1315 fn
= expr_to_var(expr
->fn
);
1319 call_backs
= search_callback(func_hash
, fn
);
1321 FOR_EACH_PTR(call_backs
, tmp
) {
1322 if (tmp
->type
== IMPLIED_RETURN
)
1323 handled
|= (tmp
->u
.implied_return
)(expr
, tmp
->info
, rl
);
1324 } END_FOR_EACH_PTR(tmp
);
1331 struct range_list
*get_range_implications(const char *fn
)
1333 struct call_back_list
*call_backs
;
1334 struct range_list
*ret
= NULL
;
1335 struct fcall_back
*tmp
;
1337 call_backs
= search_callback(func_hash
, (char *)fn
);
1339 FOR_EACH_PTR(call_backs
, tmp
) {
1340 if (tmp
->type
!= RANGED_CALL
)
1342 add_ptr_list(&ret
, tmp
->range
);
1343 } END_FOR_EACH_PTR(tmp
);
1348 void create_function_hook_hash(void)
1350 func_hash
= create_function_hashtable(5000);
1353 void register_function_hooks(int id
)
1355 add_hook(&match_function_call
, CALL_HOOK_AFTER_INLINE
);
1356 add_hook(&match_assign_call
, CALL_ASSIGNMENT_HOOK
);
1357 add_hook(&match_macro_assign
, MACRO_ASSIGNMENT_HOOK
);