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))
  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_sval(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_sval *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 left_min, left_max, right_min, right_max;
  79
  80         if (expr->op != '=') {
  81                 set_state_expr(my_id, expr->left, &undefined);
  82                 return;
  83         }
  84
  85         left_type = get_type(expr->left);
  86         if (!left_type)
  87                 return;
  88         left_min = sval_type_min(left_type);
  89         left_max = sval_type_max(left_type);
  90
  91         get_absolute_min_sval(expr->right, &right_min);
  92         get_absolute_max_sval(expr->right, &right_max);
  93
  94         /* handle wrapping.  sort of sloppy */
  95         if (sval_cmp(left_max, right_max) < 0)
  96                 right_min = left_min;
  97         if (sval_cmp(left_min, right_min) > 0)
  98                 right_max = left_max;
  99
 100         if (sval_cmp(right_min, sval_type_min(left_type)) <= 0 && sval_cmp(right_max, sval_type_max(left_type)) >= 0)
 101                 set_state_expr(my_id, expr->left, &undefined);
 102         else
 103                 set_state_expr(my_id, expr->left, alloc_absolute(right_min, right_max));
 104 }
 105
 106 static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state)
 107 {
 108         struct data_range_sval *range;
 109
 110         if (!state->data)
 111                 return;
 112         range = state->data;
 113         if (sval_is_min(range->min) && sval_is_max(range->max))
 114                 return;
 115         sm_msg("info: passes absolute_limits '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static);
 116 }
 117
 118 static void match_call_info(struct expression *expr)
 119 {
 120         struct expression *arg;
 121         char *name;
 122         int i;
 123
 124         name = get_fnptr_name(expr->fn);
 125         if (!name)
 126                 return;
 127
 128         i = -1;
 129         FOR_EACH_PTR(expr->args, arg) {
 130                 sval_t min, max;
 131
 132                 i++;
 133
 134                 if (!get_absolute_min_sval(arg, &min))
 135                         continue;
 136                 if (!get_absolute_max_sval(arg, &max))
 137                         continue;
 138                 if (sval_is_min(min) && sval_is_max(max))
 139                         continue;
 140
 141                 /* fixme: determine the type of the paramter */
 142                 sm_msg("info: passes absolute_limits '%s' %d '$$' %s %s",
 143                        name, i, show_range(min, max),
 144                        is_static(expr->fn) ? "static" : "global");
 145         } END_FOR_EACH_PTR(arg);
 146
 147         free_string(name);
 148 }
 149
 150 static void set_param_limits(const char *name, struct symbol *sym, char *key, char *value)
 151 {
 152         struct range_list_sval *rl = NULL;
 153         sval_t min, max;
 154         char fullname[256];
 155
 156         if (strncmp(key, "$$", 2))
 157                 return;
 158
 159         snprintf(fullname, 256, "%s%s", name, key + 2);
 160         get_value_ranges_sval(value, &rl);
 161         min = rl_min_sval(rl);
 162         max = rl_max_sval(rl);
 163         set_state(my_id, fullname, sym, alloc_absolute(min, max));
 164 }
 165
 166 int get_absolute_min_helper(struct expression *expr, sval_t *sval)
 167 {
 168         struct smatch_state *state;
 169         struct data_range_sval *range;
 170
 171         if (get_implied_value_sval(expr, sval))
 172                 return 1;
 173
 174         state = get_state_expr(my_id, expr);
 175         if (!state || !state->data)
 176                 return 0;
 177
 178         range = state->data;
 179         *sval = range->min;
 180         return 1;
 181 }
 182
 183 int get_absolute_max_helper(struct expression *expr, sval_t *sval)
 184 {
 185         struct smatch_state *state;
 186         struct data_range_sval *range;
 187
 188         if (get_implied_value_sval(expr, sval))
 189                 return 1;
 190
 191         state = get_state_expr(my_id, expr);
 192         if (!state || !state->data)
 193                 return 0;
 194
 195         range = state->data;
 196         *sval = range->max;
 197         return 1;
 198 }
 199
 200 void register_absolute(int id)
 201 {
 202         my_id = id;
 203
 204         add_merge_hook(my_id, &merge_func);
 205         add_hook(&match_assign, ASSIGNMENT_HOOK);
 206         if (option_info) {
 207                 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 208                 add_member_info_callback(my_id, struct_member_callback);
 209         }
 210         add_definition_db_callback(set_param_limits, ABSOLUTE_LIMITS);
 211 }
 212
 213 void register_absolute_late(int id)
 214 {
 215         add_modification_hook(my_id, reset_state);
 216 }