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 *type;
  99         long long min, max;
 100
 101         if (expr->op != '=') {
 102                 set_state_expr(absolute_id, expr->left, &undefined);
 103                 return;
 104         }
 105
 106         type = get_type(expr->left);
 107         if (!type)
 108                 return;
 109
 110         if (!get_absolute_min(expr->right, &min))
 111                 min = whole_range.min;
 112         if (!get_absolute_max(expr->right, &max))
 113                 max = whole_range.max;
 114
 115         /* handle wrapping.  sort of sloppy */
 116         if (type_max(type) < max)
 117                 min = type_min(type);
 118         if (type_min(type) > min)
 119                 max = type_max(type);
 120
 121         if (min <= type_min(type) && max >= type_max(type))
 122                 set_state_expr(absolute_id, expr->left, &undefined);
 123         else
 124                 set_state_expr(absolute_id, expr->left, alloc_absolute(min, 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 = 0;
 144
 145         name = get_fnptr_name(expr->fn);
 146         if (!name)
 147                 return;
 148
 149         FOR_EACH_PTR(expr->args, arg) {
 150                 long long min, max;
 151
 152                 if (!get_absolute_min(arg, &min))
 153                         continue;
 154                 if (!get_absolute_max(arg, &max))
 155                         continue;
 156                 if (min == whole_range.min && max == whole_range.max)
 157                         continue;
 158
 159                 /* fixme: determine the type of the paramter */
 160                 sm_msg("info: passes absolute_limits '%s' %d '$$' %s %s",
 161                        name, i, show_range(min, max),
 162                        is_static(expr->fn) ? "static" : "global");
 163                 i++;
 164         } END_FOR_EACH_PTR(arg);
 165
 166         free_string(name);
 167 }
 168
 169 static void set_param_limits(const char *name, struct symbol *sym, char *key, char *value)
 170 {
 171         struct range_list *rl = NULL;
 172         long long min, max;
 173         char fullname[256];
 174
 175         if (strncmp(key, "$$", 2))
 176                 return;
 177
 178         snprintf(fullname, 256, "%s%s", name, key + 2);
 179         get_value_ranges(value, &rl);
 180         min = rl_min(rl);
 181         max = rl_max(rl);
 182         set_state(absolute_id, fullname, sym, alloc_absolute(min, max));
 183 }
 184
 185 void register_absolute(int id)
 186 {
 187         absolute_id = id;
 188
 189         add_merge_hook(absolute_id, &merge_func);
 190         add_hook(&match_assign, ASSIGNMENT_HOOK);
 191         if (option_info) {
 192                 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
 193                 add_member_info_callback(absolute_id, struct_member_callback);
 194         }
 195         add_definition_db_callback(set_param_limits, ABSOLUTE_LIMITS);
 196 }
 197
 198 void register_absolute_late(int id)
 199 {
 200         add_modification_hook(absolute_id, reset_state);
 201 }