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