?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
function_hooks: don't call db_return_states() early
[smatch.git] / smatch_comparison.c
blob7490ed173e57a8735a53a43d7fe14aa9cce926b5
1 /*
2 * Copyright (C) 2012 Oracle.
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 * The point here is to store the relationships between two variables.
20 * Ie: y > x.
21 * To do that we create a state with the two variables in alphabetical order:
22 * ->name = "x vs y" and the state would be "<". On the false path the state
23 * would be ">=".
24 *
25 * Part of the trick of it is that if x or y is modified then we need to reset
26 * the state. We need to keep a list of all the states which depend on x and
27 * all the states which depend on y. The link_id code handles this.
28 *
29 */
30
31 #include "smatch.h"
32 #include "smatch_extra.h"
33 #include "smatch_slist.h"
34
35 int comparison_id;
36 static int link_id;
37 static int inc_dec_id;
38 static int inc_dec_link_id;
39
40 static void add_comparison(struct expression *left, int comparison, struct expression *right);
41
42 /* for handling for loops */
43 STATE(start);
44 STATE(incremented);
45
46 ALLOCATOR(compare_data, "compare data");
47
48 static struct symbol *vsl_to_sym(struct var_sym_list *vsl)
49 {
50 struct var_sym *vs;
51
52 if (!vsl)
53 return NULL;
54 if (ptr_list_size((struct ptr_list *)vsl) != 1)
55 return NULL;
56 vs = first_ptr_list((struct ptr_list *)vsl);
57 return vs->sym;
58 }
59
60 static const char *show_comparison(int comparison)
61 {
62 if (comparison == IMPOSSIBLE_COMPARISON)
63 return "impossible";
64 if (comparison == UNKNOWN_COMPARISON)
65 return "unknown";
66 return show_special(comparison);
67 }
68
69 struct smatch_state *alloc_compare_state(
70 struct expression *left,
71 const char *left_var, struct var_sym_list *left_vsl,
72 int comparison,
73 struct expression *right,
74 const char *right_var, struct var_sym_list *right_vsl)
75 {
76 struct smatch_state *state;
77 struct compare_data *data;
78
79 state = __alloc_smatch_state(0);
80 state->name = alloc_sname(show_comparison(comparison));
81 data = __alloc_compare_data(0);
82 data->left = left;
83 data->left_var = alloc_sname(left_var);
84 data->left_vsl = clone_var_sym_list(left_vsl);
85 data->comparison = comparison;
86 data->right = right;
87 data->right_var = alloc_sname(right_var);
88 data->right_vsl = clone_var_sym_list(right_vsl);
89 state->data = data;
90 return state;
91 }
92
93 int state_to_comparison(struct smatch_state *state)
94 {
95 if (!state || !state->data)
96 return UNKNOWN_COMPARISON;
97 return ((struct compare_data *)state->data)->comparison;
98 }
99
100 /*
101 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x".
102 */
103 int flip_comparison(int op)
104 {
105 switch (op) {
106 case UNKNOWN_COMPARISON:
107 return UNKNOWN_COMPARISON;
108 case '<':
109 return '>';
110 case SPECIAL_UNSIGNED_LT:
111 return SPECIAL_UNSIGNED_GT;
112 case SPECIAL_LTE:
113 return SPECIAL_GTE;
114 case SPECIAL_UNSIGNED_LTE:
115 return SPECIAL_UNSIGNED_GTE;
116 case SPECIAL_EQUAL:
117 return SPECIAL_EQUAL;
118 case SPECIAL_NOTEQUAL:
119 return SPECIAL_NOTEQUAL;
120 case SPECIAL_GTE:
121 return SPECIAL_LTE;
122 case SPECIAL_UNSIGNED_GTE:
123 return SPECIAL_UNSIGNED_LTE;
124 case '>':
125 return '<';
126 case SPECIAL_UNSIGNED_GT:
127 return SPECIAL_UNSIGNED_LT;
128 case IMPOSSIBLE_COMPARISON:
129 return UNKNOWN_COMPARISON;
130 default:
131 sm_perror("unhandled comparison %d", op);
132 return op;
133 }
134 }
135
136 int negate_comparison(int op)
137 {
138 switch (op) {
139 case UNKNOWN_COMPARISON:
140 return UNKNOWN_COMPARISON;
141 case '<':
142 return SPECIAL_GTE;
143 case SPECIAL_UNSIGNED_LT:
144 return SPECIAL_UNSIGNED_GTE;
145 case SPECIAL_LTE:
146 return '>';
147 case SPECIAL_UNSIGNED_LTE:
148 return SPECIAL_UNSIGNED_GT;
149 case SPECIAL_EQUAL:
150 return SPECIAL_NOTEQUAL;
151 case SPECIAL_NOTEQUAL:
152 return SPECIAL_EQUAL;
153 case SPECIAL_GTE:
154 return '<';
155 case SPECIAL_UNSIGNED_GTE:
156 return SPECIAL_UNSIGNED_LT;
157 case '>':
158 return SPECIAL_LTE;
159 case SPECIAL_UNSIGNED_GT:
160 return SPECIAL_UNSIGNED_LTE;
161 case IMPOSSIBLE_COMPARISON:
162 return UNKNOWN_COMPARISON;
163 default:
164 sm_perror("unhandled comparison %d", op);
165 return op;
166 }
167 }
168
169 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
170 {
171 sval_t left_min, left_max, right_min, right_max;
172 struct symbol *type = &int_ctype;
173
174 if (!left_rl || !right_rl)
175 return UNKNOWN_COMPARISON;
176
177 if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type))
178 type = rl_type(left_rl);
179 if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type))
180 type = rl_type(right_rl);
181
182 left_rl = cast_rl(type, left_rl);
183 right_rl = cast_rl(type, right_rl);
184
185 left_min = rl_min(left_rl);
186 left_max = rl_max(left_rl);
187 right_min = rl_min(right_rl);
188 right_max = rl_max(right_rl);
189
190 if (left_min.value == left_max.value &&
191 right_min.value == right_max.value &&
192 left_min.value == right_min.value)
193 return SPECIAL_EQUAL;
194
195 if (sval_cmp(left_max, right_min) < 0)
196 return '<';
197 if (sval_cmp(left_max, right_min) == 0)
198 return SPECIAL_LTE;
199 if (sval_cmp(left_min, right_max) > 0)
200 return '>';
201 if (sval_cmp(left_min, right_max) == 0)
202 return SPECIAL_GTE;
203
204 return UNKNOWN_COMPARISON;
205 }
206
207 static int comparison_from_extra(struct expression *a, struct expression *b)
208 {
209 struct range_list *left, *right;
210
211 if (!get_implied_rl(a, &left))
212 return UNKNOWN_COMPARISON;
213 if (!get_implied_rl(b, &right))
214 return UNKNOWN_COMPARISON;
215
216 return rl_comparison(left, right);
217 }
218
219 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
220 {
221 struct symbol *sym;
222 struct smatch_state *state;
223
224 if (!vsl)
225 return NULL;
226 sym = vsl_to_sym(vsl);
227 if (!sym || !sym->ident)
228 return NULL;
229 state = get_orig_estate(sym->ident->name, sym);
230 return estate_rl(state);
231 }
232
233 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
234 {
235 struct compare_data *data = sm->state->data;
236 struct range_list *left_rl, *right_rl;
237 int op = UNKNOWN_COMPARISON;
238
239 if (!data)
240 return &undefined;
241
242 if (is_impossible_path()) {
243 op = IMPOSSIBLE_COMPARISON;
244 goto alloc;
245 }
246
247 if (strstr(data->left_var, " orig"))
248 left_rl = get_orig_rl(data->left_vsl);
249 else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl))
250 goto alloc;
251
252 if (strstr(data->right_var, " orig"))
253 right_rl = get_orig_rl(data->right_vsl);
254 else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl))
255 goto alloc;
256
257 op = rl_comparison(left_rl, right_rl);
258
259 alloc:
260 return alloc_compare_state(data->left, data->left_var, data->left_vsl,
261 op,
262 data->right, data->right_var, data->right_vsl);
263 }
264
265 /* remove_unsigned_from_comparison() is obviously a hack. */
266 int remove_unsigned_from_comparison(int op)
267 {
268 switch (op) {
269 case SPECIAL_UNSIGNED_LT:
270 return '<';
271 case SPECIAL_UNSIGNED_LTE:
272 return SPECIAL_LTE;
273 case SPECIAL_UNSIGNED_GTE:
274 return SPECIAL_GTE;
275 case SPECIAL_UNSIGNED_GT:
276 return '>';
277 default:
278 return op;
279 }
280 }
281
282 /*
283 * This is for when you merge states "a < b" and "a == b", the result is that
284 * we can say for sure, "a <= b" after the merge.
285 */
286 int merge_comparisons(int one, int two)
287 {
288 int LT, EQ, GT;
289
290 if (one == UNKNOWN_COMPARISON || two == UNKNOWN_COMPARISON)
291 return UNKNOWN_COMPARISON;
292
293 if (one == IMPOSSIBLE_COMPARISON)
294 return two;
295 if (two == IMPOSSIBLE_COMPARISON)
296 return one;
297
298 one = remove_unsigned_from_comparison(one);
299 two = remove_unsigned_from_comparison(two);
300
301 if (one == two)
302 return one;
303
304 LT = EQ = GT = 0;
305
306 switch (one) {
307 case '<':
308 LT = 1;
309 break;
310 case SPECIAL_LTE:
311 LT = 1;
312 EQ = 1;
313 break;
314 case SPECIAL_EQUAL:
315 EQ = 1;
316 break;
317 case SPECIAL_GTE:
318 GT = 1;
319 EQ = 1;
320 break;
321 case '>':
322 GT = 1;
323 }
324
325 switch (two) {
326 case '<':
327 LT = 1;
328 break;
329 case SPECIAL_LTE:
330 LT = 1;
331 EQ = 1;
332 break;
333 case SPECIAL_EQUAL:
334 EQ = 1;
335 break;
336 case SPECIAL_GTE:
337 GT = 1;
338 EQ = 1;
339 break;
340 case '>':
341 GT = 1;
342 }
343
344 if (LT && EQ && GT)
345 return UNKNOWN_COMPARISON;
346 if (LT && EQ)
347 return SPECIAL_LTE;
348 if (LT && GT)
349 return SPECIAL_NOTEQUAL;
350 if (LT)
351 return '<';
352 if (EQ && GT)
353 return SPECIAL_GTE;
354 if (GT)
355 return '>';
356 return UNKNOWN_COMPARISON;
357 }
358
359 /*
360 * This is for if you have "a < b" and "b <= c" and you want to see how "a
361 * compares to c". You would call this like get_combined_comparison('<', '<=').
362 * The return comparison would be '<'.
363 */
364 int combine_comparisons(int left_compare, int right_compare)
365 {
366 int LT, EQ, GT;
367
368 left_compare = remove_unsigned_from_comparison(left_compare);
369 right_compare = remove_unsigned_from_comparison(right_compare);
370
371 LT = EQ = GT = 0;
372
373 switch (left_compare) {
374 case '<':
375 LT++;
376 break;
377 case SPECIAL_LTE:
378 LT++;
379 EQ++;
380 break;
381 case SPECIAL_EQUAL:
382 return right_compare;
383 case SPECIAL_GTE:
384 GT++;
385 EQ++;
386 break;
387 case '>':
388 GT++;
389 }
390
391 switch (right_compare) {
392 case '<':
393 LT++;
394 break;
395 case SPECIAL_LTE:
396 LT++;
397 EQ++;
398 break;
399 case SPECIAL_EQUAL:
400 return left_compare;
401 case SPECIAL_GTE:
402 GT++;
403 EQ++;
404 break;
405 case '>':
406 GT++;
407 }
408
409 if (LT == 2) {
410 if (EQ == 2)
411 return SPECIAL_LTE;
412 return '<';
413 }
414
415 if (GT == 2) {
416 if (EQ == 2)
417 return SPECIAL_GTE;
418 return '>';
419 }
420 return UNKNOWN_COMPARISON;
421 }
422
423 /*
424 * This is mostly used when you know from extra state that a <= b but you
425 * know from comparisons that a != b so then if take the intersection then
426 * we know that a < b. The name is taken from the fact that the intersection
427 * of < and <= is <.
428 */
429 int comparison_intersection(int left_compare, int right_compare)
430 {
431 int LT, GT, EQ, NE, total;
432
433 if (left_compare == IMPOSSIBLE_COMPARISON ||
434 right_compare == IMPOSSIBLE_COMPARISON)
435 return IMPOSSIBLE_COMPARISON;
436
437 left_compare = remove_unsigned_from_comparison(left_compare);
438 right_compare = remove_unsigned_from_comparison(right_compare);
439
440 LT = GT = EQ = NE = total = 0;
441
442 /* Only one side is known. */
443 if (!left_compare)
444 return right_compare;
445 if (!right_compare)
446 return left_compare;
447
448 switch (left_compare) {
449 case '<':
450 LT++;
451 total += 1;
452 break;
453 case SPECIAL_LTE:
454 LT++;
455 EQ++;
456 total += 2;
457 break;
458 case SPECIAL_EQUAL:
459 EQ++;
460 total += 1;
461 break;
462 case SPECIAL_NOTEQUAL:
463 NE++;
464 total += 1;
465 break;
466 case SPECIAL_GTE:
467 GT++;
468 EQ++;
469 total += 2;
470 break;
471 case '>':
472 GT++;
473 total += 1;
474 break;
475 default:
476 return UNKNOWN_COMPARISON;
477 }
478
479 switch (right_compare) {
480 case '<':
481 LT++;
482 total += 1;
483 break;
484 case SPECIAL_LTE:
485 LT++;
486 EQ++;
487 total += 2;
488 break;
489 case SPECIAL_EQUAL:
490 EQ++;
491 total += 1;
492 break;
493 case SPECIAL_NOTEQUAL:
494 NE++;
495 total += 1;
496 break;
497 case SPECIAL_GTE:
498 GT++;
499 EQ++;
500 total += 2;
501 break;
502 case '>':
503 GT++;
504 total += 1;
505 break;
506 default:
507 return UNKNOWN_COMPARISON;
508 }
509
510 if (LT == 2) {
511 if (EQ == 2)
512 return SPECIAL_LTE;
513 return '<';
514 }
515
516 if (GT == 2) {
517 if (EQ == 2)
518 return SPECIAL_GTE;
519 return '>';
520 }
521 if (EQ == 2)
522 return SPECIAL_EQUAL;
523 if (total == 2 && EQ && NE)
524 return IMPOSSIBLE_COMPARISON;
525 if (GT && LT)
526 return IMPOSSIBLE_COMPARISON;
527 if (GT && NE)
528 return '>';
529 if (LT && NE)
530 return '<';
531 if (NE == 2)
532 return SPECIAL_NOTEQUAL;
533 if (total == 2 && (LT || GT) && EQ)
534 return IMPOSSIBLE_COMPARISON;
535
536 return UNKNOWN_COMPARISON;
537 }
538
539 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other)
540 {
541 struct compare_data *data = cur->state->data;
542 int extra, new;
543 static bool in_recurse;
544
545 // FIXME. No data is useless
546 if (!data)
547 return;
548
549 if (in_recurse)
550 return;
551 in_recurse = true;
552 extra = comparison_from_extra(data->left, data->right);
553 in_recurse = false;
554 if (!extra)
555 return;
556 new = comparison_intersection(extra, data->comparison);
557 if (new == data->comparison)
558 return;
559
560 // FIXME: we should always preserve implications
561 set_state(comparison_id, cur->name, NULL,
562 alloc_compare_state(data->left, data->left_var, data->left_vsl,
563 new,
564 data->right, data->right_var, data->right_vsl));
565 }
566
567 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
568 {
569 struct compare_data *data = s1->data;
570 int op;
571
572 if (!data)
573 return &undefined;
574
575 op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
576 return alloc_compare_state(
577 data->left, data->left_var, data->left_vsl,
578 op,
579 data->right, data->right_var, data->right_vsl);
580 }
581
582 static struct smatch_state *alloc_link_state(struct string_list *links)
583 {
584 struct smatch_state *state;
585 static char buf[256] = "";
586 int cnt = 0;
587 char *tmp;
588
589 state = __alloc_smatch_state(0);
590
591 FOR_EACH_PTR(links, tmp) {
592 cnt += snprintf(buf + cnt, sizeof(buf) - cnt, "%s%s", cnt ? ", " : "", tmp);
593 if (cnt >= sizeof(buf))
594 goto done;
595 } END_FOR_EACH_PTR(tmp);
596
597 done:
598 state->name = alloc_sname(buf);
599 state->data = links;
600 return state;
601 }
602
603 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
604 {
605 struct smatch_state *old_state, *new_state;
606 struct string_list *links;
607 char *new;
608
609 old_state = get_state(link_id, var, sym);
610 if (old_state)
611 links = clone_str_list(old_state->data);
612 else
613 links = NULL;
614
615 new = alloc_sname(link);
616 insert_string(&links, new);
617
618 new_state = alloc_link_state(links);
619 set_state(link_id, var, sym, new_state);
620 }
621
622 static void save_start_states(struct statement *stmt)
623 {
624 struct symbol *param;
625 char orig[64];
626 char state_name[128];
627 struct smatch_state *state;
628
629 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
630 struct var_sym_list *left_vsl = NULL;
631 struct var_sym_list *right_vsl = NULL;
632
633 if (!param->ident)
634 continue;
635 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
636 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
637 add_var_sym(&left_vsl, param->ident->name, param);
638 add_var_sym(&right_vsl, orig, param);
639 state = alloc_compare_state(
640 NULL, param->ident->name, left_vsl,
641 SPECIAL_EQUAL,
642 NULL, alloc_sname(orig), right_vsl);
643 set_state(comparison_id, state_name, NULL, state);
644 save_link_var_sym(param->ident->name, param, state_name);
645 } END_FOR_EACH_PTR(param);
646 }
647
648 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
649 {
650 struct smatch_state *ret;
651 struct string_list *links;
652
653 links = combine_string_lists(s1->data, s2->data);
654 ret = alloc_link_state(links);
655 return ret;
656 }
657
658 static void match_inc(struct sm_state *sm, bool preserve)
659 {
660 struct string_list *links;
661 struct smatch_state *state, *new;
662 struct compare_data *data;
663 char *tmp;
664 int flip;
665 int op;
666
667 links = sm->state->data;
668
669 FOR_EACH_PTR(links, tmp) {
670 state = get_state(comparison_id, tmp, NULL);
671 if (!state)
672 continue;
673 data = state->data;
674 if (!data)
675 continue;
676
677 flip = 0;
678 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
679 tmp[strlen(sm->name)] != ' ')
680 flip = 1;
681
682 op = state_to_comparison(state);
683
684 switch (flip ? flip_comparison(op) : op) {
685 case SPECIAL_EQUAL:
686 case SPECIAL_GTE:
687 case SPECIAL_UNSIGNED_GTE:
688 case '>':
689 case SPECIAL_UNSIGNED_GT:
690 if (preserve)
691 break;
692 new = alloc_compare_state(
693 data->left, data->left_var, data->left_vsl,
694 flip ? '<' : '>',
695 data->right, data->right_var, data->right_vsl);
696 set_state(comparison_id, tmp, NULL, new);
697 break;
698 case '<':
699 case SPECIAL_UNSIGNED_LT:
700 new = alloc_compare_state(
701 data->left, data->left_var, data->left_vsl,
702 flip ? SPECIAL_GTE : SPECIAL_LTE,
703 data->right, data->right_var, data->right_vsl);
704 set_state(comparison_id, tmp, NULL, new);
705 break;
706 default:
707 new = alloc_compare_state(
708 data->left, data->left_var, data->left_vsl,
709 UNKNOWN_COMPARISON,
710 data->right, data->right_var, data->right_vsl);
711 set_state(comparison_id, tmp, NULL, new);
712 }
713 } END_FOR_EACH_PTR(tmp);
714 }
715
716 static void match_dec(struct sm_state *sm, bool preserve)
717 {
718 struct string_list *links;
719 struct smatch_state *state;
720 char *tmp;
721
722 links = sm->state->data;
723
724 FOR_EACH_PTR(links, tmp) {
725 struct compare_data *data;
726 struct smatch_state *new;
727
728 state = get_state(comparison_id, tmp, NULL);
729 if (!state || !state->data)
730 continue;
731
732 data = state->data;
733
734 switch (state_to_comparison(state)) {
735 case SPECIAL_EQUAL:
736 case SPECIAL_LTE:
737 case SPECIAL_UNSIGNED_LTE:
738 case '<':
739 case SPECIAL_UNSIGNED_LT: {
740 if (preserve)
741 break;
742
743 new = alloc_compare_state(
744 data->left, data->left_var, data->left_vsl,
745 '<',
746 data->right, data->right_var, data->right_vsl);
747 set_state(comparison_id, tmp, NULL, new);
748 break;
749 }
750 default:
751 new = alloc_compare_state(
752 data->left, data->left_var, data->left_vsl,
753 UNKNOWN_COMPARISON,
754 data->right, data->right_var, data->right_vsl);
755 set_state(comparison_id, tmp, NULL, new);
756 }
757 } END_FOR_EACH_PTR(tmp);
758 }
759
760 static void reset_sm(struct sm_state *sm)
761 {
762 struct string_list *links;
763 char *tmp;
764
765 links = sm->state->data;
766
767 FOR_EACH_PTR(links, tmp) {
768 struct smatch_state *old, *new;
769
770 old = get_state(comparison_id, tmp, NULL);
771 if (!old || !old->data) {
772 new = &undefined;
773 } else {
774 struct compare_data *data = old->data;
775
776 new = alloc_compare_state(
777 data->left, data->left_var, data->left_vsl,
778 UNKNOWN_COMPARISON,
779 data->right, data->right_var, data->right_vsl);
780 }
781 set_state(comparison_id, tmp, NULL, new);
782 } END_FOR_EACH_PTR(tmp);
783 set_state(link_id, sm->name, sm->sym, &undefined);
784 }
785
786 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
787 {
788 struct range_list *rl;
789 sval_t zero = { .type = &int_ctype };
790
791 if (!expr || expr->type != EXPR_ASSIGNMENT)
792 return false;
793 if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
794 return false;
795
796 get_absolute_rl(expr->right, &rl);
797 if (sval_is_negative(rl_min(rl))) {
798 reset_sm(sm);
799 return false;
800 }
801
802 if (expr->op == SPECIAL_ADD_ASSIGN)
803 match_inc(sm, rl_has_sval(rl, zero));
804 else
805 match_dec(sm, rl_has_sval(rl, zero));
806 return true;
807 }
808
809 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
810 {
811 /*
812 * if (foo > bar) then ++foo is also > bar.
813 */
814 if (!mod_expr)
815 return;
816 if (match_add_sub_assign(sm, mod_expr))
817 return;
818 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
819 return;
820
821 if (mod_expr->op == SPECIAL_INCREMENT)
822 match_inc(sm, false);
823 else if (mod_expr->op == SPECIAL_DECREMENT)
824 match_dec(sm, false);
825 }
826
827 static int is_self_assign(struct expression *expr)
828 {
829 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
830 return 0;
831 return expr_equiv(expr->left, expr->right);
832 }
833
834 static struct expression *ignore_mod_expr;
835 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
836 {
837 if (mod_expr && is_self_assign(mod_expr))
838 return;
839 if (mod_expr && mod_expr == ignore_mod_expr)
840 return;
841
842 /* handled by match_inc_dec() */
843 if (mod_expr &&
844 ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
845 (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
846 return;
847 if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT &&
848 (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN))
849 return;
850
851 reset_sm(sm);
852 }
853
854 static void match_preop(struct expression *expr)
855 {
856 struct expression *parent;
857 struct range_list *left, *right;
858 int op;
859
860 /*
861 * This is an important special case. Say you have:
862 *
863 * if (++j == limit)
864 *
865 * Assume that we know the range of limit is higher than the start
866 * value for "j". Then the first thing that we process is the ++j. We
867 * have not comparison states set up so it doesn't get caught by the
868 * modification hook. But it does get caught by smatch_extra which sets
869 * j to unknown then we parse the "j == limit" and sets false to != but
870 * really we want false to be <.
871 *
872 * So what we do is we set j < limit here, then the match_modify catches
873 * it and we do a match_inc_dec().
874 *
875 */
876
877 if (expr->type != EXPR_PREOP ||
878 (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT))
879 return;
880
881 parent = expr_get_parent_expr(expr);
882 if (!parent)
883 return;
884 if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL)
885 return;
886 if (parent->left != expr)
887 return;
888
889 if (!get_implied_rl(expr->unop, &left) ||
890 !get_implied_rl(parent->right, &right))
891 return;
892
893 op = rl_comparison(left, right);
894 if (op == UNKNOWN_COMPARISON)
895 return;
896
897 add_comparison(expr->unop, op, parent->right);
898 }
899
900 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
901 {
902 expr = strip_expr(expr);
903 if (!expr)
904 return NULL;
905 if (sym)
906 *sym = NULL;
907
908 if (expr->type == EXPR_PREOP &&
909 (expr->op == SPECIAL_INCREMENT ||
910 expr->op == SPECIAL_DECREMENT))
911 expr = strip_expr(expr->unop);
912
913 if (expr->type == EXPR_CALL) {
914 char buf[64];
915
916 snprintf(buf, sizeof(buf), "return %p", expr);
917 return alloc_string(buf);
918 }
919
920 return expr_to_chunk_sym_vsl(expr, sym, NULL);
921 }
922
923 static char *chunk_to_var(struct expression *expr)
924 {
925 return chunk_to_var_sym(expr, NULL);
926 }
927
928 static struct smatch_state *get_state_chunk(int owner, struct expression *expr)
929 {
930 char *name;
931 struct symbol *sym;
932 struct smatch_state *ret;
933
934 name = chunk_to_var_sym(expr, &sym);
935 if (!name)
936 return NULL;
937
938 ret = get_state(owner, name, sym);
939 free_string(name);
940 return ret;
941 }
942
943 static void save_link(struct expression *expr, char *link)
944 {
945 char *var;
946 struct symbol *sym;
947
948 expr = strip_expr(expr);
949 if (expr->type == EXPR_BINOP) {
950 char *chunk;
951
952 chunk = chunk_to_var(expr);
953 if (!chunk)
954 return;
955
956 save_link(expr->left, link);
957 save_link(expr->right, link);
958 save_link_var_sym(chunk, NULL, link);
959 return;
960 }
961
962 var = chunk_to_var_sym(expr, &sym);
963 if (!var)
964 return;
965
966 save_link_var_sym(var, sym, link);
967 free_string(var);
968 }
969
970 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
971 {
972 struct smatch_state *state;
973 struct compare_data *data;
974 int flip = 0;
975 char state_name[256];
976
977 if (strcmp(left, right) > 0) {
978 const char *tmp = right;
979
980 flip = 1;
981 right = left;
982 left = tmp;
983 }
984
985 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
986 state = get_state_stree(pre_stree, comparison_id, state_name, NULL);
987 if (!state || !state->data)
988 return 0;
989 data = state->data;
990 if (flip)
991 return flip_comparison(data->comparison);
992 return data->comparison;
993
994 }
995
996 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
997 {
998 struct var_sym *tmp;
999
1000 FOR_EACH_PTR(left_vsl, tmp) {
1001 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
1002 return 1;
1003 } END_FOR_EACH_PTR(tmp);
1004
1005 return 0;
1006 }
1007
1008 /*
1009 * The idea here is that we take a comparison "a < b" and then we look at all
1010 * the things which "b" is compared against "b < c" and we say that that implies
1011 * a relationship "a < c".
1012 *
1013 * The names here about because the comparisons are organized like this
1014 * "a < b < c".
1015 *
1016 */
1017 static void update_tf_links(struct stree *pre_stree,
1018 struct expression *left_expr,
1019 const char *left_var, struct var_sym_list *left_vsl,
1020 int left_comparison, int left_false_comparison,
1021 const char *mid_var, struct var_sym_list *mid_vsl,
1022 struct string_list *links)
1023 {
1024 struct smatch_state *state;
1025 struct smatch_state *true_state, *false_state;
1026 struct compare_data *data;
1027 struct expression *right_expr;
1028 const char *left_var_orig = left_var;
1029 const char *right_var;
1030 struct var_sym_list *left_vsl_orig = left_vsl;
1031 struct var_sym_list *right_vsl;
1032 int orig_comparison;
1033 int right_comparison;
1034 int true_comparison;
1035 int false_comparison;
1036 char *tmp;
1037 char state_name[256];
1038 struct var_sym *vs;
1039
1040 FOR_EACH_PTR(links, tmp) {
1041 state = get_state_stree(pre_stree, comparison_id, tmp, NULL);
1042 if (!state || !state->data)
1043 continue;
1044 left_var = left_var_orig;
1045 left_vsl = left_vsl_orig;
1046 data = state->data;
1047 right_comparison = data->comparison;
1048 right_expr = data->right;
1049 right_var = data->right_var;
1050 right_vsl = data->right_vsl;
1051 if (strcmp(mid_var, right_var) == 0) {
1052 right_expr = data->left;
1053 right_var = data->left_var;
1054 right_vsl = data->left_vsl;
1055 right_comparison = flip_comparison(right_comparison);
1056 }
1057 if (have_common_var_sym(left_vsl, right_vsl))
1058 continue;
1059
1060 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
1061
1062 true_comparison = combine_comparisons(left_comparison, right_comparison);
1063 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
1064
1065 true_comparison = comparison_intersection(orig_comparison, true_comparison);
1066 false_comparison = comparison_intersection(orig_comparison, false_comparison);
1067
1068 if (strcmp(left_var, right_var) > 0) {
1069 struct expression *tmp_expr = left_expr;
1070 const char *tmp_var = left_var;
1071 struct var_sym_list *tmp_vsl = left_vsl;
1072
1073 left_expr = right_expr;
1074 left_var = right_var;
1075 left_vsl = right_vsl;
1076 right_expr = tmp_expr;
1077 right_var = tmp_var;
1078 right_vsl = tmp_vsl;
1079 true_comparison = flip_comparison(true_comparison);
1080 false_comparison = flip_comparison(false_comparison);
1081 }
1082
1083 if (!true_comparison && !false_comparison)
1084 continue;
1085
1086 if (true_comparison)
1087 true_state = alloc_compare_state(
1088 left_expr, left_var, left_vsl,
1089 true_comparison,
1090 right_expr, right_var, right_vsl);
1091 else
1092 true_state = NULL;
1093 if (false_comparison)
1094 false_state = alloc_compare_state(
1095 left_expr, left_var, left_vsl,
1096 false_comparison,
1097 right_expr, right_var, right_vsl);
1098 else
1099 false_state = NULL;
1100
1101 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
1102 set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1103 FOR_EACH_PTR(left_vsl, vs) {
1104 save_link_var_sym(vs->var, vs->sym, state_name);
1105 } END_FOR_EACH_PTR(vs);
1106 FOR_EACH_PTR(right_vsl, vs) {
1107 save_link_var_sym(vs->var, vs->sym, state_name);
1108 } END_FOR_EACH_PTR(vs);
1109 if (!vsl_to_sym(left_vsl))
1110 save_link_var_sym(left_var, NULL, state_name);
1111 if (!vsl_to_sym(right_vsl))
1112 save_link_var_sym(right_var, NULL, state_name);
1113 } END_FOR_EACH_PTR(tmp);
1114 }
1115
1116 static void update_tf_data(struct stree *pre_stree,
1117 struct expression *left_expr,
1118 const char *left_name, struct var_sym_list *left_vsl,
1119 struct expression *right_expr,
1120 const char *right_name, struct var_sym_list *right_vsl,
1121 int true_comparison, int false_comparison)
1122 {
1123 struct smatch_state *state;
1124
1125 state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
1126 if (state)
1127 update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
1128
1129 state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
1130 if (state)
1131 update_tf_links(pre_stree, right_expr, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data);
1132 }
1133
1134 static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
1135 {
1136 if (sm->state != &start ||
1137 !mod_expr ||
1138 (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
1139 mod_expr->op != SPECIAL_INCREMENT)
1140 set_state(inc_dec_id, sm->name, sm->sym, &undefined);
1141 else
1142 set_state(inc_dec_id, sm->name, sm->sym, &incremented);
1143 }
1144
1145 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
1146 {
1147 sval_t sval;
1148 char *iter_name, *cap_name;
1149 struct symbol *iter_sym, *cap_sym;
1150 struct compare_data *data;
1151
1152 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1153 return;
1154
1155 if (!__cur_stmt || !__prev_stmt)
1156 return;
1157 if (__cur_stmt->type != STMT_ITERATOR)
1158 return;
1159 if (__cur_stmt->iterator_pre_condition != expr)
1160 return;
1161
1162 /* literals are handled in smatch_extra.c */
1163 if (get_value(expr->right, &sval))
1164 return;
1165
1166 /* First time checking the condition */
1167 if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
1168 if (!get_implied_value(expr->left, &sval) ||
1169 sval.value != 0)
1170 return;
1171
1172 iter_name = expr_to_var_sym(expr->left, &iter_sym);
1173 cap_name = expr_to_var_sym(expr->right, &cap_sym);
1174 if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
1175 free_string(iter_name);
1176 free_string(cap_name);
1177 return;
1178 }
1179
1180 set_state(inc_dec_id, iter_name, iter_sym, &start);
1181 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
1182
1183 free_string(iter_name);
1184 free_string(cap_name);
1185 return;
1186 }
1187
1188 /* Second time checking the condtion */
1189 if (__prev_stmt != __cur_stmt->iterator_post_statement)
1190 return;
1191
1192 if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1193 return;
1194
1195 data = false_state->data;
1196 false_state = alloc_compare_state(
1197 data->left, data->left_var, data->left_vsl,
1198 SPECIAL_EQUAL,
1199 data->right, data->right_var, data->right_vsl);
1200
1201 // FIXME: This doesn't handle links correct so it doesn't set "param orig"
1202 set_true_false_states(comparison_id, state_name, NULL, NULL, false_state);
1203 }
1204
1205 static int is_plus_one(struct expression *expr)
1206 {
1207 sval_t sval;
1208
1209 if (expr->type != EXPR_BINOP || expr->op != '+')
1210 return 0;
1211 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1212 return 0;
1213 return 1;
1214 }
1215
1216 static int is_minus_one(struct expression *expr)
1217 {
1218 sval_t sval;
1219
1220 if (expr->type != EXPR_BINOP || expr->op != '-')
1221 return 0;
1222 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1223 return 0;
1224 return 1;
1225 }
1226
1227 static void remove_plus_minus_zero(struct expression **expr_p)
1228 {
1229 struct expression *expr = *expr_p;
1230 sval_t sval;
1231
1232 if (!expr || expr->type != EXPR_BINOP)
1233 return;
1234 if (expr->op == '+') {
1235 if (get_implied_value(expr->left, &sval) && sval.value == 0)
1236 *expr_p = expr->right;
1237 else if (get_implied_value(expr->right, &sval) && sval.value == 0)
1238 *expr_p = expr->left;
1239 else
1240 return;
1241 return remove_plus_minus_zero(expr_p);
1242 }
1243 if (expr->op == '-') {
1244 if (get_implied_value(expr->right, &sval) && sval.value == 0) {
1245 *expr_p = expr->left;
1246 return remove_plus_minus_zero(expr_p);
1247 }
1248 }
1249 }
1250
1251 static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p)
1252 {
1253 struct expression *left = *left_p;
1254 struct expression *right = *right_p;
1255
1256 /*
1257 * These two are basically equivalent: "foo + 1 != bar" and
1258 * "foo != bar - 1". There are issues with signedness and integer
1259 * overflows. There are also issues with type as well. But let's
1260 * pretend we can ignore all that stuff for now.
1261 *
1262 */
1263
1264 if (!is_plus_one(left))
1265 return;
1266
1267 *left_p = left->left;
1268 *right_p = binop_expression(right, '-', left->right);
1269 }
1270
1271 static void move_plus_to_minus(struct expression **left_p, struct expression **right_p)
1272 {
1273 if (is_plus_one(*left_p) && is_plus_one(*right_p))
1274 return;
1275
1276 move_plus_to_minus_helper(left_p, right_p);
1277 move_plus_to_minus_helper(right_p, left_p);
1278 }
1279
1280 static void simplify_binops(struct expression **left_p, struct expression **right_p)
1281 {
1282 remove_plus_minus_zero(left_p);
1283 remove_plus_minus_zero(right_p);
1284
1285 move_plus_to_minus(left_p, right_p);
1286 }
1287
1288 static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state)
1289 {
1290 char *left = NULL;
1291 char *right = NULL;
1292 struct symbol *left_sym, *right_sym;
1293 struct var_sym_list *left_vsl = NULL;
1294 struct var_sym_list *right_vsl = NULL;
1295 int false_op;
1296 int orig_comparison;
1297 struct smatch_state *true_state, *false_state;
1298 static char state_name[256];
1299 struct stree *pre_stree;
1300 sval_t sval;
1301
1302 if (!left_expr || !right_expr)
1303 return;
1304
1305 left_expr = strip_parens(left_expr);
1306 right_expr = strip_parens(right_expr);
1307
1308 while (left_expr->type == EXPR_ASSIGNMENT)
1309 left_expr = strip_parens(left_expr->left);
1310 while (right_expr->type == EXPR_ASSIGNMENT)
1311 right_expr = strip_parens(right_expr->left);
1312
1313 false_op = negate_comparison(op);
1314
1315 simplify_binops(&left_expr, &right_expr);
1316
1317 if (op == SPECIAL_UNSIGNED_LT &&
1318 get_implied_value(left_expr, &sval) &&
1319 sval.value == 0)
1320 false_op = SPECIAL_EQUAL;
1321
1322 if (op == SPECIAL_UNSIGNED_GT &&
1323 get_implied_value(right_expr, &sval) &&
1324 sval.value == 0)
1325 false_op = SPECIAL_EQUAL;
1326
1327 left = chunk_to_var_sym(left_expr, &left_sym);
1328 if (!left)
1329 goto free;
1330 if (left_sym)
1331 add_var_sym(&left_vsl, left, left_sym);
1332 else
1333 left_vsl = expr_to_vsl(left_expr);
1334 right = chunk_to_var_sym(right_expr, &right_sym);
1335 if (!right)
1336 goto free;
1337 if (right_sym)
1338 add_var_sym(&right_vsl, right, right_sym);
1339 else
1340 right_vsl = expr_to_vsl(right_expr);
1341
1342 if (strcmp(left, right) > 0) {
1343 char *tmp_name = left;
1344 struct var_sym_list *tmp_vsl = left_vsl;
1345 struct expression *tmp_expr = left_expr;
1346
1347 left = right;
1348 left_vsl = right_vsl;
1349 left_expr = right_expr;
1350 right = tmp_name;
1351 right_vsl = tmp_vsl;
1352 right_expr = tmp_expr;
1353 op = flip_comparison(op);
1354 false_op = flip_comparison(false_op);
1355 }
1356
1357 orig_comparison = get_comparison(left_expr, right_expr);
1358 op = comparison_intersection(orig_comparison, op);
1359 false_op = comparison_intersection(orig_comparison, false_op);
1360
1361 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1362 true_state = alloc_compare_state(
1363 left_expr, left, left_vsl,
1364 op,
1365 right_expr, right, right_vsl);
1366 false_state = alloc_compare_state(
1367 left_expr, left, left_vsl,
1368 false_op,
1369 right_expr, right, right_vsl);
1370
1371 pre_stree = clone_stree(__get_cur_stree());
1372 update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1373 free_stree(&pre_stree);
1374
1375 if (op == IMPOSSIBLE_COMPARISON &&
1376 false_op != IMPOSSIBLE_COMPARISON &&
1377 false_op != UNKNOWN_COMPARISON)
1378 set_true_path_impossible();
1379 if (op != IMPOSSIBLE_COMPARISON &&
1380 op != UNKNOWN_COMPARISON &&
1381 false_op == IMPOSSIBLE_COMPARISON)
1382 set_false_path_impossible();
1383
1384 set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1385 __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1386 save_link(left_expr, state_name);
1387 save_link(right_expr, state_name);
1388
1389 if (_false_state)
1390 *_false_state = false_state;
1391 if (_state_name)
1392 *_state_name = state_name;
1393 free:
1394 free_string(left);
1395 free_string(right);
1396 }
1397
1398 void __comparison_match_condition(struct expression *expr)
1399 {
1400 struct expression *left, *right, *new_left, *new_right, *tmp;
1401 struct smatch_state *false_state = NULL;
1402 char *state_name = NULL;
1403 int redo, count;
1404
1405 if (expr->type != EXPR_COMPARE)
1406 return;
1407
1408 handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
1409 if (false_state && state_name)
1410 handle_for_loops(expr, state_name, false_state);
1411
1412 left = strip_parens(expr->left);
1413 right = strip_parens(expr->right);
1414
1415 if (left->type == EXPR_BINOP && left->op == '+') {
1416 new_left = left->left;
1417 new_right = binop_expression(right, '-', left->right);
1418 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1419
1420 new_left = left->right;
1421 new_right = binop_expression(right, '-', left->left);
1422 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1423 }
1424
1425 if ((expr->op == SPECIAL_EQUAL || expr->op == SPECIAL_NOTEQUAL) &&
1426 expr_is_zero(expr->right) &&
1427 left->type == EXPR_BINOP && left->op == '-') {
1428 new_left = left->left;
1429 new_right = left->right;
1430 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1431 }
1432
1433 redo = 0;
1434 left = strip_parens(expr->left);
1435 right = strip_parens(expr->right);
1436 if (get_last_expr_from_expression_stmt(expr->left)) {
1437 left = get_last_expr_from_expression_stmt(expr->left);
1438 redo = 1;
1439 }
1440 if (get_last_expr_from_expression_stmt(expr->right)) {
1441 right = get_last_expr_from_expression_stmt(expr->right);
1442 redo = 1;
1443 }
1444
1445 if (!redo)
1446 return;
1447
1448 count = 0;
1449 while ((tmp = get_assigned_expr(left))) {
1450 if (count++ > 3)
1451 break;
1452 left = strip_expr(tmp);
1453 }
1454 count = 0;
1455 while ((tmp = get_assigned_expr(right))) {
1456 if (count++ > 3)
1457 break;
1458 right = strip_expr(tmp);
1459 }
1460
1461 handle_comparison(left, expr->op, right, NULL, NULL);
1462 }
1463
1464 void add_comparison_var_sym(
1465 struct expression *left_expr,
1466 const char *left_name, struct var_sym_list *left_vsl,
1467 int comparison,
1468 struct expression *right_expr,
1469 const char *right_name, struct var_sym_list *right_vsl,
1470 struct expression *mod_expr)
1471 {
1472 struct smatch_state *state;
1473 struct var_sym *vs;
1474 char state_name[256];
1475
1476 ignore_mod_expr = mod_expr;
1477
1478 if (strcmp(left_name, right_name) > 0) {
1479 struct expression *tmp_expr = left_expr;
1480 const char *tmp_name = left_name;
1481 struct var_sym_list *tmp_vsl = left_vsl;
1482
1483 left_expr = right_expr;
1484 left_name = right_name;
1485 left_vsl = right_vsl;
1486 right_expr = tmp_expr;
1487 right_name = tmp_name;
1488 right_vsl = tmp_vsl;
1489 comparison = flip_comparison(comparison);
1490 }
1491 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1492 state = alloc_compare_state(
1493 left_expr, left_name, left_vsl,
1494 comparison,
1495 right_expr, right_name, right_vsl);
1496
1497 set_state(comparison_id, state_name, NULL, state);
1498
1499 FOR_EACH_PTR(left_vsl, vs) {
1500 save_link_var_sym(vs->var, vs->sym, state_name);
1501 } END_FOR_EACH_PTR(vs);
1502 FOR_EACH_PTR(right_vsl, vs) {
1503 save_link_var_sym(vs->var, vs->sym, state_name);
1504 } END_FOR_EACH_PTR(vs);
1505 }
1506
1507 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1508 {
1509 char *left_name = NULL;
1510 char *right_name = NULL;
1511 struct symbol *left_sym, *right_sym;
1512 struct var_sym_list *left_vsl, *right_vsl;
1513 struct smatch_state *state;
1514 char state_name[256];
1515
1516 left_name = chunk_to_var_sym(left, &left_sym);
1517 if (!left_name)
1518 goto free;
1519 left_vsl = expr_to_vsl(left);
1520 right_name = chunk_to_var_sym(right, &right_sym);
1521 if (!right_name)
1522 goto free;
1523 right_vsl = expr_to_vsl(right);
1524
1525 if (strcmp(left_name, right_name) > 0) {
1526 struct expression *tmp_expr = left;
1527 struct symbol *tmp_sym = left_sym;
1528 char *tmp_name = left_name;
1529 struct var_sym_list *tmp_vsl = left_vsl;
1530
1531 left = right;
1532 left_name = right_name;
1533 left_sym = right_sym;
1534 left_vsl = right_vsl;
1535 right = tmp_expr;
1536 right_name = tmp_name;
1537 right_sym = tmp_sym;
1538 right_vsl = tmp_vsl;
1539 comparison = flip_comparison(comparison);
1540 }
1541 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1542 state = alloc_compare_state(
1543 left, left_name, left_vsl,
1544 comparison,
1545 right, right_name, right_vsl);
1546
1547 set_state(comparison_id, state_name, NULL, state);
1548 save_link(left, state_name);
1549 save_link(right, state_name);
1550
1551 free:
1552 free_string(left_name);
1553 free_string(right_name);
1554 }
1555
1556 static void match_assign_add(struct expression *expr)
1557 {
1558 struct expression *right;
1559 struct expression *r_left, *r_right;
1560 sval_t left_tmp, right_tmp;
1561
1562 right = strip_expr(expr->right);
1563 r_left = strip_expr(right->left);
1564 r_right = strip_expr(right->right);
1565
1566 get_absolute_min(r_left, &left_tmp);
1567 get_absolute_min(r_right, &right_tmp);
1568
1569 if (left_tmp.value > 0)
1570 add_comparison(expr->left, '>', r_right);
1571 else if (left_tmp.value == 0)
1572 add_comparison(expr->left, SPECIAL_GTE, r_right);
1573
1574 if (right_tmp.value > 0)
1575 add_comparison(expr->left, '>', r_left);
1576 else if (right_tmp.value == 0)
1577 add_comparison(expr->left, SPECIAL_GTE, r_left);
1578 }
1579
1580 static void match_assign_sub(struct expression *expr)
1581 {
1582 struct expression *right;
1583 struct expression *r_left, *r_right;
1584 int comparison;
1585 sval_t min;
1586
1587 right = strip_expr(expr->right);
1588 r_left = strip_expr(right->left);
1589 r_right = strip_expr(right->right);
1590
1591 if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1592 return;
1593
1594 comparison = get_comparison(r_left, r_right);
1595
1596 switch (comparison) {
1597 case '>':
1598 case SPECIAL_GTE:
1599 if (implied_not_equal(r_right, 0))
1600 add_comparison(expr->left, '>', r_left);
1601 else
1602 add_comparison(expr->left, SPECIAL_GTE, r_left);
1603 return;
1604 }
1605 }
1606
1607 static void match_assign_divide(struct expression *expr)
1608 {
1609 struct expression *right;
1610 struct expression *r_left, *r_right;
1611 sval_t min;
1612
1613 right = strip_expr(expr->right);
1614 r_left = strip_expr(right->left);
1615 r_right = strip_expr(right->right);
1616 if (!get_implied_min(r_right, &min) || min.value <= 1)
1617 return;
1618
1619 add_comparison(expr->left, '<', r_left);
1620 }
1621
1622 static void match_binop_assign(struct expression *expr)
1623 {
1624 struct expression *right;
1625
1626 right = strip_expr(expr->right);
1627 if (right->op == '+')
1628 match_assign_add(expr);
1629 if (right->op == '-')
1630 match_assign_sub(expr);
1631 if (right->op == '/')
1632 match_assign_divide(expr);
1633 }
1634
1635 static void copy_comparisons(struct expression *left, struct expression *right)
1636 {
1637 struct string_list *links;
1638 struct smatch_state *state;
1639 struct compare_data *data;
1640 struct symbol *left_sym, *right_sym;
1641 char *left_var = NULL;
1642 char *right_var = NULL;
1643 struct var_sym_list *left_vsl;
1644 struct expression *expr;
1645 const char *var;
1646 struct var_sym_list *vsl;
1647 int comparison;
1648 char *tmp;
1649
1650 /*
1651 * Say we have y < foo and we assign x = y; then that means x < foo.
1652 * Internally, smatch has links from "y" and "foo" to the comparison
1653 * "foo vs y". There could also be a comparison with an array:
1654 * "x[idx] vs limit", so all three variables, "x", "idx" and "limit"
1655 * have a link.
1656 *
1657 * Also another thing which can happen is that you have an assignment
1658 * "x = y" and there is a comparison: "x vs y". And clearly we don't
1659 * want to store "x < x".
1660 *
1661 * So what this function does is it takes each link "foo vs y" and it
1662 * swaps in "foo vs x". Except it moves the "x" to the left so it's
1663 * "x vs foo" (or whatever) and the add_comparison_var_sym() will flip
1664 * it into the correct order.
1665 *
1666 */
1667
1668 left_var = chunk_to_var_sym(left, &left_sym);
1669 if (!left_var)
1670 goto done;
1671 left_vsl = expr_to_vsl(left);
1672 right_var = chunk_to_var_sym(right, &right_sym);
1673 if (!right_var)
1674 goto done;
1675
1676 state = get_state(link_id, right_var, right_sym);
1677 if (!state)
1678 return;
1679 links = state->data;
1680
1681 FOR_EACH_PTR(links, tmp) {
1682 state = get_state(comparison_id, tmp, NULL);
1683 if (!state || !state->data)
1684 continue;
1685 data = state->data;
1686 /* if there isn't a comparison then skip it. (can this happen?) */
1687 if (!data->comparison)
1688 continue;
1689
1690 /* right_var is from "left = right_var;". "var" is the variable
1691 * bit from "right_var < var".
1692 */
1693 if (strcmp(right_var, data->left_var) == 0) {
1694 expr = data->right;
1695 var = data->right_var;
1696 vsl = data->right_vsl;
1697 comparison = data->comparison;
1698 } else if (strcmp(right_var, data->right_var) == 0) {
1699 expr = data->left;
1700 var = data->left_var;
1701 vsl = data->left_vsl;
1702 comparison = flip_comparison(data->comparison);
1703 } else {
1704 /* This means the right side is only part of the
1705 * comparison. As in "x = i;" when "foo[i] < bar".
1706 */
1707 continue;
1708 }
1709
1710 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1711 if (strcmp(left_var, var) == 0)
1712 continue;
1713
1714 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl, NULL);
1715 } END_FOR_EACH_PTR(tmp);
1716
1717 done:
1718 free_string(right_var);
1719 }
1720
1721 static bool is_empty_fake_assign(struct expression *expr)
1722 {
1723 if (!is_fake_var_assign(expr))
1724 return false;
1725 if (get_state_chunk(link_id, expr->right))
1726 return false;
1727 return true;
1728 }
1729
1730 static void match_assign(struct expression *expr)
1731 {
1732 struct expression *right;
1733
1734 if (expr->op != '=')
1735 return;
1736 if (__in_fake_assign || outside_of_function())
1737 return;
1738
1739 if (is_struct(expr->left))
1740 return;
1741
1742 if (is_self_assign(expr))
1743 return;
1744
1745 if (is_empty_fake_assign(expr))
1746 return;
1747
1748 copy_comparisons(expr->left, expr->right);
1749 add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1750
1751 right = strip_expr(expr->right);
1752 if (right->type == EXPR_BINOP)
1753 match_binop_assign(expr);
1754 }
1755
1756 int get_comparison_strings(const char *one, const char *two)
1757 {
1758 char buf[256];
1759 struct smatch_state *state;
1760 int invert = 0;
1761 int ret = 0;
1762
1763 if (!one || !two)
1764 return UNKNOWN_COMPARISON;
1765
1766 if (strcmp(one, two) == 0)
1767 return SPECIAL_EQUAL;
1768
1769 if (strcmp(one, two) > 0) {
1770 const char *tmp = one;
1771
1772 one = two;
1773 two = tmp;
1774 invert = 1;
1775 }
1776
1777 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1778 state = get_state(comparison_id, buf, NULL);
1779 if (state)
1780 ret = state_to_comparison(state);
1781
1782 if (invert)
1783 ret = flip_comparison(ret);
1784
1785 return ret;
1786 }
1787
1788 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
1789 {
1790 char *one = NULL;
1791 char *two = NULL;
1792 int ret = UNKNOWN_COMPARISON;
1793 int extra = UNKNOWN_COMPARISON;
1794
1795 if (a == UNKNOWN_COMPARISON ||
1796 b == UNKNOWN_COMPARISON)
1797 return UNKNOWN_COMPARISON;
1798
1799 a = strip_parens(a);
1800 b = strip_parens(b);
1801
1802 simplify_binops(&a, &b);
1803
1804 one = chunk_to_var(a);
1805 if (!one)
1806 goto free;
1807 two = chunk_to_var(b);
1808 if (!two)
1809 goto free;
1810
1811 ret = get_comparison_strings(one, two);
1812 if (ret)
1813 goto free;
1814
1815 if (is_plus_one(a) || is_minus_one(a)) {
1816 free_string(one);
1817 one = chunk_to_var(a->left);
1818 ret = get_comparison_strings(one, two);
1819 } else if (is_plus_one(b) || is_minus_one(b)) {
1820 free_string(two);
1821 two = chunk_to_var(b->left);
1822 ret = get_comparison_strings(one, two);
1823 }
1824
1825 if (ret == UNKNOWN_COMPARISON)
1826 goto free;
1827
1828 if (is_plus_one(a) || is_minus_one(b)) {
1829 if (ret == '<')
1830 ret = SPECIAL_LTE;
1831 else if (ret == SPECIAL_EQUAL)
1832 ret = '>';
1833 else if (ret == SPECIAL_GTE)
1834 ret = '>';
1835 else
1836 ret = UNKNOWN_COMPARISON;
1837 } else if ((is_minus_one(a) || is_plus_one(b))) {
1838 if (ret == '>')
1839 ret = SPECIAL_GTE;
1840 else if (ret == SPECIAL_EQUAL)
1841 ret = '<';
1842 else if (ret == SPECIAL_LTE)
1843 ret = '<';
1844 else
1845 ret = UNKNOWN_COMPARISON;
1846 } else {
1847 ret = UNKNOWN_COMPARISON;
1848 }
1849
1850 free:
1851 free_string(one);
1852 free_string(two);
1853
1854 if (use_extra)
1855 extra = comparison_from_extra(a, b);
1856 return comparison_intersection(ret, extra);
1857 }
1858
1859 int get_comparison(struct expression *a, struct expression *b)
1860 {
1861 return get_comparison_helper(a, b, true);
1862 }
1863
1864 int get_comparison_no_extra(struct expression *a, struct expression *b)
1865 {
1866 return get_comparison_helper(a, b, false);
1867 }
1868
1869 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1870 {
1871 char *one = NULL;
1872 char *two = NULL;
1873 int ret = 0;
1874 char buf[256];
1875 struct sm_state *sm;
1876 int saved;
1877
1878 one = chunk_to_var(a);
1879 if (!one)
1880 goto free;
1881 two = chunk_to_var(b);
1882 if (!two)
1883 goto free;
1884
1885
1886 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1887 ret = 1;
1888 goto free;
1889 }
1890
1891 if (strcmp(one, two) > 0) {
1892 char *tmp = one;
1893
1894 one = two;
1895 two = tmp;
1896 comparison = flip_comparison(comparison);
1897 }
1898
1899 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1900 sm = get_sm_state(comparison_id, buf, NULL);
1901 if (!sm)
1902 goto free;
1903
1904 FOR_EACH_PTR(sm->possible, sm) {
1905 if (!sm->state->data)
1906 continue;
1907 saved = ((struct compare_data *)sm->state->data)->comparison;
1908 if (saved == comparison)
1909 ret = 1;
1910 if (comparison == SPECIAL_EQUAL &&
1911 (saved == SPECIAL_LTE ||
1912 saved == SPECIAL_GTE ||
1913 saved == SPECIAL_UNSIGNED_LTE ||
1914 saved == SPECIAL_UNSIGNED_GTE))
1915 ret = 1;
1916 if (ret == 1)
1917 goto free;
1918 } END_FOR_EACH_PTR(sm);
1919
1920 return ret;
1921 free:
1922 free_string(one);
1923 free_string(two);
1924 return ret;
1925 }
1926
1927 struct state_list *get_all_comparisons(struct expression *expr)
1928 {
1929 struct smatch_state *state;
1930 struct string_list *links;
1931 struct state_list *ret = NULL;
1932 struct sm_state *sm;
1933 char *tmp;
1934
1935 state = get_state_chunk(link_id, expr);
1936 if (!state)
1937 return NULL;
1938 links = state->data;
1939
1940 FOR_EACH_PTR(links, tmp) {
1941 sm = get_sm_state(comparison_id, tmp, NULL);
1942 if (!sm)
1943 continue;
1944 // FIXME have to compare name with vsl
1945 add_ptr_list(&ret, sm);
1946 } END_FOR_EACH_PTR(tmp);
1947
1948 return ret;
1949 }
1950
1951 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1952 {
1953 struct smatch_state *state;
1954 struct string_list *links;
1955 struct state_list *ret = NULL;
1956 struct sm_state *sm;
1957 char *tmp;
1958
1959 state = get_state_chunk(link_id, expr);
1960 if (!state)
1961 return NULL;
1962 links = state->data;
1963
1964 FOR_EACH_PTR(links, tmp) {
1965 sm = get_sm_state(comparison_id, tmp, NULL);
1966 if (!sm)
1967 continue;
1968 if (!strchr(sm->state->name, '='))
1969 continue;
1970 if (strcmp(sm->state->name, "!=") == 0)
1971 continue;
1972 add_ptr_list(&ret, sm);
1973 } END_FOR_EACH_PTR(tmp);
1974
1975 return ret;
1976 }
1977
1978 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1979 {
1980 struct smatch_state *state;
1981 struct string_list *links;
1982 struct state_list *ret = NULL;
1983 struct sm_state *sm;
1984 struct sm_state *possible;
1985 char *link;
1986
1987 return NULL;
1988
1989 state = get_state_chunk(link_id, expr);
1990 if (!state)
1991 return NULL;
1992 links = state->data;
1993
1994 FOR_EACH_PTR(links, link) {
1995 sm = get_sm_state(comparison_id, link, NULL);
1996 if (!sm)
1997 continue;
1998 FOR_EACH_PTR(sm->possible, possible) {
1999 if (strcmp(possible->state->name, "!=") != 0)
2000 continue;
2001 add_ptr_list(&ret, sm);
2002 break;
2003 } END_FOR_EACH_PTR(possible);
2004 } END_FOR_EACH_PTR(link);
2005
2006 return ret;
2007 }
2008
2009 static void update_links_from_call(struct expression *left,
2010 int left_compare,
2011 struct expression *right)
2012 {
2013 struct string_list *links;
2014 struct smatch_state *state;
2015 struct compare_data *data;
2016 struct symbol *left_sym, *right_sym;
2017 char *left_var = NULL;
2018 char *right_var = NULL;
2019 struct var_sym_list *left_vsl;
2020 struct expression *expr;
2021 const char *var;
2022 struct var_sym_list *vsl;
2023 int comparison;
2024 char *tmp;
2025
2026 left_var = chunk_to_var_sym(left, &left_sym);
2027 if (!left_var)
2028 goto done;
2029 left_vsl = expr_to_vsl(left);
2030 right_var = chunk_to_var_sym(right, &right_sym);
2031 if (!right_var)
2032 goto done;
2033
2034 state = get_state(link_id, right_var, right_sym);
2035 if (!state)
2036 return;
2037 links = state->data;
2038
2039 FOR_EACH_PTR(links, tmp) {
2040 state = get_state(comparison_id, tmp, NULL);
2041 if (!state || !state->data)
2042 continue;
2043 data = state->data;
2044 comparison = data->comparison;
2045 expr = data->right;
2046 var = data->right_var;
2047 vsl = data->right_vsl;
2048 if (strcmp(var, right_var) == 0) {
2049 expr = data->left;
2050 var = data->left_var;
2051 vsl = data->left_vsl;
2052 comparison = flip_comparison(comparison);
2053 }
2054 comparison = combine_comparisons(left_compare, comparison);
2055 if (!comparison)
2056 continue;
2057 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl, NULL);
2058 } END_FOR_EACH_PTR(tmp);
2059
2060 done:
2061 free_string(right_var);
2062 }
2063
2064 static void return_str_comparison(struct expression *expr, const char *range)
2065 {
2066 struct expression *arg;
2067 int comparison;
2068 char buf[16];
2069
2070 while (expr->type == EXPR_ASSIGNMENT)
2071 expr = strip_expr(expr->right);
2072 if (expr->type != EXPR_CALL)
2073 return;
2074 if (!str_to_comparison_arg(range, expr, &comparison, &arg))
2075 return;
2076 snprintf(buf, sizeof(buf), "%s", show_comparison(comparison));
2077 update_links_from_call(expr, comparison, arg);
2078 add_comparison(expr, comparison, arg);
2079 }
2080
2081 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
2082 {
2083 copy_comparisons(expr, call);
2084 }
2085
2086 static char *get_mask_comparison(struct expression *expr, int ignore)
2087 {
2088 struct expression *tmp, *right;
2089 int count, param;
2090 char buf[256];
2091
2092 /* The return value for "return foo & param;" is <= param */
2093
2094 count = 0;
2095 while ((tmp = get_assigned_expr(expr))) {
2096 expr = strip_expr(tmp);
2097 if (count++ > 4)
2098 break;
2099 }
2100
2101 if (expr->type != EXPR_BINOP || expr->op != '&')
2102 return NULL;
2103
2104 right = strip_expr(expr->right);
2105 param = get_param_num(right);
2106 if (param < 0 || param == ignore)
2107 return NULL;
2108
2109 snprintf(buf, sizeof(buf), "[<=$%d]", param);
2110 return alloc_sname(buf);
2111 }
2112
2113 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
2114 {
2115 struct symbol *param;
2116 char *var = NULL;
2117 char buf[256];
2118 char *ret_str = NULL;
2119 int compare;
2120 int i;
2121
2122 if (!expr)
2123 return NULL;
2124
2125 var = chunk_to_var(expr);
2126 if (!var)
2127 goto try_mask;
2128
2129 i = -1;
2130 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2131 i++;
2132 if (i == ignore)
2133 continue;
2134 if (!param->ident)
2135 continue;
2136 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2137 compare = get_comparison_strings(var, buf);
2138 if (compare == UNKNOWN_COMPARISON ||
2139 compare == IMPOSSIBLE_COMPARISON)
2140 continue;
2141 if (show_comparison(compare)[0] != starts_with)
2142 continue;
2143 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2144 ret_str = alloc_sname(buf);
2145 break;
2146 } END_FOR_EACH_PTR(param);
2147
2148 free_string(var);
2149 if (!ret_str)
2150 goto try_mask;
2151
2152 return ret_str;
2153
2154 try_mask:
2155 if (starts_with == '<')
2156 ret_str = get_mask_comparison(expr, ignore);
2157 return ret_str;
2158 }
2159
2160 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
2161 {
2162 struct symbol *param;
2163 char buf[256];
2164 int compare;
2165 int i;
2166
2167 i = -1;
2168 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2169 i++;
2170 if (!param->ident)
2171 continue;
2172 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2173 compare = get_comparison_strings(name, buf);
2174 if (compare == UNKNOWN_COMPARISON ||
2175 compare == IMPOSSIBLE_COMPARISON)
2176 continue;
2177 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2178 return alloc_sname(buf);
2179 } END_FOR_EACH_PTR(param);
2180
2181 return NULL;
2182 }
2183
2184 char *expr_equal_to_param(struct expression *expr, int ignore)
2185 {
2186 return range_comparison_to_param_helper(expr, '=', ignore);
2187 }
2188
2189 char *expr_lte_to_param(struct expression *expr, int ignore)
2190 {
2191 return range_comparison_to_param_helper(expr, '<', ignore);
2192 }
2193
2194 char *expr_param_comparison(struct expression *expr, int ignore)
2195 {
2196 struct symbol *param;
2197 char *var = NULL;
2198 char buf[256];
2199 char *ret_str = NULL;
2200 int compare;
2201 int i;
2202
2203 var = chunk_to_var(expr);
2204 if (!var)
2205 goto free;
2206
2207 i = -1;
2208 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2209 i++;
2210 if (i == ignore)
2211 continue;
2212 if (!param->ident)
2213 continue;
2214 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2215 compare = get_comparison_strings(var, buf);
2216 if (!compare)
2217 continue;
2218 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2219 ret_str = alloc_sname(buf);
2220 break;
2221 } END_FOR_EACH_PTR(param);
2222
2223 free:
2224 free_string(var);
2225 return ret_str;
2226 }
2227
2228 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
2229 {
2230 struct expression *arg;
2231 char *name;
2232 struct symbol *sym;
2233 static char buf[256];
2234 int len;
2235 int i;
2236
2237 i = -1;
2238 FOR_EACH_PTR(call->args, arg) {
2239 i++;
2240
2241 name = expr_to_var_sym(arg, &sym);
2242 if (!name || !sym)
2243 continue;
2244 if (sym != param_sym)
2245 continue;
2246
2247 len = strlen(name);
2248 if (strncmp(name, param_name, len) != 0)
2249 continue;
2250 if (param_name[len] == '\0') {
2251 snprintf(buf, sizeof(buf), "$%d", i);
2252 return buf;
2253 }
2254 if (param_name[len] != '-')
2255 continue;
2256 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
2257 return buf;
2258 } END_FOR_EACH_PTR(arg);
2259
2260 return NULL;
2261 }
2262
2263 static void match_call_info(struct expression *expr)
2264 {
2265 struct expression *arg;
2266 struct smatch_state *state;
2267 struct sm_state *sm;
2268 struct compare_data *data;
2269 int comparison;
2270 struct string_list *links;
2271 char *arg_name;
2272 const char *right_name;
2273 char *link;
2274 char info_buf[256];
2275 int i;
2276
2277 i = -1;
2278 FOR_EACH_PTR(expr->args, arg) {
2279 i++;
2280
2281 state = get_state_chunk(link_id, arg);
2282 if (!state)
2283 continue;
2284
2285 links = state->data;
2286 FOR_EACH_PTR(links, link) {
2287 struct var_sym_list *right_vsl;
2288 struct var_sym *right_vs;
2289
2290 if (strstr(link, " orig"))
2291 continue;
2292 sm = get_sm_state(comparison_id, link, NULL);
2293 if (!sm)
2294 continue;
2295 data = sm->state->data;
2296 if (!data ||
2297 data->comparison == UNKNOWN_COMPARISON ||
2298 data->comparison == IMPOSSIBLE_COMPARISON)
2299 continue;
2300 arg_name = expr_to_var(arg);
2301 if (!arg_name)
2302 continue;
2303
2304 right_vsl = NULL;
2305 if (strcmp(data->left_var, arg_name) == 0) {
2306 comparison = data->comparison;
2307 right_name = data->right_var;
2308 right_vsl = data->right_vsl;
2309 } else if (strcmp(data->right_var, arg_name) == 0) {
2310 comparison = flip_comparison(data->comparison);
2311 right_name = data->left_var;
2312 right_vsl = data->left_vsl;
2313 }
2314 if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
2315 goto free;
2316
2317 right_vs = first_ptr_list((struct ptr_list *)right_vsl);
2318 if (strcmp(right_vs->var, right_name) != 0)
2319 goto free;
2320 right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
2321 if (!right_name)
2322 goto free;
2323 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(comparison), right_name);
2324 sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
2325
2326 free:
2327 free_string(arg_name);
2328 } END_FOR_EACH_PTR(link);
2329 } END_FOR_EACH_PTR(arg);
2330 }
2331
2332 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
2333 {
2334 struct sm_state *compare_sm;
2335 struct string_list *links;
2336 char *link;
2337 struct compare_data *data;
2338 struct var_sym *left, *right;
2339 static char info_buf[256];
2340 const char *right_name;
2341
2342 if (strstr(printed_name, " orig"))
2343 return;
2344
2345 links = link_sm->state->data;
2346 FOR_EACH_PTR(links, link) {
2347 compare_sm = get_sm_state(comparison_id, link, NULL);
2348 if (!compare_sm)
2349 continue;
2350 data = compare_sm->state->data;
2351 if (!data || !data->comparison)
2352 continue;
2353
2354 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2355 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2356 continue;
2357 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2358 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2359 if (left->sym == right->sym &&
2360 strcmp(left->var, right->var) == 0)
2361 continue;
2362 /*
2363 * Both parameters link to this comparison so only
2364 * record the first one.
2365 */
2366 if (left->sym != link_sm->sym ||
2367 strcmp(left->var, link_sm->name) != 0)
2368 continue;
2369
2370 right_name = get_printed_param_name(call, right->var, right->sym);
2371 if (!right_name)
2372 continue;
2373 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_name);
2374 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
2375 } END_FOR_EACH_PTR(link);
2376 }
2377
2378 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
2379 {
2380 char *name;
2381 const char *tmp_name;
2382 struct symbol *sym;
2383 int param;
2384 char info_buf[256];
2385 bool is_addr = false;
2386
2387 /*
2388 * TODO: This only prints == comparisons. That's probably the most
2389 * useful comparison because == max has lots of implications. But it
2390 * would be good to capture the rest as well.
2391 *
2392 * This information is already in the DB but it's in the parameter math
2393 * bits and it's awkward to use it. This is is the simpler, possibly
2394 * cleaner way, but not necessarily the best, I don't know.
2395 */
2396
2397 if (!expr)
2398 return;
2399 name = expr_to_var_sym(expr, &sym);
2400 if (!name || !sym)
2401 goto free;
2402
2403 param = get_param_num_from_sym(sym);
2404 if (param < 0)
2405 goto free;
2406 if (param_was_set_var_sym(name, sym))
2407 goto free;
2408
2409 tmp_name = get_param_name_var_sym(name, sym);
2410 if (!tmp_name)
2411 goto free;
2412
2413 if (tmp_name[0] == '&') {
2414 tmp_name += 2;
2415 is_addr = true;
2416 } else {
2417 tmp_name += 1;
2418 }
2419
2420 snprintf(info_buf, sizeof(info_buf), "== %s$%d%s", is_addr ? "&" : "", param, tmp_name);
2421 sql_insert_return_states(return_id, return_ranges,
2422 PARAM_COMPARE, -1, "$", info_buf);
2423 free:
2424 free_string(name);
2425 }
2426
2427 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2428 {
2429 struct sm_state *tmp;
2430 struct string_list *links;
2431 char *link;
2432 struct sm_state *sm;
2433 struct compare_data *data;
2434 struct var_sym *left, *right;
2435 int left_param, right_param;
2436 const char *left_key, *right_key;
2437 char info_buf[258];
2438 int compare_type;
2439
2440 print_return_value_comparison(return_id, return_ranges, expr);
2441
2442 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2443 left_param = get_param_key_from_var_sym(tmp->name, tmp->sym, expr, &left_key);
2444 if (left_param < -1 || !left_key)
2445 continue;
2446
2447 links = tmp->state->data;
2448 FOR_EACH_PTR(links, link) {
2449 if (strncmp(link, "$size", 5) == 0)
2450 continue;
2451 sm = get_sm_state(comparison_id, link, NULL);
2452 if (!sm)
2453 continue;
2454 data = sm->state->data;
2455 if (!data ||
2456 data->comparison == UNKNOWN_COMPARISON ||
2457 data->comparison == IMPOSSIBLE_COMPARISON)
2458 continue;
2459 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2460 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2461 continue;
2462 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2463 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2464 if (left->sym == right->sym &&
2465 strcmp(left->var, right->var) == 0)
2466 continue;
2467 /*
2468 * The both foo and bar in the "foo == bar" comparison
2469 * have link states. To avoid duplicates only parse
2470 * the comparison if the link state is on the left.
2471 *
2472 * And actually let's move getting the left_name outside
2473 * the loop.
2474 *
2475 */
2476 if (left->sym != tmp->sym ||
2477 strcmp(left->var, tmp->name) != 0)
2478 continue;
2479
2480 if (strstr(right->var, " orig"))
2481 continue;
2482
2483 right_param = get_param_key_from_var_sym(right->var, right->sym, expr, &right_key);
2484 if (right_param < 0 || !right_key || right_key[0] != '$')
2485 continue;
2486
2487 /*
2488 * The same param can have multiple names so we can get
2489 * duplicates.
2490 */
2491 if (left_param == right_param &&
2492 strcmp(left_key, right_key) == 0)
2493 continue;
2494
2495 compare_type = PARAM_COMPARE;
2496 if (!param_was_set_var_sym(right->var, right->sym) &&
2497 !param_was_set_var_sym(left->var, left->sym))
2498 compare_type = COMPARE_LIMIT;
2499
2500 snprintf(info_buf, sizeof(info_buf), "%s $%d%s",
2501 show_comparison(data->comparison), right_param, right_key + 1);
2502 sql_insert_return_states(return_id, return_ranges,
2503 compare_type, left_param, left_key, info_buf);
2504 } END_FOR_EACH_PTR(link);
2505
2506 } END_FOR_EACH_SM(tmp);
2507 }
2508
2509 static int parse_comparison(char **value, int *op)
2510 {
2511
2512 *op = **value;
2513
2514 switch (*op) {
2515 case '<':
2516 (*value)++;
2517 if (**value == '=') {
2518 (*value)++;
2519 *op = SPECIAL_LTE;
2520 }
2521 break;
2522 case '=':
2523 (*value)++;
2524 (*value)++;
2525 *op = SPECIAL_EQUAL;
2526 break;
2527 case '!':
2528 (*value)++;
2529 (*value)++;
2530 *op = SPECIAL_NOTEQUAL;
2531 break;
2532 case '>':
2533 (*value)++;
2534 if (**value == '=') {
2535 (*value)++;
2536 *op = SPECIAL_GTE;
2537 }
2538 break;
2539 default:
2540 return 0;
2541 }
2542
2543 if (**value != ' ') {
2544 sm_perror("parsing comparison. %s", *value);
2545 return 0;
2546 }
2547
2548 (*value)++;
2549 return 1;
2550 }
2551
2552 static int split_op_param_key(char *value, int *op, int *param, char **key)
2553 {
2554 static char buf[256];
2555 char *p;
2556
2557 if (!parse_comparison(&value, op))
2558 return 0;
2559
2560 snprintf(buf, sizeof(buf), "%s", value);
2561
2562 p = buf;
2563 if (*p++ != '$')
2564 return 0;
2565
2566 *param = atoi(p);
2567 if (*param < 0 || *param > 99)
2568 return 0;
2569 p++;
2570 if (*param > 9)
2571 p++;
2572 p--;
2573 *p = '$';
2574 *key = p;
2575
2576 return 1;
2577 }
2578
2579 void select_caller_info(const char *name, struct symbol *sym, char *value)
2580 {
2581 struct var_sym_list *left_vsl = NULL;
2582 struct var_sym_list *right_vsl = NULL;
2583 char *right_key, *p, *right_name;
2584 struct symbol *right_sym;
2585 char comparison_name[128];
2586 char right_buf[128];
2587 int op, right_param;
2588
2589 if (!split_op_param_key(value, &op, &right_param, &right_key))
2590 return;
2591
2592 right_sym = get_param_sym_from_num(right_param);
2593 if (!right_sym || !right_sym->ident)
2594 return;
2595
2596 p = strchr(right_key, '$');
2597 if (!p)
2598 return;
2599
2600 snprintf(right_buf, sizeof(right_buf), "%.*s%s%s", (int)(p - right_key),
2601 right_key, right_sym->ident->name, p + 1);
2602 right_name = right_buf;
2603
2604 if (strcmp(name, right_name) > 0) {
2605 struct symbol *tmp_sym = sym;
2606 char *tmp_name = (char *)name;
2607
2608 name = right_name;
2609 sym = right_sym;
2610 right_name = tmp_name;
2611 right_sym = tmp_sym;
2612 op = flip_comparison(op);
2613 }
2614
2615 add_var_sym(&left_vsl, name, sym);
2616 add_var_sym(&right_vsl, right_name, right_sym);
2617
2618 snprintf(comparison_name, sizeof(comparison_name), "%s vs %s", name, right_name);
2619
2620 set_state(comparison_id, comparison_name, NULL,
2621 alloc_compare_state(NULL, name, left_vsl,
2622 op,
2623 NULL, right_name, right_vsl));
2624 }
2625
2626 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2627 {
2628 struct expression *left_arg, *right_arg;
2629 char *left_name = NULL;
2630 struct symbol *left_sym;
2631 char *right_name = NULL;
2632 struct symbol *right_sym;
2633 int op;
2634 int right_param;
2635 char *right_key;
2636 struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2637
2638 if (left_param == -1) {
2639 if (expr->type != EXPR_ASSIGNMENT)
2640 return;
2641 left_arg = strip_expr(expr->left);
2642
2643 while (expr->type == EXPR_ASSIGNMENT)
2644 expr = strip_expr(expr->right);
2645 if (expr->type != EXPR_CALL)
2646 return;
2647 } else {
2648 while (expr->type == EXPR_ASSIGNMENT)
2649 expr = strip_expr(expr->right);
2650 if (expr->type != EXPR_CALL)
2651 return;
2652
2653 left_arg = get_argument_from_call_expr(expr->args, left_param);
2654 if (!left_arg)
2655 return;
2656 }
2657
2658 if (!split_op_param_key(value, &op, &right_param, &right_key))
2659 return;
2660
2661 right_arg = get_argument_from_call_expr(expr->args, right_param);
2662 if (!right_arg)
2663 return;
2664
2665 left_name = get_variable_from_key(left_arg, key, &left_sym);
2666 if (!left_name || !left_sym)
2667 goto free;
2668
2669 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2670 if (!right_name || !right_sym)
2671 goto free;
2672
2673 add_var_sym(&left_vsl, left_name, left_sym);
2674 add_var_sym(&right_vsl, right_name, right_sym);
2675
2676 add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl, NULL);
2677
2678 free:
2679 free_string(left_name);
2680 free_string(right_name);
2681 }
2682
2683 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2684 {
2685 char *left_name = NULL;
2686 char *right_name = NULL;
2687 struct symbol *left_sym, *right_sym;
2688 struct expression *left_arg, *right_arg;
2689 int op, state_op;
2690 int right_param;
2691 char *right_key;
2692 int ret = 0;
2693
2694 while (expr->type == EXPR_ASSIGNMENT)
2695 expr = strip_expr(expr->right);
2696 if (expr->type != EXPR_CALL)
2697 return 0;
2698
2699 if (!split_op_param_key(value, &op, &right_param, &right_key))
2700 return 0;
2701
2702 left_arg = get_argument_from_call_expr(expr->args, left_param);
2703 if (!left_arg)
2704 return 0;
2705
2706 right_arg = get_argument_from_call_expr(expr->args, right_param);
2707 if (!right_arg)
2708 return 0;
2709
2710 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2711 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2712 if (!left_name || !right_name)
2713 goto free;
2714
2715 state_op = get_comparison_strings(left_name, right_name);
2716 if (!state_op)
2717 goto free;
2718
2719 if (comparison_intersection(remove_unsigned_from_comparison(state_op), op)
2720 == IMPOSSIBLE_COMPARISON)
2721 ret = 1;
2722 free:
2723 free_string(left_name);
2724 free_string(right_name);
2725 return ret;
2726 }
2727
2728 int impossibly_high_comparison(struct expression *expr)
2729 {
2730 struct smatch_state *link_state;
2731 struct sm_state *sm;
2732 struct string_list *links;
2733 char *link;
2734 struct compare_data *data;
2735
2736 link_state = get_state_expr(link_id, expr);
2737 if (!link_state) {
2738 if (expr->type == EXPR_BINOP &&
2739 (impossibly_high_comparison(expr->left) ||
2740 impossibly_high_comparison(expr->right)))
2741 return 1;
2742 return 0;
2743 }
2744
2745 links = link_state->data;
2746 FOR_EACH_PTR(links, link) {
2747 sm = get_sm_state(comparison_id, link, NULL);
2748 if (!sm)
2749 continue;
2750 data = sm->state->data;
2751 if (!data)
2752 continue;
2753 if (!possibly_true(data->left, data->comparison, data->right))
2754 return 1;
2755 } END_FOR_EACH_PTR(link);
2756
2757 return 0;
2758 }
2759
2760 static void free_data(struct symbol *sym)
2761 {
2762 if (__inline_fn)
2763 return;
2764 clear_compare_data_alloc();
2765 }
2766
2767 void register_comparison(int id)
2768 {
2769 comparison_id = id;
2770 set_dynamic_states(comparison_id);
2771 add_hook(&save_start_states, AFTER_DEF_HOOK);
2772 add_unmatched_state_hook(comparison_id, unmatched_comparison);
2773 add_pre_merge_hook(comparison_id, &pre_merge_hook);
2774 add_merge_hook(comparison_id, &merge_compare_states);
2775 add_hook(&free_data, AFTER_FUNC_HOOK);
2776
2777 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2778 select_caller_name_sym(&select_caller_info, PARAM_COMPARE);
2779
2780 add_split_return_callback(&print_return_comparison);
2781 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2782
2783 add_hook(&match_preop, OP_HOOK);
2784 }
2785
2786 void register_comparison_late(int id)
2787 {
2788 add_hook(&match_assign, ASSIGNMENT_HOOK);
2789 add_return_string_hook(return_str_comparison);
2790 }
2791
2792 void register_comparison_links(int id)
2793 {
2794 link_id = id;
2795 db_ignore_states(link_id);
2796 set_dynamic_states(link_id);
2797 add_merge_hook(link_id, &merge_links);
2798 add_modification_hook(link_id, &match_modify);
2799 add_modification_hook_late(link_id, match_inc_dec);
2800
2801 add_member_info_callback(link_id, struct_member_callback);
2802 }
2803
2804 void register_comparison_inc_dec(int id)
2805 {
2806 inc_dec_id = id;
2807 add_modification_hook_late(inc_dec_id, &iter_modify);
2808 }
2809
2810 void register_comparison_inc_dec_links(int id)
2811 {
2812 inc_dec_link_id = id;
2813 set_dynamic_states(inc_dec_link_id);
2814 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2815 }
2816
2817 static struct sm_state *clone_partial_sm(struct sm_state *sm, int comparison)
2818 {
2819 struct compare_data *data;
2820 struct sm_state *clone;
2821 struct stree *stree;
2822
2823 data = sm->state->data;
2824
2825 clone = clone_sm(sm);
2826 clone->state = alloc_compare_state(data->left, data->left_var, data->left_vsl,
2827 comparison,
2828 data->right, data->right_var, data->right_vsl);
2829 free_slist(&clone->possible);
2830 add_possible_sm(clone, clone);
2831
2832 stree = clone_stree(sm->pool);
2833 overwrite_sm_state_stree(&stree, clone);
2834 clone->pool = stree;
2835
2836 return clone;
2837 }
2838
2839 static void create_fake_history(struct sm_state *sm, int op,
2840 struct state_list **true_stack,
2841 struct state_list **false_stack)
2842 {
2843 struct sm_state *true_sm, *false_sm;
2844 struct compare_data *data;
2845 int true_comparison;
2846 int false_comparison;
2847
2848 data = sm->state->data;
2849
2850 if (is_merged(sm) || sm->left || sm->right)
2851 return;
2852
2853 true_comparison = comparison_intersection(data->comparison, op);
2854 false_comparison = comparison_intersection(data->comparison, negate_comparison(op));
2855
2856 true_sm = clone_partial_sm(sm, true_comparison);
2857 false_sm = clone_partial_sm(sm, false_comparison);
2858
2859 sm->merged = 1;
2860 sm->left = true_sm;
2861 sm->right = false_sm;
2862
2863 add_ptr_list(true_stack, true_sm);
2864 add_ptr_list(false_stack, false_sm);
2865 }
2866
2867 static void filter_by_sm(struct sm_state *sm, int op,
2868 struct state_list **true_stack,
2869 struct state_list **false_stack,
2870 bool *useful)
2871 {
2872 struct compare_data *data;
2873 int is_true = 0;
2874 int is_false = 0;
2875
2876 if (!sm)
2877 return;
2878 data = sm->state->data;
2879 if (!data)
2880 goto split;
2881 if (data->comparison == IMPOSSIBLE_COMPARISON)
2882 return;
2883
2884 /*
2885 * We want to check that "data->comparison" is totally inside "op". So
2886 * if data->comparison is < and op is <= then that's true. Or if
2887 * data->comparison is == and op is <= then that's true. But if
2888 * data->comparison is <= and op is < than that's neither true nor
2889 * false.
2890 */
2891 if (data->comparison == comparison_intersection(data->comparison, op))
2892 is_true = 1;
2893 if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
2894 is_false = 1;
2895
2896 if (!is_true && !is_false && !is_merged(sm)) {
2897 create_fake_history(sm, op, true_stack, false_stack);
2898 return;
2899 }
2900
2901 if (debug_implied()) {
2902 sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2903 __func__,
2904 sm->state->name,
2905 alloc_sname(show_comparison(op)),
2906 alloc_sname(show_comparison(negate_comparison(op))),
2907 alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
2908 alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
2909 show_sm(sm));
2910 }
2911
2912 *useful = true;
2913 if (is_true)
2914 add_ptr_list(true_stack, sm);
2915 if (is_false)
2916 add_ptr_list(false_stack, sm);
2917 split:
2918 filter_by_sm(sm->left, op, true_stack, false_stack, useful);
2919 filter_by_sm(sm->right, op, true_stack, false_stack, useful);
2920 }
2921
2922 struct sm_state *comparison_implication_hook(struct expression *expr,
2923 struct state_list **true_stack,
2924 struct state_list **false_stack)
2925 {
2926 struct sm_state *sm;
2927 char *left, *right;
2928 int op;
2929 static char buf[256];
2930 bool useful = false;
2931
2932 if (expr->type != EXPR_COMPARE)
2933 return NULL;
2934
2935 op = expr->op;
2936
2937 left = expr_to_var(expr->left);
2938 right = expr_to_var(expr->right);
2939 if (!left || !right) {
2940 free_string(left);
2941 free_string(right);
2942 return NULL;
2943 }
2944
2945 if (strcmp(left, right) > 0) {
2946 char *tmp = left;
2947
2948 left = right;
2949 right = tmp;
2950 op = flip_comparison(op);
2951 }
2952
2953 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2954 sm = get_sm_state(comparison_id, buf, NULL);
2955 if (!sm)
2956 return NULL;
2957 if (!sm->merged)
2958 return NULL;
2959
2960 filter_by_sm(sm, op, true_stack, false_stack, &useful);
2961 if (!useful)
2962 return NULL;
2963
2964 if (debug_implied())
2965 sm_msg("implications from comparison: (%s)", show_sm(sm));
2966
2967 return sm;
2968 }
Static analysis for C