624
625 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
626 {
627 struct smatch_state *old_state, *new_state;
628 struct string_list *links;
629 char *new;
630
631 old_state = get_state(link_id, var, sym);
632 if (old_state)
633 links = clone_str_list(old_state->data);
634 else
635 links = NULL;
636
637 new = alloc_sname(link);
638 insert_string(&links, new);
639
640 new_state = alloc_link_state(links);
641 set_state(link_id, var, sym, new_state);
642 }
643
644 static void match_inc(struct sm_state *sm)
645 {
646 struct string_list *links;
647 struct smatch_state *state, *new;
648 struct compare_data *data;
649 char *tmp;
650 int flip;
651 int op;
652
653 links = sm->state->data;
654
655 FOR_EACH_PTR(links, tmp) {
656 state = get_state(compare_id, tmp, NULL);
657 if (!state)
658 continue;
659 data = state->data;
660 if (!data)
661 continue;
662
663 flip = 0;
664 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
665 tmp[strlen(sm->name)] != ' ')
666 flip = 1;
667
668 op = state_to_comparison(state);
669
670 switch (flip ? flip_comparison(op) : op) {
671 case SPECIAL_EQUAL:
672 case SPECIAL_GTE:
673 case SPECIAL_UNSIGNED_GTE:
674 case '>':
675 case SPECIAL_UNSIGNED_GT:
676 new = alloc_compare_state(
677 data->left, data->left_var, data->left_vsl,
678 flip ? '<' : '>',
679 data->right, data->right_var, data->right_vsl);
680 set_state(compare_id, tmp, NULL, new);
681 break;
682 case '<':
683 case SPECIAL_UNSIGNED_LT:
684 new = alloc_compare_state(
685 data->left, data->left_var, data->left_vsl,
686 flip ? SPECIAL_GTE : SPECIAL_LTE,
687 data->right, data->right_var, data->right_vsl);
688 set_state(compare_id, tmp, NULL, new);
689 break;
690 default:
691 set_state(compare_id, tmp, NULL, &undefined);
692 }
693 } END_FOR_EACH_PTR(tmp);
694 }
695
696 static void match_dec(struct sm_state *sm)
697 {
698 struct string_list *links;
699 struct smatch_state *state;
700 char *tmp;
701
702 links = sm->state->data;
703
704 FOR_EACH_PTR(links, tmp) {
705 state = get_state(compare_id, tmp, NULL);
706
707 switch (state_to_comparison(state)) {
708 case SPECIAL_EQUAL:
709 case SPECIAL_LTE:
710 case SPECIAL_UNSIGNED_LTE:
711 case '<':
712 case SPECIAL_UNSIGNED_LT: {
713 struct compare_data *data = state->data;
714 struct smatch_state *new;
715
716 new = alloc_compare_state(
717 data->left, data->left_var, data->left_vsl,
718 '<',
719 data->right, data->right_var, data->right_vsl);
720 set_state(compare_id, tmp, NULL, new);
721 break;
722 }
723 default:
724 set_state(compare_id, tmp, NULL, &undefined);
725 }
726 } END_FOR_EACH_PTR(tmp);
727 }
728
729 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
730 {
731 /*
732 * if (foo > bar) then ++foo is also > bar.
733 */
734 if (!mod_expr)
735 return;
736 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
737 return;
738
739 if (mod_expr->op == SPECIAL_INCREMENT)
740 match_inc(sm);
741 else if (mod_expr->op == SPECIAL_DECREMENT)
742 match_dec(sm);
743 }
744
745 static int is_self_assign(struct expression *expr)
746 {
747 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
748 return 0;
749 return expr_equiv(expr->left, expr->right);
750 }
751
752 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
753 {
754 struct string_list *links;
755 char *tmp;
756
757 if (mod_expr && is_self_assign(mod_expr))
758 return;
759
760 /* handled by match_inc_dec() */
761 if (mod_expr &&
762 ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
763 (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
764 return;
765
766 links = sm->state->data;
767
768 FOR_EACH_PTR(links, tmp) {
769 set_state(compare_id, tmp, NULL, &undefined);
770 } END_FOR_EACH_PTR(tmp);
771 set_state(link_id, sm->name, sm->sym, &undefined);
772 }
773
774 static void match_preop(struct expression *expr)
775 {
776 struct expression *parent;
777 struct range_list *left, *right;
778 int op;
779
780 /*
781 * This is an important special case. Say you have:
782 *
783 * if (++j == limit)
784 *
785 * Assume that we know the range of limit is higher than the start
786 * value for "j". Then the first thing that we process is the ++j. We
787 * have not comparison states set up so it doesn't get caught by the
788 * modification hook. But it does get caught by smatch_extra which sets
789 * j to unknown then we parse the "j == limit" and sets false to != but
790 * really we want false to be <.
791 *
1587
1588 if (strcmp(one, two) > 0) {
1589 const char *tmp = one;
1590
1591 one = two;
1592 two = tmp;
1593 invert = 1;
1594 }
1595
1596 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1597 state = get_state(compare_id, buf, NULL);
1598 if (state)
1599 ret = state_to_comparison(state);
1600
1601 if (invert)
1602 ret = flip_comparison(ret);
1603
1604 return ret;
1605 }
1606
1607 int get_comparison(struct expression *a, struct expression *b)
1608 {
1609 char *one = NULL;
1610 char *two = NULL;
1611 int ret = 0;
1612
1613 if (!a || !b)
1614 return 0;
1615
1616 a = strip_parens(a);
1617 b = strip_parens(b);
1618
1619 move_plus_to_minus(&a, &b);
1620
1621 one = chunk_to_var(a);
1622 if (!one)
1623 goto free;
1624 two = chunk_to_var(b);
1625 if (!two)
1626 goto free;
1627
1636 } else if (is_plus_one(b) || is_minus_one(b)) {
1637 free_string(two);
1638 two = chunk_to_var(b->left);
1639 ret = get_comparison_strings(one, two);
1640 }
1641
1642 if (!ret)
1643 goto free;
1644
1645 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1646 ret = SPECIAL_LTE;
1647 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1648 ret = SPECIAL_GTE;
1649 else
1650 ret = 0;
1651
1652 free:
1653 free_string(one);
1654 free_string(two);
1655
1656 if (!ret)
1657 return comparison_from_extra(a, b);
1658 return ret;
1659 }
1660
1661 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1662 {
1663 char *one = NULL;
1664 char *two = NULL;
1665 int ret = 0;
1666 char buf[256];
1667 struct sm_state *sm;
1668 int saved;
1669
1670 one = chunk_to_var(a);
1671 if (!one)
1672 goto free;
1673 two = chunk_to_var(b);
1674 if (!two)
1675 goto free;
1676
1677
1678 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1679 ret = 1;
1680 goto free;
2310 return 0;
2311 }
2312
2313 if (**value != ' ') {
2314 sm_perror("parsing comparison. %s", *value);
2315 return 0;
2316 }
2317
2318 (*value)++;
2319 return 1;
2320 }
2321
2322 static int split_op_param_key(char *value, int *op, int *param, char **key)
2323 {
2324 static char buf[256];
2325 char *p;
2326
2327 if (!parse_comparison(&value, op))
2328 return 0;
2329
2330 snprintf(buf, sizeof(buf), value);
2331
2332 p = buf;
2333 if (*p++ != '$')
2334 return 0;
2335
2336 *param = atoi(p);
2337 if (*param < 0 || *param > 99)
2338 return 0;
2339 p++;
2340 if (*param > 9)
2341 p++;
2342 p--;
2343 *p = '$';
2344 *key = p;
2345
2346 return 1;
2347 }
2348
2349 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2350 {
2478 data = sm->state->data;
2479 if (!data)
2480 continue;
2481 if (!possibly_true(data->left, data->comparison, data->right))
2482 return 1;
2483 } END_FOR_EACH_PTR(link);
2484
2485 return 0;
2486 }
2487
2488 static void free_data(struct symbol *sym)
2489 {
2490 if (__inline_fn)
2491 return;
2492 clear_compare_data_alloc();
2493 }
2494
2495 void register_comparison(int id)
2496 {
2497 compare_id = id;
2498 add_hook(&save_start_states, AFTER_DEF_HOOK);
2499 add_unmatched_state_hook(compare_id, unmatched_comparison);
2500 add_pre_merge_hook(compare_id, &pre_merge_hook);
2501 add_merge_hook(compare_id, &merge_compare_states);
2502 add_hook(&free_data, AFTER_FUNC_HOOK);
2503 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2504 add_split_return_callback(&print_return_comparison);
2505
2506 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2507 add_hook(&match_preop, OP_HOOK);
2508 }
2509
2510 void register_comparison_late(int id)
2511 {
2512 add_hook(&match_assign, ASSIGNMENT_HOOK);
2513 }
2514
2515 void register_comparison_links(int id)
2516 {
2517 link_id = id;
2518 add_merge_hook(link_id, &merge_links);
2519 add_modification_hook(link_id, &match_modify);
2520 add_modification_hook_late(link_id, match_inc_dec);
2521
2522 add_member_info_callback(link_id, struct_member_callback);
2523 }
2524
2525 void register_comparison_inc_dec(int id)
2526 {
2527 inc_dec_id = id;
2528 add_modification_hook_late(inc_dec_id, &iter_modify);
2529 }
2530
2531 void register_comparison_inc_dec_links(int id)
2532 {
2533 inc_dec_link_id = id;
2534 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2535 }
2536
2537 static void filter_by_sm(struct sm_state *sm, int op,
2538 struct state_list **true_stack,
2539 struct state_list **false_stack)
2540 {
2541 struct compare_data *data;
2542 int istrue = 0;
2543 int isfalse = 0;
2544
2545 if (!sm)
2546 return;
2547 data = sm->state->data;
2548 if (!data) {
2549 if (sm->merged) {
2550 filter_by_sm(sm->left, op, true_stack, false_stack);
2551 filter_by_sm(sm->right, op, true_stack, false_stack);
2552 }
2553 return;
|
624
625 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
626 {
627 struct smatch_state *old_state, *new_state;
628 struct string_list *links;
629 char *new;
630
631 old_state = get_state(link_id, var, sym);
632 if (old_state)
633 links = clone_str_list(old_state->data);
634 else
635 links = NULL;
636
637 new = alloc_sname(link);
638 insert_string(&links, new);
639
640 new_state = alloc_link_state(links);
641 set_state(link_id, var, sym, new_state);
642 }
643
644 static void match_inc(struct sm_state *sm, bool preserve)
645 {
646 struct string_list *links;
647 struct smatch_state *state, *new;
648 struct compare_data *data;
649 char *tmp;
650 int flip;
651 int op;
652
653 links = sm->state->data;
654
655 FOR_EACH_PTR(links, tmp) {
656 state = get_state(compare_id, tmp, NULL);
657 if (!state)
658 continue;
659 data = state->data;
660 if (!data)
661 continue;
662
663 flip = 0;
664 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 ||
665 tmp[strlen(sm->name)] != ' ')
666 flip = 1;
667
668 op = state_to_comparison(state);
669
670 switch (flip ? flip_comparison(op) : op) {
671 case SPECIAL_EQUAL:
672 case SPECIAL_GTE:
673 case SPECIAL_UNSIGNED_GTE:
674 case '>':
675 case SPECIAL_UNSIGNED_GT:
676 if (preserve)
677 break;
678 new = alloc_compare_state(
679 data->left, data->left_var, data->left_vsl,
680 flip ? '<' : '>',
681 data->right, data->right_var, data->right_vsl);
682 set_state(compare_id, tmp, NULL, new);
683 break;
684 case '<':
685 case SPECIAL_UNSIGNED_LT:
686 new = alloc_compare_state(
687 data->left, data->left_var, data->left_vsl,
688 flip ? SPECIAL_GTE : SPECIAL_LTE,
689 data->right, data->right_var, data->right_vsl);
690 set_state(compare_id, tmp, NULL, new);
691 break;
692 default:
693 set_state(compare_id, tmp, NULL, &undefined);
694 }
695 } END_FOR_EACH_PTR(tmp);
696 }
697
698 static void match_dec(struct sm_state *sm, bool preserve)
699 {
700 struct string_list *links;
701 struct smatch_state *state;
702 char *tmp;
703
704 links = sm->state->data;
705
706 FOR_EACH_PTR(links, tmp) {
707 state = get_state(compare_id, tmp, NULL);
708
709 switch (state_to_comparison(state)) {
710 case SPECIAL_EQUAL:
711 case SPECIAL_LTE:
712 case SPECIAL_UNSIGNED_LTE:
713 case '<':
714 case SPECIAL_UNSIGNED_LT: {
715 struct compare_data *data = state->data;
716 struct smatch_state *new;
717
718 if (preserve)
719 break;
720
721 new = alloc_compare_state(
722 data->left, data->left_var, data->left_vsl,
723 '<',
724 data->right, data->right_var, data->right_vsl);
725 set_state(compare_id, tmp, NULL, new);
726 break;
727 }
728 default:
729 set_state(compare_id, tmp, NULL, &undefined);
730 }
731 } END_FOR_EACH_PTR(tmp);
732 }
733
734 static void reset_sm(struct sm_state *sm)
735 {
736 struct string_list *links;
737 char *tmp;
738
739 links = sm->state->data;
740
741 FOR_EACH_PTR(links, tmp) {
742 set_state(compare_id, tmp, NULL, &undefined);
743 } END_FOR_EACH_PTR(tmp);
744 set_state(link_id, sm->name, sm->sym, &undefined);
745 }
746
747 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr)
748 {
749 struct range_list *rl;
750 sval_t zero = { .type = &int_ctype };
751
752 if (!expr || expr->type != EXPR_ASSIGNMENT)
753 return false;
754 if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN)
755 return false;
756
757 get_absolute_rl(expr->right, &rl);
758 if (sval_is_negative(rl_min(rl))) {
759 reset_sm(sm);
760 return false;
761 }
762
763 if (expr->op == SPECIAL_ADD_ASSIGN)
764 match_inc(sm, rl_has_sval(rl, zero));
765 else
766 match_dec(sm, rl_has_sval(rl, zero));
767 return true;
768 }
769
770 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
771 {
772 /*
773 * if (foo > bar) then ++foo is also > bar.
774 */
775 if (!mod_expr)
776 return;
777 if (match_add_sub_assign(sm, mod_expr))
778 return;
779 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
780 return;
781
782 if (mod_expr->op == SPECIAL_INCREMENT)
783 match_inc(sm, false);
784 else if (mod_expr->op == SPECIAL_DECREMENT)
785 match_dec(sm, false);
786 }
787
788 static int is_self_assign(struct expression *expr)
789 {
790 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
791 return 0;
792 return expr_equiv(expr->left, expr->right);
793 }
794
795 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
796 {
797 if (mod_expr && is_self_assign(mod_expr))
798 return;
799
800 /* handled by match_inc_dec() */
801 if (mod_expr &&
802 ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) &&
803 (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT)))
804 return;
805 if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT &&
806 (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN))
807 return;
808
809 reset_sm(sm);
810 }
811
812 static void match_preop(struct expression *expr)
813 {
814 struct expression *parent;
815 struct range_list *left, *right;
816 int op;
817
818 /*
819 * This is an important special case. Say you have:
820 *
821 * if (++j == limit)
822 *
823 * Assume that we know the range of limit is higher than the start
824 * value for "j". Then the first thing that we process is the ++j. We
825 * have not comparison states set up so it doesn't get caught by the
826 * modification hook. But it does get caught by smatch_extra which sets
827 * j to unknown then we parse the "j == limit" and sets false to != but
828 * really we want false to be <.
829 *
1625
1626 if (strcmp(one, two) > 0) {
1627 const char *tmp = one;
1628
1629 one = two;
1630 two = tmp;
1631 invert = 1;
1632 }
1633
1634 snprintf(buf, sizeof(buf), "%s vs %s", one, two);
1635 state = get_state(compare_id, buf, NULL);
1636 if (state)
1637 ret = state_to_comparison(state);
1638
1639 if (invert)
1640 ret = flip_comparison(ret);
1641
1642 return ret;
1643 }
1644
1645 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra)
1646 {
1647 char *one = NULL;
1648 char *two = NULL;
1649 int ret = 0;
1650
1651 if (!a || !b)
1652 return 0;
1653
1654 a = strip_parens(a);
1655 b = strip_parens(b);
1656
1657 move_plus_to_minus(&a, &b);
1658
1659 one = chunk_to_var(a);
1660 if (!one)
1661 goto free;
1662 two = chunk_to_var(b);
1663 if (!two)
1664 goto free;
1665
1674 } else if (is_plus_one(b) || is_minus_one(b)) {
1675 free_string(two);
1676 two = chunk_to_var(b->left);
1677 ret = get_comparison_strings(one, two);
1678 }
1679
1680 if (!ret)
1681 goto free;
1682
1683 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<')
1684 ret = SPECIAL_LTE;
1685 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>')
1686 ret = SPECIAL_GTE;
1687 else
1688 ret = 0;
1689
1690 free:
1691 free_string(one);
1692 free_string(two);
1693
1694 if (!ret && use_extra)
1695 return comparison_from_extra(a, b);
1696 return ret;
1697 }
1698
1699 int get_comparison(struct expression *a, struct expression *b)
1700 {
1701 return get_comparison_helper(a, b, true);
1702 }
1703
1704 int get_comparison_no_extra(struct expression *a, struct expression *b)
1705 {
1706 return get_comparison_helper(a, b, false);
1707 }
1708
1709 int possible_comparison(struct expression *a, int comparison, struct expression *b)
1710 {
1711 char *one = NULL;
1712 char *two = NULL;
1713 int ret = 0;
1714 char buf[256];
1715 struct sm_state *sm;
1716 int saved;
1717
1718 one = chunk_to_var(a);
1719 if (!one)
1720 goto free;
1721 two = chunk_to_var(b);
1722 if (!two)
1723 goto free;
1724
1725
1726 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) {
1727 ret = 1;
1728 goto free;
2358 return 0;
2359 }
2360
2361 if (**value != ' ') {
2362 sm_perror("parsing comparison. %s", *value);
2363 return 0;
2364 }
2365
2366 (*value)++;
2367 return 1;
2368 }
2369
2370 static int split_op_param_key(char *value, int *op, int *param, char **key)
2371 {
2372 static char buf[256];
2373 char *p;
2374
2375 if (!parse_comparison(&value, op))
2376 return 0;
2377
2378 snprintf(buf, sizeof(buf), "%s", value);
2379
2380 p = buf;
2381 if (*p++ != '$')
2382 return 0;
2383
2384 *param = atoi(p);
2385 if (*param < 0 || *param > 99)
2386 return 0;
2387 p++;
2388 if (*param > 9)
2389 p++;
2390 p--;
2391 *p = '$';
2392 *key = p;
2393
2394 return 1;
2395 }
2396
2397 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value)
2398 {
2526 data = sm->state->data;
2527 if (!data)
2528 continue;
2529 if (!possibly_true(data->left, data->comparison, data->right))
2530 return 1;
2531 } END_FOR_EACH_PTR(link);
2532
2533 return 0;
2534 }
2535
2536 static void free_data(struct symbol *sym)
2537 {
2538 if (__inline_fn)
2539 return;
2540 clear_compare_data_alloc();
2541 }
2542
2543 void register_comparison(int id)
2544 {
2545 compare_id = id;
2546 set_dynamic_states(compare_id);
2547 add_hook(&save_start_states, AFTER_DEF_HOOK);
2548 add_unmatched_state_hook(compare_id, unmatched_comparison);
2549 add_pre_merge_hook(compare_id, &pre_merge_hook);
2550 add_merge_hook(compare_id, &merge_compare_states);
2551 add_hook(&free_data, AFTER_FUNC_HOOK);
2552 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2553 add_split_return_callback(&print_return_comparison);
2554
2555 select_return_states_hook(PARAM_COMPARE, &db_return_comparison);
2556 add_hook(&match_preop, OP_HOOK);
2557 }
2558
2559 void register_comparison_late(int id)
2560 {
2561 add_hook(&match_assign, ASSIGNMENT_HOOK);
2562 }
2563
2564 void register_comparison_links(int id)
2565 {
2566 link_id = id;
2567 db_ignore_states(link_id);
2568 set_dynamic_states(link_id);
2569 add_merge_hook(link_id, &merge_links);
2570 add_modification_hook(link_id, &match_modify);
2571 add_modification_hook_late(link_id, match_inc_dec);
2572
2573 add_member_info_callback(link_id, struct_member_callback);
2574 }
2575
2576 void register_comparison_inc_dec(int id)
2577 {
2578 inc_dec_id = id;
2579 add_modification_hook_late(inc_dec_id, &iter_modify);
2580 }
2581
2582 void register_comparison_inc_dec_links(int id)
2583 {
2584 inc_dec_link_id = id;
2585 set_dynamic_states(inc_dec_link_id);
2586 set_up_link_functions(inc_dec_id, inc_dec_link_id);
2587 }
2588
2589 static void filter_by_sm(struct sm_state *sm, int op,
2590 struct state_list **true_stack,
2591 struct state_list **false_stack)
2592 {
2593 struct compare_data *data;
2594 int istrue = 0;
2595 int isfalse = 0;
2596
2597 if (!sm)
2598 return;
2599 data = sm->state->data;
2600 if (!data) {
2601 if (sm->merged) {
2602 filter_by_sm(sm->left, op, true_stack, false_stack);
2603 filter_by_sm(sm->right, op, true_stack, false_stack);
2604 }
2605 return;
|