shift_to_zero: fix an error message
[smatch.git] / check_buf_comparison.c
blob30134cb0ec2d405d87d5b9c54f5be98d6c8497e8
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;
31 static int expr_equiv(struct expression *one, struct expression *two)
33 struct symbol *one_sym, *two_sym;
34 char *one_name = NULL;
35 char *two_name = NULL;
36 int ret = 0;
38 if (!one || !two)
39 return 0;
40 if (one->type != two->type)
41 return 0;
42 one_name = expr_to_str_sym(one, &one_sym);
43 if (!one_name || !one_sym)
44 goto free;
45 two_name = expr_to_str_sym(two, &two_sym);
46 if (!two_name || !two_sym)
47 goto free;
48 if (one_sym != two_sym)
49 goto free;
50 if (strcmp(one_name, two_name) == 0)
51 ret = 1;
52 free:
53 free_string(one_name);
54 free_string(two_name);
55 return ret;
58 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
60 struct expression *expr;
62 expr = sm->state->data;
63 if (!expr)
64 return;
65 set_state_expr(size_id, expr, &undefined);
68 static struct smatch_state *alloc_expr_state(struct expression *expr)
70 struct smatch_state *state;
71 char *name;
73 state = __alloc_smatch_state(0);
74 expr = strip_expr(expr);
75 name = expr_to_str(expr);
76 state->name = alloc_sname(name);
77 free_string(name);
78 state->data = expr;
79 return state;
82 static int bytes_per_element(struct expression *expr)
84 struct symbol *type;
86 type = get_type(expr);
87 if (!type)
88 return 0;
90 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
91 return 0;
93 type = get_base_type(type);
94 return type_bytes(type);
97 static void db_save_type_links(struct expression *array, struct expression *size)
99 const char *array_name;
101 array_name = get_member_name(array);
102 if (!array_name)
103 array_name = "";
104 sql_insert_data_info(size, ARRAY_LEN, array_name);
107 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
109 int size_arg = PTR_INT(_size_arg);
110 struct expression *pointer, *call, *arg;
111 struct sm_state *tmp;
113 pointer = strip_expr(expr->left);
114 call = strip_expr(expr->right);
115 arg = get_argument_from_call_expr(call->args, size_arg);
116 arg = strip_expr(arg);
118 if (arg->type == EXPR_BINOP && arg->op == '*') {
119 struct expression *left, *right;
120 sval_t sval;
122 left = strip_expr(arg->left);
123 right = strip_expr(arg->right);
125 if (get_implied_value(left, &sval) &&
126 sval.value == bytes_per_element(pointer))
127 arg = right;
129 if (get_implied_value(right, &sval) &&
130 sval.value == bytes_per_element(pointer))
131 arg = left;
134 db_save_type_links(pointer, arg);
135 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
136 if (!tmp)
137 return;
138 set_state_expr(link_id, arg, alloc_expr_state(pointer));
141 static void match_calloc(const char *fn, struct expression *expr, void *unused)
143 struct expression *pointer, *call, *arg;
144 struct sm_state *tmp;
145 sval_t sval;
147 pointer = strip_expr(expr->left);
148 call = strip_expr(expr->right);
149 arg = get_argument_from_call_expr(call->args, 0);
150 if (get_implied_value(arg, &sval) &&
151 sval.value == bytes_per_element(pointer))
152 arg = get_argument_from_call_expr(call->args, 1);
154 db_save_type_links(pointer, arg);
155 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
156 if (!tmp)
157 return;
158 set_state_expr(link_id, arg, alloc_expr_state(pointer));
161 static struct expression *get_saved_size(struct expression *buf)
163 struct smatch_state *state;
165 state = get_state_expr(size_id, buf);
166 if (state)
167 return state->data;
168 return NULL;
171 static void array_check(struct expression *expr)
173 struct expression *array;
174 struct expression *size;
175 struct expression *offset;
176 char *array_str, *offset_str;
178 expr = strip_expr(expr);
179 if (!is_array(expr))
180 return;
182 array = strip_parens(expr->unop->left);
183 size = get_saved_size(array);
184 if (!size)
185 return;
186 offset = get_array_offset(expr);
187 if (!possible_comparison(size, SPECIAL_EQUAL, offset))
188 return;
190 array_str = expr_to_str(array);
191 offset_str = expr_to_str(offset);
192 sm_msg("warn: potentially one past the end of array '%s[%s]'", array_str, offset_str);
193 free_string(array_str);
194 free_string(offset_str);
197 struct db_info {
198 char *name;
199 int ret;
202 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
204 struct db_info *info = _info;
207 * If possible the limitters are tied to the struct they limit. If we
208 * aren't sure which struct they limit then we use them as limitters for
209 * everything.
211 if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
212 info->ret = 1;
213 return 0;
216 static int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
218 struct var_sym *vs;
219 struct symbol *type;
220 char buf[80];
221 const char *p;
222 char *array_name = get_member_name(array);
223 struct db_info db_info = {.name = array_name,};
225 if (ptr_list_size((struct ptr_list *)vsl) != 1)
226 return 0;
227 vs = first_ptr_list((struct ptr_list *)vsl);
229 type = get_real_base_type(vs->sym);
230 if (!type || type->type != SYM_PTR)
231 return 0;
232 type = get_real_base_type(type);
233 if (!type || type->type != SYM_STRUCT)
234 return 0;
235 if (!type->ident)
236 return 0;
238 p = name;
239 while ((name = strstr(p, "->")))
240 p = name + 2;
242 snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
244 run_sql(db_limitter_callback, &db_info,
245 "select value from data_info where type = %d and data = '%s';",
246 ARRAY_LEN, buf);
248 return db_info.ret;
251 static int known_access_ok_comparison(struct expression *expr)
253 struct expression *array;
254 struct expression *size;
255 struct expression *offset;
256 int comparison;
258 array = strip_parens(expr->unop->left);
259 size = get_saved_size(array);
260 if (!size)
261 return 0;
262 offset = get_array_offset(expr);
263 comparison = get_comparison(size, offset);
264 if (comparison == '>' || comparison == SPECIAL_UNSIGNED_GT)
265 return 1;
267 return 0;
270 static int known_access_ok_numbers(struct expression *expr)
272 struct expression *array;
273 struct expression *offset;
274 sval_t max;
275 int size;
277 array = strip_parens(expr->unop->left);
278 offset = get_array_offset(expr);
280 size = get_array_size(array);
281 if (size <= 0)
282 return 0;
284 get_absolute_max(offset, &max);
285 if (max.uvalue < size)
286 return 1;
287 return 0;
290 static void array_check_data_info(struct expression *expr)
292 struct expression *array;
293 struct expression *offset;
294 struct state_list *slist;
295 struct sm_state *sm;
296 struct compare_data *comp;
297 char *offset_name;
298 const char *equal_name = NULL;
300 expr = strip_expr(expr);
301 if (!is_array(expr))
302 return;
304 if (known_access_ok_numbers(expr))
305 return;
306 if (known_access_ok_comparison(expr))
307 return;
309 array = strip_parens(expr->unop->left);
310 offset = get_array_offset(expr);
311 offset_name = expr_to_var(offset);
312 if (!offset_name)
313 return;
314 slist = get_all_possible_equal_comparisons(offset);
315 if (!slist)
316 goto free;
318 FOR_EACH_PTR(slist, sm) {
319 comp = sm->state->data;
320 if (strcmp(comp->var1, offset_name) == 0) {
321 if (db_var_is_array_limit(array, comp->var2, comp->vsl2)) {
322 equal_name = comp->var2;
323 break;
325 } else if (strcmp(comp->var2, offset_name) == 0) {
326 if (db_var_is_array_limit(array, comp->var1, comp->vsl1)) {
327 equal_name = comp->var1;
328 break;
331 } END_FOR_EACH_PTR(sm);
333 if (equal_name) {
334 char *array_name = expr_to_str(array);
336 sm_msg("warn: potential off by one '%s[]' limit '%s'", array_name, equal_name);
337 free_string(array_name);
340 free:
341 free_slist(&slist);
342 free_string(offset_name);
345 static void add_allocation_function(const char *func, void *call_back, int param)
347 add_function_assign_hook(func, call_back, INT_PTR(param));
350 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args)
352 struct expression *arg;
353 struct expression *size;
354 static char buf[32];
355 int i;
357 size = get_saved_size(array);
358 if (!size)
359 return NULL;
361 i = -1;
362 FOR_EACH_PTR(args, arg) {
363 i++;
364 if (arg == array)
365 continue;
366 if (!expr_equiv(arg, size))
367 continue;
368 snprintf(buf, sizeof(buf), "==$%d", i);
369 return buf;
370 } END_FOR_EACH_PTR(arg);
372 return NULL;
375 static void match_call(struct expression *call)
377 struct expression *arg;
378 char *compare;
379 int param;
381 param = -1;
382 FOR_EACH_PTR(call->args, arg) {
383 param++;
384 if (!is_pointer(arg))
385 continue;
386 compare = buf_size_param_comparison(arg, call->args);
387 if (!compare)
388 continue;
389 sql_insert_caller_info(call, ARRAY_LEN, param, "$$", compare);
390 } END_FOR_EACH_PTR(arg);
393 static int get_param(int param, char **name, struct symbol **sym)
395 struct symbol *arg;
396 int i;
398 i = 0;
399 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
401 * this is a temporary hack to work around a bug (I think in sparse?)
402 * 2.6.37-rc1:fs/reiserfs/journal.o
403 * If there is a function definition without parameter name found
404 * after a function implementation then it causes a crash.
405 * int foo() {}
406 * int bar(char *);
408 if (arg->ident->name < (char *)100)
409 continue;
410 if (i == param) {
411 *name = arg->ident->name;
412 *sym = arg;
413 return TRUE;
415 i++;
416 } END_FOR_EACH_PTR(arg);
418 return FALSE;
421 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
423 struct expression *array_expr;
424 struct expression *size_expr;
425 struct symbol *size_sym;
426 char *size_name;
427 long param;
428 struct sm_state *tmp;
430 if (strncmp(value, "==$", 3) != 0)
431 return;
432 param = strtol(value + 3, NULL, 10);
433 if (!get_param(param, &size_name, &size_sym))
434 return;
435 array_expr = symbol_expression(array_sym);
436 size_expr = symbol_expression(size_sym);
438 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
439 if (!tmp)
440 return;
441 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
446 static void munge_start_states(struct statement *stmt)
448 struct state_list *slist = NULL;
449 struct sm_state *sm;
450 struct sm_state *poss;
452 FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
453 if (sm->state != &merged)
454 continue;
456 * screw it. let's just assume that if one caller passes the
457 * size then they all do.
459 FOR_EACH_PTR(sm->possible, poss) {
460 if (poss->state != &merged &&
461 poss->state != &undefined) {
462 add_ptr_list(&slist, poss);
463 break;
465 } END_FOR_EACH_PTR(poss);
466 } END_FOR_EACH_SM(sm);
468 FOR_EACH_PTR(slist, sm) {
469 set_state(size_id, sm->name, sm->sym, sm->state);
470 } END_FOR_EACH_PTR(sm);
472 free_slist(&slist);
475 void check_buf_comparison(int id)
477 size_id = id;
479 add_allocation_function("malloc", &match_alloc, 0);
480 add_allocation_function("memdup", &match_alloc, 1);
481 add_allocation_function("realloc", &match_alloc, 1);
482 if (option_project == PROJ_KERNEL) {
483 add_allocation_function("kmalloc", &match_alloc, 0);
484 add_allocation_function("kzalloc", &match_alloc, 0);
485 add_allocation_function("vmalloc", &match_alloc, 0);
486 add_allocation_function("__vmalloc", &match_alloc, 0);
487 add_allocation_function("sock_kmalloc", &match_alloc, 1);
488 add_allocation_function("kmemdup", &match_alloc, 1);
489 add_allocation_function("kmemdup_user", &match_alloc, 1);
490 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
491 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
492 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
493 add_allocation_function("devm_kmalloc", &match_alloc, 1);
494 add_allocation_function("devm_kzalloc", &match_alloc, 1);
495 add_allocation_function("kcalloc", &match_calloc, 0);
496 add_allocation_function("krealloc", &match_alloc, 1);
499 add_hook(&array_check, OP_HOOK);
500 add_hook(&array_check_data_info, OP_HOOK);
502 add_hook(&match_call, FUNCTION_CALL_HOOK);
503 select_caller_info_hook(set_param_compare, ARRAY_LEN);
504 add_hook(&munge_start_states, AFTER_DEF_HOOK);
507 void check_buf_comparison_links(int id)
509 link_id = id;
510 add_modification_hook(link_id, &match_modify);