?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
chunk: change the API a bit
[smatch.git] / smatch_extra.c
blobaece83226f3468392b2602b8254883503c447326
1 /*
2 * Copyright (C) 2008 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 * smatch_extra.c is supposed to track the value of every variable.
20 *
21 */
22
23 #include <stdlib.h>
24 #include <errno.h>
25 #ifndef __USE_ISOC99
26 #define __USE_ISOC99
27 #endif
28 #include <limits.h>
29 #include "parse.h"
30 #include "smatch.h"
31 #include "smatch_slist.h"
32 #include "smatch_extra.h"
33
34 static int my_id;
35 static int link_id;
36
37 struct string_list *__ignored_macros = NULL;
38 static int in_warn_on_macro(void)
39 {
40 struct statement *stmt;
41 char *tmp;
42 char *macro;
43
44 stmt = get_current_statement();
45 if (!stmt)
46 return 0;
47 macro = get_macro_name(stmt->pos);
48 if (!macro)
49 return 0;
50
51 FOR_EACH_PTR(__ignored_macros, tmp) {
52 if (!strcmp(tmp, macro))
53 return 1;
54 } END_FOR_EACH_PTR(tmp);
55 return 0;
56 }
57
58 typedef void (mod_hook)(const char *name, struct symbol *sym, struct smatch_state *state);
59 DECLARE_PTR_LIST(void_fn_list, mod_hook *);
60 static struct void_fn_list *extra_mod_hooks;
61 void add_extra_mod_hook(mod_hook *fn)
62 {
63 mod_hook **p = malloc(sizeof(mod_hook *));
64 *p = fn;
65 add_ptr_list(&extra_mod_hooks, p);
66 }
67
68 void call_extra_mod_hooks(const char *name, struct symbol *sym, struct smatch_state *state)
69 {
70 mod_hook **fn;
71
72 FOR_EACH_PTR(extra_mod_hooks, fn) {
73 (*fn)(name, sym, state);
74 } END_FOR_EACH_PTR(fn);
75 }
76
77 struct sm_state *set_extra_mod_helper(const char *name, struct symbol *sym, struct smatch_state *state)
78 {
79 remove_from_equiv(name, sym);
80 call_extra_mod_hooks(name, sym, state);
81 if (__in_fake_assign && estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym))
82 return NULL;
83 return set_state(SMATCH_EXTRA, name, sym, state);
84 }
85
86 static char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym)
87 {
88 struct expression *assigned;
89 char *orig_name = NULL;
90 char buf[256];
91 char *ret = NULL;
92 int skip;
93
94 *new_sym = NULL;
95
96 if (!sym->ident)
97 return NULL;
98
99 skip = strlen(sym->ident->name);
100 if (name[skip] != '-' || name[skip + 1] != '>')
101 return NULL;
102 skip += 2;
103
104 assigned = get_assigned_expr_name_sym(sym->ident->name, sym);
105 if (!assigned)
106 return NULL;
107 if (assigned->type == EXPR_PREOP || assigned->op == '&') {
108
109 orig_name = expr_to_var_sym(assigned, new_sym);
110 if (!orig_name || !*new_sym)
111 goto free;
112
113 snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + skip);
114 ret = alloc_string(buf);
115 free_string(orig_name);
116 return ret;
117 }
118
119 if (assigned->type != EXPR_DEREF)
120 goto free;
121
122 orig_name = expr_to_var_sym(assigned, new_sym);
123 if (!orig_name || !*new_sym)
124 goto free;
125
126 snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + skip);
127 ret = alloc_string(buf);
128 free_string(orig_name);
129 return ret;
130
131 free:
132 free_string(orig_name);
133 return NULL;
134 }
135
136 struct sm_state *set_extra_mod(const char *name, struct symbol *sym, struct smatch_state *state)
137 {
138 char *new_name;
139 struct symbol *new_sym;
140 struct sm_state *sm;
141
142 if (in_warn_on_macro())
143 return NULL;
144 sm = set_extra_mod_helper(name, sym, state);
145 new_name = get_other_name_sym(name, sym, &new_sym);
146 if (new_name && new_sym)
147 set_extra_mod_helper(new_name, new_sym, state);
148 free_string(new_name);
149 return sm;
150 }
151
152 struct sm_state *set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
153 {
154 struct symbol *sym;
155 char *name;
156 struct sm_state *ret = NULL;
157
158 expr = strip_expr(expr);
159 name = expr_to_var_sym(expr, &sym);
160 if (!name || !sym)
161 goto free;
162 ret = set_extra_mod(name, sym, state);
163 free:
164 free_string(name);
165 return ret;
166 }
167
168 void set_extra_nomod(const char *name, struct symbol *sym, struct smatch_state *state)
169 {
170 char *new_name;
171 struct symbol *new_sym;
172 struct relation *rel;
173 struct smatch_state *orig_state;
174
175 orig_state = get_state(SMATCH_EXTRA, name, sym);
176
177 new_name = get_other_name_sym(name, sym, &new_sym);
178 if (new_name && new_sym)
179 set_state(SMATCH_EXTRA, new_name, new_sym, state);
180 free_string(new_name);
181
182 if (!estate_related(orig_state)) {
183 set_state(SMATCH_EXTRA, name, sym, state);
184 return;
185 }
186
187 set_related(state, estate_related(orig_state));
188 FOR_EACH_PTR(estate_related(orig_state), rel) {
189 if (option_debug_related)
190 sm_msg("%s updating related %s to %s", name, rel->name, state->name);
191 set_state(SMATCH_EXTRA, rel->name, rel->sym, state);
192 } END_FOR_EACH_PTR(rel);
193 }
194
195 /*
196 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
197 */
198 void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state)
199 {
200 char *name;
201 struct symbol *sym;
202
203 name = expr_to_var_sym(expr, &sym);
204 if (!name || !sym)
205 goto free;
206 set_extra_nomod(name, sym, state);
207 free:
208 free_string(name);
209
210 }
211
212 static void set_extra_true_false(const char *name, struct symbol *sym,
213 struct smatch_state *true_state,
214 struct smatch_state *false_state)
215 {
216 char *new_name;
217 struct symbol *new_sym;
218 struct relation *rel;
219 struct smatch_state *orig_state;
220
221 if (in_warn_on_macro())
222 return;
223
224 new_name = get_other_name_sym(name, sym, &new_sym);
225 if (new_name && new_sym)
226 set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state);
227 free_string(new_name);
228
229 orig_state = get_state(SMATCH_EXTRA, name, sym);
230
231 if (!estate_related(orig_state)) {
232 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
233 return;
234 }
235
236 if (true_state)
237 set_related(true_state, estate_related(orig_state));
238 if (false_state)
239 set_related(false_state, estate_related(orig_state));
240
241 FOR_EACH_PTR(estate_related(orig_state), rel) {
242 set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym,
243 true_state, false_state);
244 } END_FOR_EACH_PTR(rel);
245 }
246
247 static void set_extra_chunk_true_false(struct expression *expr,
248 struct smatch_state *true_state,
249 struct smatch_state *false_state)
250 {
251 struct var_sym_list *vsl;
252 struct var_sym *vs;
253 struct symbol *type;
254 char *name;
255 struct symbol *sym;
256
257 if (in_warn_on_macro())
258 return;
259
260 type = get_type(expr);
261 if (!type)
262 return;
263
264 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
265 if (!name || !vsl)
266 goto free;
267 FOR_EACH_PTR(vsl, vs) {
268 store_link(link_id, vs->var, vs->sym, name, sym);
269 } END_FOR_EACH_PTR(vs);
270
271 set_true_false_states(SMATCH_EXTRA, name, sym,
272 clone_estate(true_state),
273 clone_estate(false_state));
274 free:
275 free_string(name);
276 }
277
278 static void set_extra_expr_true_false(struct expression *expr,
279 struct smatch_state *true_state,
280 struct smatch_state *false_state)
281 {
282 char *name;
283 struct symbol *sym;
284
285 expr = strip_expr(expr);
286 name = expr_to_var_sym(expr, &sym);
287 if (!name || !sym) {
288 free_string(name);
289 set_extra_chunk_true_false(expr, true_state, false_state);
290 return;
291 }
292 set_extra_true_false(name, sym, true_state, false_state);
293 free_string(name);
294 }
295
296 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
297 {
298 struct expression *iter_var;
299 struct expression *condition;
300 struct sm_state *sm;
301 struct smatch_state *estate;
302 sval_t start;
303
304 condition = strip_expr(loop->iterator_pre_condition);
305 if (!condition)
306 return NULL;
307 if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
308 return NULL;
309 if (condition->op != SPECIAL_DECREMENT)
310 return NULL;
311
312 iter_var = condition->unop;
313 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
314 if (!sm)
315 return NULL;
316 if (sval_cmp_val(estate_min(sm->state), 0) < 0)
317 return NULL;
318 start = estate_max(sm->state);
319 if (sval_cmp_val(start, 0) <= 0)
320 return NULL;
321 if (!sval_is_max(start))
322 start.value--;
323
324 if (condition->type == EXPR_PREOP) {
325 estate = alloc_estate_range(sval_type_val(start.type, 1), start);
326 if (estate_has_hard_max(sm->state))
327 estate_set_hard_max(estate);
328 estate_copy_fuzzy_max(estate, sm->state);
329 set_extra_expr_mod(iter_var, estate);
330 }
331 if (condition->type == EXPR_POSTOP) {
332 estate = alloc_estate_range(sval_type_val(start.type, 0), start);
333 if (estate_has_hard_max(sm->state))
334 estate_set_hard_max(estate);
335 estate_copy_fuzzy_max(estate, sm->state);
336 set_extra_expr_mod(iter_var, estate);
337 }
338 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
339 }
340
341 static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr,
342 struct expression *condition)
343 {
344 struct expression *iter_var;
345 struct sm_state *sm;
346 struct smatch_state *estate;
347 sval_t start, end, max;
348
349 iter_var = iter_expr->unop;
350 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
351 if (!sm)
352 return NULL;
353 if (!estate_get_single_value(sm->state, &start))
354 return NULL;
355 if (get_implied_max(condition->right, &end))
356 end = sval_cast(get_type(iter_var), end);
357 else
358 end = sval_type_max(get_type(iter_var));
359
360 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
361 return NULL;
362
363 switch (condition->op) {
364 case SPECIAL_UNSIGNED_LT:
365 case SPECIAL_NOTEQUAL:
366 case '<':
367 if (!sval_is_min(end))
368 end.value--;
369 break;
370 case SPECIAL_UNSIGNED_LTE:
371 case SPECIAL_LTE:
372 break;
373 default:
374 return NULL;
375 }
376 if (sval_cmp(end, start) < 0)
377 return NULL;
378 estate = alloc_estate_range(start, end);
379 if (get_hard_max(condition->right, &max)) {
380 estate_set_hard_max(estate);
381 if (condition->op == '<' ||
382 condition->op == SPECIAL_UNSIGNED_LT ||
383 condition->op == SPECIAL_NOTEQUAL)
384 max.value--;
385 estate_set_fuzzy_max(estate, max);
386 }
387 set_extra_expr_mod(iter_var, estate);
388 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
389 }
390
391 static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr,
392 struct expression *condition)
393 {
394 struct expression *iter_var;
395 struct sm_state *sm;
396 struct smatch_state *estate;
397 sval_t start, end;
398
399 iter_var = iter_expr->unop;
400 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
401 if (!sm)
402 return NULL;
403 if (!estate_get_single_value(sm->state, &start))
404 return NULL;
405 if (!get_implied_min(condition->right, &end))
406 end = sval_type_min(get_type(iter_var));
407 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
408 return NULL;
409
410 switch (condition->op) {
411 case SPECIAL_NOTEQUAL:
412 case '>':
413 if (!sval_is_min(end) && !sval_is_max(end))
414 end.value++;
415 break;
416 case SPECIAL_GTE:
417 break;
418 default:
419 return NULL;
420 }
421 if (sval_cmp(end, start) > 0)
422 return NULL;
423 estate = alloc_estate_range(end, start);
424 estate_set_hard_max(estate);
425 estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate));
426 set_extra_expr_mod(iter_var, estate);
427 return get_sm_state_expr(SMATCH_EXTRA, iter_var);
428 }
429
430 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
431 {
432 struct expression *iter_expr;
433 struct expression *condition;
434
435 if (!loop->iterator_post_statement)
436 return NULL;
437 if (loop->iterator_post_statement->type != STMT_EXPRESSION)
438 return NULL;
439 iter_expr = loop->iterator_post_statement->expression;
440 if (!loop->iterator_pre_condition)
441 return NULL;
442 if (loop->iterator_pre_condition->type != EXPR_COMPARE)
443 return NULL;
444 condition = loop->iterator_pre_condition;
445
446 if (iter_expr->op == SPECIAL_INCREMENT)
447 return handle_canonical_for_inc(iter_expr, condition);
448 if (iter_expr->op == SPECIAL_DECREMENT)
449 return handle_canonical_for_dec(iter_expr, condition);
450 return NULL;
451 }
452
453 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree)
454 {
455 struct sm_state *ret;
456
457 __push_fake_cur_stree();
458 if (!loop->iterator_post_statement)
459 ret = handle_canonical_while_count_down(loop);
460 else
461 ret = handle_canonical_for_loops(loop);
462 *stree = __pop_fake_cur_stree();
463 return ret;
464 }
465
466 int __iterator_unchanged(struct sm_state *sm)
467 {
468 if (!sm)
469 return 0;
470 if (get_sm_state(my_id, sm->name, sm->sym) == sm)
471 return 1;
472 return 0;
473 }
474
475 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
476 {
477 sval_t after_value;
478
479 /* paranoid checking. prolly not needed */
480 condition = strip_expr(condition);
481 if (!condition)
482 return;
483 if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
484 return;
485 if (condition->op != SPECIAL_DECREMENT)
486 return;
487 after_value = estate_min(sm->state);
488 after_value.value--;
489 set_extra_mod(sm->name, sm->sym, alloc_estate_sval(after_value));
490 }
491
492 void __extra_pre_loop_hook_after(struct sm_state *sm,
493 struct statement *iterator,
494 struct expression *condition)
495 {
496 struct expression *iter_expr;
497 sval_t limit;
498 struct smatch_state *state;
499
500 if (!iterator) {
501 while_count_down_after(sm, condition);
502 return;
503 }
504
505 iter_expr = iterator->expression;
506
507 if (condition->type != EXPR_COMPARE)
508 return;
509 if (iter_expr->op == SPECIAL_INCREMENT) {
510 limit = sval_binop(estate_max(sm->state), '+',
511 sval_type_val(estate_type(sm->state), 1));
512 } else {
513 limit = sval_binop(estate_min(sm->state), '-',
514 sval_type_val(estate_type(sm->state), 1));
515 }
516 if (!estate_has_hard_max(sm->state) && !__has_breaks()) {
517 if (iter_expr->op == SPECIAL_INCREMENT)
518 state = alloc_estate_range(estate_min(sm->state), limit);
519 else
520 state = alloc_estate_range(limit, estate_max(sm->state));
521 } else {
522 state = alloc_estate_sval(limit);
523 }
524 if (!estate_has_hard_max(sm->state)) {
525 estate_clear_hard_max(state);
526 }
527 if (estate_has_fuzzy_max(sm->state)) {
528 sval_t hmax = estate_get_fuzzy_max(sm->state);
529 sval_t max = estate_max(sm->state);
530
531 if (sval_cmp(hmax, max) != 0)
532 estate_clear_fuzzy_max(state);
533 } else if (!estate_has_fuzzy_max(sm->state)) {
534 estate_clear_fuzzy_max(state);
535 }
536
537 set_extra_mod(sm->name, sm->sym, state);
538 }
539
540 static struct stree *unmatched_stree;
541 static struct smatch_state *unmatched_state(struct sm_state *sm)
542 {
543 struct smatch_state *state;
544
545 if (unmatched_stree) {
546 state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym);
547 if (state)
548 return state;
549 }
550 if (parent_is_gone_var_sym(sm->name, sm->sym))
551 return alloc_estate_empty();
552 return alloc_estate_whole(estate_type(sm->state));
553 }
554
555 static void clear_the_pointed_at(struct expression *expr)
556 {
557 struct stree *stree;
558 char *name;
559 struct symbol *sym;
560 struct sm_state *tmp;
561
562 name = expr_to_var_sym(expr, &sym);
563 if (!name || !sym)
564 goto free;
565
566 stree = __get_cur_stree();
567 FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) {
568 if (tmp->name[0] != '*')
569 continue;
570 if (tmp->sym != sym)
571 continue;
572 if (strcmp(tmp->name + 1, name) != 0)
573 continue;
574 set_extra_mod(tmp->name, tmp->sym, alloc_estate_whole(estate_type(tmp->state)));
575 } END_FOR_EACH_SM(tmp);
576
577 free:
578 free_string(name);
579 }
580
581 static void match_function_call(struct expression *expr)
582 {
583 struct expression *arg;
584 struct expression *tmp;
585
586 /* if we have the db this is handled in smatch_function_hooks.c */
587 if (!option_no_db)
588 return;
589 if (inlinable(expr->fn))
590 return;
591
592 FOR_EACH_PTR(expr->args, arg) {
593 tmp = strip_expr(arg);
594 if (tmp->type == EXPR_PREOP && tmp->op == '&')
595 set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop)));
596 else
597 clear_the_pointed_at(tmp);
598 } END_FOR_EACH_PTR(arg);
599 }
600
601 static int types_equiv_or_pointer(struct symbol *one, struct symbol *two)
602 {
603 if (!one || !two)
604 return 0;
605 if (one->type == SYM_PTR && two->type == SYM_PTR)
606 return 1;
607 return types_equiv(one, two);
608 }
609
610 static void save_chunk_info(struct expression *left, struct expression *right)
611 {
612 struct var_sym_list *vsl;
613 struct var_sym *vs;
614 struct expression *add_expr;
615 struct symbol *type;
616 sval_t sval;
617 char *name;
618 struct symbol *sym;
619
620 if (right->type != EXPR_BINOP || right->op != '-')
621 return;
622 if (!get_value(right->left, &sval))
623 return;
624 if (!expr_to_sym(right->right))
625 return;
626
627 add_expr = binop_expression(left, '+', right->right);
628 type = get_type(add_expr);
629 if (!type)
630 return;
631 name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl);
632 if (!name || !vsl)
633 goto free;
634 FOR_EACH_PTR(vsl, vs) {
635 store_link(link_id, vs->var, vs->sym, name, sym);
636 } END_FOR_EACH_PTR(vs);
637
638 set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval)));
639 free:
640 free_string(name);
641 }
642
643 static void match_vanilla_assign(struct expression *left, struct expression *right)
644 {
645 struct range_list *rl = NULL;
646 struct symbol *right_sym;
647 struct symbol *left_type;
648 struct symbol *right_type;
649 char *right_name = NULL;
650 struct symbol *sym;
651 char *name;
652 sval_t max;
653 struct smatch_state *state;
654
655 if (is_struct(left))
656 return;
657
658 save_chunk_info(left, right);
659
660 name = expr_to_var_sym(left, &sym);
661 if (!name)
662 return;
663
664 left_type = get_type(left);
665 right_type = get_type(right);
666
667 right_name = expr_to_var_sym(right, &right_sym);
668
669 if (!__in_fake_assign &&
670 !(right->type == EXPR_PREOP && right->op == '&') &&
671 right_name && right_sym &&
672 types_equiv_or_pointer(left_type, right_type) &&
673 !has_symbol(right, sym)) {
674 set_equiv(left, right);
675 goto free;
676 }
677
678 if (is_pointer(right) && get_address_rl(right, &rl)) {
679 state = alloc_estate_rl(rl);
680 } else if (get_implied_rl(right, &rl)) {
681 rl = cast_rl(left_type, rl);
682 state = alloc_estate_rl(rl);
683 if (get_hard_max(right, &max)) {
684 estate_set_hard_max(state);
685 estate_set_fuzzy_max(state, max);
686 }
687 } else {
688 rl = alloc_whole_rl(right_type);
689 rl = cast_rl(left_type, rl);
690 state = alloc_estate_rl(rl);
691 }
692 set_extra_mod(name, sym, state);
693 free:
694 free_string(right_name);
695 }
696
697 static int op_remove_assign(int op)
698 {
699 switch (op) {
700 case SPECIAL_ADD_ASSIGN:
701 return '+';
702 case SPECIAL_SUB_ASSIGN:
703 return '-';
704 case SPECIAL_MUL_ASSIGN:
705 return '*';
706 case SPECIAL_DIV_ASSIGN:
707 return '/';
708 case SPECIAL_MOD_ASSIGN:
709 return '%';
710 case SPECIAL_AND_ASSIGN:
711 return '&';
712 case SPECIAL_OR_ASSIGN:
713 return '|';
714 case SPECIAL_XOR_ASSIGN:
715 return '^';
716 case SPECIAL_SHL_ASSIGN:
717 return SPECIAL_LEFTSHIFT;
718 case SPECIAL_SHR_ASSIGN:
719 return SPECIAL_RIGHTSHIFT;
720 default:
721 return op;
722 }
723 }
724
725 static void match_assign(struct expression *expr)
726 {
727 struct range_list *rl = NULL;
728 struct expression *left;
729 struct expression *right;
730 struct expression *binop_expr;
731 struct symbol *left_type;
732 struct symbol *right_type;
733 struct symbol *sym;
734 char *name;
735 sval_t left_min, left_max;
736 sval_t right_min, right_max;
737 sval_t res_min, res_max;
738
739 left = strip_expr(expr->left);
740
741 right = strip_parens(expr->right);
742 while (right->type == EXPR_ASSIGNMENT && right->op == '=')
743 right = strip_parens(right->left);
744
745 if (expr->op == '=' && is_condition(expr->right))
746 return; /* handled in smatch_condition.c */
747 if (expr->op == '=' && right->type == EXPR_CALL)
748 return; /* handled in smatch_function_hooks.c */
749 if (expr->op == '=') {
750 match_vanilla_assign(left, right);
751 return;
752 }
753
754 name = expr_to_var_sym(left, &sym);
755 if (!name)
756 return;
757
758 left_type = get_type(left);
759 right_type = get_type(right);
760
761 res_min = sval_type_min(left_type);
762 res_max = sval_type_max(left_type);
763
764 switch (expr->op) {
765 case SPECIAL_ADD_ASSIGN:
766 get_absolute_max(left, &left_max);
767 get_absolute_max(right, &right_max);
768 if (sval_binop_overflows(left_max, '+', right_max))
769 break;
770 if (get_implied_min(left, &left_min) &&
771 !sval_is_negative_min(left_min) &&
772 get_implied_min(right, &right_min) &&
773 !sval_is_negative_min(right_min)) {
774 res_min = sval_binop(left_min, '+', right_min);
775 res_min = sval_cast(right_type, res_min);
776 }
777 if (inside_loop()) /* we are assuming loops don't lead to wrapping */
778 break;
779 res_max = sval_binop(left_max, '+', right_max);
780 res_max = sval_cast(right_type, res_max);
781 break;
782 case SPECIAL_SUB_ASSIGN:
783 if (get_implied_max(left, &left_max) &&
784 !sval_is_max(left_max) &&
785 get_implied_min(right, &right_min) &&
786 !sval_is_min(right_min)) {
787 res_max = sval_binop(left_max, '-', right_min);
788 res_max = sval_cast(right_type, res_max);
789 }
790 if (inside_loop())
791 break;
792 if (get_implied_min(left, &left_min) &&
793 !sval_is_min(left_min) &&
794 get_implied_max(right, &right_max) &&
795 !sval_is_max(right_max)) {
796 res_min = sval_binop(left_min, '-', right_max);
797 res_min = sval_cast(right_type, res_min);
798 }
799 break;
800 case SPECIAL_AND_ASSIGN:
801 case SPECIAL_MOD_ASSIGN:
802 case SPECIAL_SHL_ASSIGN:
803 case SPECIAL_SHR_ASSIGN:
804 case SPECIAL_OR_ASSIGN:
805 case SPECIAL_XOR_ASSIGN:
806 case SPECIAL_MUL_ASSIGN:
807 case SPECIAL_DIV_ASSIGN:
808 binop_expr = binop_expression(expr->left,
809 op_remove_assign(expr->op),
810 expr->right);
811 if (get_absolute_rl(binop_expr, &rl)) {
812 rl = cast_rl(left_type, rl);
813 set_extra_mod(name, sym, alloc_estate_rl(rl));
814 goto free;
815 }
816 break;
817 }
818 rl = cast_rl(left_type, alloc_rl(res_min, res_max));
819 set_extra_mod(name, sym, alloc_estate_rl(rl));
820 free:
821 free_string(name);
822 }
823
824 static struct smatch_state *increment_state(struct smatch_state *state)
825 {
826 sval_t min = estate_min(state);
827 sval_t max = estate_max(state);
828
829 if (!estate_rl(state))
830 return NULL;
831
832 if (inside_loop())
833 max = sval_type_max(max.type);
834
835 if (!sval_is_min(min) && !sval_is_max(min))
836 min.value++;
837 if (!sval_is_min(max) && !sval_is_max(max))
838 max.value++;
839 return alloc_estate_range(min, max);
840 }
841
842 static struct smatch_state *decrement_state(struct smatch_state *state)
843 {
844 sval_t min = estate_min(state);
845 sval_t max = estate_max(state);
846
847 if (!estate_rl(state))
848 return NULL;
849
850 if (inside_loop())
851 min = sval_type_min(min.type);
852
853 if (!sval_is_min(min) && !sval_is_max(min))
854 min.value--;
855 if (!sval_is_min(max) && !sval_is_max(max))
856 max.value--;
857 return alloc_estate_range(min, max);
858 }
859
860 static void unop_expr(struct expression *expr)
861 {
862 struct smatch_state *state;
863
864 if (expr->smatch_flags & Handled)
865 return;
866
867 switch (expr->op) {
868 case SPECIAL_INCREMENT:
869 state = get_state_expr(SMATCH_EXTRA, expr->unop);
870 state = increment_state(state);
871 if (!state)
872 state = alloc_estate_whole(get_type(expr));
873 set_extra_expr_mod(expr->unop, state);
874 break;
875 case SPECIAL_DECREMENT:
876 state = get_state_expr(SMATCH_EXTRA, expr->unop);
877 state = decrement_state(state);
878 if (!state)
879 state = alloc_estate_whole(get_type(expr));
880 set_extra_expr_mod(expr->unop, state);
881 break;
882 default:
883 return;
884 }
885 }
886
887 static void asm_expr(struct statement *stmt)
888 {
889
890 struct expression *expr;
891 struct symbol *type;
892 int state = 0;
893
894 FOR_EACH_PTR(stmt->asm_outputs, expr) {
895 switch (state) {
896 case 0: /* identifier */
897 case 1: /* constraint */
898 state++;
899 continue;
900 case 2: /* expression */
901 state = 0;
902 type = get_type(strip_expr(expr));
903 set_extra_expr_mod(expr, alloc_estate_whole(type));
904 continue;
905 }
906 } END_FOR_EACH_PTR(expr);
907 }
908
909 static void check_dereference(struct expression *expr)
910 {
911 if (outside_of_function())
912 return;
913 set_extra_expr_nomod(expr, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
914 }
915
916 static void match_dereferences(struct expression *expr)
917 {
918 if (expr->type != EXPR_PREOP)
919 return;
920 check_dereference(expr->unop);
921 }
922
923 static void match_pointer_as_array(struct expression *expr)
924 {
925 if (!is_array(expr))
926 return;
927 check_dereference(get_array_base(expr));
928 }
929
930 static void set_param_dereferenced(struct expression *arg, char *key, char *unused)
931 {
932 struct symbol *sym;
933 char *name;
934
935 name = get_variable_from_key(arg, key, &sym);
936 if (!name || !sym)
937 goto free;
938
939 set_extra_nomod(name, sym, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
940
941 free:
942 free_string(name);
943 }
944
945 static sval_t add_one(sval_t sval)
946 {
947 sval.value++;
948 return sval;
949 }
950
951 static sval_t sub_one(sval_t sval)
952 {
953 sval.value--;
954 return sval;
955 }
956
957 static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right)
958 {
959 struct range_list *left_orig;
960 struct range_list *left_true;
961 struct range_list *left_false;
962 struct range_list *right_orig;
963 struct range_list *right_true;
964 struct range_list *right_false;
965 struct smatch_state *left_true_state;
966 struct smatch_state *left_false_state;
967 struct smatch_state *right_true_state;
968 struct smatch_state *right_false_state;
969 sval_t min, max, dummy, hard_max;
970 int left_postop = 0;
971 int right_postop = 0;
972
973 if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) {
974 if (left->type == EXPR_POSTOP) {
975 left->smatch_flags |= Handled;
976 left_postop = left->op;
977 }
978 left = strip_expr(left->unop);
979 }
980 while (left->type == EXPR_ASSIGNMENT)
981 left = strip_expr(left->left);
982
983 if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) {
984 if (right->type == EXPR_POSTOP) {
985 right->smatch_flags |= Handled;
986 right_postop = right->op;
987 }
988 right = strip_expr(right->unop);
989 }
990
991 if (get_implied_rl(left, &left_orig)) {
992 left_orig = cast_rl(type, left_orig);
993 } else {
994 min = sval_type_min(get_type(left));
995 max = sval_type_max(get_type(left));
996 left_orig = cast_rl(type, alloc_rl(min, max));
997 }
998
999 if (get_implied_rl(right, &right_orig)) {
1000 right_orig = cast_rl(type, right_orig);
1001 } else {
1002 min = sval_type_min(get_type(right));
1003 max = sval_type_max(get_type(right));
1004 right_orig = cast_rl(type, alloc_rl(min, max));
1005 }
1006 min = sval_type_min(type);
1007 max = sval_type_max(type);
1008
1009 left_true = clone_rl(left_orig);
1010 left_false = clone_rl(left_orig);
1011 right_true = clone_rl(right_orig);
1012 right_false = clone_rl(right_orig);
1013
1014 switch (op) {
1015 case '<':
1016 case SPECIAL_UNSIGNED_LT:
1017 left_true = remove_range(left_orig, rl_max(right_orig), max);
1018 if (!sval_is_min(rl_min(right_orig))) {
1019 left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
1020 }
1021
1022 right_true = remove_range(right_orig, min, rl_min(left_orig));
1023 if (!sval_is_max(rl_max(left_orig)))
1024 right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
1025 break;
1026 case SPECIAL_UNSIGNED_LTE:
1027 case SPECIAL_LTE:
1028 if (!sval_is_max(rl_max(right_orig)))
1029 left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1030 left_false = remove_range(left_orig, min, rl_min(right_orig));
1031
1032 if (!sval_is_min(rl_min(left_orig)))
1033 right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1034 right_false = remove_range(right_orig, rl_max(left_orig), max);
1035
1036 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1037 left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
1038 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1039 right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
1040 break;
1041 case SPECIAL_EQUAL:
1042 if (!sval_is_max(rl_max(right_orig))) {
1043 left_true = remove_range(left_true, add_one(rl_max(right_orig)), max);
1044 }
1045 if (!sval_is_min(rl_min(right_orig))) {
1046 left_true = remove_range(left_true, min, sub_one(rl_min(right_orig)));
1047 }
1048 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1049 left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1050
1051 if (!sval_is_max(rl_max(left_orig)))
1052 right_true = remove_range(right_true, add_one(rl_max(left_orig)), max);
1053 if (!sval_is_min(rl_min(left_orig)))
1054 right_true = remove_range(right_true, min, sub_one(rl_min(left_orig)));
1055 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1056 right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1057 break;
1058 case SPECIAL_UNSIGNED_GTE:
1059 case SPECIAL_GTE:
1060 if (!sval_is_min(rl_min(right_orig)))
1061 left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
1062 left_false = remove_range(left_orig, rl_max(right_orig), max);
1063
1064 if (!sval_is_max(rl_max(left_orig)))
1065 right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
1066 right_false = remove_range(right_orig, min, rl_min(left_orig));
1067
1068 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1069 right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
1070 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1071 left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
1072 break;
1073 case '>':
1074 case SPECIAL_UNSIGNED_GT:
1075 left_true = remove_range(left_orig, min, rl_min(right_orig));
1076 if (!sval_is_max(rl_max(right_orig)))
1077 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1078
1079 right_true = remove_range(right_orig, rl_max(left_orig), max);
1080 if (!sval_is_min(rl_min(left_orig)))
1081 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1082 break;
1083 case SPECIAL_NOTEQUAL:
1084 if (!sval_is_max(rl_max(right_orig)))
1085 left_false = remove_range(left_false, add_one(rl_max(right_orig)), max);
1086 if (!sval_is_min(rl_min(right_orig)))
1087 left_false = remove_range(left_false, min, sub_one(rl_min(right_orig)));
1088 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1089 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1090
1091 if (!sval_is_max(rl_max(left_orig)))
1092 right_false = remove_range(right_false, add_one(rl_max(left_orig)), max);
1093 if (!sval_is_min(rl_min(left_orig)))
1094 right_false = remove_range(right_false, min, sub_one(rl_min(left_orig)));
1095 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1096 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1097 break;
1098 default:
1099 return;
1100 }
1101
1102 left_true = rl_truncate_cast(get_type(left), left_true);
1103 left_false = rl_truncate_cast(get_type(left), left_false);
1104 right_true = rl_truncate_cast(get_type(right), right_true);
1105 right_false = rl_truncate_cast(get_type(right), right_false);
1106
1107 left_true_state = alloc_estate_rl(left_true);
1108 left_false_state = alloc_estate_rl(left_false);
1109 right_true_state = alloc_estate_rl(right_true);
1110 right_false_state = alloc_estate_rl(right_false);
1111
1112 switch (op) {
1113 case '<':
1114 case SPECIAL_UNSIGNED_LT:
1115 case SPECIAL_UNSIGNED_LTE:
1116 case SPECIAL_LTE:
1117 if (get_hard_max(right, &dummy))
1118 estate_set_hard_max(left_true_state);
1119 if (get_hard_max(left, &dummy))
1120 estate_set_hard_max(right_false_state);
1121 break;
1122 case '>':
1123 case SPECIAL_UNSIGNED_GT:
1124 case SPECIAL_UNSIGNED_GTE:
1125 case SPECIAL_GTE:
1126 if (get_hard_max(left, &dummy))
1127 estate_set_hard_max(right_true_state);
1128 if (get_hard_max(right, &dummy))
1129 estate_set_hard_max(left_false_state);
1130 break;
1131 }
1132
1133 switch (op) {
1134 case '<':
1135 case SPECIAL_UNSIGNED_LT:
1136 case SPECIAL_UNSIGNED_LTE:
1137 case SPECIAL_LTE:
1138 if (get_hard_max(right, &hard_max)) {
1139 if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1140 hard_max.value--;
1141 estate_set_fuzzy_max(left_true_state, hard_max);
1142 }
1143 if (get_implied_value(right, &hard_max)) {
1144 if (op == SPECIAL_UNSIGNED_LTE ||
1145 op == SPECIAL_LTE)
1146 hard_max.value++;
1147 estate_set_fuzzy_max(left_false_state, hard_max);
1148 }
1149 if (get_hard_max(left, &hard_max)) {
1150 if (op == SPECIAL_UNSIGNED_LTE ||
1151 op == SPECIAL_LTE)
1152 hard_max.value--;
1153 estate_set_fuzzy_max(right_false_state, hard_max);
1154 }
1155 if (get_implied_value(left, &hard_max)) {
1156 if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1157 hard_max.value++;
1158 estate_set_fuzzy_max(right_true_state, hard_max);
1159 }
1160 break;
1161 case '>':
1162 case SPECIAL_UNSIGNED_GT:
1163 case SPECIAL_UNSIGNED_GTE:
1164 case SPECIAL_GTE:
1165 if (get_hard_max(left, &hard_max)) {
1166 if (op == '>' || op == SPECIAL_UNSIGNED_GT)
1167 hard_max.value--;
1168 estate_set_fuzzy_max(right_true_state, hard_max);
1169 }
1170 if (get_implied_value(left, &hard_max)) {
1171 if (op == SPECIAL_UNSIGNED_GTE ||
1172 op == SPECIAL_GTE)
1173 hard_max.value++;
1174 estate_set_fuzzy_max(right_false_state, hard_max);
1175 }
1176 if (get_hard_max(right, &hard_max)) {
1177 if (op == SPECIAL_UNSIGNED_LTE ||
1178 op == SPECIAL_LTE)
1179 hard_max.value--;
1180 estate_set_fuzzy_max(left_false_state, hard_max);
1181 }
1182 if (get_implied_value(right, &hard_max)) {
1183 if (op == '>' ||
1184 op == SPECIAL_UNSIGNED_GT)
1185 hard_max.value++;
1186 estate_set_fuzzy_max(left_true_state, hard_max);
1187 }
1188 break;
1189 case SPECIAL_EQUAL:
1190 if (get_hard_max(left, &hard_max))
1191 estate_set_fuzzy_max(right_true_state, hard_max);
1192 if (get_hard_max(right, &hard_max))
1193 estate_set_fuzzy_max(left_true_state, hard_max);
1194 break;
1195 }
1196
1197 if (get_hard_max(left, &hard_max)) {
1198 estate_set_hard_max(left_true_state);
1199 estate_set_hard_max(left_false_state);
1200 }
1201 if (get_hard_max(right, &hard_max)) {
1202 estate_set_hard_max(right_true_state);
1203 estate_set_hard_max(right_false_state);
1204 }
1205
1206 if (left_postop == SPECIAL_INCREMENT) {
1207 left_true_state = increment_state(left_true_state);
1208 left_false_state = increment_state(left_false_state);
1209 }
1210 if (left_postop == SPECIAL_DECREMENT) {
1211 left_true_state = decrement_state(left_true_state);
1212 left_false_state = decrement_state(left_false_state);
1213 }
1214 if (right_postop == SPECIAL_INCREMENT) {
1215 right_true_state = increment_state(right_true_state);
1216 right_false_state = increment_state(right_false_state);
1217 }
1218 if (right_postop == SPECIAL_DECREMENT) {
1219 right_true_state = decrement_state(right_true_state);
1220 right_false_state = decrement_state(right_false_state);
1221 }
1222
1223 if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) {
1224 left_true_state = NULL;
1225 left_false_state = NULL;
1226 }
1227
1228 if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) {
1229 right_true_state = NULL;
1230 right_false_state = NULL;
1231 }
1232
1233 set_extra_expr_true_false(left, left_true_state, left_false_state);
1234 set_extra_expr_true_false(right, right_true_state, right_false_state);
1235 }
1236
1237 static int is_simple_math(struct expression *expr)
1238 {
1239 if (!expr)
1240 return 0;
1241 if (expr->type != EXPR_BINOP)
1242 return 0;
1243 switch (expr->op) {
1244 case '+':
1245 case '-':
1246 case '*':
1247 return 1;
1248 }
1249 return 0;
1250 }
1251
1252 static void move_known_values(struct expression **left_p, struct expression **right_p)
1253 {
1254 struct expression *left = *left_p;
1255 struct expression *right = *right_p;
1256 sval_t sval;
1257
1258 if (get_implied_value(left, &sval)) {
1259 if (!is_simple_math(right))
1260 return;
1261 if (right->op == '*') {
1262 sval_t divisor;
1263
1264 if (!get_value(right->right, &divisor))
1265 return;
1266 if (divisor.value == 0 && sval.value % divisor.value)
1267 return;
1268 *left_p = binop_expression(left, invert_op(right->op), right->right);
1269 *right_p = right->left;
1270 return;
1271 }
1272 if (right->op == '+' && get_value(right->left, &sval)) {
1273 *left_p = binop_expression(left, invert_op(right->op), right->left);
1274 *right_p = right->right;
1275 return;
1276 }
1277 if (get_value(right->right, &sval)) {
1278 *left_p = binop_expression(left, invert_op(right->op), right->right);
1279 *right_p = right->left;
1280 return;
1281 }
1282 return;
1283 }
1284 if (get_implied_value(right, &sval)) {
1285 if (!is_simple_math(left))
1286 return;
1287 if (left->op == '*') {
1288 sval_t divisor;
1289
1290 if (!get_value(left->right, &divisor))
1291 return;
1292 if (divisor.value == 0 && sval.value % divisor.value)
1293 return;
1294 *right_p = binop_expression(right, invert_op(left->op), left->right);
1295 *left_p = left->left;
1296 return;
1297 }
1298 if (left->op == '+' && get_value(left->left, &sval)) {
1299 *right_p = binop_expression(right, invert_op(left->op), left->left);
1300 *left_p = left->right;
1301 return;
1302 }
1303
1304 if (get_value(left->right, &sval)) {
1305 *right_p = binop_expression(right, invert_op(left->op), left->right);
1306 *left_p = left->left;
1307 return;
1308 }
1309 return;
1310 }
1311 }
1312
1313 static int match_func_comparison(struct expression *expr)
1314 {
1315 struct expression *left = strip_expr(expr->left);
1316 struct expression *right = strip_expr(expr->right);
1317 sval_t sval;
1318
1319 /*
1320 * fixme: think about this harder. We should always be trying to limit
1321 * the non-call side as well. If we can't determine the limitter does
1322 * that mean we aren't querying the database and are missing important
1323 * information?
1324 */
1325
1326 if (left->type == EXPR_CALL) {
1327 if (get_implied_value(left, &sval)) {
1328 handle_comparison(get_type(expr), left, expr->op, right);
1329 return 1;
1330 }
1331 function_comparison(left, expr->op, right);
1332 return 1;
1333 }
1334
1335 if (right->type == EXPR_CALL) {
1336 if (get_implied_value(right, &sval)) {
1337 handle_comparison(get_type(expr), left, expr->op, right);
1338 return 1;
1339 }
1340 function_comparison(left, expr->op, right);
1341 return 1;
1342 }
1343
1344 return 0;
1345 }
1346
1347 static void match_comparison(struct expression *expr)
1348 {
1349 struct expression *left_orig = strip_expr(expr->left);
1350 struct expression *right_orig = strip_expr(expr->right);
1351 struct expression *left, *right;
1352 struct expression *prev;
1353 struct symbol *type;
1354
1355 if (match_func_comparison(expr))
1356 return;
1357
1358 type = get_type(expr);
1359 if (!type)
1360 type = &llong_ctype;
1361
1362 left = left_orig;
1363 right = right_orig;
1364 move_known_values(&left, &right);
1365 handle_comparison(type, left, expr->op, right);
1366
1367 prev = get_assigned_expr(left_orig);
1368 if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) {
1369 left = prev;
1370 right = right_orig;
1371 move_known_values(&left, &right);
1372 handle_comparison(type, left, expr->op, right);
1373 }
1374
1375 prev = get_assigned_expr(right_orig);
1376 if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) {
1377 left = left_orig;
1378 right = prev;
1379 move_known_values(&left, &right);
1380 handle_comparison(type, left, expr->op, right);
1381 }
1382 }
1383
1384 static void handle_AND_condition(struct expression *expr)
1385 {
1386 struct range_list *rl = NULL;
1387 sval_t known;
1388
1389 if (get_implied_value(expr->left, &known) && known.value > 0) {
1390 known.value--;
1391 get_absolute_rl(expr->right, &rl);
1392 rl = remove_range(rl, sval_type_val(known.type, 0), known);
1393 set_extra_expr_true_false(expr->right, alloc_estate_rl(rl), NULL);
1394 return;
1395 }
1396
1397 if (get_implied_value(expr->right, &known) && known.value > 0) {
1398 known.value--;
1399 get_absolute_rl(expr->left, &rl);
1400 rl = remove_range(rl, sval_type_val(known.type, 0), known);
1401 set_extra_expr_true_false(expr->left, alloc_estate_rl(rl), NULL);
1402 return;
1403 }
1404 }
1405
1406 /* this is actually hooked from smatch_implied.c... it's hacky, yes */
1407 void __extra_match_condition(struct expression *expr)
1408 {
1409 struct symbol *sym;
1410 char *name;
1411 struct smatch_state *pre_state;
1412 struct smatch_state *true_state;
1413 struct smatch_state *false_state;
1414
1415 expr = strip_expr(expr);
1416 switch (expr->type) {
1417 case EXPR_CALL:
1418 function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr());
1419 return;
1420 case EXPR_PREOP:
1421 case EXPR_SYMBOL:
1422 case EXPR_DEREF: {
1423 sval_t zero;
1424
1425 zero = sval_blank(expr);
1426 zero.value = 0;
1427
1428 name = expr_to_var_sym(expr, &sym);
1429 if (!name)
1430 return;
1431 pre_state = get_state(my_id, name, sym);
1432 true_state = estate_filter_sval(pre_state, zero);
1433 if (possibly_true(expr, SPECIAL_EQUAL, zero_expr()))
1434 false_state = alloc_estate_sval(zero);
1435 else
1436 false_state = alloc_estate_empty();
1437 set_extra_true_false(name, sym, true_state, false_state);
1438 free_string(name);
1439 return;
1440 }
1441 case EXPR_COMPARE:
1442 match_comparison(expr);
1443 return;
1444 case EXPR_ASSIGNMENT:
1445 __extra_match_condition(expr->left);
1446 return;
1447 case EXPR_BINOP:
1448 if (expr->op == '&')
1449 handle_AND_condition(expr);
1450 return;
1451 }
1452 }
1453
1454 static void assume_indexes_are_valid(struct expression *expr)
1455 {
1456 struct expression *array_expr;
1457 int array_size;
1458 struct expression *offset;
1459 struct symbol *offset_type;
1460 struct range_list *rl_before;
1461 struct range_list *rl_after;
1462 struct range_list *filter = NULL;
1463 sval_t size;
1464
1465 expr = strip_expr(expr);
1466 if (!is_array(expr))
1467 return;
1468
1469 offset = get_array_offset(expr);
1470 offset_type = get_type(offset);
1471 if (offset_type && type_signed(offset_type)) {
1472 filter = alloc_rl(sval_type_min(offset_type),
1473 sval_type_val(offset_type, -1));
1474 }
1475
1476 array_expr = get_array_base(expr);
1477 array_size = get_real_array_size(array_expr);
1478 if (array_size > 1) {
1479 size = sval_type_val(offset_type, array_size);
1480 add_range(&filter, size, sval_type_max(offset_type));
1481 }
1482
1483 if (!filter)
1484 return;
1485 get_absolute_rl(offset, &rl_before);
1486 rl_after = rl_filter(rl_before, filter);
1487 if (rl_equiv(rl_before, rl_after))
1488 return;
1489 set_extra_expr_nomod(offset, alloc_estate_rl(rl_after));
1490 }
1491
1492 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
1493 int implied_not_equal(struct expression *expr, long long val)
1494 {
1495 return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val));
1496 }
1497
1498 int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val)
1499 {
1500 struct smatch_state *estate;
1501
1502 estate = get_state(SMATCH_EXTRA, name, sym);
1503 if (!estate)
1504 return 0;
1505 if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0)))
1506 return 1;
1507 return 0;
1508 }
1509
1510 int parent_is_null_var_sym(const char *name, struct symbol *sym)
1511 {
1512 char buf[256];
1513 char *start;
1514 char *end;
1515 struct smatch_state *state;
1516
1517 strncpy(buf, name, sizeof(buf) - 1);
1518 buf[sizeof(buf) - 1] = '\0';
1519
1520 start = &buf[0];
1521 while (*start == '*') {
1522 start++;
1523 state = get_state(SMATCH_EXTRA, start, sym);
1524 if (!state)
1525 continue;
1526 if (!estate_rl(state))
1527 return 1;
1528 if (estate_min(state).value == 0 &&
1529 estate_max(state).value == 0)
1530 return 1;
1531 }
1532
1533 start = &buf[0];
1534 while (*start == '&')
1535 start++;
1536
1537 while ((end = strrchr(start, '-'))) {
1538 *end = '\0';
1539 state = get_state(SMATCH_EXTRA, start, sym);
1540 if (!state)
1541 continue;
1542 if (estate_min(state).value == 0 &&
1543 estate_max(state).value == 0)
1544 return 1;
1545 }
1546 return 0;
1547 }
1548
1549 int parent_is_null(struct expression *expr)
1550 {
1551 struct symbol *sym;
1552 char *var;
1553 int ret = 0;
1554
1555 expr = strip_expr(expr);
1556 var = expr_to_var_sym(expr, &sym);
1557 if (!var || !sym)
1558 goto free;
1559 ret = parent_is_null_var_sym(var, sym);
1560 free:
1561 free_string(var);
1562 return ret;
1563 }
1564
1565 static int param_used_callback(void *found, int argc, char **argv, char **azColName)
1566 {
1567 *(int *)found = 1;
1568 return 0;
1569 }
1570
1571 static int filter_unused_kzalloc_info(struct expression *call, int param, char *printed_name, struct sm_state *sm)
1572 {
1573 sval_t sval;
1574 int found = 0;
1575
1576 /* for function pointers assume everything is used */
1577 if (call->fn->type != EXPR_SYMBOL)
1578 return 0;
1579
1580 /*
1581 * kzalloc() information is treated as special because so there is just
1582 * a lot of stuff initialized to zero and it makes building the database
1583 * take hours and hours.
1584 *
1585 * In theory, we should just remove this line and not pass any unused
1586 * information, but I'm not sure enough that this code works so I want
1587 * to hold off on that for now.
1588 */
1589 if (!estate_get_single_value(sm->state, &sval) || sval.value != 0)
1590 return 0;
1591
1592 run_sql(&param_used_callback, &found,
1593 "select * from call_implies where %s and type = %d and parameter = %d and key = '%s';",
1594 get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name);
1595 if (found)
1596 return 0;
1597
1598 /* If the database is not built yet, then assume everything is used */
1599 run_sql(&param_used_callback, &found,
1600 "select * from call_implies where %s and type = %d;",
1601 get_static_filter(call->fn->symbol), PARAM_USED);
1602 if (!found)
1603 return 0;
1604
1605 return 1;
1606 }
1607
1608 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
1609 {
1610 if (estate_is_whole(sm->state))
1611 return;
1612 if (filter_unused_kzalloc_info(call, param, printed_name, sm))
1613 return;
1614 sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, sm->state->name);
1615 if (estate_has_fuzzy_max(sm->state))
1616 sql_insert_caller_info(call, FUZZY_MAX, param, printed_name,
1617 sval_to_str(estate_get_fuzzy_max(sm->state)));
1618 }
1619
1620 static void db_limited_before(void)
1621 {
1622 unmatched_stree = clone_stree(__get_cur_stree());
1623 }
1624
1625 static void db_limited_after(void)
1626 {
1627 free_stree(&unmatched_stree);
1628 }
1629
1630 static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op)
1631 {
1632 struct expression *arg;
1633 char *name;
1634 struct symbol *sym;
1635 struct sm_state *sm;
1636 struct symbol *compare_type, *var_type;
1637 struct range_list *rl;
1638 struct range_list *limit;
1639 struct range_list *new;
1640
1641 while (expr->type == EXPR_ASSIGNMENT)
1642 expr = strip_expr(expr->right);
1643 if (expr->type != EXPR_CALL)
1644 return;
1645
1646 arg = get_argument_from_call_expr(expr->args, param);
1647 if (!arg)
1648 return;
1649
1650 name = get_variable_from_key(arg, key, &sym);
1651 if (!name || !sym)
1652 goto free;
1653
1654 if (strcmp(key, "$") == 0)
1655 compare_type = get_arg_type(expr->fn, param);
1656 else
1657 compare_type = get_member_type_from_key(arg, key);
1658
1659 sm = get_sm_state(SMATCH_EXTRA, name, sym);
1660 if (sm)
1661 rl = estate_rl(sm->state);
1662 else
1663 rl = alloc_whole_rl(compare_type);
1664
1665 call_results_to_rl(expr, compare_type, value, &limit);
1666 new = rl_intersection(rl, limit);
1667
1668 var_type = get_member_type_from_key(arg, key);
1669 new = cast_rl(var_type, new);
1670
1671 /* We want to preserve the implications here */
1672 if (sm && rl_equiv(estate_rl(sm->state), new))
1673 __set_sm(sm);
1674 else {
1675 if (op == PARAM_LIMIT)
1676 set_extra_nomod(name, sym, alloc_estate_rl(new));
1677 else
1678 set_extra_mod(name, sym, alloc_estate_rl(new));
1679 }
1680
1681 free:
1682 free_string(name);
1683 }
1684
1685 static void db_param_limit(struct expression *expr, int param, char *key, char *value)
1686 {
1687 db_param_limit_filter(expr, param, key, value, PARAM_LIMIT);
1688 }
1689
1690 static void db_param_filter(struct expression *expr, int param, char *key, char *value)
1691 {
1692 db_param_limit_filter(expr, param, key, value, PARAM_FILTER);
1693 }
1694
1695 static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op)
1696 {
1697 struct expression *arg;
1698 char *name;
1699 struct symbol *sym;
1700 struct symbol *type;
1701 struct smatch_state *state;
1702 struct range_list *new = NULL;
1703 struct range_list *added = NULL;
1704
1705 while (expr->type == EXPR_ASSIGNMENT)
1706 expr = strip_expr(expr->right);
1707 if (expr->type != EXPR_CALL)
1708 return;
1709
1710 arg = get_argument_from_call_expr(expr->args, param);
1711 if (!arg)
1712 return;
1713 type = get_member_type_from_key(arg, key);
1714 name = get_variable_from_key(arg, key, &sym);
1715 if (!name || !sym)
1716 goto free;
1717
1718 state = get_state(SMATCH_EXTRA, name, sym);
1719 if (state)
1720 new = estate_rl(state);
1721
1722 call_results_to_rl(expr, type, value, &added);
1723
1724 if (op == PARAM_SET)
1725 new = added;
1726 else
1727 new = rl_union(new, added);
1728
1729 set_extra_mod(name, sym, alloc_estate_rl(new));
1730 free:
1731 free_string(name);
1732 }
1733
1734 static void db_param_add(struct expression *expr, int param, char *key, char *value)
1735 {
1736 db_param_add_set(expr, param, key, value, PARAM_ADD);
1737 }
1738
1739 static void db_param_set(struct expression *expr, int param, char *key, char *value)
1740 {
1741 db_param_add_set(expr, param, key, value, PARAM_SET);
1742 }
1743
1744 static void db_returned_member_info(struct expression *expr, int param, char *key, char *value)
1745 {
1746 struct symbol *type;
1747 struct symbol *sym;
1748 char *name;
1749 struct range_list *rl;
1750
1751 if (expr->type != EXPR_ASSIGNMENT)
1752 return;
1753
1754 name = return_state_to_var_sym(expr, param, key, &sym);
1755 if (!name || !sym)
1756 goto free;
1757 type = get_member_type_from_key(expr->left, key);
1758 if (!type)
1759 return;
1760 call_results_to_rl(expr->right, type, value, &rl);
1761 set_extra_mod(name, sym, alloc_estate_rl(rl));
1762
1763 free:
1764 free_string(name);
1765 }
1766
1767 static char *in_terms_of_param_math(struct expression *expr, char *printed_name)
1768 {
1769 struct symbol *sym;
1770 char *var;
1771 char buf[256];
1772 char *ret = NULL;
1773
1774 var = expr_to_var_sym(expr, &sym);
1775 if (!var || !sym)
1776 goto free;
1777 snprintf(buf, sizeof(buf), "%s%s", var, printed_name + 2);
1778
1779 ret = get_value_in_terms_of_parameter_math_var_sym(buf, sym);
1780
1781 free:
1782 free_string(var);
1783 return ret;
1784 }
1785
1786 static void returned_member_callback(int return_id, char *return_ranges, struct expression *expr, char *printed_name, struct smatch_state *state)
1787 {
1788 char buf[256];
1789 char *math_str;
1790 sval_t sval;
1791
1792 /* these are handled in smatch_param_filter/set/limit.c */
1793 if (printed_name[0] != '*' &&
1794 !strchr(printed_name, '.') && !strchr(printed_name, '-'))
1795 return;
1796
1797 if (estate_get_single_value(state, &sval)) {
1798 sql_insert_return_states(return_id, return_ranges, RETURN_VALUE, -1,
1799 printed_name, sval_to_str(sval));
1800 return;
1801 }
1802
1803 math_str = in_terms_of_param_math(expr, printed_name);
1804 if (math_str) {
1805 snprintf(buf, sizeof(buf), "%s[%s]", state->name, math_str);
1806 sql_insert_return_states(return_id, return_ranges, RETURN_VALUE, -1,
1807 printed_name, buf);
1808 return;
1809 }
1810
1811 if (estate_is_whole(state))
1812 return;
1813
1814 sql_insert_return_states(return_id, return_ranges, RETURN_VALUE, -1,
1815 printed_name, state->name);
1816 }
1817
1818 static void match_call_info(struct expression *expr)
1819 {
1820 struct smatch_state *state;
1821 struct range_list *rl = NULL;
1822 struct expression *arg;
1823 struct symbol *type;
1824 int i = 0;
1825
1826 FOR_EACH_PTR(expr->args, arg) {
1827 type = get_arg_type(expr->fn, i);
1828
1829 if (get_implied_rl(arg, &rl))
1830 rl = cast_rl(type, rl);
1831 else
1832 rl = cast_rl(type, alloc_whole_rl(get_type(arg)));
1833
1834 if (!is_whole_rl(rl))
1835 sql_insert_caller_info(expr, PARAM_VALUE, i, "$", show_rl(rl));
1836 state = get_state_expr(SMATCH_EXTRA, arg);
1837 if (estate_has_fuzzy_max(state)) {
1838 sql_insert_caller_info(expr, FUZZY_MAX, i, "$",
1839 sval_to_str(estate_get_fuzzy_max(state)));
1840 }
1841 i++;
1842 } END_FOR_EACH_PTR(arg);
1843 }
1844
1845 static void set_param_value(const char *name, struct symbol *sym, char *key, char *value)
1846 {
1847 struct range_list *rl = NULL;
1848 struct smatch_state *state;
1849 struct symbol *type;
1850 char fullname[256];
1851
1852 if (strcmp(key, "*$") == 0)
1853 snprintf(fullname, sizeof(fullname), "*%s", name);
1854 else if (strncmp(key, "$", 1) == 0)
1855 snprintf(fullname, 256, "%s%s", name, key + 1);
1856 else
1857 return;
1858
1859 type = get_member_type_from_key(symbol_expression(sym), key);
1860 str_to_rl(type, value, &rl);
1861 state = alloc_estate_rl(rl);
1862 set_state(SMATCH_EXTRA, fullname, sym, state);
1863 }
1864
1865 static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value)
1866 {
1867 struct range_list *rl = NULL;
1868 struct smatch_state *state;
1869 struct symbol *type;
1870 char fullname[256];
1871 sval_t max;
1872
1873 if (strcmp(key, "*$") == 0)
1874 snprintf(fullname, sizeof(fullname), "*%s", name);
1875 else if (strncmp(key, "$", 1) == 0)
1876 snprintf(fullname, 256, "%s%s", name, key + 1);
1877 else
1878 return;
1879
1880 state = get_state(SMATCH_EXTRA, fullname, sym);
1881 if (!state)
1882 return;
1883 type = get_member_type_from_key(symbol_expression(sym), key);
1884 str_to_rl(type, value, &rl);
1885 if (!rl_to_sval(rl, &max))
1886 return;
1887 estate_set_fuzzy_max(state, max);
1888 }
1889
1890 struct smatch_state *get_extra_state(struct expression *expr)
1891 {
1892 char *name;
1893 struct symbol *sym;
1894 struct smatch_state *ret = NULL;
1895 struct range_list *rl;
1896
1897 if (is_pointer(expr) && get_address_rl(expr, &rl))
1898 return alloc_estate_rl(rl);
1899
1900 name = expr_to_known_chunk_sym(expr, &sym);
1901 if (!name || !sym)
1902 goto free;
1903
1904 ret = get_state(SMATCH_EXTRA, name, sym);
1905 free:
1906 free_string(name);
1907 return ret;
1908 }
1909
1910 void register_smatch_extra(int id)
1911 {
1912 my_id = id;
1913
1914 add_merge_hook(my_id, &merge_estates);
1915 add_unmatched_state_hook(my_id, &unmatched_state);
1916 select_caller_info_hook(set_param_value, PARAM_VALUE);
1917 select_caller_info_hook(set_param_hard_max, FUZZY_MAX);
1918 select_return_states_hook(RETURN_VALUE, &db_returned_member_info);
1919 select_return_states_before(&db_limited_before);
1920 select_return_states_hook(PARAM_LIMIT, &db_param_limit);
1921 select_return_states_hook(PARAM_FILTER, &db_param_filter);
1922 select_return_states_hook(PARAM_ADD, &db_param_add);
1923 select_return_states_hook(PARAM_SET, &db_param_set);
1924 select_return_states_after(&db_limited_after);
1925 }
1926
1927 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
1928 {
1929 struct var_sym_list *links;
1930 struct var_sym *tmp;
1931 struct smatch_state *state;
1932
1933 links = sm->state->data;
1934
1935 FOR_EACH_PTR(links, tmp) {
1936 state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym);
1937 if (!state)
1938 continue;
1939 set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state)));
1940 } END_FOR_EACH_PTR(tmp);
1941 set_state(link_id, sm->name, sm->sym, &undefined);
1942 }
1943
1944 void register_smatch_extra_links(int id)
1945 {
1946 link_id = id;
1947 }
1948
1949 void register_smatch_extra_late(int id)
1950 {
1951 add_merge_hook(link_id, &merge_link_states);
1952 add_modification_hook(link_id, &match_link_modify);
1953 add_hook(&match_dereferences, DEREF_HOOK);
1954 add_hook(&match_pointer_as_array, OP_HOOK);
1955 select_call_implies_hook(DEREFERENCE, &set_param_dereferenced);
1956 add_hook(&match_function_call, FUNCTION_CALL_HOOK);
1957 add_hook(&match_assign, ASSIGNMENT_HOOK);
1958 add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK);
1959 add_hook(&unop_expr, OP_HOOK);
1960 add_hook(&asm_expr, ASM_HOOK);
1961
1962 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
1963 add_member_info_callback(my_id, struct_member_callback);
1964 add_returned_member_callback(my_id, returned_member_callback);
1965
1966 add_hook(&assume_indexes_are_valid, OP_HOOK);
1967 }
Static analysis for C