?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
atomic_inc_dec: add this to check_list.h
[smatch.git] / smatch_comparison.c
blobcbea2682641dab07a481f4bfb03e2265cf573963
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 char *tmp;
587 int i;
588
589 state = __alloc_smatch_state(0);
590
591 i = 0;
592 FOR_EACH_PTR(links, tmp) {
593 if (!i++) {
594 snprintf(buf, sizeof(buf), "%s", tmp);
595 } else {
596 append(buf, ", ", sizeof(buf));
597 append(buf, tmp, sizeof(buf));
598 }
599 } END_FOR_EACH_PTR(tmp);
600
601 state->name = alloc_sname(buf);
602 state->data = links;
603 return state;
604 }
605
606 static void save_start_states(struct statement *stmt)
607 {
608 struct symbol *param;
609 char orig[64];
610 char state_name[128];
611 struct smatch_state *state;
612 struct string_list *links;
613 char *link;
614
615 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
616 struct var_sym_list *left_vsl = NULL;
617 struct var_sym_list *right_vsl = NULL;
618
619 if (!param->ident)
620 continue;
621 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
622 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
623 add_var_sym(&left_vsl, param->ident->name, param);
624 add_var_sym(&right_vsl, orig, param);
625 state = alloc_compare_state(
626 NULL, param->ident->name, left_vsl,
627 SPECIAL_EQUAL,
628 NULL, alloc_sname(orig), right_vsl);
629 set_state(comparison_id, state_name, NULL, state);
630
631 link = alloc_sname(state_name);
632 links = NULL;
633 insert_string(&links, link);
634 state = alloc_link_state(links);
635 set_state(link_id, param->ident->name, param, state);
636 } END_FOR_EACH_PTR(param);
637 }
638
639 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
640 {
641 struct smatch_state *ret;
642 struct string_list *links;
643
644 links = combine_string_lists(s1->data, s2->data);
645 ret = alloc_link_state(links);
646 return ret;
647 }
648
649 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
650 {
651 struct smatch_state *old_state, *new_state;
652 struct string_list *links;
653 char *new;
654
655 old_state = get_state(link_id, var, sym);
656 if (old_state)
657 links = clone_str_list(old_state->data);
658 else
659 links = NULL;
660
661 new = alloc_sname(link);
662 insert_string(&links, new);
663
664 new_state = alloc_link_state(links);
665 set_state(link_id, var, sym, new_state);
666 }
667
668 static void match_inc(struct sm_state *sm, bool preserve)
669 {
670 struct string_list *links;
671 struct smatch_state *state, *new;
672 struct compare_data *data;
673 char *tmp;
674 int flip;
675 int op;
676
677 links = sm->state->data;
678
679 FOR_EACH_PTR(links, tmp) {
680 state = get_state(comparison_id, tmp, NULL);
681 if (!state)
682 continue;
683 data = state->data;
684 if (!data)
685 continue;
686
687 flip = 0;
688 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
689 tmp[strlen(sm->name)] != ' ')
690 flip = 1;
691
692 op = state_to_comparison(state);
693
694 switch (flip ? flip_comparison(op) : op) {
695 case SPECIAL_EQUAL:
696 case SPECIAL_GTE:
697 case SPECIAL_UNSIGNED_GTE:
698 case '>':
699 case SPECIAL_UNSIGNED_GT:
700 if (preserve)
701 break;
702 new = alloc_compare_state(
703 data->left, data->left_var, data->left_vsl,
704 flip ? '<' : '>',
705 data->right, data->right_var, data->right_vsl);
706 set_state(comparison_id, tmp, NULL, new);
707 break;
708 case '<':
709 case SPECIAL_UNSIGNED_LT:
710 new = alloc_compare_state(
711 data->left, data->left_var, data->left_vsl,
712 flip ? SPECIAL_GTE : SPECIAL_LTE,
713 data->right, data->right_var, data->right_vsl);
714 set_state(comparison_id, tmp, NULL, new);
715 break;
716 default:
717 new = alloc_compare_state(
718 data->left, data->left_var, data->left_vsl,
719 UNKNOWN_COMPARISON,
720 data->right, data->right_var, data->right_vsl);
721 set_state(comparison_id, tmp, NULL, new);
722 }
723 } END_FOR_EACH_PTR(tmp);
724 }
725
726 static void match_dec(struct sm_state *sm, bool preserve)
727 {
728 struct string_list *links;
729 struct smatch_state *state;
730 char *tmp;
731
732 links = sm->state->data;
733
734 FOR_EACH_PTR(links, tmp) {
735 struct compare_data *data;
736 struct smatch_state *new;
737
738 state = get_state(comparison_id, tmp, NULL);
739 if (!state || !state->data)
740 continue;
741
742 data = state->data;
743
744 switch (state_to_comparison(state)) {
745 case SPECIAL_EQUAL:
746 case SPECIAL_LTE:
747 case SPECIAL_UNSIGNED_LTE:
748 case '<':
749 case SPECIAL_UNSIGNED_LT: {
750 if (preserve)
751 break;
752
753 new = alloc_compare_state(
754 data->left, data->left_var, data->left_vsl,
755 '<',
756 data->right, data->right_var, data->right_vsl);
757 set_state(comparison_id, tmp, NULL, new);
758 break;
759 }
760 default:
761 new = alloc_compare_state(
762 data->left, data->left_var, data->left_vsl,
763 UNKNOWN_COMPARISON,
764 data->right, data->right_var, data->right_vsl);
765 set_state(comparison_id, tmp, NULL, new);
766 }
767 } END_FOR_EACH_PTR(tmp);
768 }
769
770 static void reset_sm(struct sm_state *sm)
771 {
772 struct string_list *links;
773 char *tmp;
774
775 links = sm->state->data;
776
777 FOR_EACH_PTR(links, tmp) {
778 struct smatch_state *old, *new;
779
780 old = get_state(comparison_id, tmp, NULL);
781 if (!old || !old->data) {
782 new = &undefined;
783 } else {
784 struct compare_data *data = old->data;
785
786 new = alloc_compare_state(
787 data->left, data->left_var, data->left_vsl,
788 UNKNOWN_COMPARISON,
789 data->right, data->right_var, data->right_vsl);
790 }
791 set_state(comparison_id, tmp, NULL, new);
792 } END_FOR_EACH_PTR(tmp);
793 set_state(link_id, sm->name, sm->sym, &undefined);
794 }
795
796 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
797 {
798 struct range_list *rl;
799 sval_t zero = { .type = &int_ctype };
800
801 if (!expr || expr->type != EXPR_ASSIGNMENT)
802 return false;
803 if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
804 return false;
805
806 get_absolute_rl(expr->right, &rl);
807 if (sval_is_negative(rl_min(rl))) {
808 reset_sm(sm);
809 return false;
810 }
811
812 if (expr->op == SPECIAL_ADD_ASSIGN)
813 match_inc(sm, rl_has_sval(rl, zero));
814 else
815 match_dec(sm, rl_has_sval(rl, zero));
816 return true;
817 }
818
819 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
820 {
821 /*
822 * if (foo > bar) then ++foo is also > bar.
823 */
824 if (!mod_expr)
825 return;
826 if (match_add_sub_assign(sm, mod_expr))
827 return;
828 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
829 return;
830
831 if (mod_expr->op == SPECIAL_INCREMENT)
832 match_inc(sm, false);
833 else if (mod_expr->op == SPECIAL_DECREMENT)
834 match_dec(sm, false);
835 }
836
837 static int is_self_assign(struct expression *expr)
838 {
839 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
840 return 0;
841 return expr_equiv(expr->left, expr->right);
842 }
843
844 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
845 {
846 if (mod_expr && is_self_assign(mod_expr))
847 return;
848
849 /* handled by match_inc_dec() */
850 if (mod_expr &&
851 ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
852 (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
853 return;
854 if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT &&
855 (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN))
856 return;
857
858 reset_sm(sm);
859 }
860
861 static void match_preop(struct expression *expr)
862 {
863 struct expression *parent;
864 struct range_list *left, *right;
865 int op;
866
867 /*
868 * This is an important special case. Say you have:
869 *
870 * if (++j == limit)
871 *
872 * Assume that we know the range of limit is higher than the start
873 * value for "j". Then the first thing that we process is the ++j. We
874 * have not comparison states set up so it doesn't get caught by the
875 * modification hook. But it does get caught by smatch_extra which sets
876 * j to unknown then we parse the "j == limit" and sets false to != but
877 * really we want false to be <.
878 *
879 * So what we do is we set j < limit here, then the match_modify catches
880 * it and we do a match_inc_dec().
881 *
882 */
883
884 if (expr->type != EXPR_PREOP ||
885 (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT))
886 return;
887
888 parent = expr_get_parent_expr(expr);
889 if (!parent)
890 return;
891 if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL)
892 return;
893 if (parent->left != expr)
894 return;
895
896 if (!get_implied_rl(expr->unop, &left) ||
897 !get_implied_rl(parent->right, &right))
898 return;
899
900 op = rl_comparison(left, right);
901 if (op == UNKNOWN_COMPARISON)
902 return;
903
904 add_comparison(expr->unop, op, parent->right);
905 }
906
907 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
908 {
909 expr = strip_expr(expr);
910 if (!expr)
911 return NULL;
912 if (sym)
913 *sym = NULL;
914
915 if (expr->type == EXPR_PREOP &&
916 (expr->op == SPECIAL_INCREMENT ||
917 expr->op == SPECIAL_DECREMENT))
918 expr = strip_expr(expr->unop);
919
920 if (expr->type == EXPR_CALL) {
921 char buf[64];
922
923 snprintf(buf, sizeof(buf), "return %p", expr);
924 return alloc_string(buf);
925 }
926
927 return expr_to_chunk_sym_vsl(expr, sym, NULL);
928 }
929
930 static char *chunk_to_var(struct expression *expr)
931 {
932 return chunk_to_var_sym(expr, NULL);
933 }
934
935 static struct smatch_state *get_state_chunk(int owner, struct expression *expr)
936 {
937 char *name;
938 struct symbol *sym;
939 struct smatch_state *ret;
940
941 name = chunk_to_var_sym(expr, &sym);
942 if (!name)
943 return NULL;
944
945 ret = get_state(owner, name, sym);
946 free_string(name);
947 return ret;
948 }
949
950 static void save_link(struct expression *expr, char *link)
951 {
952 char *var;
953 struct symbol *sym;
954
955 expr = strip_expr(expr);
956 if (expr->type == EXPR_BINOP) {
957 char *chunk;
958
959 chunk = chunk_to_var(expr);
960 if (!chunk)
961 return;
962
963 save_link(expr->left, link);
964 save_link(expr->right, link);
965 save_link_var_sym(chunk, NULL, link);
966 return;
967 }
968
969 var = chunk_to_var_sym(expr, &sym);
970 if (!var)
971 return;
972
973 save_link_var_sym(var, sym, link);
974 free_string(var);
975 }
976
977 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right)
978 {
979 struct smatch_state *state;
980 struct compare_data *data;
981 int flip = 0;
982 char state_name[256];
983
984 if (strcmp(left, right) > 0) {
985 const char *tmp = right;
986
987 flip = 1;
988 right = left;
989 left = tmp;
990 }
991
992 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
993 state = get_state_stree(pre_stree, comparison_id, state_name, NULL);
994 if (!state || !state->data)
995 return 0;
996 data = state->data;
997 if (flip)
998 return flip_comparison(data->comparison);
999 return data->comparison;
1000
1001 }
1002
1003 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl)
1004 {
1005 struct var_sym *tmp;
1006
1007 FOR_EACH_PTR(left_vsl, tmp) {
1008 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym))
1009 return 1;
1010 } END_FOR_EACH_PTR(tmp);
1011
1012 return 0;
1013 }
1014
1015 /*
1016 * The idea here is that we take a comparison "a < b" and then we look at all
1017 * the things which "b" is compared against "b < c" and we say that that implies
1018 * a relationship "a < c".
1019 *
1020 * The names here about because the comparisons are organized like this
1021 * "a < b < c".
1022 *
1023 */
1024 static void update_tf_links(struct stree *pre_stree,
1025 struct expression *left_expr,
1026 const char *left_var, struct var_sym_list *left_vsl,
1027 int left_comparison, int left_false_comparison,
1028 const char *mid_var, struct var_sym_list *mid_vsl,
1029 struct string_list *links)
1030 {
1031 struct smatch_state *state;
1032 struct smatch_state *true_state, *false_state;
1033 struct compare_data *data;
1034 struct expression *right_expr;
1035 const char *right_var;
1036 struct var_sym_list *right_vsl;
1037 int orig_comparison;
1038 int right_comparison;
1039 int true_comparison;
1040 int false_comparison;
1041 char *tmp;
1042 char state_name[256];
1043 struct var_sym *vs;
1044
1045 FOR_EACH_PTR(links, tmp) {
1046 state = get_state_stree(pre_stree, comparison_id, tmp, NULL);
1047 if (!state || !state->data)
1048 continue;
1049 data = state->data;
1050 right_comparison = data->comparison;
1051 right_expr = data->right;
1052 right_var = data->right_var;
1053 right_vsl = data->right_vsl;
1054 if (strcmp(mid_var, right_var) == 0) {
1055 right_expr = data->left;
1056 right_var = data->left_var;
1057 right_vsl = data->left_vsl;
1058 right_comparison = flip_comparison(right_comparison);
1059 }
1060 if (have_common_var_sym(left_vsl, right_vsl))
1061 continue;
1062
1063 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var);
1064
1065 true_comparison = combine_comparisons(left_comparison, right_comparison);
1066 false_comparison = combine_comparisons(left_false_comparison, right_comparison);
1067
1068 true_comparison = comparison_intersection(orig_comparison, true_comparison);
1069 false_comparison = comparison_intersection(orig_comparison, false_comparison);
1070
1071 if (strcmp(left_var, right_var) > 0) {
1072 struct expression *tmp_expr = left_expr;
1073 const char *tmp_var = left_var;
1074 struct var_sym_list *tmp_vsl = left_vsl;
1075
1076 left_expr = right_expr;
1077 left_var = right_var;
1078 left_vsl = right_vsl;
1079 right_expr = tmp_expr;
1080 right_var = tmp_var;
1081 right_vsl = tmp_vsl;
1082 true_comparison = flip_comparison(true_comparison);
1083 false_comparison = flip_comparison(false_comparison);
1084 }
1085
1086 if (!true_comparison && !false_comparison)
1087 continue;
1088
1089 if (true_comparison)
1090 true_state = alloc_compare_state(
1091 left_expr, left_var, left_vsl,
1092 true_comparison,
1093 right_expr, right_var, right_vsl);
1094 else
1095 true_state = NULL;
1096 if (false_comparison)
1097 false_state = alloc_compare_state(
1098 left_expr, left_var, left_vsl,
1099 false_comparison,
1100 right_expr, right_var, right_vsl);
1101 else
1102 false_state = NULL;
1103
1104 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
1105 set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1106 FOR_EACH_PTR(left_vsl, vs) {
1107 save_link_var_sym(vs->var, vs->sym, state_name);
1108 } END_FOR_EACH_PTR(vs);
1109 FOR_EACH_PTR(right_vsl, vs) {
1110 save_link_var_sym(vs->var, vs->sym, state_name);
1111 } END_FOR_EACH_PTR(vs);
1112 if (!vsl_to_sym(left_vsl))
1113 save_link_var_sym(left_var, NULL, state_name);
1114 if (!vsl_to_sym(right_vsl))
1115 save_link_var_sym(right_var, NULL, state_name);
1116 } END_FOR_EACH_PTR(tmp);
1117 }
1118
1119 static void update_tf_data(struct stree *pre_stree,
1120 struct expression *left_expr,
1121 const char *left_name, struct var_sym_list *left_vsl,
1122 struct expression *right_expr,
1123 const char *right_name, struct var_sym_list *right_vsl,
1124 int true_comparison, int false_comparison)
1125 {
1126 struct smatch_state *state;
1127
1128 state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl));
1129 if (state)
1130 update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data);
1131
1132 state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl));
1133 if (state)
1134 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);
1135 }
1136
1137 static void iter_modify(struct sm_state *sm, struct expression *mod_expr)
1138 {
1139 if (sm->state != &start ||
1140 !mod_expr ||
1141 (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) ||
1142 mod_expr->op != SPECIAL_INCREMENT)
1143 set_state(inc_dec_id, sm->name, sm->sym, &undefined);
1144 else
1145 set_state(inc_dec_id, sm->name, sm->sym, &incremented);
1146 }
1147
1148 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state)
1149 {
1150 sval_t sval;
1151 char *iter_name, *cap_name;
1152 struct symbol *iter_sym, *cap_sym;
1153 struct compare_data *data;
1154
1155 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1156 return;
1157
1158 if (!__cur_stmt || !__prev_stmt)
1159 return;
1160 if (__cur_stmt->type != STMT_ITERATOR)
1161 return;
1162 if (__cur_stmt->iterator_pre_condition != expr)
1163 return;
1164
1165 /* literals are handled in smatch_extra.c */
1166 if (get_value(expr->right, &sval))
1167 return;
1168
1169 /* First time checking the condition */
1170 if (__prev_stmt == __cur_stmt->iterator_pre_statement) {
1171 if (!get_implied_value(expr->left, &sval) ||
1172 sval.value != 0)
1173 return;
1174
1175 iter_name = expr_to_var_sym(expr->left, &iter_sym);
1176 cap_name = expr_to_var_sym(expr->right, &cap_sym);
1177 if (!iter_name || !cap_name || !iter_sym || !cap_sym) {
1178 free_string(iter_name);
1179 free_string(cap_name);
1180 return;
1181 }
1182
1183 set_state(inc_dec_id, iter_name, iter_sym, &start);
1184 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym);
1185
1186 free_string(iter_name);
1187 free_string(cap_name);
1188 return;
1189 }
1190
1191 /* Second time checking the condtion */
1192 if (__prev_stmt != __cur_stmt->iterator_post_statement)
1193 return;
1194
1195 if (get_state_chunk(inc_dec_id, expr->left) != &incremented)
1196 return;
1197
1198 data = false_state->data;
1199 false_state = alloc_compare_state(
1200 data->left, data->left_var, data->left_vsl,
1201 SPECIAL_EQUAL,
1202 data->right, data->right_var, data->right_vsl);
1203
1204 // FIXME: This doesn't handle links correct so it doesn't set "param orig"
1205 set_true_false_states(comparison_id, state_name, NULL, NULL, false_state);
1206 }
1207
1208 static int is_plus_one(struct expression *expr)
1209 {
1210 sval_t sval;
1211
1212 if (expr->type != EXPR_BINOP || expr->op != '+')
1213 return 0;
1214 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1215 return 0;
1216 return 1;
1217 }
1218
1219 static int is_minus_one(struct expression *expr)
1220 {
1221 sval_t sval;
1222
1223 if (expr->type != EXPR_BINOP || expr->op != '-')
1224 return 0;
1225 if (!get_implied_value(expr->right, &sval) || sval.value != 1)
1226 return 0;
1227 return 1;
1228 }
1229
1230 static void remove_plus_minus_zero(struct expression **expr_p)
1231 {
1232 struct expression *expr = *expr_p;
1233 sval_t sval;
1234
1235 if (!expr || expr->type != EXPR_BINOP)
1236 return;
1237 if (expr->op == '+') {
1238 if (get_implied_value(expr->left, &sval) && sval.value == 0)
1239 *expr_p = expr->right;
1240 else if (get_implied_value(expr->right, &sval) && sval.value == 0)
1241 *expr_p = expr->left;
1242 else
1243 return;
1244 return remove_plus_minus_zero(expr_p);
1245 }
1246 if (expr->op == '-') {
1247 if (get_implied_value(expr->right, &sval) && sval.value == 0) {
1248 *expr_p = expr->left;
1249 return remove_plus_minus_zero(expr_p);
1250 }
1251 }
1252 }
1253
1254 static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p)
1255 {
1256 struct expression *left = *left_p;
1257 struct expression *right = *right_p;
1258
1259 /*
1260 * These two are basically equivalent: "foo + 1 != bar" and
1261 * "foo != bar - 1". There are issues with signedness and integer
1262 * overflows. There are also issues with type as well. But let's
1263 * pretend we can ignore all that stuff for now.
1264 *
1265 */
1266
1267 if (!is_plus_one(left))
1268 return;
1269
1270 *left_p = left->left;
1271 *right_p = binop_expression(right, '-', left->right);
1272 }
1273
1274 static void move_plus_to_minus(struct expression **left_p, struct expression **right_p)
1275 {
1276 if (is_plus_one(*left_p) && is_plus_one(*right_p))
1277 return;
1278
1279 move_plus_to_minus_helper(left_p, right_p);
1280 move_plus_to_minus_helper(right_p, left_p);
1281 }
1282
1283 static void simplify_binops(struct expression **left_p, struct expression **right_p)
1284 {
1285 remove_plus_minus_zero(left_p);
1286 remove_plus_minus_zero(right_p);
1287
1288 move_plus_to_minus(left_p, right_p);
1289 }
1290
1291 static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state)
1292 {
1293 char *left = NULL;
1294 char *right = NULL;
1295 struct symbol *left_sym, *right_sym;
1296 struct var_sym_list *left_vsl = NULL;
1297 struct var_sym_list *right_vsl = NULL;
1298 int false_op;
1299 int orig_comparison;
1300 struct smatch_state *true_state, *false_state;
1301 static char state_name[256];
1302 struct stree *pre_stree;
1303 sval_t sval;
1304
1305 if (!left_expr || !right_expr)
1306 return;
1307
1308 left_expr = strip_parens(left_expr);
1309 right_expr = strip_parens(right_expr);
1310
1311 while (left_expr->type == EXPR_ASSIGNMENT)
1312 left_expr = strip_parens(left_expr->left);
1313 while (right_expr->type == EXPR_ASSIGNMENT)
1314 right_expr = strip_parens(right_expr->left);
1315
1316 false_op = negate_comparison(op);
1317
1318 simplify_binops(&left_expr, &right_expr);
1319
1320 if (op == SPECIAL_UNSIGNED_LT &&
1321 get_implied_value(left_expr, &sval) &&
1322 sval.value == 0)
1323 false_op = SPECIAL_EQUAL;
1324
1325 if (op == SPECIAL_UNSIGNED_GT &&
1326 get_implied_value(right_expr, &sval) &&
1327 sval.value == 0)
1328 false_op = SPECIAL_EQUAL;
1329
1330 left = chunk_to_var_sym(left_expr, &left_sym);
1331 if (!left)
1332 goto free;
1333 if (left_sym)
1334 add_var_sym(&left_vsl, left, left_sym);
1335 else
1336 left_vsl = expr_to_vsl(left_expr);
1337 right = chunk_to_var_sym(right_expr, &right_sym);
1338 if (!right)
1339 goto free;
1340 if (right_sym)
1341 add_var_sym(&right_vsl, right, right_sym);
1342 else
1343 right_vsl = expr_to_vsl(right_expr);
1344
1345 if (strcmp(left, right) > 0) {
1346 char *tmp_name = left;
1347 struct var_sym_list *tmp_vsl = left_vsl;
1348 struct expression *tmp_expr = left_expr;
1349
1350 left = right;
1351 left_vsl = right_vsl;
1352 left_expr = right_expr;
1353 right = tmp_name;
1354 right_vsl = tmp_vsl;
1355 right_expr = tmp_expr;
1356 op = flip_comparison(op);
1357 false_op = flip_comparison(false_op);
1358 }
1359
1360 orig_comparison = get_comparison(left_expr, right_expr);
1361 op = comparison_intersection(orig_comparison, op);
1362 false_op = comparison_intersection(orig_comparison, false_op);
1363
1364 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
1365 true_state = alloc_compare_state(
1366 left_expr, left, left_vsl,
1367 op,
1368 right_expr, right, right_vsl);
1369 false_state = alloc_compare_state(
1370 left_expr, left, left_vsl,
1371 false_op,
1372 right_expr, right, right_vsl);
1373
1374 pre_stree = clone_stree(__get_cur_stree());
1375 update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op);
1376 free_stree(&pre_stree);
1377
1378 set_true_false_states(comparison_id, state_name, NULL, true_state, false_state);
1379 __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state);
1380 save_link(left_expr, state_name);
1381 save_link(right_expr, state_name);
1382
1383 if (_false_state)
1384 *_false_state = false_state;
1385 if (_state_name)
1386 *_state_name = state_name;
1387 free:
1388 free_string(left);
1389 free_string(right);
1390 }
1391
1392 void __comparison_match_condition(struct expression *expr)
1393 {
1394 struct expression *left, *right, *new_left, *new_right, *tmp;
1395 struct smatch_state *false_state = NULL;
1396 char *state_name = NULL;
1397 int redo, count;
1398
1399 if (expr->type != EXPR_COMPARE)
1400 return;
1401
1402 handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state);
1403 if (false_state && state_name)
1404 handle_for_loops(expr, state_name, false_state);
1405
1406 left = strip_parens(expr->left);
1407 right = strip_parens(expr->right);
1408
1409 if (left->type == EXPR_BINOP && left->op == '+') {
1410 new_left = left->left;
1411 new_right = binop_expression(right, '-', left->right);
1412 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1413
1414 new_left = left->right;
1415 new_right = binop_expression(right, '-', left->left);
1416 handle_comparison(new_left, expr->op, new_right, NULL, NULL);
1417 }
1418
1419 redo = 0;
1420 left = strip_parens(expr->left);
1421 right = strip_parens(expr->right);
1422 if (get_last_expr_from_expression_stmt(expr->left)) {
1423 left = get_last_expr_from_expression_stmt(expr->left);
1424 redo = 1;
1425 }
1426 if (get_last_expr_from_expression_stmt(expr->right)) {
1427 right = get_last_expr_from_expression_stmt(expr->right);
1428 redo = 1;
1429 }
1430
1431 if (!redo)
1432 return;
1433
1434 count = 0;
1435 while ((tmp = get_assigned_expr(left))) {
1436 if (count++ > 3)
1437 break;
1438 left = strip_expr(tmp);
1439 }
1440 count = 0;
1441 while ((tmp = get_assigned_expr(right))) {
1442 if (count++ > 3)
1443 break;
1444 right = strip_expr(tmp);
1445 }
1446
1447 handle_comparison(left, expr->op, right, NULL, NULL);
1448 }
1449
1450 static void add_comparison_var_sym(
1451 struct expression *left_expr,
1452 const char *left_name, struct var_sym_list *left_vsl,
1453 int comparison,
1454 struct expression *right_expr,
1455 const char *right_name, struct var_sym_list *right_vsl)
1456 {
1457 struct smatch_state *state;
1458 struct var_sym *vs;
1459 char state_name[256];
1460
1461 if (strcmp(left_name, right_name) > 0) {
1462 struct expression *tmp_expr = left_expr;
1463 const char *tmp_name = left_name;
1464 struct var_sym_list *tmp_vsl = left_vsl;
1465
1466 left_expr = right_expr;
1467 left_name = right_name;
1468 left_vsl = right_vsl;
1469 right_expr = tmp_expr;
1470 right_name = tmp_name;
1471 right_vsl = tmp_vsl;
1472 comparison = flip_comparison(comparison);
1473 }
1474 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1475 state = alloc_compare_state(
1476 left_expr, left_name, left_vsl,
1477 comparison,
1478 right_expr, right_name, right_vsl);
1479
1480 set_state(comparison_id, state_name, NULL, state);
1481
1482 FOR_EACH_PTR(left_vsl, vs) {
1483 save_link_var_sym(vs->var, vs->sym, state_name);
1484 } END_FOR_EACH_PTR(vs);
1485 FOR_EACH_PTR(right_vsl, vs) {
1486 save_link_var_sym(vs->var, vs->sym, state_name);
1487 } END_FOR_EACH_PTR(vs);
1488 }
1489
1490 static void add_comparison(struct expression *left, int comparison, struct expression *right)
1491 {
1492 char *left_name = NULL;
1493 char *right_name = NULL;
1494 struct symbol *left_sym, *right_sym;
1495 struct var_sym_list *left_vsl, *right_vsl;
1496 struct smatch_state *state;
1497 char state_name[256];
1498
1499 left_name = chunk_to_var_sym(left, &left_sym);
1500 if (!left_name)
1501 goto free;
1502 left_vsl = expr_to_vsl(left);
1503 right_name = chunk_to_var_sym(right, &right_sym);
1504 if (!right_name)
1505 goto free;
1506 right_vsl = expr_to_vsl(right);
1507
1508 if (strcmp(left_name, right_name) > 0) {
1509 struct expression *tmp_expr = left;
1510 struct symbol *tmp_sym = left_sym;
1511 char *tmp_name = left_name;
1512 struct var_sym_list *tmp_vsl = left_vsl;
1513
1514 left = right;
1515 left_name = right_name;
1516 left_sym = right_sym;
1517 left_vsl = right_vsl;
1518 right = tmp_expr;
1519 right_name = tmp_name;
1520 right_sym = tmp_sym;
1521 right_vsl = tmp_vsl;
1522 comparison = flip_comparison(comparison);
1523 }
1524 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
1525 state = alloc_compare_state(
1526 left, left_name, left_vsl,
1527 comparison,
1528 right, right_name, right_vsl);
1529
1530 set_state(comparison_id, state_name, NULL, state);
1531 save_link(left, state_name);
1532 save_link(right, state_name);
1533
1534 free:
1535 free_string(left_name);
1536 free_string(right_name);
1537 }
1538
1539 static void match_assign_add(struct expression *expr)
1540 {
1541 struct expression *right;
1542 struct expression *r_left, *r_right;
1543 sval_t left_tmp, right_tmp;
1544
1545 right = strip_expr(expr->right);
1546 r_left = strip_expr(right->left);
1547 r_right = strip_expr(right->right);
1548
1549 get_absolute_min(r_left, &left_tmp);
1550 get_absolute_min(r_right, &right_tmp);
1551
1552 if (left_tmp.value > 0)
1553 add_comparison(expr->left, '>', r_right);
1554 else if (left_tmp.value == 0)
1555 add_comparison(expr->left, SPECIAL_GTE, r_right);
1556
1557 if (right_tmp.value > 0)
1558 add_comparison(expr->left, '>', r_left);
1559 else if (right_tmp.value == 0)
1560 add_comparison(expr->left, SPECIAL_GTE, r_left);
1561 }
1562
1563 static void match_assign_sub(struct expression *expr)
1564 {
1565 struct expression *right;
1566 struct expression *r_left, *r_right;
1567 int comparison;
1568 sval_t min;
1569
1570 right = strip_expr(expr->right);
1571 r_left = strip_expr(right->left);
1572 r_right = strip_expr(right->right);
1573
1574 if (get_absolute_min(r_right, &min) && sval_is_negative(min))
1575 return;
1576
1577 comparison = get_comparison(r_left, r_right);
1578
1579 switch (comparison) {
1580 case '>':
1581 case SPECIAL_GTE:
1582 if (implied_not_equal(r_right, 0))
1583 add_comparison(expr->left, '>', r_left);
1584 else
1585 add_comparison(expr->left, SPECIAL_GTE, r_left);
1586 return;
1587 }
1588 }
1589
1590 static void match_assign_divide(struct expression *expr)
1591 {
1592 struct expression *right;
1593 struct expression *r_left, *r_right;
1594 sval_t min;
1595
1596 right = strip_expr(expr->right);
1597 r_left = strip_expr(right->left);
1598 r_right = strip_expr(right->right);
1599 if (!get_implied_min(r_right, &min) || min.value <= 1)
1600 return;
1601
1602 add_comparison(expr->left, '<', r_left);
1603 }
1604
1605 static void match_binop_assign(struct expression *expr)
1606 {
1607 struct expression *right;
1608
1609 right = strip_expr(expr->right);
1610 if (right->op == '+')
1611 match_assign_add(expr);
1612 if (right->op == '-')
1613 match_assign_sub(expr);
1614 if (right->op == '/')
1615 match_assign_divide(expr);
1616 }
1617
1618 static void copy_comparisons(struct expression *left, struct expression *right)
1619 {
1620 struct string_list *links;
1621 struct smatch_state *state;
1622 struct compare_data *data;
1623 struct symbol *left_sym, *right_sym;
1624 char *left_var = NULL;
1625 char *right_var = NULL;
1626 struct var_sym_list *left_vsl;
1627 struct expression *expr;
1628 const char *var;
1629 struct var_sym_list *vsl;
1630 int comparison;
1631 char *tmp;
1632
1633 left_var = chunk_to_var_sym(left, &left_sym);
1634 if (!left_var)
1635 goto done;
1636 left_vsl = expr_to_vsl(left);
1637 right_var = chunk_to_var_sym(right, &right_sym);
1638 if (!right_var)
1639 goto done;
1640
1641 state = get_state(link_id, right_var, right_sym);
1642 if (!state)
1643 return;
1644 links = state->data;
1645
1646 FOR_EACH_PTR(links, tmp) {
1647 state = get_state(comparison_id, tmp, NULL);
1648 if (!state || !state->data)
1649 continue;
1650 data = state->data;
1651 comparison = data->comparison;
1652 expr = data->right;
1653 var = data->right_var;
1654 vsl = data->right_vsl;
1655 if (strcmp(var, right_var) == 0) {
1656 expr = data->left;
1657 var = data->left_var;
1658 vsl = data->left_vsl;
1659 comparison = flip_comparison(comparison);
1660 }
1661 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */
1662 if (strcmp(left_var, var) == 0)
1663 continue;
1664 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1665 } END_FOR_EACH_PTR(tmp);
1666
1667 done:
1668 free_string(right_var);
1669 }
1670
1671 static bool is_empty_fake_assign(struct expression *expr)
1672 {
1673 if (!__in_fake_var_assign)
1674 return false;
1675 if (get_state_chunk(link_id, expr->right))
1676 return false;
1677 return true;
1678 }
1679
1680 static void match_assign(struct expression *expr)
1681 {
1682 struct expression *right;
1683
1684 if (expr->op != '=')
1685 return;
1686 if (__in_fake_assign || outside_of_function())
1687 return;
1688
1689 if (is_struct(expr->left))
1690 return;
1691
1692 if (is_self_assign(expr))
1693 return;
1694
1695 if (is_empty_fake_assign(expr))
1696 return;
1697
1698 copy_comparisons(expr->left, expr->right);
1699 add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
1700
1701 right = strip_expr(expr->right);
1702 if (right->type == EXPR_BINOP)
1703 match_binop_assign(expr);
1704 }
1705
1706 int get_comparison_strings(const char *one, const char *two)
1707 {
1708 char buf[256];
1709 struct smatch_state *state;
1710 int invert = 0;
1711 int ret = 0;
1712
1713 if (!one || !two)
1714 return UNKNOWN_COMPARISON;
1715
1716 if (strcmp(one, two) == 0)
1717 return SPECIAL_EQUAL;
1718
1719 if (strcmp(one, two) > 0) {
1720 const char *tmp = one;
1721
1722 one = two;
1723 two = tmp;
1724 invert = 1;
1725 }
1726
1727 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1728 state = get_state(comparison_id, buf, NULL);
1729 if (state)
1730 ret = state_to_comparison(state);
1731
1732 if (invert)
1733 ret = flip_comparison(ret);
1734
1735 return ret;
1736 }
1737
1738 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
1739 {
1740 char *one = NULL;
1741 char *two = NULL;
1742 int ret = UNKNOWN_COMPARISON;
1743 int extra = UNKNOWN_COMPARISON;
1744
1745 if (a == UNKNOWN_COMPARISON ||
1746 b == UNKNOWN_COMPARISON)
1747 return UNKNOWN_COMPARISON;
1748
1749 a = strip_parens(a);
1750 b = strip_parens(b);
1751
1752 move_plus_to_minus(&a, &b);
1753
1754 simplify_binops(&a, &b);
1755
1756 one = chunk_to_var(a);
1757 if (!one)
1758 goto free;
1759 two = chunk_to_var(b);
1760 if (!two)
1761 goto free;
1762
1763 ret = get_comparison_strings(one, two);
1764 if (ret)
1765 goto free;
1766
1767 if (is_plus_one(a) || is_minus_one(a)) {
1768 free_string(one);
1769 one = chunk_to_var(a->left);
1770 ret = get_comparison_strings(one, two);
1771 } else if (is_plus_one(b) || is_minus_one(b)) {
1772 free_string(two);
1773 two = chunk_to_var(b->left);
1774 ret = get_comparison_strings(one, two);
1775 }
1776
1777 if (ret == UNKNOWN_COMPARISON)
1778 goto free;
1779
1780 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1781 ret = SPECIAL_LTE;
1782 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1783 ret = SPECIAL_GTE;
1784 else
1785 ret = UNKNOWN_COMPARISON;
1786
1787 free:
1788 free_string(one);
1789 free_string(two);
1790
1791 if (use_extra)
1792 extra = comparison_from_extra(a, b);
1793 return comparison_intersection(ret, extra);
1794 }
1795
1796 int get_comparison(struct expression *a, struct expression *b)
1797 {
1798 return get_comparison_helper(a, b, true);
1799 }
1800
1801 int get_comparison_no_extra(struct expression *a, struct expression *b)
1802 {
1803 return get_comparison_helper(a, b, false);
1804 }
1805
1806 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1807 {
1808 char *one = NULL;
1809 char *two = NULL;
1810 int ret = 0;
1811 char buf[256];
1812 struct sm_state *sm;
1813 int saved;
1814
1815 one = chunk_to_var(a);
1816 if (!one)
1817 goto free;
1818 two = chunk_to_var(b);
1819 if (!two)
1820 goto free;
1821
1822
1823 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1824 ret = 1;
1825 goto free;
1826 }
1827
1828 if (strcmp(one, two) > 0) {
1829 char *tmp = one;
1830
1831 one = two;
1832 two = tmp;
1833 comparison = flip_comparison(comparison);
1834 }
1835
1836 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1837 sm = get_sm_state(comparison_id, buf, NULL);
1838 if (!sm)
1839 goto free;
1840
1841 FOR_EACH_PTR(sm->possible, sm) {
1842 if (!sm->state->data)
1843 continue;
1844 saved = ((struct compare_data *)sm->state->data)->comparison;
1845 if (saved == comparison)
1846 ret = 1;
1847 if (comparison == SPECIAL_EQUAL &&
1848 (saved == SPECIAL_LTE ||
1849 saved == SPECIAL_GTE ||
1850 saved == SPECIAL_UNSIGNED_LTE ||
1851 saved == SPECIAL_UNSIGNED_GTE))
1852 ret = 1;
1853 if (ret == 1)
1854 goto free;
1855 } END_FOR_EACH_PTR(sm);
1856
1857 return ret;
1858 free:
1859 free_string(one);
1860 free_string(two);
1861 return ret;
1862 }
1863
1864 struct state_list *get_all_comparisons(struct expression *expr)
1865 {
1866 struct smatch_state *state;
1867 struct string_list *links;
1868 struct state_list *ret = NULL;
1869 struct sm_state *sm;
1870 char *tmp;
1871
1872 state = get_state_chunk(link_id, expr);
1873 if (!state)
1874 return NULL;
1875 links = state->data;
1876
1877 FOR_EACH_PTR(links, tmp) {
1878 sm = get_sm_state(comparison_id, tmp, NULL);
1879 if (!sm)
1880 continue;
1881 // FIXME have to compare name with vsl
1882 add_ptr_list(&ret, sm);
1883 } END_FOR_EACH_PTR(tmp);
1884
1885 return ret;
1886 }
1887
1888 struct state_list *get_all_possible_equal_comparisons(struct expression *expr)
1889 {
1890 struct smatch_state *state;
1891 struct string_list *links;
1892 struct state_list *ret = NULL;
1893 struct sm_state *sm;
1894 char *tmp;
1895
1896 state = get_state_chunk(link_id, expr);
1897 if (!state)
1898 return NULL;
1899 links = state->data;
1900
1901 FOR_EACH_PTR(links, tmp) {
1902 sm = get_sm_state(comparison_id, tmp, NULL);
1903 if (!sm)
1904 continue;
1905 if (!strchr(sm->state->name, '='))
1906 continue;
1907 if (strcmp(sm->state->name, "!=") == 0)
1908 continue;
1909 add_ptr_list(&ret, sm);
1910 } END_FOR_EACH_PTR(tmp);
1911
1912 return ret;
1913 }
1914
1915 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr)
1916 {
1917 struct smatch_state *state;
1918 struct string_list *links;
1919 struct state_list *ret = NULL;
1920 struct sm_state *sm;
1921 struct sm_state *possible;
1922 char *link;
1923
1924 return NULL;
1925
1926 state = get_state_chunk(link_id, expr);
1927 if (!state)
1928 return NULL;
1929 links = state->data;
1930
1931 FOR_EACH_PTR(links, link) {
1932 sm = get_sm_state(comparison_id, link, NULL);
1933 if (!sm)
1934 continue;
1935 FOR_EACH_PTR(sm->possible, possible) {
1936 if (strcmp(possible->state->name, "!=") != 0)
1937 continue;
1938 add_ptr_list(&ret, sm);
1939 break;
1940 } END_FOR_EACH_PTR(link);
1941 } END_FOR_EACH_PTR(link);
1942
1943 return ret;
1944 }
1945
1946 static void update_links_from_call(struct expression *left,
1947 int left_compare,
1948 struct expression *right)
1949 {
1950 struct string_list *links;
1951 struct smatch_state *state;
1952 struct compare_data *data;
1953 struct symbol *left_sym, *right_sym;
1954 char *left_var = NULL;
1955 char *right_var = NULL;
1956 struct var_sym_list *left_vsl;
1957 struct expression *expr;
1958 const char *var;
1959 struct var_sym_list *vsl;
1960 int comparison;
1961 char *tmp;
1962
1963 left_var = chunk_to_var_sym(left, &left_sym);
1964 if (!left_var)
1965 goto done;
1966 left_vsl = expr_to_vsl(left);
1967 right_var = chunk_to_var_sym(right, &right_sym);
1968 if (!right_var)
1969 goto done;
1970
1971 state = get_state(link_id, right_var, right_sym);
1972 if (!state)
1973 return;
1974 links = state->data;
1975
1976 FOR_EACH_PTR(links, tmp) {
1977 state = get_state(comparison_id, tmp, NULL);
1978 if (!state || !state->data)
1979 continue;
1980 data = state->data;
1981 comparison = data->comparison;
1982 expr = data->right;
1983 var = data->right_var;
1984 vsl = data->right_vsl;
1985 if (strcmp(var, right_var) == 0) {
1986 expr = data->left;
1987 var = data->left_var;
1988 vsl = data->left_vsl;
1989 comparison = flip_comparison(comparison);
1990 }
1991 comparison = combine_comparisons(left_compare, comparison);
1992 if (!comparison)
1993 continue;
1994 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl);
1995 } END_FOR_EACH_PTR(tmp);
1996
1997 done:
1998 free_string(right_var);
1999 }
2000
2001 void __add_return_comparison(struct expression *call, const char *range)
2002 {
2003 struct expression *arg;
2004 int comparison;
2005 char buf[16];
2006
2007 if (!str_to_comparison_arg(range, call, &comparison, &arg))
2008 return;
2009 snprintf(buf, sizeof(buf), "%s", show_comparison(comparison));
2010 update_links_from_call(call, comparison, arg);
2011 add_comparison(call, comparison, arg);
2012 }
2013
2014 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
2015 {
2016 copy_comparisons(expr, call);
2017 }
2018
2019 static char *get_mask_comparison(struct expression *expr, int ignore)
2020 {
2021 struct expression *tmp, *right;
2022 int count, param;
2023 char buf[256];
2024
2025 /* The return value for "return foo & param;" is <= param */
2026
2027 count = 0;
2028 while ((tmp = get_assigned_expr(expr))) {
2029 expr = strip_expr(tmp);
2030 if (count++ > 4)
2031 break;
2032 }
2033
2034 if (expr->type != EXPR_BINOP || expr->op != '&')
2035 return NULL;
2036
2037 right = strip_expr(expr->right);
2038 param = get_param_num(right);
2039 if (param < 0 || param == ignore)
2040 return NULL;
2041
2042 snprintf(buf, sizeof(buf), "[<=$%d]", param);
2043 return alloc_sname(buf);
2044 }
2045
2046 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore)
2047 {
2048 struct symbol *param;
2049 char *var = NULL;
2050 char buf[256];
2051 char *ret_str = NULL;
2052 int compare;
2053 int i;
2054
2055 if (!expr)
2056 return NULL;
2057
2058 var = chunk_to_var(expr);
2059 if (!var)
2060 goto try_mask;
2061
2062 i = -1;
2063 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2064 i++;
2065 if (i == ignore)
2066 continue;
2067 if (!param->ident)
2068 continue;
2069 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2070 compare = get_comparison_strings(var, buf);
2071 if (compare == UNKNOWN_COMPARISON ||
2072 compare == IMPOSSIBLE_COMPARISON)
2073 continue;
2074 if (show_comparison(compare)[0] != starts_with)
2075 continue;
2076 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2077 ret_str = alloc_sname(buf);
2078 break;
2079 } END_FOR_EACH_PTR(param);
2080
2081 free_string(var);
2082 if (!ret_str)
2083 goto try_mask;
2084
2085 return ret_str;
2086
2087 try_mask:
2088 if (starts_with == '<')
2089 ret_str = get_mask_comparison(expr, ignore);
2090 return ret_str;
2091 }
2092
2093 char *name_sym_to_param_comparison(const char *name, struct symbol *sym)
2094 {
2095 struct symbol *param;
2096 char buf[256];
2097 int compare;
2098 int i;
2099
2100 i = -1;
2101 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2102 i++;
2103 if (!param->ident)
2104 continue;
2105 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2106 compare = get_comparison_strings(name, buf);
2107 if (compare == UNKNOWN_COMPARISON ||
2108 compare == IMPOSSIBLE_COMPARISON)
2109 continue;
2110 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2111 return alloc_sname(buf);
2112 } END_FOR_EACH_PTR(param);
2113
2114 return NULL;
2115 }
2116
2117 char *expr_equal_to_param(struct expression *expr, int ignore)
2118 {
2119 return range_comparison_to_param_helper(expr, '=', ignore);
2120 }
2121
2122 char *expr_lte_to_param(struct expression *expr, int ignore)
2123 {
2124 return range_comparison_to_param_helper(expr, '<', ignore);
2125 }
2126
2127 char *expr_param_comparison(struct expression *expr, int ignore)
2128 {
2129 struct symbol *param;
2130 char *var = NULL;
2131 char buf[256];
2132 char *ret_str = NULL;
2133 int compare;
2134 int i;
2135
2136 var = chunk_to_var(expr);
2137 if (!var)
2138 goto free;
2139
2140 i = -1;
2141 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
2142 i++;
2143 if (i == ignore)
2144 continue;
2145 if (!param->ident)
2146 continue;
2147 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
2148 compare = get_comparison_strings(var, buf);
2149 if (!compare)
2150 continue;
2151 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i);
2152 ret_str = alloc_sname(buf);
2153 break;
2154 } END_FOR_EACH_PTR(param);
2155
2156 free:
2157 free_string(var);
2158 return ret_str;
2159 }
2160
2161 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym)
2162 {
2163 struct expression *arg;
2164 char *name;
2165 struct symbol *sym;
2166 static char buf[256];
2167 int len;
2168 int i;
2169
2170 i = -1;
2171 FOR_EACH_PTR(call->args, arg) {
2172 i++;
2173
2174 name = expr_to_var_sym(arg, &sym);
2175 if (!name || !sym)
2176 continue;
2177 if (sym != param_sym)
2178 continue;
2179
2180 len = strlen(name);
2181 if (strncmp(name, param_name, len) != 0)
2182 continue;
2183 if (param_name[len] == '\0') {
2184 snprintf(buf, sizeof(buf), "$%d", i);
2185 return buf;
2186 }
2187 if (param_name[len] != '-')
2188 continue;
2189 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len);
2190 return buf;
2191 } END_FOR_EACH_PTR(arg);
2192
2193 return NULL;
2194 }
2195
2196 static void match_call_info(struct expression *expr)
2197 {
2198 struct expression *arg;
2199 struct smatch_state *state;
2200 struct sm_state *sm;
2201 struct compare_data *data;
2202 int comparison;
2203 struct string_list *links;
2204 char *arg_name;
2205 const char *right_name;
2206 char *link;
2207 char info_buf[256];
2208 int i;
2209
2210 i = -1;
2211 FOR_EACH_PTR(expr->args, arg) {
2212 i++;
2213
2214 state = get_state_chunk(link_id, arg);
2215 if (!state)
2216 continue;
2217
2218 links = state->data;
2219 FOR_EACH_PTR(links, link) {
2220 struct var_sym_list *right_vsl;
2221 struct var_sym *right_vs;
2222
2223
2224 if (strstr(link, " orig"))
2225 continue;
2226 sm = get_sm_state(comparison_id, link, NULL);
2227 if (!sm)
2228 continue;
2229 data = sm->state->data;
2230 if (!data ||
2231 data->comparison == UNKNOWN_COMPARISON ||
2232 data->comparison == IMPOSSIBLE_COMPARISON)
2233 continue;
2234 arg_name = expr_to_var(arg);
2235 if (!arg_name)
2236 continue;
2237
2238 right_vsl = NULL;
2239 if (strcmp(data->left_var, arg_name) == 0) {
2240 comparison = data->comparison;
2241 right_name = data->right_var;
2242 right_vsl = data->right_vsl;
2243 } else if (strcmp(data->right_var, arg_name) == 0) {
2244 comparison = flip_comparison(data->comparison);
2245 right_name = data->left_var;
2246 right_vsl = data->left_vsl;
2247 }
2248 if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1)
2249 goto free;
2250
2251 right_vs = first_ptr_list((struct ptr_list *)right_vsl);
2252 if (strcmp(right_vs->var, right_name) != 0)
2253 goto free;
2254 right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym);
2255 if (!right_name)
2256 goto free;
2257 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(comparison), right_name);
2258 sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf);
2259
2260 free:
2261 free_string(arg_name);
2262 } END_FOR_EACH_PTR(link);
2263 } END_FOR_EACH_PTR(arg);
2264 }
2265
2266 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm)
2267 {
2268 struct sm_state *compare_sm;
2269 struct string_list *links;
2270 char *link;
2271 struct compare_data *data;
2272 struct var_sym *left, *right;
2273 static char info_buf[256];
2274 const char *right_name;
2275
2276 if (strstr(printed_name, " orig"))
2277 return;
2278
2279 links = link_sm->state->data;
2280 FOR_EACH_PTR(links, link) {
2281 compare_sm = get_sm_state(comparison_id, link, NULL);
2282 if (!compare_sm)
2283 continue;
2284 data = compare_sm->state->data;
2285 if (!data || !data->comparison)
2286 continue;
2287
2288 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2289 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2290 continue;
2291 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2292 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2293 if (left->sym == right->sym &&
2294 strcmp(left->var, right->var) == 0)
2295 continue;
2296 /*
2297 * Both parameters link to this comparison so only
2298 * record the first one.
2299 */
2300 if (left->sym != link_sm->sym ||
2301 strcmp(left->var, link_sm->name) != 0)
2302 continue;
2303
2304 right_name = get_printed_param_name(call, right->var, right->sym);
2305 if (!right_name)
2306 continue;
2307 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_name);
2308 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf);
2309 } END_FOR_EACH_PTR(link);
2310 }
2311
2312 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr)
2313 {
2314 char *name;
2315 const char *tmp_name;
2316 struct symbol *sym;
2317 int param;
2318 char info_buf[256];
2319 bool is_addr = false;
2320
2321 /*
2322 * TODO: This only prints == comparisons. That's probably the most
2323 * useful comparison because == max has lots of implications. But it
2324 * would be good to capture the rest as well.
2325 *
2326 * This information is already in the DB but it's in the parameter math
2327 * bits and it's awkward to use it. This is is the simpler, possibly
2328 * cleaner way, but not necessarily the best, I don't know.
2329 */
2330
2331 if (!expr)
2332 return;
2333 name = expr_to_var_sym(expr, &sym);
2334 if (!name || !sym)
2335 goto free;
2336
2337 param = get_param_num_from_sym(sym);
2338 if (param < 0)
2339 goto free;
2340 if (param_was_set_var_sym(name, sym))
2341 goto free;
2342
2343 tmp_name = get_param_name_var_sym(name, sym);
2344 if (!tmp_name)
2345 goto free;
2346
2347 if (tmp_name[0] == '&') {
2348 tmp_name += 2;
2349 is_addr = true;
2350 } else {
2351 tmp_name += 1;
2352 }
2353
2354 snprintf(info_buf, sizeof(info_buf), "== %s$%d%s", is_addr ? "&" : "", param, tmp_name);
2355 sql_insert_return_states(return_id, return_ranges,
2356 PARAM_COMPARE, -1, "$", info_buf);
2357 free:
2358 free_string(name);
2359 }
2360
2361 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr)
2362 {
2363 struct sm_state *tmp;
2364 struct string_list *links;
2365 char *link;
2366 struct sm_state *sm;
2367 struct compare_data *data;
2368 struct var_sym *left, *right;
2369 int left_param, right_param;
2370 char left_buf[256];
2371 char right_buf[256];
2372 char info_buf[258];
2373 const char *tmp_name;
2374
2375 print_return_value_comparison(return_id, return_ranges, expr);
2376
2377 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) {
2378 if (get_param_num_from_sym(tmp->sym) < 0)
2379 continue;
2380 links = tmp->state->data;
2381 FOR_EACH_PTR(links, link) {
2382 sm = get_sm_state(comparison_id, link, NULL);
2383 if (!sm)
2384 continue;
2385 data = sm->state->data;
2386 if (!data ||
2387 data->comparison == UNKNOWN_COMPARISON ||
2388 data->comparison == IMPOSSIBLE_COMPARISON)
2389 continue;
2390 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 ||
2391 ptr_list_size((struct ptr_list *)data->right_vsl) != 1)
2392 continue;
2393 left = first_ptr_list((struct ptr_list *)data->left_vsl);
2394 right = first_ptr_list((struct ptr_list *)data->right_vsl);
2395 if (left->sym == right->sym &&
2396 strcmp(left->var, right->var) == 0)
2397 continue;
2398 /*
2399 * Both parameters link to this comparison so only
2400 * record the first one.
2401 */
2402 if (left->sym != tmp->sym ||
2403 strcmp(left->var, tmp->name) != 0)
2404 continue;
2405
2406 if (strstr(right->var, " orig"))
2407 continue;
2408
2409 left_param = get_param_num_from_sym(left->sym);
2410 right_param = get_param_num_from_sym(right->sym);
2411 if (left_param < 0 || right_param < 0)
2412 continue;
2413
2414 tmp_name = get_param_name_var_sym(left->var, left->sym);
2415 if (!tmp_name)
2416 continue;
2417 snprintf(left_buf, sizeof(left_buf), "%s", tmp_name);
2418
2419 tmp_name = get_param_name_var_sym(right->var, right->sym);
2420 if (!tmp_name || tmp_name[0] != '$')
2421 continue;
2422 snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1);
2423
2424 /*
2425 * FIXME: this should reject $ type variables (as
2426 * opposed to $->foo type). Those should come from
2427 * smatch_param_compare_limit.c.
2428 */
2429
2430 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_buf);
2431 sql_insert_return_states(return_id, return_ranges,
2432 PARAM_COMPARE, left_param, left_buf, info_buf);
2433 } END_FOR_EACH_PTR(link);
2434
2435 } END_FOR_EACH_SM(tmp);
2436 }
2437
2438 static int parse_comparison(char **value, int *op)
2439 {
2440
2441 *op = **value;
2442
2443 switch (*op) {
2444 case '<':
2445 (*value)++;
2446 if (**value == '=') {
2447 (*value)++;
2448 *op = SPECIAL_LTE;
2449 }
2450 break;
2451 case '=':
2452 (*value)++;
2453 (*value)++;
2454 *op = SPECIAL_EQUAL;
2455 break;
2456 case '!':
2457 (*value)++;
2458 (*value)++;
2459 *op = SPECIAL_NOTEQUAL;
2460 break;
2461 case '>':
2462 (*value)++;
2463 if (**value == '=') {
2464 (*value)++;
2465 *op = SPECIAL_GTE;
2466 }
2467 break;
2468 default:
2469 return 0;
2470 }
2471
2472 if (**value != ' ') {
2473 sm_perror("parsing comparison. %s", *value);
2474 return 0;
2475 }
2476
2477 (*value)++;
2478 return 1;
2479 }
2480
2481 static int split_op_param_key(char *value, int *op, int *param, char **key)
2482 {
2483 static char buf[256];
2484 char *p;
2485
2486 if (!parse_comparison(&value, op))
2487 return 0;
2488
2489 snprintf(buf, sizeof(buf), "%s", value);
2490
2491 p = buf;
2492 if (*p++ != '$')
2493 return 0;
2494
2495 *param = atoi(p);
2496 if (*param < 0 || *param > 99)
2497 return 0;
2498 p++;
2499 if (*param > 9)
2500 p++;
2501 p--;
2502 *p = '$';
2503 *key = p;
2504
2505 return 1;
2506 }
2507
2508 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2509 {
2510 struct expression *left_arg, *right_arg;
2511 char *left_name = NULL;
2512 struct symbol *left_sym;
2513 char *right_name = NULL;
2514 struct symbol *right_sym;
2515 int op;
2516 int right_param;
2517 char *right_key;
2518 struct var_sym_list *left_vsl = NULL, *right_vsl = NULL;
2519
2520 if (left_param == -1) {
2521 if (expr->type != EXPR_ASSIGNMENT)
2522 return;
2523 left_arg = strip_expr(expr->left);
2524
2525 while (expr->type == EXPR_ASSIGNMENT)
2526 expr = strip_expr(expr->right);
2527 if (expr->type != EXPR_CALL)
2528 return;
2529 } else {
2530 while (expr->type == EXPR_ASSIGNMENT)
2531 expr = strip_expr(expr->right);
2532 if (expr->type != EXPR_CALL)
2533 return;
2534
2535 left_arg = get_argument_from_call_expr(expr->args, left_param);
2536 if (!left_arg)
2537 return;
2538 }
2539
2540 if (!split_op_param_key(value, &op, &right_param, &right_key))
2541 return;
2542
2543 right_arg = get_argument_from_call_expr(expr->args, right_param);
2544 if (!right_arg)
2545 return;
2546
2547 left_name = get_variable_from_key(left_arg, key, &left_sym);
2548 if (!left_name || !left_sym)
2549 goto free;
2550
2551 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2552 if (!right_name || !right_sym)
2553 goto free;
2554
2555 add_var_sym(&left_vsl, left_name, left_sym);
2556 add_var_sym(&right_vsl, right_name, right_sym);
2557
2558 add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl);
2559
2560 free:
2561 free_string(left_name);
2562 free_string(right_name);
2563 }
2564
2565 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value)
2566 {
2567 struct smatch_state *state;
2568 char *left_name = NULL;
2569 char *right_name = NULL;
2570 struct symbol *left_sym, *right_sym;
2571 struct expression *left_arg, *right_arg;
2572 int op, state_op;
2573 int right_param;
2574 char *right_key;
2575 int ret = 0;
2576 char buf[256];
2577
2578 while (expr->type == EXPR_ASSIGNMENT)
2579 expr = strip_expr(expr->right);
2580 if (expr->type != EXPR_CALL)
2581 return 0;
2582
2583 if (!split_op_param_key(value, &op, &right_param, &right_key))
2584 return 0;
2585
2586 left_arg = get_argument_from_call_expr(expr->args, left_param);
2587 if (!left_arg)
2588 return 0;
2589
2590 right_arg = get_argument_from_call_expr(expr->args, right_param);
2591 if (!right_arg)
2592 return 0;
2593
2594 left_name = get_variable_from_key(left_arg, left_key, &left_sym);
2595 right_name = get_variable_from_key(right_arg, right_key, &right_sym);
2596 if (!left_name || !right_name)
2597 goto free;
2598
2599 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name);
2600 state = get_state(comparison_id, buf, NULL);
2601 if (!state)
2602 goto free;
2603 state_op = state_to_comparison(state);
2604 if (!state_op)
2605 goto free;
2606
2607 if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op))
2608 ret = 1;
2609 free:
2610 free_string(left_name);
2611 free_string(right_name);
2612 return ret;
2613 }
2614
2615 int impossibly_high_comparison(struct expression *expr)
2616 {
2617 struct smatch_state *link_state;
2618 struct sm_state *sm;
2619 struct string_list *links;
2620 char *link;
2621 struct compare_data *data;
2622
2623 link_state = get_state_expr(link_id, expr);
2624 if (!link_state) {
2625 if (expr->type == EXPR_BINOP &&
2626 (impossibly_high_comparison(expr->left) ||
2627 impossibly_high_comparison(expr->right)))
2628 return 1;
2629 return 0;
2630 }
2631
2632 links = link_state->data;
2633 FOR_EACH_PTR(links, link) {
2634 sm = get_sm_state(comparison_id, link, NULL);
2635 if (!sm)
2636 continue;
2637 data = sm->state->data;
2638 if (!data)
2639 continue;
2640 if (!possibly_true(data->left, data->comparison, data->right))
2641 return 1;
2642 } END_FOR_EACH_PTR(link);
2643
2644 return 0;
2645 }
2646
2647 static void free_data(struct symbol *sym)
2648 {
2649 if (__inline_fn)
2650 return;
2651 clear_compare_data_alloc();
2652 }
2653
2654 void register_comparison(int id)
2655 {
2656 comparison_id = id;
2657 set_dynamic_states(comparison_id);
2658 add_hook(&save_start_states, AFTER_DEF_HOOK);
2659 add_unmatched_state_hook(comparison_id, unmatched_comparison);
2660 add_pre_merge_hook(comparison_id, &pre_merge_hook);
2661 add_merge_hook(comparison_id, &merge_compare_states);
2662 add_hook(&free_data, AFTER_FUNC_HOOK);
2663 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2664 add_split_return_callback(&print_return_comparison);
2665
2666 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2667 add_hook(&match_preop, OP_HOOK);
2668 }
2669
2670 void register_comparison_late(int id)
2671 {
2672 add_hook(&match_assign, ASSIGNMENT_HOOK);
2673 }
2674
2675 void register_comparison_links(int id)
2676 {
2677 link_id = id;
2678 db_ignore_states(link_id);
2679 set_dynamic_states(link_id);
2680 add_merge_hook(link_id, &merge_links);
2681 add_modification_hook(link_id, &match_modify);
2682 add_modification_hook_late(link_id, match_inc_dec);
2683
2684 add_member_info_callback(link_id, struct_member_callback);
2685 }
2686
2687 void register_comparison_inc_dec(int id)
2688 {
2689 inc_dec_id = id;
2690 add_modification_hook_late(inc_dec_id, &iter_modify);
2691 }
2692
2693 void register_comparison_inc_dec_links(int id)
2694 {
2695 inc_dec_link_id = id;
2696 set_dynamic_states(inc_dec_link_id);
2697 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2698 }
2699
2700 static struct sm_state *clone_partial_sm(struct sm_state *sm, int comparison)
2701 {
2702 struct compare_data *data;
2703 struct sm_state *clone;
2704 struct stree *stree;
2705
2706 data = sm->state->data;
2707
2708 clone = clone_sm(sm);
2709 clone->state = alloc_compare_state(data->left, data->left_var, data->left_vsl,
2710 comparison,
2711 data->right, data->right_var, data->right_vsl);
2712 free_slist(&clone->possible);
2713 add_possible_sm(clone, clone);
2714
2715 stree = clone_stree(sm->pool);
2716 overwrite_sm_state_stree(&stree, clone);
2717 clone->pool = stree;
2718
2719 return clone;
2720 }
2721
2722 static void create_fake_history(struct sm_state *sm, int op,
2723 struct state_list **true_stack,
2724 struct state_list **false_stack)
2725 {
2726 struct sm_state *true_sm, *false_sm;
2727 struct compare_data *data;
2728 int true_comparison;
2729 int false_comparison;
2730
2731 data = sm->state->data;
2732
2733 if (is_merged(sm) || sm->left || sm->right)
2734 return;
2735
2736 true_comparison = comparison_intersection(data->comparison, op);
2737 false_comparison = comparison_intersection(data->comparison, negate_comparison(op));
2738
2739 true_sm = clone_partial_sm(sm, true_comparison);
2740 false_sm = clone_partial_sm(sm, false_comparison);
2741
2742 sm->merged = 1;
2743 sm->left = true_sm;
2744 sm->right = false_sm;
2745
2746 add_ptr_list(true_stack, true_sm);
2747 add_ptr_list(false_stack, false_sm);
2748 }
2749
2750 static void filter_by_sm(struct sm_state *sm, int op,
2751 struct state_list **true_stack,
2752 struct state_list **false_stack,
2753 bool *useful)
2754 {
2755 struct compare_data *data;
2756 int is_true = 0;
2757 int is_false = 0;
2758
2759 if (!sm)
2760 return;
2761 data = sm->state->data;
2762 if (!data)
2763 goto split;
2764 if (data->comparison == IMPOSSIBLE_COMPARISON)
2765 return;
2766
2767 /*
2768 * We want to check that "data->comparison" is totally inside "op". So
2769 * if data->comparison is < and op is <= then that's true. Or if
2770 * data->comparison is == and op is <= then that's true. But if
2771 * data->comparison is <= and op is < than that's neither true nor
2772 * false.
2773 */
2774 if (data->comparison == comparison_intersection(data->comparison, op))
2775 is_true = 1;
2776 if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op)))
2777 is_false = 1;
2778
2779 if (!is_true && !is_false && !is_merged(sm)) {
2780 create_fake_history(sm, op, true_stack, false_stack);
2781 return;
2782 }
2783
2784 if (debug_implied()) {
2785 sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'",
2786 __func__,
2787 sm->state->name,
2788 alloc_sname(show_comparison(op)),
2789 alloc_sname(show_comparison(negate_comparison(op))),
2790 alloc_sname(show_comparison(comparison_intersection(data->comparison, op))),
2791 alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))),
2792 show_sm(sm));
2793 }
2794
2795 *useful = true;
2796 if (is_true)
2797 add_ptr_list(true_stack, sm);
2798 if (is_false)
2799 add_ptr_list(false_stack, sm);
2800 split:
2801 filter_by_sm(sm->left, op, true_stack, false_stack, useful);
2802 filter_by_sm(sm->right, op, true_stack, false_stack, useful);
2803 }
2804
2805 struct sm_state *comparison_implication_hook(struct expression *expr,
2806 struct state_list **true_stack,
2807 struct state_list **false_stack)
2808 {
2809 struct sm_state *sm;
2810 char *left, *right;
2811 int op;
2812 static char buf[256];
2813 bool useful = false;
2814
2815 if (expr->type != EXPR_COMPARE)
2816 return NULL;
2817
2818 op = expr->op;
2819
2820 left = expr_to_var(expr->left);
2821 right = expr_to_var(expr->right);
2822 if (!left || !right) {
2823 free_string(left);
2824 free_string(right);
2825 return NULL;
2826 }
2827
2828 if (strcmp(left, right) > 0) {
2829 char *tmp = left;
2830
2831 left = right;
2832 right = tmp;
2833 op = flip_comparison(op);
2834 }
2835
2836 snprintf(buf, sizeof(buf), "%s vs %s", left, right);
2837 sm = get_sm_state(comparison_id, buf, NULL);
2838 if (!sm)
2839 return NULL;
2840 if (!sm->merged)
2841 return NULL;
2842
2843 filter_by_sm(sm, op, true_stack, false_stack, &useful);
2844 if (!useful)
2845 return NULL;
2846
2847 if (debug_implied())
2848 sm_msg("implications from comparison: (%s)", show_sm(sm));
2849
2850 return sm;
2851 }
Static analysis for C