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 #define REGULAR_CALL 0
56 #define IMPLIED_RETURN 3
57 #define MACRO_ASSIGN 4
58 #define MACRO_ASSIGN_EXTRA 5
60 struct return_implies_callback
{
62 return_implies_hook
*callback
;
64 ALLOCATOR(return_implies_callback
, "return_implies callbacks");
65 DECLARE_PTR_LIST(db_implies_list
, struct return_implies_callback
);
66 static struct db_implies_list
*db_return_states_list
;
68 typedef void (void_fn
)(void);
69 DECLARE_PTR_LIST(void_fn_list
, void_fn
*);
70 static struct void_fn_list
*return_states_before
;
71 static struct void_fn_list
*return_states_after
;
73 static struct fcall_back
*alloc_fcall_back(int type
, void *call_back
,
76 struct fcall_back
*cb
;
78 cb
= __alloc_fcall_back(0);
80 cb
->u
.call_back
= call_back
;
85 void add_function_hook(const char *look_for
, func_hook
*call_back
, void *info
)
87 struct fcall_back
*cb
;
89 cb
= alloc_fcall_back(REGULAR_CALL
, call_back
, info
);
90 add_callback(func_hash
, look_for
, cb
);
93 void add_function_assign_hook(const char *look_for
, func_hook
*call_back
,
96 struct fcall_back
*cb
;
98 cb
= alloc_fcall_back(ASSIGN_CALL
, call_back
, info
);
99 add_callback(func_hash
, look_for
, cb
);
102 void add_implied_return_hook(const char *look_for
,
103 implied_return_hook
*call_back
,
106 struct fcall_back
*cb
;
108 cb
= alloc_fcall_back(IMPLIED_RETURN
, call_back
, info
);
109 add_callback(func_hash
, look_for
, cb
);
112 void add_macro_assign_hook(const char *look_for
, func_hook
*call_back
,
115 struct fcall_back
*cb
;
117 cb
= alloc_fcall_back(MACRO_ASSIGN
, call_back
, info
);
118 add_callback(func_hash
, look_for
, cb
);
121 void add_macro_assign_hook_extra(const char *look_for
, func_hook
*call_back
,
124 struct fcall_back
*cb
;
126 cb
= alloc_fcall_back(MACRO_ASSIGN_EXTRA
, call_back
, info
);
127 add_callback(func_hash
, look_for
, cb
);
130 void return_implies_state(const char *look_for
, long long start
, long long end
,
131 implication_hook
*call_back
, void *info
)
133 struct fcall_back
*cb
;
135 cb
= alloc_fcall_back(RANGED_CALL
, call_back
, info
);
136 cb
->range
= alloc_range_perm(ll_to_sval(start
), ll_to_sval(end
));
137 add_callback(func_hash
, look_for
, cb
);
140 void select_return_states_hook(int type
, return_implies_hook
*callback
)
142 struct return_implies_callback
*cb
= __alloc_return_implies_callback(0);
145 cb
->callback
= callback
;
146 add_ptr_list(&db_return_states_list
, cb
);
149 void select_return_states_before(void_fn
*fn
)
151 void_fn
**p
= malloc(sizeof(void_fn
*));
153 add_ptr_list(&return_states_before
, p
);
156 void select_return_states_after(void_fn
*fn
)
158 void_fn
**p
= malloc(sizeof(void_fn
*));
160 add_ptr_list(&return_states_after
, p
);
163 static void call_return_states_before_hooks(void)
167 FOR_EACH_PTR(return_states_before
, fn
) {
169 } END_FOR_EACH_PTR(fn
);
172 static void call_return_states_after_hooks(void)
176 FOR_EACH_PTR(return_states_after
, fn
) {
178 } END_FOR_EACH_PTR(fn
);
181 static int call_call_backs(struct call_back_list
*list
, int type
,
182 const char *fn
, struct expression
*expr
)
184 struct fcall_back
*tmp
;
187 FOR_EACH_PTR(list
, tmp
) {
188 if (tmp
->type
== type
) {
189 (tmp
->u
.call_back
)(fn
, expr
, tmp
->info
);
192 } END_FOR_EACH_PTR(tmp
);
197 static void call_ranged_call_backs(struct call_back_list
*list
,
198 const char *fn
, struct expression
*call_expr
,
199 struct expression
*assign_expr
)
201 struct fcall_back
*tmp
;
203 FOR_EACH_PTR(list
, tmp
) {
204 (tmp
->u
.ranged
)(fn
, call_expr
, assign_expr
, tmp
->info
);
205 } END_FOR_EACH_PTR(tmp
);
208 static struct call_back_list
*get_same_ranged_call_backs(struct call_back_list
*list
,
209 struct data_range
*drange
)
211 struct call_back_list
*ret
= NULL
;
212 struct fcall_back
*tmp
;
214 FOR_EACH_PTR(list
, tmp
) {
215 if (tmp
->type
!= RANGED_CALL
)
217 if (ranges_equiv(tmp
->range
, drange
))
218 add_ptr_list(&ret
, tmp
);
219 } END_FOR_EACH_PTR(tmp
);
223 static int in_list_exact_sval(struct range_list
*list
, struct data_range
*drange
)
225 struct data_range
*tmp
;
227 FOR_EACH_PTR(list
, tmp
) {
228 if (ranges_equiv(tmp
, drange
))
230 } END_FOR_EACH_PTR(tmp
);
234 static int assign_ranged_funcs(const char *fn
, struct expression
*expr
,
235 struct call_back_list
*call_backs
)
237 struct fcall_back
*tmp
;
241 struct smatch_state
*estate
;
242 struct stree
*tmp_stree
;
243 struct stree
*final_states
= NULL
;
244 struct range_list
*handled_ranges
= NULL
;
245 struct call_back_list
*same_range_call_backs
= NULL
;
251 var_name
= expr_to_var_sym(expr
->left
, &sym
);
252 if (!var_name
|| !sym
)
255 FOR_EACH_PTR(call_backs
, tmp
) {
256 if (tmp
->type
!= RANGED_CALL
)
259 if (in_list_exact_sval(handled_ranges
, tmp
->range
))
261 __push_fake_cur_stree();
262 tack_on(&handled_ranges
, tmp
->range
);
264 same_range_call_backs
= get_same_ranged_call_backs(call_backs
, tmp
->range
);
265 call_ranged_call_backs(same_range_call_backs
, fn
, expr
->right
, expr
);
266 __free_ptr_list((struct ptr_list
**)&same_range_call_backs
);
268 estate
= alloc_estate_range(tmp
->range
->min
, tmp
->range
->max
);
269 set_extra_mod(var_name
, sym
, estate
);
271 tmp_stree
= __pop_fake_cur_stree();
272 merge_fake_stree(&final_states
, tmp_stree
);
273 free_stree(&tmp_stree
);
275 } END_FOR_EACH_PTR(tmp
);
277 FOR_EACH_SM(final_states
, sm
) {
279 } END_FOR_EACH_SM(sm
);
281 free_stree(&final_states
);
283 free_string(var_name
);
287 static void call_implies_callbacks(int comparison
, struct expression
*expr
, sval_t sval
, int left
, struct stree
**implied_true
, struct stree
**implied_false
)
289 struct call_back_list
*call_backs
;
290 struct fcall_back
*tmp
;
292 struct data_range
*value_range
;
293 struct stree
*true_states
= NULL
;
294 struct stree
*false_states
= NULL
;
295 struct stree
*tmp_stree
;
297 *implied_true
= NULL
;
298 *implied_false
= NULL
;
299 if (expr
->fn
->type
!= EXPR_SYMBOL
|| !expr
->fn
->symbol
)
301 fn
= expr
->fn
->symbol
->ident
->name
;
302 call_backs
= search_callback(func_hash
, (char *)expr
->fn
->symbol
->ident
->name
);
305 value_range
= alloc_range(sval
, sval
);
307 /* set true states */
308 __push_fake_cur_stree();
309 FOR_EACH_PTR(call_backs
, tmp
) {
310 if (tmp
->type
!= RANGED_CALL
)
312 if (!true_comparison_range_LR(comparison
, tmp
->range
, value_range
, left
))
314 (tmp
->u
.ranged
)(fn
, expr
, NULL
, tmp
->info
);
315 } END_FOR_EACH_PTR(tmp
);
316 tmp_stree
= __pop_fake_cur_stree();
317 merge_fake_stree(&true_states
, tmp_stree
);
318 free_stree(&tmp_stree
);
320 /* set false states */
321 __push_fake_cur_stree();
322 FOR_EACH_PTR(call_backs
, tmp
) {
323 if (tmp
->type
!= RANGED_CALL
)
325 if (!false_comparison_range_LR(comparison
, tmp
->range
, value_range
, left
))
327 (tmp
->u
.ranged
)(fn
, expr
, NULL
, tmp
->info
);
328 } END_FOR_EACH_PTR(tmp
);
329 tmp_stree
= __pop_fake_cur_stree();
330 merge_fake_stree(&false_states
, tmp_stree
);
331 free_stree(&tmp_stree
);
333 *implied_true
= true_states
;
334 *implied_false
= false_states
;
337 struct db_callback_info
{
340 struct expression
*expr
;
341 struct range_list
*rl
;
344 struct db_implies_list
*callbacks
;
348 static void handle_ret_equals_param(char *ret_string
, struct range_list
*rl
, struct expression
*call
)
352 struct expression
*arg
;
353 struct range_list
*orig
;
355 str
= strstr(ret_string
, "==$");
359 param
= strtoll(str
, NULL
, 10);
360 arg
= get_argument_from_call_expr(call
->args
, param
);
363 get_absolute_rl(arg
, &orig
);
364 rl
= rl_intersection(orig
, rl
);
367 set_extra_expr_nomod(arg
, alloc_estate_rl(rl
));
370 static int db_compare_callback(void *_info
, int argc
, char **argv
, char **azColName
)
372 struct db_callback_info
*db_info
= _info
;
373 struct range_list
*ret_range
;
376 struct return_implies_callback
*tmp
;
384 return_id
= atoi(argv
[0]);
385 type
= atoi(argv
[2]);
386 param
= atoi(argv
[3]);
390 if (db_info
->prev_return_id
!= -1 && return_id
!= db_info
->prev_return_id
) {
391 stree
= __pop_fake_cur_stree();
392 merge_fake_stree(&db_info
->stree
, stree
);
394 __push_fake_cur_stree();
396 db_info
->prev_return_id
= return_id
;
398 call_results_to_rl(db_info
->expr
, get_type(strip_expr(db_info
->expr
)), argv
[1], &ret_range
);
399 ret_range
= cast_rl(get_type(db_info
->expr
), ret_range
);
401 ret_range
= alloc_whole_rl(get_type(db_info
->expr
));
403 comparison
= db_info
->comparison
;
405 comparison
= flip_comparison(comparison
);
407 if (db_info
->true_side
) {
408 if (!possibly_true_rl(ret_range
, comparison
, db_info
->rl
))
410 filter_by_comparison(&ret_range
, comparison
, db_info
->rl
);
412 if (!possibly_false_rl(ret_range
, comparison
, db_info
->rl
))
414 filter_by_comparison(&ret_range
, negate_comparison(comparison
), db_info
->rl
);
417 handle_ret_equals_param(argv
[1], ret_range
, db_info
->expr
);
419 FOR_EACH_PTR(db_info
->callbacks
, tmp
) {
420 if (tmp
->type
== type
)
421 tmp
->callback(db_info
->expr
, param
, key
, value
);
422 } END_FOR_EACH_PTR(tmp
);
426 static void compare_db_return_states_callbacks(int comparison
, struct expression
*expr
, sval_t sval
, int left
, struct stree
*implied_true
, struct stree
*implied_false
)
429 struct stree
*true_states
;
430 struct stree
*false_states
;
432 struct db_callback_info db_info
;
434 db_info
.comparison
= comparison
;
436 db_info
.rl
= alloc_rl(sval
, sval
);
438 db_info
.callbacks
= db_return_states_list
;
440 call_return_states_before_hooks();
442 db_info
.true_side
= 1;
443 db_info
.stree
= NULL
;
444 db_info
.prev_return_id
= -1;
445 __push_fake_cur_stree();
446 sql_select_return_states("return_id, return, type, parameter, key, value", expr
,
447 db_compare_callback
, &db_info
);
448 stree
= __pop_fake_cur_stree();
449 merge_fake_stree(&db_info
.stree
, stree
);
451 true_states
= db_info
.stree
;
453 db_info
.true_side
= 0;
454 db_info
.stree
= NULL
;
455 db_info
.prev_return_id
= -1;
456 __push_fake_cur_stree();
457 sql_select_return_states("return_id, return, type, parameter, key, value", expr
,
458 db_compare_callback
, &db_info
);
459 stree
= __pop_fake_cur_stree();
460 merge_fake_stree(&db_info
.stree
, stree
);
462 false_states
= db_info
.stree
;
464 FOR_EACH_SM(true_states
, sm
) {
465 __set_true_false_sm(sm
, NULL
);
466 } END_FOR_EACH_SM(sm
);
467 FOR_EACH_SM(false_states
, sm
) {
468 __set_true_false_sm(NULL
, sm
);
469 } END_FOR_EACH_SM(sm
);
471 free_stree(&true_states
);
472 free_stree(&false_states
);
474 call_return_states_after_hooks();
476 FOR_EACH_SM(implied_true
, sm
) {
477 __set_true_false_sm(sm
, NULL
);
478 } END_FOR_EACH_SM(sm
);
479 FOR_EACH_SM(implied_false
, sm
) {
480 __set_true_false_sm(NULL
, sm
);
481 } END_FOR_EACH_SM(sm
);
485 void function_comparison(int comparison
, struct expression
*expr
, sval_t sval
, int left
)
487 struct stree
*implied_true
, *implied_false
;
489 call_implies_callbacks(comparison
, expr
, sval
, left
, &implied_true
, &implied_false
);
490 compare_db_return_states_callbacks(comparison
, expr
, sval
, left
, implied_true
, implied_false
);
491 free_stree(&implied_true
);
492 free_stree(&implied_false
);
495 static int db_assign_return_states_callback(void *_info
, int argc
, char **argv
, char **azColName
)
497 struct db_callback_info
*db_info
= _info
;
498 struct range_list
*ret_range
;
501 struct return_implies_callback
*tmp
;
508 return_id
= atoi(argv
[0]);
509 type
= atoi(argv
[2]);
510 param
= atoi(argv
[3]);
514 if (db_info
->prev_return_id
!= -1 && return_id
!= db_info
->prev_return_id
) {
515 stree
= __pop_fake_cur_stree();
516 merge_fake_stree(&db_info
->stree
, stree
);
518 __push_fake_cur_stree();
520 db_info
->prev_return_id
= return_id
;
522 call_results_to_rl(db_info
->expr
->right
, get_type(strip_expr(db_info
->expr
->right
)), argv
[1], &ret_range
);
523 __add_comparison_info(db_info
->expr
->left
, strip_expr(db_info
->expr
->right
), argv
[1]);
525 ret_range
= alloc_whole_rl(get_type(strip_expr(db_info
->expr
->right
)));
526 ret_range
= cast_rl(get_type(db_info
->expr
->right
), ret_range
);
528 FOR_EACH_PTR(db_return_states_list
, tmp
) {
529 if (tmp
->type
== type
)
530 tmp
->callback(db_info
->expr
, param
, key
, value
);
531 } END_FOR_EACH_PTR(tmp
);
532 ret_range
= cast_rl(get_type(db_info
->expr
->left
), ret_range
);
533 set_extra_expr_mod(db_info
->expr
->left
, alloc_estate_rl(ret_range
));
538 static int db_return_states_assign(struct expression
*expr
)
540 struct expression
*right
;
544 struct db_callback_info db_info
;
546 right
= strip_expr(expr
->right
);
548 db_info
.prev_return_id
= -1;
550 db_info
.stree
= NULL
;
552 call_return_states_before_hooks();
554 __push_fake_cur_stree();
555 sql_select_return_states("return_id, return, type, parameter, key, value",
556 right
, db_assign_return_states_callback
, &db_info
);
557 stree
= __pop_fake_cur_stree();
558 merge_fake_stree(&db_info
.stree
, stree
);
561 FOR_EACH_SM(db_info
.stree
, sm
) {
564 } END_FOR_EACH_SM(sm
);
566 free_stree(&db_info
.stree
);
567 call_return_states_after_hooks();
572 static int handle_implied_return(struct expression
*expr
)
574 struct range_list
*rl
;
576 if (!get_implied_return(expr
->right
, &rl
))
578 rl
= cast_rl(get_type(expr
->left
), rl
);
579 set_extra_expr_mod(expr
->left
, alloc_estate_rl(rl
));
583 static void match_assign_call(struct expression
*expr
)
585 struct call_back_list
*call_backs
;
587 struct expression
*right
;
589 struct range_list
*rl
;
594 right
= strip_expr(expr
->right
);
595 if (right
->fn
->type
!= EXPR_SYMBOL
|| !right
->fn
->symbol
) {
596 handled
|= db_return_states_assign(expr
);
598 goto assigned_unknown
;
601 if (is_fake_call(right
)) {
602 if (!get_state_expr(SMATCH_EXTRA
, expr
->left
))
604 set_extra_expr_mod(expr
->left
, alloc_estate_whole(get_type(expr
->left
)));
608 fn
= right
->fn
->symbol
->ident
->name
;
611 * some of these conflict (they try to set smatch extra twice), so we
612 * call them in order from least important to most important.
615 call_backs
= search_callback(func_hash
, (char *)fn
);
616 call_call_backs(call_backs
, ASSIGN_CALL
, fn
, expr
);
618 handled
|= db_return_states_assign(expr
);
619 handled
|= assign_ranged_funcs(fn
, expr
, call_backs
);
620 handled
|= handle_implied_return(expr
);
626 get_absolute_rl(expr
->right
, &rl
);
627 rl
= cast_rl(get_type(expr
->left
), rl
);
628 set_extra_expr_mod(expr
->left
, alloc_estate_rl(rl
));
631 static int db_return_states_callback(void *_info
, int argc
, char **argv
, char **azColName
)
633 struct db_callback_info
*db_info
= _info
;
634 struct range_list
*ret_range
;
637 struct return_implies_callback
*tmp
;
645 return_id
= atoi(argv
[0]);
646 type
= atoi(argv
[2]);
647 param
= atoi(argv
[3]);
651 if (db_info
->prev_return_id
!= -1 && return_id
!= db_info
->prev_return_id
) {
652 stree
= __pop_fake_cur_stree();
653 merge_fake_stree(&db_info
->stree
, stree
);
655 __push_fake_cur_stree();
658 db_info
->prev_return_id
= return_id
;
660 call_results_to_rl(db_info
->expr
, get_type(strip_expr(db_info
->expr
)), argv
[1], &ret_range
);
661 ret_range
= cast_rl(get_type(db_info
->expr
), ret_range
);
663 FOR_EACH_PTR(db_return_states_list
, tmp
) {
664 if (tmp
->type
== type
)
665 tmp
->callback(db_info
->expr
, param
, key
, value
);
666 } END_FOR_EACH_PTR(tmp
);
669 * We want to store the return values so that we can split the strees
670 * in smatch_db.c. This uses set_state() directly because it's not a
671 * real smatch_extra state.
673 snprintf(buf
, sizeof(buf
), "return %p", db_info
->expr
);
674 set_state(SMATCH_EXTRA
, buf
, NULL
, alloc_estate_rl(ret_range
));
679 static void db_return_states(struct expression
*expr
)
683 struct db_callback_info db_info
;
685 if (!__get_cur_stree()) /* no return functions */
688 db_info
.prev_return_id
= -1;
690 db_info
.stree
= NULL
;
692 call_return_states_before_hooks();
694 __push_fake_cur_stree();
696 sql_select_return_states("return_id, return, type, parameter, key, value",
697 expr
, db_return_states_callback
, &db_info
);
698 stree
= __pop_fake_cur_stree();
699 merge_fake_stree(&db_info
.stree
, stree
);
702 FOR_EACH_SM(db_info
.stree
, sm
) {
704 } END_FOR_EACH_SM(sm
);
706 free_stree(&db_info
.stree
);
707 call_return_states_after_hooks();
710 static void db_return_states_call(struct expression
*expr
)
712 if (is_assigned_call(expr
))
714 db_return_states(expr
);
717 static void match_function_call(struct expression
*expr
)
719 struct call_back_list
*call_backs
;
721 if (expr
->fn
->type
== EXPR_SYMBOL
&& expr
->fn
->symbol
) {
722 call_backs
= search_callback(func_hash
, (char *)expr
->fn
->symbol
->ident
->name
);
724 call_call_backs(call_backs
, REGULAR_CALL
,
725 expr
->fn
->symbol
->ident
->name
, expr
);
727 db_return_states_call(expr
);
730 static void match_macro_assign(struct expression
*expr
)
732 struct call_back_list
*call_backs
;
734 struct expression
*right
;
736 right
= strip_expr(expr
->right
);
737 macro
= get_macro_name(right
->pos
);
738 call_backs
= search_callback(func_hash
, (char *)macro
);
741 call_call_backs(call_backs
, MACRO_ASSIGN
, macro
, expr
);
742 call_call_backs(call_backs
, MACRO_ASSIGN_EXTRA
, macro
, expr
);
745 int get_implied_return(struct expression
*expr
, struct range_list
**rl
)
747 struct call_back_list
*call_backs
;
748 struct fcall_back
*tmp
;
754 expr
= strip_expr(expr
);
755 fn
= expr_to_var(expr
->fn
);
759 call_backs
= search_callback(func_hash
, fn
);
761 FOR_EACH_PTR(call_backs
, tmp
) {
762 if (tmp
->type
== IMPLIED_RETURN
) {
763 (tmp
->u
.implied_return
)(expr
, tmp
->info
, rl
);
766 } END_FOR_EACH_PTR(tmp
);
773 void create_function_hook_hash(void)
775 func_hash
= create_function_hashtable(5000);
778 void register_function_hooks(int id
)
780 add_hook(&match_function_call
, CALL_HOOK_AFTER_INLINE
);
781 add_hook(&match_assign_call
, CALL_ASSIGNMENT_HOOK
);
782 add_hook(&match_macro_assign
, MACRO_ASSIGNMENT_HOOK
);