capped: multiplications can be capped
[smatch.git] / smatch_buf_size.c
blob12d4029c938d0878062bb4b866b3e441bfb362ad
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 type = get_type(expr);
135 if (!type)
136 return 0;
138 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
139 return 0;
141 type = get_base_type(type);
142 return type_bytes(type);
145 static int bytes_to_elements(struct expression *expr, int bytes)
147 int bpe;
149 bpe = bytes_per_element(expr);
150 if (bpe == 0)
151 return 0;
152 return bytes / bpe;
155 static int elements_to_bytes(struct expression *expr, int elements)
157 int bpe;
159 bpe = bytes_per_element(expr);
160 return elements * bpe;
163 static int get_initializer_size(struct expression *expr)
165 switch (expr->type) {
166 case EXPR_STRING:
167 return expr->string->length;
168 case EXPR_INITIALIZER: {
169 struct expression *tmp;
170 int i = 0;
172 FOR_EACH_PTR(expr->expr_list, tmp) {
173 if (tmp->type == EXPR_INDEX) {
174 if (tmp->idx_to >= i)
175 i = tmp->idx_to;
176 else
177 continue;
180 i++;
181 } END_FOR_EACH_PTR(tmp);
182 return i;
184 case EXPR_SYMBOL:
185 return get_array_size(expr);
187 return 0;
190 static struct range_list *db_size_rl;
191 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
193 struct range_list *tmp = NULL;
195 if (!db_size_rl) {
196 str_to_rl(&int_ctype, argv[0], &db_size_rl);
197 } else {
198 str_to_rl(&int_ctype, argv[0], &tmp);
199 db_size_rl = rl_union(db_size_rl, tmp);
201 return 0;
204 static struct range_list *size_from_db(struct expression *expr)
206 int this_file_only = 0;
207 char *name;
209 name = get_member_name(expr);
210 if (!name && is_static(expr)) {
211 name = expr_to_var(expr);
212 this_file_only = 1;
214 if (!name)
215 return 0;
217 if (this_file_only) {
218 db_size_rl = NULL;
219 run_sql(db_size_callback, NULL,
220 "select size from function_type_size where type = '%s' and file = '%s';",
221 name, get_filename());
222 if (db_size_rl)
223 return db_size_rl;
224 return 0;
227 db_size_rl = NULL;
228 run_sql(db_size_callback, NULL,
229 "select size from type_size where type = '%s';",
230 name);
231 return db_size_rl;
234 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
236 struct expression *call;
237 sval_t sval;
239 if (expr->type != EXPR_ASSIGNMENT)
240 return;
241 call = strip_expr(expr->right);
243 if (!parse_call_math(call, math, &sval))
244 return;
245 set_state_expr(my_size_id, expr->left, size_to_estate(sval.value));
248 int get_real_array_size(struct expression *expr)
250 struct symbol *type;
251 sval_t sval;
253 if (!expr)
254 return 0;
255 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
256 return 0;
258 type = get_type(expr);
259 if (!type)
260 return 0;
261 if (!type || type->type != SYM_ARRAY)
262 return 0;
264 if (!get_implied_value(type->array_size, &sval))
265 return 0;
267 /* People put one element arrays on the end of structs */
268 if (sval.value == 1)
269 return 0;
271 return sval.value;
274 static int get_size_from_initializer(struct expression *expr)
276 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
277 return 0;
278 if (expr->symbol->initializer == expr) /* int a = a; */
279 return 0;
280 return get_initializer_size(expr->symbol->initializer);
283 static struct range_list *get_stored_size_bytes(struct expression *expr)
285 struct smatch_state *state;
287 state = get_state_expr(my_size_id, expr);
288 if (!state)
289 return NULL;
290 return estate_rl(state);
293 static int get_bytes_from_address(struct expression *expr)
295 struct symbol *type;
296 int ret;
298 if (!option_spammy)
299 return 0;
300 if (expr->type != EXPR_PREOP || expr->op != '&')
301 return 0;
302 type = get_type(expr);
303 if (!type)
304 return 0;
306 if (type->type == SYM_PTR)
307 type = get_base_type(type);
309 ret = type_bytes(type);
310 if (ret == 1)
311 return 0; /* ignore char pointers */
313 return ret;
316 static struct expression *remove_addr_fluff(struct expression *expr)
318 struct expression *tmp;
319 sval_t sval;
321 expr = strip_expr(expr);
323 /* remove '&' and '*' operations that cancel */
324 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
325 tmp = strip_expr(expr->unop);
326 if (tmp->type != EXPR_PREOP)
327 break;
328 if (tmp->op != '*')
329 break;
330 expr = strip_expr(tmp->unop);
333 if (!expr)
334 return NULL;
336 /* "foo + 0" is just "foo" */
337 if (expr->type == EXPR_BINOP && expr->op == '+' &&
338 get_value(expr->right, &sval) && sval.value == 0)
339 return expr->left;
341 return expr;
344 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
346 struct symbol *tmp;
347 int i;
349 i = 0;
350 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
351 if (i++ || !tmp->ident)
352 return 0;
353 if (tmp->ident == member)
354 return 1;
355 return 0;
356 } END_FOR_EACH_PTR_REVERSE(tmp);
358 return 0;
361 static int last_member_is_resizable(struct symbol *sym)
363 struct symbol *last_member;
364 struct symbol *type;
365 sval_t sval;
367 last_member = last_ptr_list((struct ptr_list *)sym->symbol_list);
368 if (!last_member || !last_member->ident)
369 return 0;
371 type = get_real_base_type(last_member);
372 if (type->type == SYM_STRUCT)
373 return last_member_is_resizable(type);
374 if (type->type != SYM_ARRAY)
375 return 0;
377 if (!get_implied_value(type->array_size, &sval))
378 return 0;
380 if (sval.value != 0 && sval.value != 1)
381 return 0;
383 return 1;
386 static int get_stored_size_end_struct_bytes(struct expression *expr)
388 struct symbol *sym;
389 struct symbol *base_sym;
390 struct smatch_state *state;
392 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
393 return 0;
395 if (expr->type == EXPR_PREOP && expr->op == '&')
396 expr = strip_parens(expr->unop);
398 sym = expr_to_sym(expr);
399 if (!sym || !sym->ident)
400 return 0;
401 if (!type_bytes(sym))
402 return 0;
403 if (sym->type != SYM_NODE)
404 return 0;
406 base_sym = get_real_base_type(sym);
407 if (!base_sym || base_sym->type != SYM_PTR)
408 return 0;
409 base_sym = get_real_base_type(base_sym);
410 if (!base_sym || base_sym->type != SYM_STRUCT)
411 return 0;
413 if (!is_last_member_of_struct(base_sym, expr->member))
414 return 0;
415 if (!last_member_is_resizable(base_sym))
416 return 0;
418 state = get_state(my_size_id, sym->ident->name, sym);
419 if (!estate_to_size(state))
420 return 0;
422 return estate_to_size(state) - type_bytes(base_sym) + type_bytes(get_type(expr));
425 static struct range_list *alloc_int_rl(int value)
427 sval_t sval = {
428 .type = &int_ctype,
429 {.value = value},
432 return alloc_rl(sval, sval);
435 struct range_list *get_array_size_bytes_rl(struct expression *expr)
437 struct range_list *ret = NULL;
438 int size;
440 expr = remove_addr_fluff(expr);
441 if (!expr)
442 return NULL;
444 /* "BAR" */
445 if (expr->type == EXPR_STRING)
446 return alloc_int_rl(expr->string->length);
448 if (expr->type == EXPR_BINOP && expr->op == '+') {
449 sval_t offset;
450 struct symbol *type;
451 int bytes;
453 if (!get_implied_value(expr->right, &offset))
454 return NULL;
455 type = get_type(expr->left);
456 if (!type)
457 return 0;
458 if (type->type != SYM_ARRAY && type->type != SYM_PTR)
459 return 0;
460 type = get_real_base_type(type);
461 bytes = type_bytes(type);
462 if (bytes == 0)
463 return NULL;
464 offset.value *= bytes;
465 size = get_array_size_bytes(expr->left);
466 if (size <= 0)
467 return NULL;
468 return alloc_int_rl(size - offset.value);
471 /* buf[4] */
472 size = get_real_array_size(expr);
473 if (size)
474 return alloc_int_rl(elements_to_bytes(expr, size));
476 /* buf = malloc(1024); */
477 ret = get_stored_size_bytes(expr);
478 if (ret)
479 return ret;
481 size = get_stored_size_end_struct_bytes(expr);
482 if (size)
483 return alloc_int_rl(size);
485 /* char *foo = "BAR" */
486 size = get_size_from_initializer(expr);
487 if (size)
488 return alloc_int_rl(elements_to_bytes(expr, size));
490 size = get_bytes_from_address(expr);
491 if (size)
492 return alloc_int_rl(size);
494 ret = size_from_db(expr);
495 if (ret)
496 return ret;
498 return NULL;
501 int get_array_size_bytes(struct expression *expr)
503 struct range_list *rl;
504 sval_t sval;
506 rl = get_array_size_bytes_rl(expr);
507 if (!rl_to_sval(rl, &sval))
508 return 0;
509 if (sval.uvalue >= INT_MAX)
510 return 0;
511 return sval.value;
514 int get_array_size_bytes_max(struct expression *expr)
516 struct range_list *rl;
517 sval_t bytes;
519 rl = get_array_size_bytes_rl(expr);
520 if (!rl)
521 return 0;
522 bytes = rl_min(rl);
523 if (bytes.value < 0)
524 return 0;
525 bytes = rl_max(rl);
526 if (bytes.uvalue >= INT_MAX)
527 return 0;
528 return bytes.value;
531 int get_array_size_bytes_min(struct expression *expr)
533 struct range_list *rl;
534 struct data_range *range;
536 rl = get_array_size_bytes_rl(expr);
537 if (!rl)
538 return 0;
540 FOR_EACH_PTR(rl, range) {
541 if (range->min.value <= 0)
542 return 0;
543 if (range->max.value <= 0)
544 return 0;
545 if (range->min.uvalue >= INT_MAX)
546 return 0;
547 return range->min.value;
548 } END_FOR_EACH_PTR(range);
550 return 0;
553 int get_array_size(struct expression *expr)
555 if (!expr)
556 return 0;
557 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
560 static struct expression *strip_ampersands(struct expression *expr)
562 struct symbol *type;
564 if (expr->type != EXPR_PREOP)
565 return expr;
566 if (expr->op != '&')
567 return expr;
568 type = get_type(expr->unop);
569 if (!type || type->type != SYM_ARRAY)
570 return expr;
571 return expr->unop;
574 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
576 char *name;
578 if (!option_info)
579 return;
581 name = get_member_name(buffer);
582 if (!name && is_static(buffer))
583 name = expr_to_var(buffer);
584 if (!name)
585 return;
586 if (rl && !is_whole_rl(rl))
587 sql_insert_function_type_size(name, show_rl(rl));
588 else
589 sql_insert_function_type_size(name, "(-1)");
591 free_string(name);
594 static void store_alloc(struct expression *expr, struct range_list *rl)
596 struct symbol *type;
598 rl = clone_rl(rl); // FIXME!!!
599 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
601 type = get_type(expr);
602 if (!type)
603 return;
604 if (type->type != SYM_PTR)
605 return;
606 type = get_real_base_type(type);
607 if (!type)
608 return;
609 if (type == &void_ctype)
610 return;
611 if (type->type != SYM_BASETYPE && type->type != SYM_PTR)
612 return;
614 info_record_alloction(expr, rl);
617 static void match_array_assignment(struct expression *expr)
619 struct expression *left;
620 struct expression *right;
621 char *left_member, *right_member;
622 struct range_list *rl;
623 sval_t sval;
625 if (expr->op != '=')
626 return;
627 left = strip_expr(expr->left);
628 right = strip_expr(expr->right);
629 right = strip_ampersands(right);
631 if (!is_pointer(left))
632 return;
633 if (is_allocation_function(right))
634 return;
636 left_member = get_member_name(left);
637 right_member = get_member_name(right);
638 if (left_member && right_member && strcmp(left_member, right_member) == 0) {
639 free_string(left_member);
640 free_string(right_member);
641 return;
643 free_string(left_member);
644 free_string(right_member);
646 if (get_implied_value(right, &sval) && sval.value == 0) {
647 rl = alloc_int_rl(0);
648 goto store;
651 rl = get_array_size_bytes_rl(right);
653 store:
654 store_alloc(left, rl);
657 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
659 int size_arg = PTR_INT(_size_arg);
660 struct expression *right;
661 struct expression *arg;
662 struct range_list *rl;
664 right = strip_expr(expr->right);
665 arg = get_argument_from_call_expr(right->args, size_arg);
666 get_absolute_rl(arg, &rl);
667 rl = cast_rl(&int_ctype, rl);
668 store_alloc(expr->left, rl);
671 static void match_calloc(const char *fn, struct expression *expr, void *unused)
673 struct expression *right;
674 struct expression *arg;
675 sval_t elements;
676 sval_t size;
678 right = strip_expr(expr->right);
679 arg = get_argument_from_call_expr(right->args, 0);
680 if (!get_implied_value(arg, &elements))
681 return; // FIXME!!!
682 arg = get_argument_from_call_expr(right->args, 1);
683 if (get_implied_value(arg, &size))
684 store_alloc(expr->left, size_to_rl(elements.value * size.value));
685 else
686 store_alloc(expr->left, size_to_rl(-1));
689 static void match_page(const char *fn, struct expression *expr, void *_unused)
691 sval_t page_size = {
692 .type = &int_ctype,
693 {.value = 4096},
696 store_alloc(expr->left, alloc_rl(page_size, page_size));
699 static void match_strndup(const char *fn, struct expression *expr, void *unused)
701 struct expression *fn_expr;
702 struct expression *size_expr;
703 sval_t size;
705 fn_expr = strip_expr(expr->right);
706 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
707 if (get_implied_max(size_expr, &size)) {
708 size.value++;
709 store_alloc(expr->left, size_to_rl(size.value));
710 } else {
711 store_alloc(expr->left, size_to_rl(-1));
716 static void match_call(struct expression *expr)
718 struct expression *arg;
719 struct symbol *type;
720 struct range_list *rl;
721 int i;
723 i = -1;
724 FOR_EACH_PTR(expr->args, arg) {
725 i++;
726 type = get_type(arg);
727 if (!type || (type->type != SYM_PTR && type->type != SYM_ARRAY))
728 continue;
729 rl = get_array_size_bytes_rl(arg);
730 if (!rl)
731 continue;
732 if (is_whole_rl(rl))
733 continue;
734 sql_insert_caller_info(expr, BUF_SIZE, i, "$", show_rl(rl));
735 } END_FOR_EACH_PTR(arg);
738 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
740 if (sm->state == &merged ||
741 strcmp(sm->state->name, "(-1)") == 0 ||
742 strcmp(sm->state->name, "empty") == 0 ||
743 strcmp(sm->state->name, "0") == 0)
744 return;
745 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, sm->state->name);
748 void register_buf_size(int id)
750 my_size_id = id;
752 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
754 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
755 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
757 allocation_funcs = create_function_hashtable(100);
758 add_allocation_function("malloc", &match_alloc, 0);
759 add_allocation_function("calloc", &match_calloc, 0);
760 add_allocation_function("memdup", &match_alloc, 1);
761 add_allocation_function("realloc", &match_alloc, 1);
762 if (option_project == PROJ_KERNEL) {
763 add_allocation_function("kmalloc", &match_alloc, 0);
764 add_allocation_function("kzalloc", &match_alloc, 0);
765 add_allocation_function("vmalloc", &match_alloc, 0);
766 add_allocation_function("__vmalloc", &match_alloc, 0);
767 add_allocation_function("kcalloc", &match_calloc, 0);
768 add_allocation_function("kmalloc_array", &match_calloc, 0);
769 add_allocation_function("drm_malloc_ab", &match_calloc, 0);
770 add_allocation_function("drm_calloc_large", &match_calloc, 0);
771 add_allocation_function("sock_kmalloc", &match_alloc, 1);
772 add_allocation_function("kmemdup", &match_alloc, 1);
773 add_allocation_function("kmemdup_user", &match_alloc, 1);
774 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
775 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
776 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
777 add_allocation_function("devm_kmalloc", &match_alloc, 1);
778 add_allocation_function("devm_kzalloc", &match_alloc, 1);
779 add_allocation_function("krealloc", &match_alloc, 1);
780 add_allocation_function("kmap", &match_page, 0);
781 add_allocation_function("get_zeroed_page", &match_page, 0);
784 add_allocation_function("strndup", match_strndup, 0);
785 if (option_project == PROJ_KERNEL)
786 add_allocation_function("kstrndup", match_strndup, 0);
788 add_modification_hook(my_size_id, &set_size_undefined);
790 add_merge_hook(my_size_id, &merge_size_func);
793 void register_buf_size_late(int id)
795 /* has to happen after match_alloc() */
796 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
798 add_hook(&match_call, FUNCTION_CALL_HOOK);
799 add_member_info_callback(my_size_id, struct_member_callback);