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