smatch_buf_size.c

   1 /*
   2  * smatch/smatch_buf_size.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include "parse.h"
  12 #include "smatch.h"
  13 #include "smatch_slist.h"
  14 #include "smatch_extra.h"
  15
  16 struct bound {
  17         int param;
  18         int size;
  19 };
  20
  21 /*
  22  * This check has two smatch IDs.
  23  * my_size_id - used to store the size of arrays.
  24  * my_strlen_id - track the strlen() of buffers.
  25  */
  26 static int my_size_id;
  27 static int my_strlen_id;
  28
  29 static char *alloc_num(long long num)
  30 {
  31         static char buff[256];
  32
  33         if (num == whole_range.min)
  34                 snprintf(buff, 255, "min");
  35         else if (num == whole_range.max)
  36                 snprintf(buff, 255, "max");
  37         else if (num < 0)
  38                 snprintf(buff, 255, "(%lld)", num);
  39         else
  40                 snprintf(buff, 255, "%lld", num);
  41
  42         buff[255] = '\0';
  43         return alloc_sname(buff);
  44 }
  45
  46 static struct smatch_state *alloc_my_state(int val)
  47 {
  48         struct smatch_state *state;
  49
  50         state = __alloc_smatch_state(0);
  51         state->name = alloc_num(val);
  52         state->data = malloc(sizeof(int));
  53         *(int *)state->data = val;
  54         return state;
  55 }
  56
  57 static int get_initializer_size(struct expression *expr)
  58 {
  59         switch(expr->type) {
  60         case EXPR_STRING:
  61                 return expr->string->length;
  62         case EXPR_INITIALIZER: {
  63                 struct expression *tmp;
  64                 int i = 0;
  65                 int max = 0;
  66
  67                 FOR_EACH_PTR(expr->expr_list, tmp) {
  68                         if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
  69                                 max = tmp->idx_to;
  70                         i++;
  71                 } END_FOR_EACH_PTR(tmp);
  72                 if (max)
  73                         return max + 1;
  74                 return i;
  75         }
  76         case EXPR_SYMBOL:
  77                 return get_array_size(expr);
  78         }
  79         return 0;
  80 }
  81
  82 static float get_cast_ratio(struct expression *unstripped)
  83 {
  84         struct expression *start_expr;
  85         struct symbol *start_type;
  86         struct symbol *end_type;
  87         int start_bytes = 0;
  88         int end_bytes = 0;
  89
  90         start_expr = strip_expr(unstripped);
  91         start_type  =  get_type(start_expr);
  92         end_type = get_type(unstripped);
  93         if (!start_type || !end_type)
  94                 return 1;
  95
  96         if (start_type->type == SYM_PTR)
  97                 start_bytes = (get_base_type(start_type))->ctype.alignment;
  98         if (start_type->type == SYM_ARRAY)
  99                 start_bytes = (get_base_type(start_type))->bit_size / 8;
 100         if (end_type->type == SYM_PTR)
 101                 end_bytes = (get_base_type(end_type))->ctype.alignment;
 102         if (end_type->type == SYM_ARRAY)
 103                 end_bytes = (get_base_type(end_type))->bit_size / 8;
 104
 105         if (!start_bytes || !end_bytes)
 106                 return 1;
 107         return start_bytes / end_bytes;
 108 }
 109
 110 int get_array_size(struct expression *expr)
 111 {
 112         struct symbol *tmp;
 113         struct smatch_state *state;
 114         int ret = 0;
 115         float cast_ratio;
 116         long long len;
 117
 118         if (expr->type == EXPR_STRING)
 119                 return expr->string->length;
 120
 121         cast_ratio = get_cast_ratio(expr);
 122         expr = strip_expr(expr);
 123         tmp = get_type(expr);
 124         if (!tmp)
 125                 return 0;
 126
 127         if (tmp->type == SYM_ARRAY) {
 128                 ret = get_expression_value(tmp->array_size);
 129                 if (ret == 1)
 130                         return 0;
 131                 if (ret)
 132                         return ret * cast_ratio;
 133         }
 134
 135         state = get_state_expr(my_size_id, expr);
 136         if (state == &merged)
 137                 return 0;
 138         if (state && state->data) {
 139                 if (tmp->type == SYM_PTR)
 140                         tmp = get_base_type(tmp);
 141                 if (!tmp->ctype.alignment)
 142                         return 0;
 143                 ret = *(int *)state->data / tmp->ctype.alignment;
 144                 return ret * cast_ratio;
 145         }
 146
 147         if (expr->type == EXPR_SYMBOL && expr->symbol->initializer) {
 148                 if (expr->symbol->initializer != expr) /* int a = a; */
 149                         return get_initializer_size(expr->symbol->initializer) * cast_ratio;
 150         }
 151
 152         state = get_state_expr(my_strlen_id, expr);
 153         if (!state || !state->data)
 154                 return 0;
 155         if (get_implied_max((struct expression *)state->data, &len))
 156                 return len + 1; /* add one because strlen doesn't include the NULL */
 157         return 0;
 158 }
 159
 160 int get_array_size_bytes(struct expression *expr)
 161 {
 162         struct symbol *tmp;
 163         int array_size;
 164         int element_size;
 165
 166         if (expr->type == EXPR_STRING)
 167                 return expr->string->length;
 168
 169         tmp = get_type(expr);
 170         if (!tmp)
 171                 return 0;
 172
 173         if (tmp->type == SYM_ARRAY) {
 174                 tmp = get_base_type(tmp);
 175                 element_size = tmp->bit_size / 8;
 176         } else if (tmp->type == SYM_PTR) {
 177                 tmp = get_base_type(tmp);
 178                 element_size = tmp->ctype.alignment;
 179         } else {
 180                 return 0;
 181         }
 182         array_size = get_array_size(expr);
 183         return array_size * element_size;
 184 }
 185
 186 static void match_strlen_condition(struct expression *expr)
 187 {
 188         struct expression *left;
 189         struct expression *right;
 190         struct expression *str;
 191         int strlen_left = 0;
 192         int strlen_right = 0;
 193         long long val;
 194         struct smatch_state *true_state = NULL;
 195         struct smatch_state *false_state = NULL;
 196
 197         if (expr->type != EXPR_COMPARE)
 198                 return;
 199         left = strip_expr(expr->left);
 200         right = strip_expr(expr->right);
 201
 202         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 203                 str = get_argument_from_call_expr(left->args, 0);
 204                 strlen_left = 1;
 205         }
 206         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 207                 str = get_argument_from_call_expr(right->args, 0);
 208                 strlen_right = 1;
 209         }
 210
 211         if (!strlen_left && !strlen_right)
 212                 return;
 213         if (strlen_left && strlen_right)
 214                 return;
 215
 216         if (strlen_left) {
 217                 if (!get_value(right, &val))
 218                         return;
 219         }
 220         if (strlen_right) {
 221                 if (!get_value(left, &val))
 222                         return;
 223         }
 224
 225         if (expr->op == SPECIAL_EQUAL) {
 226                 set_true_false_states_expr(my_size_id, str, alloc_my_state(val + 1), NULL);
 227                 return;
 228         }
 229         if (expr->op == SPECIAL_NOTEQUAL) {
 230                 set_true_false_states_expr(my_size_id, str, NULL, alloc_my_state(val + 1));
 231                 return;
 232         }
 233
 234         switch (expr->op) {
 235         case '<':
 236         case SPECIAL_UNSIGNED_LT:
 237                 if (strlen_left)
 238                         true_state = alloc_my_state(val);
 239                 else
 240                         false_state = alloc_my_state(val + 1);
 241                 break;
 242         case SPECIAL_LTE:
 243         case SPECIAL_UNSIGNED_LTE:
 244                 if (strlen_left)
 245                         true_state = alloc_my_state(val + 1);
 246                 else
 247                         false_state = alloc_my_state(val);
 248                 break;
 249         case SPECIAL_GTE:
 250         case SPECIAL_UNSIGNED_GTE:
 251                 if (strlen_left)
 252                         false_state = alloc_my_state(val);
 253                 else
 254                         true_state = alloc_my_state(val + 1);
 255                 break;
 256         case '>':
 257         case SPECIAL_UNSIGNED_GT:
 258                 if (strlen_left)
 259                         false_state = alloc_my_state(val + 1);
 260                 else
 261                         true_state = alloc_my_state(val);
 262                 break;
 263         }
 264         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 265 }
 266
 267 static struct expression *strip_ampersands(struct expression *expr)
 268 {
 269         struct symbol *type;
 270
 271         if (expr->type != EXPR_PREOP)
 272                 return expr;
 273         if (expr->op != '&')
 274                 return expr;
 275         type = get_type(expr->unop);
 276         if (!type || type->type != SYM_ARRAY)
 277                 return expr;
 278         return expr->unop;
 279 }
 280
 281 static void match_array_assignment(struct expression *expr)
 282 {
 283         struct expression *left;
 284         struct expression *right;
 285         int array_size;
 286
 287         if (expr->op != '=')
 288                 return;
 289         left = strip_expr(expr->left);
 290         right = strip_expr(expr->right);
 291         right = strip_ampersands(right);
 292         array_size = get_array_size_bytes(right);
 293         if (array_size)
 294                 set_state_expr(my_size_id, left, alloc_my_state(array_size));
 295 }
 296
 297 static void match_malloc(const char *fn, struct expression *expr, void *unused)
 298 {
 299         struct expression *right;
 300         struct expression *arg;
 301         long long bytes;
 302
 303         right = strip_expr(expr->right);
 304         arg = get_argument_from_call_expr(right->args, 0);
 305         if (!get_implied_value(arg, &bytes))
 306                 return;
 307         set_state_expr(my_size_id, expr->left, alloc_my_state(bytes));
 308 }
 309
 310 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 311 {
 312         struct expression *right;
 313         struct expression *arg;
 314         long long elements;
 315         long long size;
 316
 317         right = strip_expr(expr->right);
 318         arg = get_argument_from_call_expr(right->args, 0);
 319         if (!get_implied_value(arg, &elements))
 320                 return;
 321         arg = get_argument_from_call_expr(right->args, 1);
 322         if (!get_implied_value(arg, &size))
 323                 return;
 324         set_state_expr(my_size_id, expr->left, alloc_my_state(elements * size));
 325 }
 326
 327 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 328 {
 329         struct expression *right;
 330         struct expression *str;
 331         struct expression *len_expr;
 332         char *len_name;
 333         struct smatch_state *state;
 334
 335         right = strip_expr(expr->right);
 336         str = get_argument_from_call_expr(right->args, 0);
 337         len_expr = strip_expr(expr->left);
 338
 339         len_name = get_variable_from_expr(len_expr, NULL);
 340         if (!len_name)
 341                 return;
 342
 343         state = __alloc_smatch_state(0);
 344         state->name = len_name;
 345         state->data = len_expr;
 346         set_state_expr(my_strlen_id, str, state);
 347 }
 348
 349 void register_buf_size(int id)
 350 {
 351         my_size_id = id;
 352         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 353         add_hook(&match_strlen_condition, CONDITION_HOOK);
 354         add_function_assign_hook("malloc", &match_malloc, NULL);
 355         add_function_assign_hook("calloc", &match_calloc, NULL);
 356         add_function_assign_hook("strlen", &match_strlen, NULL);
 357         if (option_project == PROJ_KERNEL) {
 358                 add_function_assign_hook("kmalloc", &match_malloc, NULL);
 359                 add_function_assign_hook("kzalloc", &match_malloc, NULL);
 360                 add_function_assign_hook("vmalloc", &match_malloc, NULL);
 361                 add_function_assign_hook("__vmalloc", &match_malloc, NULL);
 362                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 363                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 364                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 365         }
 366 }
 367
 368 void register_strlen(int id)
 369 {
 370         my_strlen_id = id;
 371 }