smatch.h: include scope.h
[smatch.git] / smatch_buf_size.c
blob0d3d137dee2bb1bd08cbf6c6604f9e10c654e923
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"
16 #include "smatch_function_hashtable.h"
18 #define UNKNOWN_SIZE (-1)
20 static int my_size_id;
22 struct limiter {
23 int buf_arg;
24 int limit_arg;
26 static struct limiter b0_l2 = {0, 2};
28 static DEFINE_HASHTABLE_INSERT(insert_func, char, int);
29 static DEFINE_HASHTABLE_SEARCH(search_func, char, int);
30 static struct hashtable *allocation_funcs;
32 static char *get_fn_name(struct expression *expr)
34 if (expr->type != EXPR_CALL)
35 return NULL;
36 if (expr->fn->type != EXPR_SYMBOL)
37 return NULL;
38 return expr_to_var(expr->fn);
41 static int is_allocation_function(struct expression *expr)
43 char *func;
44 int ret = 0;
46 func = get_fn_name(expr);
47 if (!func)
48 return 0;
49 if (search_func(allocation_funcs, func))
50 ret = 1;
51 free_string(func);
52 return ret;
55 static void add_allocation_function(const char *func, void *call_back, int param)
57 insert_func(allocation_funcs, (char *)func, (int *)1);
58 add_function_assign_hook(func, call_back, INT_PTR(param));
61 static int estate_to_size(struct smatch_state *state)
63 sval_t sval;
65 if (!state || !estate_rl(state))
66 return 0;
67 sval = estate_max(state);
68 return sval.value;
71 static struct smatch_state *size_to_estate(int size)
73 sval_t sval;
75 sval.type = &int_ctype;
76 sval.value = size;
78 return alloc_estate_sval(sval);
81 static struct range_list *size_to_rl(int size)
83 sval_t sval;
85 sval.type = &int_ctype;
86 sval.value = size;
88 return alloc_rl(sval, sval);
91 static struct smatch_state *unmatched_size_state(struct sm_state *sm)
93 return size_to_estate(UNKNOWN_SIZE);
96 static void set_size_undefined(struct sm_state *sm, struct expression *mod_expr)
98 set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
101 static struct smatch_state *merge_size_func(struct smatch_state *s1, struct smatch_state *s2)
103 return merge_estates(s1, s2);
106 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
108 struct range_list *rl = NULL;
109 struct smatch_state *state;
110 char fullname[256];
112 if (strncmp(key, "$$", 2) != 0)
113 return;
115 snprintf(fullname, 256, "%s%s", name, key + 2);
117 str_to_rl(&int_ctype, value, &rl);
118 if (!rl || is_whole_rl(rl))
119 return;
120 state = alloc_estate_rl(rl);
121 set_state(my_size_id, fullname, sym, state);
124 static int bytes_per_element(struct expression *expr)
126 struct symbol *type;
127 int bpe;
129 if (expr->type == EXPR_STRING)
130 return 1;
131 type = get_type(expr);
132 if (!type)
133 return 0;
135 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
136 return 0;
138 type = get_base_type(type);
139 bpe = bits_to_bytes(type->bit_size);
141 if (bpe == -1) /* void pointer */
142 bpe = 1;
144 return bpe;
147 static int bytes_to_elements(struct expression *expr, int bytes)
149 int bpe;
151 bpe = bytes_per_element(expr);
152 if (bpe == 0)
153 return 0;
154 return bytes / bpe;
157 static int elements_to_bytes(struct expression *expr, int elements)
159 int bpe;
161 bpe = bytes_per_element(expr);
162 return elements * bpe;
165 static int get_initializer_size(struct expression *expr)
167 switch (expr->type) {
168 case EXPR_STRING:
169 return expr->string->length;
170 case EXPR_INITIALIZER: {
171 struct expression *tmp;
172 int i = 0;
174 FOR_EACH_PTR(expr->expr_list, tmp) {
175 if (tmp->type == EXPR_INDEX) {
176 if (tmp->idx_to >= i)
177 i = tmp->idx_to;
178 else
179 continue;
182 i++;
183 } END_FOR_EACH_PTR(tmp);
184 return i;
186 case EXPR_SYMBOL:
187 return get_array_size(expr);
189 return 0;
192 static struct range_list *db_size_rl;
193 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
195 struct range_list *tmp = NULL;
197 if (!db_size_rl) {
198 str_to_rl(&int_ctype, argv[0], &db_size_rl);
199 } else {
200 str_to_rl(&int_ctype, argv[0], &tmp);
201 db_size_rl = rl_union(db_size_rl, tmp);
203 return 0;
206 static struct range_list *size_from_db(struct expression *expr)
208 int this_file_only = 0;
209 char *name;
211 name = get_member_name(expr);
212 if (!name && is_static(expr)) {
213 name = expr_to_var(expr);
214 this_file_only = 1;
216 if (!name)
217 return 0;
219 if (this_file_only) {
220 db_size_rl = NULL;
221 run_sql(db_size_callback, "select size from function_type_size where type = '%s' and file = '%s';",
222 name, get_filename());
223 if (db_size_rl)
224 return db_size_rl;
225 return 0;
228 db_size_rl = NULL;
229 run_sql(db_size_callback, "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->type == EXPR_BINOP) /* array elements foo[5] */
254 return 0;
256 type = get_type(expr);
257 if (!type)
258 return 0;
259 if (!type || type->type != SYM_ARRAY)
260 return 0;
262 if (!get_implied_value(type->array_size, &sval))
263 return 0;
265 /* People put one element arrays on the end of structs */
266 if (sval.value == 1)
267 return 0;
269 return sval.value;
272 static int get_size_from_initializer(struct expression *expr)
274 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
275 return 0;
276 if (expr->symbol->initializer == expr) /* int a = a; */
277 return 0;
278 return get_initializer_size(expr->symbol->initializer);
281 static struct range_list *get_stored_size_bytes(struct expression *expr)
283 struct smatch_state *state;
285 state = get_state_expr(my_size_id, expr);
286 if (!state)
287 return NULL;
288 return estate_rl(state);
291 static int get_bytes_from_address(struct expression *expr)
293 struct symbol *type;
294 int ret;
296 if (!option_spammy)
297 return 0;
298 if (expr->type != EXPR_PREOP || expr->op != '&')
299 return 0;
300 type = get_type(expr);
301 if (!type)
302 return 0;
304 if (type->type == SYM_PTR)
305 type = get_base_type(type);
307 ret = bits_to_bytes(type->bit_size);
308 if (ret == -1)
309 return 0;
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 get_stored_size_end_struct_bytes(struct expression *expr)
363 struct symbol *type;
364 char *name;
365 struct symbol *sym;
366 struct smatch_state *state;
367 sval_t sval;
369 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
370 return 0;
372 type = get_type(expr);
373 if (!type || type->type != SYM_ARRAY)
374 return 0;
376 if (!get_implied_value(type->array_size, &sval))
377 return 0;
379 if (sval.value != 0 && sval.value != 1)
380 return 0;
382 name = expr_to_var_sym(expr, &sym);
383 free_string(name);
384 if (!sym || !sym->ident || !sym->ident->name)
385 return 0;
386 if (!sym->bit_size)
387 return 0;
389 if (sym->type != SYM_NODE)
390 return 0;
392 state = get_state(my_size_id, sym->ident->name, sym);
393 if (!estate_to_size(state))
394 return 0;
396 sym = get_real_base_type(sym);
397 if (!sym || sym->type != SYM_PTR)
398 return 0;
399 sym = get_real_base_type(sym);
400 if (!sym || sym->type != SYM_STRUCT)
401 return 0;
402 if (!is_last_member_of_struct(sym, expr->member))
403 return 0;
405 return estate_to_size(state) - bits_to_bytes(sym->bit_size) +
406 bits_to_bytes(type->bit_size);
409 static struct range_list *alloc_int_rl(int value)
411 sval_t sval = {
412 .type = &int_ctype,
413 {.value = value},
416 return alloc_rl(sval, sval);
419 struct range_list *get_array_size_bytes_rl(struct expression *expr)
421 int declared_size = 0;
422 struct range_list *ret = NULL;
423 int size;
425 expr = remove_addr_fluff(expr);
426 if (!expr)
427 return NULL;
429 /* "BAR" */
430 if (expr->type == EXPR_STRING)
431 return alloc_int_rl(expr->string->length);
433 /* buf[4] */
434 size = get_real_array_size(expr);
435 if (size)
436 declared_size = elements_to_bytes(expr, size);
438 /* buf = malloc(1024); */
439 ret = get_stored_size_bytes(expr);
440 if (ret) {
441 if (declared_size)
442 return rl_union(ret, alloc_int_rl(size));
443 return ret;
445 if (declared_size)
446 return alloc_int_rl(declared_size);
448 size = get_stored_size_end_struct_bytes(expr);
449 if (size)
450 return alloc_int_rl(size);
452 /* char *foo = "BAR" */
453 size = get_size_from_initializer(expr);
454 if (size)
455 return alloc_int_rl(elements_to_bytes(expr, size));
457 size = get_bytes_from_address(expr);
458 if (size)
459 return alloc_int_rl(size);
461 /* if (strlen(foo) > 4) */
462 size = get_size_from_strlen(expr);
463 if (size)
464 return alloc_int_rl(size);
466 ret = size_from_db(expr);
467 if (ret)
468 return ret;
470 return NULL;
473 int get_array_size_bytes(struct expression *expr)
475 struct range_list *rl;
476 sval_t sval;
478 rl = get_array_size_bytes_rl(expr);
479 if (!rl_to_sval(rl, &sval))
480 return 0;
481 if (sval.uvalue >= INT_MAX)
482 return 0;
483 return sval.value;
486 int get_array_size_bytes_max(struct expression *expr)
488 struct range_list *rl;
489 sval_t bytes;
491 rl = get_array_size_bytes_rl(expr);
492 if (!rl)
493 return 0;
494 bytes = rl_min(rl);
495 if (bytes.value < 0)
496 return 0;
497 bytes = rl_max(rl);
498 if (bytes.uvalue >= INT_MAX)
499 return 0;
500 return bytes.value;
503 int get_array_size_bytes_min(struct expression *expr)
505 struct range_list *rl;
506 struct data_range *range;
508 rl = get_array_size_bytes_rl(expr);
509 if (!rl)
510 return 0;
512 FOR_EACH_PTR(rl, range) {
513 if (range->min.value <= 0)
514 return 0;
515 if (range->max.value <= 0)
516 return 0;
517 if (range->min.uvalue >= INT_MAX)
518 return 0;
519 return range->min.value;
520 } END_FOR_EACH_PTR(range);
522 return 0;
525 int get_array_size(struct expression *expr)
527 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
530 static void match_strlen_condition(struct expression *expr)
532 struct expression *left;
533 struct expression *right;
534 struct expression *str = NULL;
535 int strlen_left = 0;
536 int strlen_right = 0;
537 sval_t sval;
538 struct smatch_state *true_state = NULL;
539 struct smatch_state *false_state = NULL;
541 if (expr->type != EXPR_COMPARE)
542 return;
543 left = strip_expr(expr->left);
544 right = strip_expr(expr->right);
546 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
547 str = get_argument_from_call_expr(left->args, 0);
548 strlen_left = 1;
550 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
551 str = get_argument_from_call_expr(right->args, 0);
552 strlen_right = 1;
555 if (!strlen_left && !strlen_right)
556 return;
557 if (strlen_left && strlen_right)
558 return;
560 if (strlen_left) {
561 if (!get_value(right, &sval))
562 return;
564 if (strlen_right) {
565 if (!get_value(left, &sval))
566 return;
569 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
571 if (expr->op == SPECIAL_EQUAL) {
572 set_true_false_states_expr(my_size_id, str, size_to_estate(sval.value + 1), NULL);
573 return;
575 if (expr->op == SPECIAL_NOTEQUAL) {
576 set_true_false_states_expr(my_size_id, str, NULL, size_to_estate(sval.value + 1));
577 return;
580 switch (expr->op) {
581 case '<':
582 case SPECIAL_UNSIGNED_LT:
583 if (strlen_left)
584 true_state = size_to_estate(sval.value);
585 else
586 false_state = size_to_estate(sval.value + 1);
587 break;
588 case SPECIAL_LTE:
589 case SPECIAL_UNSIGNED_LTE:
590 if (strlen_left)
591 true_state = size_to_estate(sval.value + 1);
592 else
593 false_state = size_to_estate(sval.value);
594 break;
595 case SPECIAL_GTE:
596 case SPECIAL_UNSIGNED_GTE:
597 if (strlen_left)
598 false_state = size_to_estate(sval.value);
599 else
600 true_state = size_to_estate(sval.value + 1);
601 break;
602 case '>':
603 case SPECIAL_UNSIGNED_GT:
604 if (strlen_left)
605 false_state = size_to_estate(sval.value + 1);
606 else
607 true_state = size_to_estate(sval.value);
608 break;
610 set_true_false_states_expr(my_size_id, str, true_state, false_state);
613 static struct expression *strip_ampersands(struct expression *expr)
615 struct symbol *type;
617 if (expr->type != EXPR_PREOP)
618 return expr;
619 if (expr->op != '&')
620 return expr;
621 type = get_type(expr->unop);
622 if (!type || type->type != SYM_ARRAY)
623 return expr;
624 return expr->unop;
627 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
629 char *name;
631 if (!option_info)
632 return;
634 name = get_member_name(buffer);
635 if (!name && is_static(buffer))
636 name = expr_to_var(buffer);
637 if (!name)
638 return;
639 if (rl && !is_whole_rl(rl))
640 sql_insert_function_type_size(name, show_rl(rl));
641 else
642 sql_insert_function_type_size(name, "(-1)");
644 free_string(name);
647 static void store_alloc(struct expression *expr, struct range_list *rl)
649 rl = clone_rl(rl); // FIXME!!!
650 info_record_alloction(expr, rl);
651 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
654 static void match_array_assignment(struct expression *expr)
656 struct expression *left;
657 struct expression *right;
658 struct range_list *rl;
659 sval_t sval;
661 if (expr->op != '=')
662 return;
663 left = strip_expr(expr->left);
664 right = strip_expr(expr->right);
665 right = strip_ampersands(right);
667 if (is_allocation_function(right))
668 return;
670 if (get_implied_value(right, &sval) && sval.value == 0) {
671 rl = alloc_int_rl(0);
672 goto store;
675 rl = get_array_size_bytes_rl(right);
677 store:
678 store_alloc(left, rl);
681 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
683 int size_arg = PTR_INT(_size_arg);
684 struct expression *right;
685 struct expression *arg;
686 struct range_list *rl;
688 right = strip_expr(expr->right);
689 arg = get_argument_from_call_expr(right->args, size_arg);
690 get_absolute_rl(arg, &rl);
691 rl = cast_rl(&int_ctype, rl);
692 store_alloc(expr->left, rl);
695 static void match_calloc(const char *fn, struct expression *expr, void *unused)
697 struct expression *right;
698 struct expression *arg;
699 sval_t elements;
700 sval_t size;
702 right = strip_expr(expr->right);
703 arg = get_argument_from_call_expr(right->args, 0);
704 if (!get_implied_value(arg, &elements))
705 return; // FIXME!!!
706 arg = get_argument_from_call_expr(right->args, 1);
707 if (get_implied_value(arg, &size))
708 store_alloc(expr->left, size_to_rl(elements.value * size.value));
709 else
710 store_alloc(expr->left, size_to_rl(-1));
713 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
715 struct limiter *limiter = (struct limiter *)_limiter;
716 struct expression *dest;
717 struct expression *size_expr;
718 sval_t size;
720 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
721 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
722 if (!get_implied_max(size_expr, &size))
723 return;
724 set_state_expr(my_size_id, dest, size_to_estate(size.value));
727 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
729 struct expression fake_assign;
731 fake_assign.op = '=';
732 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
733 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
734 match_array_assignment(&fake_assign);
737 static void match_strndup(const char *fn, struct expression *expr, void *unused)
739 struct expression *fn_expr;
740 struct expression *size_expr;
741 sval_t size;
743 fn_expr = strip_expr(expr->right);
744 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
745 if (get_implied_max(size_expr, &size)) {
746 size.value++;
747 store_alloc(expr->left, size_to_rl(size.value));
748 } else {
749 store_alloc(expr->left, size_to_rl(-1));
754 static void match_call(struct expression *expr)
756 struct expression *arg;
757 struct range_list *rl;
758 int i;
760 i = 0;
761 FOR_EACH_PTR(expr->args, arg) {
762 rl = get_array_size_bytes_rl(arg);
763 if (rl && !is_whole_rl(rl))
764 sql_insert_caller_info(expr, BUF_SIZE, i, "$$", show_rl(rl));
765 i++;
766 } END_FOR_EACH_PTR(arg);
769 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
771 if (state == &merged)
772 return;
773 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, state->name);
776 void register_buf_size(int id)
778 my_size_id = id;
780 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
782 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
783 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
785 allocation_funcs = create_function_hashtable(100);
786 add_allocation_function("malloc", &match_alloc, 0);
787 add_allocation_function("calloc", &match_calloc, 0);
788 add_allocation_function("memdup", &match_alloc, 1);
789 if (option_project == PROJ_KERNEL) {
790 add_allocation_function("kmalloc", &match_alloc, 0);
791 add_allocation_function("kzalloc", &match_alloc, 0);
792 add_allocation_function("vmalloc", &match_alloc, 0);
793 add_allocation_function("__vmalloc", &match_alloc, 0);
794 add_allocation_function("kcalloc", &match_calloc, 0);
795 add_allocation_function("kmalloc_array", &match_calloc, 0);
796 add_allocation_function("drm_malloc_ab", &match_calloc, 0);
797 add_allocation_function("drm_calloc_large", &match_calloc, 0);
798 add_allocation_function("sock_kmalloc", &match_alloc, 1);
799 add_allocation_function("kmemdup", &match_alloc, 1);
800 add_allocation_function("kmemdup_user", &match_alloc, 1);
801 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
802 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
803 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
804 add_allocation_function("devm_kmalloc", &match_alloc, 1);
805 add_allocation_function("devm_kzalloc", &match_alloc, 1);
807 add_hook(&match_strlen_condition, CONDITION_HOOK);
809 add_allocation_function("strndup", match_strndup, 0);
810 if (option_project == PROJ_KERNEL)
811 add_allocation_function("kstrndup", match_strndup, 0);
813 add_modification_hook(my_size_id, &set_size_undefined);
815 add_merge_hook(my_size_id, &merge_size_func);
818 void register_buf_size_late(int id)
820 /* has to happen after match_alloc() */
821 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
823 add_function_hook("strlcpy", &match_limited, &b0_l2);
824 add_function_hook("strlcat", &match_limited, &b0_l2);
825 add_function_hook("memscan", &match_limited, &b0_l2);
827 add_function_hook("strcpy", &match_strcpy, NULL);
829 add_hook(&match_call, FUNCTION_CALL_HOOK);
830 add_member_info_callback(my_size_id, struct_member_callback);