Print this page
new smatch


  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17 
  18 #include "symbol.h"
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22 
  23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
  24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
  25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
  26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
  27 
  28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
  29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
  30 
  31 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  32 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  33 


  34 struct range_list *rl_zero(void)
  35 {
  36         static struct range_list *zero_perm;
  37 
  38         if (!zero_perm)
  39                 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
  40         return zero_perm;
  41 }
  42 
  43 struct range_list *rl_one(void)
  44 {
  45         static struct range_list *one_perm;
  46 
  47         if (!one_perm)
  48                 one_perm = clone_rl_permanent(alloc_rl(one, one));
  49 
  50         return one_perm;
  51 }
  52 
  53 enum {


 839         int final_pass_orig = final_pass;
 840 
 841         cond_true = expr->cond_true;
 842         if (!cond_true)
 843                 cond_true = expr->conditional;
 844 
 845         if (known_condition_true(expr->conditional))
 846                 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
 847         if (known_condition_false(expr->conditional))
 848                 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
 849 
 850         if (implied == RL_EXACT)
 851                 return false;
 852 
 853         if (implied_condition_true(expr->conditional))
 854                 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
 855         if (implied_condition_false(expr->conditional))
 856                 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
 857 
 858         /* this becomes a problem with deeply nested conditional statements */
 859         if (low_on_memory())
 860                 return false;
 861 
 862         type = get_type(expr);
 863 
 864         __push_fake_cur_stree();
 865         final_pass = 0;
 866         __split_whole_condition(expr->conditional);
 867         true_rl = NULL;
 868         get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
 869         __push_true_states();
 870         __use_false_states();
 871         false_rl = NULL;
 872         get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
 873         __merge_true_states();
 874         __free_fake_cur_stree();
 875         final_pass = final_pass_orig;
 876 
 877         if (!true_rl || !false_rl)
 878                 return false;
 879         true_rl = cast_rl(type, true_rl);


 930         sym = expr->symbol;
 931         if (!(sym->ctype.modifiers & MOD_CONST))
 932                 return 0;
 933         if (get_value(sym->initializer, &right)) {
 934                 *sval = sval_cast(get_type(expr), right);
 935                 return 1;
 936         }
 937         return 0;
 938 }
 939 
 940 struct range_list *var_to_absolute_rl(struct expression *expr)
 941 {
 942         struct smatch_state *state;
 943         struct range_list *rl;
 944 
 945         state = get_extra_state(expr);
 946         if (!state || is_whole_rl(estate_rl(state))) {
 947                 state = get_real_absolute_state(expr);
 948                 if (state && state->data && !estate_is_whole(state))
 949                         return clone_rl(estate_rl(state));
 950                 if (get_local_rl(expr, &rl) && !is_whole_rl(rl))
 951                         return rl;
 952                 if (get_mtag_rl(expr, &rl))
 953                         return rl;
 954                 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
 955                         return rl;
 956                 return alloc_whole_rl(get_type(expr));
 957         }
 958         /* err on the side of saying things are possible */
 959         if (!estate_rl(state))
 960                 return alloc_whole_rl(get_type(expr));
 961         return clone_rl(estate_rl(state));
 962 }
 963 
 964 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 965 {
 966         struct smatch_state *state;
 967         struct range_list *rl;
 968         sval_t sval, min, max;
 969         struct symbol *type;
 970 
 971         if (get_const_value(expr, &sval)) {


 991                 *res_sval = sval;
 992                 return true;
 993         }
 994 
 995         type = get_type(expr);
 996         if (type &&
 997             (type->type == SYM_ARRAY ||
 998              type->type == SYM_FN))
 999                 return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000 
1001         /* FIXME: call rl_to_sval() on the results */
1002 
1003         switch (implied) {
1004         case RL_HARD:
1005         case RL_IMPLIED:
1006         case RL_ABSOLUTE:
1007                 state = get_extra_state(expr);
1008                 if (!state) {
1009                         if (implied == RL_HARD)
1010                                 return false;
1011                         if (get_local_rl(expr, res))
1012                                 return true;
1013                         if (get_mtag_rl(expr, res))
1014                                 return true;
1015                         if (get_db_type_rl(expr, res))
1016                                 return true;
1017                         if (is_array(expr) && get_array_rl(expr, res))
1018                                 return true;
1019                         return false;
1020                 }
1021                 if (implied == RL_HARD && !estate_has_hard_max(state))
1022                         return false;
1023                 *res = clone_rl(estate_rl(state));
1024                 return true;
1025         case RL_REAL_ABSOLUTE: {
1026                 struct smatch_state *abs_state;
1027 
1028                 state = get_extra_state(expr);
1029                 abs_state = get_real_absolute_state(expr);
1030 
1031                 if (estate_rl(state) && estate_rl(abs_state)) {
1032                         *res = clone_rl(rl_intersection(estate_rl(state),


1043                          * extra state if there is one.  We don't bother keeping
1044                          * the abs state in sync all the time because we know it
1045                          * will be filtered later.
1046                          *
1047                          * It's not totally obvious to me how they should be
1048                          * handled.  Perhaps we should take the whole rl and
1049                          * filter by the imaginary states.  Perhaps we should
1050                          * just go with the empty state.
1051                          *
1052                          * Anyway what we currently do is return NULL here and
1053                          * that gets translated into the whole range in
1054                          * get_real_absolute_rl().
1055                          *
1056                          */
1057                         return false;
1058                 } else if (estate_rl(abs_state)) {
1059                         *res = clone_rl(estate_rl(abs_state));
1060                         return true;
1061                 }
1062 
1063                 if (get_local_rl(expr, res))
1064                         return true;
1065                 if (get_mtag_rl(expr, res))
1066                         return true;
1067                 if (get_db_type_rl(expr, res))
1068                         return true;
1069                 if (is_array(expr) && get_array_rl(expr, res))
1070                         return true;
1071                 return false;
1072         }
1073         case RL_FUZZY:
1074                 if (!get_fuzzy_min_helper(expr, &min))
1075                         min = sval_type_min(get_type(expr));
1076                 if (!get_fuzzy_max_helper(expr, &max))
1077                         return false;
1078                 /* fuzzy ranges are often inverted */
1079                 if (sval_cmp(min, max) > 0) {
1080                         sval = min;
1081                         min = max;
1082                         max = sval;
1083                 }
1084                 *res = alloc_rl(min, max);


1499                 return false;
1500 
1501         if (sval.type)
1502                 *res = alloc_rl(sval, sval);
1503         else
1504                 *res = rl;
1505         return true;
1506 }
1507 
1508 struct {
1509         struct expression *expr;
1510         sval_t sval;
1511 } cached_results[24];
1512 static int cache_idx;
1513 
1514 void clear_math_cache(void)
1515 {
1516         memset(cached_results, 0, sizeof(cached_results));
1517 }
1518 










1519 /*
1520  * Don't cache EXPR_VALUE because values are fast already.
1521  *
1522  */
1523 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1524 {
1525         struct expression *tmp;
1526         int recurse_cnt = 0;
1527 
1528         tmp = strip_expr(expr);
1529         if (!tmp || tmp->type != EXPR_VALUE)
1530                 return false;
1531 
1532         return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1533 }
1534 
1535 /* returns 1 if it can get a value literal or else returns 0 */
1536 int get_value(struct expression *expr, sval_t *res_sval)
1537 {
1538         struct range_list *(*orig_custom_fn)(struct expression *expr);


1743                 type = &llong_ctype;
1744         rl = NULL;
1745         get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1746         if (rl)
1747                 *sval = rl_max(rl);
1748         else
1749                 *sval = sval_type_max(type);
1750 
1751         if (sval_cmp(sval_type_max(type), *sval) < 0)
1752                 *sval = sval_type_max(type);
1753         return 1;
1754 }
1755 
1756 int known_condition_true(struct expression *expr)
1757 {
1758         sval_t tmp;
1759 
1760         if (!expr)
1761                 return 0;
1762 






1763         if (get_value(expr, &tmp) && tmp.value)
1764                 return 1;
1765 
1766         return 0;
1767 }
1768 
1769 int known_condition_false(struct expression *expr)
1770 {


1771         if (!expr)
1772                 return 0;
1773 
1774         if (is_zero(expr))

1775                 return 1;


1776 



1777         return 0;
1778 }
1779 
1780 int implied_condition_true(struct expression *expr)
1781 {
1782         sval_t tmp;
1783 
1784         if (!expr)
1785                 return 0;
1786 
1787         if (known_condition_true(expr))
1788                 return 1;
1789         if (get_implied_value(expr, &tmp) && tmp.value)
1790                 return 1;
1791 
1792         if (expr->type == EXPR_POSTOP)
1793                 return implied_condition_true(expr->unop);
1794 
1795         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1796                 return implied_not_equal(expr->unop, 1);




  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17 
  18 #include "symbol.h"
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22 
  23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
  24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
  25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
  26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
  27 
  28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
  29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
  30 
  31 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  32 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  33 
  34 static int fast_math_only;
  35 
  36 struct range_list *rl_zero(void)
  37 {
  38         static struct range_list *zero_perm;
  39 
  40         if (!zero_perm)
  41                 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
  42         return zero_perm;
  43 }
  44 
  45 struct range_list *rl_one(void)
  46 {
  47         static struct range_list *one_perm;
  48 
  49         if (!one_perm)
  50                 one_perm = clone_rl_permanent(alloc_rl(one, one));
  51 
  52         return one_perm;
  53 }
  54 
  55 enum {


 841         int final_pass_orig = final_pass;
 842 
 843         cond_true = expr->cond_true;
 844         if (!cond_true)
 845                 cond_true = expr->conditional;
 846 
 847         if (known_condition_true(expr->conditional))
 848                 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
 849         if (known_condition_false(expr->conditional))
 850                 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
 851 
 852         if (implied == RL_EXACT)
 853                 return false;
 854 
 855         if (implied_condition_true(expr->conditional))
 856                 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
 857         if (implied_condition_false(expr->conditional))
 858                 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
 859 
 860         /* this becomes a problem with deeply nested conditional statements */
 861         if (fast_math_only || low_on_memory())
 862                 return false;
 863 
 864         type = get_type(expr);
 865 
 866         __push_fake_cur_stree();
 867         final_pass = 0;
 868         __split_whole_condition(expr->conditional);
 869         true_rl = NULL;
 870         get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
 871         __push_true_states();
 872         __use_false_states();
 873         false_rl = NULL;
 874         get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
 875         __merge_true_states();
 876         __free_fake_cur_stree();
 877         final_pass = final_pass_orig;
 878 
 879         if (!true_rl || !false_rl)
 880                 return false;
 881         true_rl = cast_rl(type, true_rl);


 932         sym = expr->symbol;
 933         if (!(sym->ctype.modifiers & MOD_CONST))
 934                 return 0;
 935         if (get_value(sym->initializer, &right)) {
 936                 *sval = sval_cast(get_type(expr), right);
 937                 return 1;
 938         }
 939         return 0;
 940 }
 941 
 942 struct range_list *var_to_absolute_rl(struct expression *expr)
 943 {
 944         struct smatch_state *state;
 945         struct range_list *rl;
 946 
 947         state = get_extra_state(expr);
 948         if (!state || is_whole_rl(estate_rl(state))) {
 949                 state = get_real_absolute_state(expr);
 950                 if (state && state->data && !estate_is_whole(state))
 951                         return clone_rl(estate_rl(state));


 952                 if (get_mtag_rl(expr, &rl))
 953                         return rl;
 954                 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
 955                         return rl;
 956                 return alloc_whole_rl(get_type(expr));
 957         }
 958         /* err on the side of saying things are possible */
 959         if (!estate_rl(state))
 960                 return alloc_whole_rl(get_type(expr));
 961         return clone_rl(estate_rl(state));
 962 }
 963 
 964 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 965 {
 966         struct smatch_state *state;
 967         struct range_list *rl;
 968         sval_t sval, min, max;
 969         struct symbol *type;
 970 
 971         if (get_const_value(expr, &sval)) {


 991                 *res_sval = sval;
 992                 return true;
 993         }
 994 
 995         type = get_type(expr);
 996         if (type &&
 997             (type->type == SYM_ARRAY ||
 998              type->type == SYM_FN))
 999                 return handle_address(expr, implied, recurse_cnt, res, res_sval);
1000 
1001         /* FIXME: call rl_to_sval() on the results */
1002 
1003         switch (implied) {
1004         case RL_HARD:
1005         case RL_IMPLIED:
1006         case RL_ABSOLUTE:
1007                 state = get_extra_state(expr);
1008                 if (!state) {
1009                         if (implied == RL_HARD)
1010                                 return false;


1011                         if (get_mtag_rl(expr, res))
1012                                 return true;
1013                         if (get_db_type_rl(expr, res))
1014                                 return true;
1015                         if (is_array(expr) && get_array_rl(expr, res))
1016                                 return true;
1017                         return false;
1018                 }
1019                 if (implied == RL_HARD && !estate_has_hard_max(state))
1020                         return false;
1021                 *res = clone_rl(estate_rl(state));
1022                 return true;
1023         case RL_REAL_ABSOLUTE: {
1024                 struct smatch_state *abs_state;
1025 
1026                 state = get_extra_state(expr);
1027                 abs_state = get_real_absolute_state(expr);
1028 
1029                 if (estate_rl(state) && estate_rl(abs_state)) {
1030                         *res = clone_rl(rl_intersection(estate_rl(state),


1041                          * extra state if there is one.  We don't bother keeping
1042                          * the abs state in sync all the time because we know it
1043                          * will be filtered later.
1044                          *
1045                          * It's not totally obvious to me how they should be
1046                          * handled.  Perhaps we should take the whole rl and
1047                          * filter by the imaginary states.  Perhaps we should
1048                          * just go with the empty state.
1049                          *
1050                          * Anyway what we currently do is return NULL here and
1051                          * that gets translated into the whole range in
1052                          * get_real_absolute_rl().
1053                          *
1054                          */
1055                         return false;
1056                 } else if (estate_rl(abs_state)) {
1057                         *res = clone_rl(estate_rl(abs_state));
1058                         return true;
1059                 }
1060 


1061                 if (get_mtag_rl(expr, res))
1062                         return true;
1063                 if (get_db_type_rl(expr, res))
1064                         return true;
1065                 if (is_array(expr) && get_array_rl(expr, res))
1066                         return true;
1067                 return false;
1068         }
1069         case RL_FUZZY:
1070                 if (!get_fuzzy_min_helper(expr, &min))
1071                         min = sval_type_min(get_type(expr));
1072                 if (!get_fuzzy_max_helper(expr, &max))
1073                         return false;
1074                 /* fuzzy ranges are often inverted */
1075                 if (sval_cmp(min, max) > 0) {
1076                         sval = min;
1077                         min = max;
1078                         max = sval;
1079                 }
1080                 *res = alloc_rl(min, max);


1495                 return false;
1496 
1497         if (sval.type)
1498                 *res = alloc_rl(sval, sval);
1499         else
1500                 *res = rl;
1501         return true;
1502 }
1503 
1504 struct {
1505         struct expression *expr;
1506         sval_t sval;
1507 } cached_results[24];
1508 static int cache_idx;
1509 
1510 void clear_math_cache(void)
1511 {
1512         memset(cached_results, 0, sizeof(cached_results));
1513 }
1514 
1515 void set_fast_math_only(void)
1516 {
1517         fast_math_only++;
1518 }
1519 
1520 void clear_fast_math_only(void)
1521 {
1522         fast_math_only--;
1523 }
1524 
1525 /*
1526  * Don't cache EXPR_VALUE because values are fast already.
1527  *
1528  */
1529 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1530 {
1531         struct expression *tmp;
1532         int recurse_cnt = 0;
1533 
1534         tmp = strip_expr(expr);
1535         if (!tmp || tmp->type != EXPR_VALUE)
1536                 return false;
1537 
1538         return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1539 }
1540 
1541 /* returns 1 if it can get a value literal or else returns 0 */
1542 int get_value(struct expression *expr, sval_t *res_sval)
1543 {
1544         struct range_list *(*orig_custom_fn)(struct expression *expr);


1749                 type = &llong_ctype;
1750         rl = NULL;
1751         get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1752         if (rl)
1753                 *sval = rl_max(rl);
1754         else
1755                 *sval = sval_type_max(type);
1756 
1757         if (sval_cmp(sval_type_max(type), *sval) < 0)
1758                 *sval = sval_type_max(type);
1759         return 1;
1760 }
1761 
1762 int known_condition_true(struct expression *expr)
1763 {
1764         sval_t tmp;
1765 
1766         if (!expr)
1767                 return 0;
1768 
1769         if (__inline_fn && get_param_num(expr) >= 0) {
1770                 if (get_implied_value(expr, &tmp) && tmp.value)
1771                         return 1;
1772                 return 0;
1773         }
1774 
1775         if (get_value(expr, &tmp) && tmp.value)
1776                 return 1;
1777 
1778         return 0;
1779 }
1780 
1781 int known_condition_false(struct expression *expr)
1782 {
1783         sval_t tmp;
1784 
1785         if (!expr)
1786                 return 0;
1787 
1788         if (__inline_fn && get_param_num(expr) >= 0) {
1789                 if (get_implied_value(expr, &tmp) && tmp.value == 0)
1790                         return 1;
1791                 return 0;
1792         }
1793 
1794         if (expr_is_zero(expr))
1795                 return 1;
1796 
1797         return 0;
1798 }
1799 
1800 int implied_condition_true(struct expression *expr)
1801 {
1802         sval_t tmp;
1803 
1804         if (!expr)
1805                 return 0;
1806 
1807         if (known_condition_true(expr))
1808                 return 1;
1809         if (get_implied_value(expr, &tmp) && tmp.value)
1810                 return 1;
1811 
1812         if (expr->type == EXPR_POSTOP)
1813                 return implied_condition_true(expr->unop);
1814 
1815         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1816                 return implied_not_equal(expr->unop, 1);