smatch_absolute.c

   1 /*
   2  * smatch/smatch_absolute.c
   3  *
   4  * Copyright (C) 2012 Oracle.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  * This is to track the absolute max that variables can be.  It's a bit like
   9  * smatch_extra.c but it only tracks the absolute max and min.  So for example,
  10  * if you have "int x = (unsigned char)y;" then the absolute max of x is 255.
  11  *
  12  * I imagine this will be useful for find integer overflows.
  13  *
  14  */
  15
  16 #include "smatch.h"
  17 #include "smatch_slist.h"
  18 #include "smatch_extra.h"
  19
  20 static int my_id;
  21
  22 static const char *show_range(sval_t min, sval_t max)
  23 {
  24         static char buf[256];
  25
  26         if (sval_cmp(min, max) == 0)
  27                 return sval_to_str(min);
  28         snprintf(buf, sizeof(buf), "%s-%s", sval_to_str(min), sval_to_str(max));
  29         return buf;
  30
  31 }
  32
  33 static struct smatch_state *alloc_absolute(sval_t min, sval_t max)
  34 {
  35         struct smatch_state *state;
  36
  37         if (sval_is_min(min) && sval_is_max(max))
  38                 return &undefined;
  39
  40         state = __alloc_smatch_state(0);
  41         state->name = alloc_string(show_range(min, max));
  42         state->data = alloc_range(min, max);
  43         return state;
  44 }
  45
  46 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
  47 {
  48         struct data_range *r1, *r2;
  49         sval_t min, max;
  50
  51         if (!s1->data || !s2->data)
  52                 return &undefined;
  53
  54         r1 = s1->data;
  55         r2 = s2->data;
  56
  57         if (r1->min.value == r2->min.value && r1->max.value == r2->max.value)
  58                 return s1;
  59
  60         min = r1->min;
  61         if (sval_cmp(r2->min, min) < 0)
  62                 min = r2->min;
  63         max = r1->max;
  64         if (sval_cmp(r2->max, max) > 0)
  65                 max = r2->max;
  66
  67         return alloc_absolute(min, max);
  68 }
  69
  70 static void reset_state(struct sm_state *sm)
  71 {
  72         set_state(my_id, sm->name, sm->sym, &undefined);
  73 }
  74
  75 static void match_assign(struct expression *expr)
  76 {
  77         struct symbol *left_type;
  78         sval_t min, max;
  79         struct range_list *rl;
  80
  81         if (expr->op != '=') {
  82                 set_state_expr(my_id, expr->left, &undefined);
  83                 return;
  84         }
  85
  86         left_type = get_type(expr->left);
  87         if (!left_type)
  88                 return;
  89
  90         get_absolute_min(expr->right, &min);
  91         get_absolute_max(expr->right, &max);
  92
  93         rl = alloc_rl(min, max);
  94         rl = cast_rl(left_type, rl);
  95
  96         min = rl_min(rl);
  97         max = rl_max(rl);
  98         set_state_expr(my_id, expr->left, alloc_absolute(min, max));
  99 }
 100
 101 static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state)
 102 {
 103         struct data_range *range;
 104
 105         if (!state->data)
 106                 return;
 107         range = state->data;
 108         if (sval_is_min(range->min) && sval_is_max(range->max))
 109                 return;
 110         sm_msg("info: passes absolute_limits '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static);
 111 }
 112
 113 static void match_call_info(struct expression *expr)
 114 {
 115         struct expression *arg;
 116         char *name;
 117         int i;
 118
 119         name = get_fnptr_name(expr->fn);
 120         if (!name)
 121                 return;
 122
 123         i = -1;
 124         FOR_EACH_PTR(expr->args, arg) {
 125                 sval_t min, max;
 126
 127                 i++;
 128
 129                 if (!get_absolute_min(arg, &min))
 130                         continue;
 131                 if (!get_absolute_max(arg, &max))
 132                         continue;
 133                 if (sval_is_min(min) && sval_is_max(max))
 134                         continue;
 135
 136                 /* fixme: determine the type of the paramter */
 137                 sm_msg("info: passes absolute_limits '%s' %d '$$' %s %s",
 138                        name, i, show_range(min, max),
 139                        is_static(expr->fn) ? "static" : "global");
 140         } END_FOR_EACH_PTR(arg);
 141
 142         free_string(name);
 143 }
 144
 145 static void set_param_limits(const char *name, struct symbol *sym, char *key, char *value)
 146 {
 147         struct range_list *rl = NULL;
 148         sval_t min, max;
 149         char fullname[256];
 150
 151         if (strncmp(key, "$$", 2))
 152                 return;
 153
 154         snprintf(fullname, 256, "%s%s", name, key + 2);
 155         str_to_rl(get_real_base_type(sym), value, &rl);
 156         min = rl_min(rl);
 157         max = rl_max(rl);
 158         set_state(my_id, fullname, sym, alloc_absolute(min, max));
 159 }
 160
 161 int get_absolute_min_helper(struct expression *expr, sval_t *sval)
 162 {
 163         struct smatch_state *state;
 164         struct data_range *range;
 165
 166         if (get_implied_min(expr, sval))
 167                 return 1;
 168
 169         state = get_state_expr(my_id, expr);
 170         if (!state || !state->data)
 171                 return 0;
 172
 173         range = state->data;
 174         *sval = range->min;
 175         return 1;
 176 }
 177
 178 int get_absolute_max_helper(struct expression *expr, sval_t *sval)
 179 {
 180         struct smatch_state *state;
 181         struct data_range *range;
 182
 183         if (get_implied_max(expr, sval))
 184                 return 1;
 185
 186         state = get_state_expr(my_id, expr);
 187         if (!state || !state->data)
 188                 return 0;
 189
 190         range = state->data;
 191         *sval = range->max;
 192         return 1;
 193 }
 194
 195 void register_absolute(int id)
 196 {
 197         my_id = id;
 198
 199         add_merge_hook(my_id, &merge_func);
 200         add_hook(&match_assign, ASSIGNMENT_HOOK);
 201         if (option_info) {
 202                 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 203                 add_member_info_callback(my_id, struct_member_callback);
 204         }
 205         add_definition_db_callback(set_param_limits, ABSOLUTE_LIMITS);
 206 }
 207
 208 void register_absolute_late(int id)
 209 {
 210         add_modification_hook(my_id, reset_state);
 211 }