implied: add a timeout in smatch_implied.c
[smatch.git] / smatch_buf_comparison.c
blob586ef7c9d1c05e89a598c036163cd878b235c9ed
1 /*
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
20 * the value of x.
24 #include "smatch.h"
25 #include "smatch_extra.h"
26 #include "smatch_slist.h"
28 static int size_id;
29 static int link_id;
32 * We need this for code which does:
34 * if (size)
35 * foo = malloc(size);
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;
43 sval_t sval;
45 if (!sm->state->data)
46 return &undefined;
47 size_expr = sm->state->data;
48 if (!get_implied_value(size_expr, &sval) || sval.value != 0)
49 return &undefined;
50 return sm->state;
53 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
55 struct expression *expr1, *expr2;
57 expr1 = s1->data;
58 expr2 = s2->data;
60 if (expr1 && expr2 && expr_equiv(expr1, expr2))
61 return s1;
62 return &merged;
65 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
67 struct expression *expr;
68 struct sm_state *tmp;
70 expr = sm->state->data;
71 if (expr) {
72 set_state_expr(size_id, expr, &undefined);
73 set_state(link_id, sm->name, sm->sym, &undefined);
74 return;
77 FOR_EACH_PTR(sm->possible, tmp) {
78 expr = tmp->state->data;
79 if (expr)
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;
88 char *name;
90 state = __alloc_smatch_state(0);
91 expr = strip_expr(expr);
92 name = expr_to_str(expr);
93 state->name = alloc_sname(name);
94 free_string(name);
95 state->data = expr;
96 return state;
99 static int bytes_per_element(struct expression *expr)
101 struct symbol *type;
103 type = get_type(expr);
104 if (!type)
105 return 0;
107 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
108 return 0;
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);
119 if (!array_name)
120 array_name = "";
121 sql_insert_data_info(size, ARRAY_LEN, array_name);
124 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
126 int size_arg = PTR_INT(_size_arg);
127 struct expression *pointer, *call, *arg;
128 struct sm_state *tmp;
130 pointer = strip_expr(expr->left);
131 call = strip_expr(expr->right);
132 arg = get_argument_from_call_expr(call->args, size_arg);
133 arg = strip_expr(arg);
135 if (arg->type == EXPR_BINOP && arg->op == '*') {
136 struct expression *left, *right;
137 sval_t sval;
139 left = strip_expr(arg->left);
140 right = strip_expr(arg->right);
142 if (get_implied_value(left, &sval) &&
143 sval.value == bytes_per_element(pointer))
144 arg = right;
146 if (get_implied_value(right, &sval) &&
147 sval.value == bytes_per_element(pointer))
148 arg = left;
151 db_save_type_links(pointer, arg);
152 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
153 if (!tmp)
154 return;
155 set_state_expr(link_id, arg, alloc_expr_state(pointer));
158 static void match_calloc(const char *fn, struct expression *expr, void *unused)
160 struct expression *pointer, *call, *arg;
161 struct sm_state *tmp;
162 sval_t sval;
164 pointer = strip_expr(expr->left);
165 call = strip_expr(expr->right);
166 arg = get_argument_from_call_expr(call->args, 0);
167 if (get_implied_value(arg, &sval) &&
168 sval.value == bytes_per_element(pointer))
169 arg = get_argument_from_call_expr(call->args, 1);
171 db_save_type_links(pointer, arg);
172 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
173 if (!tmp)
174 return;
175 set_state_expr(link_id, arg, alloc_expr_state(pointer));
178 struct expression *get_size_variable(struct expression *buf)
180 struct smatch_state *state;
182 state = get_state_expr(size_id, buf);
183 if (state)
184 return state->data;
185 return NULL;
188 static void array_check(struct expression *expr)
190 struct expression *array;
191 struct expression *size;
192 struct expression *offset;
193 char *array_str, *offset_str;
195 expr = strip_expr(expr);
196 if (!is_array(expr))
197 return;
199 array = get_array_base(expr);
200 size = get_size_variable(array);
201 if (!size)
202 return;
203 offset = get_array_offset(expr);
204 if (!possible_comparison(size, SPECIAL_EQUAL, offset))
205 return;
207 array_str = expr_to_str(array);
208 offset_str = expr_to_str(offset);
209 sm_msg("warn: potentially one past the end of array '%s[%s]'", array_str, offset_str);
210 free_string(array_str);
211 free_string(offset_str);
214 struct db_info {
215 char *name;
216 int ret;
219 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
221 struct db_info *info = _info;
224 * If possible the limitters are tied to the struct they limit. If we
225 * aren't sure which struct they limit then we use them as limitters for
226 * everything.
228 if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
229 info->ret = 1;
230 return 0;
233 static char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl)
235 struct var_sym *vs;
236 struct symbol *type;
237 static char buf[80];
238 const char *p;
240 if (ptr_list_size((struct ptr_list *)vsl) != 1)
241 return NULL;
242 vs = first_ptr_list((struct ptr_list *)vsl);
244 type = get_real_base_type(vs->sym);
245 if (!type || type->type != SYM_PTR)
246 goto top_level_name;
247 type = get_real_base_type(type);
248 if (!type || type->type != SYM_STRUCT)
249 goto top_level_name;
250 if (!type->ident)
251 goto top_level_name;
253 p = name;
254 while ((name = strstr(p, "->")))
255 p = name + 2;
257 snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
258 return alloc_sname(buf);
260 top_level_name:
261 if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL))
262 return NULL;
263 if (vs->sym->ctype.modifiers & MOD_STATIC)
264 snprintf(buf, sizeof(buf),"static %s", name);
265 else
266 snprintf(buf, sizeof(buf),"global %s", name);
267 return alloc_sname(buf);
270 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
272 char *size_name;
273 char *array_name = get_data_info_name(array);
274 struct db_info db_info = {.name = array_name,};
276 size_name = vsl_to_data_info_name(name, vsl);
277 if (!size_name)
278 return 0;
280 run_sql(db_limitter_callback, &db_info,
281 "select value from data_info where type = %d and data = '%s';",
282 ARRAY_LEN, size_name);
284 return db_info.ret;
287 static int known_access_ok_comparison(struct expression *expr)
289 struct expression *array;
290 struct expression *size;
291 struct expression *offset;
292 int comparison;
294 array = get_array_base(expr);
295 size = get_size_variable(array);
296 if (!size)
297 return 0;
298 offset = get_array_offset(expr);
299 comparison = get_comparison(size, offset);
300 if (comparison == '>' || comparison == SPECIAL_UNSIGNED_GT)
301 return 1;
303 return 0;
306 static int known_access_ok_numbers(struct expression *expr)
308 struct expression *array;
309 struct expression *offset;
310 sval_t max;
311 int size;
313 array = get_array_base(expr);
314 offset = get_array_offset(expr);
316 size = get_array_size(array);
317 if (size <= 0)
318 return 0;
320 get_absolute_max(offset, &max);
321 if (max.uvalue < size)
322 return 1;
323 return 0;
326 static void array_check_data_info(struct expression *expr)
328 struct expression *array;
329 struct expression *offset;
330 struct state_list *slist;
331 struct sm_state *sm;
332 struct compare_data *comp;
333 char *offset_name;
334 const char *equal_name = NULL;
336 expr = strip_expr(expr);
337 if (!is_array(expr))
338 return;
340 if (known_access_ok_numbers(expr))
341 return;
342 if (known_access_ok_comparison(expr))
343 return;
345 array = get_array_base(expr);
346 offset = get_array_offset(expr);
347 offset_name = expr_to_var(offset);
348 if (!offset_name)
349 return;
350 slist = get_all_possible_equal_comparisons(offset);
351 if (!slist)
352 goto free;
354 FOR_EACH_PTR(slist, sm) {
355 comp = sm->state->data;
356 if (strcmp(comp->var1, offset_name) == 0) {
357 if (db_var_is_array_limit(array, comp->var2, comp->vsl2)) {
358 equal_name = comp->var2;
359 break;
361 } else if (strcmp(comp->var2, offset_name) == 0) {
362 if (db_var_is_array_limit(array, comp->var1, comp->vsl1)) {
363 equal_name = comp->var1;
364 break;
367 } END_FOR_EACH_PTR(sm);
369 if (equal_name) {
370 char *array_name = expr_to_str(array);
372 sm_msg("warn: potential off by one '%s[]' limit '%s'", array_name, equal_name);
373 free_string(array_name);
376 free:
377 free_slist(&slist);
378 free_string(offset_name);
381 static void add_allocation_function(const char *func, void *call_back, int param)
383 add_function_assign_hook(func, call_back, INT_PTR(param));
386 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args)
388 struct expression *arg;
389 struct expression *size;
390 static char buf[32];
391 int i;
393 size = get_size_variable(array);
394 if (!size)
395 return NULL;
397 i = -1;
398 FOR_EACH_PTR(args, arg) {
399 i++;
400 if (arg == array)
401 continue;
402 if (!expr_equiv(arg, size))
403 continue;
404 snprintf(buf, sizeof(buf), "==$%d", i);
405 return buf;
406 } END_FOR_EACH_PTR(arg);
408 return NULL;
411 static void match_call(struct expression *call)
413 struct expression *arg;
414 char *compare;
415 int param;
417 param = -1;
418 FOR_EACH_PTR(call->args, arg) {
419 param++;
420 if (!is_pointer(arg))
421 continue;
422 compare = buf_size_param_comparison(arg, call->args);
423 if (!compare)
424 continue;
425 sql_insert_caller_info(call, ARRAY_LEN, param, "$", compare);
426 } END_FOR_EACH_PTR(arg);
429 static int get_param(int param, char **name, struct symbol **sym)
431 struct symbol *arg;
432 int i;
434 i = 0;
435 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
437 * this is a temporary hack to work around a bug (I think in sparse?)
438 * 2.6.37-rc1:fs/reiserfs/journal.o
439 * If there is a function definition without parameter name found
440 * after a function implementation then it causes a crash.
441 * int foo() {}
442 * int bar(char *);
444 if (arg->ident->name < (char *)100)
445 continue;
446 if (i == param) {
447 *name = arg->ident->name;
448 *sym = arg;
449 return TRUE;
451 i++;
452 } END_FOR_EACH_PTR(arg);
454 return FALSE;
457 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
459 struct expression *array_expr;
460 struct expression *size_expr;
461 struct symbol *size_sym;
462 char *size_name;
463 long param;
464 struct sm_state *tmp;
466 if (strncmp(value, "==$", 3) != 0)
467 return;
468 param = strtol(value + 3, NULL, 10);
469 if (!get_param(param, &size_name, &size_sym))
470 return;
471 array_expr = symbol_expression(array_sym);
472 size_expr = symbol_expression(size_sym);
474 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
475 if (!tmp)
476 return;
477 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
480 static void set_arraysize_arg(const char *array_name, struct symbol *array_sym, char *key, char *value)
482 struct expression *array_expr;
483 struct expression *size_expr;
484 struct symbol *size_sym;
485 char *size_name;
486 long param;
487 struct sm_state *tmp;
489 param = strtol(key, NULL, 10);
490 if (!get_param(param, &size_name, &size_sym))
491 return;
492 array_expr = symbol_expression(array_sym);
493 size_expr = symbol_expression(size_sym);
495 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
496 if (!tmp)
497 return;
498 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
501 static void munge_start_states(struct statement *stmt)
503 struct state_list *slist = NULL;
504 struct sm_state *sm;
505 struct sm_state *poss;
507 FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
508 if (sm->state != &merged)
509 continue;
511 * screw it. let's just assume that if one caller passes the
512 * size then they all do.
514 FOR_EACH_PTR(sm->possible, poss) {
515 if (poss->state != &merged &&
516 poss->state != &undefined) {
517 add_ptr_list(&slist, poss);
518 break;
520 } END_FOR_EACH_PTR(poss);
521 } END_FOR_EACH_SM(sm);
523 FOR_EACH_PTR(slist, sm) {
524 set_state(size_id, sm->name, sm->sym, sm->state);
525 } END_FOR_EACH_PTR(sm);
527 free_slist(&slist);
530 void register_buf_comparison(int id)
532 size_id = id;
534 add_unmatched_state_hook(size_id, &unmatched_state);
536 add_allocation_function("malloc", &match_alloc, 0);
537 add_allocation_function("memdup", &match_alloc, 1);
538 add_allocation_function("realloc", &match_alloc, 1);
539 if (option_project == PROJ_KERNEL) {
540 add_allocation_function("kmalloc", &match_alloc, 0);
541 add_allocation_function("kzalloc", &match_alloc, 0);
542 add_allocation_function("vmalloc", &match_alloc, 0);
543 add_allocation_function("__vmalloc", &match_alloc, 0);
544 add_allocation_function("sock_kmalloc", &match_alloc, 1);
545 add_allocation_function("kmemdup", &match_alloc, 1);
546 add_allocation_function("kmemdup_user", &match_alloc, 1);
547 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
548 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
549 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
550 add_allocation_function("devm_kmalloc", &match_alloc, 1);
551 add_allocation_function("devm_kzalloc", &match_alloc, 1);
552 add_allocation_function("kcalloc", &match_calloc, 0);
553 add_allocation_function("krealloc", &match_alloc, 1);
556 add_hook(&array_check, OP_HOOK);
557 add_hook(&array_check_data_info, OP_HOOK);
559 add_hook(&match_call, FUNCTION_CALL_HOOK);
560 select_caller_info_hook(set_param_compare, ARRAY_LEN);
561 select_caller_info_hook(set_arraysize_arg, ARRAYSIZE_ARG);
562 add_hook(&munge_start_states, AFTER_DEF_HOOK);
565 void register_buf_comparison_links(int id)
567 link_id = id;
568 add_merge_hook(link_id, &merge_links);
569 add_modification_hook(link_id, &match_link_modify);