2 * Copyright (C) 2008,2009 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
21 #include "smatch_slist.h"
25 ALLOCATOR(smatch_state
, "smatch state");
26 ALLOCATOR(sm_state
, "sm state");
27 ALLOCATOR(named_slist
, "named slist");
28 __DO_ALLOCATOR(char, 1, 4, "state names", sname
);
30 static int sm_state_counter
;
32 char *show_sm(struct sm_state
*sm
)
39 pos
= snprintf(buf
, sizeof(buf
), "[%s] '%s' = %s (",
40 check_name(sm
->owner
), sm
->name
, show_state(sm
->state
));
41 if (pos
> sizeof(buf
))
45 FOR_EACH_PTR(sm
->possible
, tmp
) {
47 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, ", ");
48 if (pos
> sizeof(buf
))
50 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, "%s",
51 show_state(tmp
->state
));
52 if (pos
> sizeof(buf
))
54 } END_FOR_EACH_PTR(tmp
);
55 snprintf(buf
+ pos
, sizeof(buf
) - pos
, ")");
60 for (i
= 0; i
< 3; i
++)
61 buf
[sizeof(buf
) - 2 - i
] = '.';
65 void __print_slist(struct state_list
*slist
)
69 printf("dumping slist at %d\n", get_lineno());
70 FOR_EACH_PTR(slist
, sm
) {
71 printf("%s\n", show_sm(sm
));
72 } END_FOR_EACH_PTR(sm
);
76 /* NULL states go at the end to simplify merge_slist */
77 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
88 if (a
->owner
> b
->owner
)
90 if (a
->owner
< b
->owner
)
93 ret
= strcmp(a
->name
, b
->name
);
97 if (!b
->sym
&& a
->sym
)
99 if (!a
->sym
&& b
->sym
)
109 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
, int preserve
)
113 ret
= cmp_tracker(a
, b
);
117 /* todo: add hook for smatch_extra.c */
118 if (a
->state
> b
->state
)
120 if (a
->state
< b
->state
)
122 /* This is obviously a massive disgusting hack but we need to preserve
123 * the unmerged states for smatch extra because we use them in
124 * smatch_db.c. Meanwhile if we preserve all the other unmerged states
125 * then it uses a lot of memory and we don't use it. Hence this hack.
127 * Also sometimes even just preserving every possible SMATCH_EXTRA state
128 * takes too much resources so we have to cap that. Capping is probably
129 * not often a problem in real life.
131 if (a
->owner
== SMATCH_EXTRA
&& preserve
) {
134 if (a
->merged
== 1 && b
->merged
== 0)
143 static struct sm_state
*alloc_sm_state(int owner
, const char *name
,
144 struct symbol
*sym
, struct smatch_state
*state
)
146 struct sm_state
*sm_state
= __alloc_sm_state(0);
150 sm_state
->name
= alloc_sname(name
);
151 sm_state
->owner
= owner
;
153 sm_state
->state
= state
;
154 sm_state
->line
= get_lineno();
155 sm_state
->merged
= 0;
156 sm_state
->implied
= 0;
157 sm_state
->pool
= NULL
;
158 sm_state
->left
= NULL
;
159 sm_state
->right
= NULL
;
160 sm_state
->nr_children
= 1;
161 sm_state
->possible
= NULL
;
162 add_ptr_list(&sm_state
->possible
, sm_state
);
166 static struct sm_state
*alloc_state_no_name(int owner
, const char *name
,
168 struct smatch_state
*state
)
170 struct sm_state
*tmp
;
172 tmp
= alloc_sm_state(owner
, NULL
, sym
, state
);
177 int too_many_possible(struct sm_state
*sm
)
179 if (ptr_list_size((struct ptr_list
*)sm
->possible
) >= 100)
184 void add_possible_sm(struct sm_state
*to
, struct sm_state
*new)
186 struct sm_state
*tmp
;
189 if (too_many_possible(to
))
192 FOR_EACH_PTR(to
->possible
, tmp
) {
193 if (cmp_sm_states(tmp
, new, preserve
) < 0)
195 else if (cmp_sm_states(tmp
, new, preserve
) == 0) {
198 INSERT_CURRENT(new, tmp
);
201 } END_FOR_EACH_PTR(tmp
);
202 add_ptr_list(&to
->possible
, new);
205 static void copy_possibles(struct sm_state
*to
, struct sm_state
*from
)
207 struct sm_state
*tmp
;
209 FOR_EACH_PTR(from
->possible
, tmp
) {
210 add_possible_sm(to
, tmp
);
211 } END_FOR_EACH_PTR(tmp
);
214 char *alloc_sname(const char *str
)
220 tmp
= __alloc_sname(strlen(str
) + 1);
228 * I decided to use 50M here based on trial and error.
229 * It works out OK for the kernel and so it should work
230 * for most other projects as well.
232 if (sm_state_counter
* sizeof(struct sm_state
) >= 50000000)
237 int low_on_memory(void)
239 if (sm_state_counter
* sizeof(struct sm_state
) >= 25000000)
244 static void free_sm_state(struct sm_state
*sm
)
246 free_slist(&sm
->possible
);
248 * fixme. Free the actual state.
249 * Right now we leave it until the end of the function
250 * because we don't want to double free it.
251 * Use the freelist to not double free things
255 static void free_all_sm_states(struct allocation_blob
*blob
)
257 unsigned int size
= sizeof(struct sm_state
);
258 unsigned int offset
= 0;
260 while (offset
< blob
->offset
) {
261 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
266 /* At the end of every function we free all the sm_states */
267 void free_every_single_sm_state(void)
269 struct allocator_struct
*desc
= &sm_state_allocator
;
270 struct allocation_blob
*blob
= desc
->blobs
;
273 desc
->allocations
= 0;
274 desc
->total_bytes
= 0;
275 desc
->useful_bytes
= 0;
276 desc
->freelist
= NULL
;
278 struct allocation_blob
*next
= blob
->next
;
279 free_all_sm_states(blob
);
280 blob_free(blob
, desc
->chunking
);
284 clear_smatch_state_alloc();
286 sm_state_counter
= 0;
289 struct sm_state
*clone_sm(struct sm_state
*s
)
291 struct sm_state
*ret
;
293 ret
= alloc_state_no_name(s
->owner
, s
->name
, s
->sym
, s
->state
);
294 ret
->merged
= s
->merged
;
295 ret
->implied
= s
->implied
;
297 /* clone_sm() doesn't copy the pools. Each state needs to have
299 ret
->possible
= clone_slist(s
->possible
);
301 ret
->right
= s
->right
;
302 ret
->nr_children
= s
->nr_children
;
306 int is_merged(struct sm_state
*sm
)
311 int is_implied(struct sm_state
*sm
)
316 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
318 struct sm_state
*tmp
;
320 FOR_EACH_PTR(slist
, tmp
) {
321 if (tmp
->state
== state
)
323 } END_FOR_EACH_PTR(tmp
);
327 static void check_order(struct state_list
*slist
)
331 struct sm_state
*last
= NULL
;
334 FOR_EACH_PTR(slist
, sm
) {
335 if (last
&& cmp_tracker(sm
, last
) <= 0) {
336 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
337 "%s vs %s\n", last
->owner
, sm
->owner
,
338 last
->sym
, sm
->sym
, last
->name
, sm
->name
);
342 } END_FOR_EACH_PTR(sm
);
349 struct state_list
*clone_slist(struct state_list
*from_slist
)
352 struct state_list
*to_slist
= NULL
;
354 FOR_EACH_PTR(from_slist
, sm
) {
355 add_ptr_list(&to_slist
, sm
);
356 } END_FOR_EACH_PTR(sm
);
360 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
362 struct state_list
*slist
;
363 struct state_list_stack
*to_stack
= NULL
;
365 FOR_EACH_PTR(from_stack
, slist
) {
366 push_slist(&to_stack
, slist
);
367 } END_FOR_EACH_PTR(slist
);
371 struct smatch_state
*merge_states(int owner
, const char *name
,
373 struct smatch_state
*state1
,
374 struct smatch_state
*state2
)
376 struct smatch_state
*ret
;
378 if (state1
== state2
)
380 else if (__has_merge_function(owner
))
381 ret
= __client_merge_function(owner
, state1
, state2
);
382 else if (!state1
|| !state2
)
389 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
391 struct smatch_state
*s
;
392 struct sm_state
*result
;
396 s
= merge_states(one
->owner
, one
->name
, one
->sym
, one
->state
, two
->state
);
397 result
= alloc_state_no_name(one
->owner
, one
->name
, one
->sym
, s
);
401 result
->nr_children
= one
->nr_children
+ two
->nr_children
;
402 copy_possibles(result
, one
);
403 copy_possibles(result
, two
);
406 strcmp(check_name(one
->owner
), option_debug_check
) == 0) {
407 struct sm_state
*tmp
;
410 printf("%d merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
411 get_lineno(), check_name(one
->owner
), one
->name
,
412 show_state(one
->state
), one
->line
,
413 show_state(two
->state
), two
->line
,
416 FOR_EACH_PTR(result
->possible
, tmp
) {
419 printf("%s", show_state(tmp
->state
));
420 } END_FOR_EACH_PTR(tmp
);
427 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, int owner
, const char *name
,
435 FOR_EACH_PTR(slist
, sm
) {
436 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
))
438 } END_FOR_EACH_PTR(sm
);
442 struct smatch_state
*get_state_slist(struct state_list
*slist
,
443 int owner
, const char *name
,
448 sm
= get_sm_state_slist(slist
, owner
, name
, sym
);
454 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
456 struct sm_state
*tmp
;
458 FOR_EACH_PTR(*slist
, tmp
) {
459 if (cmp_tracker(tmp
, new) < 0)
461 else if (cmp_tracker(tmp
, new) == 0) {
462 REPLACE_CURRENT_PTR(tmp
, new);
465 INSERT_CURRENT(new, tmp
);
468 } END_FOR_EACH_PTR(tmp
);
469 add_ptr_list(slist
, new);
472 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
475 struct state_list
*slist
;
477 slist
= pop_slist(stack
);
478 overwrite_sm_state(&slist
, sm
);
479 push_slist(stack
, slist
);
482 struct sm_state
*set_state_slist(struct state_list
**slist
, int owner
, const char *name
,
483 struct symbol
*sym
, struct smatch_state
*state
)
485 struct sm_state
*tmp
;
486 struct sm_state
*new = alloc_sm_state(owner
, name
, sym
, state
);
488 FOR_EACH_PTR(*slist
, tmp
) {
489 if (cmp_tracker(tmp
, new) < 0)
491 else if (cmp_tracker(tmp
, new) == 0) {
492 REPLACE_CURRENT_PTR(tmp
, new);
495 INSERT_CURRENT(new, tmp
);
498 } END_FOR_EACH_PTR(tmp
);
499 add_ptr_list(slist
, new);
503 void delete_state_slist(struct state_list
**slist
, int owner
, const char *name
,
508 FOR_EACH_PTR(*slist
, sm
) {
509 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
)) {
510 DELETE_CURRENT_PTR(sm
);
513 } END_FOR_EACH_PTR(sm
);
516 void delete_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
519 struct state_list
*slist
;
521 slist
= pop_slist(stack
);
522 delete_state_slist(&slist
, owner
, name
, sym
);
523 push_slist(stack
, slist
);
526 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
528 add_ptr_list(list_stack
, slist
);
531 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
533 struct state_list
*slist
;
535 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
536 delete_ptr_list_last((struct ptr_list
**)list_stack
);
540 void free_slist(struct state_list
**slist
)
542 __free_ptr_list((struct ptr_list
**)slist
);
545 void free_stack(struct state_list_stack
**stack
)
547 __free_ptr_list((struct ptr_list
**)stack
);
550 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
552 struct state_list
*slist
;
554 FOR_EACH_PTR(*slist_stack
, slist
) {
556 } END_FOR_EACH_PTR(slist
);
557 free_stack(slist_stack
);
561 * set_state_stack() sets the state for the top slist on the stack.
563 struct sm_state
*set_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
564 struct symbol
*sym
, struct smatch_state
*state
)
566 struct state_list
*slist
;
569 slist
= pop_slist(stack
);
570 sm
= set_state_slist(&slist
, owner
, name
, sym
, state
);
571 push_slist(stack
, slist
);
577 * get_sm_state_stack() gets the state for the top slist on the stack.
579 struct sm_state
*get_sm_state_stack(struct state_list_stack
*stack
,
580 int owner
, const char *name
,
583 struct state_list
*slist
;
584 struct sm_state
*ret
;
586 slist
= pop_slist(&stack
);
587 ret
= get_sm_state_slist(slist
, owner
, name
, sym
);
588 push_slist(&stack
, slist
);
592 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
593 int owner
, const char *name
,
598 sm
= get_sm_state_stack(stack
, owner
, name
, sym
);
604 static void match_states(struct state_list
**one
, struct state_list
**two
)
606 struct sm_state
*one_sm
;
607 struct sm_state
*two_sm
;
608 struct sm_state
*tmp
;
609 struct smatch_state
*tmp_state
;
610 struct state_list
*add_to_one
= NULL
;
611 struct state_list
*add_to_two
= NULL
;
613 PREPARE_PTR_LIST(*one
, one_sm
);
614 PREPARE_PTR_LIST(*two
, two_sm
);
616 if (!one_sm
&& !two_sm
)
618 if (cmp_tracker(one_sm
, two_sm
) < 0) {
619 __set_fake_cur_slist_fast(*two
);
620 tmp_state
= __client_unmatched_state_function(one_sm
);
621 __pop_fake_cur_slist_fast();
622 tmp
= alloc_state_no_name(one_sm
->owner
, one_sm
->name
,
623 one_sm
->sym
, tmp_state
);
624 add_ptr_list(&add_to_two
, tmp
);
625 NEXT_PTR_LIST(one_sm
);
626 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
627 NEXT_PTR_LIST(one_sm
);
628 NEXT_PTR_LIST(two_sm
);
630 __set_fake_cur_slist_fast(*one
);
631 tmp_state
= __client_unmatched_state_function(two_sm
);
632 __pop_fake_cur_slist_fast();
633 tmp
= alloc_state_no_name(two_sm
->owner
, two_sm
->name
,
634 two_sm
->sym
, tmp_state
);
635 add_ptr_list(&add_to_one
, tmp
);
636 NEXT_PTR_LIST(two_sm
);
639 FINISH_PTR_LIST(two_sm
);
640 FINISH_PTR_LIST(one_sm
);
642 overwrite_slist(add_to_one
, one
);
643 overwrite_slist(add_to_two
, two
);
646 static void clone_pool_havers(struct state_list
*slist
)
649 struct sm_state
*new;
651 FOR_EACH_PTR(slist
, sm
) {
654 REPLACE_CURRENT_PTR(sm
, new);
656 } END_FOR_EACH_PTR(sm
);
661 * Sets the first state to the slist_id.
663 static void set_slist_id(struct state_list
*slist
)
665 struct smatch_state
*state
;
666 struct sm_state
*tmp
, *new;
668 state
= alloc_state_num(++__slist_id
);
669 new = alloc_sm_state(-1, "unnull_path", NULL
, state
);
671 FOR_EACH_PTR(slist
, tmp
) {
672 if (tmp
->owner
!= (unsigned short)-1)
674 REPLACE_CURRENT_PTR(tmp
, new);
676 } END_FOR_EACH_PTR(tmp
);
679 int get_slist_id(struct state_list
*slist
)
681 struct sm_state
*tmp
;
683 FOR_EACH_PTR(slist
, tmp
) {
684 if (tmp
->owner
!= (unsigned short)-1)
686 return PTR_INT(tmp
->state
->data
);
687 } END_FOR_EACH_PTR(tmp
);
692 * merge_slist() is called whenever paths merge, such as after
693 * an if statement. It takes the two slists and creates one.
695 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
697 struct sm_state
*one_sm
, *two_sm
, *tmp
;
698 struct state_list
*results
= NULL
;
699 struct state_list
*implied_one
= NULL
;
700 struct state_list
*implied_two
= NULL
;
708 /* merging a null and nonnull path gives you only the nonnull path */
713 *to
= clone_slist(slist
);
717 implied_one
= clone_slist(*to
);
718 implied_two
= clone_slist(slist
);
720 match_states(&implied_one
, &implied_two
);
722 clone_pool_havers(implied_one
);
723 clone_pool_havers(implied_two
);
725 set_slist_id(implied_one
);
726 set_slist_id(implied_two
);
728 PREPARE_PTR_LIST(implied_one
, one_sm
);
729 PREPARE_PTR_LIST(implied_two
, two_sm
);
731 if (!one_sm
&& !two_sm
)
733 if (cmp_tracker(one_sm
, two_sm
) < 0) {
734 sm_msg("error: Internal smatch error.");
735 NEXT_PTR_LIST(one_sm
);
736 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
737 if (one_sm
!= two_sm
) {
738 one_sm
->pool
= implied_one
;
739 two_sm
->pool
= implied_two
;
742 tmp
= merge_sm_states(one_sm
, two_sm
);
743 add_ptr_list(&results
, tmp
);
744 NEXT_PTR_LIST(one_sm
);
745 NEXT_PTR_LIST(two_sm
);
747 sm_msg("error: Internal smatch error.");
748 NEXT_PTR_LIST(two_sm
);
751 FINISH_PTR_LIST(two_sm
);
752 FINISH_PTR_LIST(one_sm
);
759 * filter_slist() removes any sm states "slist" holds in common with "filter"
761 void filter_slist(struct state_list
**slist
, struct state_list
*filter
)
763 struct sm_state
*one_sm
, *two_sm
;
764 struct state_list
*results
= NULL
;
766 PREPARE_PTR_LIST(*slist
, one_sm
);
767 PREPARE_PTR_LIST(filter
, two_sm
);
769 if (!one_sm
&& !two_sm
)
771 if (cmp_tracker(one_sm
, two_sm
) < 0) {
772 add_ptr_list(&results
, one_sm
);
773 NEXT_PTR_LIST(one_sm
);
774 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
775 if (one_sm
!= two_sm
)
776 add_ptr_list(&results
, one_sm
);
777 NEXT_PTR_LIST(one_sm
);
778 NEXT_PTR_LIST(two_sm
);
780 NEXT_PTR_LIST(two_sm
);
783 FINISH_PTR_LIST(two_sm
);
784 FINISH_PTR_LIST(one_sm
);
791 * and_slist_stack() pops the top two slists, overwriting the one with
792 * the other and pushing it back on the stack.
794 void and_slist_stack(struct state_list_stack
**slist_stack
)
796 struct sm_state
*tmp
;
797 struct state_list
*right_slist
= pop_slist(slist_stack
);
799 FOR_EACH_PTR(right_slist
, tmp
) {
800 overwrite_sm_state_stack(slist_stack
, tmp
);
801 } END_FOR_EACH_PTR(tmp
);
802 free_slist(&right_slist
);
806 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
807 * It pops the two slists from the top of the stack and merges them
808 * together in a way that preserves the things they have in common
809 * but creates a merged state for most of the rest.
810 * You could have code that had: if (foo || foo) { foo->baz;
811 * It's this function which ensures smatch does the right thing.
813 void or_slist_stack(struct state_list_stack
**pre_conds
,
814 struct state_list
*cur_slist
,
815 struct state_list_stack
**slist_stack
)
817 struct state_list
*new;
818 struct state_list
*old
;
819 struct state_list
*pre_slist
;
820 struct state_list
*res
;
821 struct state_list
*tmp_slist
;
823 new = pop_slist(slist_stack
);
824 old
= pop_slist(slist_stack
);
826 pre_slist
= pop_slist(pre_conds
);
827 push_slist(pre_conds
, clone_slist(pre_slist
));
829 res
= clone_slist(pre_slist
);
830 overwrite_slist(old
, &res
);
832 tmp_slist
= clone_slist(cur_slist
);
833 overwrite_slist(new, &tmp_slist
);
835 merge_slist(&res
, tmp_slist
);
836 filter_slist(&res
, pre_slist
);
838 push_slist(slist_stack
, res
);
839 free_slist(&tmp_slist
);
840 free_slist(&pre_slist
);
846 * get_slist_from_named_stack() is only used for gotos.
848 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
851 struct named_slist
*tmp
;
853 FOR_EACH_PTR(stack
, tmp
) {
854 if (!strcmp(tmp
->name
, name
))
856 } END_FOR_EACH_PTR(tmp
);
860 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
862 struct sm_state
*tmp
;
864 FOR_EACH_PTR(from
, tmp
) {
865 overwrite_sm_state(to
, tmp
);
866 } END_FOR_EACH_PTR(tmp
);