debug: introduce __smatch_buf_size_rl() which is more verbose
[smatch.git] / smatch_buf_size.c
blob84651a12208217e4eb9d665c3df96edca6924cb7
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"
17 #define UNKNOWN_SIZE (-1)
19 static int my_size_id;
21 struct limiter {
22 int buf_arg;
23 int limit_arg;
25 static struct limiter b0_l2 = {0, 2};
27 static int estate_to_size(struct smatch_state *state)
29 sval_t sval;
31 if (!state || !estate_rl(state))
32 return 0;
33 sval = estate_max(state);
34 return sval.value;
37 static struct smatch_state *size_to_estate(int size)
39 sval_t sval;
41 sval.type = &int_ctype;
42 sval.value = size;
44 return alloc_estate_sval(sval);
47 static struct smatch_state *unmatched_size_state(struct sm_state *sm)
49 return size_to_estate(UNKNOWN_SIZE);
52 static void set_size_undefined(struct sm_state *sm, struct expression *mod_expr)
54 set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
57 static struct smatch_state *merge_size_func(struct smatch_state *s1, struct smatch_state *s2)
59 return merge_estates(s1, s2);
62 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
64 struct range_list *rl = NULL;
65 struct smatch_state *state;
66 char fullname[256];
68 if (strncmp(key, "$$", 2) != 0)
69 return;
71 snprintf(fullname, 256, "%s%s", name, key + 2);
73 str_to_rl(&int_ctype, value, &rl);
74 if (!rl || is_whole_rl(rl))
75 return;
76 state = alloc_estate_rl(rl);
77 set_state(my_size_id, fullname, sym, state);
80 static int bytes_per_element(struct expression *expr)
82 struct symbol *type;
83 int bpe;
85 if (expr->type == EXPR_STRING)
86 return 1;
87 type = get_type(expr);
88 if (!type)
89 return 0;
91 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
92 return 0;
94 type = get_base_type(type);
95 bpe = bits_to_bytes(type->bit_size);
97 if (bpe == -1) /* void pointer */
98 bpe = 1;
100 return bpe;
103 static int bytes_to_elements(struct expression *expr, int bytes)
105 int bpe;
107 bpe = bytes_per_element(expr);
108 if (bpe == 0)
109 return 0;
110 return bytes / bpe;
113 static int elements_to_bytes(struct expression *expr, int elements)
115 int bpe;
117 bpe = bytes_per_element(expr);
118 return elements * bpe;
121 static int get_initializer_size(struct expression *expr)
123 switch (expr->type) {
124 case EXPR_STRING:
125 return expr->string->length;
126 case EXPR_INITIALIZER: {
127 struct expression *tmp;
128 int i = 0;
130 FOR_EACH_PTR(expr->expr_list, tmp) {
131 if (tmp->type == EXPR_INDEX) {
132 if (tmp->idx_to >= i)
133 i = tmp->idx_to;
134 else
135 continue;
138 i++;
139 } END_FOR_EACH_PTR(tmp);
140 return i;
142 case EXPR_SYMBOL:
143 return get_array_size(expr);
145 return 0;
148 static struct range_list *db_size_rl;
149 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
151 struct range_list *tmp = NULL;
153 if (!db_size_rl) {
154 str_to_rl(&int_ctype, argv[0], &db_size_rl);
155 } else {
156 str_to_rl(&int_ctype, argv[0], &tmp);
157 db_size_rl = rl_union(db_size_rl, tmp);
159 return 0;
162 static struct range_list *size_from_db(struct expression *expr)
164 int this_file_only = 0;
165 char *name;
167 name = get_member_name(expr);
168 if (!name && is_static(expr)) {
169 name = expr_to_var(expr);
170 this_file_only = 1;
172 if (!name)
173 return 0;
175 if (this_file_only) {
176 db_size_rl = NULL;
177 run_sql(db_size_callback, "select size from function_type_size where type = '%s' and file = '%s'",
178 name, get_filename());
179 if (db_size_rl)
180 return db_size_rl;
181 return 0;
184 db_size_rl = NULL;
185 run_sql(db_size_callback, "select size from type_size where type = '%s'",
186 name);
187 return db_size_rl;
190 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
192 struct expression *call;
193 sval_t sval;
195 if (expr->type != EXPR_ASSIGNMENT)
196 return;
197 call = strip_expr(expr->right);
199 if (!parse_call_math(call, math, &sval))
200 return;
201 set_state_expr(my_size_id, expr->left, size_to_estate(sval.value));
204 int get_real_array_size(struct expression *expr)
206 struct symbol *type;
207 sval_t sval;
209 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
210 return 0;
212 type = get_type(expr);
213 if (!type || type->type != SYM_ARRAY)
214 return 0;
216 if (!get_implied_value(type->array_size, &sval))
217 return 0;
219 /* People put one element arrays on the end of structs */
220 if (sval.value == 1)
221 return 0;
223 return sval.value;
226 static int get_size_from_initializer(struct expression *expr)
228 if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
229 return 0;
230 if (expr->symbol->initializer == expr) /* int a = a; */
231 return 0;
232 return get_initializer_size(expr->symbol->initializer);
235 static struct range_list *get_stored_size_bytes(struct expression *expr)
237 struct smatch_state *state;
239 state = get_state_expr(my_size_id, expr);
240 if (!state)
241 return NULL;
242 return estate_rl(state);
245 static int get_bytes_from_address(struct expression *expr)
247 struct symbol *type;
248 int ret;
250 if (!option_spammy)
251 return 0;
252 if (expr->type != EXPR_PREOP || expr->op != '&')
253 return 0;
254 type = get_type(expr);
255 if (!type)
256 return 0;
258 if (type->type == SYM_PTR)
259 type = get_base_type(type);
261 ret = bits_to_bytes(type->bit_size);
262 if (ret == -1)
263 return 0;
264 if (ret == 1)
265 return 0; /* ignore char pointers */
267 return ret;
270 static struct expression *remove_addr_fluff(struct expression *expr)
272 struct expression *tmp;
273 sval_t sval;
275 expr = strip_expr(expr);
277 /* remove '&' and '*' operations that cancel */
278 while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
279 tmp = strip_expr(expr->unop);
280 if (tmp->type != EXPR_PREOP)
281 break;
282 if (tmp->op != '*')
283 break;
284 expr = strip_expr(tmp->unop);
287 if (!expr)
288 return NULL;
290 /* "foo + 0" is just "foo" */
291 if (expr->type == EXPR_BINOP && expr->op == '+' &&
292 get_value(expr->right, &sval) && sval.value == 0)
293 return expr->left;
295 return expr;
298 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
300 struct symbol *tmp;
301 int i;
303 i = 0;
304 FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
305 if (i++ || !tmp->ident)
306 return 0;
307 if (tmp->ident == member)
308 return 1;
309 return 0;
310 } END_FOR_EACH_PTR_REVERSE(tmp);
312 return 0;
315 static int get_stored_size_end_struct_bytes(struct expression *expr)
317 struct symbol *type;
318 char *name;
319 struct symbol *sym;
320 struct smatch_state *state;
321 sval_t sval;
323 if (expr->type == EXPR_BINOP) /* array elements foo[5] */
324 return 0;
326 type = get_type(expr);
327 if (!type || type->type != SYM_ARRAY)
328 return 0;
330 if (!get_implied_value(type->array_size, &sval))
331 return 0;
333 if (sval.value != 0 && sval.value != 1)
334 return 0;
336 name = expr_to_var_sym(expr, &sym);
337 free_string(name);
338 if (!sym || !sym->ident || !sym->ident->name)
339 return 0;
340 if (!sym->bit_size)
341 return 0;
343 if (sym->type != SYM_NODE)
344 return 0;
346 state = get_state(my_size_id, sym->ident->name, sym);
347 if (!estate_to_size(state))
348 return 0;
350 sym = get_real_base_type(sym);
351 if (!sym || sym->type != SYM_PTR)
352 return 0;
353 sym = get_real_base_type(sym);
354 if (!sym || sym->type != SYM_STRUCT)
355 return 0;
356 if (!is_last_member_of_struct(sym, expr->member))
357 return 0;
359 return estate_to_size(state) - bits_to_bytes(sym->bit_size) +
360 bits_to_bytes(type->bit_size);
363 static struct range_list *alloc_int_rl(int value)
365 sval_t sval = {
366 .type = &int_ctype,
367 .value = value,
370 return alloc_rl(sval, sval);
373 struct range_list *get_array_size_bytes_rl(struct expression *expr)
375 int declared_size = 0;
376 struct range_list *ret = NULL;
377 int size;
379 expr = remove_addr_fluff(expr);
380 if (!expr)
381 return NULL;
383 /* "BAR" */
384 if (expr->type == EXPR_STRING)
385 return alloc_int_rl(expr->string->length);
387 /* buf[4] */
388 size = get_real_array_size(expr);
389 if (size)
390 declared_size = elements_to_bytes(expr, size);
392 /* buf = malloc(1024); */
393 ret = get_stored_size_bytes(expr);
394 if (ret) {
395 if (declared_size)
396 return rl_union(ret, alloc_int_rl(size));
397 return ret;
399 if (declared_size)
400 return alloc_int_rl(declared_size);
402 size = get_stored_size_end_struct_bytes(expr);
403 if (size)
404 return alloc_int_rl(size);
406 /* char *foo = "BAR" */
407 size = get_size_from_initializer(expr);
408 if (size)
409 return alloc_int_rl(elements_to_bytes(expr, size));
411 size = get_bytes_from_address(expr);
412 if (size)
413 return alloc_int_rl(size);
415 /* if (strlen(foo) > 4) */
416 size = get_size_from_strlen(expr);
417 if (size)
418 return alloc_int_rl(size);
420 ret = size_from_db(expr);
421 if (ret)
422 return ret;
423 return NULL;
426 int get_array_size_bytes(struct expression *expr)
428 struct range_list *rl;
429 sval_t sval;
431 rl = get_array_size_bytes_rl(expr);
432 if (!rl_to_sval(rl, &sval))
433 return 0;
434 if (sval.uvalue >= INT_MAX)
435 return 0;
436 return sval.value;
439 int get_array_size_bytes_max(struct expression *expr)
441 struct range_list *rl;
442 sval_t bytes;
444 rl = get_array_size_bytes_rl(expr);
445 if (!rl)
446 return 0;
447 bytes = rl_min(rl);
448 if (bytes.value < 0)
449 return 0;
450 bytes = rl_max(rl);
451 if (bytes.uvalue >= INT_MAX)
452 return 0;
453 return bytes.value;
456 int get_array_size_bytes_min(struct expression *expr)
458 struct range_list *rl;
459 struct data_range *range;
461 rl = get_array_size_bytes_rl(expr);
462 if (!rl)
463 return 0;
465 FOR_EACH_PTR(rl, range) {
466 if (range->min.value <= 0)
467 return 0;
468 if (range->max.value <= 0)
469 return 0;
470 if (range->min.uvalue >= INT_MAX)
471 return 0;
472 return range->min.value;
473 } END_FOR_EACH_PTR(range);
475 return 0;
478 int get_array_size(struct expression *expr)
480 return bytes_to_elements(expr, get_array_size_bytes_max(expr));
483 static void match_strlen_condition(struct expression *expr)
485 struct expression *left;
486 struct expression *right;
487 struct expression *str = NULL;
488 int strlen_left = 0;
489 int strlen_right = 0;
490 sval_t sval;
491 struct smatch_state *true_state = NULL;
492 struct smatch_state *false_state = NULL;
494 if (expr->type != EXPR_COMPARE)
495 return;
496 left = strip_expr(expr->left);
497 right = strip_expr(expr->right);
499 if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
500 str = get_argument_from_call_expr(left->args, 0);
501 strlen_left = 1;
503 if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
504 str = get_argument_from_call_expr(right->args, 0);
505 strlen_right = 1;
508 if (!strlen_left && !strlen_right)
509 return;
510 if (strlen_left && strlen_right)
511 return;
513 if (strlen_left) {
514 if (!get_value(right, &sval))
515 return;
517 if (strlen_right) {
518 if (!get_value(left, &sval))
519 return;
522 /* FIXME: why are we using my_size_id here instead of my_strlen_id */
524 if (expr->op == SPECIAL_EQUAL) {
525 set_true_false_states_expr(my_size_id, str, size_to_estate(sval.value + 1), NULL);
526 return;
528 if (expr->op == SPECIAL_NOTEQUAL) {
529 set_true_false_states_expr(my_size_id, str, NULL, size_to_estate(sval.value + 1));
530 return;
533 switch (expr->op) {
534 case '<':
535 case SPECIAL_UNSIGNED_LT:
536 if (strlen_left)
537 true_state = size_to_estate(sval.value);
538 else
539 false_state = size_to_estate(sval.value + 1);
540 break;
541 case SPECIAL_LTE:
542 case SPECIAL_UNSIGNED_LTE:
543 if (strlen_left)
544 true_state = size_to_estate(sval.value + 1);
545 else
546 false_state = size_to_estate(sval.value);
547 break;
548 case SPECIAL_GTE:
549 case SPECIAL_UNSIGNED_GTE:
550 if (strlen_left)
551 false_state = size_to_estate(sval.value);
552 else
553 true_state = size_to_estate(sval.value + 1);
554 break;
555 case '>':
556 case SPECIAL_UNSIGNED_GT:
557 if (strlen_left)
558 false_state = size_to_estate(sval.value + 1);
559 else
560 true_state = size_to_estate(sval.value);
561 break;
563 set_true_false_states_expr(my_size_id, str, true_state, false_state);
566 static struct expression *strip_ampersands(struct expression *expr)
568 struct symbol *type;
570 if (expr->type != EXPR_PREOP)
571 return expr;
572 if (expr->op != '&')
573 return expr;
574 type = get_type(expr->unop);
575 if (!type || type->type != SYM_ARRAY)
576 return expr;
577 return expr->unop;
580 static void match_array_assignment(struct expression *expr)
582 struct expression *left;
583 struct expression *right;
584 struct range_list *rl;
586 if (expr->op != '=')
587 return;
588 left = strip_expr(expr->left);
589 right = strip_expr(expr->right);
590 right = strip_ampersands(right);
591 rl = get_array_size_bytes_rl(right);
592 if (rl && !is_whole_rl(rl))
593 set_state_expr(my_size_id, left, alloc_estate_rl(clone_rl(rl)));
596 static void info_record_alloction(struct expression *buffer, struct expression *size)
598 char *name;
599 sval_t sval;
601 if (!option_info)
602 return;
604 name = get_member_name(buffer);
605 if (!name && is_static(buffer))
606 name = expr_to_var(buffer);
607 if (!name)
608 return;
609 if (get_implied_value(size, &sval))
610 sql_insert_function_type_size(name, sval.value);
611 else
612 sql_insert_function_type_size(name, -1);
614 free_string(name);
617 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
619 int size_arg = PTR_INT(_size_arg);
620 struct expression *right;
621 struct expression *arg;
622 struct range_list *rl;
624 right = strip_expr(expr->right);
625 arg = get_argument_from_call_expr(right->args, size_arg);
627 info_record_alloction(expr->left, arg);
629 if (!get_implied_rl(arg, &rl))
630 return;
631 set_state_expr(my_size_id, expr->left, alloc_estate_rl(rl));
634 static void match_calloc(const char *fn, struct expression *expr, void *unused)
636 struct expression *right;
637 struct expression *arg;
638 sval_t elements;
639 sval_t size;
641 right = strip_expr(expr->right);
642 arg = get_argument_from_call_expr(right->args, 0);
643 if (!get_implied_value(arg, &elements))
644 return;
645 arg = get_argument_from_call_expr(right->args, 1);
646 if (!get_implied_value(arg, &size))
647 return;
648 set_state_expr(my_size_id, expr->left, size_to_estate(elements.value * size.value));
651 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
653 struct limiter *limiter = (struct limiter *)_limiter;
654 struct expression *dest;
655 struct expression *size_expr;
656 sval_t size;
658 dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
659 size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
660 if (!get_implied_max(size_expr, &size))
661 return;
662 set_state_expr(my_size_id, dest, size_to_estate(size.value));
665 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
667 struct expression fake_assign;
669 fake_assign.op = '=';
670 fake_assign.left = get_argument_from_call_expr(expr->args, 0);
671 fake_assign.right = get_argument_from_call_expr(expr->args, 1);
672 match_array_assignment(&fake_assign);
675 static void match_strndup(const char *fn, struct expression *expr, void *unused)
677 struct expression *fn_expr;
678 struct expression *size_expr;
679 sval_t size;
681 fn_expr = strip_expr(expr->right);
682 size_expr = get_argument_from_call_expr(fn_expr->args, 1);
683 if (!get_implied_max(size_expr, &size))
684 return;
686 /* It's easy to forget space for the NUL char */
687 size.value++;
688 set_state_expr(my_size_id, expr->left, size_to_estate(size.value));
691 static void match_call(struct expression *expr)
693 struct expression *arg;
694 struct range_list *rl;
695 int i;
697 i = 0;
698 FOR_EACH_PTR(expr->args, arg) {
699 rl = get_array_size_bytes_rl(arg);
700 if (rl && !is_whole_rl(rl))
701 sql_insert_caller_info(expr, BUF_SIZE, i, "$$", show_rl(rl));
702 i++;
703 } END_FOR_EACH_PTR(arg);
706 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
708 if (state == &merged)
709 return;
710 sql_insert_caller_info(call, BUF_SIZE, param, printed_name, state->name);
713 void register_buf_size(int id)
715 my_size_id = id;
717 add_unmatched_state_hook(my_size_id, &unmatched_size_state);
719 select_caller_info_hook(set_param_buf_size, BUF_SIZE);
720 select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
722 add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
723 add_function_assign_hook("calloc", &match_calloc, NULL);
724 add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
725 if (option_project == PROJ_KERNEL) {
726 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
727 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
728 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
729 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
730 add_function_assign_hook("kcalloc", &match_calloc, NULL);
731 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
732 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
733 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
734 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
735 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
736 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
737 add_function_assign_hook("dma_alloc_attrs", &match_alloc, INT_PTR(1));
738 add_function_assign_hook("devm_kmalloc", &match_alloc, INT_PTR(1));
739 add_function_assign_hook("devm_kzalloc", &match_alloc, INT_PTR(1));
741 add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
742 add_hook(&match_strlen_condition, CONDITION_HOOK);
744 add_function_assign_hook("strndup", match_strndup, NULL);
745 if (option_project == PROJ_KERNEL)
746 add_function_assign_hook("kstrndup", match_strndup, NULL);
748 add_modification_hook(my_size_id, &set_size_undefined);
750 add_merge_hook(my_size_id, &merge_size_func);
753 void register_buf_size_late(int id)
755 add_function_hook("strlcpy", &match_limited, &b0_l2);
756 add_function_hook("strlcat", &match_limited, &b0_l2);
757 add_function_hook("memscan", &match_limited, &b0_l2);
759 add_function_hook("strcpy", &match_strcpy, NULL);
761 add_hook(&match_call, FUNCTION_CALL_HOOK);
762 add_member_info_callback(my_size_id, struct_member_callback);