expressions: introduce compare_expression()
[smatch.git] / smatch_buf_comparison.c
blob3e9a1cfaa4ec82d2ff9fb50db443acb777c029ca
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 void match_modify(struct sm_state *sm, struct expression *mod_expr)
55 struct expression *expr;
57 expr = sm->state->data;
58 if (!expr)
59 return;
60 set_state_expr(size_id, expr, &undefined);
63 static struct smatch_state *alloc_expr_state(struct expression *expr)
65 struct smatch_state *state;
66 char *name;
68 state = __alloc_smatch_state(0);
69 expr = strip_expr(expr);
70 name = expr_to_str(expr);
71 state->name = alloc_sname(name);
72 free_string(name);
73 state->data = expr;
74 return state;
77 static int bytes_per_element(struct expression *expr)
79 struct symbol *type;
81 type = get_type(expr);
82 if (!type)
83 return 0;
85 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
86 return 0;
88 type = get_base_type(type);
89 return type_bytes(type);
92 static void db_save_type_links(struct expression *array, struct expression *size)
94 const char *array_name;
96 array_name = get_data_info_name(array);
97 if (!array_name)
98 array_name = "";
99 sql_insert_data_info(size, ARRAY_LEN, array_name);
102 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
104 int size_arg = PTR_INT(_size_arg);
105 struct expression *pointer, *call, *arg;
106 struct sm_state *tmp;
108 pointer = strip_expr(expr->left);
109 call = strip_expr(expr->right);
110 arg = get_argument_from_call_expr(call->args, size_arg);
111 arg = strip_expr(arg);
113 if (arg->type == EXPR_BINOP && arg->op == '*') {
114 struct expression *left, *right;
115 sval_t sval;
117 left = strip_expr(arg->left);
118 right = strip_expr(arg->right);
120 if (get_implied_value(left, &sval) &&
121 sval.value == bytes_per_element(pointer))
122 arg = right;
124 if (get_implied_value(right, &sval) &&
125 sval.value == bytes_per_element(pointer))
126 arg = left;
129 db_save_type_links(pointer, arg);
130 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
131 if (!tmp)
132 return;
133 set_state_expr(link_id, arg, alloc_expr_state(pointer));
136 static void match_calloc(const char *fn, struct expression *expr, void *unused)
138 struct expression *pointer, *call, *arg;
139 struct sm_state *tmp;
140 sval_t sval;
142 pointer = strip_expr(expr->left);
143 call = strip_expr(expr->right);
144 arg = get_argument_from_call_expr(call->args, 0);
145 if (get_implied_value(arg, &sval) &&
146 sval.value == bytes_per_element(pointer))
147 arg = get_argument_from_call_expr(call->args, 1);
149 db_save_type_links(pointer, arg);
150 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
151 if (!tmp)
152 return;
153 set_state_expr(link_id, arg, alloc_expr_state(pointer));
156 struct expression *get_size_variable(struct expression *buf)
158 struct smatch_state *state;
160 state = get_state_expr(size_id, buf);
161 if (state)
162 return state->data;
163 return NULL;
166 static void array_check(struct expression *expr)
168 struct expression *array;
169 struct expression *size;
170 struct expression *offset;
171 char *array_str, *offset_str;
173 expr = strip_expr(expr);
174 if (!is_array(expr))
175 return;
177 array = get_array_base(expr);
178 size = get_size_variable(array);
179 if (!size)
180 return;
181 offset = get_array_offset(expr);
182 if (!possible_comparison(size, SPECIAL_EQUAL, offset))
183 return;
185 array_str = expr_to_str(array);
186 offset_str = expr_to_str(offset);
187 sm_msg("warn: potentially one past the end of array '%s[%s]'", array_str, offset_str);
188 free_string(array_str);
189 free_string(offset_str);
192 struct db_info {
193 char *name;
194 int ret;
197 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
199 struct db_info *info = _info;
202 * If possible the limitters are tied to the struct they limit. If we
203 * aren't sure which struct they limit then we use them as limitters for
204 * everything.
206 if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
207 info->ret = 1;
208 return 0;
211 static char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl)
213 struct var_sym *vs;
214 struct symbol *type;
215 static char buf[80];
216 const char *p;
218 if (ptr_list_size((struct ptr_list *)vsl) != 1)
219 return NULL;
220 vs = first_ptr_list((struct ptr_list *)vsl);
222 type = get_real_base_type(vs->sym);
223 if (!type || type->type != SYM_PTR)
224 goto top_level_name;
225 type = get_real_base_type(type);
226 if (!type || type->type != SYM_STRUCT)
227 goto top_level_name;
228 if (!type->ident)
229 goto top_level_name;
231 p = name;
232 while ((name = strstr(p, "->")))
233 p = name + 2;
235 snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
236 return alloc_sname(buf);
238 top_level_name:
239 if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL))
240 return NULL;
241 if (vs->sym->ctype.modifiers & MOD_STATIC)
242 snprintf(buf, sizeof(buf),"static %s", name);
243 else
244 snprintf(buf, sizeof(buf),"global %s", name);
245 return alloc_sname(buf);
248 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
250 char *size_name;
251 char *array_name = get_data_info_name(array);
252 struct db_info db_info = {.name = array_name,};
254 size_name = vsl_to_data_info_name(name, vsl);
255 if (!size_name)
256 return 0;
258 run_sql(db_limitter_callback, &db_info,
259 "select value from data_info where type = %d and data = '%s';",
260 ARRAY_LEN, size_name);
262 return db_info.ret;
265 static int known_access_ok_comparison(struct expression *expr)
267 struct expression *array;
268 struct expression *size;
269 struct expression *offset;
270 int comparison;
272 array = get_array_base(expr);
273 size = get_size_variable(array);
274 if (!size)
275 return 0;
276 offset = get_array_offset(expr);
277 comparison = get_comparison(size, offset);
278 if (comparison == '>' || comparison == SPECIAL_UNSIGNED_GT)
279 return 1;
281 return 0;
284 static int known_access_ok_numbers(struct expression *expr)
286 struct expression *array;
287 struct expression *offset;
288 sval_t max;
289 int size;
291 array = get_array_base(expr);
292 offset = get_array_offset(expr);
294 size = get_array_size(array);
295 if (size <= 0)
296 return 0;
298 get_absolute_max(offset, &max);
299 if (max.uvalue < size)
300 return 1;
301 return 0;
304 static void array_check_data_info(struct expression *expr)
306 struct expression *array;
307 struct expression *offset;
308 struct state_list *slist;
309 struct sm_state *sm;
310 struct compare_data *comp;
311 char *offset_name;
312 const char *equal_name = NULL;
314 expr = strip_expr(expr);
315 if (!is_array(expr))
316 return;
318 if (known_access_ok_numbers(expr))
319 return;
320 if (known_access_ok_comparison(expr))
321 return;
323 array = get_array_base(expr);
324 offset = get_array_offset(expr);
325 offset_name = expr_to_var(offset);
326 if (!offset_name)
327 return;
328 slist = get_all_possible_equal_comparisons(offset);
329 if (!slist)
330 goto free;
332 FOR_EACH_PTR(slist, sm) {
333 comp = sm->state->data;
334 if (strcmp(comp->var1, offset_name) == 0) {
335 if (db_var_is_array_limit(array, comp->var2, comp->vsl2)) {
336 equal_name = comp->var2;
337 break;
339 } else if (strcmp(comp->var2, offset_name) == 0) {
340 if (db_var_is_array_limit(array, comp->var1, comp->vsl1)) {
341 equal_name = comp->var1;
342 break;
345 } END_FOR_EACH_PTR(sm);
347 if (equal_name) {
348 char *array_name = expr_to_str(array);
350 sm_msg("warn: potential off by one '%s[]' limit '%s'", array_name, equal_name);
351 free_string(array_name);
354 free:
355 free_slist(&slist);
356 free_string(offset_name);
359 static void add_allocation_function(const char *func, void *call_back, int param)
361 add_function_assign_hook(func, call_back, INT_PTR(param));
364 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args)
366 struct expression *arg;
367 struct expression *size;
368 static char buf[32];
369 int i;
371 size = get_size_variable(array);
372 if (!size)
373 return NULL;
375 i = -1;
376 FOR_EACH_PTR(args, arg) {
377 i++;
378 if (arg == array)
379 continue;
380 if (!expr_equiv(arg, size))
381 continue;
382 snprintf(buf, sizeof(buf), "==$%d", i);
383 return buf;
384 } END_FOR_EACH_PTR(arg);
386 return NULL;
389 static void match_call(struct expression *call)
391 struct expression *arg;
392 char *compare;
393 int param;
395 param = -1;
396 FOR_EACH_PTR(call->args, arg) {
397 param++;
398 if (!is_pointer(arg))
399 continue;
400 compare = buf_size_param_comparison(arg, call->args);
401 if (!compare)
402 continue;
403 sql_insert_caller_info(call, ARRAY_LEN, param, "$", compare);
404 } END_FOR_EACH_PTR(arg);
407 static int get_param(int param, char **name, struct symbol **sym)
409 struct symbol *arg;
410 int i;
412 i = 0;
413 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
415 * this is a temporary hack to work around a bug (I think in sparse?)
416 * 2.6.37-rc1:fs/reiserfs/journal.o
417 * If there is a function definition without parameter name found
418 * after a function implementation then it causes a crash.
419 * int foo() {}
420 * int bar(char *);
422 if (arg->ident->name < (char *)100)
423 continue;
424 if (i == param) {
425 *name = arg->ident->name;
426 *sym = arg;
427 return TRUE;
429 i++;
430 } END_FOR_EACH_PTR(arg);
432 return FALSE;
435 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
437 struct expression *array_expr;
438 struct expression *size_expr;
439 struct symbol *size_sym;
440 char *size_name;
441 long param;
442 struct sm_state *tmp;
444 if (strncmp(value, "==$", 3) != 0)
445 return;
446 param = strtol(value + 3, NULL, 10);
447 if (!get_param(param, &size_name, &size_sym))
448 return;
449 array_expr = symbol_expression(array_sym);
450 size_expr = symbol_expression(size_sym);
452 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
453 if (!tmp)
454 return;
455 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
460 static void munge_start_states(struct statement *stmt)
462 struct state_list *slist = NULL;
463 struct sm_state *sm;
464 struct sm_state *poss;
466 FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
467 if (sm->state != &merged)
468 continue;
470 * screw it. let's just assume that if one caller passes the
471 * size then they all do.
473 FOR_EACH_PTR(sm->possible, poss) {
474 if (poss->state != &merged &&
475 poss->state != &undefined) {
476 add_ptr_list(&slist, poss);
477 break;
479 } END_FOR_EACH_PTR(poss);
480 } END_FOR_EACH_SM(sm);
482 FOR_EACH_PTR(slist, sm) {
483 set_state(size_id, sm->name, sm->sym, sm->state);
484 } END_FOR_EACH_PTR(sm);
486 free_slist(&slist);
489 void register_buf_comparison(int id)
491 size_id = id;
493 add_unmatched_state_hook(size_id, &unmatched_state);
495 add_allocation_function("malloc", &match_alloc, 0);
496 add_allocation_function("memdup", &match_alloc, 1);
497 add_allocation_function("realloc", &match_alloc, 1);
498 if (option_project == PROJ_KERNEL) {
499 add_allocation_function("kmalloc", &match_alloc, 0);
500 add_allocation_function("kzalloc", &match_alloc, 0);
501 add_allocation_function("vmalloc", &match_alloc, 0);
502 add_allocation_function("__vmalloc", &match_alloc, 0);
503 add_allocation_function("sock_kmalloc", &match_alloc, 1);
504 add_allocation_function("kmemdup", &match_alloc, 1);
505 add_allocation_function("kmemdup_user", &match_alloc, 1);
506 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
507 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
508 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
509 add_allocation_function("devm_kmalloc", &match_alloc, 1);
510 add_allocation_function("devm_kzalloc", &match_alloc, 1);
511 add_allocation_function("kcalloc", &match_calloc, 0);
512 add_allocation_function("krealloc", &match_alloc, 1);
515 add_hook(&array_check, OP_HOOK);
516 add_hook(&array_check_data_info, OP_HOOK);
518 add_hook(&match_call, FUNCTION_CALL_HOOK);
519 select_caller_info_hook(set_param_compare, ARRAY_LEN);
520 add_hook(&munge_start_states, AFTER_DEF_HOOK);
523 void register_buf_comparison_links(int id)
525 link_id = id;
526 add_modification_hook(link_id, &match_modify);