2 * sparse/smatch_slist.c
4 * Copyright (C) 2008,2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
13 #include "smatch_slist.h"
18 ALLOCATOR(sm_state
, "smatch state");
19 ALLOCATOR(named_slist
, "named slist");
21 void __print_slist(struct state_list
*slist
)
23 struct sm_state
*state
;
24 struct sm_state
*poss
;
27 printf("dumping slist at %d\n", get_lineno());
28 FOR_EACH_PTR(slist
, state
) {
29 printf("%d '%s'=%s (", state
->owner
, state
->name
,
30 show_state(state
->state
));
32 FOR_EACH_PTR(state
->possible
, poss
) {
35 printf("%s", show_state(poss
->state
));
36 } END_FOR_EACH_PTR(poss
);
38 } END_FOR_EACH_PTR(state
);
43 /* NULL states go at the end to simplify merge_slist */
44 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
55 if (a
->owner
> b
->owner
)
57 if (a
->owner
< b
->owner
)
60 ret
= strcmp(a
->name
, b
->name
);
64 if (!b
->sym
&& a
->sym
)
66 if (!a
->sym
&& b
->sym
)
76 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
80 ret
= cmp_tracker(a
, b
);
84 /* todo: add hook for smatch_extra.c */
85 if (a
->state
> b
->state
)
87 if (a
->state
< b
->state
)
92 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
96 FOR_EACH_PTR(*slist
, tmp
) {
97 if (cmp_sm_states(tmp
, new) < 0)
99 else if (cmp_sm_states(tmp
, new) == 0) {
102 INSERT_CURRENT(new, tmp
);
105 } END_FOR_EACH_PTR(tmp
);
106 add_ptr_list(slist
, new);
109 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
111 struct sm_state
*tmp
;
112 struct sm_state
*tmp2
;
115 struct smatch_state
*s
;
117 s
= merge_states(sm
->name
, sm
->owner
, sm
->sym
, sm
->state
, NULL
);
118 tmp
= alloc_state(sm
->name
, sm
->owner
, sm
->sym
, s
);
119 add_sm_state_slist(&sm
->possible
, tmp
);
123 FOR_EACH_PTR(new->possible
, tmp
) {
124 tmp2
= alloc_state(tmp
->name
, tmp
->owner
, tmp
->sym
, tmp
->state
);
125 add_sm_state_slist(&sm
->possible
, tmp2
);
126 } END_FOR_EACH_PTR(tmp
);
129 struct sm_state
*alloc_state(const char *name
, int owner
,
130 struct symbol
*sym
, struct smatch_state
*state
)
132 struct sm_state
*sm_state
= __alloc_sm_state(0);
134 sm_state
->name
= alloc_string(name
);
135 sm_state
->owner
= owner
;
137 sm_state
->state
= state
;
138 sm_state
->my_pools
= NULL
;
139 sm_state
->all_pools
= NULL
;
140 sm_state
->possible
= NULL
;
141 add_ptr_list(&sm_state
->possible
, sm_state
);
145 static void free_sm_state(struct sm_state
*sm
)
147 free_string(sm
->name
);
148 free_slist(&sm
->possible
);
149 free_stack(&sm
->my_pools
);
150 free_stack(&sm
->all_pools
);
152 * fixme. Free the actual state.
153 * Right now we leave it until the end of the function
154 * because we don't want to double free it.
155 * Use the freelist to not double free things
159 static void free_all_sm_states(struct allocation_blob
*blob
)
161 unsigned int size
= sizeof(struct sm_state
);
162 unsigned int offset
= 0;
164 while (offset
< blob
->offset
) {
165 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
170 /* At the end of every function we free all the sm_states */
171 void free_every_single_sm_state()
173 struct allocator_struct
*desc
= &sm_state_allocator
;
174 struct allocation_blob
*blob
= desc
->blobs
;
177 desc
->allocations
= 0;
178 desc
->total_bytes
= 0;
179 desc
->useful_bytes
= 0;
180 desc
->freelist
= NULL
;
182 struct allocation_blob
*next
= blob
->next
;
183 free_all_sm_states(blob
);
184 blob_free(blob
, desc
->chunking
);
189 struct sm_state
*clone_state(struct sm_state
*s
)
191 struct sm_state
*ret
;
192 struct sm_state
*poss
;
194 ret
= alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
195 ret
->my_pools
= clone_stack(s
->my_pools
);
196 ret
->all_pools
= clone_stack(s
->all_pools
);
197 FOR_EACH_PTR(s
->possible
, poss
) {
198 add_sm_state_slist(&ret
->possible
, poss
);
199 } END_FOR_EACH_PTR(poss
);
203 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
205 struct sm_state
*tmp
;
207 FOR_EACH_PTR(slist
, tmp
) {
208 if (tmp
->state
== state
)
210 } END_FOR_EACH_PTR(tmp
);
214 static void check_order(struct state_list
*slist
)
217 struct sm_state
*state
;
218 struct sm_state
*last
= NULL
;
221 FOR_EACH_PTR(slist
, state
) {
222 if (last
&& cmp_tracker(state
, last
) <= 0) {
223 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
224 "%s vs %s\n", last
->owner
, state
->owner
,
225 last
->sym
, state
->sym
, last
->name
, state
->name
);
229 } END_FOR_EACH_PTR(state
);
236 static void check_my_pools(struct sm_state
*sm
)
238 struct sm_state
*poss
;
239 struct state_list
*slist
;
241 if (sm
->state
!= &merged
)
244 FOR_EACH_PTR(sm
->possible
, poss
) {
245 if (poss
->state
== &merged
)
247 FOR_EACH_PTR(sm
->my_pools
, slist
) {
248 if (get_state_slist(slist
, sm
->name
, sm
->owner
, sm
->sym
)
251 } END_FOR_EACH_PTR(slist
);
252 printf("%d pool not found for '%s' possible state \"%s\".\n",
253 get_lineno(), sm
->name
, show_state(poss
->state
));
257 } END_FOR_EACH_PTR(poss
);
261 static void sanity_check_pools(struct state_list
*slist
)
264 struct sm_state
*tmp
;
266 FOR_EACH_PTR(slist
, tmp
) {
268 } END_FOR_EACH_PTR(tmp
);
272 struct state_list
*clone_slist(struct state_list
*from_slist
)
274 struct sm_state
*state
;
275 struct sm_state
*tmp
;
276 struct state_list
*to_slist
= NULL
;
278 FOR_EACH_PTR(from_slist
, state
) {
279 tmp
= clone_state(state
);
280 add_ptr_list(&to_slist
, tmp
);
281 } END_FOR_EACH_PTR(state
);
282 check_order(to_slist
);
286 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
288 struct state_list
*slist
;
289 struct state_list_stack
*to_stack
= NULL
;
291 FOR_EACH_PTR(from_stack
, slist
) {
292 push_slist(&to_stack
, slist
);
293 } END_FOR_EACH_PTR(slist
);
297 struct smatch_state
*merge_states(const char *name
, int owner
,
299 struct smatch_state
*state1
,
300 struct smatch_state
*state2
)
302 struct smatch_state
*ret
;
304 if (state1
== state2
)
306 else if (__has_merge_function(owner
))
307 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
308 else if (!state1
|| !state2
)
316 * add_pool() adds a slist to ->pools. If the slist has already been
317 * added earlier then it doesn't get added a second time.
319 static void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
321 struct state_list
*tmp
;
323 FOR_EACH_PTR(*pools
, tmp
) {
326 else if (tmp
== new) {
329 INSERT_CURRENT(new, tmp
);
332 } END_FOR_EACH_PTR(tmp
);
333 add_ptr_list(pools
, new);
336 static void copy_pools(struct sm_state
*to
, struct sm_state
*sm
)
338 struct state_list
*tmp
;
343 FOR_EACH_PTR(sm
->my_pools
, tmp
) {
344 add_pool(&to
->my_pools
, tmp
);
345 } END_FOR_EACH_PTR(tmp
);
347 FOR_EACH_PTR(sm
->all_pools
, tmp
) {
348 add_pool(&to
->all_pools
, tmp
);
349 } END_FOR_EACH_PTR(tmp
);
352 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
354 struct smatch_state
*s
;
355 struct sm_state
*result
;
357 s
= merge_states(one
->name
, one
->owner
, one
->sym
, one
->state
,
358 (two
?two
->state
:NULL
));
359 result
= alloc_state(one
->name
, one
->owner
, one
->sym
, s
);
360 add_possible(result
, one
);
361 add_possible(result
, two
);
362 copy_pools(result
, one
);
363 copy_pools(result
, two
);
366 struct sm_state
*tmp
;
369 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
370 get_lineno(), one
->name
, one
->owner
,
371 show_state(one
->state
), show_state(two
?two
->state
:NULL
),
374 FOR_EACH_PTR(result
->possible
, tmp
) {
378 printf("%s", show_state(tmp
->state
));
379 } END_FOR_EACH_PTR(tmp
);
386 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, const char *name
,
387 int owner
, struct symbol
*sym
)
389 struct sm_state
*state
;
394 FOR_EACH_PTR(slist
, state
) {
395 if (state
->owner
== owner
&& state
->sym
== sym
396 && !strcmp(state
->name
, name
))
398 } END_FOR_EACH_PTR(state
);
402 struct smatch_state
*get_state_slist(struct state_list
*slist
,
403 const char *name
, int owner
,
406 struct sm_state
*state
;
408 state
= get_sm_state_slist(slist
, name
, owner
, sym
);
414 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
416 struct sm_state
*tmp
;
418 FOR_EACH_PTR(*slist
, tmp
) {
419 if (cmp_tracker(tmp
, new) < 0)
421 else if (cmp_tracker(tmp
, new) == 0) {
422 REPLACE_CURRENT_PTR(tmp
, new);
425 INSERT_CURRENT(new, tmp
);
428 } END_FOR_EACH_PTR(tmp
);
429 add_ptr_list(slist
, new);
432 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
433 struct sm_state
*state
)
435 struct state_list
*slist
;
437 slist
= pop_slist(stack
);
438 overwrite_sm_state(&slist
, state
);
439 push_slist(stack
, slist
);
442 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
443 struct symbol
*sym
, struct smatch_state
*state
)
445 struct sm_state
*tmp
;
446 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
448 FOR_EACH_PTR(*slist
, tmp
) {
449 if (cmp_tracker(tmp
, new) < 0)
451 else if (cmp_tracker(tmp
, new) == 0) {
452 REPLACE_CURRENT_PTR(tmp
, new);
455 INSERT_CURRENT(new, tmp
);
458 } END_FOR_EACH_PTR(tmp
);
459 add_ptr_list(slist
, new);
462 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
465 struct sm_state
*state
;
467 FOR_EACH_PTR(*slist
, state
) {
468 if (state
->owner
== owner
&& state
->sym
== sym
469 && !strcmp(state
->name
, name
)){
470 delete_ptr_list_entry((struct ptr_list
**)slist
,
474 } END_FOR_EACH_PTR(state
);
478 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
480 add_ptr_list(list_stack
, slist
);
483 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
485 struct state_list
*slist
;
487 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
488 delete_ptr_list_last((struct ptr_list
**)list_stack
);
492 void free_slist(struct state_list
**slist
)
494 __free_ptr_list((struct ptr_list
**)slist
);
497 void free_stack(struct state_list_stack
**stack
)
499 __free_ptr_list((struct ptr_list
**)stack
);
502 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
504 struct state_list
*slist
;
506 FOR_EACH_PTR(*slist_stack
, slist
) {
508 } END_FOR_EACH_PTR(slist
);
509 free_stack(slist_stack
);
513 * set_state_stack() sets the state for the top slist on the stack.
515 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
516 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
518 struct state_list
*slist
;
520 slist
= pop_slist(stack
);
521 set_state_slist(&slist
, name
, owner
, sym
, state
);
522 push_slist(stack
, slist
);
526 * get_state_stack() gets the state for the top slist on the stack.
528 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
529 const char *name
, int owner
,
532 struct state_list
*slist
;
533 struct smatch_state
*ret
;
535 slist
= pop_slist(&stack
);
536 ret
= get_state_slist(slist
, name
, owner
, sym
);
537 push_slist(&stack
, slist
);
542 * We want to find which states have been modified inside a branch.
543 * If you have 2 &merged states they could be different states really
544 * and maybe one or both were modified. We say it is unchanged if
545 * the ->state pointers are the same and they belong to the same pools.
546 * If they have been modified on both sides of a branch to the same thing,
547 * it's still OK to say they are the same, because that means they won't
548 * belong to any pools.
550 static int is_really_same(struct sm_state
*one
, struct sm_state
*two
)
552 struct state_list
*tmp1
;
553 struct state_list
*tmp2
;
555 if (one
->state
!= two
->state
)
558 PREPARE_PTR_LIST(one
->my_pools
, tmp1
);
559 PREPARE_PTR_LIST(two
->my_pools
, tmp2
);
565 } else if (tmp1
== tmp2
) {
572 FINISH_PTR_LIST(tmp2
);
573 FINISH_PTR_LIST(tmp1
);
577 static void register_implied_pool(struct state_list
*pool
)
581 FOR_EACH_PTR(pool
, sm
) {
583 add_pool(&sm
->my_pools
, pool
);
585 add_pool(&sm
->all_pools
, pool
);
586 } END_FOR_EACH_PTR(sm
);
588 push_slist(&implied_pools
, pool
);
592 * merge_slist() is called whenever paths merge, such as after
593 * an if statement. It takes the two slists and creates one.
595 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
597 struct sm_state
*to_state
, *state
, *tmp
;
598 struct state_list
*results
= NULL
;
599 struct state_list
*implied_to
= NULL
;
600 struct state_list
*implied_from
= NULL
;
604 sanity_check_pools(*to
);
605 sanity_check_pools(slist
);
607 /* merging a null and nonnull path gives you only the nonnull path */
612 *to
= clone_slist(slist
);
616 implied_to
= clone_slist(*to
);
617 implied_from
= clone_slist(slist
);
619 register_implied_pool(implied_to
);
620 register_implied_pool(implied_from
);
622 PREPARE_PTR_LIST(implied_to
, to_state
);
623 PREPARE_PTR_LIST(implied_from
, state
);
625 if (!to_state
&& !state
)
627 if (cmp_tracker(to_state
, state
) < 0) {
628 tmp
= merge_sm_states(to_state
, NULL
);
629 add_ptr_list(&results
, tmp
);
630 NEXT_PTR_LIST(to_state
);
631 } else if (cmp_tracker(to_state
, state
) == 0) {
632 tmp
= merge_sm_states(to_state
, state
);
633 if (!is_really_same(to_state
, state
)) {
634 add_pool(&tmp
->my_pools
, implied_to
);
635 add_pool(&tmp
->my_pools
, implied_from
);
637 add_ptr_list(&results
, tmp
);
638 NEXT_PTR_LIST(to_state
);
639 NEXT_PTR_LIST(state
);
641 tmp
= merge_sm_states(state
, NULL
);
642 add_ptr_list(&results
, tmp
);
643 NEXT_PTR_LIST(state
);
646 FINISH_PTR_LIST(state
);
647 FINISH_PTR_LIST(to_state
);
653 static int pool_in_pools(struct state_list_stack
*pools
,
654 struct state_list
*pool
)
656 struct state_list
*tmp
;
658 FOR_EACH_PTR(pools
, tmp
) {
661 } END_FOR_EACH_PTR(tmp
);
665 struct state_list
*clone_states_in_pool(struct state_list
*pool
,
666 struct state_list
*cur_slist
)
668 struct sm_state
*state
;
669 struct sm_state
*cur_state
;
670 struct sm_state
*tmp
;
671 struct state_list
*to_slist
= NULL
;
673 FOR_EACH_PTR(pool
, state
) {
674 cur_state
= get_sm_state_slist(cur_slist
, state
->name
,
675 state
->owner
, state
->sym
);
678 if (is_really_same(state
, cur_state
))
680 if (pool_in_pools(cur_state
->all_pools
, pool
)) {
681 tmp
= clone_state(state
);
682 add_ptr_list(&to_slist
, tmp
);
684 } END_FOR_EACH_PTR(state
);
685 sanity_check_pools(to_slist
);
690 * merge_implied() takes an implied state and another possibly implied state
691 * from another pool. It checks that the second pool is reachable from
692 * cur_slist then merges the two states and returns the result.
694 struct sm_state
*merge_implied(struct sm_state
*one
, struct sm_state
*two
,
695 struct state_list
*pool
,
696 struct state_list
*cur_slist
)
698 struct sm_state
*cur_state
;
700 cur_state
= get_sm_state_slist(cur_slist
, two
->name
, two
->owner
,
703 return NULL
; /* this can't actually happen */
704 if (!pool_in_pools(cur_state
->all_pools
, pool
))
706 return merge_sm_states(one
, two
);
710 * filter() is used to find what states are the same across
711 * a series of slists.
712 * It takes a **slist and a *filter.
713 * It removes everything from **slist that isn't in *filter.
714 * The reason you would want to do this is if you want to
715 * know what other states are true if one state is true. (smatch_implied).
717 void filter(struct state_list
**slist
, struct state_list
*filter
,
718 struct state_list
*cur_slist
)
720 struct sm_state
*s_one
, *s_two
;
721 struct state_list
*results
= NULL
;
722 struct sm_state
*tmp
;
727 PREPARE_PTR_LIST(*slist
, s_one
);
728 PREPARE_PTR_LIST(filter
, s_two
);
730 if (!s_one
|| !s_two
)
732 if (cmp_tracker(s_one
, s_two
) < 0) {
733 DIMPLIED("removed %s\n", s_one
->name
);
734 NEXT_PTR_LIST(s_one
);
735 } else if (cmp_tracker(s_one
, s_two
) == 0) {
736 tmp
= merge_implied(s_one
, s_two
, filter
, cur_slist
);
738 add_ptr_list(&results
, tmp
);
740 DIMPLIED("removed %s\n", s_one
->name
);
741 NEXT_PTR_LIST(s_one
);
742 NEXT_PTR_LIST(s_two
);
744 NEXT_PTR_LIST(s_two
);
747 FINISH_PTR_LIST(s_two
);
748 FINISH_PTR_LIST(s_one
);
750 sanity_check_pools(results
);
756 * and_slist_stack() is basically the same as popping the top two slists,
757 * overwriting the one with the other and pushing it back on the stack.
758 * The difference is that it checks to see that a mutually exclusive
759 * state isn't included in both stacks. If smatch sees something like
760 * "if (a && !a)" it prints a warning.
762 void and_slist_stack(struct state_list_stack
**slist_stack
)
764 struct sm_state
*tmp
;
765 struct smatch_state
*tmp_state
;
766 struct state_list
*tmp_slist
= pop_slist(slist_stack
);
768 FOR_EACH_PTR(tmp_slist
, tmp
) {
769 tmp_state
= get_state_stack(*slist_stack
, tmp
->name
,
770 tmp
->owner
, tmp
->sym
);
771 if (tmp_state
&& tmp_state
!= tmp
->state
) {
772 smatch_msg("mutually exclusive 'and' conditions states "
774 tmp
->name
, show_state(tmp_state
),
775 show_state(tmp
->state
));
777 set_state_stack(slist_stack
, tmp
->name
, tmp
->owner
, tmp
->sym
,
779 } END_FOR_EACH_PTR(tmp
);
780 free_slist(&tmp_slist
);
784 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
785 * It pops the two slists from the top of the stack and merges them
786 * together in a way that preserves the things they have in common
787 * but creates a merged state for most of the rest.
788 * You could have code that had: if (foo || foo) { foo->baz;
789 * It's this function which ensures smatch does the right thing.
791 void or_slist_stack(struct state_list_stack
**pre_conds
,
792 struct state_list
*cur_slist
,
793 struct state_list_stack
**slist_stack
)
795 struct state_list
*new;
796 struct state_list
*old
;
797 struct state_list
*res
= NULL
;
798 struct state_list
*tmp_slist
;
800 new = pop_slist(slist_stack
);
801 old
= pop_slist(slist_stack
);
803 tmp_slist
= pop_slist(pre_conds
);
804 res
= clone_slist(tmp_slist
);
805 push_slist(pre_conds
, tmp_slist
);
806 overwrite_slist(old
, &res
);
808 tmp_slist
= clone_slist(cur_slist
);
809 overwrite_slist(new, &tmp_slist
);
811 merge_slist(&res
, tmp_slist
);
813 push_slist(slist_stack
, res
);
814 free_slist(&tmp_slist
);
820 * get_slist_from_named_stack() is only used for gotos.
822 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
825 struct named_slist
*tmp
;
827 FOR_EACH_PTR(stack
, tmp
) {
828 if (!strcmp(tmp
->name
, name
))
830 } END_FOR_EACH_PTR(tmp
);
834 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
836 struct sm_state
*tmp
;
838 FOR_EACH_PTR(from
, tmp
) {
839 overwrite_sm_state(to
, tmp
);
840 } END_FOR_EACH_PTR(tmp
);
843 unsigned int __get_allocations()
845 return sm_state_allocator
.allocations
;