2 * Copyright (C) 2012 Oracle.
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
19 * The point here is to store that a buffer has x bytes even if we don't know
25 #include "smatch_extra.h"
26 #include "smatch_slist.h"
32 * There is a bunch of code which does this:
37 * So if "size" is non-zero then the size of "foo" is size. But really it's
38 * also true if size is zero. It's just better to assume to not trample over
39 * the data that we have by merging &undefined states.
42 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
47 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
49 struct expression
*expr1
, *expr2
;
54 if (expr1
&& expr2
&& expr_equiv(expr1
, expr2
))
59 static void match_link_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
61 struct expression
*expr
;
64 expr
= sm
->state
->data
;
66 set_state_expr(size_id
, expr
, &undefined
);
67 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
71 FOR_EACH_PTR(sm
->possible
, tmp
) {
72 expr
= tmp
->state
->data
;
74 set_state_expr(size_id
, expr
, &undefined
);
75 } END_FOR_EACH_PTR(tmp
);
76 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
79 static const char *limit_map
[] = {
87 int state_to_limit(struct smatch_state
*state
)
91 if (!state
|| !state
->data
)
94 for (i
= 0; i
< ARRAY_SIZE(limit_map
); i
++) {
95 if (strncmp(state
->name
, limit_map
[i
], strlen(limit_map
[i
])) == 0)
96 return i
+ BYTE_COUNT
;
102 const char *limit_type_str(unsigned int limit_type
)
104 if (limit_type
- BYTE_COUNT
>= ARRAY_SIZE(limit_map
)) {
105 sm_msg("internal: wrong size type %u", limit_type
);
109 return limit_map
[limit_type
- BYTE_COUNT
];
112 static struct smatch_state
*alloc_compare_size(int limit_type
, struct expression
*expr
)
114 struct smatch_state
*state
;
118 state
= __alloc_smatch_state(0);
119 expr
= strip_expr(expr
);
120 name
= expr_to_str(expr
);
121 snprintf(buf
, sizeof(buf
), "%s %s", limit_type_str(limit_type
), name
);
122 state
->name
= alloc_sname(buf
);
128 static int bytes_per_element(struct expression
*expr
)
132 type
= get_type(expr
);
136 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
)
139 type
= get_base_type(type
);
140 return type_bytes(type
);
143 static void db_save_type_links(struct expression
*array
, int type_limit
, struct expression
*size
)
145 const char *array_name
;
147 array_name
= get_data_info_name(array
);
150 sql_insert_data_info(size
, type_limit
, array_name
);
153 static void match_alloc_helper(struct expression
*pointer
, struct expression
*size
)
155 struct smatch_state
*state
;
156 struct expression
*tmp
;
158 int limit_type
= ELEM_COUNT
;
161 pointer
= strip_expr(pointer
);
162 size
= strip_expr(size
);
163 if (!size
|| !pointer
)
166 tmp
= get_assigned_expr_recurse(size
);
167 if (tmp
&& tmp
->op
== EXPR_BINOP
)
168 size
= strip_expr(tmp
);
170 if (size
->type
== EXPR_BINOP
&& size
->op
== '*') {
171 struct expression
*mult_left
, *mult_right
;
173 mult_left
= strip_expr(size
->left
);
174 mult_right
= strip_expr(size
->right
);
176 if (get_implied_value(mult_left
, &sval
) &&
177 sval
.value
== bytes_per_element(pointer
))
179 else if (get_implied_value(mult_right
, &sval
) &&
180 sval
.value
== bytes_per_element(pointer
))
186 /* Only save links to variables, not fixed sizes */
187 if (get_value(size
, &sval
))
190 if (size
->type
== EXPR_BINOP
&& size
->op
== '+' &&
191 get_value(size
->right
, &sval
) && sval
.value
== 1) {
193 limit_type
= ELEM_LAST
;
196 db_save_type_links(pointer
, limit_type
, size
);
197 state
= alloc_compare_size(limit_type
, size
);
198 sm
= set_state_expr(size_id
, pointer
, state
);
201 set_state_expr(link_id
, size
, alloc_state_expr(pointer
));
204 static void match_alloc(const char *fn
, struct expression
*expr
, void *_size_arg
)
206 int size_arg
= PTR_INT(_size_arg
);
207 struct expression
*pointer
, *call
, *arg
;
209 pointer
= strip_expr(expr
->left
);
210 call
= strip_expr(expr
->right
);
211 arg
= get_argument_from_call_expr(call
->args
, size_arg
);
212 match_alloc_helper(pointer
, arg
);
215 static void match_calloc(const char *fn
, struct expression
*expr
, void *_start_arg
)
217 struct smatch_state
*state
;
218 int start_arg
= PTR_INT(_start_arg
);
219 struct expression
*pointer
, *call
, *arg
;
220 struct sm_state
*tmp
;
221 int limit_type
= ELEM_COUNT
;
224 pointer
= strip_expr(expr
->left
);
225 call
= strip_expr(expr
->right
);
226 arg
= get_argument_from_call_expr(call
->args
, start_arg
);
227 if (get_implied_value(arg
, &sval
) &&
228 sval
.value
== bytes_per_element(pointer
))
229 arg
= get_argument_from_call_expr(call
->args
, start_arg
+ 1);
231 if (arg
->type
== EXPR_BINOP
&& arg
->op
== '+' &&
232 get_value(arg
->right
, &sval
) && sval
.value
== 1) {
234 limit_type
= ELEM_LAST
;
237 state
= alloc_compare_size(limit_type
, arg
);
238 db_save_type_links(pointer
, limit_type
, arg
);
239 tmp
= set_state_expr(size_id
, pointer
, state
);
242 set_state_expr(link_id
, arg
, alloc_state_expr(pointer
));
245 static struct expression
*get_size_variable_from_binop(struct expression
*expr
, int *limit_type
)
247 struct smatch_state
*state
;
248 struct expression
*ret
;
254 if (!get_value(expr
->right
, &offset
))
256 state
= get_state_expr(size_id
, expr
->left
);
257 if (!state
|| !state
->data
)
260 type
= get_type(expr
->left
);
261 if (!type_is_ptr(type
))
263 type
= get_real_base_type(type
);
264 if (!type_bytes(type
))
266 offset_bytes
= offset
.value
* type_bytes(type
);
269 if (ret
->type
!= EXPR_BINOP
|| ret
->op
!= '+')
272 *limit_type
= state_to_limit(state
);
274 if (get_value(ret
->left
, &orig_fixed
) && orig_fixed
.value
== offset_bytes
)
276 if (get_value(ret
->right
, &orig_fixed
) && orig_fixed
.value
== offset_bytes
)
282 struct expression
*get_size_variable(struct expression
*buf
, int *limit_type
)
284 struct smatch_state
*state
;
285 struct expression
*ret
;
287 buf
= strip_expr(buf
);
290 if (buf
->type
== EXPR_BINOP
&& buf
->op
== '+') {
291 ret
= get_size_variable_from_binop(buf
, limit_type
);
296 state
= get_state_expr(size_id
, buf
);
299 *limit_type
= state_to_limit(state
);
303 struct expression
*get_array_variable(struct expression
*size
)
305 struct smatch_state
*state
;
307 state
= get_state_expr(link_id
, size
);
313 static void array_check(struct expression
*expr
)
315 struct expression
*array
;
316 struct expression
*size
;
317 struct expression
*offset
;
318 char *array_str
, *offset_str
;
321 expr
= strip_expr(expr
);
325 array
= get_array_base(expr
);
326 size
= get_size_variable(array
, &limit_type
);
329 if (limit_type
!= ELEM_COUNT
)
331 offset
= get_array_offset(expr
);
332 if (!possible_comparison(size
, SPECIAL_EQUAL
, offset
))
334 if (getting_address(expr
))
337 array_str
= expr_to_str(array
);
338 offset_str
= expr_to_str(offset
);
339 sm_warning("potentially one past the end of array '%s[%s]'", array_str
, offset_str
);
340 free_string(array_str
);
341 free_string(offset_str
);
349 static int db_limitter_callback(void *_info
, int argc
, char **argv
, char **azColName
)
351 struct db_info
*info
= _info
;
354 * If possible the limitters are tied to the struct they limit. If we
355 * aren't sure which struct they limit then we use them as limitters for
358 if (!info
->name
|| argv
[0][0] == '\0' || strcmp(info
->name
, argv
[0]) == 0)
363 static char *vsl_to_data_info_name(const char *name
, struct var_sym_list
*vsl
)
370 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
372 vs
= first_ptr_list((struct ptr_list
*)vsl
);
374 type
= get_real_base_type(vs
->sym
);
375 if (!type
|| type
->type
!= SYM_PTR
)
377 type
= get_real_base_type(type
);
378 if (!type
|| type
->type
!= SYM_STRUCT
)
384 while ((name
= strstr(p
, "->")))
387 snprintf(buf
, sizeof(buf
),"(struct %s)->%s", type
->ident
->name
, p
);
388 return alloc_sname(buf
);
391 if (!(vs
->sym
->ctype
.modifiers
& MOD_TOPLEVEL
))
393 if (vs
->sym
->ctype
.modifiers
& MOD_STATIC
)
394 snprintf(buf
, sizeof(buf
),"static %s", name
);
396 snprintf(buf
, sizeof(buf
),"global %s", name
);
397 return alloc_sname(buf
);
400 int db_var_is_array_limit(struct expression
*array
, const char *name
, struct var_sym_list
*vsl
)
403 char *array_name
= get_data_info_name(array
);
404 struct db_info db_info
= {.name
= array_name
,};
406 size_name
= vsl_to_data_info_name(name
, vsl
);
410 run_sql(db_limitter_callback
, &db_info
,
411 "select value from data_info where type = %d and data = '%s';",
412 ARRAY_LEN
, size_name
);
417 int buf_comparison_index_ok(struct expression
*expr
)
419 struct expression
*array
;
420 struct expression
*size
;
421 struct expression
*offset
;
425 array
= get_array_base(expr
);
426 size
= get_size_variable(array
, &limit_type
);
429 offset
= get_array_offset(expr
);
430 comparison
= get_comparison(offset
, size
);
434 if ((limit_type
== ELEM_COUNT
|| limit_type
== ELEM_LAST
) &&
435 (comparison
== '<' || comparison
== SPECIAL_UNSIGNED_LT
))
437 if (limit_type
== ELEM_LAST
&&
438 (comparison
== SPECIAL_LTE
||
439 comparison
== SPECIAL_UNSIGNED_LTE
||
440 comparison
== SPECIAL_EQUAL
))
446 static int known_access_ok_numbers(struct expression
*expr
)
448 struct expression
*array
;
449 struct expression
*offset
;
453 array
= get_array_base(expr
);
454 offset
= get_array_offset(expr
);
456 size
= get_array_size(array
);
460 get_absolute_max(offset
, &max
);
461 if (max
.uvalue
< size
)
466 static void array_check_data_info(struct expression
*expr
)
468 struct expression
*array
;
469 struct expression
*offset
;
470 struct state_list
*slist
;
472 struct compare_data
*comp
;
474 const char *equal_name
= NULL
;
476 expr
= strip_expr(expr
);
480 if (known_access_ok_numbers(expr
))
482 if (buf_comparison_index_ok(expr
))
485 array
= get_array_base(expr
);
486 offset
= get_array_offset(expr
);
487 offset_name
= expr_to_var(offset
);
490 slist
= get_all_possible_equal_comparisons(offset
);
494 FOR_EACH_PTR(slist
, sm
) {
495 comp
= sm
->state
->data
;
496 if (strcmp(comp
->left_var
, offset_name
) == 0) {
497 if (db_var_is_array_limit(array
, comp
->right_var
, comp
->right_vsl
)) {
498 equal_name
= comp
->right_var
;
501 } else if (strcmp(comp
->right_var
, offset_name
) == 0) {
502 if (db_var_is_array_limit(array
, comp
->left_var
, comp
->left_vsl
)) {
503 equal_name
= comp
->left_var
;
507 } END_FOR_EACH_PTR(sm
);
510 char *array_name
= expr_to_str(array
);
512 sm_warning("potential off by one '%s[]' limit '%s'", array_name
, equal_name
);
513 free_string(array_name
);
518 free_string(offset_name
);
521 static void add_allocation_function(const char *func
, void *call_back
, int param
)
523 add_function_assign_hook(func
, call_back
, INT_PTR(param
));
526 static int is_sizeof(struct expression
*expr
)
530 if (expr
->type
== EXPR_SIZEOF
)
532 name
= pos_ident(expr
->pos
);
533 if (name
&& strcmp(name
, "sizeof") == 0)
538 static int match_size_binop(struct expression
*size
, struct expression
*expr
, int *limit_type
)
540 int orig_type
= *limit_type
;
541 struct expression
*left
;
545 if (!expr_equiv(size
, left
))
548 if (expr
->op
== '-' &&
549 get_value(expr
->right
, &sval
) &&
551 orig_type
== ELEM_COUNT
) {
552 *limit_type
= ELEM_LAST
;
556 if (expr
->op
== '+' &&
557 get_value(expr
->right
, &sval
) &&
559 orig_type
== ELEM_LAST
) {
560 *limit_type
= ELEM_COUNT
;
564 if (expr
->op
== '*' &&
565 is_sizeof(expr
->right
) &&
566 orig_type
== ELEM_COUNT
) {
567 *limit_type
= BYTE_COUNT
;
571 if (expr
->op
== '/' &&
572 is_sizeof(expr
->right
) &&
573 orig_type
== BYTE_COUNT
) {
574 *limit_type
= ELEM_COUNT
;
581 static char *buf_size_param_comparison(struct expression
*array
, struct expression_list
*args
, int *limit_type
)
583 struct expression
*tmp
, *arg
;
584 struct expression
*size
;
588 size
= get_size_variable(array
, limit_type
);
592 if (*limit_type
== USED_LAST
)
593 *limit_type
= ELEM_LAST
;
594 if (*limit_type
== USED_COUNT
)
595 *limit_type
= ELEM_COUNT
;
598 FOR_EACH_PTR(args
, tmp
) {
603 if (expr_equiv(arg
, size
) ||
604 (arg
->type
== EXPR_BINOP
&&
605 match_size_binop(size
, arg
, limit_type
))) {
606 snprintf(buf
, sizeof(buf
), "==$%d", i
);
609 } END_FOR_EACH_PTR(tmp
);
614 static void match_call(struct expression
*call
)
616 struct expression
*arg
;
623 FOR_EACH_PTR(call
->args
, arg
) {
625 if (!is_pointer(arg
))
627 compare
= buf_size_param_comparison(arg
, call
->args
, &limit_type
);
630 snprintf(buf
, sizeof(buf
), "%d", limit_type
);
631 sql_insert_caller_info(call
, limit_type
, param
, compare
, buf
);
632 } END_FOR_EACH_PTR(arg
);
635 static int get_param(int param
, char **name
, struct symbol
**sym
)
641 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, arg
) {
643 * this is a temporary hack to work around a bug (I think in sparse?)
644 * 2.6.37-rc1:fs/reiserfs/journal.o
645 * If there is a function definition without parameter name found
646 * after a function implementation then it causes a crash.
650 if (arg
->ident
->name
< (char *)100)
653 *name
= arg
->ident
->name
;
658 } END_FOR_EACH_PTR(arg
);
663 static void set_param_compare(const char *array_name
, struct symbol
*array_sym
, char *key
, char *value
)
665 struct smatch_state
*state
;
666 struct expression
*array_expr
;
667 struct expression
*size_expr
;
668 struct symbol
*size_sym
;
671 struct sm_state
*tmp
;
674 if (strncmp(key
, "==$", 3) != 0)
676 param
= strtol(key
+ 3, NULL
, 10);
677 if (!get_param(param
, &size_name
, &size_sym
))
679 array_expr
= symbol_expression(array_sym
);
680 size_expr
= symbol_expression(size_sym
);
681 limit_type
= strtol(value
, NULL
, 10);
683 state
= alloc_compare_size(limit_type
, size_expr
);
684 tmp
= set_state_expr(size_id
, array_expr
, state
);
687 set_state_expr(link_id
, size_expr
, alloc_state_expr(array_expr
));
690 static void set_implied(struct expression
*call
, struct expression
*array_expr
, char *key
, char *value
)
692 struct expression
*size_expr
;
693 struct symbol
*size_sym
;
696 struct sm_state
*tmp
;
699 if (strncmp(key
, "==$", 3) != 0)
701 param
= strtol(key
+ 3, NULL
, 10);
702 if (!get_param(param
, &size_name
, &size_sym
))
704 size_expr
= symbol_expression(size_sym
);
706 limit_type
= strtol(value
, NULL
, 10);
707 tmp
= set_state_expr(size_id
, array_expr
, alloc_compare_size(limit_type
, size_expr
));
710 set_state_expr(link_id
, size_expr
, alloc_state_expr(array_expr
));
713 static void munge_start_states(struct statement
*stmt
)
715 struct state_list
*slist
= NULL
;
717 struct sm_state
*poss
;
719 FOR_EACH_MY_SM(size_id
, __get_cur_stree(), sm
) {
720 if (sm
->state
!= &merged
)
723 * screw it. let's just assume that if one caller passes the
724 * size then they all do.
726 FOR_EACH_PTR(sm
->possible
, poss
) {
727 if (poss
->state
!= &merged
&&
728 poss
->state
!= &undefined
) {
729 add_ptr_list(&slist
, poss
);
732 } END_FOR_EACH_PTR(poss
);
733 } END_FOR_EACH_SM(sm
);
735 FOR_EACH_PTR(slist
, sm
) {
736 set_state(size_id
, sm
->name
, sm
->sym
, sm
->state
);
737 } END_FOR_EACH_PTR(sm
);
742 static void set_used(struct expression
*expr
)
744 struct expression
*parent
;
745 struct expression
*array
;
746 struct expression
*offset
;
747 struct sm_state
*tmp
;
750 if (expr
->op
!= SPECIAL_INCREMENT
)
753 limit_type
= USED_LAST
;
754 if (expr
->type
== EXPR_POSTOP
)
755 limit_type
= USED_COUNT
;
757 parent
= expr_get_parent_expr(expr
);
758 if (!parent
|| parent
->type
!= EXPR_BINOP
)
760 parent
= expr_get_parent_expr(parent
);
761 if (!parent
|| !is_array(parent
))
764 array
= get_array_base(parent
);
765 offset
= get_array_offset(parent
);
769 tmp
= set_state_expr(size_id
, array
, alloc_compare_size(limit_type
, offset
->unop
));
772 set_state_expr(link_id
, offset
->unop
, alloc_state_expr(array
));
775 static int match_assign_array(struct expression
*expr
)
781 static int match_assign_size(struct expression
*expr
)
783 struct expression
*right
, *size
, *array
;
784 struct smatch_state
*state
;
785 struct sm_state
*tmp
;
790 if (size
->type
== EXPR_BINOP
)
793 array
= get_array_variable(size
);
796 state
= get_state_expr(size_id
, array
);
797 if (!state
|| !state
->data
)
800 limit_type
= state_to_limit(state
);
804 if (right
->type
== EXPR_BINOP
&& !match_size_binop(size
, right
, &limit_type
))
807 tmp
= set_state_expr(size_id
, array
, alloc_compare_size(limit_type
, expr
->left
));
810 set_state_expr(link_id
, expr
->left
, alloc_state_expr(array
));
814 static void match_assign(struct expression
*expr
)
819 if (match_assign_array(expr
))
821 match_assign_size(expr
);
824 static void match_copy(const char *fn
, struct expression
*expr
, void *unused
)
826 struct expression
*src
, *size
;
827 int src_param
, size_param
;
829 src
= get_argument_from_call_expr(expr
->args
, 1);
830 size
= get_argument_from_call_expr(expr
->args
, 2);
831 src
= strip_expr(src
);
832 size
= strip_expr(size
);
835 if (src
->type
!= EXPR_SYMBOL
|| size
->type
!= EXPR_SYMBOL
)
838 src_param
= get_param_num_from_sym(src
->symbol
);
839 size_param
= get_param_num_from_sym(size
->symbol
);
840 if (src_param
< 0 || size_param
< 0)
843 sql_insert_cache(call_implies
, "'%s', '%s', 0, %d, %d, %d, '==$%d', '%d'",
844 get_base_file(), get_function(), fn_static(),
845 BYTE_COUNT
, src_param
, size_param
, BYTE_COUNT
);
848 void register_buf_comparison(int id
)
854 set_dynamic_states(size_id
);
856 add_unmatched_state_hook(size_id
, &unmatched_state
);
858 add_allocation_function("malloc", &match_alloc
, 0);
859 add_allocation_function("memdup", &match_alloc
, 1);
860 add_allocation_function("realloc", &match_alloc
, 1);
861 if (option_project
== PROJ_KERNEL
) {
862 add_allocation_function("kmalloc", &match_alloc
, 0);
863 add_allocation_function("kzalloc", &match_alloc
, 0);
864 add_allocation_function("vmalloc", &match_alloc
, 0);
865 add_allocation_function("__vmalloc", &match_alloc
, 0);
866 add_allocation_function("sock_kmalloc", &match_alloc
, 1);
867 add_allocation_function("kmemdup", &match_alloc
, 1);
868 add_allocation_function("memdup_user", &match_alloc
, 1);
869 add_allocation_function("dma_alloc_attrs", &match_alloc
, 1);
870 add_allocation_function("dma_alloc_coherent", &match_alloc
, 1);
871 add_allocation_function("devm_kmalloc", &match_alloc
, 1);
872 add_allocation_function("devm_kzalloc", &match_alloc
, 1);
873 add_allocation_function("kcalloc", &match_calloc
, 0);
874 add_allocation_function("devm_kcalloc", &match_calloc
, 1);
875 add_allocation_function("kmalloc_array", &match_calloc
, 0);
876 add_allocation_function("krealloc", &match_alloc
, 1);
878 add_function_hook("copy_from_user", &match_copy
, NULL
);
879 add_function_hook("__copy_from_user", &match_copy
, NULL
);
882 add_hook(&array_check
, OP_HOOK
);
883 add_hook(&array_check_data_info
, OP_HOOK
);
884 add_hook(&set_used
, OP_HOOK
);
886 add_hook(&match_call
, FUNCTION_CALL_HOOK
);
887 add_hook(&munge_start_states
, AFTER_DEF_HOOK
);
889 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
891 for (i
= BYTE_COUNT
; i
<= USED_COUNT
; i
++) {
892 select_call_implies_hook(i
, &set_implied
);
893 select_caller_info_hook(set_param_compare
, i
);
894 select_return_implies_hook(i
, &set_implied
);
898 void register_buf_comparison_links(int id
)
901 set_dynamic_states(link_id
);
902 add_merge_hook(link_id
, &merge_links
);
903 add_modification_hook(link_id
, &match_link_modify
);