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
);
257 if (!type
|| type
->type
!= SYM_ARRAY
)
260 if (!get_implied_value(type
->array_size
, &sval
))
263 /* People put one element arrays on the end of structs */
270 static int get_size_from_initializer(struct expression
*expr
)
272 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
|| !expr
->symbol
->initializer
)
274 if (expr
->symbol
->initializer
== expr
) /* int a = a; */
276 return get_initializer_size(expr
->symbol
->initializer
);
279 static struct range_list
*get_stored_size_bytes(struct expression
*expr
)
281 struct smatch_state
*state
;
283 state
= get_state_expr(my_size_id
, expr
);
286 return estate_rl(state
);
289 static int get_bytes_from_address(struct expression
*expr
)
296 if (expr
->type
!= EXPR_PREOP
|| expr
->op
!= '&')
298 type
= get_type(expr
);
302 if (type
->type
== SYM_PTR
)
303 type
= get_base_type(type
);
305 ret
= bits_to_bytes(type
->bit_size
);
309 return 0; /* ignore char pointers */
314 static struct expression
*remove_addr_fluff(struct expression
*expr
)
316 struct expression
*tmp
;
319 expr
= strip_expr(expr
);
321 /* remove '&' and '*' operations that cancel */
322 while (expr
&& expr
->type
== EXPR_PREOP
&& expr
->op
== '&') {
323 tmp
= strip_expr(expr
->unop
);
324 if (tmp
->type
!= EXPR_PREOP
)
328 expr
= strip_expr(tmp
->unop
);
334 /* "foo + 0" is just "foo" */
335 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+' &&
336 get_value(expr
->right
, &sval
) && sval
.value
== 0)
342 static int is_last_member_of_struct(struct symbol
*sym
, struct ident
*member
)
348 FOR_EACH_PTR_REVERSE(sym
->symbol_list
, tmp
) {
349 if (i
++ || !tmp
->ident
)
351 if (tmp
->ident
== member
)
354 } END_FOR_EACH_PTR_REVERSE(tmp
);
359 static int get_stored_size_end_struct_bytes(struct expression
*expr
)
364 struct smatch_state
*state
;
367 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
370 type
= get_type(expr
);
371 if (!type
|| type
->type
!= SYM_ARRAY
)
374 if (!get_implied_value(type
->array_size
, &sval
))
377 if (sval
.value
!= 0 && sval
.value
!= 1)
380 name
= expr_to_var_sym(expr
, &sym
);
382 if (!sym
|| !sym
->ident
|| !sym
->ident
->name
)
387 if (sym
->type
!= SYM_NODE
)
390 state
= get_state(my_size_id
, sym
->ident
->name
, sym
);
391 if (!estate_to_size(state
))
394 sym
= get_real_base_type(sym
);
395 if (!sym
|| sym
->type
!= SYM_PTR
)
397 sym
= get_real_base_type(sym
);
398 if (!sym
|| sym
->type
!= SYM_STRUCT
)
400 if (!is_last_member_of_struct(sym
, expr
->member
))
403 return estate_to_size(state
) - bits_to_bytes(sym
->bit_size
) +
404 bits_to_bytes(type
->bit_size
);
407 static struct range_list
*alloc_int_rl(int value
)
414 return alloc_rl(sval
, sval
);
417 struct range_list
*get_array_size_bytes_rl(struct expression
*expr
)
419 int declared_size
= 0;
420 struct range_list
*ret
= NULL
;
423 expr
= remove_addr_fluff(expr
);
428 if (expr
->type
== EXPR_STRING
)
429 return alloc_int_rl(expr
->string
->length
);
432 size
= get_real_array_size(expr
);
434 declared_size
= elements_to_bytes(expr
, size
);
436 /* buf = malloc(1024); */
437 ret
= get_stored_size_bytes(expr
);
440 return rl_union(ret
, alloc_int_rl(size
));
444 return alloc_int_rl(declared_size
);
446 size
= get_stored_size_end_struct_bytes(expr
);
448 return alloc_int_rl(size
);
450 /* char *foo = "BAR" */
451 size
= get_size_from_initializer(expr
);
453 return alloc_int_rl(elements_to_bytes(expr
, size
));
455 size
= get_bytes_from_address(expr
);
457 return alloc_int_rl(size
);
459 /* if (strlen(foo) > 4) */
460 size
= get_size_from_strlen(expr
);
462 return alloc_int_rl(size
);
464 ret
= size_from_db(expr
);
471 int get_array_size_bytes(struct expression
*expr
)
473 struct range_list
*rl
;
476 rl
= get_array_size_bytes_rl(expr
);
477 if (!rl_to_sval(rl
, &sval
))
479 if (sval
.uvalue
>= INT_MAX
)
484 int get_array_size_bytes_max(struct expression
*expr
)
486 struct range_list
*rl
;
489 rl
= get_array_size_bytes_rl(expr
);
496 if (bytes
.uvalue
>= INT_MAX
)
501 int get_array_size_bytes_min(struct expression
*expr
)
503 struct range_list
*rl
;
504 struct data_range
*range
;
506 rl
= get_array_size_bytes_rl(expr
);
510 FOR_EACH_PTR(rl
, range
) {
511 if (range
->min
.value
<= 0)
513 if (range
->max
.value
<= 0)
515 if (range
->min
.uvalue
>= INT_MAX
)
517 return range
->min
.value
;
518 } END_FOR_EACH_PTR(range
);
523 int get_array_size(struct expression
*expr
)
525 return bytes_to_elements(expr
, get_array_size_bytes_max(expr
));
528 static void match_strlen_condition(struct expression
*expr
)
530 struct expression
*left
;
531 struct expression
*right
;
532 struct expression
*str
= NULL
;
534 int strlen_right
= 0;
536 struct smatch_state
*true_state
= NULL
;
537 struct smatch_state
*false_state
= NULL
;
539 if (expr
->type
!= EXPR_COMPARE
)
541 left
= strip_expr(expr
->left
);
542 right
= strip_expr(expr
->right
);
544 if (left
->type
== EXPR_CALL
&& sym_name_is("strlen", left
->fn
)) {
545 str
= get_argument_from_call_expr(left
->args
, 0);
548 if (right
->type
== EXPR_CALL
&& sym_name_is("strlen", right
->fn
)) {
549 str
= get_argument_from_call_expr(right
->args
, 0);
553 if (!strlen_left
&& !strlen_right
)
555 if (strlen_left
&& strlen_right
)
559 if (!get_value(right
, &sval
))
563 if (!get_value(left
, &sval
))
567 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
569 if (expr
->op
== SPECIAL_EQUAL
) {
570 set_true_false_states_expr(my_size_id
, str
, size_to_estate(sval
.value
+ 1), NULL
);
573 if (expr
->op
== SPECIAL_NOTEQUAL
) {
574 set_true_false_states_expr(my_size_id
, str
, NULL
, size_to_estate(sval
.value
+ 1));
580 case SPECIAL_UNSIGNED_LT
:
582 true_state
= size_to_estate(sval
.value
);
584 false_state
= size_to_estate(sval
.value
+ 1);
587 case SPECIAL_UNSIGNED_LTE
:
589 true_state
= size_to_estate(sval
.value
+ 1);
591 false_state
= size_to_estate(sval
.value
);
594 case SPECIAL_UNSIGNED_GTE
:
596 false_state
= size_to_estate(sval
.value
);
598 true_state
= size_to_estate(sval
.value
+ 1);
601 case SPECIAL_UNSIGNED_GT
:
603 false_state
= size_to_estate(sval
.value
+ 1);
605 true_state
= size_to_estate(sval
.value
);
608 set_true_false_states_expr(my_size_id
, str
, true_state
, false_state
);
611 static struct expression
*strip_ampersands(struct expression
*expr
)
615 if (expr
->type
!= EXPR_PREOP
)
619 type
= get_type(expr
->unop
);
620 if (!type
|| type
->type
!= SYM_ARRAY
)
625 static void info_record_alloction(struct expression
*buffer
, struct range_list
*rl
)
632 name
= get_member_name(buffer
);
633 if (!name
&& is_static(buffer
))
634 name
= expr_to_var(buffer
);
637 if (rl
&& !is_whole_rl(rl
))
638 sql_insert_function_type_size(name
, show_rl(rl
));
640 sql_insert_function_type_size(name
, "(-1)");
645 static void store_alloc(struct expression
*expr
, struct range_list
*rl
)
647 rl
= clone_rl(rl
); // FIXME!!!
648 info_record_alloction(expr
, rl
);
649 set_state_expr(my_size_id
, expr
, alloc_estate_rl(rl
));
652 static void match_array_assignment(struct expression
*expr
)
654 struct expression
*left
;
655 struct expression
*right
;
656 struct range_list
*rl
;
661 left
= strip_expr(expr
->left
);
662 right
= strip_expr(expr
->right
);
663 right
= strip_ampersands(right
);
665 if (is_allocation_function(right
))
668 if (get_implied_value(right
, &sval
) && sval
.value
== 0) {
669 rl
= alloc_int_rl(0);
673 rl
= get_array_size_bytes_rl(right
);
676 store_alloc(left
, rl
);
679 static void match_alloc(const char *fn
, struct expression
*expr
, void *_size_arg
)
681 int size_arg
= PTR_INT(_size_arg
);
682 struct expression
*right
;
683 struct expression
*arg
;
684 struct range_list
*rl
;
686 right
= strip_expr(expr
->right
);
687 arg
= get_argument_from_call_expr(right
->args
, size_arg
);
688 get_absolute_rl(arg
, &rl
);
689 rl
= cast_rl(&int_ctype
, rl
);
690 store_alloc(expr
->left
, rl
);
693 static void match_calloc(const char *fn
, struct expression
*expr
, void *unused
)
695 struct expression
*right
;
696 struct expression
*arg
;
700 right
= strip_expr(expr
->right
);
701 arg
= get_argument_from_call_expr(right
->args
, 0);
702 if (!get_implied_value(arg
, &elements
))
704 arg
= get_argument_from_call_expr(right
->args
, 1);
705 if (get_implied_value(arg
, &size
))
706 store_alloc(expr
->left
, size_to_rl(elements
.value
* size
.value
));
708 store_alloc(expr
->left
, size_to_rl(-1));
711 static void match_limited(const char *fn
, struct expression
*expr
, void *_limiter
)
713 struct limiter
*limiter
= (struct limiter
*)_limiter
;
714 struct expression
*dest
;
715 struct expression
*size_expr
;
718 dest
= get_argument_from_call_expr(expr
->args
, limiter
->buf_arg
);
719 size_expr
= get_argument_from_call_expr(expr
->args
, limiter
->limit_arg
);
720 if (!get_implied_max(size_expr
, &size
))
722 set_state_expr(my_size_id
, dest
, size_to_estate(size
.value
));
725 static void match_strcpy(const char *fn
, struct expression
*expr
, void *unused
)
727 struct expression fake_assign
;
729 fake_assign
.op
= '=';
730 fake_assign
.left
= get_argument_from_call_expr(expr
->args
, 0);
731 fake_assign
.right
= get_argument_from_call_expr(expr
->args
, 1);
732 match_array_assignment(&fake_assign
);
735 static void match_strndup(const char *fn
, struct expression
*expr
, void *unused
)
737 struct expression
*fn_expr
;
738 struct expression
*size_expr
;
741 fn_expr
= strip_expr(expr
->right
);
742 size_expr
= get_argument_from_call_expr(fn_expr
->args
, 1);
743 if (get_implied_max(size_expr
, &size
)) {
745 store_alloc(expr
->left
, size_to_rl(size
.value
));
747 store_alloc(expr
->left
, size_to_rl(-1));
752 static void match_call(struct expression
*expr
)
754 struct expression
*arg
;
755 struct range_list
*rl
;
759 FOR_EACH_PTR(expr
->args
, arg
) {
760 rl
= get_array_size_bytes_rl(arg
);
761 if (rl
&& !is_whole_rl(rl
))
762 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 smatch_state
*state
)
769 if (state
== &merged
)
771 sql_insert_caller_info(call
, BUF_SIZE
, param
, printed_name
, state
->name
);
774 void register_buf_size(int id
)
778 add_unmatched_state_hook(my_size_id
, &unmatched_size_state
);
780 select_caller_info_hook(set_param_buf_size
, BUF_SIZE
);
781 select_return_states_hook(BUF_SIZE
, &db_returns_buf_size
);
783 allocation_funcs
= create_function_hashtable(100);
784 add_allocation_function("malloc", &match_alloc
, 0);
785 add_allocation_function("calloc", &match_calloc
, 0);
786 add_allocation_function("memdup", &match_alloc
, 1);
787 if (option_project
== PROJ_KERNEL
) {
788 add_allocation_function("kmalloc", &match_alloc
, 0);
789 add_allocation_function("kzalloc", &match_alloc
, 0);
790 add_allocation_function("vmalloc", &match_alloc
, 0);
791 add_allocation_function("__vmalloc", &match_alloc
, 0);
792 add_allocation_function("kcalloc", &match_calloc
, 0);
793 add_allocation_function("kmalloc_array", &match_calloc
, 0);
794 add_allocation_function("drm_malloc_ab", &match_calloc
, 0);
795 add_allocation_function("drm_calloc_large", &match_calloc
, 0);
796 add_allocation_function("sock_kmalloc", &match_alloc
, 1);
797 add_allocation_function("kmemdup", &match_alloc
, 1);
798 add_allocation_function("kmemdup_user", &match_alloc
, 1);
799 add_allocation_function("dma_alloc_attrs", &match_alloc
, 1);
800 add_allocation_function("pci_alloc_consistent", &match_alloc
, 1);
801 add_allocation_function("pci_alloc_coherent", &match_alloc
, 1);
802 add_allocation_function("devm_kmalloc", &match_alloc
, 1);
803 add_allocation_function("devm_kzalloc", &match_alloc
, 1);
805 add_hook(&match_strlen_condition
, CONDITION_HOOK
);
807 add_allocation_function("strndup", match_strndup
, 0);
808 if (option_project
== PROJ_KERNEL
)
809 add_allocation_function("kstrndup", match_strndup
, 0);
811 add_modification_hook(my_size_id
, &set_size_undefined
);
813 add_merge_hook(my_size_id
, &merge_size_func
);
816 void register_buf_size_late(int id
)
818 /* has to happen after match_alloc() */
819 add_hook(&match_array_assignment
, ASSIGNMENT_HOOK
);
821 add_function_hook("strlcpy", &match_limited
, &b0_l2
);
822 add_function_hook("strlcat", &match_limited
, &b0_l2
);
823 add_function_hook("memscan", &match_limited
, &b0_l2
);
825 add_function_hook("strcpy", &match_strcpy
, NULL
);
827 add_hook(&match_call
, FUNCTION_CALL_HOOK
);
828 add_member_info_callback(my_size_id
, struct_member_callback
);