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