1 /*
2 * Copyright (C) 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 /*
19 * Imagine we have this code:
20 * foo = 1;
21 * if (bar)
22 * foo = 99;
23 * else
24 * frob();
25 * // <-- point #1
26 * if (foo == 99) // <-- point #2
27 * bar->baz; // <-- point #3
28 *
29 *
30 * At point #3 bar is non null and can be dereferenced.
31 *
32 * It's smatch_implied.c which sets bar to non null at point #2.
33 *
34 * At point #1 merge_slist() stores the list of states from both
35 * the true and false paths. On the true path foo == 99 and on
380
381 FOR_EACH_PTR(keep_gates, tmp) {
382 if (is_merged(tmp))
383 continue;
384 old = get_sm_state_stree(tmp->pool, sm->owner, sm->name, sm->sym);
385 if (!old)
386 continue;
387 if (old == sm)
388 return 1;
389 } END_FOR_EACH_PTR(tmp);
390 return 0;
391 }
392
393 static int taking_too_long(void)
394 {
395 static void *printed;
396
397 if (out_of_memory())
398 return 1;
399
400 if (time_parsing_function() < 60)
401 return 0;
402
403 if (!__inline_fn && printed != cur_func_sym) {
404 if (!is_skipped_function())
405 sm_perror("turning off implications after 60 seconds");
406 printed = cur_func_sym;
407 }
408 return 1;
409 }
410
411 /*
412 * NOTE: If a state is in both the keep stack and the remove stack then that is
413 * a bug. Only add states which are definitely true or definitely false. If
414 * you have a leaf state that could be both true and false, then create a fake
415 * split history where one side is true and one side is false. Otherwise, if
416 * you can't do that, then don't add it to either list.
417 */
418 struct sm_state *filter_pools(struct sm_state *sm,
419 const struct state_list *remove_stack,
420 const struct state_list *keep_stack,
576
577 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
578
579 DIMPLIED("filtering true stack.\n");
580 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
581 DIMPLIED("filtering false stack.\n");
582 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
583 free_slist(&true_stack);
584 free_slist(&false_stack);
585 if (option_debug_implied || option_debug) {
586 printf("These are the implied states for the true path: (%s %s %s)\n",
587 sm->name, show_special(comparison), show_rl(rl));
588 __print_stree(*true_states);
589 printf("These are the implied states for the false path: (%s %s %s)\n",
590 sm->name, show_special(comparison), show_rl(rl));
591 __print_stree(*false_states);
592 }
593
594 gettimeofday(&time_after, NULL);
595 sec = time_after.tv_sec - time_before.tv_sec;
596 if (sec > 20) {
597 sm->nr_children = 4000;
598 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
599 }
600 }
601
602 static struct expression *get_last_expr(struct statement *stmt)
603 {
604 struct statement *last;
605
606 last = last_ptr_list((struct ptr_list *)stmt->stmts);
607 if (last->type == STMT_EXPRESSION)
608 return last->expression;
609
610 if (last->type == STMT_LABEL) {
611 if (last->label_statement &&
612 last->label_statement->type == STMT_EXPRESSION)
613 return last->label_statement->expression;
614 }
615
616 return NULL;
|
1 /*
2 * Copyright (C) 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 * Copyright 2019 Joyent, Inc.
18 */
19
20 /*
21 * Imagine we have this code:
22 * foo = 1;
23 * if (bar)
24 * foo = 99;
25 * else
26 * frob();
27 * // <-- point #1
28 * if (foo == 99) // <-- point #2
29 * bar->baz; // <-- point #3
30 *
31 *
32 * At point #3 bar is non null and can be dereferenced.
33 *
34 * It's smatch_implied.c which sets bar to non null at point #2.
35 *
36 * At point #1 merge_slist() stores the list of states from both
37 * the true and false paths. On the true path foo == 99 and on
382
383 FOR_EACH_PTR(keep_gates, tmp) {
384 if (is_merged(tmp))
385 continue;
386 old = get_sm_state_stree(tmp->pool, sm->owner, sm->name, sm->sym);
387 if (!old)
388 continue;
389 if (old == sm)
390 return 1;
391 } END_FOR_EACH_PTR(tmp);
392 return 0;
393 }
394
395 static int taking_too_long(void)
396 {
397 static void *printed;
398
399 if (out_of_memory())
400 return 1;
401
402 if (time_parsing_function() < option_timeout)
403 return 0;
404
405 if (!__inline_fn && printed != cur_func_sym) {
406 if (!is_skipped_function())
407 sm_perror("turning off implications after 60 seconds");
408 printed = cur_func_sym;
409 }
410 return 1;
411 }
412
413 /*
414 * NOTE: If a state is in both the keep stack and the remove stack then that is
415 * a bug. Only add states which are definitely true or definitely false. If
416 * you have a leaf state that could be both true and false, then create a fake
417 * split history where one side is true and one side is false. Otherwise, if
418 * you can't do that, then don't add it to either list.
419 */
420 struct sm_state *filter_pools(struct sm_state *sm,
421 const struct state_list *remove_stack,
422 const struct state_list *keep_stack,
578
579 separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
580
581 DIMPLIED("filtering true stack.\n");
582 *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
583 DIMPLIED("filtering false stack.\n");
584 *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
585 free_slist(&true_stack);
586 free_slist(&false_stack);
587 if (option_debug_implied || option_debug) {
588 printf("These are the implied states for the true path: (%s %s %s)\n",
589 sm->name, show_special(comparison), show_rl(rl));
590 __print_stree(*true_states);
591 printf("These are the implied states for the false path: (%s %s %s)\n",
592 sm->name, show_special(comparison), show_rl(rl));
593 __print_stree(*false_states);
594 }
595
596 gettimeofday(&time_after, NULL);
597 sec = time_after.tv_sec - time_before.tv_sec;
598 if (sec > option_timeout) {
599 sm->nr_children = 4000;
600 sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
601 }
602 }
603
604 static struct expression *get_last_expr(struct statement *stmt)
605 {
606 struct statement *last;
607
608 last = last_ptr_list((struct ptr_list *)stmt->stmts);
609 if (last->type == STMT_EXPRESSION)
610 return last->expression;
611
612 if (last->type == STMT_LABEL) {
613 if (last->label_statement &&
614 last->label_statement->type == STMT_EXPRESSION)
615 return last->label_statement->expression;
616 }
617
618 return NULL;
|