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 * We need this for code which does:
37 * We want to record that the size of "foo" is "size" even after the merge.
40 static struct smatch_state
*unmatched_state(struct sm_state
*sm
)
42 struct expression
*size_expr
;
47 size_expr
= sm
->state
->data
;
48 if (!get_implied_value(size_expr
, &sval
) || sval
.value
!= 0)
53 static struct smatch_state
*merge_links(struct smatch_state
*s1
, struct smatch_state
*s2
)
55 struct expression
*expr1
, *expr2
;
60 if (expr1
&& expr2
&& expr_equiv(expr1
, expr2
))
65 static void match_link_modify(struct sm_state
*sm
, struct expression
*mod_expr
)
67 struct expression
*expr
;
70 expr
= sm
->state
->data
;
72 set_state_expr(size_id
, expr
, &undefined
);
73 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
77 FOR_EACH_PTR(sm
->possible
, tmp
) {
78 expr
= tmp
->state
->data
;
80 set_state_expr(size_id
, expr
, &undefined
);
81 } END_FOR_EACH_PTR(tmp
);
82 set_state(link_id
, sm
->name
, sm
->sym
, &undefined
);
85 static struct smatch_state
*alloc_expr_state(struct expression
*expr
)
87 struct smatch_state
*state
;
90 state
= __alloc_smatch_state(0);
91 expr
= strip_expr(expr
);
92 name
= expr_to_str(expr
);
93 state
->name
= alloc_sname(name
);
99 static int bytes_per_element(struct expression
*expr
)
103 type
= get_type(expr
);
107 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
)
110 type
= get_base_type(type
);
111 return type_bytes(type
);
114 static void db_save_type_links(struct expression
*array
, struct expression
*size
)
116 const char *array_name
;
118 array_name
= get_data_info_name(array
);
121 sql_insert_data_info(size
, ARRAY_LEN
, array_name
);
124 static void match_alloc_helper(struct expression
*pointer
, struct expression
*size
)
126 struct expression
*tmp
;
131 pointer
= strip_expr(pointer
);
132 size
= strip_expr(size
);
133 if (!size
|| !pointer
)
136 while ((tmp
= get_assigned_expr(size
))) {
137 size
= strip_expr(tmp
);
142 if (size
->type
== EXPR_BINOP
&& size
->op
== '*') {
143 struct expression
*mult_left
, *mult_right
;
145 mult_left
= strip_expr(size
->left
);
146 mult_right
= strip_expr(size
->right
);
148 if (get_implied_value(mult_left
, &sval
) &&
149 sval
.value
== bytes_per_element(pointer
))
151 else if (get_implied_value(mult_right
, &sval
) &&
152 sval
.value
== bytes_per_element(pointer
))
158 db_save_type_links(pointer
, size
);
159 sm
= set_state_expr(size_id
, pointer
, alloc_expr_state(size
));
162 set_state_expr(link_id
, size
, alloc_expr_state(pointer
));
165 static void match_alloc(const char *fn
, struct expression
*expr
, void *_size_arg
)
167 int size_arg
= PTR_INT(_size_arg
);
168 struct expression
*pointer
, *call
, *arg
;
170 pointer
= strip_expr(expr
->left
);
171 call
= strip_expr(expr
->right
);
172 arg
= get_argument_from_call_expr(call
->args
, size_arg
);
173 match_alloc_helper(pointer
, arg
);
176 static void match_calloc(const char *fn
, struct expression
*expr
, void *_start_arg
)
178 int start_arg
= PTR_INT(_start_arg
);
179 struct expression
*pointer
, *call
, *arg
;
180 struct sm_state
*tmp
;
183 pointer
= strip_expr(expr
->left
);
184 call
= strip_expr(expr
->right
);
185 arg
= get_argument_from_call_expr(call
->args
, start_arg
);
186 if (get_implied_value(arg
, &sval
) &&
187 sval
.value
== bytes_per_element(pointer
))
188 arg
= get_argument_from_call_expr(call
->args
, start_arg
+ 1);
190 db_save_type_links(pointer
, arg
);
191 tmp
= set_state_expr(size_id
, pointer
, alloc_expr_state(arg
));
194 set_state_expr(link_id
, arg
, alloc_expr_state(pointer
));
197 struct expression
*get_size_variable(struct expression
*buf
)
199 struct smatch_state
*state
;
201 state
= get_state_expr(size_id
, buf
);
207 struct expression
*get_array_variable(struct expression
*size
)
209 struct smatch_state
*state
;
211 state
= get_state_expr(link_id
, size
);
217 static void array_check(struct expression
*expr
)
219 struct expression
*array
;
220 struct expression
*size
;
221 struct expression
*offset
;
222 char *array_str
, *offset_str
;
224 expr
= strip_expr(expr
);
228 array
= get_array_base(expr
);
229 size
= get_size_variable(array
);
232 offset
= get_array_offset(expr
);
233 if (!possible_comparison(size
, SPECIAL_EQUAL
, offset
))
236 array_str
= expr_to_str(array
);
237 offset_str
= expr_to_str(offset
);
238 sm_msg("warn: potentially one past the end of array '%s[%s]'", array_str
, offset_str
);
239 free_string(array_str
);
240 free_string(offset_str
);
248 static int db_limitter_callback(void *_info
, int argc
, char **argv
, char **azColName
)
250 struct db_info
*info
= _info
;
253 * If possible the limitters are tied to the struct they limit. If we
254 * aren't sure which struct they limit then we use them as limitters for
257 if (!info
->name
|| argv
[0][0] == '\0' || strcmp(info
->name
, argv
[0]) == 0)
262 static char *vsl_to_data_info_name(const char *name
, struct var_sym_list
*vsl
)
269 if (ptr_list_size((struct ptr_list
*)vsl
) != 1)
271 vs
= first_ptr_list((struct ptr_list
*)vsl
);
273 type
= get_real_base_type(vs
->sym
);
274 if (!type
|| type
->type
!= SYM_PTR
)
276 type
= get_real_base_type(type
);
277 if (!type
|| type
->type
!= SYM_STRUCT
)
283 while ((name
= strstr(p
, "->")))
286 snprintf(buf
, sizeof(buf
),"(struct %s)->%s", type
->ident
->name
, p
);
287 return alloc_sname(buf
);
290 if (!(vs
->sym
->ctype
.modifiers
& MOD_TOPLEVEL
))
292 if (vs
->sym
->ctype
.modifiers
& MOD_STATIC
)
293 snprintf(buf
, sizeof(buf
),"static %s", name
);
295 snprintf(buf
, sizeof(buf
),"global %s", name
);
296 return alloc_sname(buf
);
299 int db_var_is_array_limit(struct expression
*array
, const char *name
, struct var_sym_list
*vsl
)
302 char *array_name
= get_data_info_name(array
);
303 struct db_info db_info
= {.name
= array_name
,};
305 size_name
= vsl_to_data_info_name(name
, vsl
);
309 run_sql(db_limitter_callback
, &db_info
,
310 "select value from data_info where type = %d and data = '%s';",
311 ARRAY_LEN
, size_name
);
316 static int known_access_ok_comparison(struct expression
*expr
)
318 struct expression
*array
;
319 struct expression
*size
;
320 struct expression
*offset
;
323 array
= get_array_base(expr
);
324 size
= get_size_variable(array
);
327 offset
= get_array_offset(expr
);
328 comparison
= get_comparison(size
, offset
);
329 if (comparison
== '>' || comparison
== SPECIAL_UNSIGNED_GT
)
335 static int known_access_ok_numbers(struct expression
*expr
)
337 struct expression
*array
;
338 struct expression
*offset
;
342 array
= get_array_base(expr
);
343 offset
= get_array_offset(expr
);
345 size
= get_array_size(array
);
349 get_absolute_max(offset
, &max
);
350 if (max
.uvalue
< size
)
355 static void array_check_data_info(struct expression
*expr
)
357 struct expression
*array
;
358 struct expression
*offset
;
359 struct state_list
*slist
;
361 struct compare_data
*comp
;
363 const char *equal_name
= NULL
;
365 expr
= strip_expr(expr
);
369 if (known_access_ok_numbers(expr
))
371 if (known_access_ok_comparison(expr
))
374 array
= get_array_base(expr
);
375 offset
= get_array_offset(expr
);
376 offset_name
= expr_to_var(offset
);
379 slist
= get_all_possible_equal_comparisons(offset
);
383 FOR_EACH_PTR(slist
, sm
) {
384 comp
= sm
->state
->data
;
385 if (strcmp(comp
->left_var
, offset_name
) == 0) {
386 if (db_var_is_array_limit(array
, comp
->right_var
, comp
->right_vsl
)) {
387 equal_name
= comp
->right_var
;
390 } else if (strcmp(comp
->right_var
, offset_name
) == 0) {
391 if (db_var_is_array_limit(array
, comp
->left_var
, comp
->left_vsl
)) {
392 equal_name
= comp
->left_var
;
396 } END_FOR_EACH_PTR(sm
);
399 char *array_name
= expr_to_str(array
);
401 sm_msg("warn: potential off by one '%s[]' limit '%s'", array_name
, equal_name
);
402 free_string(array_name
);
407 free_string(offset_name
);
410 static void add_allocation_function(const char *func
, void *call_back
, int param
)
412 add_function_assign_hook(func
, call_back
, INT_PTR(param
));
415 static char *buf_size_param_comparison(struct expression
*array
, struct expression_list
*args
)
417 struct expression
*arg
;
418 struct expression
*size
;
422 size
= get_size_variable(array
);
427 FOR_EACH_PTR(args
, arg
) {
431 if (!expr_equiv(arg
, size
))
433 snprintf(buf
, sizeof(buf
), "==$%d", i
);
435 } END_FOR_EACH_PTR(arg
);
440 static void match_call(struct expression
*call
)
442 struct expression
*arg
;
447 FOR_EACH_PTR(call
->args
, arg
) {
449 if (!is_pointer(arg
))
451 compare
= buf_size_param_comparison(arg
, call
->args
);
454 sql_insert_caller_info(call
, ARRAY_LEN
, param
, "$", compare
);
455 } END_FOR_EACH_PTR(arg
);
458 static int get_param(int param
, char **name
, struct symbol
**sym
)
464 FOR_EACH_PTR(cur_func_sym
->ctype
.base_type
->arguments
, arg
) {
466 * this is a temporary hack to work around a bug (I think in sparse?)
467 * 2.6.37-rc1:fs/reiserfs/journal.o
468 * If there is a function definition without parameter name found
469 * after a function implementation then it causes a crash.
473 if (arg
->ident
->name
< (char *)100)
476 *name
= arg
->ident
->name
;
481 } END_FOR_EACH_PTR(arg
);
486 static void set_param_compare(const char *array_name
, struct symbol
*array_sym
, char *key
, char *value
)
488 struct expression
*array_expr
;
489 struct expression
*size_expr
;
490 struct symbol
*size_sym
;
493 struct sm_state
*tmp
;
495 if (strncmp(value
, "==$", 3) != 0)
497 param
= strtol(value
+ 3, NULL
, 10);
498 if (!get_param(param
, &size_name
, &size_sym
))
500 array_expr
= symbol_expression(array_sym
);
501 size_expr
= symbol_expression(size_sym
);
503 tmp
= set_state_expr(size_id
, array_expr
, alloc_expr_state(size_expr
));
506 set_state_expr(link_id
, size_expr
, alloc_expr_state(array_expr
));
509 static void set_arraysize_arg(const char *array_name
, struct symbol
*array_sym
, char *key
, char *value
)
511 struct expression
*array_expr
;
512 struct expression
*size_expr
;
513 struct symbol
*size_sym
;
516 struct sm_state
*tmp
;
518 param
= strtol(key
, NULL
, 10);
519 if (!get_param(param
, &size_name
, &size_sym
))
521 array_expr
= symbol_expression(array_sym
);
522 size_expr
= symbol_expression(size_sym
);
524 tmp
= set_state_expr(size_id
, array_expr
, alloc_expr_state(size_expr
));
527 set_state_expr(link_id
, size_expr
, alloc_expr_state(array_expr
));
530 static void munge_start_states(struct statement
*stmt
)
532 struct state_list
*slist
= NULL
;
534 struct sm_state
*poss
;
536 FOR_EACH_MY_SM(size_id
, __get_cur_stree(), sm
) {
537 if (sm
->state
!= &merged
)
540 * screw it. let's just assume that if one caller passes the
541 * size then they all do.
543 FOR_EACH_PTR(sm
->possible
, poss
) {
544 if (poss
->state
!= &merged
&&
545 poss
->state
!= &undefined
) {
546 add_ptr_list(&slist
, poss
);
549 } END_FOR_EACH_PTR(poss
);
550 } END_FOR_EACH_SM(sm
);
552 FOR_EACH_PTR(slist
, sm
) {
553 set_state(size_id
, sm
->name
, sm
->sym
, sm
->state
);
554 } END_FOR_EACH_PTR(sm
);
559 void register_buf_comparison(int id
)
563 add_unmatched_state_hook(size_id
, &unmatched_state
);
565 add_allocation_function("malloc", &match_alloc
, 0);
566 add_allocation_function("memdup", &match_alloc
, 1);
567 add_allocation_function("realloc", &match_alloc
, 1);
568 if (option_project
== PROJ_KERNEL
) {
569 add_allocation_function("kmalloc", &match_alloc
, 0);
570 add_allocation_function("kzalloc", &match_alloc
, 0);
571 add_allocation_function("vmalloc", &match_alloc
, 0);
572 add_allocation_function("__vmalloc", &match_alloc
, 0);
573 add_allocation_function("sock_kmalloc", &match_alloc
, 1);
574 add_allocation_function("kmemdup", &match_alloc
, 1);
575 add_allocation_function("kmemdup_user", &match_alloc
, 1);
576 add_allocation_function("dma_alloc_attrs", &match_alloc
, 1);
577 add_allocation_function("pci_alloc_consistent", &match_alloc
, 1);
578 add_allocation_function("pci_alloc_coherent", &match_alloc
, 1);
579 add_allocation_function("devm_kmalloc", &match_alloc
, 1);
580 add_allocation_function("devm_kzalloc", &match_alloc
, 1);
581 add_allocation_function("kcalloc", &match_calloc
, 0);
582 add_allocation_function("devm_kcalloc", &match_calloc
, 1);
583 add_allocation_function("kmalloc_array", &match_calloc
, 0);
584 add_allocation_function("krealloc", &match_alloc
, 1);
587 add_hook(&array_check
, OP_HOOK
);
588 add_hook(&array_check_data_info
, OP_HOOK
);
590 add_hook(&match_call
, FUNCTION_CALL_HOOK
);
591 select_caller_info_hook(set_param_compare
, ARRAY_LEN
);
592 select_caller_info_hook(set_arraysize_arg
, ARRAYSIZE_ARG
);
593 add_hook(&munge_start_states
, AFTER_DEF_HOOK
);
596 void register_buf_comparison_links(int id
)
599 add_merge_hook(link_id
, &merge_links
);
600 add_modification_hook(link_id
, &match_link_modify
);