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