smatch_comparison: store how two variables compare with each other
[smatch.git] / smatch_buf_size.c
blob2f8cb3abc4a29fcdfb4739ae6e9974d30e7110ef
1 /*
2 * smatch/smatch_buf_size.c
4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include <stdlib.h>
11 #include <errno.h>
12 #include "parse.h"
13 #include "smatch.h"
14 #include "smatch_slist.h"
15 #include "smatch_extra.h"
18 * This check has two smatch IDs.
19 * my_size_id - used to store the size of arrays.
20 * my_strlen_id - track the strlen() of buffers.
23 static int my_size_id;
24 static int my_strlen_id;
26 struct limiter {
27 int buf_arg;
28 int limit_arg;
30 static struct limiter b0_l2 = {0, 2};
32 static _Bool params_set[32];
34 static void set_undefined(struct sm_state *sm)
36 if (sm->state != &undefined)
37 set_state(sm->owner, sm->name, sm->sym, &undefined);
40 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
42 if (PTR_INT(s1->data) == PTR_INT(s2->data))
43 return s1;
44 return &undefined;
47 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
49 char fullname[256];
50 unsigned int size;
52 if (strncmp(key, "$$", 2))
53 return;
55 snprintf(fullname, 256, "%s%s", name, key + 2);
57 errno = 0;
58 size = strtoul(value, NULL, 10);
59 if (errno)
60 return;
62 set_state(my_size_id, fullname, sym, alloc_state_num(size));
65 static int bytes_per_element(struct expression *expr)
67 struct symbol *type;
68 int bpe;
70 if (expr->type == EXPR_STRING)
71 return 1;
72 type = get_type(expr);
73 if (!type)
74 return 0;
76 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
77 return 0;
79 type = get_base_type(type);
80 bpe = bits_to_bytes(type->bit_size);
82 if (bpe == -1) /* void pointer */
83 bpe = 1;
85 return bpe;
88 static int bytes_to_elements(struct expression *expr, int bytes)
90 int bpe;
92 bpe = bytes_per_element(expr);
93 if (bpe == 0)
94 return 0;
95 return bytes / bpe;
98 static int elements_to_bytes(struct expression *expr, int elements)
100 int bpe;
102 bpe = bytes_per_element(expr);
103 return elements * bpe;
106 static int get_initializer_size(struct expression *expr)
108 switch (expr->type) {
109 case EXPR_STRING:
110 return expr->string->length;
111 case EXPR_INITIALIZER: {
112 struct expression *tmp;
113 int i = 0;
114 int max = 0;
116 FOR_EACH_PTR(expr->expr_list, tmp) {
117 if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
118 max = tmp->idx_to;
119 i++;
120 } END_FOR_EACH_PTR(tmp);
121 if (max)
122 return max + 1;
123 return i;
125 case EXPR_SYMBOL:
126 return get_array_size(expr);
128 return 0;
131 static int db_size;
132 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
134 if (db_size == 0)
135 db_size = atoi(argv[0]);
136 else
137 db_size = -1;
138 return 0;
141 static int size_from_db(struct expression *expr)
143 int this_file_only = 0;
144 char *name;
146 if (!option_spammy)
147 return 0;
149 name = get_member_name(expr);
150 if (!name && is_static(expr)) {
151 name = expr_to_str(expr);
152 this_file_only = 1;
154 if (!name)
155 return 0;
157 db_size = 0;
158 run_sql(db_size_callback, "select size from type_size where type = '%s' and file = '%s'",
159 name, get_filename());
160 if (db_size == -1)
161 return 0;
162 if (db_size != 0)
163 return db_size;
164 if (this_file_only)
165 return 0;
167 run_sql(db_size_callback, "select size from type_size where type = '%s'",
168 name);
170 if (db_size == -1)
171 db_size = 0;
173 return db_size;
176 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
178 struct expression *call;
179 sval_t sval;
181 if (expr->type != EXPR_ASSIGNMENT)
182 return;
183 call = strip_expr(expr->right);
185 if (!parse_call_math(call, math, &sval))
186 return;
187 set_state_expr(my_size_id, expr->left, alloc_state_num(sval.value));
190 static int get_real_array_size(struct expression *expr)
192 struct symbol *type;
193 int ret;
195 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
196 return 0;
198 type = get_type(expr);
199 if (!type || type->type != SYM_ARRAY)
200 return 0;
202 ret = get_expression_value(type->array_size);
203 /* Dynamically sized array are -1 in sparse */
204 if (ret <= 0)
205 return 0;
206 /* People put one element arrays on the end of structs */
207 if (ret == 1)
208 return 0;
210 return ret;
213 static int get_size_from_initializer(struct expression *expr)
215 if (expr->type != EXPR_SYMBOL || !expr->symbol->initializer)
216 return 0;
217 if (expr->symbol->initializer == expr) /* int a = a; */
218 return 0;
219 return get_initializer_size(expr->symbol->initializer);
222 static int get_stored_size_bytes(struct expression *expr)
224 struct smatch_state *state;
226 state = get_state_expr(my_size_id, expr);
227 if (!state)
228 return 0;
229 return PTR_INT(state->data);
232 static int get_stored_size_bytes_min(struct expression *expr)
234 struct sm_state *sm, *tmp;
235 int min = 0;
237 sm = get_sm_state_expr(my_size_id, expr);
238 if (!sm)
239 return 0;
240 FOR_EACH_PTR(sm->possible, tmp) {
241 if (PTR_INT(tmp->state->data) <= 0)
242 continue;
243 if (PTR_INT(tmp->state->data) < min)
244 min = PTR_INT(tmp->state->data);
245 } END_FOR_EACH_PTR(tmp);
247 return min;
250 static int get_bytes_from_address(struct expression *expr)
252 struct symbol *type;
253 int ret;
255 if (!option_spammy)
256 return 0;
257 if (expr->type != EXPR_PREOP || expr->op != '&')
258 return 0;
259 type = get_type(expr);
260 if (!type)
261 return 0;
263 if (type->type == SYM_PTR)
264 type = get_base_type(type);
266 ret = bits_to_bytes(type->bit_size);
267 if (ret == -1)
268 return 0;
269 if (ret == 1)
270 return 0; /* ignore char pointers */
272 return ret;
275 static int get_size_from_strlen(struct expression *expr)
277 struct smatch_state *state;
278 sval_t len;
280 state = get_state_expr(my_strlen_id, expr);
281 if (!state || !state->data)
282 return 0;
283 if (get_implied_max((struct expression *)state->data, &len))
284 return len.value + 1; /* add one because strlen doesn't include the NULL */
285 return 0;
288 static struct expression *remove_addr_fluff(struct expression *expr)
290 struct expression *tmp;
291 sval_t sval;
293 expr = strip_expr(expr);
295 /* remove '&' and '*' operations that cancel */
296 while (expr->type == EXPR_PREOP && expr->op == '&') {
297 tmp = strip_expr(expr->unop);
298 if (tmp->type != EXPR_PREOP)
299 break;
300 if (tmp->op != '*')
301 break;
302 expr = strip_expr(tmp->unop);
305 /* "foo + 0" is just "foo" */
306 if (expr->type == EXPR_BINOP && expr->op == '+' &&
307 get_value(expr->right, &sval) && sval.value == 0)
308 return expr->left;
310 return expr;
313 int get_array_size_bytes(struct expression *expr)
315 int size;
317 expr = remove_addr_fluff(expr);
318 if (!expr)
319 return 0;
321 /* strcpy(foo, "BAR"); */
322 if (expr->type == EXPR_STRING)
323 return expr->string->length;
325 /* buf[4] */
326 size = get_real_array_size(expr);
327 if (size)
328 return elements_to_bytes(expr, size);
330 /* buf = malloc(1024); */
331 size = get_stored_size_bytes(expr);
332 if (size)
333 return size;
335 /* char *foo = "BAR" */
336 size = get_size_from_initializer(expr);
337 if (size)
338 return elements_to_bytes(expr, size);
340 size = get_bytes_from_address(expr);
341 if (size)
342 return size;
344 /* if (strlen(foo) > 4) */
345 size = get_size_from_strlen(expr);
346 if (size)
347 return size;
349 return size_from_db(expr);
352 int get_array_size_bytes_min(struct expression *expr)
354 int size;
355 int tmp;
357 size = get_array_size_bytes(expr);
359 tmp = get_stored_size_bytes_min(expr);
360 if (size <= 0 || (tmp >= 1 && tmp < size))
361 size = tmp;
362 return size;
365 int get_array_size(struct expression *expr)
367 int bytes;
369 bytes = get_array_size_bytes(expr);
370 return bytes_to_elements(expr, bytes);
373 static void match_strlen_condition(struct expression *expr)
375 struct expression *left;
376 struct expression *right;
377 struct expression *str = NULL;
378 int strlen_left = 0;
379 int strlen_right = 0;
380 sval_t sval;
381 struct smatch_state *true_state = NULL;
382 struct smatch_state *false_state = NULL;
384 if (expr->type != EXPR_COMPARE)
385 return;
386 left = strip_expr(expr->left);
387 right = strip_expr(expr->right);
389 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
390 str = get_argument_from_call_expr(left->args, 0);
391 strlen_left = 1;
393 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
394 str = get_argument_from_call_expr(right->args, 0);
395 strlen_right = 1;
398 if (!strlen_left && !strlen_right)
399 return;
400 if (strlen_left && strlen_right)
401 return;
403 if (strlen_left) {
404 if (!get_value(right, &sval))
405 return;
407 if (strlen_right) {
408 if (!get_value(left, &sval))
409 return;
412 if (expr->op == SPECIAL_EQUAL) {
413 set_true_false_states_expr(my_size_id, str, alloc_state_num(sval.value + 1), NULL);
414 return;
416 if (expr->op == SPECIAL_NOTEQUAL) {
417 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(sval.value + 1));
418 return;
421 switch (expr->op) {
422 case '<':
423 case SPECIAL_UNSIGNED_LT:
424 if (strlen_left)
425 true_state = alloc_state_num(sval.value);
426 else
427 false_state = alloc_state_num(sval.value + 1);
428 break;
429 case SPECIAL_LTE:
430 case SPECIAL_UNSIGNED_LTE:
431 if (strlen_left)
432 true_state = alloc_state_num(sval.value + 1);
433 else
434 false_state = alloc_state_num(sval.value);
435 break;
436 case SPECIAL_GTE:
437 case SPECIAL_UNSIGNED_GTE:
438 if (strlen_left)
439 false_state = alloc_state_num(sval.value);
440 else
441 true_state = alloc_state_num(sval.value + 1);
442 break;
443 case '>':
444 case SPECIAL_UNSIGNED_GT:
445 if (strlen_left)
446 false_state = alloc_state_num(sval.value + 1);
447 else
448 true_state = alloc_state_num(sval.value);
449 break;
451 set_true_false_states_expr(my_size_id, str, true_state, false_state);
454 static struct expression *strip_ampersands(struct expression *expr)
456 struct symbol *type;
458 if (expr->type != EXPR_PREOP)
459 return expr;
460 if (expr->op != '&')
461 return expr;
462 type = get_type(expr->unop);
463 if (!type || type->type != SYM_ARRAY)
464 return expr;
465 return expr->unop;
468 static void match_array_assignment(struct expression *expr)
470 struct expression *left;
471 struct expression *right;
472 int array_size;
474 if (expr->op != '=')
475 return;
476 left = strip_expr(expr->left);
477 right = strip_expr(expr->right);
478 right = strip_ampersands(right);
479 array_size = get_array_size_bytes(right);
480 if (array_size)
481 set_state_expr(my_size_id, left, alloc_state_num(array_size));
484 static void info_record_alloction(struct expression *buffer, struct expression *size)
486 char *name;
487 sval_t sval;
489 if (!option_info)
490 return;
492 name = get_member_name(buffer);
493 if (!name && is_static(buffer))
494 name = expr_to_str(buffer);
495 if (!name)
496 return;
497 if (get_implied_value(size, &sval))
498 sm_msg("info: '%s' allocated_buf_size %s", name, sval_to_str(sval));
499 else
500 sm_msg("info: '%s' allocated_buf_size -1", name);
501 free_string(name);
504 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
506 int size_arg = PTR_INT(_size_arg);
507 struct expression *right;
508 struct expression *arg;
509 sval_t bytes;
511 right = strip_expr(expr->right);
512 arg = get_argument_from_call_expr(right->args, size_arg);
514 info_record_alloction(expr->left, arg);
516 if (!get_implied_value(arg, &bytes))
517 return;
518 set_state_expr(my_size_id, expr->left, alloc_state_num(bytes.value));
521 static void match_calloc(const char *fn, struct expression *expr, void *unused)
523 struct expression *right;
524 struct expression *arg;
525 sval_t elements;
526 sval_t size;
528 right = strip_expr(expr->right);
529 arg = get_argument_from_call_expr(right->args, 0);
530 if (!get_implied_value(arg, &elements))
531 return;
532 arg = get_argument_from_call_expr(right->args, 1);
533 if (!get_implied_value(arg, &size))
534 return;
535 set_state_expr(my_size_id, expr->left, alloc_state_num(elements.value * size.value));
538 static void match_strlen(const char *fn, struct expression *expr, void *unused)
540 struct expression *right;
541 struct expression *str;
542 struct expression *len_expr;
543 char *len_name;
544 struct smatch_state *state;
546 right = strip_expr(expr->right);
547 str = get_argument_from_call_expr(right->args, 0);
548 len_expr = strip_expr(expr->left);
550 len_name = expr_to_str(len_expr);
551 if (!len_name)
552 return;
554 state = __alloc_smatch_state(0);
555 state->name = len_name;
556 state->data = len_expr;
557 set_state_expr(my_strlen_id, str, state);
560 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
562 struct limiter *limiter = (struct limiter *)_limiter;
563 struct expression *dest;
564 struct expression *size_expr;
565 sval_t size;
567 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
568 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
569 if (!get_implied_max(size_expr, &size))
570 return;
571 set_state_expr(my_size_id, dest, alloc_state_num(size.value));
574 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
576 struct expression fake_assign;
578 fake_assign.op = '=';
579 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
580 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
581 match_array_assignment(&fake_assign);
584 static void match_strndup(const char *fn, struct expression *expr, void *unused)
586 struct expression *fn_expr;
587 struct expression *size_expr;
588 sval_t size;
590 fn_expr = strip_expr(expr->right);
591 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
592 if (!get_implied_max(size_expr, &size))
593 return;
595 /* It's easy to forget space for the NUL char */
596 size.value++;
597 set_state_expr(my_size_id, expr->left, alloc_state_num(size.value));
600 static void match_call(struct expression *expr)
602 char *name;
603 struct expression *arg;
604 int bytes;
605 int i;
607 name = get_fnptr_name(expr->fn);
608 if (!name)
609 return;
611 i = 0;
612 FOR_EACH_PTR(expr->args, arg) {
613 bytes = get_array_size_bytes(arg);
614 if (bytes > 1)
615 sm_msg("info: passes_buffer '%s' %d '$$' %d %s",
616 name, i, bytes,
617 is_static(expr->fn) ? "static" : "global");
618 i++;
619 } END_FOR_EACH_PTR(arg);
621 free_string(name);
624 static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state)
626 if (state == &merged)
627 return;
628 sm_msg("info: passes_buffer '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static);
631 static void match_func_end(struct symbol *sym)
633 memset(params_set, 0, sizeof(params_set));
636 void register_buf_size(int id)
638 my_size_id = id;
640 add_definition_db_callback(set_param_buf_size, BUF_SIZE);
641 add_db_return_states_callback(BUF_SIZE, &db_returns_buf_size);
643 add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
644 add_function_assign_hook("calloc", &match_calloc, NULL);
645 add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
646 if (option_project == PROJ_KERNEL) {
647 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
648 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
649 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
650 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
651 add_function_assign_hook("kcalloc", &match_calloc, NULL);
652 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
653 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
654 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
655 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
656 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
657 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
659 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
660 add_hook(&match_strlen_condition, CONDITION_HOOK);
661 add_function_assign_hook("strlen", &match_strlen, NULL);
663 add_function_assign_hook("strndup", match_strndup, NULL);
664 if (option_project == PROJ_KERNEL)
665 add_function_assign_hook("kstrndup", match_strndup, NULL);
667 add_hook(&match_func_end, END_FUNC_HOOK);
668 add_modification_hook(my_size_id, &set_undefined);
670 add_merge_hook(my_size_id, &merge_func);
673 void register_strlen(int id)
675 my_strlen_id = id;
676 add_modification_hook(my_strlen_id, &set_undefined);
677 add_merge_hook(my_strlen_id, &merge_func);
680 void register_buf_size_late(int id)
682 add_function_hook("strlcpy", &match_limited, &b0_l2);
683 add_function_hook("strlcat", &match_limited, &b0_l2);
684 add_function_hook("memscan", &match_limited, &b0_l2);
686 add_function_hook("strcpy", &match_strcpy, NULL);
688 if (option_info) {
689 add_hook(&match_call, FUNCTION_CALL_HOOK);
690 add_member_info_callback(my_size_id, struct_member_callback);