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