extra: assume indexes are in bounds
[smatch.git] / smatch_buf_size.c
blob3987fbc3622b3f7616f5858eb37cb58dd8881f72
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"
16 #include "smatch_function_hashtable.h"
18 #define UNKNOWN_SIZE (-1)
20 static int my_size_id;
22 struct limiter {
23 int buf_arg;
24 int limit_arg;
26 static struct limiter b0_l2 = {0, 2};
28 static DEFINE_HASHTABLE_INSERT(insert_func, char, int);
29 static DEFINE_HASHTABLE_SEARCH(search_func, char, int);
30 static struct hashtable *allocation_funcs;
32 static char *get_fn_name(struct expression *expr)
34 if (expr->type != EXPR_CALL)
35 return NULL;
36 if (expr->fn->type != EXPR_SYMBOL)
37 return NULL;
38 return expr_to_var(expr->fn);
41 static int is_allocation_function(struct expression *expr)
43 char *func;
44 int ret = 0;
46 func = get_fn_name(expr);
47 if (!func)
48 return 0;
49 if (search_func(allocation_funcs, func))
50 ret = 1;
51 free_string(func);
52 return ret;
55 static void add_allocation_function(const char *func, void *call_back, int param)
57 insert_func(allocation_funcs, (char *)func, (int *)1);
58 add_function_assign_hook(func, call_back, INT_PTR(param));
61 static int estate_to_size(struct smatch_state *state)
63 sval_t sval;
65 if (!state || !estate_rl(state))
66 return 0;
67 sval = estate_max(state);
68 return sval.value;
71 static struct smatch_state *size_to_estate(int size)
73 sval_t sval;
75 sval.type = &int_ctype;
76 sval.value = size;
78 return alloc_estate_sval(sval);
81 static struct range_list *size_to_rl(int size)
83 sval_t sval;
85 sval.type = &int_ctype;
86 sval.value = size;
88 return alloc_rl(sval, sval);
91 static struct smatch_state *unmatched_size_state(struct sm_state *sm)
93 return size_to_estate(UNKNOWN_SIZE);
96 static void set_size_undefined(struct sm_state *sm, struct expression *mod_expr)
98 set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
101 static struct smatch_state *merge_size_func(struct smatch_state *s1, struct smatch_state *s2)
103 return merge_estates(s1, s2);
106 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
108 struct range_list *rl = NULL;
109 struct smatch_state *state;
110 char fullname[256];
112 if (strncmp(key, "$$", 2) != 0)
113 return;
115 snprintf(fullname, 256, "%s%s", name, key + 2);
117 str_to_rl(&int_ctype, value, &rl);
118 if (!rl || is_whole_rl(rl))
119 return;
120 state = alloc_estate_rl(rl);
121 set_state(my_size_id, fullname, sym, state);
124 static int bytes_per_element(struct expression *expr)
126 struct symbol *type;
127 int bpe;
129 if (expr->type == EXPR_STRING)
130 return 1;
131 type = get_type(expr);
132 if (!type)
133 return 0;
135 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
136 return 0;
138 type = get_base_type(type);
139 bpe = bits_to_bytes(type->bit_size);
141 if (bpe == -1) /* void pointer */
142 bpe = 1;
144 return bpe;
147 static int bytes_to_elements(struct expression *expr, int bytes)
149 int bpe;
151 bpe = bytes_per_element(expr);
152 if (bpe == 0)
153 return 0;
154 return bytes / bpe;
157 static int elements_to_bytes(struct expression *expr, int elements)
159 int bpe;
161 bpe = bytes_per_element(expr);
162 return elements * bpe;
165 static int get_initializer_size(struct expression *expr)
167 switch (expr->type) {
168 case EXPR_STRING:
169 return expr->string->length;
170 case EXPR_INITIALIZER: {
171 struct expression *tmp;
172 int i = 0;
174 FOR_EACH_PTR(expr->expr_list, tmp) {
175 if (tmp->type == EXPR_INDEX) {
176 if (tmp->idx_to >= i)
177 i = tmp->idx_to;
178 else
179 continue;
182 i++;
183 } END_FOR_EACH_PTR(tmp);
184 return i;
186 case EXPR_SYMBOL:
187 return get_array_size(expr);
189 return 0;
192 static struct range_list *db_size_rl;
193 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
195 struct range_list *tmp = NULL;
197 if (!db_size_rl) {
198 str_to_rl(&int_ctype, argv[0], &db_size_rl);
199 } else {
200 str_to_rl(&int_ctype, argv[0], &tmp);
201 db_size_rl = rl_union(db_size_rl, tmp);
203 return 0;
206 static struct range_list *size_from_db(struct expression *expr)
208 int this_file_only = 0;
209 char *name;
211 name = get_member_name(expr);
212 if (!name && is_static(expr)) {
213 name = expr_to_var(expr);
214 this_file_only = 1;
216 if (!name)
217 return 0;
219 if (this_file_only) {
220 db_size_rl = NULL;
221 run_sql(db_size_callback, "select size from function_type_size where type = '%s' and file = '%s'",
222 name, get_filename());
223 if (db_size_rl)
224 return db_size_rl;
225 return 0;
228 db_size_rl = NULL;
229 run_sql(db_size_callback, "select size from type_size where type = '%s'",
230 name);
231 return db_size_rl;
234 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
236 struct expression *call;
237 sval_t sval;
239 if (expr->type != EXPR_ASSIGNMENT)
240 return;
241 call = strip_expr(expr->right);
243 if (!parse_call_math(call, math, &sval))
244 return;
245 set_state_expr(my_size_id, expr->left, size_to_estate(sval.value));
248 int get_real_array_size(struct expression *expr)
250 struct symbol *type;
251 sval_t sval;
253 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
254 return 0;
256 type = get_type(expr);
257 if (!type || type->type != SYM_ARRAY)
258 return 0;
260 if (!get_implied_value(type->array_size, &sval))
261 return 0;
263 /* People put one element arrays on the end of structs */
264 if (sval.value == 1)
265 return 0;
267 return sval.value;
270 static int get_size_from_initializer(struct expression *expr)
272 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
273 return 0;
274 if (expr->symbol->initializer == expr) /* int a = a; */
275 return 0;
276 return get_initializer_size(expr->symbol->initializer);
279 static struct range_list *get_stored_size_bytes(struct expression *expr)
281 struct smatch_state *state;
283 state = get_state_expr(my_size_id, expr);
284 if (!state)
285 return NULL;
286 return estate_rl(state);
289 static int get_bytes_from_address(struct expression *expr)
291 struct symbol *type;
292 int ret;
294 if (!option_spammy)
295 return 0;
296 if (expr->type != EXPR_PREOP || expr->op != '&')
297 return 0;
298 type = get_type(expr);
299 if (!type)
300 return 0;
302 if (type->type == SYM_PTR)
303 type = get_base_type(type);
305 ret = bits_to_bytes(type->bit_size);
306 if (ret == -1)
307 return 0;
308 if (ret == 1)
309 return 0; /* ignore char pointers */
311 return ret;
314 static struct expression *remove_addr_fluff(struct expression *expr)
316 struct expression *tmp;
317 sval_t sval;
319 expr = strip_expr(expr);
321 /* remove '&' and '*' operations that cancel */
322 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
323 tmp = strip_expr(expr->unop);
324 if (tmp->type != EXPR_PREOP)
325 break;
326 if (tmp->op != '*')
327 break;
328 expr = strip_expr(tmp->unop);
331 if (!expr)
332 return NULL;
334 /* "foo + 0" is just "foo" */
335 if (expr->type == EXPR_BINOP && expr->op == '+' &&
336 get_value(expr->right, &sval) && sval.value == 0)
337 return expr->left;
339 return expr;
342 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
344 struct symbol *tmp;
345 int i;
347 i = 0;
348 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
349 if (i++ || !tmp->ident)
350 return 0;
351 if (tmp->ident == member)
352 return 1;
353 return 0;
354 } END_FOR_EACH_PTR_REVERSE(tmp);
356 return 0;
359 static int get_stored_size_end_struct_bytes(struct expression *expr)
361 struct symbol *type;
362 char *name;
363 struct symbol *sym;
364 struct smatch_state *state;
365 sval_t sval;
367 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
368 return 0;
370 type = get_type(expr);
371 if (!type || type->type != SYM_ARRAY)
372 return 0;
374 if (!get_implied_value(type->array_size, &sval))
375 return 0;
377 if (sval.value != 0 && sval.value != 1)
378 return 0;
380 name = expr_to_var_sym(expr, &sym);
381 free_string(name);
382 if (!sym || !sym->ident || !sym->ident->name)
383 return 0;
384 if (!sym->bit_size)
385 return 0;
387 if (sym->type != SYM_NODE)
388 return 0;
390 state = get_state(my_size_id, sym->ident->name, sym);
391 if (!estate_to_size(state))
392 return 0;
394 sym = get_real_base_type(sym);
395 if (!sym || sym->type != SYM_PTR)
396 return 0;
397 sym = get_real_base_type(sym);
398 if (!sym || sym->type != SYM_STRUCT)
399 return 0;
400 if (!is_last_member_of_struct(sym, expr->member))
401 return 0;
403 return estate_to_size(state) - bits_to_bytes(sym->bit_size) +
404 bits_to_bytes(type->bit_size);
407 static struct range_list *alloc_int_rl(int value)
409 sval_t sval = {
410 .type = &int_ctype,
411 .value = value,
414 return alloc_rl(sval, sval);
417 struct range_list *get_array_size_bytes_rl(struct expression *expr)
419 int declared_size = 0;
420 struct range_list *ret = NULL;
421 int size;
423 expr = remove_addr_fluff(expr);
424 if (!expr)
425 return NULL;
427 /* "BAR" */
428 if (expr->type == EXPR_STRING)
429 return alloc_int_rl(expr->string->length);
431 /* buf[4] */
432 size = get_real_array_size(expr);
433 if (size)
434 declared_size = elements_to_bytes(expr, size);
436 /* buf = malloc(1024); */
437 ret = get_stored_size_bytes(expr);
438 if (ret) {
439 if (declared_size)
440 return rl_union(ret, alloc_int_rl(size));
441 return ret;
443 if (declared_size)
444 return alloc_int_rl(declared_size);
446 size = get_stored_size_end_struct_bytes(expr);
447 if (size)
448 return alloc_int_rl(size);
450 /* char *foo = "BAR" */
451 size = get_size_from_initializer(expr);
452 if (size)
453 return alloc_int_rl(elements_to_bytes(expr, size));
455 size = get_bytes_from_address(expr);
456 if (size)
457 return alloc_int_rl(size);
459 /* if (strlen(foo) > 4) */
460 size = get_size_from_strlen(expr);
461 if (size)
462 return alloc_int_rl(size);
464 ret = size_from_db(expr);
465 if (ret)
466 return ret;
468 return NULL;
471 int get_array_size_bytes(struct expression *expr)
473 struct range_list *rl;
474 sval_t sval;
476 rl = get_array_size_bytes_rl(expr);
477 if (!rl_to_sval(rl, &sval))
478 return 0;
479 if (sval.uvalue >= INT_MAX)
480 return 0;
481 return sval.value;
484 int get_array_size_bytes_max(struct expression *expr)
486 struct range_list *rl;
487 sval_t bytes;
489 rl = get_array_size_bytes_rl(expr);
490 if (!rl)
491 return 0;
492 bytes = rl_min(rl);
493 if (bytes.value < 0)
494 return 0;
495 bytes = rl_max(rl);
496 if (bytes.uvalue >= INT_MAX)
497 return 0;
498 return bytes.value;
501 int get_array_size_bytes_min(struct expression *expr)
503 struct range_list *rl;
504 struct data_range *range;
506 rl = get_array_size_bytes_rl(expr);
507 if (!rl)
508 return 0;
510 FOR_EACH_PTR(rl, range) {
511 if (range->min.value <= 0)
512 return 0;
513 if (range->max.value <= 0)
514 return 0;
515 if (range->min.uvalue >= INT_MAX)
516 return 0;
517 return range->min.value;
518 } END_FOR_EACH_PTR(range);
520 return 0;
523 int get_array_size(struct expression *expr)
525 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
528 static void match_strlen_condition(struct expression *expr)
530 struct expression *left;
531 struct expression *right;
532 struct expression *str = NULL;
533 int strlen_left = 0;
534 int strlen_right = 0;
535 sval_t sval;
536 struct smatch_state *true_state = NULL;
537 struct smatch_state *false_state = NULL;
539 if (expr->type != EXPR_COMPARE)
540 return;
541 left = strip_expr(expr->left);
542 right = strip_expr(expr->right);
544 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
545 str = get_argument_from_call_expr(left->args, 0);
546 strlen_left = 1;
548 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
549 str = get_argument_from_call_expr(right->args, 0);
550 strlen_right = 1;
553 if (!strlen_left && !strlen_right)
554 return;
555 if (strlen_left && strlen_right)
556 return;
558 if (strlen_left) {
559 if (!get_value(right, &sval))
560 return;
562 if (strlen_right) {
563 if (!get_value(left, &sval))
564 return;
567 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
569 if (expr->op == SPECIAL_EQUAL) {
570 set_true_false_states_expr(my_size_id, str, size_to_estate(sval.value + 1), NULL);
571 return;
573 if (expr->op == SPECIAL_NOTEQUAL) {
574 set_true_false_states_expr(my_size_id, str, NULL, size_to_estate(sval.value + 1));
575 return;
578 switch (expr->op) {
579 case '<':
580 case SPECIAL_UNSIGNED_LT:
581 if (strlen_left)
582 true_state = size_to_estate(sval.value);
583 else
584 false_state = size_to_estate(sval.value + 1);
585 break;
586 case SPECIAL_LTE:
587 case SPECIAL_UNSIGNED_LTE:
588 if (strlen_left)
589 true_state = size_to_estate(sval.value + 1);
590 else
591 false_state = size_to_estate(sval.value);
592 break;
593 case SPECIAL_GTE:
594 case SPECIAL_UNSIGNED_GTE:
595 if (strlen_left)
596 false_state = size_to_estate(sval.value);
597 else
598 true_state = size_to_estate(sval.value + 1);
599 break;
600 case '>':
601 case SPECIAL_UNSIGNED_GT:
602 if (strlen_left)
603 false_state = size_to_estate(sval.value + 1);
604 else
605 true_state = size_to_estate(sval.value);
606 break;
608 set_true_false_states_expr(my_size_id, str, true_state, false_state);
611 static struct expression *strip_ampersands(struct expression *expr)
613 struct symbol *type;
615 if (expr->type != EXPR_PREOP)
616 return expr;
617 if (expr->op != '&')
618 return expr;
619 type = get_type(expr->unop);
620 if (!type || type->type != SYM_ARRAY)
621 return expr;
622 return expr->unop;
625 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
627 char *name;
629 if (!option_info)
630 return;
632 name = get_member_name(buffer);
633 if (!name && is_static(buffer))
634 name = expr_to_var(buffer);
635 if (!name)
636 return;
637 if (rl && !is_whole_rl(rl))
638 sql_insert_function_type_size(name, show_rl(rl));
639 else
640 sql_insert_function_type_size(name, "(-1)");
642 free_string(name);
645 static void store_alloc(struct expression *expr, struct range_list *rl)
647 rl = clone_rl(rl); // FIXME!!!
648 info_record_alloction(expr, rl);
649 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
652 static void match_array_assignment(struct expression *expr)
654 struct expression *left;
655 struct expression *right;
656 struct range_list *rl;
657 sval_t sval;
659 if (expr->op != '=')
660 return;
661 left = strip_expr(expr->left);
662 right = strip_expr(expr->right);
663 right = strip_ampersands(right);
665 if (is_allocation_function(right))
666 return;
668 if (get_implied_value(right, &sval) && sval.value == 0) {
669 rl = alloc_int_rl(0);
670 goto store;
673 rl = get_array_size_bytes_rl(right);
675 store:
676 store_alloc(left, rl);
679 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
681 int size_arg = PTR_INT(_size_arg);
682 struct expression *right;
683 struct expression *arg;
684 struct range_list *rl;
686 right = strip_expr(expr->right);
687 arg = get_argument_from_call_expr(right->args, size_arg);
688 get_absolute_rl(arg, &rl);
689 rl = cast_rl(&int_ctype, rl);
690 store_alloc(expr->left, rl);
693 static void match_calloc(const char *fn, struct expression *expr, void *unused)
695 struct expression *right;
696 struct expression *arg;
697 sval_t elements;
698 sval_t size;
700 right = strip_expr(expr->right);
701 arg = get_argument_from_call_expr(right->args, 0);
702 if (!get_implied_value(arg, &elements))
703 return; // FIXME!!!
704 arg = get_argument_from_call_expr(right->args, 1);
705 if (get_implied_value(arg, &size))
706 store_alloc(expr->left, size_to_rl(elements.value * size.value));
707 else
708 store_alloc(expr->left, size_to_rl(-1));
711 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
713 struct limiter *limiter = (struct limiter *)_limiter;
714 struct expression *dest;
715 struct expression *size_expr;
716 sval_t size;
718 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
719 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
720 if (!get_implied_max(size_expr, &size))
721 return;
722 set_state_expr(my_size_id, dest, size_to_estate(size.value));
725 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
727 struct expression fake_assign;
729 fake_assign.op = '=';
730 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
731 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
732 match_array_assignment(&fake_assign);
735 static void match_strndup(const char *fn, struct expression *expr, void *unused)
737 struct expression *fn_expr;
738 struct expression *size_expr;
739 sval_t size;
741 fn_expr = strip_expr(expr->right);
742 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
743 if (get_implied_max(size_expr, &size)) {
744 size.value++;
745 store_alloc(expr->left, size_to_rl(size.value));
746 } else {
747 store_alloc(expr->left, size_to_rl(-1));
752 static void match_call(struct expression *expr)
754 struct expression *arg;
755 struct range_list *rl;
756 int i;
758 i = 0;
759 FOR_EACH_PTR(expr->args, arg) {
760 rl = get_array_size_bytes_rl(arg);
761 if (rl && !is_whole_rl(rl))
762 sql_insert_caller_info(expr, BUF_SIZE, i, "$$", show_rl(rl));
763 i++;
764 } END_FOR_EACH_PTR(arg);
767 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
769 if (state == &merged)
770 return;
771 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, state->name);
774 void register_buf_size(int id)
776 my_size_id = id;
778 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
780 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
781 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
783 allocation_funcs = create_function_hashtable(100);
784 add_allocation_function("malloc", &match_alloc, 0);
785 add_allocation_function("calloc", &match_calloc, 0);
786 add_allocation_function("memdup", &match_alloc, 1);
787 if (option_project == PROJ_KERNEL) {
788 add_allocation_function("kmalloc", &match_alloc, 0);
789 add_allocation_function("kzalloc", &match_alloc, 0);
790 add_allocation_function("vmalloc", &match_alloc, 0);
791 add_allocation_function("__vmalloc", &match_alloc, 0);
792 add_allocation_function("kcalloc", &match_calloc, 0);
793 add_allocation_function("kmalloc_array", &match_calloc, 0);
794 add_allocation_function("drm_malloc_ab", &match_calloc, 0);
795 add_allocation_function("drm_calloc_large", &match_calloc, 0);
796 add_allocation_function("sock_kmalloc", &match_alloc, 1);
797 add_allocation_function("kmemdup", &match_alloc, 1);
798 add_allocation_function("kmemdup_user", &match_alloc, 1);
799 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
800 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
801 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
802 add_allocation_function("devm_kmalloc", &match_alloc, 1);
803 add_allocation_function("devm_kzalloc", &match_alloc, 1);
805 add_hook(&match_strlen_condition, CONDITION_HOOK);
807 add_allocation_function("strndup", match_strndup, 0);
808 if (option_project == PROJ_KERNEL)
809 add_allocation_function("kstrndup", match_strndup, 0);
811 add_modification_hook(my_size_id, &set_size_undefined);
813 add_merge_hook(my_size_id, &merge_size_func);
816 void register_buf_size_late(int id)
818 /* has to happen after match_alloc() */
819 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
821 add_function_hook("strlcpy", &match_limited, &b0_l2);
822 add_function_hook("strlcat", &match_limited, &b0_l2);
823 add_function_hook("memscan", &match_limited, &b0_l2);
825 add_function_hook("strcpy", &match_strcpy, NULL);
827 add_hook(&match_call, FUNCTION_CALL_HOOK);
828 add_member_info_callback(my_size_id, struct_member_callback);