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 int absolute_id;
  21
  22 static char *show_num(long long num)
  23 {
  24         static char buf[64];
  25
  26         if (num < 0)
  27                 sprintf(buf, "(%lld)", num);
  28         else
  29                 sprintf(buf, "%lld", num);
  30         return buf;
  31 }
  32
  33 static char *show_range(long long min, long long max)
  34 {
  35         static char buf[256];
  36         char *p = buf;
  37
  38         if (min == whole_range.min)
  39                 p += sprintf(p, "min");
  40         else if (min == whole_range.max)
  41                 p += sprintf(p, "max");
  42         else
  43                 p += sprintf(p, "%s", show_num(min));
  44         if (min != max) {
  45                 if (max == whole_range.max)
  46                         sprintf(p, "-max");
  47                 else
  48                         sprintf(p, "-%s", show_num(max));
  49         }
  50         return buf;
  51
  52 }
  53
  54 static struct smatch_state *alloc_absolute(long long min, long long max)
  55 {
  56         struct smatch_state *state;
  57
  58         if (min == whole_range.min && max == whole_range.max)
  59                 return &undefined;
  60
  61         state = __alloc_smatch_state(0);
  62         state->name = alloc_string(show_range(min, max));
  63         state->data = alloc_range(min, max);
  64         return state;
  65 }
  66
  67 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
  68 {
  69         struct data_range *r1, *r2;
  70         long long min, max;
  71
  72         if (!s1->data || !s2->data)
  73                 return &undefined;
  74
  75         r1 = s1->data;
  76         r2 = s2->data;
  77
  78         if (r1->min == r2->min && r1->max == r2->max)
  79                 return s1;
  80
  81         min = r1->min;
  82         if (r2->min < min)
  83                 min = r2->min;
  84         max = r1->max;
  85         if (r2->max > max)
  86                 max = r2->max;
  87
  88         return alloc_absolute(min, max);
  89 }
  90
  91 static void reset_state(struct sm_state *sm)
  92 {
  93         set_state(absolute_id, sm->name, sm->sym, &undefined);
  94 }
  95
  96 static void match_assign(struct expression *expr)
  97 {
  98         struct symbol *left_type;
  99         sval_t left_min, left_max, right_min, right_max;
 100
 101         if (expr->op != '=') {
 102                 set_state_expr(absolute_id, expr->left, &undefined);
 103                 return;
 104         }
 105
 106         left_type = get_type(expr->left);
 107         if (!left_type)
 108                 return;
 109         left_min = sval_type_min(left_type);
 110         left_max = sval_type_max(left_type);
 111
 112         get_absolute_min_sval(expr->right, &right_min);
 113         get_absolute_max_sval(expr->right, &right_max);
 114
 115         /* handle wrapping.  sort of sloppy */
 116         if (sval_cmp(left_max, right_max) < 0)
 117                 right_min = left_min;
 118         if (sval_cmp(left_min, right_min) > 0)
 119                 right_max = left_max;
 120
 121         if (sval_cmp(right_min, sval_type_min(left_type)) <= 0 && sval_cmp(right_max, sval_type_max(left_type)) >= 0)
 122                 set_state_expr(absolute_id, expr->left, &undefined);
 123         else
 124                 set_state_expr(absolute_id, expr->left, alloc_absolute(sval_to_ll(right_min), sval_to_ll(right_max)));
 125 }
 126
 127 static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state)
 128 {
 129         struct data_range *range;
 130
 131         if (!state->data)
 132                 return;
 133         range = state->data;
 134         if (range->min == whole_range.min && range->max == whole_range.max)
 135                 return;
 136         sm_msg("info: passes absolute_limits '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static);
 137 }
 138
 139 static void match_call_info(struct expression *expr)
 140 {
 141         struct expression *arg;
 142         char *name;
 143         int i;
 144
 145         name = get_fnptr_name(expr->fn);
 146         if (!name)
 147                 return;
 148
 149         i = -1;
 150         FOR_EACH_PTR(expr->args, arg) {
 151                 long long min;
 152                 sval_t max;
 153
 154                 i++;
 155
 156                 if (!get_absolute_min(arg, &min))
 157                         continue;
 158                 if (!get_absolute_max_sval(arg, &max))
 159                         continue;
 160                 if (min == whole_range.min && sval_cmp_val(max, whole_range.max) >= 0)
 161                         continue;
 162
 163                 /* fixme: determine the type of the paramter */
 164                 sm_msg("info: passes absolute_limits '%s' %d '$$' %s %s",
 165                        name, i, show_range(min, sval_to_ll(max)),
 166                        is_static(expr->fn) ? "static" : "global");
 167         } END_FOR_EACH_PTR(arg);
 168
 169         free_string(name);
 170 }
 171
 172 static void set_param_limits(const char *name, struct symbol *sym, char *key, char *value)
 173 {
 174         struct range_list *rl = NULL;
 175         long long min, max;
 176         char fullname[256];
 177
 178         if (strncmp(key, "$$", 2))
 179                 return;
 180
 181         snprintf(fullname, 256, "%s%s", name, key + 2);
 182         get_value_ranges(value, &rl);
 183         min = rl_min(rl);
 184         max = rl_max(rl);
 185         set_state(absolute_id, fullname, sym, alloc_absolute(min, max));
 186 }
 187
 188 void register_absolute(int id)
 189 {
 190         absolute_id = id;
 191
 192         add_merge_hook(absolute_id, &merge_func);
 193         add_hook(&match_assign, ASSIGNMENT_HOOK);
 194         if (option_info) {
 195                 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 196                 add_member_info_callback(absolute_id, struct_member_callback);
 197         }
 198         add_definition_db_callback(set_param_limits, ABSOLUTE_LIMITS);
 199 }
 200
 201 void register_absolute_late(int id)
 202 {
 203         add_modification_hook(absolute_id, reset_state);
 204 }