1 /*
2 * Copyright (C) 2009 Dan Carpenter.
3 *
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.
8 *
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.
13 *
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
16 */
17
18 /*
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.
26 *
27 */
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include "smatch.h"
32 #include "smatch_slist.h"
33 #include "smatch_extra.h"
34 #include "smatch_function_hashtable.h"
35
36 struct fcall_back {
37 int type;
38 struct data_range *range;
39 union {
40 func_hook *call_back;
41 implication_hook *ranged;
42 implied_return_hook *implied_return;
43 } u;
44 void *info;
45 };
46
47 ALLOCATOR(fcall_back, "call backs");
48 DECLARE_PTR_LIST(call_back_list, struct fcall_back);
49
50 DEFINE_FUNCTION_HASHTABLE_STATIC(callback, struct fcall_back, struct call_back_list);
51 static struct hashtable *func_hash;
52
53 int __in_fake_parameter_assign;
54
55 #define REGULAR_CALL 0
56 #define RANGED_CALL 1
57 #define ASSIGN_CALL 2
58 #define IMPLIED_RETURN 3
59 #define MACRO_ASSIGN 4
60 #define MACRO_ASSIGN_EXTRA 5
61
62 struct return_implies_callback {
63 int type;
64 return_implies_hook *callback;
65 };
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;
69
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;
74
75 static struct fcall_back *alloc_fcall_back(int type, void *call_back,
76 void *info)
77 {
78 struct fcall_back *cb;
79
80 cb = __alloc_fcall_back(0);
81 cb->type = type;
82 cb->u.call_back = call_back;
83 cb->info = info;
84 return cb;
85 }
86
87 void add_function_hook(const char *look_for, func_hook *call_back, void *info)
88 {
89 struct fcall_back *cb;
90
91 cb = alloc_fcall_back(REGULAR_CALL, call_back, info);
92 add_callback(func_hash, look_for, cb);
93 }
94
95 void add_function_assign_hook(const char *look_for, func_hook *call_back,
96 void *info)
97 {
98 struct fcall_back *cb;
99
100 cb = alloc_fcall_back(ASSIGN_CALL, call_back, info);
101 add_callback(func_hash, look_for, cb);
102 }
103
104 void add_implied_return_hook(const char *look_for,
105 implied_return_hook *call_back,
106 void *info)
107 {
108 struct fcall_back *cb;
109
110 cb = alloc_fcall_back(IMPLIED_RETURN, call_back, info);
111 add_callback(func_hash, look_for, cb);
112 }
113
114 void add_macro_assign_hook(const char *look_for, func_hook *call_back,
115 void *info)
116 {
117 struct fcall_back *cb;
118
119 cb = alloc_fcall_back(MACRO_ASSIGN, call_back, info);
120 add_callback(func_hash, look_for, cb);
121 }
122
123 void add_macro_assign_hook_extra(const char *look_for, func_hook *call_back,
124 void *info)
125 {
126 struct fcall_back *cb;
127
128 cb = alloc_fcall_back(MACRO_ASSIGN_EXTRA, call_back, info);
129 add_callback(func_hash, look_for, cb);
130 }
131
132 void return_implies_state(const char *look_for, long long start, long long end,
133 implication_hook *call_back, void *info)
134 {
135 struct fcall_back *cb;
136
137 cb = alloc_fcall_back(RANGED_CALL, call_back, info);
138 cb->range = alloc_range_perm(ll_to_sval(start), ll_to_sval(end));
139 add_callback(func_hash, look_for, cb);
140 }
141
142 void select_return_states_hook(int type, return_implies_hook *callback)
143 {
144 struct return_implies_callback *cb = __alloc_return_implies_callback(0);
145
146 cb->type = type;
147 cb->callback = callback;
148 add_ptr_list(&db_return_states_list, cb);
149 }
150
151 void select_return_states_before(void_fn *fn)
152 {
153 void_fn **p = malloc(sizeof(void_fn *));
154 *p = fn;
155 add_ptr_list(&return_states_before, p);
156 }
157
158 void select_return_states_after(void_fn *fn)
159 {
160 void_fn **p = malloc(sizeof(void_fn *));
161 *p = fn;
162 add_ptr_list(&return_states_after, p);
163 }
164
165 static void call_return_states_before_hooks(void)
166 {
167 void_fn **fn;
168
169 FOR_EACH_PTR(return_states_before, fn) {
170 (*fn)();
171 } END_FOR_EACH_PTR(fn);
172 }
173
174 static void call_return_states_after_hooks(struct expression *expr)
175 {
176 void_fn **fn;
177
178 FOR_EACH_PTR(return_states_after, fn) {
179 (*fn)();
180 } END_FOR_EACH_PTR(fn);
181 __pass_to_client(expr, FUNCTION_CALL_HOOK_AFTER_DB);
182 }
183
184 static int call_call_backs(struct call_back_list *list, int type,
185 const char *fn, struct expression *expr)
186 {
187 struct fcall_back *tmp;
188 int handled = 0;
189
190 FOR_EACH_PTR(list, tmp) {
191 if (tmp->type == type) {
192 (tmp->u.call_back)(fn, expr, tmp->info);
193 handled = 1;
194 }
195 } END_FOR_EACH_PTR(tmp);
196
197 return handled;
198 }
199
200 static void call_ranged_call_backs(struct call_back_list *list,
201 const char *fn, struct expression *call_expr,
202 struct expression *assign_expr)
203 {
204 struct fcall_back *tmp;
205
206 FOR_EACH_PTR(list, tmp) {
207 (tmp->u.ranged)(fn, call_expr, assign_expr, tmp->info);
208 } END_FOR_EACH_PTR(tmp);
209 }
210
211 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
212 struct data_range *drange)
213 {
214 struct call_back_list *ret = NULL;
215 struct fcall_back *tmp;
216
217 FOR_EACH_PTR(list, tmp) {
218 if (tmp->type != RANGED_CALL)
219 continue;
220 if (ranges_equiv(tmp->range, drange))
221 add_ptr_list(&ret, tmp);
222 } END_FOR_EACH_PTR(tmp);
223 return ret;
224 }
225
226 static int in_list_exact_sval(struct range_list *list, struct data_range *drange)
227 {
228 struct data_range *tmp;
229
230 FOR_EACH_PTR(list, tmp) {
231 if (ranges_equiv(tmp, drange))
232 return 1;
233 } END_FOR_EACH_PTR(tmp);
234 return 0;
235 }
236
237 static int assign_ranged_funcs(const char *fn, struct expression *expr,
238 struct call_back_list *call_backs)
239 {
240 struct fcall_back *tmp;
241 struct sm_state *sm;
242 char *var_name;
243 struct symbol *sym;
244 struct smatch_state *estate;
245 struct stree *tmp_stree;
246 struct stree *final_states = NULL;
247 struct range_list *handled_ranges = NULL;
248 struct call_back_list *same_range_call_backs = NULL;
249 int handled = 0;
250
251 if (!call_backs)
252 return 0;
253
254 var_name = expr_to_var_sym(expr->left, &sym);
255 if (!var_name || !sym)
256 goto free;
257
258 FOR_EACH_PTR(call_backs, tmp) {
259 if (tmp->type != RANGED_CALL)
260 continue;
261
262 if (in_list_exact_sval(handled_ranges, tmp->range))
263 continue;
264 __push_fake_cur_stree();
265 tack_on(&handled_ranges, tmp->range);
266
267 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
268 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
269 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
270
271 estate = alloc_estate_range(tmp->range->min, tmp->range->max);
272 set_extra_mod(var_name, sym, expr->left, estate);
273
274 tmp_stree = __pop_fake_cur_stree();
275 merge_fake_stree(&final_states, tmp_stree);
276 free_stree(&tmp_stree);
277 handled = 1;
278 } END_FOR_EACH_PTR(tmp);
279
280 FOR_EACH_SM(final_states, sm) {
281 __set_sm(sm);
282 } END_FOR_EACH_SM(sm);
283
284 free_stree(&final_states);
285 free:
286 free_string(var_name);
287 return handled;
288 }
289
290 static void call_implies_callbacks(int comparison, struct expression *expr, sval_t sval, int left, struct stree **implied_true, struct stree **implied_false)
291 {
292 struct call_back_list *call_backs;
293 struct fcall_back *tmp;
294 const char *fn;
295 struct data_range *value_range;
296 struct stree *true_states = NULL;
297 struct stree *false_states = NULL;
298 struct stree *tmp_stree;
299
300 *implied_true = NULL;
301 *implied_false = NULL;
302 if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
303 return;
304 fn = expr->fn->symbol->ident->name;
305 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
306 if (!call_backs)
307 return;
308 value_range = alloc_range(sval, sval);
309
310 /* set true states */
311 __push_fake_cur_stree();
312 FOR_EACH_PTR(call_backs, tmp) {
313 if (tmp->type != RANGED_CALL)
314 continue;
315 if (!true_comparison_range_LR(comparison, tmp->range, value_range, left))
316 continue;
317 (tmp->u.ranged)(fn, expr, NULL, tmp->info);
318 } END_FOR_EACH_PTR(tmp);
319 tmp_stree = __pop_fake_cur_stree();
320 merge_fake_stree(&true_states, tmp_stree);
321 free_stree(&tmp_stree);
322
323 /* set false states */
324 __push_fake_cur_stree();
325 FOR_EACH_PTR(call_backs, tmp) {
326 if (tmp->type != RANGED_CALL)
327 continue;
328 if (!false_comparison_range_LR(comparison, tmp->range, value_range, left))
329 continue;
330 (tmp->u.ranged)(fn, expr, NULL, tmp->info);
331 } END_FOR_EACH_PTR(tmp);
332 tmp_stree = __pop_fake_cur_stree();
333 merge_fake_stree(&false_states, tmp_stree);
334 free_stree(&tmp_stree);
335
336 *implied_true = true_states;
337 *implied_false = false_states;
338 }
339
340 struct db_callback_info {
341 int true_side;
342 int comparison;
343 struct expression *expr;
344 struct range_list *rl;
345 int left;
346 struct stree *stree;
347 struct db_implies_list *callbacks;
348 int prev_return_id;
349 int cull;
350 int has_states;
351 char *ret_str;
352 struct smatch_state *ret_state;
353 struct expression *var_expr;
354 int handled;
355 };
356
357 static void store_return_state(struct db_callback_info *db_info, const char *ret_str, struct smatch_state *state)
358 {
359 db_info->ret_str = alloc_sname(ret_str),
360 db_info->ret_state = state;
361 }
362
363 static bool fake_a_param_assignment(struct expression *expr, const char *return_str)
364 {
365 struct expression *arg, *left, *right, *fake_assign;
366 char *p;
367 int param;
368 char buf[256];
369 char *str;
370
371 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
372 return false;
373 left = expr->left;
374 right = expr->right;
375
376 while (right->type == EXPR_ASSIGNMENT)
377 right = strip_expr(right->right);
378 if (!right || right->type != EXPR_CALL)
379 return false;
380
381 p = strchr(return_str, '[');
382 if (!p)
383 return false;
384
385 p++;
386 if (p[0] == '=' && p[1] == '=')
387 p += 2;
388 if (p[0] != '$')
389 return false;
390
391 snprintf(buf, sizeof(buf), "%s", p);
392
393 p = buf;
394 p += 1;
395 param = strtol(p, &p, 10);
396
397 p = strchr(p, ']');
398 if (!p || *p != ']')
399 return false;
400 *p = '\0';
401
402 arg = get_argument_from_call_expr(right->args, param);
403 if (!arg)
404 return false;
405 /*
406 * This is a sanity check to prevent side effects from evaluating stuff
407 * twice.
408 */
409 str = expr_to_chunk_sym_vsl(arg, NULL, NULL);
410 if (!str)
411 return false;
412 free_string(str);
413
414 right = gen_expression_from_key(arg, buf);
415 if (!right) /* Mostly fails for binops like [$0 + 4032] */
416 return false;
417 fake_assign = assign_expression(left, '=', right);
418 __in_fake_parameter_assign++;
419 __split_expr(fake_assign);
420 __in_fake_parameter_assign--;
421 return true;
422 }
423
424 static void set_return_state(struct expression *expr, struct db_callback_info *db_info)
425 {
426 struct smatch_state *state;
427
428 if (!db_info->ret_state)
429 return;
430
431 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
432 set_extra_expr_mod(expr, state);
433 db_info->ret_state = NULL;
434 fake_a_param_assignment(db_info->expr, db_info->ret_str);
435 db_info->ret_str = NULL;
436 }
437
438 static void handle_ret_equals_param(char *ret_string, struct range_list *rl, struct expression *call)
439 {
440 char *str;
441 long long param;
442 struct expression *arg;
443 struct range_list *orig;
444
445 str = strstr(ret_string, "==$");
446 if (!str)
447 return;
448 str += 3;
449 param = strtoll(str, NULL, 10);
450 arg = get_argument_from_call_expr(call->args, param);
451 if (!arg)
452 return;
453 get_absolute_rl(arg, &orig);
454 rl = rl_intersection(orig, rl);
455 if (!rl)
456 return;
457 set_extra_expr_nomod(arg, alloc_estate_rl(rl));
458 }
459
460 static int impossible_limit(struct expression *expr, int param, char *key, char *value)
461 {
462 struct expression *arg;
463 struct smatch_state *state;
464 struct range_list *passed;
465 struct range_list *limit;
466 struct symbol *compare_type;
467
468 while (expr->type == EXPR_ASSIGNMENT)
469 expr = strip_expr(expr->right);
470 if (expr->type != EXPR_CALL)
471 return 0;
472
473 arg = get_argument_from_call_expr(expr->args, param);
474 if (!arg)
475 return 0;
476
477 if (strcmp(key, "$") == 0) {
478 if (!get_implied_rl(arg, &passed))
479 return 0;
480
481 compare_type = get_arg_type(expr->fn, param);
482 } else {
483 char *name;
484 struct symbol *sym;
485
486 name = get_variable_from_key(arg, key, &sym);
487 if (!name || !sym)
488 return 0;
489
490 state = get_state(SMATCH_EXTRA, name, sym);
491 if (!state) {
492 free_string(name);
493 return 0;
494 }
495 passed = estate_rl(state);
496 if (!passed || is_whole_rl(passed)) {
497 free_string(name);
498 return 0;
499 }
500
501 compare_type = get_member_type_from_key(arg, key);
502 }
503
504 passed = cast_rl(compare_type, passed);
505 call_results_to_rl(expr, compare_type, value, &limit);
506 if (!limit || is_whole_rl(limit))
507 return 0;
508 if (possibly_true_rl(passed, SPECIAL_EQUAL, limit))
509 return 0;
510 if (option_debug || local_debug)
511 sm_msg("impossible: %d '%s' limit '%s' == '%s'", param, key, show_rl(passed), value);
512 return 1;
513 }
514
515 static int is_impossible_data(int type, struct expression *expr, int param, char *key, char *value)
516 {
517 if (type == PARAM_LIMIT && impossible_limit(expr, param, key, value))
518 return 1;
519 if (type == COMPARE_LIMIT && param_compare_limit_is_impossible(expr, param, key, value)) {
520 if (local_debug)
521 sm_msg("param_compare_limit_is_impossible: %d %s %s", param, key, value);
522 return 1;
523 }
524 return 0;
525 }
526
527 static int func_type_mismatch(struct expression *expr, const char *value)
528 {
529 struct symbol *type;
530
531 /* This makes faking returns easier */
532 if (!value || value[0] == '\0')
533 return 0;
534
535 while (expr->type == EXPR_ASSIGNMENT)
536 expr = strip_expr(expr->right);
537
538 /*
539 * Short cut: We only care about function pointers that are struct
540 * members.
541 *
542 */
543 if (expr->fn->type == EXPR_SYMBOL)
544 return 0;
545
546 type = get_type(expr->fn);
547 if (!type)
548 return 0;
549 if (type->type == SYM_PTR)
550 type = get_real_base_type(type);
551
552 if (strcmp(type_to_str(type), value) == 0)
553 return 0;
554
555 return 1;
556 }
557
558 static int db_compare_callback(void *_info, int argc, char **argv, char **azColName)
559 {
560 struct db_callback_info *db_info = _info;
561 struct range_list *var_rl = db_info->rl;
562 struct range_list *ret_range;
563 int type, param;
564 char *key, *value;
565 struct return_implies_callback *tmp;
566 struct stree *stree;
567 int return_id;
568 int comparison;
569
570 if (argc != 6)
571 return 0;
572
573 return_id = atoi(argv[0]);
574 type = atoi(argv[2]);
575 param = atoi(argv[3]);
576 key = argv[4];
577 value = argv[5];
578
579 db_info->has_states = 1;
580 if (db_info->prev_return_id != -1 && type == INTERNAL) {
581 set_return_state(db_info->var_expr, db_info);
582 stree = __pop_fake_cur_stree();
583
584 if (!db_info->cull)
585 merge_fake_stree(&db_info->stree, stree);
586 free_stree(&stree);
587 __push_fake_cur_stree();
588 db_info->cull = 0;
589 }
590 db_info->prev_return_id = return_id;
591
592 if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
593 db_info->cull = 1;
594 if (db_info->cull)
595 return 0;
596 if (type == CULL_PATH) {
597 db_info->cull = 1;
598 return 0;
599 }
600
601 if (is_impossible_data(type, db_info->expr, param, key, value)) {
602 db_info->cull = 1;
603 return 0;
604 }
605
606 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), argv[1], &ret_range);
607 ret_range = cast_rl(get_type(db_info->expr), ret_range);
608 if (!ret_range)
609 ret_range = alloc_whole_rl(get_type(db_info->expr));
610
611 comparison = db_info->comparison;
612 if (db_info->left)
613 comparison = flip_comparison(comparison);
614
615 if (db_info->true_side) {
616 if (!possibly_true_rl(var_rl, comparison, ret_range))
617 return 0;
618 if (type == PARAM_LIMIT)
619 param_limit_implications(db_info->expr, param, key, value);
620 filter_by_comparison(&var_rl, comparison, ret_range);
621 filter_by_comparison(&ret_range, flip_comparison(comparison), var_rl);
622 } else {
623 if (!possibly_false_rl(var_rl, comparison, ret_range))
624 return 0;
625 if (type == PARAM_LIMIT)
626 param_limit_implications(db_info->expr, param, key, value);
627 filter_by_comparison(&var_rl, negate_comparison(comparison), ret_range);
628 filter_by_comparison(&ret_range, flip_comparison(negate_comparison(comparison)), var_rl);
629 }
630
631 handle_ret_equals_param(argv[1], ret_range, db_info->expr);
632
633 if (type == INTERNAL) {
634 set_state(-1, "unnull_path", NULL, &true_state);
635 __add_return_comparison(strip_expr(db_info->expr), argv[1]);
636 __add_return_to_param_mapping(db_info->expr, argv[1]);
637 store_return_state(db_info, argv[1], alloc_estate_rl(clone_rl(var_rl)));
638 }
639
640 FOR_EACH_PTR(db_info->callbacks, tmp) {
641 if (tmp->type == type)
642 tmp->callback(db_info->expr, param, key, value);
643 } END_FOR_EACH_PTR(tmp);
644
645 return 0;
646 }
647
648 static void compare_db_return_states_callbacks(struct expression *left, int comparison, struct expression *right, struct stree *implied_true, struct stree *implied_false)
649 {
650 struct stree *orig_states;
651 struct stree *stree;
652 struct stree *true_states;
653 struct stree *false_states;
654 struct sm_state *sm;
655 struct db_callback_info db_info = {};
656 struct expression *var_expr;
657 struct expression *call_expr;
658 struct range_list *rl;
659 int call_on_left;
660
661 orig_states = clone_stree(__get_cur_stree());
662
663 /* legacy cruft. need to fix call_implies_callbacks(). */
664 call_on_left = 1;
665 call_expr = left;
666 var_expr = right;
667 if (left->type != EXPR_CALL) {
668 call_on_left = 0;
669 call_expr = right;
670 var_expr = left;
671 }
672
673 get_absolute_rl(var_expr, &rl);
674
675 db_info.comparison = comparison;
676 db_info.expr = call_expr;
677 db_info.rl = rl;
678 db_info.left = call_on_left;
679 db_info.callbacks = db_return_states_list;
680 db_info.var_expr = var_expr;
681
682 call_return_states_before_hooks();
683
684 db_info.true_side = 1;
685 db_info.stree = NULL;
686 db_info.prev_return_id = -1;
687 __push_fake_cur_stree();
688 sql_select_return_states("return_id, return, type, parameter, key, value",
689 call_expr, db_compare_callback, &db_info);
690 set_return_state(db_info.var_expr, &db_info);
691 stree = __pop_fake_cur_stree();
692 if (!db_info.cull) {
693 set_return_state(db_info.var_expr, &db_info);
694 merge_fake_stree(&db_info.stree, stree);
695 }
696 free_stree(&stree);
697 true_states = db_info.stree;
698 if (!true_states && db_info.has_states) {
699 __push_fake_cur_stree();
700 set_path_impossible();
701 true_states = __pop_fake_cur_stree();
702 }
703
704 nullify_path();
705 __unnullify_path();
706 FOR_EACH_SM(orig_states, sm) {
707 __set_sm_cur_stree(sm);
708 } END_FOR_EACH_SM(sm);
709
710 db_info.true_side = 0;
711 db_info.stree = NULL;
712 db_info.prev_return_id = -1;
713 db_info.cull = 0;
714 __push_fake_cur_stree();
715 sql_select_return_states("return_id, return, type, parameter, key, value", call_expr,
716 db_compare_callback, &db_info);
717 stree = __pop_fake_cur_stree();
718 if (!db_info.cull) {
719 set_return_state(db_info.var_expr, &db_info);
720 merge_fake_stree(&db_info.stree, stree);
721 }
722 free_stree(&stree);
723 false_states = db_info.stree;
724 if (!false_states && db_info.has_states) {
725 __push_fake_cur_stree();
726 set_path_impossible();
727 false_states = __pop_fake_cur_stree();
728 }
729
730 nullify_path();
731 __unnullify_path();
732 FOR_EACH_SM(orig_states, sm) {
733 __set_sm_cur_stree(sm);
734 } END_FOR_EACH_SM(sm);
735
736 free_stree(&orig_states);
737
738 FOR_EACH_SM(true_states, sm) {
739 __set_true_false_sm(sm, NULL);
740 } END_FOR_EACH_SM(sm);
741 FOR_EACH_SM(false_states, sm) {
742 __set_true_false_sm(NULL, sm);
743 } END_FOR_EACH_SM(sm);
744
745 free_stree(&true_states);
746 free_stree(&false_states);
747
748 call_return_states_after_hooks(call_expr);
749
750 FOR_EACH_SM(implied_true, sm) {
751 __set_true_false_sm(sm, NULL);
752 } END_FOR_EACH_SM(sm);
753 FOR_EACH_SM(implied_false, sm) {
754 __set_true_false_sm(NULL, sm);
755 } END_FOR_EACH_SM(sm);
756 }
757
758 void function_comparison(struct expression *left, int comparison, struct expression *right)
759 {
760 struct expression *var_expr;
761 struct expression *call_expr;
762 struct stree *implied_true = NULL;
763 struct stree *implied_false = NULL;
764 struct range_list *rl;
765 sval_t sval;
766 int call_on_left;
767
768 if (unreachable())
769 return;
770
771 /* legacy cruft. need to fix call_implies_callbacks(). */
772 call_on_left = 1;
773 call_expr = left;
774 var_expr = right;
775 if (left->type != EXPR_CALL) {
776 call_on_left = 0;
777 call_expr = right;
778 var_expr = left;
779 }
780
781 get_absolute_rl(var_expr, &rl);
782
783 if (rl_to_sval(rl, &sval))
784 call_implies_callbacks(comparison, call_expr, sval, call_on_left, &implied_true, &implied_false);
785
786 compare_db_return_states_callbacks(left, comparison, right, implied_true, implied_false);
787 free_stree(&implied_true);
788 free_stree(&implied_false);
789 }
790
791 static void call_ranged_return_hooks(struct db_callback_info *db_info)
792 {
793 struct call_back_list *call_backs;
794 struct expression *expr;
795 struct fcall_back *tmp;
796 char *fn;
797
798 expr = strip_expr(db_info->expr);
799 while (expr->type == EXPR_ASSIGNMENT)
800 expr = strip_expr(expr->right);
801 if (expr->type != EXPR_CALL ||
802 expr->fn->type != EXPR_SYMBOL)
803 return;
804
805 fn = expr->fn->symbol_name->name;
806
807 call_backs = search_callback(func_hash, fn);
808 FOR_EACH_PTR(call_backs, tmp) {
809 struct range_list *range_rl = NULL;
810
811 if (tmp->type != RANGED_CALL)
812 continue;
813 add_range(&range_rl, tmp->range->min, tmp->range->max);
814 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl);
815 if (possibly_true_rl(range_rl, SPECIAL_EQUAL, estate_rl(db_info->ret_state))) {
816 if (!possibly_true_rl(rl_invert(range_rl), SPECIAL_EQUAL, estate_rl(db_info->ret_state)))
817 (tmp->u.ranged)(fn, expr, db_info->expr, tmp->info);
818 else
819 db_info->handled = -1;
820 }
821 } END_FOR_EACH_PTR(tmp);
822 }
823
824 static int db_assign_return_states_callback(void *_info, int argc, char **argv, char **azColName)
825 {
826 struct db_callback_info *db_info = _info;
827 struct range_list *ret_range;
828 int type, param;
829 char *key, *value;
830 struct return_implies_callback *tmp;
831 struct stree *stree;
832 int return_id;
833
834 if (argc != 6)
835 return 0;
836
837 return_id = atoi(argv[0]);
838 type = atoi(argv[2]);
839 param = atoi(argv[3]);
840 key = argv[4];
841 value = argv[5];
842
843 if (db_info->prev_return_id != -1 && type == INTERNAL) {
844 call_ranged_return_hooks(db_info);
845 set_return_state(db_info->expr->left, db_info);
846 stree = __pop_fake_cur_stree();
847 if (!db_info->cull)
848 merge_fake_stree(&db_info->stree, stree);
849 free_stree(&stree);
850 __push_fake_cur_stree();
851 db_info->cull = 0;
852 }
853 db_info->prev_return_id = return_id;
854
855 if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
856 db_info->cull = 1;
857 if (db_info->cull)
858 return 0;
859 if (type == CULL_PATH) {
860 db_info->cull = 1;
861 return 0;
862 }
863 if (is_impossible_data(type, db_info->expr, param, key, value)) {
864 db_info->cull = 1;
865 return 0;
866 }
867
868 if (type == PARAM_LIMIT)
869 param_limit_implications(db_info->expr, param, key, value);
870
871 db_info->handled = 1;
872 call_results_to_rl(db_info->expr->right, get_type(strip_expr(db_info->expr->right)), argv[1], &ret_range);
873 if (!ret_range)
874 ret_range = alloc_whole_rl(get_type(strip_expr(db_info->expr->right)));
875 ret_range = cast_rl(get_type(db_info->expr->right), ret_range);
876
877 if (type == INTERNAL) {
878 set_state(-1, "unnull_path", NULL, &true_state);
879 __add_return_comparison(strip_expr(db_info->expr->right), argv[1]);
880 __add_comparison_info(db_info->expr->left, strip_expr(db_info->expr->right), argv[1]);
881 __add_return_to_param_mapping(db_info->expr, argv[1]);
882 store_return_state(db_info, argv[1], alloc_estate_rl(ret_range));
883 }
884
885 FOR_EACH_PTR(db_return_states_list, tmp) {
886 if (tmp->type == type)
887 tmp->callback(db_info->expr, param, key, value);
888 } END_FOR_EACH_PTR(tmp);
889
890 return 0;
891 }
892
893 static int db_return_states_assign(struct expression *expr)
894 {
895 struct expression *right;
896 struct sm_state *sm;
897 struct stree *stree;
898 struct db_callback_info db_info = {};
899
900 right = strip_expr(expr->right);
901
902 db_info.prev_return_id = -1;
903 db_info.expr = expr;
904 db_info.stree = NULL;
905 db_info.handled = 0;
906
907 call_return_states_before_hooks();
908
909 __push_fake_cur_stree();
910 sql_select_return_states("return_id, return, type, parameter, key, value",
911 right, db_assign_return_states_callback, &db_info);
912 if (option_debug) {
913 sm_msg("%s return_id %d return_ranges %s",
914 db_info.cull ? "culled" : "merging",
915 db_info.prev_return_id,
916 db_info.ret_state ? db_info.ret_state->name : "'<empty>'");
917 }
918 if (db_info.handled)
919 call_ranged_return_hooks(&db_info);
920 set_return_state(db_info.expr->left, &db_info);
921 stree = __pop_fake_cur_stree();
922 if (!db_info.cull)
923 merge_fake_stree(&db_info.stree, stree);
924 free_stree(&stree);
925
926 if (!db_info.stree && db_info.cull) { /* this means we culled everything */
927 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
928 set_path_impossible();
929 }
930 FOR_EACH_SM(db_info.stree, sm) {
931 __set_sm(sm);
932 } END_FOR_EACH_SM(sm);
933
934 free_stree(&db_info.stree);
935 call_return_states_after_hooks(right);
936
937 return db_info.handled;
938 }
939
940 static int handle_implied_return(struct expression *expr)
941 {
942 struct range_list *rl;
943
944 if (!get_implied_return(expr->right, &rl))
945 return 0;
946 rl = cast_rl(get_type(expr->left), rl);
947 set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
948 return 1;
949 }
950
951 static void match_assign_call(struct expression *expr)
952 {
953 struct call_back_list *call_backs;
954 const char *fn;
955 struct expression *right;
956 int handled = 0;
957 struct range_list *rl;
958
959 if (expr->op != '=')
960 return;
961
962 right = strip_expr(expr->right);
963 if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol) {
964 handled |= db_return_states_assign(expr);
965 if (!handled)
966 goto assigned_unknown;
967 return;
968 }
969 if (is_fake_call(right)) {
970 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
971 return;
972 }
973
974 fn = right->fn->symbol->ident->name;
975 call_backs = search_callback(func_hash, (char *)fn);
976
977 /*
978 * The ordering here is sort of important.
979 * One example, of how this matters is that when we do:
980 *
981 * len = strlen(str);
982 *
983 * That is handled by smatch_common_functions.c and smatch_strlen.c.
984 * They use implied_return and function_assign_hook respectively.
985 * We want to get the implied return first before we do the function
986 * assignment hook otherwise we end up writing the wrong thing for len
987 * in smatch_extra.c because we assume that it already holds the
988 * strlen() when we haven't set it yet.
989 */
990
991 if (db_return_states_assign(expr) == 1)
992 handled = 1;
993 else
994 handled = assign_ranged_funcs(fn, expr, call_backs);
995 handled |= handle_implied_return(expr);
996
997
998 call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
999
1000 if (handled)
1001 return;
1002
1003 assigned_unknown:
1004 get_absolute_rl(expr->right, &rl);
1005 rl = cast_rl(get_type(expr->left), rl);
1006 set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
1007 }
1008
1009 static int db_return_states_callback(void *_info, int argc, char **argv, char **azColName)
1010 {
1011 struct db_callback_info *db_info = _info;
1012 struct range_list *ret_range;
1013 int type, param;
1014 char *key, *value;
1015 struct return_implies_callback *tmp;
1016 struct stree *stree;
1017 int return_id;
1018 char buf[64];
1019
1020 if (argc != 6)
1021 return 0;
1022
1023 return_id = atoi(argv[0]);
1024 type = atoi(argv[2]);
1025 param = atoi(argv[3]);
1026 key = argv[4];
1027 value = argv[5];
1028
1029 if (db_info->prev_return_id != -1 && type == INTERNAL) {
1030 stree = __pop_fake_cur_stree();
1031 if (!db_info->cull)
1032 merge_fake_stree(&db_info->stree, stree);
1033 free_stree(&stree);
1034 __push_fake_cur_stree();
1035 __unnullify_path();
1036 db_info->cull = 0;
1037 }
1038 db_info->prev_return_id = return_id;
1039
1040 if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
1041 db_info->cull = 1;
1042 if (db_info->cull)
1043 return 0;
1044 if (type == CULL_PATH) {
1045 db_info->cull = 1;
1046 return 0;
1047 }
1048 if (is_impossible_data(type, db_info->expr, param, key, value)) {
1049 db_info->cull = 1;
1050 return 0;
1051 }
1052
1053 if (type == PARAM_LIMIT)
1054 param_limit_implications(db_info->expr, param, key, value);
1055
1056 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), argv[1], &ret_range);
1057 ret_range = cast_rl(get_type(db_info->expr), ret_range);
1058
1059 if (type == INTERNAL) {
1060 set_state(-1, "unnull_path", NULL, &true_state);
1061 __add_return_comparison(strip_expr(db_info->expr), argv[1]);
1062 __add_return_to_param_mapping(db_info->expr, argv[1]);
1063 }
1064
1065
1066 FOR_EACH_PTR(db_return_states_list, tmp) {
1067 if (tmp->type == type)
1068 tmp->callback(db_info->expr, param, key, value);
1069 } END_FOR_EACH_PTR(tmp);
1070
1071 /*
1072 * We want to store the return values so that we can split the strees
1073 * in smatch_db.c. This uses set_state() directly because it's not a
1074 * real smatch_extra state.
1075 */
1076 snprintf(buf, sizeof(buf), "return %p", db_info->expr);
1077 set_state(SMATCH_EXTRA, buf, NULL, alloc_estate_rl(ret_range));
1078
1079 return 0;
1080 }
1081
1082 static void db_return_states(struct expression *expr)
1083 {
1084 struct sm_state *sm;
1085 struct stree *stree;
1086 struct db_callback_info db_info = {};
1087
1088 if (!__get_cur_stree()) /* no return functions */
1089 return;
1090
1091 db_info.prev_return_id = -1;
1092 db_info.expr = expr;
1093 db_info.stree = NULL;
1094
1095 call_return_states_before_hooks();
1096
1097 __push_fake_cur_stree();
1098 __unnullify_path();
1099 sql_select_return_states("return_id, return, type, parameter, key, value",
1100 expr, db_return_states_callback, &db_info);
1101 stree = __pop_fake_cur_stree();
1102 if (!db_info.cull)
1103 merge_fake_stree(&db_info.stree, stree);
1104 free_stree(&stree);
1105
1106 FOR_EACH_SM(db_info.stree, sm) {
1107 __set_sm(sm);
1108 } END_FOR_EACH_SM(sm);
1109
1110 free_stree(&db_info.stree);
1111 call_return_states_after_hooks(expr);
1112 }
1113
1114 static int is_condition_call(struct expression *expr)
1115 {
1116 struct expression *tmp;
1117
1118 FOR_EACH_PTR_REVERSE(big_condition_stack, tmp) {
1119 if (expr == tmp || expr_get_parent_expr(expr) == tmp)
1120 return 1;
1121 if (tmp->pos.line < expr->pos.line)
1122 return 0;
1123 } END_FOR_EACH_PTR_REVERSE(tmp);
1124
1125 return 0;
1126 }
1127
1128 static void db_return_states_call(struct expression *expr)
1129 {
1130 if (unreachable())
1131 return;
1132
1133 if (is_assigned_call(expr))
1134 return;
1135 if (is_condition_call(expr))
1136 return;
1137 db_return_states(expr);
1138 }
1139
1140 static void match_function_call(struct expression *expr)
1141 {
1142 struct call_back_list *call_backs;
1143
1144 if (expr->fn->type == EXPR_SYMBOL && expr->fn->symbol) {
1145 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
1146 if (call_backs)
1147 call_call_backs(call_backs, REGULAR_CALL,
1148 expr->fn->symbol->ident->name, expr);
1149 }
1150 db_return_states_call(expr);
1151 }
1152
1153 static void match_macro_assign(struct expression *expr)
1154 {
1155 struct call_back_list *call_backs;
1156 const char *macro;
1157 struct expression *right;
1158
1159 right = strip_expr(expr->right);
1160 macro = get_macro_name(right->pos);
1161 call_backs = search_callback(func_hash, (char *)macro);
1162 if (!call_backs)
1163 return;
1164 call_call_backs(call_backs, MACRO_ASSIGN, macro, expr);
1165 call_call_backs(call_backs, MACRO_ASSIGN_EXTRA, macro, expr);
1166 }
1167
1168 int get_implied_return(struct expression *expr, struct range_list **rl)
1169 {
1170 struct call_back_list *call_backs;
1171 struct fcall_back *tmp;
1172 int handled = 0;
1173 char *fn;
1174
1175 *rl = NULL;
1176
1177 expr = strip_expr(expr);
1178 fn = expr_to_var(expr->fn);
1179 if (!fn)
1180 goto out;
1181
1182 call_backs = search_callback(func_hash, fn);
1183
1184 FOR_EACH_PTR(call_backs, tmp) {
1185 if (tmp->type == IMPLIED_RETURN) {
1186 (tmp->u.implied_return)(expr, tmp->info, rl);
1187 handled = 1;
1188 }
1189 } END_FOR_EACH_PTR(tmp);
1190
1191 out:
1192 free_string(fn);
1193 return handled;
1194 }
1195
1196 void create_function_hook_hash(void)
1197 {
1198 func_hash = create_function_hashtable(5000);
1199 }
1200
1201 void register_function_hooks(int id)
1202 {
1203 add_hook(&match_function_call, CALL_HOOK_AFTER_INLINE);
1204 add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
1205 add_hook(&match_macro_assign, MACRO_ASSIGNMENT_HOOK);
1206 }