math: uninitialized variable handling bitwise ANDs
[smatch.git] / smatch_buf_size.c
blob616deadb5299b16144810f6cca7d8632194446e7
1 /*
2 * Copyright (C) 2010 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
18 #include <stdlib.h>
19 #include <errno.h>
20 #include "parse.h"
21 #include "smatch.h"
22 #include "smatch_slist.h"
23 #include "smatch_extra.h"
24 #include "smatch_function_hashtable.h"
26 #define UNKNOWN_SIZE (-1)
28 static int my_size_id;
30 static DEFINE_HASHTABLE_INSERT(insert_func, char, int);
31 static DEFINE_HASHTABLE_SEARCH(search_func, char, int);
32 static struct hashtable *allocation_funcs;
34 static char *get_fn_name(struct expression *expr)
36 if (expr->type != EXPR_CALL)
37 return NULL;
38 if (expr->fn->type != EXPR_SYMBOL)
39 return NULL;
40 return expr_to_var(expr->fn);
43 static int is_allocation_function(struct expression *expr)
45 char *func;
46 int ret = 0;
48 func = get_fn_name(expr);
49 if (!func)
50 return 0;
51 if (search_func(allocation_funcs, func))
52 ret = 1;
53 free_string(func);
54 return ret;
57 static void add_allocation_function(const char *func, void *call_back, int param)
59 insert_func(allocation_funcs, (char *)func, (int *)1);
60 add_function_assign_hook(func, call_back, INT_PTR(param));
63 static int estate_to_size(struct smatch_state *state)
65 sval_t sval;
67 if (!state || !estate_rl(state))
68 return 0;
69 sval = estate_max(state);
70 return sval.value;
73 static struct smatch_state *size_to_estate(int size)
75 sval_t sval;
77 sval.type = &int_ctype;
78 sval.value = size;
80 return alloc_estate_sval(sval);
83 static struct range_list *size_to_rl(int size)
85 sval_t sval;
87 sval.type = &int_ctype;
88 sval.value = size;
90 return alloc_rl(sval, sval);
93 static struct smatch_state *unmatched_size_state(struct sm_state *sm)
95 return size_to_estate(UNKNOWN_SIZE);
98 static void set_size_undefined(struct sm_state *sm, struct expression *mod_expr)
100 set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
103 static struct smatch_state *merge_size_func(struct smatch_state *s1, struct smatch_state *s2)
105 return merge_estates(s1, s2);
108 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
110 struct range_list *rl = NULL;
111 struct smatch_state *state;
112 char fullname[256];
114 if (strncmp(key, "$", 1) != 0)
115 return;
117 snprintf(fullname, 256, "%s%s", name, key + 1);
119 str_to_rl(&int_ctype, value, &rl);
120 if (!rl || is_whole_rl(rl))
121 return;
122 state = alloc_estate_rl(rl);
123 set_state(my_size_id, fullname, sym, state);
126 static int bytes_per_element(struct expression *expr)
128 struct symbol *type;
130 if (!expr)
131 return 0;
132 if (expr->type == EXPR_STRING)
133 return 1;
134 if (expr->type == EXPR_PREOP && expr->op == '&') {
135 type = get_type(expr->unop);
136 if (type && type->type == SYM_ARRAY)
137 expr = expr->unop;
139 type = get_type(expr);
140 if (!type)
141 return 0;
143 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
144 return 0;
146 type = get_base_type(type);
147 return type_bytes(type);
150 static int bytes_to_elements(struct expression *expr, int bytes)
152 int bpe;
154 bpe = bytes_per_element(expr);
155 if (bpe == 0)
156 return 0;
157 return bytes / bpe;
160 static int elements_to_bytes(struct expression *expr, int elements)
162 int bpe;
164 bpe = bytes_per_element(expr);
165 return elements * bpe;
168 static int get_initializer_size(struct expression *expr)
170 switch (expr->type) {
171 case EXPR_STRING:
172 return expr->string->length;
173 case EXPR_INITIALIZER: {
174 struct expression *tmp;
175 int i = 0;
177 FOR_EACH_PTR(expr->expr_list, tmp) {
178 if (tmp->type == EXPR_INDEX) {
179 if (tmp->idx_to >= i)
180 i = tmp->idx_to;
181 else
182 continue;
185 i++;
186 } END_FOR_EACH_PTR(tmp);
187 return i;
189 case EXPR_SYMBOL:
190 return get_array_size(expr);
192 return 0;
195 static struct range_list *db_size_rl;
196 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
198 struct range_list *tmp = NULL;
200 if (!db_size_rl) {
201 str_to_rl(&int_ctype, argv[0], &db_size_rl);
202 } else {
203 str_to_rl(&int_ctype, argv[0], &tmp);
204 db_size_rl = rl_union(db_size_rl, tmp);
206 return 0;
209 static struct range_list *size_from_db(struct expression *expr)
211 int this_file_only = 0;
212 char *name;
214 name = get_member_name(expr);
215 if (!name && is_static(expr)) {
216 name = expr_to_var(expr);
217 this_file_only = 1;
219 if (!name)
220 return NULL;
222 if (this_file_only) {
223 db_size_rl = NULL;
224 run_sql(db_size_callback, NULL,
225 "select size from function_type_size where type = '%s' and file = '%s';",
226 name, get_filename());
227 if (db_size_rl)
228 return db_size_rl;
229 return NULL;
232 db_size_rl = NULL;
233 run_sql(db_size_callback, NULL,
234 "select size from type_size where type = '%s';",
235 name);
236 return db_size_rl;
239 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
241 struct expression *call;
242 struct range_list *rl;
244 if (expr->type != EXPR_ASSIGNMENT)
245 return;
246 call = strip_expr(expr->right);
248 if (!parse_call_math_rl(call, math, &rl))
249 return;
250 rl = cast_rl(&int_ctype, rl);
251 set_state_expr(my_size_id, expr->left, alloc_estate_rl(rl));
254 int get_real_array_size(struct expression *expr)
256 struct symbol *type;
257 sval_t sval;
259 if (!expr)
260 return 0;
261 if (expr->type == EXPR_PREOP && expr->op == '&')
262 expr = expr->unop;
263 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
264 return 0;
266 type = get_type(expr);
267 if (!type)
268 return 0;
269 if (!type || type->type != SYM_ARRAY)
270 return 0;
272 if (!get_implied_value(type->array_size, &sval))
273 return 0;
275 /* People put one element arrays on the end of structs */
276 if (sval.value == 1)
277 return 0;
279 return sval.value;
282 static int get_size_from_initializer(struct expression *expr)
284 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
285 return 0;
286 if (expr->symbol->initializer == expr) /* int a = a; */
287 return 0;
288 return get_initializer_size(expr->symbol->initializer);
291 static struct range_list *get_stored_size_bytes(struct expression *expr)
293 struct smatch_state *state;
295 state = get_state_expr(my_size_id, expr);
296 if (!state)
297 return NULL;
298 return estate_rl(state);
301 static int get_bytes_from_address(struct expression *expr)
303 struct symbol *type;
304 int ret;
306 if (!option_spammy)
307 return 0;
308 if (expr->type != EXPR_PREOP || expr->op != '&')
309 return 0;
310 type = get_type(expr);
311 if (!type)
312 return 0;
314 if (type->type == SYM_PTR)
315 type = get_base_type(type);
317 ret = type_bytes(type);
318 if (ret == 1)
319 return 0; /* ignore char pointers */
321 return ret;
324 static struct expression *remove_addr_fluff(struct expression *expr)
326 struct expression *tmp;
327 sval_t sval;
329 expr = strip_expr(expr);
331 /* remove '&' and '*' operations that cancel */
332 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
333 tmp = strip_expr(expr->unop);
334 if (tmp->type != EXPR_PREOP)
335 break;
336 if (tmp->op != '*')
337 break;
338 expr = strip_expr(tmp->unop);
341 if (!expr)
342 return NULL;
344 /* "foo + 0" is just "foo" */
345 if (expr->type == EXPR_BINOP && expr->op == '+' &&
346 get_value(expr->right, &sval) && sval.value == 0)
347 return expr->left;
349 return expr;
352 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
354 struct symbol *tmp;
355 int i;
357 i = 0;
358 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
359 if (i++ || !tmp->ident)
360 return 0;
361 if (tmp->ident == member)
362 return 1;
363 return 0;
364 } END_FOR_EACH_PTR_REVERSE(tmp);
366 return 0;
369 static int last_member_is_resizable(struct symbol *sym)
371 struct symbol *last_member;
372 struct symbol *type;
373 sval_t sval;
375 last_member = last_ptr_list((struct ptr_list *)sym->symbol_list);
376 if (!last_member || !last_member->ident)
377 return 0;
379 type = get_real_base_type(last_member);
380 if (type->type == SYM_STRUCT)
381 return last_member_is_resizable(type);
382 if (type->type != SYM_ARRAY)
383 return 0;
385 if (!get_implied_value(type->array_size, &sval))
386 return 0;
388 if (sval.value != 0 && sval.value != 1)
389 return 0;
391 return 1;
394 static int get_stored_size_end_struct_bytes(struct expression *expr)
396 struct symbol *sym;
397 struct symbol *base_sym;
398 struct smatch_state *state;
400 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
401 return 0;
403 if (expr->type == EXPR_PREOP && expr->op == '&')
404 expr = strip_parens(expr->unop);
406 sym = expr_to_sym(expr);
407 if (!sym || !sym->ident)
408 return 0;
409 if (!type_bytes(sym))
410 return 0;
411 if (sym->type != SYM_NODE)
412 return 0;
414 base_sym = get_real_base_type(sym);
415 if (!base_sym || base_sym->type != SYM_PTR)
416 return 0;
417 base_sym = get_real_base_type(base_sym);
418 if (!base_sym || base_sym->type != SYM_STRUCT)
419 return 0;
421 if (!is_last_member_of_struct(base_sym, expr->member))
422 return 0;
423 if (!last_member_is_resizable(base_sym))
424 return 0;
426 state = get_state(my_size_id, sym->ident->name, sym);
427 if (!estate_to_size(state))
428 return 0;
430 return estate_to_size(state) - type_bytes(base_sym) + array_bytes(get_type(expr));
433 static struct range_list *alloc_int_rl(int value)
435 sval_t sval = {
436 .type = &int_ctype,
437 {.value = value},
440 return alloc_rl(sval, sval);
443 struct range_list *get_array_size_bytes_rl(struct expression *expr)
445 struct range_list *ret = NULL;
446 int size;
448 expr = remove_addr_fluff(expr);
449 if (!expr)
450 return NULL;
452 /* "BAR" */
453 if (expr->type == EXPR_STRING)
454 return alloc_int_rl(expr->string->length);
456 if (expr->type == EXPR_BINOP && expr->op == '+') {
457 sval_t offset;
458 struct symbol *type;
459 int bytes;
461 if (!get_implied_value(expr->right, &offset))
462 return NULL;
463 type = get_type(expr->left);
464 if (!type)
465 return NULL;
466 if (type->type != SYM_ARRAY && type->type != SYM_PTR)
467 return NULL;
468 type = get_real_base_type(type);
469 bytes = type_bytes(type);
470 if (bytes == 0)
471 return NULL;
472 offset.value *= bytes;
473 size = get_array_size_bytes(expr->left);
474 if (size <= 0)
475 return NULL;
476 return alloc_int_rl(size - offset.value);
479 /* buf[4] */
480 size = get_real_array_size(expr);
481 if (size)
482 return alloc_int_rl(elements_to_bytes(expr, size));
484 /* buf = malloc(1024); */
485 ret = get_stored_size_bytes(expr);
486 if (ret)
487 return ret;
489 size = get_stored_size_end_struct_bytes(expr);
490 if (size)
491 return alloc_int_rl(size);
493 /* char *foo = "BAR" */
494 size = get_size_from_initializer(expr);
495 if (size)
496 return alloc_int_rl(elements_to_bytes(expr, size));
498 size = get_bytes_from_address(expr);
499 if (size)
500 return alloc_int_rl(size);
502 ret = size_from_db(expr);
503 if (ret)
504 return ret;
506 return NULL;
509 int get_array_size_bytes(struct expression *expr)
511 struct range_list *rl;
512 sval_t sval;
514 rl = get_array_size_bytes_rl(expr);
515 if (!rl_to_sval(rl, &sval))
516 return 0;
517 if (sval.uvalue >= INT_MAX)
518 return 0;
519 return sval.value;
522 int get_array_size_bytes_max(struct expression *expr)
524 struct range_list *rl;
525 sval_t bytes;
527 rl = get_array_size_bytes_rl(expr);
528 if (!rl)
529 return 0;
530 bytes = rl_min(rl);
531 if (bytes.value < 0)
532 return 0;
533 bytes = rl_max(rl);
534 if (bytes.uvalue >= INT_MAX)
535 return 0;
536 return bytes.value;
539 int get_array_size_bytes_min(struct expression *expr)
541 struct range_list *rl;
542 struct data_range *range;
544 rl = get_array_size_bytes_rl(expr);
545 if (!rl)
546 return 0;
548 FOR_EACH_PTR(rl, range) {
549 if (range->min.value <= 0)
550 return 0;
551 if (range->max.value <= 0)
552 return 0;
553 if (range->min.uvalue >= INT_MAX)
554 return 0;
555 return range->min.value;
556 } END_FOR_EACH_PTR(range);
558 return 0;
561 int get_array_size(struct expression *expr)
563 if (!expr)
564 return 0;
565 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
568 static struct expression *strip_ampersands(struct expression *expr)
570 struct symbol *type;
572 if (expr->type != EXPR_PREOP)
573 return expr;
574 if (expr->op != '&')
575 return expr;
576 type = get_type(expr->unop);
577 if (!type || type->type != SYM_ARRAY)
578 return expr;
579 return expr->unop;
582 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
584 char *name;
586 if (!option_info)
587 return;
589 name = get_member_name(buffer);
590 if (!name && is_static(buffer))
591 name = expr_to_var(buffer);
592 if (!name)
593 return;
594 if (rl && !is_whole_rl(rl))
595 sql_insert_function_type_size(name, show_rl(rl));
596 else
597 sql_insert_function_type_size(name, "(-1)");
599 free_string(name);
602 static void store_alloc(struct expression *expr, struct range_list *rl)
604 struct symbol *type;
606 rl = clone_rl(rl); // FIXME!!!
607 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
609 type = get_type(expr);
610 if (!type)
611 return;
612 if (type->type != SYM_PTR)
613 return;
614 type = get_real_base_type(type);
615 if (!type)
616 return;
617 if (type == &void_ctype)
618 return;
619 if (type->type != SYM_BASETYPE && type->type != SYM_PTR)
620 return;
622 info_record_alloction(expr, rl);
625 static void match_array_assignment(struct expression *expr)
627 struct expression *left;
628 struct expression *right;
629 char *left_member, *right_member;
630 struct range_list *rl;
631 sval_t sval;
633 if (expr->op != '=')
634 return;
635 left = strip_expr(expr->left);
636 right = strip_expr(expr->right);
637 right = strip_ampersands(right);
639 if (!is_pointer(left))
640 return;
641 if (is_allocation_function(right))
642 return;
644 left_member = get_member_name(left);
645 right_member = get_member_name(right);
646 if (left_member && right_member && strcmp(left_member, right_member) == 0) {
647 free_string(left_member);
648 free_string(right_member);
649 return;
651 free_string(left_member);
652 free_string(right_member);
654 if (get_implied_value(right, &sval) && sval.value == 0) {
655 rl = alloc_int_rl(0);
656 goto store;
659 rl = get_array_size_bytes_rl(right);
661 store:
662 store_alloc(left, rl);
665 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
667 int size_arg = PTR_INT(_size_arg);
668 struct expression *right;
669 struct expression *arg;
670 struct range_list *rl;
672 right = strip_expr(expr->right);
673 arg = get_argument_from_call_expr(right->args, size_arg);
674 get_absolute_rl(arg, &rl);
675 rl = cast_rl(&int_ctype, rl);
676 store_alloc(expr->left, rl);
679 static void match_calloc(const char *fn, struct expression *expr, void *unused)
681 struct expression *right;
682 struct expression *arg;
683 sval_t elements;
684 sval_t size;
686 right = strip_expr(expr->right);
687 arg = get_argument_from_call_expr(right->args, 0);
688 if (!get_implied_value(arg, &elements))
689 return; // FIXME!!!
690 arg = get_argument_from_call_expr(right->args, 1);
691 if (get_implied_value(arg, &size))
692 store_alloc(expr->left, size_to_rl(elements.value * size.value));
693 else
694 store_alloc(expr->left, size_to_rl(-1));
697 static void match_page(const char *fn, struct expression *expr, void *_unused)
699 sval_t page_size = {
700 .type = &int_ctype,
701 {.value = 4096},
704 store_alloc(expr->left, alloc_rl(page_size, page_size));
707 static void match_strndup(const char *fn, struct expression *expr, void *unused)
709 struct expression *fn_expr;
710 struct expression *size_expr;
711 sval_t size;
713 fn_expr = strip_expr(expr->right);
714 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
715 if (get_implied_max(size_expr, &size)) {
716 size.value++;
717 store_alloc(expr->left, size_to_rl(size.value));
718 } else {
719 store_alloc(expr->left, size_to_rl(-1));
724 static void match_alloc_pages(const char *fn, struct expression *expr, void *_order_arg)
726 int order_arg = PTR_INT(_order_arg);
727 struct expression *right;
728 struct expression *arg;
729 sval_t sval;
731 right = strip_expr(expr->right);
732 arg = get_argument_from_call_expr(right->args, order_arg);
733 if (!get_implied_value(arg, &sval))
734 return;
735 if (sval.value < 0 || sval.value > 10)
736 return;
738 sval.type = &int_ctype;
739 sval.value = 1 << sval.value;
740 sval.value *= 4096;
742 store_alloc(expr->left, alloc_rl(sval, sval));
745 static void match_call(struct expression *expr)
747 struct expression *arg;
748 struct symbol *type;
749 struct range_list *rl;
750 int i;
752 i = -1;
753 FOR_EACH_PTR(expr->args, arg) {
754 i++;
755 type = get_type(arg);
756 if (!type || (type->type != SYM_PTR && type->type != SYM_ARRAY))
757 continue;
758 rl = get_array_size_bytes_rl(arg);
759 if (!rl)
760 continue;
761 if (is_whole_rl(rl))
762 continue;
763 sql_insert_caller_info(expr, BUF_SIZE, i, "$", show_rl(rl));
764 } END_FOR_EACH_PTR(arg);
767 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
769 if (sm->state == &merged ||
770 strcmp(sm->state->name, "(-1)") == 0 ||
771 strcmp(sm->state->name, "empty") == 0 ||
772 strcmp(sm->state->name, "0") == 0)
773 return;
774 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, sm->state->name);
778 * This is slightly (very) weird because half of this stuff is handled in
779 * smatch_parse_call_math.c which is poorly named. But anyway, add some buf
780 * sizes here.
783 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
785 char buf[16];
786 int size;
788 size = get_array_size_bytes(expr);
789 if (!size)
790 return;
792 snprintf(buf, sizeof(buf), "%d", size);
793 sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "", buf);
796 void register_buf_size(int id)
798 my_size_id = id;
800 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
802 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
803 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
804 add_split_return_callback(print_returned_allocations);
806 allocation_funcs = create_function_hashtable(100);
807 add_allocation_function("malloc", &match_alloc, 0);
808 add_allocation_function("calloc", &match_calloc, 0);
809 add_allocation_function("memdup", &match_alloc, 1);
810 add_allocation_function("realloc", &match_alloc, 1);
811 if (option_project == PROJ_KERNEL) {
812 add_allocation_function("kmalloc", &match_alloc, 0);
813 add_allocation_function("kmalloc_node", &match_alloc, 0);
814 add_allocation_function("kzalloc", &match_alloc, 0);
815 add_allocation_function("kzalloc_node", &match_alloc, 0);
816 add_allocation_function("vmalloc", &match_alloc, 0);
817 add_allocation_function("__vmalloc", &match_alloc, 0);
818 add_allocation_function("kcalloc", &match_calloc, 0);
819 add_allocation_function("kmalloc_array", &match_calloc, 0);
820 add_allocation_function("drm_malloc_ab", &match_calloc, 0);
821 add_allocation_function("drm_calloc_large", &match_calloc, 0);
822 add_allocation_function("sock_kmalloc", &match_alloc, 1);
823 add_allocation_function("kmemdup", &match_alloc, 1);
824 add_allocation_function("kmemdup_user", &match_alloc, 1);
825 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
826 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
827 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
828 add_allocation_function("devm_kmalloc", &match_alloc, 1);
829 add_allocation_function("devm_kzalloc", &match_alloc, 1);
830 add_allocation_function("krealloc", &match_alloc, 1);
831 add_allocation_function("__alloc_bootmem", &match_alloc, 0);
832 add_allocation_function("alloc_bootmem", &match_alloc, 0);
833 add_allocation_function("kmap", &match_page, 0);
834 add_allocation_function("get_zeroed_page", &match_page, 0);
835 add_allocation_function("alloc_pages", &match_alloc_pages, 1);
836 add_allocation_function("alloc_pages_current", &match_alloc_pages, 1);
837 add_allocation_function("__get_free_pages", &match_alloc_pages, 1);
840 add_allocation_function("strndup", match_strndup, 0);
841 if (option_project == PROJ_KERNEL)
842 add_allocation_function("kstrndup", match_strndup, 0);
844 add_modification_hook(my_size_id, &set_size_undefined);
846 add_merge_hook(my_size_id, &merge_size_func);
849 void register_buf_size_late(int id)
851 /* has to happen after match_alloc() */
852 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
854 add_hook(&match_call, FUNCTION_CALL_HOOK);
855 add_member_info_callback(my_size_id, struct_member_callback);