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 /*
  17  * This check has two smatch IDs.
  18  * my_size_id - used to store the size of arrays.
  19  * my_strlen_id - track the strlen() of buffers.
  20  */
  21
  22 static int my_size_id;
  23 static int my_strlen_id;
  24
  25 struct limiter {
  26         int buf_arg;
  27         int limit_arg;
  28 };
  29 static struct limiter b0_l2 = {0, 2};
  30
  31 static int get_initializer_size(struct expression *expr)
  32 {
  33         switch (expr->type) {
  34         case EXPR_STRING:
  35                 return expr->string->length;
  36         case EXPR_INITIALIZER: {
  37                 struct expression *tmp;
  38                 int i = 0;
  39                 int max = 0;
  40
  41                 FOR_EACH_PTR(expr->expr_list, tmp) {
  42                         if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
  43                                 max = tmp->idx_to;
  44                         i++;
  45                 } END_FOR_EACH_PTR(tmp);
  46                 if (max)
  47                         return max + 1;
  48                 return i;
  49         }
  50         case EXPR_SYMBOL:
  51                 return get_array_size(expr);
  52         }
  53         return 0;
  54 }
  55
  56 static float get_cast_ratio(struct expression *unstripped)
  57 {
  58         struct expression *start_expr;
  59         struct symbol *start_type;
  60         struct symbol *end_type;
  61         int start_bytes = 0;
  62         int end_bytes = 0;
  63
  64         start_expr = strip_expr(unstripped);
  65         start_type  =  get_type(start_expr);
  66         end_type = get_type(unstripped);
  67         if (!start_type || !end_type)
  68                 return 1;
  69
  70         if (start_type->type == SYM_PTR)
  71                 start_bytes = (get_base_type(start_type))->ctype.alignment;
  72         if (start_type->type == SYM_ARRAY)
  73                 start_bytes = (get_base_type(start_type))->bit_size / 8;
  74         if (end_type->type == SYM_PTR)
  75                 end_bytes = (get_base_type(end_type))->ctype.alignment;
  76         if (end_type->type == SYM_ARRAY)
  77                 end_bytes = (get_base_type(end_type))->bit_size / 8;
  78
  79         if (!start_bytes || !end_bytes)
  80                 return 1;
  81         return start_bytes / end_bytes;
  82 }
  83
  84 int get_array_size(struct expression *expr)
  85 {
  86         struct symbol *tmp;
  87         struct smatch_state *state;
  88         int ret = 0;
  89         float cast_ratio;
  90         long long len;
  91
  92         if (expr->type == EXPR_STRING)
  93                 return expr->string->length;
  94
  95         cast_ratio = get_cast_ratio(expr);
  96         expr = strip_expr(expr);
  97         tmp = get_type(expr);
  98         if (!tmp)
  99                 return 0;
 100
 101         if (tmp->type == SYM_ARRAY) {
 102                 ret = get_expression_value(tmp->array_size);
 103                 /* Dynamically sized array are -1 in sparse */
 104                 if (ret < 0)
 105                         return 0;
 106                 /* People put one element arrays on the end of structs */
 107                 if (ret == 1)
 108                         return 0;
 109                 if (ret)
 110                         return ret * cast_ratio;
 111         }
 112
 113         state = get_state_expr(my_size_id, expr);
 114         if (state == &merged)
 115                 return 0;
 116         if (state && state->data) {
 117                 if (tmp->type == SYM_PTR)
 118                         tmp = get_base_type(tmp);
 119                 if (!tmp->ctype.alignment)
 120                         return 0;
 121                 ret = (int)state->data / tmp->ctype.alignment;
 122                 return ret * cast_ratio;
 123         }
 124
 125         if (expr->type == EXPR_SYMBOL && expr->symbol->initializer) {
 126                 if (expr->symbol->initializer != expr) /* int a = a; */
 127                         return get_initializer_size(expr->symbol->initializer) * cast_ratio;
 128         }
 129
 130         state = get_state_expr(my_strlen_id, expr);
 131         if (!state || !state->data)
 132                 return 0;
 133         if (get_implied_max((struct expression *)state->data, &len))
 134                 return len + 1; /* add one because strlen doesn't include the NULL */
 135         return 0;
 136 }
 137
 138 int get_array_size_bytes(struct expression *expr)
 139 {
 140         struct symbol *tmp;
 141         int array_size;
 142         int element_size;
 143
 144         if (expr->type == EXPR_STRING)
 145                 return expr->string->length;
 146
 147         tmp = get_type(expr);
 148         if (!tmp)
 149                 return 0;
 150
 151         if (tmp->type == SYM_ARRAY) {
 152                 tmp = get_base_type(tmp);
 153                 element_size = tmp->bit_size / 8;
 154         } else if (tmp->type == SYM_PTR) {
 155                 tmp = get_base_type(tmp);
 156                 element_size = tmp->ctype.alignment;
 157         } else {
 158                 return 0;
 159         }
 160         array_size = get_array_size(expr);
 161         return array_size * element_size;
 162 }
 163
 164 static void match_strlen_condition(struct expression *expr)
 165 {
 166         struct expression *left;
 167         struct expression *right;
 168         struct expression *str;
 169         int strlen_left = 0;
 170         int strlen_right = 0;
 171         long long val;
 172         struct smatch_state *true_state = NULL;
 173         struct smatch_state *false_state = NULL;
 174
 175         if (expr->type != EXPR_COMPARE)
 176                 return;
 177         left = strip_expr(expr->left);
 178         right = strip_expr(expr->right);
 179
 180         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 181                 str = get_argument_from_call_expr(left->args, 0);
 182                 strlen_left = 1;
 183         }
 184         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 185                 str = get_argument_from_call_expr(right->args, 0);
 186                 strlen_right = 1;
 187         }
 188
 189         if (!strlen_left && !strlen_right)
 190                 return;
 191         if (strlen_left && strlen_right)
 192                 return;
 193
 194         if (strlen_left) {
 195                 if (!get_value(right, &val))
 196                         return;
 197         }
 198         if (strlen_right) {
 199                 if (!get_value(left, &val))
 200                         return;
 201         }
 202
 203         if (expr->op == SPECIAL_EQUAL) {
 204                 set_true_false_states_expr(my_size_id, str, alloc_state_num(val + 1), NULL);
 205                 return;
 206         }
 207         if (expr->op == SPECIAL_NOTEQUAL) {
 208                 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(val + 1));
 209                 return;
 210         }
 211
 212         switch (expr->op) {
 213         case '<':
 214         case SPECIAL_UNSIGNED_LT:
 215                 if (strlen_left)
 216                         true_state = alloc_state_num(val);
 217                 else
 218                         false_state = alloc_state_num(val + 1);
 219                 break;
 220         case SPECIAL_LTE:
 221         case SPECIAL_UNSIGNED_LTE:
 222                 if (strlen_left)
 223                         true_state = alloc_state_num(val + 1);
 224                 else
 225                         false_state = alloc_state_num(val);
 226                 break;
 227         case SPECIAL_GTE:
 228         case SPECIAL_UNSIGNED_GTE:
 229                 if (strlen_left)
 230                         false_state = alloc_state_num(val);
 231                 else
 232                         true_state = alloc_state_num(val + 1);
 233                 break;
 234         case '>':
 235         case SPECIAL_UNSIGNED_GT:
 236                 if (strlen_left)
 237                         false_state = alloc_state_num(val + 1);
 238                 else
 239                         true_state = alloc_state_num(val);
 240                 break;
 241         }
 242         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 243 }
 244
 245 static struct expression *strip_ampersands(struct expression *expr)
 246 {
 247         struct symbol *type;
 248
 249         if (expr->type != EXPR_PREOP)
 250                 return expr;
 251         if (expr->op != '&')
 252                 return expr;
 253         type = get_type(expr->unop);
 254         if (!type || type->type != SYM_ARRAY)
 255                 return expr;
 256         return expr->unop;
 257 }
 258
 259 static void match_array_assignment(struct expression *expr)
 260 {
 261         struct expression *left;
 262         struct expression *right;
 263         int array_size;
 264
 265         if (expr->op != '=')
 266                 return;
 267         left = strip_expr(expr->left);
 268         right = strip_expr(expr->right);
 269         right = strip_ampersands(right);
 270         array_size = get_array_size_bytes(right);
 271         if (array_size)
 272                 set_state_expr(my_size_id, left, alloc_state_num(array_size));
 273 }
 274
 275 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 276 {
 277         int size_arg = (int)_size_arg;
 278         struct expression *right;
 279         struct expression *arg;
 280         long long bytes;
 281
 282         right = strip_expr(expr->right);
 283         arg = get_argument_from_call_expr(right->args, size_arg);
 284         if (!get_implied_value(arg, &bytes))
 285                 return;
 286         set_state_expr(my_size_id, expr->left, alloc_state_num(bytes));
 287 }
 288
 289 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 290 {
 291         struct expression *right;
 292         struct expression *arg;
 293         long long elements;
 294         long long size;
 295
 296         right = strip_expr(expr->right);
 297         arg = get_argument_from_call_expr(right->args, 0);
 298         if (!get_implied_value(arg, &elements))
 299                 return;
 300         arg = get_argument_from_call_expr(right->args, 1);
 301         if (!get_implied_value(arg, &size))
 302                 return;
 303         set_state_expr(my_size_id, expr->left, alloc_state_num(elements * size));
 304 }
 305
 306 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 307 {
 308         struct expression *right;
 309         struct expression *str;
 310         struct expression *len_expr;
 311         char *len_name;
 312         struct smatch_state *state;
 313
 314         right = strip_expr(expr->right);
 315         str = get_argument_from_call_expr(right->args, 0);
 316         len_expr = strip_expr(expr->left);
 317
 318         len_name = get_variable_from_expr(len_expr, NULL);
 319         if (!len_name)
 320                 return;
 321
 322         state = __alloc_smatch_state(0);
 323         state->name = len_name;
 324         state->data = len_expr;
 325         set_state_expr(my_strlen_id, str, state);
 326 }
 327
 328 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 329 {
 330         struct limiter *limiter = (struct limiter *)_limiter;
 331         struct expression *dest;
 332         struct expression *size_expr;
 333         long long size;
 334
 335         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 336         size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 337         if (!get_implied_max(size_expr, &size))
 338                 return;
 339         set_state_expr(my_size_id, dest, alloc_state_num(size));
 340 }
 341
 342 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 343 {
 344         struct expression fake_assign;
 345
 346         fake_assign.op = '=';
 347         fake_assign.left = get_argument_from_call_expr(expr->args, 0);
 348         fake_assign.right = get_argument_from_call_expr(expr->args, 1);
 349         match_array_assignment(&fake_assign);
 350 }
 351
 352 static void match_strndup(const char *fn, struct expression *expr, void *unused)
 353 {
 354         struct expression *fn_expr;
 355         struct expression *size_expr;
 356         long long size;
 357
 358         fn_expr = strip_expr(expr->right);
 359         size_expr = get_argument_from_call_expr(fn_expr->args, 1);
 360         if (!get_implied_max(size_expr, &size))
 361                 return;
 362
 363         /* It's easy to forget space for the NUL char */
 364         size++;
 365         set_state_expr(my_size_id, expr->left, alloc_state_num(size));
 366 }
 367
 368 void register_buf_size(int id)
 369 {
 370         my_size_id = id;
 371
 372         add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
 373         add_function_assign_hook("calloc", &match_calloc, NULL);
 374         add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
 375         if (option_project == PROJ_KERNEL) {
 376                 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
 377                 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
 378                 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
 379                 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
 380                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 381                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 382                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 383                 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
 384                 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
 385         }
 386         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 387         add_hook(&match_strlen_condition, CONDITION_HOOK);
 388         add_function_assign_hook("strlen", &match_strlen, NULL);
 389
 390         add_function_hook("strncpy", &match_limited, &b0_l2);
 391         add_function_hook("strlcpy", &match_limited, &b0_l2);
 392         add_function_hook("strlcat", &match_limited, &b0_l2);
 393         add_function_hook("memcpy", &match_limited, &b0_l2);
 394         add_function_hook("memscan", &match_limited, &b0_l2);
 395
 396         add_function_hook("strcpy", &match_strcpy, NULL);
 397
 398         add_function_assign_hook("strndup", match_strndup, NULL);
 399         if (option_project == PROJ_KERNEL)
 400                 add_function_assign_hook("kstrndup", match_strndup, NULL);
 401 }
 402
 403 void register_strlen(int id)
 404 {
 405         my_strlen_id = id;
 406 }