flow: re-write how struct members are initialized
[smatch.git] / smatch_buf_size.c
blob49e57a2fc78a3d54fdab939982101cdbd126d4c4
1 /*
2 * smatch/smatch_buf_size.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
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"
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.
23 static int my_size_id;
24 static int my_strlen_id;
26 struct limiter {
27 int buf_arg;
28 int limit_arg;
30 static struct limiter b0_l2 = {0, 2};
32 static void set_undefined(struct sm_state *sm, struct expression *mod_expr)
34 if (sm->state != &undefined)
35 set_state(sm->owner, sm->name, sm->sym, &undefined);
38 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
40 if (PTR_INT(s1->data) == PTR_INT(s2->data))
41 return s1;
42 return &undefined;
45 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
47 char fullname[256];
48 unsigned int size;
50 if (strncmp(key, "$$", 2))
51 return;
53 snprintf(fullname, 256, "%s%s", name, key + 2);
55 errno = 0;
56 size = strtoul(value, NULL, 10);
57 if (errno)
58 return;
60 set_state(my_size_id, fullname, sym, alloc_state_num(size));
63 static int bytes_per_element(struct expression *expr)
65 struct symbol *type;
66 int bpe;
68 if (expr->type == EXPR_STRING)
69 return 1;
70 type = get_type(expr);
71 if (!type)
72 return 0;
74 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
75 return 0;
77 type = get_base_type(type);
78 bpe = bits_to_bytes(type->bit_size);
80 if (bpe == -1) /* void pointer */
81 bpe = 1;
83 return bpe;
86 static int bytes_to_elements(struct expression *expr, int bytes)
88 int bpe;
90 bpe = bytes_per_element(expr);
91 if (bpe == 0)
92 return 0;
93 return bytes / bpe;
96 static int elements_to_bytes(struct expression *expr, int elements)
98 int bpe;
100 bpe = bytes_per_element(expr);
101 return elements * bpe;
104 static int get_initializer_size(struct expression *expr)
106 switch (expr->type) {
107 case EXPR_STRING:
108 return expr->string->length;
109 case EXPR_INITIALIZER: {
110 struct expression *tmp;
111 int i = 0;
113 FOR_EACH_PTR(expr->expr_list, tmp) {
114 if (tmp->type == EXPR_INDEX) {
115 if (tmp->idx_to >= i)
116 i = tmp->idx_to;
117 else
118 continue;
121 i++;
122 } END_FOR_EACH_PTR(tmp);
123 return i;
125 case EXPR_SYMBOL:
126 return get_array_size(expr);
128 return 0;
131 static int db_size;
132 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
134 if (db_size == 0)
135 db_size = atoi(argv[0]);
136 else
137 db_size = -1;
138 return 0;
141 static int size_from_db(struct expression *expr)
143 int this_file_only = 0;
144 char *name;
146 if (!option_spammy)
147 return 0;
149 name = get_member_name(expr);
150 if (!name && is_static(expr)) {
151 name = expr_to_var(expr);
152 this_file_only = 1;
154 if (!name)
155 return 0;
157 db_size = 0;
158 run_sql(db_size_callback, "select size from type_size where type = '%s' and file = '%s'",
159 name, get_filename());
160 if (db_size < 0)
161 return 0;
162 if (db_size != 0)
163 return db_size;
164 if (this_file_only)
165 return 0;
167 run_sql(db_size_callback, "select size from type_size where type = '%s'",
168 name);
170 if (db_size < 0)
171 db_size = 0;
173 return db_size;
176 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
178 struct expression *call;
179 sval_t sval;
181 if (expr->type != EXPR_ASSIGNMENT)
182 return;
183 call = strip_expr(expr->right);
185 if (!parse_call_math(call, math, &sval))
186 return;
187 set_state_expr(my_size_id, expr->left, alloc_state_num(sval.value));
190 int get_real_array_size(struct expression *expr)
192 struct symbol *type;
193 sval_t sval;
195 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
196 return 0;
198 type = get_type(expr);
199 if (!type || type->type != SYM_ARRAY)
200 return 0;
202 if (!get_implied_value(type->array_size, &sval))
203 return 0;
205 /* People put one element arrays on the end of structs */
206 if (sval.value == 1)
207 return 0;
209 return sval.value;
212 static int get_size_from_initializer(struct expression *expr)
214 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
215 return 0;
216 if (expr->symbol->initializer == expr) /* int a = a; */
217 return 0;
218 return get_initializer_size(expr->symbol->initializer);
221 static int get_stored_size_bytes(struct expression *expr)
223 struct smatch_state *state;
225 state = get_state_expr(my_size_id, expr);
226 if (!state)
227 return 0;
228 return PTR_INT(state->data);
231 static int get_stored_size_bytes_min(struct expression *expr)
233 struct sm_state *sm, *tmp;
234 int min = 0;
236 sm = get_sm_state_expr(my_size_id, expr);
237 if (!sm)
238 return 0;
239 FOR_EACH_PTR(sm->possible, tmp) {
240 if (PTR_INT(tmp->state->data) <= 0)
241 continue;
242 if (PTR_INT(tmp->state->data) < min)
243 min = PTR_INT(tmp->state->data);
244 } END_FOR_EACH_PTR(tmp);
246 return min;
249 static int get_bytes_from_address(struct expression *expr)
251 struct symbol *type;
252 int ret;
254 if (!option_spammy)
255 return 0;
256 if (expr->type != EXPR_PREOP || expr->op != '&')
257 return 0;
258 type = get_type(expr);
259 if (!type)
260 return 0;
262 if (type->type == SYM_PTR)
263 type = get_base_type(type);
265 ret = bits_to_bytes(type->bit_size);
266 if (ret == -1)
267 return 0;
268 if (ret == 1)
269 return 0; /* ignore char pointers */
271 return ret;
274 static int get_size_from_strlen(struct expression *expr)
276 struct smatch_state *state;
277 sval_t len;
279 state = get_state_expr(my_strlen_id, expr);
280 if (!state || !state->data)
281 return 0;
282 if (!get_implied_max((struct expression *)state->data, &len))
283 return 0;
284 if (sval_is_max(len))
285 return 0;
286 if (len.uvalue > INT_MAX - 1 || len.value < 0)
287 return 0;
288 return len.value + 1; /* add one because strlen doesn't include the NULL */
291 static struct expression *remove_addr_fluff(struct expression *expr)
293 struct expression *tmp;
294 sval_t sval;
296 expr = strip_expr(expr);
298 /* remove '&' and '*' operations that cancel */
299 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
300 tmp = strip_expr(expr->unop);
301 if (tmp->type != EXPR_PREOP)
302 break;
303 if (tmp->op != '*')
304 break;
305 expr = strip_expr(tmp->unop);
308 if (!expr)
309 return NULL;
311 /* "foo + 0" is just "foo" */
312 if (expr->type == EXPR_BINOP && expr->op == '+' &&
313 get_value(expr->right, &sval) && sval.value == 0)
314 return expr->left;
316 return expr;
319 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
321 struct symbol *tmp;
322 int i;
324 i = 0;
325 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
326 if (i++ || !tmp->ident)
327 return 0;
328 if (tmp->ident == member)
329 return 1;
330 return 0;
331 } END_FOR_EACH_PTR_REVERSE(tmp);
333 return 0;
336 static int get_stored_size_end_struct_bytes(struct expression *expr)
338 struct symbol *type;
339 char *name;
340 struct symbol *sym;
341 struct smatch_state *state;
342 sval_t sval;
344 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
345 return 0;
347 type = get_type(expr);
348 if (!type || type->type != SYM_ARRAY)
349 return 0;
351 if (!get_implied_value(type->array_size, &sval))
352 return 0;
354 if (sval.value != 0 && sval.value != 1)
355 return 0;
357 name = expr_to_var_sym(expr, &sym);
358 free_string(name);
359 if (!sym || !sym->ident || !sym->ident->name)
360 return 0;
361 if (!sym->bit_size)
362 return 0;
364 if (sym->type != SYM_NODE)
365 return 0;
367 state = get_state(my_size_id, sym->ident->name, sym);
368 if (!state || !state->data)
369 return 0;
371 sym = get_real_base_type(sym);
372 if (!sym || sym->type != SYM_PTR)
373 return 0;
374 sym = get_real_base_type(sym);
375 if (!sym || sym->type != SYM_STRUCT)
376 return 0;
377 if (!is_last_member_of_struct(sym, expr->member))
378 return 0;
380 return PTR_INT(state->data) - bits_to_bytes(sym->bit_size) +
381 bits_to_bytes(type->bit_size);
384 int get_array_size_bytes(struct expression *expr)
386 int size;
388 expr = remove_addr_fluff(expr);
389 if (!expr)
390 return 0;
392 /* strcpy(foo, "BAR"); */
393 if (expr->type == EXPR_STRING)
394 return expr->string->length;
396 /* buf[4] */
397 size = get_real_array_size(expr);
398 if (size)
399 return elements_to_bytes(expr, size);
401 /* buf = malloc(1024); */
402 size = get_stored_size_bytes(expr);
403 if (size)
404 return size;
406 size = get_stored_size_end_struct_bytes(expr);
407 if (size)
408 return size;
410 /* char *foo = "BAR" */
411 size = get_size_from_initializer(expr);
412 if (size)
413 return elements_to_bytes(expr, size);
415 size = get_bytes_from_address(expr);
416 if (size)
417 return size;
419 /* if (strlen(foo) > 4) */
420 size = get_size_from_strlen(expr);
421 if (size)
422 return size;
424 return size_from_db(expr);
427 int get_array_size_bytes_min(struct expression *expr)
429 int size;
430 int tmp;
432 size = get_array_size_bytes(expr);
434 tmp = get_stored_size_bytes_min(expr);
435 if (size <= 0 || (tmp >= 1 && tmp < size))
436 size = tmp;
437 return size;
440 int get_array_size(struct expression *expr)
442 int bytes;
444 bytes = get_array_size_bytes(expr);
445 return bytes_to_elements(expr, bytes);
448 static void match_strlen_condition(struct expression *expr)
450 struct expression *left;
451 struct expression *right;
452 struct expression *str = NULL;
453 int strlen_left = 0;
454 int strlen_right = 0;
455 sval_t sval;
456 struct smatch_state *true_state = NULL;
457 struct smatch_state *false_state = NULL;
459 if (expr->type != EXPR_COMPARE)
460 return;
461 left = strip_expr(expr->left);
462 right = strip_expr(expr->right);
464 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
465 str = get_argument_from_call_expr(left->args, 0);
466 strlen_left = 1;
468 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
469 str = get_argument_from_call_expr(right->args, 0);
470 strlen_right = 1;
473 if (!strlen_left && !strlen_right)
474 return;
475 if (strlen_left && strlen_right)
476 return;
478 if (strlen_left) {
479 if (!get_value(right, &sval))
480 return;
482 if (strlen_right) {
483 if (!get_value(left, &sval))
484 return;
487 if (expr->op == SPECIAL_EQUAL) {
488 set_true_false_states_expr(my_size_id, str, alloc_state_num(sval.value + 1), NULL);
489 return;
491 if (expr->op == SPECIAL_NOTEQUAL) {
492 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(sval.value + 1));
493 return;
496 switch (expr->op) {
497 case '<':
498 case SPECIAL_UNSIGNED_LT:
499 if (strlen_left)
500 true_state = alloc_state_num(sval.value);
501 else
502 false_state = alloc_state_num(sval.value + 1);
503 break;
504 case SPECIAL_LTE:
505 case SPECIAL_UNSIGNED_LTE:
506 if (strlen_left)
507 true_state = alloc_state_num(sval.value + 1);
508 else
509 false_state = alloc_state_num(sval.value);
510 break;
511 case SPECIAL_GTE:
512 case SPECIAL_UNSIGNED_GTE:
513 if (strlen_left)
514 false_state = alloc_state_num(sval.value);
515 else
516 true_state = alloc_state_num(sval.value + 1);
517 break;
518 case '>':
519 case SPECIAL_UNSIGNED_GT:
520 if (strlen_left)
521 false_state = alloc_state_num(sval.value + 1);
522 else
523 true_state = alloc_state_num(sval.value);
524 break;
526 set_true_false_states_expr(my_size_id, str, true_state, false_state);
529 static struct expression *strip_ampersands(struct expression *expr)
531 struct symbol *type;
533 if (expr->type != EXPR_PREOP)
534 return expr;
535 if (expr->op != '&')
536 return expr;
537 type = get_type(expr->unop);
538 if (!type || type->type != SYM_ARRAY)
539 return expr;
540 return expr->unop;
543 static void match_array_assignment(struct expression *expr)
545 struct expression *left;
546 struct expression *right;
547 int array_size;
549 if (expr->op != '=')
550 return;
551 left = strip_expr(expr->left);
552 right = strip_expr(expr->right);
553 right = strip_ampersands(right);
554 array_size = get_array_size_bytes(right);
555 if (array_size)
556 set_state_expr(my_size_id, left, alloc_state_num(array_size));
559 static void info_record_alloction(struct expression *buffer, struct expression *size)
561 char *name;
562 sval_t sval;
564 if (!option_info)
565 return;
567 name = get_member_name(buffer);
568 if (!name && is_static(buffer))
569 name = expr_to_var(buffer);
570 if (!name)
571 return;
572 if (get_implied_value(size, &sval))
573 sql_insert_type_size(name, sval.value);
574 else
575 sql_insert_type_size(name, -1);
577 free_string(name);
580 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
582 int size_arg = PTR_INT(_size_arg);
583 struct expression *right;
584 struct expression *arg;
585 sval_t bytes;
587 right = strip_expr(expr->right);
588 arg = get_argument_from_call_expr(right->args, size_arg);
590 info_record_alloction(expr->left, arg);
592 if (!get_implied_value(arg, &bytes))
593 return;
594 set_state_expr(my_size_id, expr->left, alloc_state_num(bytes.value));
597 static void match_calloc(const char *fn, struct expression *expr, void *unused)
599 struct expression *right;
600 struct expression *arg;
601 sval_t elements;
602 sval_t size;
604 right = strip_expr(expr->right);
605 arg = get_argument_from_call_expr(right->args, 0);
606 if (!get_implied_value(arg, &elements))
607 return;
608 arg = get_argument_from_call_expr(right->args, 1);
609 if (!get_implied_value(arg, &size))
610 return;
611 set_state_expr(my_size_id, expr->left, alloc_state_num(elements.value * size.value));
614 static void match_strlen(const char *fn, struct expression *expr, void *unused)
616 struct expression *right;
617 struct expression *str;
618 struct expression *len_expr;
619 char *len_name;
620 struct smatch_state *state;
622 right = strip_expr(expr->right);
623 str = get_argument_from_call_expr(right->args, 0);
624 len_expr = strip_expr(expr->left);
626 len_name = expr_to_var(len_expr);
627 if (!len_name)
628 return;
630 state = __alloc_smatch_state(0);
631 state->name = len_name;
632 state->data = len_expr;
633 set_state_expr(my_strlen_id, str, state);
636 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
638 struct limiter *limiter = (struct limiter *)_limiter;
639 struct expression *dest;
640 struct expression *size_expr;
641 sval_t size;
643 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
644 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
645 if (!get_implied_max(size_expr, &size))
646 return;
647 set_state_expr(my_size_id, dest, alloc_state_num(size.value));
650 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
652 struct expression fake_assign;
654 fake_assign.op = '=';
655 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
656 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
657 match_array_assignment(&fake_assign);
660 static void match_strndup(const char *fn, struct expression *expr, void *unused)
662 struct expression *fn_expr;
663 struct expression *size_expr;
664 sval_t size;
666 fn_expr = strip_expr(expr->right);
667 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
668 if (!get_implied_max(size_expr, &size))
669 return;
671 /* It's easy to forget space for the NUL char */
672 size.value++;
673 set_state_expr(my_size_id, expr->left, alloc_state_num(size.value));
676 static void match_call(struct expression *expr)
678 struct expression *arg;
679 int bytes;
680 int i;
682 i = 0;
683 FOR_EACH_PTR(expr->args, arg) {
684 bytes = get_array_size_bytes(arg);
685 if (bytes > 1) {
686 char buf[11];
688 snprintf(buf, sizeof(buf), "%d", bytes);
689 sql_insert_caller_info(expr, BUF_SIZE, i, "$$", buf);
691 i++;
692 } END_FOR_EACH_PTR(arg);
695 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
697 if (state == &merged)
698 return;
699 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, state->name);
702 void register_buf_size(int id)
704 my_size_id = id;
706 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
707 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
709 add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
710 add_function_assign_hook("calloc", &match_calloc, NULL);
711 add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
712 if (option_project == PROJ_KERNEL) {
713 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
714 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
715 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
716 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
717 add_function_assign_hook("kcalloc", &match_calloc, NULL);
718 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
719 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
720 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
721 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
722 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
723 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
724 add_function_assign_hook("dma_alloc_attrs", &match_alloc, INT_PTR(1));
726 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
727 add_hook(&match_strlen_condition, CONDITION_HOOK);
728 add_function_assign_hook("strlen", &match_strlen, NULL);
730 add_function_assign_hook("strndup", match_strndup, NULL);
731 if (option_project == PROJ_KERNEL)
732 add_function_assign_hook("kstrndup", match_strndup, NULL);
734 add_modification_hook(my_size_id, &set_undefined);
736 add_merge_hook(my_size_id, &merge_func);
739 void register_strlen(int id)
741 my_strlen_id = id;
742 add_modification_hook(my_strlen_id, &set_undefined);
743 add_merge_hook(my_strlen_id, &merge_func);
746 void register_buf_size_late(int id)
748 add_function_hook("strlcpy", &match_limited, &b0_l2);
749 add_function_hook("strlcat", &match_limited, &b0_l2);
750 add_function_hook("memscan", &match_limited, &b0_l2);
752 add_function_hook("strcpy", &match_strcpy, NULL);
754 add_hook(&match_call, FUNCTION_CALL_HOOK);
755 add_member_info_callback(my_size_id, struct_member_callback);