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 expression
*tmp
;
157 int limit_type
= ELEM_COUNT
;
161 pointer
= strip_expr(pointer
);
162 size
= strip_expr(size
);
163 if (!size
|| !pointer
)
166 while ((tmp
= get_assigned_expr(size
))) {
167 size
= strip_expr(tmp
);
172 if (size
->type
== EXPR_BINOP
&& size
->op
== '*') {
173 struct expression
*mult_left
, *mult_right
;
175 mult_left
= strip_expr(size
->left
);
176 mult_right
= strip_expr(size
->right
);
178 if (get_implied_value(mult_left
, &sval
) &&
179 sval
.value
== bytes_per_element(pointer
))
181 else if (get_implied_value(mult_right
, &sval
) &&
182 sval
.value
== bytes_per_element(pointer
))
188 /* Only save links to variables, not fixed sizes */
189 if (get_value(size
, &sval
))
192 if (size
->type
== EXPR_BINOP
&& size
->op
== '+' &&
193 get_value(size
->right
, &sval
) && sval
.value
== 1) {
195 limit_type
= ELEM_LAST
;
198 db_save_type_links(pointer
, limit_type
, size
);
199 sm
= set_state_expr(size_id
, pointer
, alloc_compare_size(limit_type
, size
));
202 set_state_expr(link_id
, size
, alloc_state_expr(pointer
));
205 static void match_alloc(const char *fn
, struct expression
*expr
, void *_size_arg
)
207 int size_arg
= PTR_INT(_size_arg
);
208 struct expression
*pointer
, *call
, *arg
;
210 pointer
= strip_expr(expr
->left
);
211 call
= strip_expr(expr
->right
);
212 arg
= get_argument_from_call_expr(call
->args
, size_arg
);
213 match_alloc_helper(pointer
, arg
);
216 static void match_calloc(const char *fn
, struct expression
*expr
, void *_start_arg
)
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 db_save_type_links(pointer
, limit_type
, arg
);
238 tmp
= set_state_expr(size_id
, pointer
, alloc_compare_size(limit_type
, arg
));
241 set_state_expr(link_id
, arg
, alloc_state_expr(pointer
));
244 static struct expression
*get_size_variable_from_binop(struct expression
*expr
, int *limit_type
)
246 struct smatch_state
*state
;
247 struct expression
*ret
;
253 if (!get_value(expr
->right
, &offset
))
255 state
= get_state_expr(size_id
, expr
->left
);
256 if (!state
|| !state
->data
)
259 type
= get_type(expr
->left
);
260 if (!type_is_ptr(type
))
262 type
= get_real_base_type(type
);
263 if (!type_bytes(type
))
265 offset_bytes
= offset
.value
* type_bytes(type
);
268 if (ret
->type
!= EXPR_BINOP
|| ret
->op
!= '+')
271 *limit_type
= state_to_limit(state
);
273 if (get_value(ret
->left
, &orig_fixed
) && orig_fixed
.value
== offset_bytes
)
275 if (get_value(ret
->right
, &orig_fixed
) && orig_fixed
.value
== offset_bytes
)
281 struct expression
*get_size_variable(struct expression
*buf
, int *limit_type
)
283 struct smatch_state
*state
;
284 struct expression
*ret
;
286 buf
= strip_expr(buf
);
289 if (buf
->type
== EXPR_BINOP
&& buf
->op
== '+') {
290 ret
= get_size_variable_from_binop(buf
, limit_type
);
295 state
= get_state_expr(size_id
, buf
);
298 *limit_type
= state_to_limit(state
);
302 struct expression
*get_array_variable(struct expression
*size
)
304 struct smatch_state
*state
;
306 state
= get_state_expr(link_id
, size
);
312 static void array_check(struct expression
*expr
)
314 struct expression
*array
;
315 struct expression
*size
;
316 struct expression
*offset
;
317 char *array_str
, *offset_str
;
320 expr
= strip_expr(expr
);
324 array
= get_array_base(expr
);
325 size
= get_size_variable(array
, &limit_type
);
328 if (limit_type
!= ELEM_COUNT
)
330 offset
= get_array_offset(expr
);
331 if (!possible_comparison(size
, SPECIAL_EQUAL
, offset
))
334 array_str
= expr_to_str(array
);
335 offset_str
= expr_to_str(offset
);
336 sm_warning("potentially one past the end of array '%s[%s]'", array_str
, offset_str
);
337 free_string(array_str
);
338 free_string(offset_str
);
346 static int db_limitter_callback(void *_info
, int argc
, char **argv
, char **azColName
)
348 struct db_info
*info
= _info
;
351 * If possible the limitters are tied to the struct they limit. If we
352 * aren't sure which struct they limit then we use them as limitters for
355 if (!info
->name
|| argv
[0][0] == '\0' || strcmp(info
->name
, argv
[0]) == 0)
360 static char *vsl_to_data_info_name(const char *name
, struct var_sym_list
*vsl
)
367 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
369 vs
= first_ptr_list((struct ptr_list
*)vsl
);
371 type
= get_real_base_type(vs
->sym
);
372 if (!type
|| type
->type
!= SYM_PTR
)
374 type
= get_real_base_type(type
);
375 if (!type
|| type
->type
!= SYM_STRUCT
)
381 while ((name
= strstr(p
, "->")))
384 snprintf(buf
, sizeof(buf
),"(struct %s)->%s", type
->ident
->name
, p
);
385 return alloc_sname(buf
);
388 if (!(vs
->sym
->ctype
.modifiers
& MOD_TOPLEVEL
))
390 if (vs
->sym
->ctype
.modifiers
& MOD_STATIC
)
391 snprintf(buf
, sizeof(buf
),"static %s", name
);
393 snprintf(buf
, sizeof(buf
),"global %s", name
);
394 return alloc_sname(buf
);
397 int db_var_is_array_limit(struct expression
*array
, const char *name
, struct var_sym_list
*vsl
)
400 char *array_name
= get_data_info_name(array
);
401 struct db_info db_info
= {.name
= array_name
,};
403 size_name
= vsl_to_data_info_name(name
, vsl
);
407 run_sql(db_limitter_callback
, &db_info
,
408 "select value from data_info where type = %d and data = '%s';",
409 ARRAY_LEN
, size_name
);
414 int buf_comparison_index_ok(struct expression
*expr
)
416 struct expression
*array
;
417 struct expression
*size
;
418 struct expression
*offset
;
422 array
= get_array_base(expr
);
423 size
= get_size_variable(array
, &limit_type
);
426 offset
= get_array_offset(expr
);
427 comparison
= get_comparison(offset
, size
);
431 if ((limit_type
== ELEM_COUNT
|| limit_type
== ELEM_LAST
) &&
432 (comparison
== '<' || comparison
== SPECIAL_UNSIGNED_LT
))
434 if (limit_type
== ELEM_LAST
&&
435 (comparison
== SPECIAL_LTE
||
436 comparison
== SPECIAL_UNSIGNED_LTE
||
437 comparison
== SPECIAL_EQUAL
))
443 static int known_access_ok_numbers(struct expression
*expr
)
445 struct expression
*array
;
446 struct expression
*offset
;
450 array
= get_array_base(expr
);
451 offset
= get_array_offset(expr
);
453 size
= get_array_size(array
);
457 get_absolute_max(offset
, &max
);
458 if (max
.uvalue
< size
)
463 static void array_check_data_info(struct expression
*expr
)
465 struct expression
*array
;
466 struct expression
*offset
;
467 struct state_list
*slist
;
469 struct compare_data
*comp
;
471 const char *equal_name
= NULL
;
473 expr
= strip_expr(expr
);
477 if (known_access_ok_numbers(expr
))
479 if (buf_comparison_index_ok(expr
))
482 array
= get_array_base(expr
);
483 offset
= get_array_offset(expr
);
484 offset_name
= expr_to_var(offset
);
487 slist
= get_all_possible_equal_comparisons(offset
);
491 FOR_EACH_PTR(slist
, sm
) {
492 comp
= sm
->state
->data
;
493 if (strcmp(comp
->left_var
, offset_name
) == 0) {
494 if (db_var_is_array_limit(array
, comp
->right_var
, comp
->right_vsl
)) {
495 equal_name
= comp
->right_var
;
498 } else if (strcmp(comp
->right_var
, offset_name
) == 0) {
499 if (db_var_is_array_limit(array
, comp
->left_var
, comp
->left_vsl
)) {
500 equal_name
= comp
->left_var
;
504 } END_FOR_EACH_PTR(sm
);
507 char *array_name
= expr_to_str(array
);
509 sm_warning("potential off by one '%s[]' limit '%s'", array_name
, equal_name
);
510 free_string(array_name
);
515 free_string(offset_name
);
518 static void add_allocation_function(const char *func
, void *call_back
, int param
)
520 add_function_assign_hook(func
, call_back
, INT_PTR(param
));
523 static int is_sizeof(struct expression
*expr
)
527 if (expr
->type
== EXPR_SIZEOF
)
529 name
= pos_ident(expr
->pos
);
530 if (name
&& strcmp(name
, "sizeof") == 0)
535 static int match_size_binop(struct expression
*size
, struct expression
*expr
, int *limit_type
)
537 int orig_type
= *limit_type
;
538 struct expression
*left
;
542 if (!expr_equiv(size
, left
))
545 if (expr
->op
== '-' &&
546 get_value(expr
->right
, &sval
) &&
548 orig_type
== ELEM_COUNT
) {
549 *limit_type
= ELEM_LAST
;
553 if (expr
->op
== '+' &&
554 get_value(expr
->right
, &sval
) &&
556 orig_type
== ELEM_LAST
) {
557 *limit_type
= ELEM_COUNT
;
561 if (expr
->op
== '*' &&
562 is_sizeof(expr
->right
) &&
563 orig_type
== ELEM_COUNT
) {
564 *limit_type
= BYTE_COUNT
;
568 if (expr
->op
== '/' &&
569 is_sizeof(expr
->right
) &&
570 orig_type
== BYTE_COUNT
) {
571 *limit_type
= ELEM_COUNT
;
578 static char *buf_size_param_comparison(struct expression
*array
, struct expression_list
*args
, int *limit_type
)
580 struct expression
*tmp
, *arg
;
581 struct expression
*size
;
585 size
= get_size_variable(array
, limit_type
);
589 if (*limit_type
== USED_LAST
)
590 *limit_type
= ELEM_LAST
;
591 if (*limit_type
== USED_COUNT
)
592 *limit_type
= ELEM_COUNT
;
595 FOR_EACH_PTR(args
, tmp
) {
600 if (expr_equiv(arg
, size
) ||
601 (arg
->type
== EXPR_BINOP
&&
602 match_size_binop(size
, arg
, limit_type
))) {
603 snprintf(buf
, sizeof(buf
), "==$%d", i
);
606 } END_FOR_EACH_PTR(tmp
);
611 static void match_call(struct expression
*call
)
613 struct expression
*arg
;
620 FOR_EACH_PTR(call
->args
, arg
) {
622 if (!is_pointer(arg
))
624 compare
= buf_size_param_comparison(arg
, call
->args
, &limit_type
);
627 snprintf(buf
, sizeof(buf
), "%d", limit_type
);
628 sql_insert_caller_info(call
, limit_type
, param
, compare
, buf
);
629 } END_FOR_EACH_PTR(arg
);
632 static int get_param(int param
, char **name
, struct symbol
**sym
)
638 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, arg
) {
640 * this is a temporary hack to work around a bug (I think in sparse?)
641 * 2.6.37-rc1:fs/reiserfs/journal.o
642 * If there is a function definition without parameter name found
643 * after a function implementation then it causes a crash.
647 if (arg
->ident
->name
< (char *)100)
650 *name
= arg
->ident
->name
;
655 } END_FOR_EACH_PTR(arg
);
660 static void set_param_compare(const char *array_name
, struct symbol
*array_sym
, char *key
, char *value
)
662 struct expression
*array_expr
;
663 struct expression
*size_expr
;
664 struct symbol
*size_sym
;
667 struct sm_state
*tmp
;
670 if (strncmp(key
, "==$", 3) != 0)
672 param
= strtol(key
+ 3, NULL
, 10);
673 if (!get_param(param
, &size_name
, &size_sym
))
675 array_expr
= symbol_expression(array_sym
);
676 size_expr
= symbol_expression(size_sym
);
677 limit_type
= strtol(value
, NULL
, 10);
679 tmp
= set_state_expr(size_id
, array_expr
, alloc_compare_size(limit_type
, size_expr
));
682 set_state_expr(link_id
, size_expr
, alloc_state_expr(array_expr
));
685 static void set_implied(struct expression
*call
, struct expression
*array_expr
, char *key
, char *value
)
687 struct expression
*size_expr
;
688 struct symbol
*size_sym
;
691 struct sm_state
*tmp
;
694 if (strncmp(key
, "==$", 3) != 0)
696 param
= strtol(key
+ 3, NULL
, 10);
697 if (!get_param(param
, &size_name
, &size_sym
))
699 size_expr
= symbol_expression(size_sym
);
701 limit_type
= strtol(value
, NULL
, 10);
702 tmp
= set_state_expr(size_id
, array_expr
, alloc_compare_size(limit_type
, size_expr
));
705 set_state_expr(link_id
, size_expr
, alloc_state_expr(array_expr
));
708 static void munge_start_states(struct statement
*stmt
)
710 struct state_list
*slist
= NULL
;
712 struct sm_state
*poss
;
714 FOR_EACH_MY_SM(size_id
, __get_cur_stree(), sm
) {
715 if (sm
->state
!= &merged
)
718 * screw it. let's just assume that if one caller passes the
719 * size then they all do.
721 FOR_EACH_PTR(sm
->possible
, poss
) {
722 if (poss
->state
!= &merged
&&
723 poss
->state
!= &undefined
) {
724 add_ptr_list(&slist
, poss
);
727 } END_FOR_EACH_PTR(poss
);
728 } END_FOR_EACH_SM(sm
);
730 FOR_EACH_PTR(slist
, sm
) {
731 set_state(size_id
, sm
->name
, sm
->sym
, sm
->state
);
732 } END_FOR_EACH_PTR(sm
);
737 static void set_used(struct expression
*expr
)
739 struct expression
*parent
;
740 struct expression
*array
;
741 struct expression
*offset
;
742 struct sm_state
*tmp
;
745 if (expr
->op
!= SPECIAL_INCREMENT
)
748 limit_type
= USED_LAST
;
749 if (expr
->type
== EXPR_POSTOP
)
750 limit_type
= USED_COUNT
;
752 parent
= expr_get_parent_expr(expr
);
753 if (!parent
|| parent
->type
!= EXPR_BINOP
)
755 parent
= expr_get_parent_expr(parent
);
756 if (!parent
|| !is_array(parent
))
759 array
= get_array_base(parent
);
760 offset
= get_array_offset(parent
);
764 tmp
= set_state_expr(size_id
, array
, alloc_compare_size(limit_type
, offset
->unop
));
767 set_state_expr(link_id
, offset
->unop
, alloc_state_expr(array
));
770 static int match_assign_array(struct expression
*expr
)
776 static int match_assign_size(struct expression
*expr
)
778 struct expression
*right
, *size
, *array
;
779 struct smatch_state
*state
;
780 struct sm_state
*tmp
;
785 if (size
->type
== EXPR_BINOP
)
788 array
= get_array_variable(size
);
791 state
= get_state_expr(size_id
, array
);
792 if (!state
|| !state
->data
)
795 limit_type
= state_to_limit(state
);
799 if (right
->type
== EXPR_BINOP
&& !match_size_binop(size
, right
, &limit_type
))
802 tmp
= set_state_expr(size_id
, array
, alloc_compare_size(limit_type
, expr
->left
));
805 set_state_expr(link_id
, expr
->left
, alloc_state_expr(array
));
809 static void match_assign(struct expression
*expr
)
814 if (match_assign_array(expr
))
816 match_assign_size(expr
);
819 static void match_copy(const char *fn
, struct expression
*expr
, void *unused
)
821 struct expression
*src
, *size
;
822 int src_param
, size_param
;
824 src
= get_argument_from_call_expr(expr
->args
, 1);
825 size
= get_argument_from_call_expr(expr
->args
, 2);
826 src
= strip_expr(src
);
827 size
= strip_expr(size
);
830 if (src
->type
!= EXPR_SYMBOL
|| size
->type
!= EXPR_SYMBOL
)
833 src_param
= get_param_num_from_sym(src
->symbol
);
834 size_param
= get_param_num_from_sym(size
->symbol
);
835 if (src_param
< 0 || size_param
< 0)
838 sql_insert_cache(call_implies
, "'%s', '%s', 0, %d, %d, %d, '==$%d', '%d'",
839 get_base_file(), get_function(), fn_static(),
840 BYTE_COUNT
, src_param
, size_param
, BYTE_COUNT
);
843 void register_buf_comparison(int id
)
849 set_dynamic_states(size_id
);
851 add_unmatched_state_hook(size_id
, &unmatched_state
);
853 add_allocation_function("malloc", &match_alloc
, 0);
854 add_allocation_function("memdup", &match_alloc
, 1);
855 add_allocation_function("realloc", &match_alloc
, 1);
856 if (option_project
== PROJ_KERNEL
) {
857 add_allocation_function("kmalloc", &match_alloc
, 0);
858 add_allocation_function("kzalloc", &match_alloc
, 0);
859 add_allocation_function("vmalloc", &match_alloc
, 0);
860 add_allocation_function("__vmalloc", &match_alloc
, 0);
861 add_allocation_function("sock_kmalloc", &match_alloc
, 1);
862 add_allocation_function("kmemdup", &match_alloc
, 1);
863 add_allocation_function("memdup_user", &match_alloc
, 1);
864 add_allocation_function("dma_alloc_attrs", &match_alloc
, 1);
865 add_allocation_function("pci_alloc_consistent", &match_alloc
, 1);
866 add_allocation_function("pci_alloc_coherent", &match_alloc
, 1);
867 add_allocation_function("devm_kmalloc", &match_alloc
, 1);
868 add_allocation_function("devm_kzalloc", &match_alloc
, 1);
869 add_allocation_function("kcalloc", &match_calloc
, 0);
870 add_allocation_function("devm_kcalloc", &match_calloc
, 1);
871 add_allocation_function("kmalloc_array", &match_calloc
, 0);
872 add_allocation_function("krealloc", &match_alloc
, 1);
874 add_function_hook("copy_from_user", &match_copy
, NULL
);
875 add_function_hook("__copy_from_user", &match_copy
, NULL
);
878 add_hook(&array_check
, OP_HOOK
);
879 add_hook(&array_check_data_info
, OP_HOOK
);
880 add_hook(&set_used
, OP_HOOK
);
882 add_hook(&match_call
, FUNCTION_CALL_HOOK
);
883 add_hook(&munge_start_states
, AFTER_DEF_HOOK
);
885 add_hook(&match_assign
, ASSIGNMENT_HOOK
);
887 for (i
= BYTE_COUNT
; i
<= USED_COUNT
; i
++) {
888 select_call_implies_hook(i
, &set_implied
);
889 select_caller_info_hook(set_param_compare
, i
);
890 select_return_implies_hook(i
, &set_implied
);
894 void register_buf_comparison_links(int id
)
897 set_dynamic_states(link_id
);
898 add_merge_hook(link_id
, &merge_links
);
899 add_modification_hook(link_id
, &match_link_modify
);