slist: introduce merge_fake_stree()
[smatch.git] / smatch_buf_size.c
blobc051212c0b9ff6e5a0129302ad4848bfe8b67717
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, "$$", 2) != 0)
121 return;
123 snprintf(fullname, 256, "%s%s", name, key + 2);
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->type == EXPR_STRING)
137 return 1;
138 type = get_type(expr);
139 if (!type)
140 return 0;
142 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
143 return 0;
145 type = get_base_type(type);
146 return type_bytes(type);
149 static int bytes_to_elements(struct expression *expr, int bytes)
151 int bpe;
153 bpe = bytes_per_element(expr);
154 if (bpe == 0)
155 return 0;
156 return bytes / bpe;
159 static int elements_to_bytes(struct expression *expr, int elements)
161 int bpe;
163 bpe = bytes_per_element(expr);
164 return elements * bpe;
167 static int get_initializer_size(struct expression *expr)
169 switch (expr->type) {
170 case EXPR_STRING:
171 return expr->string->length;
172 case EXPR_INITIALIZER: {
173 struct expression *tmp;
174 int i = 0;
176 FOR_EACH_PTR(expr->expr_list, tmp) {
177 if (tmp->type == EXPR_INDEX) {
178 if (tmp->idx_to >= i)
179 i = tmp->idx_to;
180 else
181 continue;
184 i++;
185 } END_FOR_EACH_PTR(tmp);
186 return i;
188 case EXPR_SYMBOL:
189 return get_array_size(expr);
191 return 0;
194 static struct range_list *db_size_rl;
195 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
197 struct range_list *tmp = NULL;
199 if (!db_size_rl) {
200 str_to_rl(&int_ctype, argv[0], &db_size_rl);
201 } else {
202 str_to_rl(&int_ctype, argv[0], &tmp);
203 db_size_rl = rl_union(db_size_rl, tmp);
205 return 0;
208 static struct range_list *size_from_db(struct expression *expr)
210 int this_file_only = 0;
211 char *name;
213 name = get_member_name(expr);
214 if (!name && is_static(expr)) {
215 name = expr_to_var(expr);
216 this_file_only = 1;
218 if (!name)
219 return 0;
221 if (this_file_only) {
222 db_size_rl = NULL;
223 run_sql(db_size_callback, "select size from function_type_size where type = '%s' and file = '%s';",
224 name, get_filename());
225 if (db_size_rl)
226 return db_size_rl;
227 return 0;
230 db_size_rl = NULL;
231 run_sql(db_size_callback, "select size from type_size where type = '%s';",
232 name);
233 return db_size_rl;
236 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
238 struct expression *call;
239 sval_t sval;
241 if (expr->type != EXPR_ASSIGNMENT)
242 return;
243 call = strip_expr(expr->right);
245 if (!parse_call_math(call, math, &sval))
246 return;
247 set_state_expr(my_size_id, expr->left, size_to_estate(sval.value));
250 int get_real_array_size(struct expression *expr)
252 struct symbol *type;
253 sval_t sval;
255 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
256 return 0;
258 type = get_type(expr);
259 if (!type)
260 return 0;
261 if (!type || type->type != SYM_ARRAY)
262 return 0;
264 if (!get_implied_value(type->array_size, &sval))
265 return 0;
267 /* People put one element arrays on the end of structs */
268 if (sval.value == 1)
269 return 0;
271 return sval.value;
274 static int get_size_from_initializer(struct expression *expr)
276 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
277 return 0;
278 if (expr->symbol->initializer == expr) /* int a = a; */
279 return 0;
280 return get_initializer_size(expr->symbol->initializer);
283 static struct range_list *get_stored_size_bytes(struct expression *expr)
285 struct smatch_state *state;
287 state = get_state_expr(my_size_id, expr);
288 if (!state)
289 return NULL;
290 return estate_rl(state);
293 static int get_bytes_from_address(struct expression *expr)
295 struct symbol *type;
296 int ret;
298 if (!option_spammy)
299 return 0;
300 if (expr->type != EXPR_PREOP || expr->op != '&')
301 return 0;
302 type = get_type(expr);
303 if (!type)
304 return 0;
306 if (type->type == SYM_PTR)
307 type = get_base_type(type);
309 ret = type_bytes(type);
310 if (ret == 1)
311 return 0; /* ignore char pointers */
313 return ret;
316 static struct expression *remove_addr_fluff(struct expression *expr)
318 struct expression *tmp;
319 sval_t sval;
321 expr = strip_expr(expr);
323 /* remove '&' and '*' operations that cancel */
324 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
325 tmp = strip_expr(expr->unop);
326 if (tmp->type != EXPR_PREOP)
327 break;
328 if (tmp->op != '*')
329 break;
330 expr = strip_expr(tmp->unop);
333 if (!expr)
334 return NULL;
336 /* "foo + 0" is just "foo" */
337 if (expr->type == EXPR_BINOP && expr->op == '+' &&
338 get_value(expr->right, &sval) && sval.value == 0)
339 return expr->left;
341 return expr;
344 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
346 struct symbol *tmp;
347 int i;
349 i = 0;
350 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
351 if (i++ || !tmp->ident)
352 return 0;
353 if (tmp->ident == member)
354 return 1;
355 return 0;
356 } END_FOR_EACH_PTR_REVERSE(tmp);
358 return 0;
361 static int get_stored_size_end_struct_bytes(struct expression *expr)
363 struct symbol *type;
364 char *name;
365 struct symbol *sym;
366 struct smatch_state *state;
367 sval_t sval;
369 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
370 return 0;
372 type = get_type(expr);
373 if (!type || type->type != SYM_ARRAY)
374 return 0;
376 if (!get_implied_value(type->array_size, &sval))
377 return 0;
379 if (sval.value != 0 && sval.value != 1)
380 return 0;
382 name = expr_to_var_sym(expr, &sym);
383 free_string(name);
384 if (!sym || !sym->ident || !sym->ident->name)
385 return 0;
386 if (!type_bytes(sym))
387 return 0;
389 if (sym->type != SYM_NODE)
390 return 0;
392 state = get_state(my_size_id, sym->ident->name, sym);
393 if (!estate_to_size(state))
394 return 0;
396 sym = get_real_base_type(sym);
397 if (!sym || sym->type != SYM_PTR)
398 return 0;
399 sym = get_real_base_type(sym);
400 if (!sym || sym->type != SYM_STRUCT)
401 return 0;
402 if (!is_last_member_of_struct(sym, expr->member))
403 return 0;
405 return estate_to_size(state) - type_bytes(sym) + type_bytes(type);
408 static struct range_list *alloc_int_rl(int value)
410 sval_t sval = {
411 .type = &int_ctype,
412 {.value = value},
415 return alloc_rl(sval, sval);
418 struct range_list *get_array_size_bytes_rl(struct expression *expr)
420 int declared_size = 0;
421 struct range_list *ret = NULL;
422 int size;
424 expr = remove_addr_fluff(expr);
425 if (!expr)
426 return NULL;
428 /* "BAR" */
429 if (expr->type == EXPR_STRING)
430 return alloc_int_rl(expr->string->length);
432 /* buf[4] */
433 size = get_real_array_size(expr);
434 if (size)
435 declared_size = elements_to_bytes(expr, size);
437 /* buf = malloc(1024); */
438 ret = get_stored_size_bytes(expr);
439 if (ret) {
440 if (declared_size)
441 return rl_union(ret, alloc_int_rl(size));
442 return ret;
444 if (declared_size)
445 return alloc_int_rl(declared_size);
447 size = get_stored_size_end_struct_bytes(expr);
448 if (size)
449 return alloc_int_rl(size);
451 /* char *foo = "BAR" */
452 size = get_size_from_initializer(expr);
453 if (size)
454 return alloc_int_rl(elements_to_bytes(expr, size));
456 size = get_bytes_from_address(expr);
457 if (size)
458 return alloc_int_rl(size);
460 /* if (strlen(foo) > 4) */
461 size = get_size_from_strlen(expr);
462 if (size)
463 return alloc_int_rl(size);
465 ret = size_from_db(expr);
466 if (ret)
467 return ret;
469 return NULL;
472 int get_array_size_bytes(struct expression *expr)
474 struct range_list *rl;
475 sval_t sval;
477 rl = get_array_size_bytes_rl(expr);
478 if (!rl_to_sval(rl, &sval))
479 return 0;
480 if (sval.uvalue >= INT_MAX)
481 return 0;
482 return sval.value;
485 int get_array_size_bytes_max(struct expression *expr)
487 struct range_list *rl;
488 sval_t bytes;
490 rl = get_array_size_bytes_rl(expr);
491 if (!rl)
492 return 0;
493 bytes = rl_min(rl);
494 if (bytes.value < 0)
495 return 0;
496 bytes = rl_max(rl);
497 if (bytes.uvalue >= INT_MAX)
498 return 0;
499 return bytes.value;
502 int get_array_size_bytes_min(struct expression *expr)
504 struct range_list *rl;
505 struct data_range *range;
507 rl = get_array_size_bytes_rl(expr);
508 if (!rl)
509 return 0;
511 FOR_EACH_PTR(rl, range) {
512 if (range->min.value <= 0)
513 return 0;
514 if (range->max.value <= 0)
515 return 0;
516 if (range->min.uvalue >= INT_MAX)
517 return 0;
518 return range->min.value;
519 } END_FOR_EACH_PTR(range);
521 return 0;
524 int get_array_size(struct expression *expr)
526 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
529 static void match_strlen_condition(struct expression *expr)
531 struct expression *left;
532 struct expression *right;
533 struct expression *str = NULL;
534 int strlen_left = 0;
535 int strlen_right = 0;
536 sval_t sval;
537 struct smatch_state *true_state = NULL;
538 struct smatch_state *false_state = NULL;
540 if (expr->type != EXPR_COMPARE)
541 return;
542 left = strip_expr(expr->left);
543 right = strip_expr(expr->right);
545 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
546 str = get_argument_from_call_expr(left->args, 0);
547 strlen_left = 1;
549 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
550 str = get_argument_from_call_expr(right->args, 0);
551 strlen_right = 1;
554 if (!strlen_left && !strlen_right)
555 return;
556 if (strlen_left && strlen_right)
557 return;
559 if (strlen_left) {
560 if (!get_value(right, &sval))
561 return;
563 if (strlen_right) {
564 if (!get_value(left, &sval))
565 return;
568 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
570 if (expr->op == SPECIAL_EQUAL) {
571 set_true_false_states_expr(my_size_id, str, size_to_estate(sval.value + 1), NULL);
572 return;
574 if (expr->op == SPECIAL_NOTEQUAL) {
575 set_true_false_states_expr(my_size_id, str, NULL, size_to_estate(sval.value + 1));
576 return;
579 switch (expr->op) {
580 case '<':
581 case SPECIAL_UNSIGNED_LT:
582 if (strlen_left)
583 true_state = size_to_estate(sval.value);
584 else
585 false_state = size_to_estate(sval.value + 1);
586 break;
587 case SPECIAL_LTE:
588 case SPECIAL_UNSIGNED_LTE:
589 if (strlen_left)
590 true_state = size_to_estate(sval.value + 1);
591 else
592 false_state = size_to_estate(sval.value);
593 break;
594 case SPECIAL_GTE:
595 case SPECIAL_UNSIGNED_GTE:
596 if (strlen_left)
597 false_state = size_to_estate(sval.value);
598 else
599 true_state = size_to_estate(sval.value + 1);
600 break;
601 case '>':
602 case SPECIAL_UNSIGNED_GT:
603 if (strlen_left)
604 false_state = size_to_estate(sval.value + 1);
605 else
606 true_state = size_to_estate(sval.value);
607 break;
609 set_true_false_states_expr(my_size_id, str, true_state, false_state);
612 static struct expression *strip_ampersands(struct expression *expr)
614 struct symbol *type;
616 if (expr->type != EXPR_PREOP)
617 return expr;
618 if (expr->op != '&')
619 return expr;
620 type = get_type(expr->unop);
621 if (!type || type->type != SYM_ARRAY)
622 return expr;
623 return expr->unop;
626 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
628 char *name;
630 if (!option_info)
631 return;
633 name = get_member_name(buffer);
634 if (!name && is_static(buffer))
635 name = expr_to_var(buffer);
636 if (!name)
637 return;
638 if (rl && !is_whole_rl(rl))
639 sql_insert_function_type_size(name, show_rl(rl));
640 else
641 sql_insert_function_type_size(name, "(-1)");
643 free_string(name);
646 static void store_alloc(struct expression *expr, struct range_list *rl)
648 rl = clone_rl(rl); // FIXME!!!
649 info_record_alloction(expr, rl);
650 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
653 static void match_array_assignment(struct expression *expr)
655 struct expression *left;
656 struct expression *right;
657 struct range_list *rl;
658 sval_t sval;
660 if (expr->op != '=')
661 return;
662 left = strip_expr(expr->left);
663 right = strip_expr(expr->right);
664 right = strip_ampersands(right);
666 if (is_allocation_function(right))
667 return;
669 if (get_implied_value(right, &sval) && sval.value == 0) {
670 rl = alloc_int_rl(0);
671 goto store;
674 rl = get_array_size_bytes_rl(right);
676 store:
677 store_alloc(left, rl);
680 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
682 int size_arg = PTR_INT(_size_arg);
683 struct expression *right;
684 struct expression *arg;
685 struct range_list *rl;
687 right = strip_expr(expr->right);
688 arg = get_argument_from_call_expr(right->args, size_arg);
689 get_absolute_rl(arg, &rl);
690 rl = cast_rl(&int_ctype, rl);
691 store_alloc(expr->left, rl);
694 static void match_calloc(const char *fn, struct expression *expr, void *unused)
696 struct expression *right;
697 struct expression *arg;
698 sval_t elements;
699 sval_t size;
701 right = strip_expr(expr->right);
702 arg = get_argument_from_call_expr(right->args, 0);
703 if (!get_implied_value(arg, &elements))
704 return; // FIXME!!!
705 arg = get_argument_from_call_expr(right->args, 1);
706 if (get_implied_value(arg, &size))
707 store_alloc(expr->left, size_to_rl(elements.value * size.value));
708 else
709 store_alloc(expr->left, size_to_rl(-1));
712 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
714 struct limiter *limiter = (struct limiter *)_limiter;
715 struct expression *dest;
716 struct expression *size_expr;
717 sval_t size;
719 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
720 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
721 if (!get_implied_max(size_expr, &size))
722 return;
723 set_state_expr(my_size_id, dest, size_to_estate(size.value));
726 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
728 struct expression fake_assign;
730 fake_assign.op = '=';
731 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
732 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
733 match_array_assignment(&fake_assign);
736 static void match_strndup(const char *fn, struct expression *expr, void *unused)
738 struct expression *fn_expr;
739 struct expression *size_expr;
740 sval_t size;
742 fn_expr = strip_expr(expr->right);
743 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
744 if (get_implied_max(size_expr, &size)) {
745 size.value++;
746 store_alloc(expr->left, size_to_rl(size.value));
747 } else {
748 store_alloc(expr->left, size_to_rl(-1));
753 static void match_call(struct expression *expr)
755 struct expression *arg;
756 struct range_list *rl;
757 int i;
759 i = 0;
760 FOR_EACH_PTR(expr->args, arg) {
761 rl = get_array_size_bytes_rl(arg);
762 if (rl && !is_whole_rl(rl))
763 sql_insert_caller_info(expr, BUF_SIZE, i, "$$", show_rl(rl));
764 i++;
765 } END_FOR_EACH_PTR(arg);
768 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
770 if (state == &merged)
771 return;
772 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, state->name);
775 void register_buf_size(int id)
777 my_size_id = id;
779 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
781 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
782 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
784 allocation_funcs = create_function_hashtable(100);
785 add_allocation_function("malloc", &match_alloc, 0);
786 add_allocation_function("calloc", &match_calloc, 0);
787 add_allocation_function("memdup", &match_alloc, 1);
788 if (option_project == PROJ_KERNEL) {
789 add_allocation_function("kmalloc", &match_alloc, 0);
790 add_allocation_function("kzalloc", &match_alloc, 0);
791 add_allocation_function("vmalloc", &match_alloc, 0);
792 add_allocation_function("__vmalloc", &match_alloc, 0);
793 add_allocation_function("kcalloc", &match_calloc, 0);
794 add_allocation_function("kmalloc_array", &match_calloc, 0);
795 add_allocation_function("drm_malloc_ab", &match_calloc, 0);
796 add_allocation_function("drm_calloc_large", &match_calloc, 0);
797 add_allocation_function("sock_kmalloc", &match_alloc, 1);
798 add_allocation_function("kmemdup", &match_alloc, 1);
799 add_allocation_function("kmemdup_user", &match_alloc, 1);
800 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
801 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
802 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
803 add_allocation_function("devm_kmalloc", &match_alloc, 1);
804 add_allocation_function("devm_kzalloc", &match_alloc, 1);
806 add_hook(&match_strlen_condition, CONDITION_HOOK);
808 add_allocation_function("strndup", match_strndup, 0);
809 if (option_project == PROJ_KERNEL)
810 add_allocation_function("kstrndup", match_strndup, 0);
812 add_modification_hook(my_size_id, &set_size_undefined);
814 add_merge_hook(my_size_id, &merge_size_func);
817 void register_buf_size_late(int id)
819 /* has to happen after match_alloc() */
820 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
822 add_function_hook("strlcpy", &match_limited, &b0_l2);
823 add_function_hook("strlcat", &match_limited, &b0_l2);
824 add_function_hook("memscan", &match_limited, &b0_l2);
826 add_function_hook("strcpy", &match_strcpy, NULL);
828 add_hook(&match_call, FUNCTION_CALL_HOOK);
829 add_member_info_callback(my_size_id, struct_member_callback);