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
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
)
38 if (expr
->fn
->type
!= EXPR_SYMBOL
)
40 return expr_to_var(expr
->fn
);
43 static int is_allocation_function(struct expression
*expr
)
48 func
= get_fn_name(expr
);
51 if (search_func(allocation_funcs
, func
))
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
)
67 if (!state
|| !estate_rl(state
))
69 sval
= estate_max(state
);
73 static struct smatch_state
*size_to_estate(int size
)
77 sval
.type
= &int_ctype
;
80 return alloc_estate_sval(sval
);
83 static struct range_list
*size_to_rl(int size
)
87 sval
.type
= &int_ctype
;
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
;
114 if (strncmp(key
, "$", 1) != 0)
117 snprintf(fullname
, 256, "%s%s", name
, key
+ 1);
119 str_to_rl(&int_ctype
, value
, &rl
);
120 if (!rl
|| is_whole_rl(rl
))
122 state
= alloc_estate_rl(rl
);
123 set_state(my_size_id
, fullname
, sym
, state
);
126 static int bytes_per_element(struct expression
*expr
)
132 if (expr
->type
== EXPR_STRING
)
134 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '&') {
135 type
= get_type(expr
->unop
);
136 if (type
&& type
->type
== SYM_ARRAY
)
139 type
= get_type(expr
);
143 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
)
146 type
= get_base_type(type
);
147 return type_bytes(type
);
150 static int bytes_to_elements(struct expression
*expr
, int bytes
)
154 bpe
= bytes_per_element(expr
);
160 static int elements_to_bytes(struct expression
*expr
, int elements
)
164 bpe
= bytes_per_element(expr
);
165 return elements
* bpe
;
168 static int get_initializer_size(struct expression
*expr
)
170 switch (expr
->type
) {
172 return expr
->string
->length
;
173 case EXPR_INITIALIZER
: {
174 struct expression
*tmp
;
177 FOR_EACH_PTR(expr
->expr_list
, tmp
) {
178 if (tmp
->type
== EXPR_INDEX
) {
179 if (tmp
->idx_to
>= i
)
186 } END_FOR_EACH_PTR(tmp
);
190 return get_array_size(expr
);
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
;
201 str_to_rl(&int_ctype
, argv
[0], &db_size_rl
);
203 str_to_rl(&int_ctype
, argv
[0], &tmp
);
204 db_size_rl
= rl_union(db_size_rl
, tmp
);
209 static struct range_list
*size_from_db(struct expression
*expr
)
211 int this_file_only
= 0;
214 name
= get_member_name(expr
);
215 if (!name
&& is_static(expr
)) {
216 name
= expr_to_var(expr
);
222 if (this_file_only
) {
224 run_sql(db_size_callback
, NULL
,
225 "select size from function_type_size where type = '%s' and file = '%s';",
226 name
, get_filename());
233 run_sql(db_size_callback
, NULL
,
234 "select size from type_size where type = '%s';",
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
)
246 call
= strip_expr(expr
->right
);
248 if (!parse_call_math_rl(call
, math
, &rl
))
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
)
261 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '&')
263 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
266 type
= get_type(expr
);
269 if (!type
|| type
->type
!= SYM_ARRAY
)
272 if (!get_implied_value(type
->array_size
, &sval
))
275 /* People put one element arrays on the end of structs */
282 static int get_size_from_initializer(struct expression
*expr
)
284 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
|| !expr
->symbol
->initializer
)
286 if (expr
->symbol
->initializer
== expr
) /* int a = a; */
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
);
298 return estate_rl(state
);
301 static int get_bytes_from_address(struct expression
*expr
)
308 if (expr
->type
!= EXPR_PREOP
|| expr
->op
!= '&')
310 type
= get_type(expr
);
314 if (type
->type
== SYM_PTR
)
315 type
= get_base_type(type
);
317 ret
= type_bytes(type
);
319 return 0; /* ignore char pointers */
324 static struct expression
*remove_addr_fluff(struct expression
*expr
)
326 struct expression
*tmp
;
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
)
338 expr
= strip_expr(tmp
->unop
);
344 /* "foo + 0" is just "foo" */
345 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+' &&
346 get_value(expr
->right
, &sval
) && sval
.value
== 0)
352 static int is_last_member_of_struct(struct symbol
*sym
, struct ident
*member
)
358 FOR_EACH_PTR_REVERSE(sym
->symbol_list
, tmp
) {
359 if (i
++ || !tmp
->ident
)
361 if (tmp
->ident
== member
)
364 } END_FOR_EACH_PTR_REVERSE(tmp
);
369 static int last_member_is_resizable(struct symbol
*sym
)
371 struct symbol
*last_member
;
375 last_member
= last_ptr_list((struct ptr_list
*)sym
->symbol_list
);
376 if (!last_member
|| !last_member
->ident
)
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
)
385 if (!get_implied_value(type
->array_size
, &sval
))
388 if (sval
.value
!= 0 && sval
.value
!= 1)
394 static int get_stored_size_end_struct_bytes(struct expression
*expr
)
397 struct symbol
*base_sym
;
398 struct smatch_state
*state
;
400 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
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
)
409 if (!type_bytes(sym
))
411 if (sym
->type
!= SYM_NODE
)
414 base_sym
= get_real_base_type(sym
);
415 if (!base_sym
|| base_sym
->type
!= SYM_PTR
)
417 base_sym
= get_real_base_type(base_sym
);
418 if (!base_sym
|| base_sym
->type
!= SYM_STRUCT
)
421 if (!is_last_member_of_struct(base_sym
, expr
->member
))
423 if (!last_member_is_resizable(base_sym
))
426 state
= get_state(my_size_id
, sym
->ident
->name
, sym
);
427 if (!estate_to_size(state
))
430 return estate_to_size(state
) - type_bytes(base_sym
) + type_bytes(get_type(expr
));
433 static struct range_list
*alloc_int_rl(int 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
;
448 expr
= remove_addr_fluff(expr
);
453 if (expr
->type
== EXPR_STRING
)
454 return alloc_int_rl(expr
->string
->length
);
456 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+') {
461 if (!get_implied_value(expr
->right
, &offset
))
463 type
= get_type(expr
->left
);
466 if (type
->type
!= SYM_ARRAY
&& type
->type
!= SYM_PTR
)
468 type
= get_real_base_type(type
);
469 bytes
= type_bytes(type
);
472 offset
.value
*= bytes
;
473 size
= get_array_size_bytes(expr
->left
);
476 return alloc_int_rl(size
- offset
.value
);
480 size
= get_real_array_size(expr
);
482 return alloc_int_rl(elements_to_bytes(expr
, size
));
484 /* buf = malloc(1024); */
485 ret
= get_stored_size_bytes(expr
);
489 size
= get_stored_size_end_struct_bytes(expr
);
491 return alloc_int_rl(size
);
493 /* char *foo = "BAR" */
494 size
= get_size_from_initializer(expr
);
496 return alloc_int_rl(elements_to_bytes(expr
, size
));
498 size
= get_bytes_from_address(expr
);
500 return alloc_int_rl(size
);
502 ret
= size_from_db(expr
);
509 int get_array_size_bytes(struct expression
*expr
)
511 struct range_list
*rl
;
514 rl
= get_array_size_bytes_rl(expr
);
515 if (!rl_to_sval(rl
, &sval
))
517 if (sval
.uvalue
>= INT_MAX
)
522 int get_array_size_bytes_max(struct expression
*expr
)
524 struct range_list
*rl
;
527 rl
= get_array_size_bytes_rl(expr
);
534 if (bytes
.uvalue
>= INT_MAX
)
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
);
548 FOR_EACH_PTR(rl
, range
) {
549 if (range
->min
.value
<= 0)
551 if (range
->max
.value
<= 0)
553 if (range
->min
.uvalue
>= INT_MAX
)
555 return range
->min
.value
;
556 } END_FOR_EACH_PTR(range
);
561 int get_array_size(struct expression
*expr
)
565 return bytes_to_elements(expr
, get_array_size_bytes_max(expr
));
568 static struct expression
*strip_ampersands(struct expression
*expr
)
572 if (expr
->type
!= EXPR_PREOP
)
576 type
= get_type(expr
->unop
);
577 if (!type
|| type
->type
!= SYM_ARRAY
)
582 static void info_record_alloction(struct expression
*buffer
, struct range_list
*rl
)
589 name
= get_member_name(buffer
);
590 if (!name
&& is_static(buffer
))
591 name
= expr_to_var(buffer
);
594 if (rl
&& !is_whole_rl(rl
))
595 sql_insert_function_type_size(name
, show_rl(rl
));
597 sql_insert_function_type_size(name
, "(-1)");
602 static void store_alloc(struct expression
*expr
, struct range_list
*rl
)
606 rl
= clone_rl(rl
); // FIXME!!!
607 set_state_expr(my_size_id
, expr
, alloc_estate_rl(rl
));
609 type
= get_type(expr
);
612 if (type
->type
!= SYM_PTR
)
614 type
= get_real_base_type(type
);
617 if (type
== &void_ctype
)
619 if (type
->type
!= SYM_BASETYPE
&& type
->type
!= SYM_PTR
)
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
;
635 left
= strip_expr(expr
->left
);
636 right
= strip_expr(expr
->right
);
637 right
= strip_ampersands(right
);
639 if (!is_pointer(left
))
641 if (is_allocation_function(right
))
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
);
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);
659 rl
= get_array_size_bytes_rl(right
);
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
;
686 right
= strip_expr(expr
->right
);
687 arg
= get_argument_from_call_expr(right
->args
, 0);
688 if (!get_implied_value(arg
, &elements
))
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
));
694 store_alloc(expr
->left
, size_to_rl(-1));
697 static void match_page(const char *fn
, struct expression
*expr
, void *_unused
)
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
;
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
)) {
717 store_alloc(expr
->left
, size_to_rl(size
.value
));
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
;
731 right
= strip_expr(expr
->right
);
732 arg
= get_argument_from_call_expr(right
->args
, order_arg
);
733 if (!get_implied_value(arg
, &sval
))
735 if (sval
.value
< 0 || sval
.value
> 10)
738 sval
.type
= &int_ctype
;
739 sval
.value
= 1 << sval
.value
;
742 store_alloc(expr
->left
, alloc_rl(sval
, sval
));
745 static void match_call(struct expression
*expr
)
747 struct expression
*arg
;
749 struct range_list
*rl
;
753 FOR_EACH_PTR(expr
->args
, arg
) {
755 type
= get_type(arg
);
756 if (!type
|| (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
))
758 rl
= get_array_size_bytes_rl(arg
);
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)
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
783 static void print_returned_allocations(int return_id
, char *return_ranges
, struct expression
*expr
)
788 size
= get_array_size_bytes(expr
);
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
)
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
);