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