?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
smatch_scripts/new_bugs.pl: total re-write of the script in Perl
[smatch.git] / smatch_flow.c
blob638ac8b133d1efac40136f45a55b2e84d5bfc6d0
1 /*
2 * Copyright (C) 2006,2008 Dan Carpenter.
3 *
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.
8 *
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.
13 *
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
16 */
17
18 #define _GNU_SOURCE 1
19 #include <unistd.h>
20 #include <stdio.h>
21 #include "token.h"
22 #include "scope.h"
23 #include "smatch.h"
24 #include "smatch_expression_stacks.h"
25 #include "smatch_extra.h"
26 #include "smatch_slist.h"
27
28 int __in_fake_assign;
29 int __in_fake_struct_assign;
30 int __in_fake_var_assign;
31 int __fake_state_cnt;
32 int in_fake_env;
33 int final_pass;
34 int __inline_call;
35 struct expression *__inline_fn;
36
37 static int __smatch_lineno = 0;
38
39 static char *base_file;
40 static const char *filename;
41 static char *pathname;
42 static char *full_filename;
43 static char *full_base_file;
44 static char *cur_func;
45 static unsigned int loop_count;
46 static int last_goto_statement_handled;
47 int __expr_stmt_count;
48 int __in_function_def;
49 int __in_unmatched_hook;
50 static struct expression_list *switch_expr_stack = NULL;
51 static struct expression_list *post_op_stack = NULL;
52
53 static struct ptr_list *fn_data_list;
54 static struct ptr_list *backup;
55
56 struct expression_list *big_expression_stack;
57 struct statement_list *big_statement_stack;
58 struct statement *__prev_stmt;
59 struct statement *__cur_stmt;
60 struct statement *__next_stmt;
61 int __in_pre_condition = 0;
62 int __bail_on_rest_of_function = 0;
63 static struct timeval fn_start_time;
64 static struct timeval outer_fn_start_time;
65 char *get_function(void) { return cur_func; }
66 int get_lineno(void) { return __smatch_lineno; }
67 int inside_loop(void) { return !!loop_count; }
68 int definitely_inside_loop(void) { return !!(loop_count & ~0x08000000); }
69 struct expression *get_switch_expr(void) { return top_expression(switch_expr_stack); }
70 int in_expression_statement(void) { return !!__expr_stmt_count; }
71
72 static void split_symlist(struct symbol_list *sym_list);
73 static void split_declaration(struct symbol_list *sym_list);
74 static void split_expr_list(struct expression_list *expr_list, struct expression *parent);
75 static void split_args(struct expression *expr);
76 static struct expression *fake_a_variable_assign(struct symbol *type, struct expression *expr);
77 static void add_inline_function(struct symbol *sym);
78 static void parse_inline(struct expression *expr);
79
80 int option_assume_loops = 0;
81 int option_two_passes = 0;
82 struct symbol *cur_func_sym = NULL;
83 struct stree *global_states;
84
85 const unsigned long valid_ptr_min = 4096;
86 unsigned long valid_ptr_max = ULONG_MAX & ~(MTAG_OFFSET_MASK);
87 const sval_t valid_ptr_min_sval = {
88 .type = &ptr_ctype,
89 {.value = 4096},
90 };
91 sval_t valid_ptr_max_sval = {
92 .type = &ptr_ctype,
93 {.value = ULONG_MAX & ~(MTAG_OFFSET_MASK)},
94 };
95 struct range_list *valid_ptr_rl;
96
97 void alloc_valid_ptr_rl(void)
98 {
99 valid_ptr_max = sval_type_max(&ulong_ctype).value & ~(MTAG_OFFSET_MASK);
100 valid_ptr_max_sval.value = valid_ptr_max;
101
102 valid_ptr_rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
103 valid_ptr_rl = cast_rl(&ptr_ctype, valid_ptr_rl);
104 valid_ptr_rl = clone_rl_permanent(valid_ptr_rl);
105 }
106
107 int outside_of_function(void)
108 {
109 return cur_func_sym == NULL;
110 }
111
112 const char *get_filename(void)
113 {
114 if (option_info && option_full_path)
115 return full_base_file;
116 if (option_info)
117 return base_file;
118 if (option_full_path)
119 return full_filename;
120 return filename;
121 }
122
123 const char *get_base_file(void)
124 {
125 if (option_full_path)
126 return full_base_file;
127 return base_file;
128 }
129
130 static void set_position(struct position pos)
131 {
132 int len;
133 static int prev_stream = -1;
134
135 if (in_fake_env)
136 return;
137
138 if (pos.stream == 0 && pos.line == 0)
139 return;
140
141 __smatch_lineno = pos.line;
142
143 if (pos.stream == prev_stream)
144 return;
145
146 filename = stream_name(pos.stream);
147
148 free(full_filename);
149 pathname = getcwd(NULL, 0);
150 if (pathname) {
151 len = strlen(pathname) + 1 + strlen(filename) + 1;
152 full_filename = malloc(len);
153 snprintf(full_filename, len, "%s/%s", pathname, filename);
154 } else {
155 full_filename = alloc_string(filename);
156 }
157 free(pathname);
158 }
159
160 int is_assigned_call(struct expression *expr)
161 {
162 struct expression *parent = expr_get_parent_expr(expr);
163
164 if (parent &&
165 parent->type == EXPR_ASSIGNMENT &&
166 parent->op == '=' &&
167 strip_expr(parent->right) == expr)
168 return 1;
169
170 return 0;
171 }
172
173 int is_fake_assigned_call(struct expression *expr)
174 {
175 struct expression *parent = expr_get_fake_parent_expr(expr);
176
177 if (parent &&
178 parent->type == EXPR_ASSIGNMENT &&
179 parent->op == '=' &&
180 strip_expr(parent->right) == expr)
181 return 1;
182
183 return 0;
184 }
185
186 static bool is_inline_func(struct expression *expr)
187 {
188 if (expr->type != EXPR_SYMBOL || !expr->symbol)
189 return false;
190 if (!expr->symbol->definition)
191 return false;
192 if (expr->symbol->definition->ctype.modifiers & MOD_INLINE)
193 return true;
194
195 return 0;
196 }
197
198 static int is_noreturn_func(struct expression *expr)
199 {
200 if (expr->type != EXPR_SYMBOL || !expr->symbol)
201 return 0;
202 if (expr->symbol->ctype.modifiers & MOD_NORETURN)
203 return 1;
204 return 0;
205 }
206
207 static int inline_budget = 20;
208
209 int inlinable(struct expression *expr)
210 {
211 struct symbol *sym;
212 struct statement *last_stmt = NULL;
213
214 if (__inline_fn) /* don't nest */
215 return 0;
216
217 if (expr->type != EXPR_SYMBOL || !expr->symbol)
218 return 0;
219 if (is_no_inline_function(expr->symbol->ident->name))
220 return 0;
221 sym = get_base_type(expr->symbol);
222 if (sym->stmt && sym->stmt->type == STMT_COMPOUND) {
223 if (ptr_list_size((struct ptr_list *)sym->stmt->stmts) > 10)
224 return 0;
225 if (sym->stmt->type != STMT_COMPOUND)
226 return 0;
227 last_stmt = last_ptr_list((struct ptr_list *)sym->stmt->stmts);
228 }
229 if (sym->inline_stmt && sym->inline_stmt->type == STMT_COMPOUND) {
230 if (ptr_list_size((struct ptr_list *)sym->inline_stmt->stmts) > 10)
231 return 0;
232 if (sym->inline_stmt->type != STMT_COMPOUND)
233 return 0;
234 last_stmt = last_ptr_list((struct ptr_list *)sym->inline_stmt->stmts);
235 }
236
237 if (!last_stmt)
238 return 0;
239
240 /* the magic numbers in this function are pulled out of my bum. */
241 if (last_stmt->pos.line > sym->pos.line + inline_budget)
242 return 0;
243
244 return 1;
245 }
246
247 void __process_post_op_stack(void)
248 {
249 struct expression *expr;
250
251 FOR_EACH_PTR(post_op_stack, expr) {
252 __pass_to_client(expr, OP_HOOK);
253 } END_FOR_EACH_PTR(expr);
254
255 __free_ptr_list((struct ptr_list **)&post_op_stack);
256 }
257
258 static int handle_comma_assigns(struct expression *expr)
259 {
260 struct expression *right;
261 struct expression *assign;
262
263 right = strip_expr(expr->right);
264 if (right->type != EXPR_COMMA)
265 return 0;
266
267 __split_expr(right->left);
268 __process_post_op_stack();
269
270 assign = assign_expression(expr->left, '=', right->right);
271 __split_expr(assign);
272
273 return 1;
274 }
275
276 /* This is to handle *p++ = foo; assignments */
277 static int handle_postop_assigns(struct expression *expr)
278 {
279 struct expression *left, *fake_left;
280 struct expression *assign;
281
282 left = strip_expr(expr->left);
283 if (left->type != EXPR_PREOP || left->op != '*')
284 return 0;
285 left = strip_expr(left->unop);
286 if (left->type != EXPR_POSTOP)
287 return 0;
288
289 fake_left = deref_expression(strip_expr(left->unop));
290 assign = assign_expression(fake_left, '=', expr->right);
291
292 __split_expr(assign);
293 __split_expr(expr->left);
294
295 return 1;
296 }
297
298 static int prev_expression_is_getting_address(struct expression *expr)
299 {
300 struct expression *parent;
301
302 do {
303 parent = expr_get_parent_expr(expr);
304
305 if (!parent)
306 return 0;
307 if (parent->type == EXPR_PREOP && parent->op == '&')
308 return 1;
309 if (parent->type == EXPR_PREOP && parent->op == '(')
310 goto next;
311 if (parent->type == EXPR_DEREF && parent->op == '.')
312 goto next;
313
314 return 0;
315 next:
316 expr = parent;
317 } while (1);
318 }
319
320 static void handle_builtin_overflow_func(struct expression *expr)
321 {
322 struct expression *a, *b, *res, *assign;
323 int op;
324
325 if (sym_name_is("__builtin_add_overflow", expr->fn))
326 op = '+';
327 else if (sym_name_is("__builtin_sub_overflow", expr->fn))
328 op = '-';
329 else if (sym_name_is("__builtin_mul_overflow", expr->fn))
330 op = '*';
331 else
332 return;
333
334 a = get_argument_from_call_expr(expr->args, 0);
335 b = get_argument_from_call_expr(expr->args, 1);
336 res = get_argument_from_call_expr(expr->args, 2);
337
338 assign = assign_expression(deref_expression(res), '=', binop_expression(a, op, b));
339 __split_expr(assign);
340 }
341
342 static int handle__builtin_choose_expr(struct expression *expr)
343 {
344 struct expression *const_expr, *expr1, *expr2;
345 sval_t sval;
346
347 if (!sym_name_is("__builtin_choose_expr", expr->fn))
348 return 0;
349
350 const_expr = get_argument_from_call_expr(expr->args, 0);
351 expr1 = get_argument_from_call_expr(expr->args, 1);
352 expr2 = get_argument_from_call_expr(expr->args, 2);
353
354 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
355 return 0;
356 if (sval.value)
357 __split_expr(expr1);
358 else
359 __split_expr(expr2);
360 return 1;
361 }
362
363 static int handle__builtin_choose_expr_assigns(struct expression *expr)
364 {
365 struct expression *const_expr, *right, *expr1, *expr2, *fake;
366 sval_t sval;
367
368 right = strip_expr(expr->right);
369 if (right->type != EXPR_CALL)
370 return 0;
371 if (!sym_name_is("__builtin_choose_expr", right->fn))
372 return 0;
373
374 const_expr = get_argument_from_call_expr(right->args, 0);
375 expr1 = get_argument_from_call_expr(right->args, 1);
376 expr2 = get_argument_from_call_expr(right->args, 2);
377
378 if (!get_value(const_expr, &sval) || !expr1 || !expr2)
379 return 0;
380
381 fake = assign_expression(expr->left, '=', sval.value ? expr1 : expr2);
382 __split_expr(fake);
383 return 1;
384 }
385
386 void __split_expr(struct expression *expr)
387 {
388 if (!expr)
389 return;
390
391 // sm_msg(" Debug expr_type %d %s", expr->type, show_special(expr->op));
392
393 if (__in_fake_assign && expr->type != EXPR_ASSIGNMENT)
394 return;
395 if (__in_fake_assign >= 4) /* don't allow too much nesting */
396 return;
397
398 push_expression(&big_expression_stack, expr);
399 set_position(expr->pos);
400 __pass_to_client(expr, EXPR_HOOK);
401
402 switch (expr->type) {
403 case EXPR_PREOP:
404 expr_set_parent_expr(expr->unop, expr);
405
406 if (expr->op == '*' &&
407 !prev_expression_is_getting_address(expr))
408 __pass_to_client(expr, DEREF_HOOK);
409 __split_expr(expr->unop);
410 __pass_to_client(expr, OP_HOOK);
411 break;
412 case EXPR_POSTOP:
413 expr_set_parent_expr(expr->unop, expr);
414
415 __split_expr(expr->unop);
416 push_expression(&post_op_stack, expr);
417 break;
418 case EXPR_STATEMENT:
419 __expr_stmt_count++;
420 if (expr->statement && !expr->statement) {
421 stmt_set_parent_stmt(expr->statement,
422 last_ptr_list((struct ptr_list *)big_statement_stack));
423 }
424 __split_stmt(expr->statement);
425 __expr_stmt_count--;
426 break;
427 case EXPR_LOGICAL:
428 case EXPR_COMPARE:
429 expr_set_parent_expr(expr->left, expr);
430 expr_set_parent_expr(expr->right, expr);
431
432 __pass_to_client(expr, LOGIC_HOOK);
433 __handle_logic(expr);
434 break;
435 case EXPR_BINOP:
436 expr_set_parent_expr(expr->left, expr);
437 expr_set_parent_expr(expr->right, expr);
438
439 __pass_to_client(expr, BINOP_HOOK);
440 case EXPR_COMMA:
441 expr_set_parent_expr(expr->left, expr);
442 expr_set_parent_expr(expr->right, expr);
443
444 __split_expr(expr->left);
445 __process_post_op_stack();
446 __split_expr(expr->right);
447 break;
448 case EXPR_ASSIGNMENT: {
449 struct expression *right;
450
451 expr_set_parent_expr(expr->left, expr);
452 expr_set_parent_expr(expr->right, expr);
453
454 right = strip_expr(expr->right);
455 if (!right)
456 break;
457
458 __pass_to_client(expr, RAW_ASSIGNMENT_HOOK);
459
460 /* foo = !bar() */
461 if (__handle_condition_assigns(expr))
462 goto after_assign;
463 /* foo = (x < 5 ? foo : 5); */
464 if (__handle_select_assigns(expr))
465 goto after_assign;
466 /* foo = ({frob(); frob(); frob(); 1;}) */
467 if (__handle_expr_statement_assigns(expr))
468 break; // FIXME: got after
469 /* foo = (3, 4); */
470 if (handle_comma_assigns(expr))
471 goto after_assign;
472 if (handle__builtin_choose_expr_assigns(expr))
473 goto after_assign;
474 if (handle_postop_assigns(expr))
475 break; /* no need to goto after_assign */
476
477 __split_expr(expr->right);
478 if (outside_of_function())
479 __pass_to_client(expr, GLOBAL_ASSIGNMENT_HOOK);
480 else
481 __pass_to_client(expr, ASSIGNMENT_HOOK);
482
483 __fake_struct_member_assignments(expr);
484
485 /* Re-examine ->right for inlines. See the commit message */
486 right = strip_expr(expr->right);
487 if (expr->op == '=' && right->type == EXPR_CALL)
488 __pass_to_client(expr, CALL_ASSIGNMENT_HOOK);
489
490 if (get_macro_name(right->pos) &&
491 get_macro_name(expr->pos) != get_macro_name(right->pos))
492 __pass_to_client(expr, MACRO_ASSIGNMENT_HOOK);
493
494 after_assign:
495 __pass_to_client(expr, ASSIGNMENT_HOOK_AFTER);
496 __split_expr(expr->left);
497 break;
498 }
499 case EXPR_DEREF:
500 expr_set_parent_expr(expr->deref, expr);
501
502 __pass_to_client(expr, DEREF_HOOK);
503 __split_expr(expr->deref);
504 break;
505 case EXPR_SLICE:
506 expr_set_parent_expr(expr->base, expr);
507
508 __split_expr(expr->base);
509 break;
510 case EXPR_CAST:
511 case EXPR_FORCE_CAST:
512 expr_set_parent_expr(expr->cast_expression, expr);
513
514 __pass_to_client(expr, CAST_HOOK);
515 __split_expr(expr->cast_expression);
516 break;
517 case EXPR_SIZEOF:
518 if (expr->cast_expression)
519 __pass_to_client(strip_parens(expr->cast_expression),
520 SIZEOF_HOOK);
521 break;
522 case EXPR_OFFSETOF:
523 case EXPR_ALIGNOF:
524 break;
525 case EXPR_CONDITIONAL:
526 case EXPR_SELECT:
527 expr_set_parent_expr(expr->conditional, expr);
528 expr_set_parent_expr(expr->cond_true, expr);
529 expr_set_parent_expr(expr->cond_false, expr);
530
531 if (known_condition_true(expr->conditional)) {
532 __split_expr(expr->cond_true);
533 break;
534 }
535 if (known_condition_false(expr->conditional)) {
536 __split_expr(expr->cond_false);
537 break;
538 }
539 __pass_to_client(expr, SELECT_HOOK);
540 __split_whole_condition(expr->conditional);
541 __split_expr(expr->cond_true);
542 __push_true_states();
543 __use_false_states();
544 __split_expr(expr->cond_false);
545 __merge_true_states();
546 break;
547 case EXPR_CALL:
548 expr_set_parent_expr(expr->fn, expr);
549
550 if (sym_name_is("__builtin_constant_p", expr->fn))
551 break;
552 if (handle__builtin_choose_expr(expr))
553 break;
554 __split_expr(expr->fn);
555 split_args(expr);
556 if (is_inline_func(expr->fn))
557 add_inline_function(expr->fn->symbol->definition);
558 if (inlinable(expr->fn))
559 __inline_call = 1;
560 __process_post_op_stack();
561 __pass_to_client(expr, FUNCTION_CALL_HOOK_BEFORE);
562 __pass_to_client(expr, FUNCTION_CALL_HOOK);
563 __inline_call = 0;
564 if (inlinable(expr->fn))
565 parse_inline(expr);
566 __pass_to_client(expr, CALL_HOOK_AFTER_INLINE);
567 if (is_noreturn_func(expr->fn))
568 nullify_path();
569 handle_builtin_overflow_func(expr);
570 break;
571 case EXPR_INITIALIZER:
572 split_expr_list(expr->expr_list, expr);
573 break;
574 case EXPR_IDENTIFIER:
575 expr_set_parent_expr(expr->ident_expression, expr);
576 __split_expr(expr->ident_expression);
577 break;
578 case EXPR_INDEX:
579 expr_set_parent_expr(expr->idx_expression, expr);
580 __split_expr(expr->idx_expression);
581 break;
582 case EXPR_POS:
583 expr_set_parent_expr(expr->init_expr, expr);
584 __split_expr(expr->init_expr);
585 break;
586 case EXPR_SYMBOL:
587 __pass_to_client(expr, SYM_HOOK);
588 break;
589 case EXPR_STRING:
590 __pass_to_client(expr, STRING_HOOK);
591 break;
592 default:
593 break;
594 };
595 __pass_to_client(expr, EXPR_HOOK_AFTER);
596 pop_expression(&big_expression_stack);
597 }
598
599 static int is_forever_loop(struct statement *stmt)
600 {
601 struct expression *expr;
602 sval_t sval;
603
604 expr = strip_expr(stmt->iterator_pre_condition);
605 if (!expr)
606 expr = stmt->iterator_post_condition;
607 if (!expr) {
608 /* this is a for(;;) loop... */
609 return 1;
610 }
611
612 if (get_value(expr, &sval) && sval.value != 0)
613 return 1;
614
615 return 0;
616 }
617
618 static int loop_num;
619 static char *get_loop_name(int num)
620 {
621 char buf[256];
622
623 snprintf(buf, 255, "-loop%d", num);
624 buf[255] = '\0';
625 return alloc_sname(buf);
626 }
627
628 /*
629 * Pre Loops are while and for loops.
630 */
631 static void handle_pre_loop(struct statement *stmt)
632 {
633 int once_through; /* we go through the loop at least once */
634 struct sm_state *extra_sm = NULL;
635 int unchanged = 0;
636 char *loop_name;
637 struct stree *stree = NULL;
638 struct sm_state *sm = NULL;
639
640 loop_name = get_loop_name(loop_num);
641 loop_num++;
642
643 __split_stmt(stmt->iterator_pre_statement);
644 __prev_stmt = stmt->iterator_pre_statement;
645
646 once_through = implied_condition_true(stmt->iterator_pre_condition);
647
648 loop_count++;
649 __push_continues();
650 __push_breaks();
651
652 __merge_gotos(loop_name, NULL);
653
654 extra_sm = __extra_handle_canonical_loops(stmt, &stree);
655 __in_pre_condition++;
656 __pass_to_client(stmt, PRELOOP_HOOK);
657 __split_whole_condition(stmt->iterator_pre_condition);
658 __in_pre_condition--;
659 FOR_EACH_SM(stree, sm) {
660 set_state(sm->owner, sm->name, sm->sym, sm->state);
661 } END_FOR_EACH_SM(sm);
662 free_stree(&stree);
663 if (extra_sm)
664 extra_sm = get_sm_state(extra_sm->owner, extra_sm->name, extra_sm->sym);
665
666 if (option_assume_loops)
667 once_through = 1;
668
669 __split_stmt(stmt->iterator_statement);
670 if (is_forever_loop(stmt)) {
671 __merge_continues();
672 __save_gotos(loop_name, NULL);
673
674 __push_fake_cur_stree();
675 __split_stmt(stmt->iterator_post_statement);
676 stree = __pop_fake_cur_stree();
677
678 __discard_false_states();
679 __use_breaks();
680
681 if (!__path_is_null())
682 __merge_stree_into_cur(stree);
683 free_stree(&stree);
684 } else {
685 __merge_continues();
686 unchanged = __iterator_unchanged(extra_sm);
687 __split_stmt(stmt->iterator_post_statement);
688 __prev_stmt = stmt->iterator_post_statement;
689 __cur_stmt = stmt;
690
691 __save_gotos(loop_name, NULL);
692 __in_pre_condition++;
693 __split_whole_condition(stmt->iterator_pre_condition);
694 __in_pre_condition--;
695 nullify_path();
696 __merge_false_states();
697 if (once_through)
698 __discard_false_states();
699 else
700 __merge_false_states();
701
702 if (extra_sm && unchanged)
703 __extra_pre_loop_hook_after(extra_sm,
704 stmt->iterator_post_statement,
705 stmt->iterator_pre_condition);
706 __merge_breaks();
707 }
708 loop_count--;
709 }
710
711 /*
712 * Post loops are do {} while();
713 */
714 static void handle_post_loop(struct statement *stmt)
715 {
716 char *loop_name;
717
718 loop_name = get_loop_name(loop_num);
719 loop_num++;
720 loop_count++;
721
722 __push_continues();
723 __push_breaks();
724 __merge_gotos(loop_name, NULL);
725 __split_stmt(stmt->iterator_statement);
726 __merge_continues();
727 if (!expr_is_zero(stmt->iterator_post_condition))
728 __save_gotos(loop_name, NULL);
729
730 if (is_forever_loop(stmt)) {
731 __use_breaks();
732 } else {
733 __split_whole_condition(stmt->iterator_post_condition);
734 __use_false_states();
735 __merge_breaks();
736 }
737 loop_count--;
738 }
739
740 static int empty_statement(struct statement *stmt)
741 {
742 if (!stmt)
743 return 0;
744 if (stmt->type == STMT_EXPRESSION && !stmt->expression)
745 return 1;
746 return 0;
747 }
748
749 static int last_stmt_on_same_line(void)
750 {
751 struct statement *stmt;
752 int i = 0;
753
754 FOR_EACH_PTR_REVERSE(big_statement_stack, stmt) {
755 if (!i++)
756 continue;
757 if (stmt->pos.line == get_lineno())
758 return 1;
759 return 0;
760 } END_FOR_EACH_PTR_REVERSE(stmt);
761 return 0;
762 }
763
764 static void split_asm_ops(struct asm_operand_list *ops)
765 {
766 struct asm_operand *op;
767
768 FOR_EACH_PTR(ops, op) {
769 __split_expr(op->expr);
770 } END_FOR_EACH_PTR(op);
771 }
772
773 static int is_case_val(struct statement *stmt, sval_t sval)
774 {
775 sval_t case_sval;
776
777 if (stmt->type != STMT_CASE)
778 return 0;
779 if (!stmt->case_expression) {
780 __set_default();
781 return 1;
782 }
783 if (!get_value(stmt->case_expression, &case_sval))
784 return 0;
785 if (case_sval.value == sval.value)
786 return 1;
787 return 0;
788 }
789
790 static struct range_list *get_case_rl(struct expression *switch_expr,
791 struct expression *case_expr,
792 struct expression *case_to)
793 {
794 sval_t start, end;
795 struct range_list *rl = NULL;
796 struct symbol *switch_type;
797
798 switch_type = get_type(switch_expr);
799 if (get_value(case_to, &end) && get_value(case_expr, &start)) {
800 start = sval_cast(switch_type, start);
801 end = sval_cast(switch_type, end);
802 add_range(&rl, start, end);
803 } else if (get_value(case_expr, &start)) {
804 start = sval_cast(switch_type, start);
805 add_range(&rl, start, start);
806 }
807
808 return rl;
809 }
810
811 static void split_known_switch(struct statement *stmt, sval_t sval)
812 {
813 struct statement *tmp;
814 struct range_list *rl;
815
816 __split_expr(stmt->switch_expression);
817 sval = sval_cast(get_type(stmt->switch_expression), sval);
818
819 push_expression(&switch_expr_stack, stmt->switch_expression);
820 __save_switch_states(top_expression(switch_expr_stack));
821 nullify_path();
822 __push_default();
823 __push_breaks();
824
825 stmt = stmt->switch_statement;
826
827 __push_scope_hooks();
828 FOR_EACH_PTR(stmt->stmts, tmp) {
829 __smatch_lineno = tmp->pos.line;
830 if (is_case_val(tmp, sval)) {
831 rl = alloc_rl(sval, sval);
832 __merge_switches(top_expression(switch_expr_stack), rl);
833 __pass_case_to_client(top_expression(switch_expr_stack), rl);
834 }
835 if (__path_is_null())
836 continue;
837 __split_stmt(tmp);
838 if (__path_is_null()) {
839 __set_default();
840 goto out;
841 }
842 } END_FOR_EACH_PTR(tmp);
843 out:
844 __call_scope_hooks();
845 if (!__pop_default())
846 __merge_switches(top_expression(switch_expr_stack), NULL);
847 __discard_switches();
848 __merge_breaks();
849 pop_expression(&switch_expr_stack);
850 }
851
852 static void split_case(struct statement *stmt)
853 {
854 struct range_list *rl = NULL;
855
856 expr_set_parent_stmt(stmt->case_expression, stmt);
857 expr_set_parent_stmt(stmt->case_to, stmt);
858
859 rl = get_case_rl(top_expression(switch_expr_stack),
860 stmt->case_expression, stmt->case_to);
861 while (stmt->case_statement->type == STMT_CASE) {
862 struct range_list *tmp;
863
864 tmp = get_case_rl(top_expression(switch_expr_stack),
865 stmt->case_statement->case_expression,
866 stmt->case_statement->case_to);
867 if (!tmp)
868 break;
869 rl = rl_union(rl, tmp);
870 if (!stmt->case_expression)
871 __set_default();
872 stmt = stmt->case_statement;
873 }
874
875 __merge_switches(top_expression(switch_expr_stack), rl);
876
877 if (!stmt->case_expression)
878 __set_default();
879 __split_stmt(stmt->case_statement);
880 }
881
882 int time_parsing_function(void)
883 {
884 return ms_since(&fn_start_time) / 1000;
885 }
886
887 bool taking_too_long(void)
888 {
889 if ((ms_since(&outer_fn_start_time) / 1000) > 60 * 5) /* five minutes */
890 return 1;
891 return 0;
892 }
893
894 static int is_last_stmt(struct statement *cur_stmt)
895 {
896 struct symbol *fn;
897 struct statement *stmt;
898
899 if (!cur_func_sym)
900 return 0;
901 fn = get_base_type(cur_func_sym);
902 if (!fn)
903 return 0;
904 stmt = fn->stmt;
905 if (!stmt)
906 stmt = fn->inline_stmt;
907 if (!stmt || stmt->type != STMT_COMPOUND)
908 return 0;
909 stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
910 if (stmt && stmt->type == STMT_LABEL)
911 stmt = stmt->label_statement;
912 if (stmt == cur_stmt)
913 return 1;
914 return 0;
915 }
916
917 static void handle_backward_goto(struct statement *goto_stmt)
918 {
919 const char *goto_name, *label_name;
920 struct statement *func_stmt;
921 struct symbol *base_type = get_base_type(cur_func_sym);
922 struct statement *tmp;
923 int found = 0;
924
925 if (!option_info)
926 return;
927 if (last_goto_statement_handled)
928 return;
929 last_goto_statement_handled = 1;
930
931 if (!goto_stmt->goto_label ||
932 goto_stmt->goto_label->type != SYM_LABEL ||
933 !goto_stmt->goto_label->ident)
934 return;
935 goto_name = goto_stmt->goto_label->ident->name;
936
937 func_stmt = base_type->stmt;
938 if (!func_stmt)
939 func_stmt = base_type->inline_stmt;
940 if (!func_stmt)
941 return;
942 if (func_stmt->type != STMT_COMPOUND)
943 return;
944
945 FOR_EACH_PTR(func_stmt->stmts, tmp) {
946 if (!found) {
947 if (tmp->type != STMT_LABEL)
948 continue;
949 if (!tmp->label_identifier ||
950 tmp->label_identifier->type != SYM_LABEL ||
951 !tmp->label_identifier->ident)
952 continue;
953 label_name = tmp->label_identifier->ident->name;
954 if (strcmp(goto_name, label_name) != 0)
955 continue;
956 found = 1;
957 }
958 __split_stmt(tmp);
959 } END_FOR_EACH_PTR(tmp);
960 }
961
962 static void fake_a_return(void)
963 {
964 struct symbol *return_type;
965
966 nullify_path();
967 __unnullify_path();
968
969 return_type = get_real_base_type(cur_func_sym);
970 return_type = get_real_base_type(return_type);
971 if (return_type != &void_ctype) {
972 __pass_to_client(unknown_value_expression(NULL), RETURN_HOOK);
973 nullify_path();
974 }
975 }
976
977 static void split_ret_value(struct expression *expr)
978 {
979 struct symbol *type;
980
981 if (!expr)
982 return;
983
984 type = get_real_base_type(cur_func_sym);
985 type = get_real_base_type(type);
986 expr = fake_a_variable_assign(type, expr);
987
988 __in_fake_var_assign++;
989 __split_expr(expr);
990 __in_fake_var_assign--;
991 }
992
993 static void fake_an_empty_default(struct position pos)
994 {
995 static struct statement none = {};
996
997 none.pos = pos;
998 none.type = STMT_NONE;
999 __merge_switches(top_expression(switch_expr_stack), NULL);
1000 __split_stmt(&none);
1001 }
1002
1003 static void split_compound(struct statement *stmt)
1004 {
1005 struct statement *prev = NULL;
1006 struct statement *cur = NULL;
1007 struct statement *next;
1008
1009 __push_scope_hooks();
1010
1011 FOR_EACH_PTR(stmt->stmts, next) {
1012 /* just set them all ahead of time */
1013 stmt_set_parent_stmt(next, stmt);
1014
1015 if (cur) {
1016 __prev_stmt = prev;
1017 __next_stmt = next;
1018 __cur_stmt = cur;
1019 __split_stmt(cur);
1020 }
1021 prev = cur;
1022 cur = next;
1023 } END_FOR_EACH_PTR(next);
1024 if (cur) {
1025 __prev_stmt = prev;
1026 __cur_stmt = cur;
1027 __next_stmt = NULL;
1028 __split_stmt(cur);
1029 }
1030
1031 /*
1032 * For function scope, then delay calling the scope hooks until the
1033 * end of function hooks can run. I'm not positive this is the right
1034 * thing...
1035 */
1036 if (!is_last_stmt(cur))
1037 __call_scope_hooks();
1038 }
1039
1040 /*
1041 * This is a hack, work around for detecting empty functions.
1042 */
1043 static int need_delayed_scope_hooks(void)
1044 {
1045 struct symbol *fn = get_base_type(cur_func_sym);
1046 struct statement *stmt;
1047
1048 if (!fn)
1049 return 0;
1050 stmt = fn->stmt;
1051 if (!stmt)
1052 stmt = fn->inline_stmt;
1053 if (stmt && stmt->type == STMT_COMPOUND)
1054 return 1;
1055 return 0;
1056 }
1057
1058 void __split_label_stmt(struct statement *stmt)
1059 {
1060 if (stmt->label_identifier &&
1061 stmt->label_identifier->type == SYM_LABEL &&
1062 stmt->label_identifier->ident) {
1063 loop_count |= 0x0800000;
1064 __merge_gotos(stmt->label_identifier->ident->name, stmt->label_identifier);
1065 }
1066 }
1067
1068 static void find_asm_gotos(struct statement *stmt)
1069 {
1070 struct symbol *sym;
1071
1072 FOR_EACH_PTR(stmt->asm_labels, sym) {
1073 __save_gotos(sym->ident->name, sym);
1074 } END_FOR_EACH_PTR(sym);
1075 }
1076
1077 void __split_stmt(struct statement *stmt)
1078 {
1079 static int indent_cnt;
1080 sval_t sval;
1081
1082 if (!stmt)
1083 goto out;
1084
1085 if (!__in_fake_assign)
1086 __silence_warnings_for_stmt = false;
1087
1088 if (__bail_on_rest_of_function || is_skipped_function())
1089 return;
1090
1091 if (out_of_memory() || taking_too_long()) {
1092 struct timeval stop;
1093
1094 gettimeofday(&stop, NULL);
1095
1096 __bail_on_rest_of_function = 1;
1097 final_pass = 1;
1098 sm_perror("Function too hairy. Giving up. %lu seconds",
1099 stop.tv_sec - fn_start_time.tv_sec);
1100 fake_a_return();
1101 final_pass = 0; /* turn off sm_msg() from here */
1102 return;
1103 }
1104
1105 indent_cnt++;
1106
1107 add_ptr_list(&big_statement_stack, stmt);
1108 free_expression_stack(&big_expression_stack);
1109 set_position(stmt->pos);
1110 __pass_to_client(stmt, STMT_HOOK);
1111
1112 switch (stmt->type) {
1113 case STMT_DECLARATION:
1114 split_declaration(stmt->declaration);
1115 break;
1116 case STMT_RETURN:
1117 expr_set_parent_stmt(stmt->ret_value, stmt);
1118
1119 split_ret_value(stmt->ret_value);
1120 __pass_to_client(stmt->ret_value, RETURN_HOOK);
1121 __process_post_op_stack();
1122 nullify_path();
1123 break;
1124 case STMT_EXPRESSION:
1125 expr_set_parent_stmt(stmt->expression, stmt);
1126 expr_set_parent_stmt(stmt->context, stmt);
1127
1128 __split_expr(stmt->expression);
1129 break;
1130 case STMT_COMPOUND:
1131 split_compound(stmt);
1132 break;
1133 case STMT_IF:
1134 stmt_set_parent_stmt(stmt->if_true, stmt);
1135 stmt_set_parent_stmt(stmt->if_false, stmt);
1136 expr_set_parent_stmt(stmt->if_conditional, stmt);
1137
1138 if (known_condition_true(stmt->if_conditional)) {
1139 __split_stmt(stmt->if_true);
1140 break;
1141 }
1142 if (known_condition_false(stmt->if_conditional)) {
1143 __split_stmt(stmt->if_false);
1144 break;
1145 }
1146 __split_whole_condition(stmt->if_conditional);
1147 __split_stmt(stmt->if_true);
1148 if (empty_statement(stmt->if_true) &&
1149 last_stmt_on_same_line() &&
1150 !get_macro_name(stmt->if_true->pos))
1151 sm_warning("if();");
1152 __push_true_states();
1153 __use_false_states();
1154 __split_stmt(stmt->if_false);
1155 __merge_true_states();
1156 break;
1157 case STMT_ITERATOR:
1158 stmt_set_parent_stmt(stmt->iterator_pre_statement, stmt);
1159 stmt_set_parent_stmt(stmt->iterator_statement, stmt);
1160 stmt_set_parent_stmt(stmt->iterator_post_statement, stmt);
1161 expr_set_parent_stmt(stmt->iterator_pre_condition, stmt);
1162 expr_set_parent_stmt(stmt->iterator_post_condition, stmt);
1163
1164 if (stmt->iterator_pre_condition)
1165 handle_pre_loop(stmt);
1166 else if (stmt->iterator_post_condition)
1167 handle_post_loop(stmt);
1168 else {
1169 // these are for(;;) type loops.
1170 handle_pre_loop(stmt);
1171 }
1172 break;
1173 case STMT_SWITCH:
1174 stmt_set_parent_stmt(stmt->switch_statement, stmt);
1175 expr_set_parent_stmt(stmt->switch_expression, stmt);
1176
1177 if (get_value(stmt->switch_expression, &sval)) {
1178 split_known_switch(stmt, sval);
1179 break;
1180 }
1181 __split_expr(stmt->switch_expression);
1182 push_expression(&switch_expr_stack, stmt->switch_expression);
1183 __save_switch_states(top_expression(switch_expr_stack));
1184 nullify_path();
1185 __push_default();
1186 __push_breaks();
1187 __split_stmt(stmt->switch_statement);
1188 if (!__pop_default() && have_remaining_cases())
1189 fake_an_empty_default(stmt->pos);
1190 __discard_switches();
1191 __merge_breaks();
1192 pop_expression(&switch_expr_stack);
1193 break;
1194 case STMT_CASE:
1195 split_case(stmt);
1196 break;
1197 case STMT_LABEL:
1198 __split_label_stmt(stmt);
1199 __split_stmt(stmt->label_statement);
1200 break;
1201 case STMT_GOTO:
1202 expr_set_parent_stmt(stmt->goto_expression, stmt);
1203
1204 __split_expr(stmt->goto_expression);
1205 if (stmt->goto_label && stmt->goto_label->type == SYM_NODE) {
1206 if (!strcmp(stmt->goto_label->ident->name, "break")) {
1207 __process_breaks();
1208 } else if (!strcmp(stmt->goto_label->ident->name,
1209 "continue")) {
1210 __process_continues();
1211 }
1212 } else if (stmt->goto_label &&
1213 stmt->goto_label->type == SYM_LABEL &&
1214 stmt->goto_label->ident) {
1215 __save_gotos(stmt->goto_label->ident->name, stmt->goto_label);
1216 }
1217 nullify_path();
1218 if (is_last_stmt(stmt))
1219 handle_backward_goto(stmt);
1220 break;
1221 case STMT_NONE:
1222 break;
1223 case STMT_ASM:
1224 expr_set_parent_stmt(stmt->asm_string, stmt);
1225
1226 find_asm_gotos(stmt);
1227 __pass_to_client(stmt, ASM_HOOK);
1228 __split_expr(stmt->asm_string);
1229 split_asm_ops(stmt->asm_outputs);
1230 split_asm_ops(stmt->asm_inputs);
1231 split_expr_list(stmt->asm_clobbers, NULL);
1232 break;
1233 case STMT_CONTEXT:
1234 break;
1235 case STMT_RANGE:
1236 __split_expr(stmt->range_expression);
1237 __split_expr(stmt->range_low);
1238 __split_expr(stmt->range_high);
1239 break;
1240 }
1241 __pass_to_client(stmt, STMT_HOOK_AFTER);
1242 if (--indent_cnt == 0)
1243 __discard_fake_states();
1244 out:
1245 __process_post_op_stack();
1246 }
1247
1248 static void split_expr_list(struct expression_list *expr_list, struct expression *parent)
1249 {
1250 struct expression *expr;
1251
1252 FOR_EACH_PTR(expr_list, expr) {
1253 expr_set_parent_expr(expr, parent);
1254 __split_expr(expr);
1255 __process_post_op_stack();
1256 } END_FOR_EACH_PTR(expr);
1257 }
1258
1259 static bool cast_arg(struct symbol *type, struct expression *arg)
1260 {
1261 struct symbol *orig;
1262
1263 if (!type)
1264 return false;
1265
1266 arg = strip_parens(arg);
1267 if (arg != strip_expr(arg))
1268 return true;
1269
1270 orig = get_type(arg);
1271 if (!orig)
1272 return true;
1273 if (orig == type)
1274 return false;
1275
1276 /*
1277 * I would have expected that we could just do use (orig == type) but I
1278 * guess for pointers we need to get the basetype to do that comparison.
1279 *
1280 */
1281
1282 if (orig->type != SYM_PTR ||
1283 type->type != SYM_PTR) {
1284 if (type_fits(type, orig))
1285 return false;
1286 return true;
1287 }
1288 orig = get_real_base_type(orig);
1289 type = get_real_base_type(type);
1290 if (orig == type)
1291 return false;
1292
1293 return true;
1294 }
1295
1296 static struct expression *fake_a_variable_assign(struct symbol *type, struct expression *expr)
1297 {
1298 struct expression *var, *assign, *parent;
1299 char buf[64];
1300 bool cast;
1301
1302 if (!expr)
1303 return NULL;
1304
1305 if (expr->type == EXPR_ASSIGNMENT)
1306 return expr;
1307
1308 cast = cast_arg(type, expr);
1309 /*
1310 * Using expr_to_sym() here is a hack. We want to say that we don't
1311 * need to assign frob(foo) or frob(foo->bar) if the types are right.
1312 * It turns out faking these assignments is way more expensive than I
1313 * would have imagined. I'm not sure why exactly.
1314 *
1315 */
1316 if (!cast) {
1317 /*
1318 * if the code is "return *p;" where "p" is a user pointer then
1319 * we want to create a fake assignment so that it sets the state
1320 * in check_kernel_user_data.c.
1321 *
1322 */
1323 if (expr->type != EXPR_PREOP &&
1324 expr->op != '*' && expr->op != '&' &&
1325 expr_to_sym(expr))
1326 return expr;
1327 }
1328
1329 snprintf(buf, sizeof(buf), "__sm_fake_%p", expr);
1330 var = fake_variable(type, buf);
1331 assign = assign_expression(var, '=', expr);
1332 assign->smatch_flags |= Fake;
1333
1334 parent = expr_get_parent_expr(expr);
1335 expr_set_parent_expr(assign, parent);
1336 expr_set_parent_expr(expr, assign);
1337
1338 __fake_state_cnt++;
1339
1340 return assign;
1341 }
1342
1343 static void split_args(struct expression *expr)
1344 {
1345 struct expression *arg, *tmp;
1346 struct symbol *type;
1347 int i;
1348
1349 i = -1;
1350 FOR_EACH_PTR(expr->args, arg) {
1351 i++;
1352 expr_set_parent_expr(arg, expr);
1353 type = get_arg_type(expr->fn, i);
1354 tmp = fake_a_variable_assign(type, arg);
1355 if (tmp != arg)
1356 __in_fake_var_assign++;
1357 __split_expr(tmp);
1358 if (tmp != arg)
1359 __in_fake_var_assign--;
1360 __process_post_op_stack();
1361 } END_FOR_EACH_PTR(arg);
1362 }
1363
1364 static void split_sym(struct symbol *sym)
1365 {
1366 if (!sym)
1367 return;
1368 if (!(sym->namespace & NS_SYMBOL))
1369 return;
1370
1371 __split_stmt(sym->stmt);
1372 __split_expr(sym->array_size);
1373 split_symlist(sym->arguments);
1374 split_symlist(sym->symbol_list);
1375 __split_stmt(sym->inline_stmt);
1376 split_symlist(sym->inline_symbol_list);
1377 }
1378
1379 static void split_symlist(struct symbol_list *sym_list)
1380 {
1381 struct symbol *sym;
1382
1383 FOR_EACH_PTR(sym_list, sym) {
1384 split_sym(sym);
1385 } END_FOR_EACH_PTR(sym);
1386 }
1387
1388 typedef void (fake_cb)(struct expression *expr);
1389
1390 static int member_to_number(struct expression *expr, struct ident *member)
1391 {
1392 struct symbol *type, *tmp;
1393 char *name;
1394 int i;
1395
1396 if (!member)
1397 return -1;
1398 name = member->name;
1399
1400 type = get_type(expr);
1401 if (!type || type->type != SYM_STRUCT)
1402 return -1;
1403
1404 i = -1;
1405 FOR_EACH_PTR(type->symbol_list, tmp) {
1406 i++;
1407 if (!tmp->ident)
1408 continue;
1409 if (strcmp(name, tmp->ident->name) == 0)
1410 return i;
1411 } END_FOR_EACH_PTR(tmp);
1412 return -1;
1413 }
1414
1415 static struct ident *number_to_member(struct expression *expr, int num)
1416 {
1417 struct symbol *type, *member;
1418 int i = 0;
1419
1420 type = get_type(expr);
1421 if (!type || type->type != SYM_STRUCT)
1422 return NULL;
1423
1424 FOR_EACH_PTR(type->symbol_list, member) {
1425 if (i == num)
1426 return member->ident;
1427 i++;
1428 } END_FOR_EACH_PTR(member);
1429 return NULL;
1430 }
1431
1432 static void fake_element_assigns_helper(struct expression *array, struct expression_list *expr_list, fake_cb *fake_cb);
1433
1434 static void set_inner_struct_members(struct expression *expr, struct symbol *member)
1435 {
1436 struct expression *edge_member, *assign;
1437 struct symbol *base = get_real_base_type(member);
1438 struct symbol *tmp;
1439
1440 if (member->ident)
1441 expr = member_expression(expr, '.', member->ident);
1442
1443 FOR_EACH_PTR(base->symbol_list, tmp) {
1444 struct symbol *type;
1445
1446 type = get_real_base_type(tmp);
1447 if (!type)
1448 continue;
1449
1450 edge_member = member_expression(expr, '.', tmp->ident);
1451 if (get_extra_state(edge_member))
1452 continue;
1453
1454 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
1455 set_inner_struct_members(expr, tmp);
1456 continue;
1457 }
1458
1459 if (!tmp->ident)
1460 continue;
1461
1462 assign = assign_expression(edge_member, '=', zero_expr());
1463 __split_expr(assign);
1464 } END_FOR_EACH_PTR(tmp);
1465
1466
1467 }
1468
1469 static void set_unset_to_zero(struct symbol *type, struct expression *expr)
1470 {
1471 struct symbol *tmp;
1472 struct expression *member = NULL;
1473 struct expression *assign;
1474 int op = '*';
1475
1476 if (expr->type == EXPR_PREOP && expr->op == '&') {
1477 expr = strip_expr(expr->unop);
1478 op = '.';
1479 }
1480
1481 FOR_EACH_PTR(type->symbol_list, tmp) {
1482 type = get_real_base_type(tmp);
1483 if (!type)
1484 continue;
1485
1486 if (tmp->ident) {
1487 member = member_expression(expr, op, tmp->ident);
1488 if (get_extra_state(member))
1489 continue;
1490 }
1491
1492 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
1493 set_inner_struct_members(expr, tmp);
1494 continue;
1495 }
1496 if (type->type == SYM_ARRAY)
1497 continue;
1498 if (!tmp->ident)
1499 continue;
1500
1501 assign = assign_expression(member, '=', zero_expr());
1502 __split_expr(assign);
1503 } END_FOR_EACH_PTR(tmp);
1504 }
1505
1506 static void fake_member_assigns_helper(struct expression *symbol, struct expression_list *members, fake_cb *fake_cb)
1507 {
1508 struct expression *deref, *assign, *tmp, *right;
1509 struct symbol *struct_type, *type;
1510 struct ident *member;
1511 int member_idx;
1512
1513 struct_type = get_type(symbol);
1514 if (!struct_type ||
1515 (struct_type->type != SYM_STRUCT && struct_type->type != SYM_UNION))
1516 return;
1517
1518 /*
1519 * We're parsing an initializer that could look something like this:
1520 * struct foo foo = {
1521 * 42,
1522 * .whatever.xxx = 11,
1523 * .zzz = 12,
1524 * };
1525 *
1526 * So what we have here is a list with 42, .whatever, and .zzz. We need
1527 * to break it up into left and right sides of the assignments.
1528 *
1529 */
1530 member_idx = 0;
1531 FOR_EACH_PTR(members, tmp) {
1532 deref = NULL;
1533 if (tmp->type == EXPR_IDENTIFIER) {
1534 member_idx = member_to_number(symbol, tmp->expr_ident);
1535 while (tmp->type == EXPR_IDENTIFIER) {
1536 member = tmp->expr_ident;
1537 tmp = tmp->ident_expression;
1538 if (deref)
1539 deref = member_expression(deref, '.', member);
1540 else
1541 deref = member_expression(symbol, '.', member);
1542 }
1543 } else {
1544 member = number_to_member(symbol, member_idx);
1545 deref = member_expression(symbol, '.', member);
1546 }
1547 right = tmp;
1548 member_idx++;
1549 if (right->type == EXPR_INITIALIZER) {
1550 type = get_type(deref);
1551 if (type && type->type == SYM_ARRAY)
1552 fake_element_assigns_helper(deref, right->expr_list, fake_cb);
1553 else
1554 fake_member_assigns_helper(deref, right->expr_list, fake_cb);
1555 } else {
1556 assign = assign_expression(deref, '=', right);
1557 fake_cb(assign);
1558 }
1559 } END_FOR_EACH_PTR(tmp);
1560
1561 set_unset_to_zero(struct_type, symbol);
1562 }
1563
1564 static void fake_member_assigns(struct symbol *sym, fake_cb *fake_cb)
1565 {
1566 fake_member_assigns_helper(symbol_expression(sym),
1567 sym->initializer->expr_list, fake_cb);
1568 }
1569
1570 static void fake_element_assigns_helper(struct expression *array, struct expression_list *expr_list, fake_cb *fake_cb)
1571 {
1572 struct expression *offset, *binop, *assign, *tmp;
1573 struct symbol *type;
1574 int idx;
1575
1576 if (ptr_list_size((struct ptr_list *)expr_list) > 1000)
1577 return;
1578
1579 idx = 0;
1580 FOR_EACH_PTR(expr_list, tmp) {
1581 if (tmp->type == EXPR_INDEX) {
1582 if (tmp->idx_from != tmp->idx_to)
1583 return;
1584 idx = tmp->idx_from;
1585 if (!tmp->idx_expression)
1586 goto next;
1587 tmp = tmp->idx_expression;
1588 }
1589 offset = value_expr(idx);
1590 binop = array_element_expression(array, offset);
1591 if (tmp->type == EXPR_INITIALIZER) {
1592 type = get_type(binop);
1593 if (type && type->type == SYM_ARRAY)
1594 fake_element_assigns_helper(binop, tmp->expr_list, fake_cb);
1595 else
1596 fake_member_assigns_helper(binop, tmp->expr_list, fake_cb);
1597 } else {
1598 assign = assign_expression(binop, '=', tmp);
1599 fake_cb(assign);
1600 }
1601 next:
1602 idx++;
1603 } END_FOR_EACH_PTR(tmp);
1604 }
1605
1606 static void fake_element_assigns(struct symbol *sym, fake_cb *fake_cb)
1607 {
1608 fake_element_assigns_helper(symbol_expression(sym), sym->initializer->expr_list, fake_cb);
1609 }
1610
1611 static void fake_assign_expr(struct symbol *sym)
1612 {
1613 struct expression *assign, *symbol;
1614
1615 symbol = symbol_expression(sym);
1616 assign = assign_expression(symbol, '=', sym->initializer);
1617 __split_expr(assign);
1618 }
1619
1620 static void do_initializer_stuff(struct symbol *sym)
1621 {
1622 if (!sym->initializer)
1623 return;
1624
1625 if (sym->initializer->type == EXPR_INITIALIZER) {
1626 if (get_real_base_type(sym)->type == SYM_ARRAY)
1627 fake_element_assigns(sym, __split_expr);
1628 else
1629 fake_member_assigns(sym, __split_expr);
1630 } else {
1631 fake_assign_expr(sym);
1632 }
1633 }
1634
1635 static void split_declaration(struct symbol_list *sym_list)
1636 {
1637 struct symbol *sym;
1638
1639 FOR_EACH_PTR(sym_list, sym) {
1640 __pass_to_client(sym, DECLARATION_HOOK);
1641 do_initializer_stuff(sym);
1642 split_sym(sym);
1643 } END_FOR_EACH_PTR(sym);
1644 }
1645
1646 static void call_global_assign_hooks(struct expression *assign)
1647 {
1648 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1649 }
1650
1651 static void fake_global_assign(struct symbol *sym)
1652 {
1653 struct expression *assign, *symbol;
1654
1655 if (get_real_base_type(sym)->type == SYM_ARRAY) {
1656 if (sym->initializer && sym->initializer->type == EXPR_INITIALIZER) {
1657 fake_element_assigns(sym, call_global_assign_hooks);
1658 } else if (sym->initializer) {
1659 symbol = symbol_expression(sym);
1660 assign = assign_expression(symbol, '=', sym->initializer);
1661 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1662 } else {
1663 fake_element_assigns_helper(symbol_expression(sym), NULL, call_global_assign_hooks);
1664 }
1665 } else if (get_real_base_type(sym)->type == SYM_STRUCT) {
1666 if (sym->initializer && sym->initializer->type == EXPR_INITIALIZER) {
1667 fake_member_assigns(sym, call_global_assign_hooks);
1668 } else if (sym->initializer) {
1669 symbol = symbol_expression(sym);
1670 assign = assign_expression(symbol, '=', sym->initializer);
1671 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1672 } else {
1673 fake_member_assigns_helper(symbol_expression(sym), NULL, call_global_assign_hooks);
1674 }
1675 } else {
1676 symbol = symbol_expression(sym);
1677 if (sym->initializer) {
1678 assign = assign_expression(symbol, '=', sym->initializer);
1679 __split_expr(assign);
1680 } else {
1681 assign = assign_expression(symbol, '=', zero_expr());
1682 }
1683 __pass_to_client(assign, GLOBAL_ASSIGNMENT_HOOK);
1684 }
1685 }
1686
1687 static void start_function_definition(struct symbol *sym)
1688 {
1689 __in_function_def = 1;
1690 __pass_to_client(sym, FUNC_DEF_HOOK);
1691 __in_function_def = 0;
1692 __pass_to_client(sym, AFTER_DEF_HOOK);
1693
1694 }
1695
1696 void add_function_data(unsigned long *fn_data)
1697 {
1698 __add_ptr_list(&fn_data_list, fn_data);
1699 }
1700
1701 static void clear_function_data(void)
1702 {
1703 unsigned long *tmp;
1704
1705 FOR_EACH_PTR(fn_data_list, tmp) {
1706 *tmp = 0;
1707 } END_FOR_EACH_PTR(tmp);
1708 }
1709
1710 static void split_function(struct symbol *sym)
1711 {
1712 struct symbol *base_type = get_base_type(sym);
1713 struct timeval stop;
1714
1715 if (!base_type->stmt && !base_type->inline_stmt)
1716 return;
1717
1718 gettimeofday(&outer_fn_start_time, NULL);
1719 gettimeofday(&fn_start_time, NULL);
1720 cur_func_sym = sym;
1721 if (sym->ident)
1722 cur_func = sym->ident->name;
1723 set_position(sym->pos);
1724 clear_function_data();
1725 loop_count = 0;
1726 last_goto_statement_handled = 0;
1727 sm_debug("new function: %s\n", cur_func);
1728 __stree_id = 0;
1729 if (option_two_passes) {
1730 __unnullify_path();
1731 loop_num = 0;
1732 final_pass = 0;
1733 start_function_definition(sym);
1734 __split_stmt(base_type->stmt);
1735 __split_stmt(base_type->inline_stmt);
1736 nullify_path();
1737 }
1738 __unnullify_path();
1739 loop_num = 0;
1740 final_pass = 1;
1741 start_function_definition(sym);
1742 __split_stmt(base_type->stmt);
1743 __split_stmt(base_type->inline_stmt);
1744 __pass_to_client(sym, END_FUNC_HOOK);
1745 if (need_delayed_scope_hooks())
1746 __call_scope_hooks();
1747 __pass_to_client(sym, AFTER_FUNC_HOOK);
1748
1749 clear_all_states();
1750
1751 gettimeofday(&stop, NULL);
1752 if (option_time && stop.tv_sec - fn_start_time.tv_sec > 2) {
1753 final_pass++;
1754 sm_msg("func_time: %lu", stop.tv_sec - fn_start_time.tv_sec);
1755 final_pass--;
1756 }
1757 cur_func_sym = NULL;
1758 cur_func = NULL;
1759 free_data_info_allocs();
1760 free_expression_stack(&switch_expr_stack);
1761 __free_ptr_list((struct ptr_list **)&big_statement_stack);
1762 __bail_on_rest_of_function = 0;
1763 }
1764
1765 static void save_flow_state(void)
1766 {
1767 unsigned long *tmp;
1768
1769 __add_ptr_list(&backup, INT_PTR(loop_num << 2));
1770 __add_ptr_list(&backup, INT_PTR(loop_count << 2));
1771 __add_ptr_list(&backup, INT_PTR(final_pass << 2));
1772
1773 __add_ptr_list(&backup, big_statement_stack);
1774 __add_ptr_list(&backup, big_expression_stack);
1775 __add_ptr_list(&backup, big_condition_stack);
1776 __add_ptr_list(&backup, switch_expr_stack);
1777
1778 __add_ptr_list(&backup, cur_func_sym);
1779
1780 __add_ptr_list(&backup, __prev_stmt);
1781 __add_ptr_list(&backup, __cur_stmt);
1782 __add_ptr_list(&backup, __next_stmt);
1783
1784 FOR_EACH_PTR(fn_data_list, tmp) {
1785 __add_ptr_list(&backup, (void *)*tmp);
1786 } END_FOR_EACH_PTR(tmp);
1787 }
1788
1789 static void *pop_backup(void)
1790 {
1791 void *ret;
1792
1793 ret = last_ptr_list(backup);
1794 delete_ptr_list_last(&backup);
1795 return ret;
1796 }
1797
1798 static void restore_flow_state(void)
1799 {
1800 unsigned long *tmp;
1801
1802 FOR_EACH_PTR_REVERSE(fn_data_list, tmp) {
1803 *tmp = (unsigned long)pop_backup();
1804 } END_FOR_EACH_PTR_REVERSE(tmp);
1805
1806 __next_stmt = pop_backup();
1807 __cur_stmt = pop_backup();
1808 __prev_stmt = pop_backup();
1809
1810 cur_func_sym = pop_backup();
1811 switch_expr_stack = pop_backup();
1812 big_condition_stack = pop_backup();
1813 big_expression_stack = pop_backup();
1814 big_statement_stack = pop_backup();
1815 final_pass = PTR_INT(pop_backup()) >> 2;
1816 loop_count = PTR_INT(pop_backup()) >> 2;
1817 loop_num = PTR_INT(pop_backup()) >> 2;
1818 }
1819
1820 static void parse_inline(struct expression *call)
1821 {
1822 struct symbol *base_type;
1823 char *cur_func_bak = cur_func; /* not aligned correctly for backup */
1824 struct timeval time_backup = fn_start_time;
1825 struct expression *orig_inline = __inline_fn;
1826 int orig_budget;
1827
1828 if (out_of_memory() || taking_too_long())
1829 return;
1830
1831 save_flow_state();
1832
1833 __pass_to_client(call, INLINE_FN_START);
1834 final_pass = 0; /* don't print anything */
1835 __inline_fn = call;
1836 orig_budget = inline_budget;
1837 inline_budget = inline_budget - 5;
1838
1839 base_type = get_base_type(call->fn->symbol);
1840 cur_func_sym = call->fn->symbol;
1841 if (call->fn->symbol->ident)
1842 cur_func = call->fn->symbol->ident->name;
1843 else
1844 cur_func = NULL;
1845 set_position(call->fn->symbol->pos);
1846
1847 save_all_states();
1848 big_statement_stack = NULL;
1849 big_expression_stack = NULL;
1850 big_condition_stack = NULL;
1851 switch_expr_stack = NULL;
1852
1853 sm_debug("inline function: %s\n", cur_func);
1854 __unnullify_path();
1855 clear_function_data();
1856 loop_num = 0;
1857 loop_count = 0;
1858 start_function_definition(call->fn->symbol);
1859 __split_stmt(base_type->stmt);
1860 __split_stmt(base_type->inline_stmt);
1861 __pass_to_client(call->fn->symbol, END_FUNC_HOOK);
1862 __pass_to_client(call->fn->symbol, AFTER_FUNC_HOOK);
1863
1864 free_expression_stack(&switch_expr_stack);
1865 __free_ptr_list((struct ptr_list **)&big_statement_stack);
1866 nullify_path();
1867 free_goto_stack();
1868
1869 restore_flow_state();
1870 fn_start_time = time_backup;
1871 cur_func = cur_func_bak;
1872
1873 restore_all_states();
1874 set_position(call->pos);
1875 __inline_fn = orig_inline;
1876 inline_budget = orig_budget;
1877 __pass_to_client(call, INLINE_FN_END);
1878 }
1879
1880 static struct symbol_list *inlines_called;
1881 static void add_inline_function(struct symbol *sym)
1882 {
1883 static struct symbol_list *already_added;
1884 struct symbol *tmp;
1885
1886 FOR_EACH_PTR(already_added, tmp) {
1887 if (tmp == sym)
1888 return;
1889 } END_FOR_EACH_PTR(tmp);
1890
1891 add_ptr_list(&already_added, sym);
1892 add_ptr_list(&inlines_called, sym);
1893 }
1894
1895 static void process_inlines(void)
1896 {
1897 struct symbol *tmp;
1898
1899 FOR_EACH_PTR(inlines_called, tmp) {
1900 split_function(tmp);
1901 } END_FOR_EACH_PTR(tmp);
1902 free_ptr_list(&inlines_called);
1903 }
1904
1905 static struct symbol *get_last_scoped_symbol(struct symbol_list *big_list, int use_static)
1906 {
1907 struct symbol *sym;
1908
1909 FOR_EACH_PTR_REVERSE(big_list, sym) {
1910 if (!sym->scope)
1911 continue;
1912 if (use_static && sym->ctype.modifiers & MOD_STATIC)
1913 return sym;
1914 if (!use_static && !(sym->ctype.modifiers & MOD_STATIC))
1915 return sym;
1916 } END_FOR_EACH_PTR_REVERSE(sym);
1917
1918 return NULL;
1919 }
1920
1921 static bool interesting_function(struct symbol *sym)
1922 {
1923 static int prev_stream = -1;
1924 static bool prev_answer;
1925 const char *filename;
1926 int len;
1927
1928 if (!(sym->ctype.modifiers & MOD_INLINE))
1929 return true;
1930
1931 if (sym->pos.stream == prev_stream)
1932 return prev_answer;
1933
1934 prev_stream = sym->pos.stream;
1935 prev_answer = false;
1936
1937 filename = stream_name(sym->pos.stream);
1938 len = strlen(filename);
1939 if (len > 0 && filename[len - 1] == 'c')
1940 prev_answer = true;
1941 return prev_answer;
1942 }
1943
1944 static void split_inlines_in_scope(struct symbol *sym)
1945 {
1946 struct symbol *base;
1947 struct symbol_list *scope_list;
1948 int stream;
1949
1950 scope_list = sym->scope->symbols;
1951 stream = sym->pos.stream;
1952
1953 /* find the last static symbol in the file */
1954 FOR_EACH_PTR_REVERSE(scope_list, sym) {
1955 if (sym->pos.stream != stream)
1956 continue;
1957 if (sym->type != SYM_NODE)
1958 continue;
1959 base = get_base_type(sym);
1960 if (!base)
1961 continue;
1962 if (base->type != SYM_FN)
1963 continue;
1964 if (!base->inline_stmt)
1965 continue;
1966 if (!interesting_function(sym))
1967 continue;
1968 add_inline_function(sym);
1969 } END_FOR_EACH_PTR_REVERSE(sym);
1970
1971 process_inlines();
1972 }
1973
1974 static void split_inlines(struct symbol_list *sym_list)
1975 {
1976 struct symbol *sym;
1977
1978 sym = get_last_scoped_symbol(sym_list, 0);
1979 if (sym)
1980 split_inlines_in_scope(sym);
1981 sym = get_last_scoped_symbol(sym_list, 1);
1982 if (sym)
1983 split_inlines_in_scope(sym);
1984 }
1985
1986 static struct stree *clone_estates_perm(struct stree *orig)
1987 {
1988 struct stree *ret = NULL;
1989 struct sm_state *tmp;
1990
1991 FOR_EACH_SM(orig, tmp) {
1992 set_state_stree_perm(&ret, tmp->owner, tmp->name, tmp->sym, clone_estate_perm(tmp->state));
1993 } END_FOR_EACH_SM(tmp);
1994
1995 return ret;
1996 }
1997
1998 struct position last_pos;
1999 static void split_c_file_functions(struct symbol_list *sym_list)
2000 {
2001 struct symbol *sym;
2002
2003 __unnullify_path();
2004 FOR_EACH_PTR(sym_list, sym) {
2005 set_position(sym->pos);
2006 if (sym->type != SYM_NODE || get_base_type(sym)->type != SYM_FN) {
2007 __pass_to_client(sym, BASE_HOOK);
2008 fake_global_assign(sym);
2009 }
2010 } END_FOR_EACH_PTR(sym);
2011 global_states = clone_estates_perm(get_all_states_stree(SMATCH_EXTRA));
2012 nullify_path();
2013
2014 FOR_EACH_PTR(sym_list, sym) {
2015 set_position(sym->pos);
2016 last_pos = sym->pos;
2017 if (!interesting_function(sym))
2018 continue;
2019 if (sym->type == SYM_NODE && get_base_type(sym)->type == SYM_FN) {
2020 split_function(sym);
2021 process_inlines();
2022 }
2023 last_pos = sym->pos;
2024 } END_FOR_EACH_PTR(sym);
2025 split_inlines(sym_list);
2026 __pass_to_client(sym_list, END_FILE_HOOK);
2027 }
2028
2029 static int final_before_fake;
2030 void init_fake_env(void)
2031 {
2032 if (!in_fake_env)
2033 final_before_fake = final_pass;
2034 in_fake_env++;
2035 __push_fake_cur_stree();
2036 final_pass = 0;
2037 }
2038
2039 void end_fake_env(void)
2040 {
2041 __pop_fake_cur_stree();
2042 in_fake_env--;
2043 if (!in_fake_env)
2044 final_pass = final_before_fake;
2045 }
2046
2047 static void open_output_files(char *base_file)
2048 {
2049 char buf[256];
2050
2051 snprintf(buf, sizeof(buf), "%s.smatch", base_file);
2052 sm_outfd = fopen(buf, "w");
2053 if (!sm_outfd)
2054 sm_fatal("Cannot open %s", buf);
2055
2056 if (!option_info)
2057 return;
2058
2059 snprintf(buf, sizeof(buf), "%s.smatch.sql", base_file);
2060 sql_outfd = fopen(buf, "w");
2061 if (!sql_outfd)
2062 sm_fatal("Error: Cannot open %s", buf);
2063
2064 snprintf(buf, sizeof(buf), "%s.smatch.caller_info", base_file);
2065 caller_info_fd = fopen(buf, "w");
2066 if (!caller_info_fd)
2067 sm_fatal("Error: Cannot open %s", buf);
2068 }
2069
2070 void smatch(struct string_list *filelist)
2071 {
2072 struct symbol_list *sym_list;
2073 struct timeval stop, start;
2074 char *path;
2075 int len;
2076
2077 gettimeofday(&start, NULL);
2078
2079 FOR_EACH_PTR_NOTAG(filelist, base_file) {
2080 path = getcwd(NULL, 0);
2081 free(full_base_file);
2082 if (path) {
2083 len = strlen(path) + 1 + strlen(base_file) + 1;
2084 full_base_file = malloc(len);
2085 snprintf(full_base_file, len, "%s/%s", path, base_file);
2086 } else {
2087 full_base_file = alloc_string(base_file);
2088 }
2089 if (option_file_output)
2090 open_output_files(base_file);
2091 sym_list = sparse_keep_tokens(base_file);
2092 split_c_file_functions(sym_list);
2093 } END_FOR_EACH_PTR_NOTAG(base_file);
2094
2095 gettimeofday(&stop, NULL);
2096
2097 set_position(last_pos);
2098 final_pass = 1;
2099 if (option_time)
2100 sm_msg("time: %lu", stop.tv_sec - start.tv_sec);
2101 if (option_mem)
2102 sm_msg("mem: %luKb", get_max_memory());
2103 }
Static analysis for C