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