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
;
34 static struct limiter b0_l2
= {0, 2};
36 static DEFINE_HASHTABLE_INSERT(insert_func
, char, int);
37 static DEFINE_HASHTABLE_SEARCH(search_func
, char, int);
38 static struct hashtable
*allocation_funcs
;
40 static char *get_fn_name(struct expression
*expr
)
42 if (expr
->type
!= EXPR_CALL
)
44 if (expr
->fn
->type
!= EXPR_SYMBOL
)
46 return expr_to_var(expr
->fn
);
49 static int is_allocation_function(struct expression
*expr
)
54 func
= get_fn_name(expr
);
57 if (search_func(allocation_funcs
, func
))
63 static void add_allocation_function(const char *func
, void *call_back
, int param
)
65 insert_func(allocation_funcs
, (char *)func
, (int *)1);
66 add_function_assign_hook(func
, call_back
, INT_PTR(param
));
69 static int estate_to_size(struct smatch_state
*state
)
73 if (!state
|| !estate_rl(state
))
75 sval
= estate_max(state
);
79 static struct smatch_state
*size_to_estate(int size
)
83 sval
.type
= &int_ctype
;
86 return alloc_estate_sval(sval
);
89 static struct range_list
*size_to_rl(int size
)
93 sval
.type
= &int_ctype
;
96 return alloc_rl(sval
, sval
);
99 static struct smatch_state
*unmatched_size_state(struct sm_state
*sm
)
101 return size_to_estate(UNKNOWN_SIZE
);
104 static void set_size_undefined(struct sm_state
*sm
, struct expression
*mod_expr
)
106 set_state(sm
->owner
, sm
->name
, sm
->sym
, size_to_estate(UNKNOWN_SIZE
));
109 static struct smatch_state
*merge_size_func(struct smatch_state
*s1
, struct smatch_state
*s2
)
111 return merge_estates(s1
, s2
);
114 void set_param_buf_size(const char *name
, struct symbol
*sym
, char *key
, char *value
)
116 struct range_list
*rl
= NULL
;
117 struct smatch_state
*state
;
120 if (strncmp(key
, "$", 1) != 0)
123 snprintf(fullname
, 256, "%s%s", name
, key
+ 1);
125 str_to_rl(&int_ctype
, value
, &rl
);
126 if (!rl
|| is_whole_rl(rl
))
128 state
= alloc_estate_rl(rl
);
129 set_state(my_size_id
, fullname
, sym
, state
);
132 static int bytes_per_element(struct expression
*expr
)
136 if (expr
->type
== EXPR_STRING
)
138 type
= get_type(expr
);
142 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
)
145 type
= get_base_type(type
);
146 return type_bytes(type
);
149 static int bytes_to_elements(struct expression
*expr
, int bytes
)
153 bpe
= bytes_per_element(expr
);
159 static int elements_to_bytes(struct expression
*expr
, int elements
)
163 bpe
= bytes_per_element(expr
);
164 return elements
* bpe
;
167 static int get_initializer_size(struct expression
*expr
)
169 switch (expr
->type
) {
171 return expr
->string
->length
;
172 case EXPR_INITIALIZER
: {
173 struct expression
*tmp
;
176 FOR_EACH_PTR(expr
->expr_list
, tmp
) {
177 if (tmp
->type
== EXPR_INDEX
) {
178 if (tmp
->idx_to
>= i
)
185 } END_FOR_EACH_PTR(tmp
);
189 return get_array_size(expr
);
194 static struct range_list
*db_size_rl
;
195 static int db_size_callback(void *unused
, int argc
, char **argv
, char **azColName
)
197 struct range_list
*tmp
= NULL
;
200 str_to_rl(&int_ctype
, argv
[0], &db_size_rl
);
202 str_to_rl(&int_ctype
, argv
[0], &tmp
);
203 db_size_rl
= rl_union(db_size_rl
, tmp
);
208 static struct range_list
*size_from_db(struct expression
*expr
)
210 int this_file_only
= 0;
213 name
= get_member_name(expr
);
214 if (!name
&& is_static(expr
)) {
215 name
= expr_to_var(expr
);
221 if (this_file_only
) {
223 run_sql(db_size_callback
, NULL
,
224 "select size from function_type_size where type = '%s' and file = '%s';",
225 name
, get_filename());
232 run_sql(db_size_callback
, NULL
,
233 "select size from type_size where type = '%s';",
238 static void db_returns_buf_size(struct expression
*expr
, int param
, char *unused
, char *math
)
240 struct expression
*call
;
243 if (expr
->type
!= EXPR_ASSIGNMENT
)
245 call
= strip_expr(expr
->right
);
247 if (!parse_call_math(call
, math
, &sval
))
249 set_state_expr(my_size_id
, expr
->left
, size_to_estate(sval
.value
));
252 int get_real_array_size(struct expression
*expr
)
257 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
260 type
= get_type(expr
);
263 if (!type
|| type
->type
!= SYM_ARRAY
)
266 if (!get_implied_value(type
->array_size
, &sval
))
269 /* People put one element arrays on the end of structs */
276 static int get_size_from_initializer(struct expression
*expr
)
278 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
|| !expr
->symbol
->initializer
)
280 if (expr
->symbol
->initializer
== expr
) /* int a = a; */
282 return get_initializer_size(expr
->symbol
->initializer
);
285 static struct range_list
*get_stored_size_bytes(struct expression
*expr
)
287 struct smatch_state
*state
;
289 state
= get_state_expr(my_size_id
, expr
);
292 return estate_rl(state
);
295 static int get_bytes_from_address(struct expression
*expr
)
302 if (expr
->type
!= EXPR_PREOP
|| expr
->op
!= '&')
304 type
= get_type(expr
);
308 if (type
->type
== SYM_PTR
)
309 type
= get_base_type(type
);
311 ret
= type_bytes(type
);
313 return 0; /* ignore char pointers */
318 static struct expression
*remove_addr_fluff(struct expression
*expr
)
320 struct expression
*tmp
;
323 expr
= strip_expr(expr
);
325 /* remove '&' and '*' operations that cancel */
326 while (expr
&& expr
->type
== EXPR_PREOP
&& expr
->op
== '&') {
327 tmp
= strip_expr(expr
->unop
);
328 if (tmp
->type
!= EXPR_PREOP
)
332 expr
= strip_expr(tmp
->unop
);
338 /* "foo + 0" is just "foo" */
339 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+' &&
340 get_value(expr
->right
, &sval
) && sval
.value
== 0)
346 static int is_last_member_of_struct(struct symbol
*sym
, struct ident
*member
)
352 FOR_EACH_PTR_REVERSE(sym
->symbol_list
, tmp
) {
353 if (i
++ || !tmp
->ident
)
355 if (tmp
->ident
== member
)
358 } END_FOR_EACH_PTR_REVERSE(tmp
);
363 static int get_stored_size_end_struct_bytes(struct expression
*expr
)
368 struct smatch_state
*state
;
371 if (expr
->type
== EXPR_BINOP
) /* array elements foo[5] */
374 type
= get_type(expr
);
375 if (!type
|| type
->type
!= SYM_ARRAY
)
378 if (!get_implied_value(type
->array_size
, &sval
))
381 if (sval
.value
!= 0 && sval
.value
!= 1)
384 name
= expr_to_var_sym(expr
, &sym
);
386 if (!sym
|| !sym
->ident
)
388 if (!type_bytes(sym
))
391 if (sym
->type
!= SYM_NODE
)
394 state
= get_state(my_size_id
, sym
->ident
->name
, sym
);
395 if (!estate_to_size(state
))
398 sym
= get_real_base_type(sym
);
399 if (!sym
|| sym
->type
!= SYM_PTR
)
401 sym
= get_real_base_type(sym
);
402 if (!sym
|| sym
->type
!= SYM_STRUCT
)
404 if (!is_last_member_of_struct(sym
, expr
->member
))
407 return estate_to_size(state
) - type_bytes(sym
) + type_bytes(type
);
410 static struct range_list
*alloc_int_rl(int value
)
417 return alloc_rl(sval
, sval
);
420 struct range_list
*get_array_size_bytes_rl(struct expression
*expr
)
422 int declared_size
= 0;
423 struct range_list
*ret
= NULL
;
426 expr
= remove_addr_fluff(expr
);
431 if (expr
->type
== EXPR_STRING
)
432 return alloc_int_rl(expr
->string
->length
);
434 if (expr
->type
== EXPR_BINOP
&& expr
->op
== '+') {
437 if (!get_implied_value(expr
->right
, &offset
))
439 size
= get_array_size_bytes(expr
->left
);
442 return alloc_int_rl(size
- offset
.value
);
446 size
= get_real_array_size(expr
);
448 declared_size
= elements_to_bytes(expr
, size
);
450 /* buf = malloc(1024); */
451 ret
= get_stored_size_bytes(expr
);
454 return rl_union(ret
, alloc_int_rl(size
));
458 return alloc_int_rl(declared_size
);
460 size
= get_stored_size_end_struct_bytes(expr
);
462 return alloc_int_rl(size
);
464 /* char *foo = "BAR" */
465 size
= get_size_from_initializer(expr
);
467 return alloc_int_rl(elements_to_bytes(expr
, size
));
469 size
= get_bytes_from_address(expr
);
471 return alloc_int_rl(size
);
473 /* if (strlen(foo) > 4) */
474 size
= get_size_from_strlen(expr
);
476 return alloc_int_rl(size
);
478 ret
= size_from_db(expr
);
485 int get_array_size_bytes(struct expression
*expr
)
487 struct range_list
*rl
;
490 rl
= get_array_size_bytes_rl(expr
);
491 if (!rl_to_sval(rl
, &sval
))
493 if (sval
.uvalue
>= INT_MAX
)
498 int get_array_size_bytes_max(struct expression
*expr
)
500 struct range_list
*rl
;
503 rl
= get_array_size_bytes_rl(expr
);
510 if (bytes
.uvalue
>= INT_MAX
)
515 int get_array_size_bytes_min(struct expression
*expr
)
517 struct range_list
*rl
;
518 struct data_range
*range
;
520 rl
= get_array_size_bytes_rl(expr
);
524 FOR_EACH_PTR(rl
, range
) {
525 if (range
->min
.value
<= 0)
527 if (range
->max
.value
<= 0)
529 if (range
->min
.uvalue
>= INT_MAX
)
531 return range
->min
.value
;
532 } END_FOR_EACH_PTR(range
);
537 int get_array_size(struct expression
*expr
)
539 return bytes_to_elements(expr
, get_array_size_bytes_max(expr
));
542 static void match_strlen_condition(struct expression
*expr
)
544 struct expression
*left
;
545 struct expression
*right
;
546 struct expression
*str
= NULL
;
548 int strlen_right
= 0;
550 struct smatch_state
*true_state
= NULL
;
551 struct smatch_state
*false_state
= NULL
;
553 if (expr
->type
!= EXPR_COMPARE
)
555 left
= strip_expr(expr
->left
);
556 right
= strip_expr(expr
->right
);
558 if (left
->type
== EXPR_CALL
&& sym_name_is("strlen", left
->fn
)) {
559 str
= get_argument_from_call_expr(left
->args
, 0);
562 if (right
->type
== EXPR_CALL
&& sym_name_is("strlen", right
->fn
)) {
563 str
= get_argument_from_call_expr(right
->args
, 0);
567 if (!strlen_left
&& !strlen_right
)
569 if (strlen_left
&& strlen_right
)
573 if (!get_value(right
, &sval
))
577 if (!get_value(left
, &sval
))
581 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
583 if (expr
->op
== SPECIAL_EQUAL
) {
584 set_true_false_states_expr(my_size_id
, str
, size_to_estate(sval
.value
+ 1), NULL
);
587 if (expr
->op
== SPECIAL_NOTEQUAL
) {
588 set_true_false_states_expr(my_size_id
, str
, NULL
, size_to_estate(sval
.value
+ 1));
594 case SPECIAL_UNSIGNED_LT
:
596 true_state
= size_to_estate(sval
.value
);
598 false_state
= size_to_estate(sval
.value
+ 1);
601 case SPECIAL_UNSIGNED_LTE
:
603 true_state
= size_to_estate(sval
.value
+ 1);
605 false_state
= size_to_estate(sval
.value
);
608 case SPECIAL_UNSIGNED_GTE
:
610 false_state
= size_to_estate(sval
.value
);
612 true_state
= size_to_estate(sval
.value
+ 1);
615 case SPECIAL_UNSIGNED_GT
:
617 true_state
= size_to_estate(-1);
618 false_state
= size_to_estate(sval
.value
+ 1);
620 true_state
= size_to_estate(sval
.value
);
623 set_true_false_states_expr(my_size_id
, str
, true_state
, false_state
);
626 static struct expression
*strip_ampersands(struct expression
*expr
)
630 if (expr
->type
!= EXPR_PREOP
)
634 type
= get_type(expr
->unop
);
635 if (!type
|| type
->type
!= SYM_ARRAY
)
640 static void info_record_alloction(struct expression
*buffer
, struct range_list
*rl
)
647 name
= get_member_name(buffer
);
648 if (!name
&& is_static(buffer
))
649 name
= expr_to_var(buffer
);
652 if (rl
&& !is_whole_rl(rl
))
653 sql_insert_function_type_size(name
, show_rl(rl
));
655 sql_insert_function_type_size(name
, "(-1)");
660 static void store_alloc(struct expression
*expr
, struct range_list
*rl
)
662 rl
= clone_rl(rl
); // FIXME!!!
663 info_record_alloction(expr
, rl
);
664 set_state_expr(my_size_id
, expr
, alloc_estate_rl(rl
));
667 static void match_array_assignment(struct expression
*expr
)
669 struct expression
*left
;
670 struct expression
*right
;
671 char *left_member
, *right_member
;
672 struct range_list
*rl
;
677 left
= strip_expr(expr
->left
);
678 right
= strip_expr(expr
->right
);
679 right
= strip_ampersands(right
);
681 if (!is_pointer(left
))
683 if (is_allocation_function(right
))
686 left_member
= get_member_name(left
);
687 right_member
= get_member_name(right
);
688 if (left_member
&& right_member
&& strcmp(left_member
, right_member
) == 0) {
689 free_string(left_member
);
690 free_string(right_member
);
693 free_string(left_member
);
694 free_string(right_member
);
696 if (get_implied_value(right
, &sval
) && sval
.value
== 0) {
697 rl
= alloc_int_rl(0);
701 rl
= get_array_size_bytes_rl(right
);
704 store_alloc(left
, rl
);
707 static void match_alloc(const char *fn
, struct expression
*expr
, void *_size_arg
)
709 int size_arg
= PTR_INT(_size_arg
);
710 struct expression
*right
;
711 struct expression
*arg
;
712 struct range_list
*rl
;
714 right
= strip_expr(expr
->right
);
715 arg
= get_argument_from_call_expr(right
->args
, size_arg
);
716 get_absolute_rl(arg
, &rl
);
717 rl
= cast_rl(&int_ctype
, rl
);
718 store_alloc(expr
->left
, rl
);
721 static void match_calloc(const char *fn
, struct expression
*expr
, void *unused
)
723 struct expression
*right
;
724 struct expression
*arg
;
728 right
= strip_expr(expr
->right
);
729 arg
= get_argument_from_call_expr(right
->args
, 0);
730 if (!get_implied_value(arg
, &elements
))
732 arg
= get_argument_from_call_expr(right
->args
, 1);
733 if (get_implied_value(arg
, &size
))
734 store_alloc(expr
->left
, size_to_rl(elements
.value
* size
.value
));
736 store_alloc(expr
->left
, size_to_rl(-1));
739 static void match_limited(const char *fn
, struct expression
*expr
, void *_limiter
)
741 struct limiter
*limiter
= (struct limiter
*)_limiter
;
742 struct expression
*dest
;
743 struct expression
*size_expr
;
746 dest
= get_argument_from_call_expr(expr
->args
, limiter
->buf_arg
);
747 size_expr
= get_argument_from_call_expr(expr
->args
, limiter
->limit_arg
);
748 if (!get_implied_max(size_expr
, &size
))
750 set_state_expr(my_size_id
, dest
, size_to_estate(size
.value
));
753 static void match_strcpy(const char *fn
, struct expression
*expr
, void *unused
)
755 struct expression fake_assign
;
757 fake_assign
.op
= '=';
758 fake_assign
.left
= get_argument_from_call_expr(expr
->args
, 0);
759 fake_assign
.right
= get_argument_from_call_expr(expr
->args
, 1);
760 match_array_assignment(&fake_assign
);
763 static void match_strndup(const char *fn
, struct expression
*expr
, void *unused
)
765 struct expression
*fn_expr
;
766 struct expression
*size_expr
;
769 fn_expr
= strip_expr(expr
->right
);
770 size_expr
= get_argument_from_call_expr(fn_expr
->args
, 1);
771 if (get_implied_max(size_expr
, &size
)) {
773 store_alloc(expr
->left
, size_to_rl(size
.value
));
775 store_alloc(expr
->left
, size_to_rl(-1));
780 static void match_call(struct expression
*expr
)
782 struct expression
*arg
;
784 struct range_list
*rl
;
788 FOR_EACH_PTR(expr
->args
, arg
) {
790 type
= get_type(arg
);
791 if (!type
|| (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
))
793 rl
= get_array_size_bytes_rl(arg
);
798 sql_insert_caller_info(expr
, BUF_SIZE
, i
, "$", show_rl(rl
));
799 } END_FOR_EACH_PTR(arg
);
802 static void struct_member_callback(struct expression
*call
, int param
, char *printed_name
, struct smatch_state
*state
)
804 if (state
== &merged
)
806 sql_insert_caller_info(call
, BUF_SIZE
, param
, printed_name
, state
->name
);
809 void register_buf_size(int id
)
813 add_unmatched_state_hook(my_size_id
, &unmatched_size_state
);
815 select_caller_info_hook(set_param_buf_size
, BUF_SIZE
);
816 select_return_states_hook(BUF_SIZE
, &db_returns_buf_size
);
818 allocation_funcs
= create_function_hashtable(100);
819 add_allocation_function("malloc", &match_alloc
, 0);
820 add_allocation_function("calloc", &match_calloc
, 0);
821 add_allocation_function("memdup", &match_alloc
, 1);
822 add_allocation_function("realloc", &match_alloc
, 1);
823 if (option_project
== PROJ_KERNEL
) {
824 add_allocation_function("kmalloc", &match_alloc
, 0);
825 add_allocation_function("kzalloc", &match_alloc
, 0);
826 add_allocation_function("vmalloc", &match_alloc
, 0);
827 add_allocation_function("__vmalloc", &match_alloc
, 0);
828 add_allocation_function("kcalloc", &match_calloc
, 0);
829 add_allocation_function("kmalloc_array", &match_calloc
, 0);
830 add_allocation_function("drm_malloc_ab", &match_calloc
, 0);
831 add_allocation_function("drm_calloc_large", &match_calloc
, 0);
832 add_allocation_function("sock_kmalloc", &match_alloc
, 1);
833 add_allocation_function("kmemdup", &match_alloc
, 1);
834 add_allocation_function("kmemdup_user", &match_alloc
, 1);
835 add_allocation_function("dma_alloc_attrs", &match_alloc
, 1);
836 add_allocation_function("pci_alloc_consistent", &match_alloc
, 1);
837 add_allocation_function("pci_alloc_coherent", &match_alloc
, 1);
838 add_allocation_function("devm_kmalloc", &match_alloc
, 1);
839 add_allocation_function("devm_kzalloc", &match_alloc
, 1);
840 add_allocation_function("krealloc", &match_alloc
, 1);
842 add_hook(&match_strlen_condition
, CONDITION_HOOK
);
844 add_allocation_function("strndup", match_strndup
, 0);
845 if (option_project
== PROJ_KERNEL
)
846 add_allocation_function("kstrndup", match_strndup
, 0);
848 add_modification_hook(my_size_id
, &set_size_undefined
);
850 add_merge_hook(my_size_id
, &merge_size_func
);
853 void register_buf_size_late(int id
)
855 /* has to happen after match_alloc() */
856 add_hook(&match_array_assignment
, ASSIGNMENT_HOOK
);
858 add_function_hook("strlcpy", &match_limited
, &b0_l2
);
859 add_function_hook("strlcat", &match_limited
, &b0_l2
);
860 add_function_hook("memscan", &match_limited
, &b0_l2
);
862 add_function_hook("strcpy", &match_strcpy
, NULL
);
864 add_hook(&match_call
, FUNCTION_CALL_HOOK
);
865 add_member_info_callback(my_size_id
, struct_member_callback
);