db: rename FILTER_VALUE, LIMITED_VALUE, and ADDED_VALUE
[smatch.git] / smatch_buf_size.c
blobf56a9e67cb66ccf8f6dffeac91f4f6e0978bad3b
1 /*
2 * Copyright (C) 2010 Dan Carpenter.
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
18 #include <stdlib.h>
19 #include <errno.h>
20 #include "parse.h"
21 #include "smatch.h"
22 #include "smatch_slist.h"
23 #include "smatch_extra.h"
24 #include "smatch_function_hashtable.h"
26 #define UNKNOWN_SIZE (-1)
28 static int my_size_id;
30 struct limiter {
31 int buf_arg;
32 int limit_arg;
34 static struct limiter b0_l2 = {0, 2};
36 static DEFINE_HASHTABLE_INSERT(insert_func, char, int);
37 static DEFINE_HASHTABLE_SEARCH(search_func, char, int);
38 static struct hashtable *allocation_funcs;
40 static char *get_fn_name(struct expression *expr)
42 if (expr->type != EXPR_CALL)
43 return NULL;
44 if (expr->fn->type != EXPR_SYMBOL)
45 return NULL;
46 return expr_to_var(expr->fn);
49 static int is_allocation_function(struct expression *expr)
51 char *func;
52 int ret = 0;
54 func = get_fn_name(expr);
55 if (!func)
56 return 0;
57 if (search_func(allocation_funcs, func))
58 ret = 1;
59 free_string(func);
60 return ret;
63 static void add_allocation_function(const char *func, void *call_back, int param)
65 insert_func(allocation_funcs, (char *)func, (int *)1);
66 add_function_assign_hook(func, call_back, INT_PTR(param));
69 static int estate_to_size(struct smatch_state *state)
71 sval_t sval;
73 if (!state || !estate_rl(state))
74 return 0;
75 sval = estate_max(state);
76 return sval.value;
79 static struct smatch_state *size_to_estate(int size)
81 sval_t sval;
83 sval.type = &int_ctype;
84 sval.value = size;
86 return alloc_estate_sval(sval);
89 static struct range_list *size_to_rl(int size)
91 sval_t sval;
93 sval.type = &int_ctype;
94 sval.value = size;
96 return alloc_rl(sval, sval);
99 static struct smatch_state *unmatched_size_state(struct sm_state *sm)
101 return size_to_estate(UNKNOWN_SIZE);
104 static void set_size_undefined(struct sm_state *sm, struct expression *mod_expr)
106 set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
109 static struct smatch_state *merge_size_func(struct smatch_state *s1, struct smatch_state *s2)
111 return merge_estates(s1, s2);
114 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
116 struct range_list *rl = NULL;
117 struct smatch_state *state;
118 char fullname[256];
120 if (strncmp(key, "$", 1) != 0)
121 return;
123 snprintf(fullname, 256, "%s%s", name, key + 1);
125 str_to_rl(&int_ctype, value, &rl);
126 if (!rl || is_whole_rl(rl))
127 return;
128 state = alloc_estate_rl(rl);
129 set_state(my_size_id, fullname, sym, state);
132 static int bytes_per_element(struct expression *expr)
134 struct symbol *type;
136 if (!expr)
137 return 0;
138 if (expr->type == EXPR_STRING)
139 return 1;
140 type = get_type(expr);
141 if (!type)
142 return 0;
144 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
145 return 0;
147 type = get_base_type(type);
148 return type_bytes(type);
151 static int bytes_to_elements(struct expression *expr, int bytes)
153 int bpe;
155 bpe = bytes_per_element(expr);
156 if (bpe == 0)
157 return 0;
158 return bytes / bpe;
161 static int elements_to_bytes(struct expression *expr, int elements)
163 int bpe;
165 bpe = bytes_per_element(expr);
166 return elements * bpe;
169 static int get_initializer_size(struct expression *expr)
171 switch (expr->type) {
172 case EXPR_STRING:
173 return expr->string->length;
174 case EXPR_INITIALIZER: {
175 struct expression *tmp;
176 int i = 0;
178 FOR_EACH_PTR(expr->expr_list, tmp) {
179 if (tmp->type == EXPR_INDEX) {
180 if (tmp->idx_to >= i)
181 i = tmp->idx_to;
182 else
183 continue;
186 i++;
187 } END_FOR_EACH_PTR(tmp);
188 return i;
190 case EXPR_SYMBOL:
191 return get_array_size(expr);
193 return 0;
196 static struct range_list *db_size_rl;
197 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
199 struct range_list *tmp = NULL;
201 if (!db_size_rl) {
202 str_to_rl(&int_ctype, argv[0], &db_size_rl);
203 } else {
204 str_to_rl(&int_ctype, argv[0], &tmp);
205 db_size_rl = rl_union(db_size_rl, tmp);
207 return 0;
210 static struct range_list *size_from_db(struct expression *expr)
212 int this_file_only = 0;
213 char *name;
215 name = get_member_name(expr);
216 if (!name && is_static(expr)) {
217 name = expr_to_var(expr);
218 this_file_only = 1;
220 if (!name)
221 return 0;
223 if (this_file_only) {
224 db_size_rl = NULL;
225 run_sql(db_size_callback, NULL,
226 "select size from function_type_size where type = '%s' and file = '%s';",
227 name, get_filename());
228 if (db_size_rl)
229 return db_size_rl;
230 return 0;
233 db_size_rl = NULL;
234 run_sql(db_size_callback, NULL,
235 "select size from type_size where type = '%s';",
236 name);
237 return db_size_rl;
240 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
242 struct expression *call;
243 sval_t sval;
245 if (expr->type != EXPR_ASSIGNMENT)
246 return;
247 call = strip_expr(expr->right);
249 if (!parse_call_math(call, math, &sval))
250 return;
251 set_state_expr(my_size_id, expr->left, size_to_estate(sval.value));
254 int get_real_array_size(struct expression *expr)
256 struct symbol *type;
257 sval_t sval;
259 if (!expr)
260 return 0;
261 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
262 return 0;
264 type = get_type(expr);
265 if (!type)
266 return 0;
267 if (!type || type->type != SYM_ARRAY)
268 return 0;
270 if (!get_implied_value(type->array_size, &sval))
271 return 0;
273 /* People put one element arrays on the end of structs */
274 if (sval.value == 1)
275 return 0;
277 return sval.value;
280 static int get_size_from_initializer(struct expression *expr)
282 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
283 return 0;
284 if (expr->symbol->initializer == expr) /* int a = a; */
285 return 0;
286 return get_initializer_size(expr->symbol->initializer);
289 static struct range_list *get_stored_size_bytes(struct expression *expr)
291 struct smatch_state *state;
293 state = get_state_expr(my_size_id, expr);
294 if (!state)
295 return NULL;
296 return estate_rl(state);
299 static int get_bytes_from_address(struct expression *expr)
301 struct symbol *type;
302 int ret;
304 if (!option_spammy)
305 return 0;
306 if (expr->type != EXPR_PREOP || expr->op != '&')
307 return 0;
308 type = get_type(expr);
309 if (!type)
310 return 0;
312 if (type->type == SYM_PTR)
313 type = get_base_type(type);
315 ret = type_bytes(type);
316 if (ret == 1)
317 return 0; /* ignore char pointers */
319 return ret;
322 static struct expression *remove_addr_fluff(struct expression *expr)
324 struct expression *tmp;
325 sval_t sval;
327 expr = strip_expr(expr);
329 /* remove '&' and '*' operations that cancel */
330 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
331 tmp = strip_expr(expr->unop);
332 if (tmp->type != EXPR_PREOP)
333 break;
334 if (tmp->op != '*')
335 break;
336 expr = strip_expr(tmp->unop);
339 if (!expr)
340 return NULL;
342 /* "foo + 0" is just "foo" */
343 if (expr->type == EXPR_BINOP && expr->op == '+' &&
344 get_value(expr->right, &sval) && sval.value == 0)
345 return expr->left;
347 return expr;
350 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
352 struct symbol *tmp;
353 int i;
355 i = 0;
356 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
357 if (i++ || !tmp->ident)
358 return 0;
359 if (tmp->ident == member)
360 return 1;
361 return 0;
362 } END_FOR_EACH_PTR_REVERSE(tmp);
364 return 0;
367 static int get_stored_size_end_struct_bytes(struct expression *expr)
369 struct symbol *type;
370 char *name;
371 struct symbol *sym;
372 struct smatch_state *state;
373 sval_t sval;
375 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
376 return 0;
378 type = get_type(expr);
379 if (!type || type->type != SYM_ARRAY)
380 return 0;
382 if (!get_implied_value(type->array_size, &sval))
383 return 0;
385 if (sval.value != 0 && sval.value != 1)
386 return 0;
388 name = expr_to_var_sym(expr, &sym);
389 free_string(name);
390 if (!sym || !sym->ident)
391 return 0;
392 if (!type_bytes(sym))
393 return 0;
395 if (sym->type != SYM_NODE)
396 return 0;
398 state = get_state(my_size_id, sym->ident->name, sym);
399 if (!estate_to_size(state))
400 return 0;
402 sym = get_real_base_type(sym);
403 if (!sym || sym->type != SYM_PTR)
404 return 0;
405 sym = get_real_base_type(sym);
406 if (!sym || sym->type != SYM_STRUCT)
407 return 0;
408 if (!is_last_member_of_struct(sym, expr->member))
409 return 0;
411 return estate_to_size(state) - type_bytes(sym) + type_bytes(type);
414 static struct range_list *alloc_int_rl(int value)
416 sval_t sval = {
417 .type = &int_ctype,
418 {.value = value},
421 return alloc_rl(sval, sval);
424 struct range_list *get_array_size_bytes_rl(struct expression *expr)
426 int declared_size = 0;
427 struct range_list *ret = NULL;
428 int size;
430 expr = remove_addr_fluff(expr);
431 if (!expr)
432 return NULL;
434 /* "BAR" */
435 if (expr->type == EXPR_STRING)
436 return alloc_int_rl(expr->string->length);
438 if (expr->type == EXPR_BINOP && expr->op == '+') {
439 sval_t offset;
441 if (!get_implied_value(expr->right, &offset))
442 return NULL;
443 size = get_array_size_bytes(expr->left);
444 if (size <= 0)
445 return NULL;
446 return alloc_int_rl(size - offset.value);
449 /* buf[4] */
450 size = get_real_array_size(expr);
451 if (size)
452 declared_size = elements_to_bytes(expr, size);
454 /* buf = malloc(1024); */
455 ret = get_stored_size_bytes(expr);
456 if (ret) {
457 if (declared_size)
458 return rl_union(ret, alloc_int_rl(size));
459 return ret;
461 if (declared_size)
462 return alloc_int_rl(declared_size);
464 size = get_stored_size_end_struct_bytes(expr);
465 if (size)
466 return alloc_int_rl(size);
468 /* char *foo = "BAR" */
469 size = get_size_from_initializer(expr);
470 if (size)
471 return alloc_int_rl(elements_to_bytes(expr, size));
473 size = get_bytes_from_address(expr);
474 if (size)
475 return alloc_int_rl(size);
477 /* if (strlen(foo) > 4) */
478 size = get_size_from_strlen(expr);
479 if (size)
480 return alloc_int_rl(size);
482 ret = size_from_db(expr);
483 if (ret)
484 return ret;
486 return NULL;
489 int get_array_size_bytes(struct expression *expr)
491 struct range_list *rl;
492 sval_t sval;
494 rl = get_array_size_bytes_rl(expr);
495 if (!rl_to_sval(rl, &sval))
496 return 0;
497 if (sval.uvalue >= INT_MAX)
498 return 0;
499 return sval.value;
502 int get_array_size_bytes_max(struct expression *expr)
504 struct range_list *rl;
505 sval_t bytes;
507 rl = get_array_size_bytes_rl(expr);
508 if (!rl)
509 return 0;
510 bytes = rl_min(rl);
511 if (bytes.value < 0)
512 return 0;
513 bytes = rl_max(rl);
514 if (bytes.uvalue >= INT_MAX)
515 return 0;
516 return bytes.value;
519 int get_array_size_bytes_min(struct expression *expr)
521 struct range_list *rl;
522 struct data_range *range;
524 rl = get_array_size_bytes_rl(expr);
525 if (!rl)
526 return 0;
528 FOR_EACH_PTR(rl, range) {
529 if (range->min.value <= 0)
530 return 0;
531 if (range->max.value <= 0)
532 return 0;
533 if (range->min.uvalue >= INT_MAX)
534 return 0;
535 return range->min.value;
536 } END_FOR_EACH_PTR(range);
538 return 0;
541 int get_array_size(struct expression *expr)
543 if (!expr)
544 return 0;
545 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
548 static void match_strlen_condition(struct expression *expr)
550 struct expression *left;
551 struct expression *right;
552 struct expression *str = NULL;
553 int strlen_left = 0;
554 int strlen_right = 0;
555 sval_t sval;
556 struct smatch_state *true_state = NULL;
557 struct smatch_state *false_state = NULL;
559 if (expr->type != EXPR_COMPARE)
560 return;
561 left = strip_expr(expr->left);
562 right = strip_expr(expr->right);
564 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
565 str = get_argument_from_call_expr(left->args, 0);
566 strlen_left = 1;
568 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
569 str = get_argument_from_call_expr(right->args, 0);
570 strlen_right = 1;
573 if (!strlen_left && !strlen_right)
574 return;
575 if (strlen_left && strlen_right)
576 return;
578 if (strlen_left) {
579 if (!get_value(right, &sval))
580 return;
582 if (strlen_right) {
583 if (!get_value(left, &sval))
584 return;
587 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
589 if (expr->op == SPECIAL_EQUAL) {
590 set_true_false_states_expr(my_size_id, str, size_to_estate(sval.value + 1), NULL);
591 return;
593 if (expr->op == SPECIAL_NOTEQUAL) {
594 set_true_false_states_expr(my_size_id, str, NULL, size_to_estate(sval.value + 1));
595 return;
598 switch (expr->op) {
599 case '<':
600 case SPECIAL_UNSIGNED_LT:
601 if (strlen_left)
602 true_state = size_to_estate(sval.value);
603 else
604 false_state = size_to_estate(sval.value + 1);
605 break;
606 case SPECIAL_LTE:
607 case SPECIAL_UNSIGNED_LTE:
608 if (strlen_left)
609 true_state = size_to_estate(sval.value + 1);
610 else
611 false_state = size_to_estate(sval.value);
612 break;
613 case SPECIAL_GTE:
614 case SPECIAL_UNSIGNED_GTE:
615 if (strlen_left)
616 false_state = size_to_estate(sval.value);
617 else
618 true_state = size_to_estate(sval.value + 1);
619 break;
620 case '>':
621 case SPECIAL_UNSIGNED_GT:
622 if (strlen_left) {
623 true_state = size_to_estate(-1);
624 false_state = size_to_estate(sval.value + 1);
625 } else
626 true_state = size_to_estate(sval.value);
627 break;
629 set_true_false_states_expr(my_size_id, str, true_state, false_state);
632 static struct expression *strip_ampersands(struct expression *expr)
634 struct symbol *type;
636 if (expr->type != EXPR_PREOP)
637 return expr;
638 if (expr->op != '&')
639 return expr;
640 type = get_type(expr->unop);
641 if (!type || type->type != SYM_ARRAY)
642 return expr;
643 return expr->unop;
646 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
648 char *name;
650 if (!option_info)
651 return;
653 name = get_member_name(buffer);
654 if (!name && is_static(buffer))
655 name = expr_to_var(buffer);
656 if (!name)
657 return;
658 if (rl && !is_whole_rl(rl))
659 sql_insert_function_type_size(name, show_rl(rl));
660 else
661 sql_insert_function_type_size(name, "(-1)");
663 free_string(name);
666 static void store_alloc(struct expression *expr, struct range_list *rl)
668 rl = clone_rl(rl); // FIXME!!!
669 info_record_alloction(expr, rl);
670 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
673 static void match_array_assignment(struct expression *expr)
675 struct expression *left;
676 struct expression *right;
677 char *left_member, *right_member;
678 struct range_list *rl;
679 sval_t sval;
681 if (expr->op != '=')
682 return;
683 left = strip_expr(expr->left);
684 right = strip_expr(expr->right);
685 right = strip_ampersands(right);
687 if (!is_pointer(left))
688 return;
689 if (is_allocation_function(right))
690 return;
692 left_member = get_member_name(left);
693 right_member = get_member_name(right);
694 if (left_member && right_member && strcmp(left_member, right_member) == 0) {
695 free_string(left_member);
696 free_string(right_member);
697 return;
699 free_string(left_member);
700 free_string(right_member);
702 if (get_implied_value(right, &sval) && sval.value == 0) {
703 rl = alloc_int_rl(0);
704 goto store;
707 rl = get_array_size_bytes_rl(right);
709 store:
710 store_alloc(left, rl);
713 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
715 int size_arg = PTR_INT(_size_arg);
716 struct expression *right;
717 struct expression *arg;
718 struct range_list *rl;
720 right = strip_expr(expr->right);
721 arg = get_argument_from_call_expr(right->args, size_arg);
722 get_absolute_rl(arg, &rl);
723 rl = cast_rl(&int_ctype, rl);
724 store_alloc(expr->left, rl);
727 static void match_calloc(const char *fn, struct expression *expr, void *unused)
729 struct expression *right;
730 struct expression *arg;
731 sval_t elements;
732 sval_t size;
734 right = strip_expr(expr->right);
735 arg = get_argument_from_call_expr(right->args, 0);
736 if (!get_implied_value(arg, &elements))
737 return; // FIXME!!!
738 arg = get_argument_from_call_expr(right->args, 1);
739 if (get_implied_value(arg, &size))
740 store_alloc(expr->left, size_to_rl(elements.value * size.value));
741 else
742 store_alloc(expr->left, size_to_rl(-1));
745 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
747 struct limiter *limiter = (struct limiter *)_limiter;
748 struct expression *dest;
749 struct expression *size_expr;
750 sval_t size;
752 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
753 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
754 if (!get_implied_max(size_expr, &size))
755 return;
756 set_state_expr(my_size_id, dest, size_to_estate(size.value));
759 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
761 struct expression fake_assign;
763 fake_assign.op = '=';
764 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
765 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
766 match_array_assignment(&fake_assign);
769 static void match_strndup(const char *fn, struct expression *expr, void *unused)
771 struct expression *fn_expr;
772 struct expression *size_expr;
773 sval_t size;
775 fn_expr = strip_expr(expr->right);
776 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
777 if (get_implied_max(size_expr, &size)) {
778 size.value++;
779 store_alloc(expr->left, size_to_rl(size.value));
780 } else {
781 store_alloc(expr->left, size_to_rl(-1));
786 static void match_call(struct expression *expr)
788 struct expression *arg;
789 struct symbol *type;
790 struct range_list *rl;
791 int i;
793 i = -1;
794 FOR_EACH_PTR(expr->args, arg) {
795 i++;
796 type = get_type(arg);
797 if (!type || (type->type != SYM_PTR && type->type != SYM_ARRAY))
798 continue;
799 rl = get_array_size_bytes_rl(arg);
800 if (!rl)
801 continue;
802 if (is_whole_rl(rl))
803 continue;
804 sql_insert_caller_info(expr, BUF_SIZE, i, "$", show_rl(rl));
805 } END_FOR_EACH_PTR(arg);
808 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
810 if (sm->state == &merged ||
811 strcmp(sm->state->name, "(-1)") == 0 ||
812 strcmp(sm->state->name, "empty") == 0 ||
813 strcmp(sm->state->name, "0") == 0)
814 return;
815 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, sm->state->name);
818 void register_buf_size(int id)
820 my_size_id = id;
822 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
824 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
825 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
827 allocation_funcs = create_function_hashtable(100);
828 add_allocation_function("malloc", &match_alloc, 0);
829 add_allocation_function("calloc", &match_calloc, 0);
830 add_allocation_function("memdup", &match_alloc, 1);
831 add_allocation_function("realloc", &match_alloc, 1);
832 if (option_project == PROJ_KERNEL) {
833 add_allocation_function("kmalloc", &match_alloc, 0);
834 add_allocation_function("kzalloc", &match_alloc, 0);
835 add_allocation_function("vmalloc", &match_alloc, 0);
836 add_allocation_function("__vmalloc", &match_alloc, 0);
837 add_allocation_function("kcalloc", &match_calloc, 0);
838 add_allocation_function("kmalloc_array", &match_calloc, 0);
839 add_allocation_function("drm_malloc_ab", &match_calloc, 0);
840 add_allocation_function("drm_calloc_large", &match_calloc, 0);
841 add_allocation_function("sock_kmalloc", &match_alloc, 1);
842 add_allocation_function("kmemdup", &match_alloc, 1);
843 add_allocation_function("kmemdup_user", &match_alloc, 1);
844 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
845 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
846 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
847 add_allocation_function("devm_kmalloc", &match_alloc, 1);
848 add_allocation_function("devm_kzalloc", &match_alloc, 1);
849 add_allocation_function("krealloc", &match_alloc, 1);
851 add_hook(&match_strlen_condition, CONDITION_HOOK);
853 add_allocation_function("strndup", match_strndup, 0);
854 if (option_project == PROJ_KERNEL)
855 add_allocation_function("kstrndup", match_strndup, 0);
857 add_modification_hook(my_size_id, &set_size_undefined);
859 add_merge_hook(my_size_id, &merge_size_func);
862 void register_buf_size_late(int id)
864 /* has to happen after match_alloc() */
865 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
867 add_function_hook("strlcpy", &match_limited, &b0_l2);
868 add_function_hook("strlcat", &match_limited, &b0_l2);
869 add_function_hook("memscan", &match_limited, &b0_l2);
871 add_function_hook("strcpy", &match_strcpy, NULL);
873 add_hook(&match_call, FUNCTION_CALL_HOOK);
874 add_member_info_callback(my_size_id, struct_member_callback);