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;
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 {
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));
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;
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) {
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)
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)
|
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 return_implies_state_sval(const char *look_for, sval_t start, sval_t end,
143 implication_hook *call_back, void *info)
144 {
145 struct fcall_back *cb;
146
147 cb = alloc_fcall_back(RANGED_CALL, call_back, info);
148 cb->range = alloc_range_perm(start, end);
149 add_callback(func_hash, look_for, cb);
150 }
151
152 void select_return_states_hook(int type, return_implies_hook *callback)
153 {
154 struct return_implies_callback *cb = __alloc_return_implies_callback(0);
155
156 cb->type = type;
157 cb->callback = callback;
158 add_ptr_list(&db_return_states_list, cb);
159 }
160
161 void select_return_states_before(void_fn *fn)
162 {
163 void_fn **p = malloc(sizeof(void_fn *));
164 *p = fn;
165 add_ptr_list(&return_states_before, p);
166 }
167
168 void select_return_states_after(void_fn *fn)
169 {
170 void_fn **p = malloc(sizeof(void_fn *));
171 *p = fn;
239
240 FOR_EACH_PTR(list, tmp) {
241 if (ranges_equiv(tmp, drange))
242 return 1;
243 } END_FOR_EACH_PTR(tmp);
244 return 0;
245 }
246
247 static int assign_ranged_funcs(const char *fn, struct expression *expr,
248 struct call_back_list *call_backs)
249 {
250 struct fcall_back *tmp;
251 struct sm_state *sm;
252 char *var_name;
253 struct symbol *sym;
254 struct smatch_state *estate;
255 struct stree *tmp_stree;
256 struct stree *final_states = NULL;
257 struct range_list *handled_ranges = NULL;
258 struct call_back_list *same_range_call_backs = NULL;
259 struct range_list *rl;
260 int handled = 0;
261
262 if (!call_backs)
263 return 0;
264
265 var_name = expr_to_var_sym(expr->left, &sym);
266 if (!var_name || !sym)
267 goto free;
268
269 FOR_EACH_PTR(call_backs, tmp) {
270 if (tmp->type != RANGED_CALL)
271 continue;
272
273 if (in_list_exact_sval(handled_ranges, tmp->range))
274 continue;
275 __push_fake_cur_stree();
276 tack_on(&handled_ranges, tmp->range);
277
278 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
279 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
280 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
281
282 rl = alloc_rl(tmp->range->min, tmp->range->max);
283 rl = cast_rl(get_type(expr->left), rl);
284 estate = alloc_estate_rl(rl);
285 set_extra_mod(var_name, sym, expr->left, estate);
286
287 tmp_stree = __pop_fake_cur_stree();
288 merge_fake_stree(&final_states, tmp_stree);
289 free_stree(&tmp_stree);
290 handled = 1;
291 } END_FOR_EACH_PTR(tmp);
292
293 FOR_EACH_SM(final_states, sm) {
294 __set_sm(sm);
295 } END_FOR_EACH_SM(sm);
296
297 free_stree(&final_states);
298 free:
299 free_string(var_name);
300 return handled;
301 }
302
303 static void call_implies_callbacks(int comparison, struct expression *expr, sval_t sval, int left, struct stree **implied_true, struct stree **implied_false)
304 {
358 int left;
359 struct stree *stree;
360 struct db_implies_list *callbacks;
361 int prev_return_id;
362 int cull;
363 int has_states;
364 char *ret_str;
365 struct smatch_state *ret_state;
366 struct expression *var_expr;
367 int handled;
368 };
369
370 static void store_return_state(struct db_callback_info *db_info, const char *ret_str, struct smatch_state *state)
371 {
372 db_info->ret_str = alloc_sname(ret_str),
373 db_info->ret_state = state;
374 }
375
376 static bool fake_a_param_assignment(struct expression *expr, const char *return_str)
377 {
378 struct expression *arg, *left, *right, *tmp, *fake_assign;
379 char *p;
380 int param;
381 char buf[256];
382 char *str;
383
384 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
385 return false;
386 left = expr->left;
387 right = expr->right;
388
389 while (right->type == EXPR_ASSIGNMENT)
390 right = strip_expr(right->right);
391 if (!right || right->type != EXPR_CALL)
392 return false;
393
394 p = strchr(return_str, '[');
395 if (!p)
396 return false;
397
398 p++;
399 if (p[0] == '=' && p[1] == '=')
400 p += 2;
401 if (p[0] != '$')
402 return false;
403
404 snprintf(buf, sizeof(buf), "%s", p);
405
406 p = buf;
407 p += 1;
408 param = strtol(p, &p, 10);
409
410 p = strchr(p, ']');
411 if (!p || *p != ']')
412 return false;
413 *p = '\0';
414
415 arg = get_argument_from_call_expr(right->args, param);
416 if (!arg)
417 return false;
418
419 /* There should be a get_other_name() function which returns an expr */
420 tmp = get_assigned_expr(arg);
421 if (tmp)
422 arg = tmp;
423
424 /*
425 * This is a sanity check to prevent side effects from evaluating stuff
426 * twice.
427 */
428 str = expr_to_chunk_sym_vsl(arg, NULL, NULL);
429 if (!str)
430 return false;
431 free_string(str);
432
433 right = gen_expression_from_key(arg, buf);
434 if (!right) /* Mostly fails for binops like [$0 + 4032] */
435 return false;
436 fake_assign = assign_expression(left, '=', right);
437 __in_fake_parameter_assign++;
438 __split_expr(fake_assign);
439 __in_fake_parameter_assign--;
440 return true;
441 }
442
443 static void set_return_assign_state(struct db_callback_info *db_info)
444 {
445 struct expression *expr = db_info->expr->left;
446 struct smatch_state *state;
447
448 if (!db_info->ret_state)
449 return;
450
451 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
452 set_extra_expr_mod(expr, state);
453 db_info->ret_state = NULL;
454 fake_a_param_assignment(db_info->expr, db_info->ret_str);
455 db_info->ret_str = NULL;
456 }
457
458 static void set_other_side_state(struct db_callback_info *db_info)
459 {
460 struct expression *expr = db_info->var_expr;
461 struct smatch_state *state;
462
463 if (!db_info->ret_state)
464 return;
465
466 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
467 set_extra_expr_nomod(expr, state);
468 db_info->ret_state = NULL;
469 db_info->ret_str = NULL;
470 }
471
472 static void handle_ret_equals_param(char *ret_string, struct range_list *rl, struct expression *call)
473 {
474 char *str;
475 long long param;
476 struct expression *arg;
477 struct range_list *orig;
478
479 str = strstr(ret_string, "==$");
480 if (!str)
481 return;
482 str += 3;
483 param = strtoll(str, NULL, 10);
484 arg = get_argument_from_call_expr(call->args, param);
485 if (!arg)
486 return;
487 get_absolute_rl(arg, &orig);
488 rl = rl_intersection(orig, rl);
489 if (!rl)
490 return;
491 set_extra_expr_nomod(arg, alloc_estate_rl(rl));
578 return 0;
579
580 type = get_type(expr->fn);
581 if (!type)
582 return 0;
583 if (type->type == SYM_PTR)
584 type = get_real_base_type(type);
585
586 if (strcmp(type_to_str(type), value) == 0)
587 return 0;
588
589 return 1;
590 }
591
592 static int db_compare_callback(void *_info, int argc, char **argv, char **azColName)
593 {
594 struct db_callback_info *db_info = _info;
595 struct range_list *var_rl = db_info->rl;
596 struct range_list *ret_range;
597 int type, param;
598 char *ret_str, *key, *value;
599 struct return_implies_callback *tmp;
600 struct stree *stree;
601 int return_id;
602 int comparison;
603
604 if (argc != 6)
605 return 0;
606
607 return_id = atoi(argv[0]);
608 ret_str = argv[1];
609 type = atoi(argv[2]);
610 param = atoi(argv[3]);
611 key = argv[4];
612 value = argv[5];
613
614 db_info->has_states = 1;
615 if (db_info->prev_return_id != -1 && type == INTERNAL) {
616 set_other_side_state(db_info);
617 stree = __pop_fake_cur_stree();
618
619 if (!db_info->cull)
620 merge_fake_stree(&db_info->stree, stree);
621 free_stree(&stree);
622 __push_fake_cur_stree();
623 db_info->cull = 0;
624 }
625 db_info->prev_return_id = return_id;
626
627 if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
628 db_info->cull = 1;
629 if (db_info->cull)
630 return 0;
631 if (type == CULL_PATH) {
632 db_info->cull = 1;
633 return 0;
634 }
635
636 if (is_impossible_data(type, db_info->expr, param, key, value)) {
637 db_info->cull = 1;
638 return 0;
639 }
640
641 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range);
642 ret_range = cast_rl(get_type(db_info->expr), ret_range);
643 if (!ret_range)
644 ret_range = alloc_whole_rl(get_type(db_info->expr));
645
646 comparison = db_info->comparison;
647 if (db_info->left)
648 comparison = flip_comparison(comparison);
649
650 if (db_info->true_side) {
651 if (!possibly_true_rl(var_rl, comparison, ret_range))
652 return 0;
653 if (type == PARAM_LIMIT)
654 param_limit_implications(db_info->expr, param, key, value);
655 filter_by_comparison(&var_rl, comparison, ret_range);
656 filter_by_comparison(&ret_range, flip_comparison(comparison), var_rl);
657 } else {
658 if (!possibly_false_rl(var_rl, comparison, ret_range))
659 return 0;
660 if (type == PARAM_LIMIT)
661 param_limit_implications(db_info->expr, param, key, value);
662 filter_by_comparison(&var_rl, negate_comparison(comparison), ret_range);
663 filter_by_comparison(&ret_range, flip_comparison(negate_comparison(comparison)), var_rl);
664 }
665
666 handle_ret_equals_param(ret_str, ret_range, db_info->expr);
667
668 if (type == INTERNAL) {
669 set_state(-1, "unnull_path", NULL, &true_state);
670 __add_return_comparison(strip_expr(db_info->expr), ret_str);
671 __add_return_to_param_mapping(db_info->expr, ret_str);
672 store_return_state(db_info, ret_str, alloc_estate_rl(clone_rl(var_rl)));
673 }
674
675 FOR_EACH_PTR(db_info->callbacks, tmp) {
676 if (tmp->type == type)
677 tmp->callback(db_info->expr, param, key, value);
678 } END_FOR_EACH_PTR(tmp);
679
680 return 0;
681 }
682
683 static void compare_db_return_states_callbacks(struct expression *left, int comparison, struct expression *right, struct stree *implied_true, struct stree *implied_false)
684 {
685 struct stree *orig_states;
686 struct stree *stree;
687 struct stree *true_states;
688 struct stree *false_states;
689 struct sm_state *sm;
690 struct db_callback_info db_info = {};
691 struct expression *var_expr;
692 struct expression *call_expr;
705 var_expr = left;
706 }
707
708 get_absolute_rl(var_expr, &rl);
709
710 db_info.comparison = comparison;
711 db_info.expr = call_expr;
712 db_info.rl = rl;
713 db_info.left = call_on_left;
714 db_info.callbacks = db_return_states_list;
715 db_info.var_expr = var_expr;
716
717 call_return_states_before_hooks();
718
719 db_info.true_side = 1;
720 db_info.stree = NULL;
721 db_info.prev_return_id = -1;
722 __push_fake_cur_stree();
723 sql_select_return_states("return_id, return, type, parameter, key, value",
724 call_expr, db_compare_callback, &db_info);
725 set_other_side_state(&db_info);
726 stree = __pop_fake_cur_stree();
727 if (!db_info.cull)
728 merge_fake_stree(&db_info.stree, stree);
729 free_stree(&stree);
730 true_states = db_info.stree;
731 if (!true_states && db_info.has_states) {
732 __push_fake_cur_stree();
733 set_path_impossible();
734 true_states = __pop_fake_cur_stree();
735 }
736
737 nullify_path();
738 __unnullify_path();
739 FOR_EACH_SM(orig_states, sm) {
740 __set_sm_cur_stree(sm);
741 } END_FOR_EACH_SM(sm);
742
743 db_info.true_side = 0;
744 db_info.stree = NULL;
745 db_info.prev_return_id = -1;
746 db_info.cull = 0;
747 __push_fake_cur_stree();
748 sql_select_return_states("return_id, return, type, parameter, key, value", call_expr,
749 db_compare_callback, &db_info);
750 set_other_side_state(&db_info);
751 stree = __pop_fake_cur_stree();
752 if (!db_info.cull)
753 merge_fake_stree(&db_info.stree, stree);
754 free_stree(&stree);
755 false_states = db_info.stree;
756 if (!false_states && db_info.has_states) {
757 __push_fake_cur_stree();
758 set_path_impossible();
759 false_states = __pop_fake_cur_stree();
760 }
761
762 nullify_path();
763 __unnullify_path();
764 FOR_EACH_SM(orig_states, sm) {
765 __set_sm_cur_stree(sm);
766 } END_FOR_EACH_SM(sm);
767
768 free_stree(&orig_states);
769
770 FOR_EACH_SM(true_states, sm) {
771 __set_true_false_sm(sm, NULL);
772 } END_FOR_EACH_SM(sm);
773 FOR_EACH_SM(false_states, sm) {
821 }
822
823 static void call_ranged_return_hooks(struct db_callback_info *db_info)
824 {
825 struct call_back_list *call_backs;
826 struct expression *expr;
827 struct fcall_back *tmp;
828 char *fn;
829
830 expr = strip_expr(db_info->expr);
831 while (expr->type == EXPR_ASSIGNMENT)
832 expr = strip_expr(expr->right);
833 if (expr->type != EXPR_CALL ||
834 expr->fn->type != EXPR_SYMBOL)
835 return;
836
837 fn = expr->fn->symbol_name->name;
838
839 call_backs = search_callback(func_hash, fn);
840 FOR_EACH_PTR(call_backs, tmp) {
841 struct range_list *range_rl;
842
843 if (tmp->type != RANGED_CALL)
844 continue;
845 range_rl = alloc_rl(tmp->range->min, tmp->range->max);
846 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl);
847 if (possibly_true_rl(range_rl, SPECIAL_EQUAL, estate_rl(db_info->ret_state)))
848 (tmp->u.ranged)(fn, expr, db_info->expr, tmp->info);
849 } END_FOR_EACH_PTR(tmp);
850 }
851
852 static int db_assign_return_states_callback(void *_info, int argc, char **argv, char **azColName)
853 {
854 struct db_callback_info *db_info = _info;
855 struct range_list *ret_range;
856 int type, param;
857 char *ret_str, *key, *value;
858 struct return_implies_callback *tmp;
859 struct stree *stree;
860 int return_id;
861
862 if (argc != 6)
863 return 0;
864
865 return_id = atoi(argv[0]);
866 ret_str = argv[1];
867 type = atoi(argv[2]);
868 param = atoi(argv[3]);
869 key = argv[4];
870 value = argv[5];
871
872 if (db_info->prev_return_id != -1 && type == INTERNAL) {
873 call_ranged_return_hooks(db_info);
874 set_return_assign_state(db_info);
875 stree = __pop_fake_cur_stree();
876 if (!db_info->cull)
877 merge_fake_stree(&db_info->stree, stree);
878 free_stree(&stree);
879 __push_fake_cur_stree();
880 db_info->cull = 0;
881 }
882 db_info->prev_return_id = return_id;
883
884 if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
885 db_info->cull = 1;
886 if (db_info->cull)
887 return 0;
888 if (type == CULL_PATH) {
889 db_info->cull = 1;
890 return 0;
891 }
892 if (is_impossible_data(type, db_info->expr, param, key, value)) {
893 db_info->cull = 1;
894 return 0;
895 }
896
897 if (type == PARAM_LIMIT)
898 param_limit_implications(db_info->expr, param, key, value);
899
900 db_info->handled = 1;
901 call_results_to_rl(db_info->expr->right, get_type(strip_expr(db_info->expr->right)), ret_str, &ret_range);
902 if (!ret_range)
903 ret_range = alloc_whole_rl(get_type(strip_expr(db_info->expr->right)));
904 ret_range = cast_rl(get_type(db_info->expr->right), ret_range);
905
906 if (type == INTERNAL) {
907 set_state(-1, "unnull_path", NULL, &true_state);
908 __add_return_comparison(strip_expr(db_info->expr->right), ret_str);
909 __add_comparison_info(db_info->expr->left, strip_expr(db_info->expr->right), ret_str);
910 __add_return_to_param_mapping(db_info->expr, ret_str);
911 store_return_state(db_info, ret_str, alloc_estate_rl(ret_range));
912 }
913
914 FOR_EACH_PTR(db_return_states_list, tmp) {
915 if (tmp->type == type)
916 tmp->callback(db_info->expr, param, key, value);
917 } END_FOR_EACH_PTR(tmp);
918
919 return 0;
920 }
921
922 static int db_return_states_assign(struct expression *expr)
923 {
924 struct expression *right;
925 struct sm_state *sm;
926 struct stree *stree;
927 struct db_callback_info db_info = {};
928
929 right = strip_expr(expr->right);
930
931 db_info.prev_return_id = -1;
932 db_info.expr = expr;
933 db_info.stree = NULL;
934 db_info.handled = 0;
935
936 call_return_states_before_hooks();
937
938 __push_fake_cur_stree();
939 sql_select_return_states("return_id, return, type, parameter, key, value",
940 right, db_assign_return_states_callback, &db_info);
941 if (option_debug) {
942 sm_msg("%s return_id %d return_ranges %s",
943 db_info.cull ? "culled" : "merging",
944 db_info.prev_return_id,
945 db_info.ret_state ? db_info.ret_state->name : "'<empty>'");
946 }
947 if (db_info.handled)
948 call_ranged_return_hooks(&db_info);
949 set_return_assign_state(&db_info);
950 stree = __pop_fake_cur_stree();
951 if (!db_info.cull)
952 merge_fake_stree(&db_info.stree, stree);
953 free_stree(&stree);
954
955 if (!db_info.stree && db_info.cull) { /* this means we culled everything */
956 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
957 set_path_impossible();
958 }
959 FOR_EACH_SM(db_info.stree, sm) {
960 __set_sm(sm);
961 } END_FOR_EACH_SM(sm);
962
963 free_stree(&db_info.stree);
964 call_return_states_after_hooks(right);
965
966 return db_info.handled;
967 }
968
969 static int handle_implied_return(struct expression *expr)
1023 handled = assign_ranged_funcs(fn, expr, call_backs);
1024 handled |= handle_implied_return(expr);
1025
1026
1027 call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
1028
1029 if (handled)
1030 return;
1031
1032 assigned_unknown:
1033 get_absolute_rl(expr->right, &rl);
1034 rl = cast_rl(get_type(expr->left), rl);
1035 set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
1036 }
1037
1038 static int db_return_states_callback(void *_info, int argc, char **argv, char **azColName)
1039 {
1040 struct db_callback_info *db_info = _info;
1041 struct range_list *ret_range;
1042 int type, param;
1043 char *ret_str, *key, *value;
1044 struct return_implies_callback *tmp;
1045 struct stree *stree;
1046 int return_id;
1047 char buf[64];
1048
1049 if (argc != 6)
1050 return 0;
1051
1052 return_id = atoi(argv[0]);
1053 ret_str = argv[1];
1054 type = atoi(argv[2]);
1055 param = atoi(argv[3]);
1056 key = argv[4];
1057 value = argv[5];
1058
1059 if (db_info->prev_return_id != -1 && type == INTERNAL) {
1060 stree = __pop_fake_cur_stree();
1061 if (!db_info->cull)
1062 merge_fake_stree(&db_info->stree, stree);
1063 free_stree(&stree);
1064 __push_fake_cur_stree();
1065 __unnullify_path();
1066 db_info->cull = 0;
1067 }
1068 db_info->prev_return_id = return_id;
1069
1070 if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
1071 db_info->cull = 1;
1072 if (db_info->cull)
1073 return 0;
1074 if (type == CULL_PATH) {
1075 db_info->cull = 1;
1076 return 0;
1077 }
1078 if (is_impossible_data(type, db_info->expr, param, key, value)) {
1079 db_info->cull = 1;
1080 return 0;
1081 }
1082
1083 if (type == PARAM_LIMIT)
1084 param_limit_implications(db_info->expr, param, key, value);
1085
1086 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range);
1087 ret_range = cast_rl(get_type(db_info->expr), ret_range);
1088
1089 if (type == INTERNAL) {
1090 set_state(-1, "unnull_path", NULL, &true_state);
1091 __add_return_comparison(strip_expr(db_info->expr), ret_str);
1092 __add_return_to_param_mapping(db_info->expr, ret_str);
1093 }
1094
1095
1096 FOR_EACH_PTR(db_return_states_list, tmp) {
1097 if (tmp->type == type)
1098 tmp->callback(db_info->expr, param, key, value);
1099 } END_FOR_EACH_PTR(tmp);
1100
1101 /*
1102 * We want to store the return values so that we can split the strees
1103 * in smatch_db.c. This uses set_state() directly because it's not a
1104 * real smatch_extra state.
1105 */
1106 snprintf(buf, sizeof(buf), "return %p", db_info->expr);
1107 set_state(SMATCH_EXTRA, buf, NULL, alloc_estate_rl(ret_range));
1108
1109 return 0;
1110 }
1111
1112 static void db_return_states(struct expression *expr)
|