2 * smatch/smatch_buf_size.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
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
;
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
)
36 if (expr
->fn
->type
!= EXPR_SYMBOL
)
38 return expr_to_var(expr
->fn
);
41 static int is_allocation_function(struct expression
*expr
)
46 func
= get_fn_name(expr
);
49 if (search_func(allocation_funcs
, func
))
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
)
65 if (!state
|| !estate_rl(state
))
67 sval
= estate_max(state
);
71 static struct smatch_state
*size_to_estate(int size
)
75 sval
.type
= &int_ctype
;
78 return alloc_estate_sval(sval
);
81 static struct range_list
*size_to_rl(int size
)
85 sval
.type
= &int_ctype
;
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
;
112 if (strncmp(key
, "$$", 2) != 0)
115 snprintf(fullname
, 256, "%s%s", name
, key
+ 2);
117 str_to_rl(&int_ctype
, value
, &rl
);
118 if (!rl
|| is_whole_rl(rl
))
120 state
= alloc_estate_rl(rl
);
121 set_state(my_size_id
, fullname
, sym
, state
);
124 static int bytes_per_element(struct expression
*expr
)
129 if (expr
->type
== EXPR_STRING
)
131 type
= get_type(expr
);
135 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
)
138 type
= get_base_type(type
);
139 bpe
= bits_to_bytes(type
->bit_size
);
141 if (bpe
== -1) /* void pointer */
147 static int bytes_to_elements(struct expression
*expr
, int bytes
)
151 bpe
= bytes_per_element(expr
);
157 static int elements_to_bytes(struct expression
*expr
, int elements
)
161 bpe
= bytes_per_element(expr
);
162 return elements
* bpe
;
165 static int get_initializer_size(struct expression
*expr
)
167 switch (expr
->type
) {
169 return expr
->string
->length
;
170 case EXPR_INITIALIZER
: {
171 struct expression
*tmp
;
174 FOR_EACH_PTR(expr
->expr_list
, tmp
) {
175 if (tmp
->type
== EXPR_INDEX
) {
176 if (tmp
->idx_to
>= i
)
183 } END_FOR_EACH_PTR(tmp
);
187 return get_array_size(expr
);
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
;
198 str_to_rl(&int_ctype
, argv
[0], &db_size_rl
);
200 str_to_rl(&int_ctype
, argv
[0], &tmp
);
201 db_size_rl
= rl_union(db_size_rl
, tmp
);
206 static struct range_list
*size_from_db(struct expression
*expr
)
208 int this_file_only
= 0;
211 name
= get_member_name(expr
);
212 if (!name
&& is_static(expr
)) {
213 name
= expr_to_var(expr
);
219 if (this_file_only
) {
221 run_sql(db_size_callback
, "select size from function_type_size where type = '%s' and file = '%s';",
222 name
, get_filename());
229 run_sql(db_size_callback
, "select size from type_size where type = '%s';",
234 static void db_returns_buf_size(struct expression
*expr
, int param
, char *unused
, char *math
)
236 struct expression
*call
;
239 if (expr
->type
!= EXPR_ASSIGNMENT
)
241 call
= strip_expr(expr
->right
);
243 if (!parse_call_math(call
, math
, &sval
))
245 set_state_expr(my_size_id
, expr
->left
, size_to_estate(sval
.value
));
248 int get_real_array_size(struct expression
*expr
)
253 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
256 type
= get_type(expr
);
259 if (!type
|| type
->type
!= SYM_ARRAY
)
262 if (!get_implied_value(type
->array_size
, &sval
))
265 /* People put one element arrays on the end of structs */
272 static int get_size_from_initializer(struct expression
*expr
)
274 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
|| !expr
->symbol
->initializer
)
276 if (expr
->symbol
->initializer
== expr
) /* int a = a; */
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
);
288 return estate_rl(state
);
291 static int get_bytes_from_address(struct expression
*expr
)
298 if (expr
->type
!= EXPR_PREOP
|| expr
->op
!= '&')
300 type
= get_type(expr
);
304 if (type
->type
== SYM_PTR
)
305 type
= get_base_type(type
);
307 ret
= bits_to_bytes(type
->bit_size
);
311 return 0; /* ignore char pointers */
316 static struct expression
*remove_addr_fluff(struct expression
*expr
)
318 struct expression
*tmp
;
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
)
330 expr
= strip_expr(tmp
->unop
);
336 /* "foo + 0" is just "foo" */
337 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+' &&
338 get_value(expr
->right
, &sval
) && sval
.value
== 0)
344 static int is_last_member_of_struct(struct symbol
*sym
, struct ident
*member
)
350 FOR_EACH_PTR_REVERSE(sym
->symbol_list
, tmp
) {
351 if (i
++ || !tmp
->ident
)
353 if (tmp
->ident
== member
)
356 } END_FOR_EACH_PTR_REVERSE(tmp
);
361 static int get_stored_size_end_struct_bytes(struct expression
*expr
)
366 struct smatch_state
*state
;
369 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
372 type
= get_type(expr
);
373 if (!type
|| type
->type
!= SYM_ARRAY
)
376 if (!get_implied_value(type
->array_size
, &sval
))
379 if (sval
.value
!= 0 && sval
.value
!= 1)
382 name
= expr_to_var_sym(expr
, &sym
);
384 if (!sym
|| !sym
->ident
|| !sym
->ident
->name
)
389 if (sym
->type
!= SYM_NODE
)
392 state
= get_state(my_size_id
, sym
->ident
->name
, sym
);
393 if (!estate_to_size(state
))
396 sym
= get_real_base_type(sym
);
397 if (!sym
|| sym
->type
!= SYM_PTR
)
399 sym
= get_real_base_type(sym
);
400 if (!sym
|| sym
->type
!= SYM_STRUCT
)
402 if (!is_last_member_of_struct(sym
, expr
->member
))
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
)
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
;
425 expr
= remove_addr_fluff(expr
);
430 if (expr
->type
== EXPR_STRING
)
431 return alloc_int_rl(expr
->string
->length
);
434 size
= get_real_array_size(expr
);
436 declared_size
= elements_to_bytes(expr
, size
);
438 /* buf = malloc(1024); */
439 ret
= get_stored_size_bytes(expr
);
442 return rl_union(ret
, alloc_int_rl(size
));
446 return alloc_int_rl(declared_size
);
448 size
= get_stored_size_end_struct_bytes(expr
);
450 return alloc_int_rl(size
);
452 /* char *foo = "BAR" */
453 size
= get_size_from_initializer(expr
);
455 return alloc_int_rl(elements_to_bytes(expr
, size
));
457 size
= get_bytes_from_address(expr
);
459 return alloc_int_rl(size
);
461 /* if (strlen(foo) > 4) */
462 size
= get_size_from_strlen(expr
);
464 return alloc_int_rl(size
);
466 ret
= size_from_db(expr
);
473 int get_array_size_bytes(struct expression
*expr
)
475 struct range_list
*rl
;
478 rl
= get_array_size_bytes_rl(expr
);
479 if (!rl_to_sval(rl
, &sval
))
481 if (sval
.uvalue
>= INT_MAX
)
486 int get_array_size_bytes_max(struct expression
*expr
)
488 struct range_list
*rl
;
491 rl
= get_array_size_bytes_rl(expr
);
498 if (bytes
.uvalue
>= INT_MAX
)
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
);
512 FOR_EACH_PTR(rl
, range
) {
513 if (range
->min
.value
<= 0)
515 if (range
->max
.value
<= 0)
517 if (range
->min
.uvalue
>= INT_MAX
)
519 return range
->min
.value
;
520 } END_FOR_EACH_PTR(range
);
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
;
536 int strlen_right
= 0;
538 struct smatch_state
*true_state
= NULL
;
539 struct smatch_state
*false_state
= NULL
;
541 if (expr
->type
!= EXPR_COMPARE
)
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);
550 if (right
->type
== EXPR_CALL
&& sym_name_is("strlen", right
->fn
)) {
551 str
= get_argument_from_call_expr(right
->args
, 0);
555 if (!strlen_left
&& !strlen_right
)
557 if (strlen_left
&& strlen_right
)
561 if (!get_value(right
, &sval
))
565 if (!get_value(left
, &sval
))
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
);
575 if (expr
->op
== SPECIAL_NOTEQUAL
) {
576 set_true_false_states_expr(my_size_id
, str
, NULL
, size_to_estate(sval
.value
+ 1));
582 case SPECIAL_UNSIGNED_LT
:
584 true_state
= size_to_estate(sval
.value
);
586 false_state
= size_to_estate(sval
.value
+ 1);
589 case SPECIAL_UNSIGNED_LTE
:
591 true_state
= size_to_estate(sval
.value
+ 1);
593 false_state
= size_to_estate(sval
.value
);
596 case SPECIAL_UNSIGNED_GTE
:
598 false_state
= size_to_estate(sval
.value
);
600 true_state
= size_to_estate(sval
.value
+ 1);
603 case SPECIAL_UNSIGNED_GT
:
605 false_state
= size_to_estate(sval
.value
+ 1);
607 true_state
= size_to_estate(sval
.value
);
610 set_true_false_states_expr(my_size_id
, str
, true_state
, false_state
);
613 static struct expression
*strip_ampersands(struct expression
*expr
)
617 if (expr
->type
!= EXPR_PREOP
)
621 type
= get_type(expr
->unop
);
622 if (!type
|| type
->type
!= SYM_ARRAY
)
627 static void info_record_alloction(struct expression
*buffer
, struct range_list
*rl
)
634 name
= get_member_name(buffer
);
635 if (!name
&& is_static(buffer
))
636 name
= expr_to_var(buffer
);
639 if (rl
&& !is_whole_rl(rl
))
640 sql_insert_function_type_size(name
, show_rl(rl
));
642 sql_insert_function_type_size(name
, "(-1)");
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
;
663 left
= strip_expr(expr
->left
);
664 right
= strip_expr(expr
->right
);
665 right
= strip_ampersands(right
);
667 if (is_allocation_function(right
))
670 if (get_implied_value(right
, &sval
) && sval
.value
== 0) {
671 rl
= alloc_int_rl(0);
675 rl
= get_array_size_bytes_rl(right
);
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
;
702 right
= strip_expr(expr
->right
);
703 arg
= get_argument_from_call_expr(right
->args
, 0);
704 if (!get_implied_value(arg
, &elements
))
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
));
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
;
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
))
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
;
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
)) {
747 store_alloc(expr
->left
, size_to_rl(size
.value
));
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
;
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
));
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
)
773 sql_insert_caller_info(call
, BUF_SIZE
, param
, printed_name
, state
->name
);
776 void register_buf_size(int 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
);