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"
17 ALLOCATOR(sm_state
, "smatch state");
18 ALLOCATOR(named_slist
, "named slist");
20 void __print_slist(struct state_list
*slist
)
22 struct sm_state
*state
;
23 struct sm_state
*poss
;
26 printf("dumping slist at %d\n", get_lineno());
27 FOR_EACH_PTR(slist
, state
) {
28 printf("%d '%s'=%s (", state
->owner
, state
->name
,
29 show_state(state
->state
));
31 FOR_EACH_PTR(state
->possible
, poss
) {
34 printf("%s", show_state(poss
->state
));
35 } END_FOR_EACH_PTR(poss
);
37 } END_FOR_EACH_PTR(state
);
41 void add_history(struct sm_state
*state
)
43 struct state_history
*tmp
;
47 tmp
= malloc(sizeof(*tmp
));
48 tmp
->loc
= get_lineno();
49 add_ptr_list(&state
->line_history
, tmp
);
53 /* NULL states go at the end to simplify merge_slist */
54 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
65 if (a
->owner
> b
->owner
)
67 if (a
->owner
< b
->owner
)
70 ret
= strcmp(a
->name
, b
->name
);
74 if (!b
->sym
&& a
->sym
)
76 if (!a
->sym
&& b
->sym
)
86 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
90 ret
= cmp_tracker(a
, b
);
94 /* todo: add hook for smatch_extra.c */
95 if (a
->state
> b
->state
)
97 if (a
->state
< b
->state
)
102 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
104 struct sm_state
*tmp
;
106 FOR_EACH_PTR(*slist
, tmp
) {
107 if (cmp_sm_states(tmp
, new) < 0)
109 else if (cmp_sm_states(tmp
, new) == 0) {
112 INSERT_CURRENT(new, tmp
);
115 } END_FOR_EACH_PTR(tmp
);
116 add_ptr_list(slist
, new);
119 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
121 struct sm_state
*tmp
;
122 struct sm_state
*tmp2
;
125 struct smatch_state
*s
;
127 s
= merge_states(sm
->name
, sm
->owner
, sm
->sym
, sm
->state
, NULL
);
128 tmp
= alloc_state(sm
->name
, sm
->owner
, sm
->sym
, s
);
129 add_sm_state_slist(&sm
->possible
, tmp
);
133 FOR_EACH_PTR(new->possible
, tmp
) {
134 tmp2
= alloc_state(tmp
->name
, tmp
->owner
, tmp
->sym
, tmp
->state
);
135 add_sm_state_slist(&sm
->possible
, tmp2
);
136 } END_FOR_EACH_PTR(tmp
);
139 struct sm_state
*alloc_state(const char *name
, int owner
,
140 struct symbol
*sym
, struct smatch_state
*state
)
142 struct sm_state
*sm_state
= __alloc_sm_state(0);
144 sm_state
->name
= (char *)name
;
145 sm_state
->owner
= owner
;
147 sm_state
->state
= state
;
148 sm_state
->line_history
= NULL
;
149 add_history(sm_state
);
150 sm_state
->my_pools
= NULL
;
151 sm_state
->all_pools
= NULL
;
152 sm_state
->possible
= NULL
;
153 add_ptr_list(&sm_state
->possible
, sm_state
);
157 /* At the end of every function we free all the sm_states */
158 void free_every_single_sm_state()
160 struct allocator_struct
*desc
= &sm_state_allocator
;
161 struct allocation_blob
*blob
= desc
->blobs
;
164 desc
->allocations
= 0;
165 desc
->total_bytes
= 0;
166 desc
->useful_bytes
= 0;
167 desc
->freelist
= NULL
;
169 struct allocation_blob
*next
= blob
->next
;
170 struct sm_state
*sm
= (struct sm_state
*)blob
->data
;
172 free_slist(&sm
->possible
);
173 __free_ptr_list((struct ptr_list
**)&sm
->my_pools
);
174 __free_ptr_list((struct ptr_list
**)&sm
->all_pools
);
175 blob_free(blob
, desc
->chunking
);
180 struct sm_state
*clone_state(struct sm_state
*s
)
182 struct sm_state
*ret
;
183 struct sm_state
*tmp
;
184 struct sm_state
*poss
;
186 ret
= alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
187 ret
->my_pools
= clone_stack(s
->my_pools
);
188 ret
->all_pools
= clone_stack(s
->all_pools
);
189 FOR_EACH_PTR(s
->possible
, poss
) {
190 tmp
= alloc_state(s
->name
, s
->owner
, s
->sym
, poss
->state
);
191 add_sm_state_slist(&ret
->possible
, tmp
);
192 } END_FOR_EACH_PTR(poss
);
196 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
198 struct sm_state
*tmp
;
200 FOR_EACH_PTR(slist
, tmp
) {
201 if (tmp
->state
== state
)
203 } END_FOR_EACH_PTR(tmp
);
208 static void check_order(struct state_list
*slist
)
210 struct sm_state
*state
;
211 struct sm_state
*last
= NULL
;
214 FOR_EACH_PTR(slist
, state
) {
215 if (last
&& cmp_tracker(state
, last
) <= 0) {
216 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
217 "%s vs %s\n", last
->owner
, state
->owner
,
218 last
->sym
, state
->sym
, last
->name
, state
->name
);
222 } END_FOR_EACH_PTR(state
);
229 struct state_list
*clone_slist(struct state_list
*from_slist
)
231 struct sm_state
*state
;
232 struct sm_state
*tmp
;
233 struct state_list
*to_slist
= NULL
;
235 FOR_EACH_PTR(from_slist
, state
) {
236 tmp
= clone_state(state
);
237 add_ptr_list(&to_slist
, tmp
);
238 } END_FOR_EACH_PTR(state
);
240 check_order(to_slist
);
245 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
247 struct state_list
*slist
;
248 struct state_list_stack
*to_stack
= NULL
;
250 FOR_EACH_PTR(from_stack
, slist
) {
251 push_slist(&to_stack
, slist
);
252 } END_FOR_EACH_PTR(slist
);
256 struct smatch_state
*merge_states(const char *name
, int owner
,
258 struct smatch_state
*state1
,
259 struct smatch_state
*state2
)
261 struct smatch_state
*ret
;
263 if (state1
== state2
)
265 else if (__has_merge_function(owner
))
266 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
267 else if (!state1
|| !state2
)
275 * add_pool() adds a slist to ->pools. If the slist has already been
276 * added earlier then it doesn't get added a second time.
278 static void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
280 struct state_list
*tmp
;
282 FOR_EACH_PTR(*pools
, tmp
) {
285 else if (tmp
== new) {
288 INSERT_CURRENT(new, tmp
);
291 } END_FOR_EACH_PTR(tmp
);
292 add_ptr_list(pools
, new);
295 static void copy_pools(struct sm_state
*to
, struct sm_state
*sm
)
297 struct state_list
*tmp
;
302 FOR_EACH_PTR(sm
->my_pools
, tmp
) {
303 add_pool(&to
->my_pools
, tmp
);
304 } END_FOR_EACH_PTR(tmp
);
306 FOR_EACH_PTR(sm
->all_pools
, tmp
) {
307 add_pool(&to
->all_pools
, tmp
);
308 } END_FOR_EACH_PTR(tmp
);
311 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
313 struct smatch_state
*s
;
314 struct sm_state
*result
;
316 s
= merge_states(one
->name
, one
->owner
, one
->sym
, one
->state
,
317 (two
?two
->state
:NULL
));
318 result
= alloc_state(one
->name
, one
->owner
, one
->sym
, s
);
319 add_possible(result
, one
);
320 add_possible(result
, two
);
321 copy_pools(result
, one
);
322 copy_pools(result
, two
);
325 struct sm_state
*tmp
;
328 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
329 get_lineno(), one
->name
, one
->owner
,
330 show_state(one
->state
), show_state(two
?two
->state
:NULL
),
333 FOR_EACH_PTR(result
->possible
, tmp
) {
337 printf("%s", show_state(tmp
->state
));
338 } END_FOR_EACH_PTR(tmp
);
345 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, const char *name
,
346 int owner
, struct symbol
*sym
)
348 struct sm_state
*state
;
353 FOR_EACH_PTR(slist
, state
) {
354 if (state
->owner
== owner
&& state
->sym
== sym
355 && !strcmp(state
->name
, name
))
357 } END_FOR_EACH_PTR(state
);
361 struct smatch_state
*get_state_slist(struct state_list
*slist
,
362 const char *name
, int owner
,
365 struct sm_state
*state
;
367 state
= get_sm_state_slist(slist
, name
, owner
, sym
);
373 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*state
)
375 struct sm_state
*tmp
;
376 struct sm_state
*new = clone_state(state
); //fixme. why?
378 FOR_EACH_PTR(*slist
, tmp
) {
379 if (cmp_tracker(tmp
, new) < 0)
381 else if (cmp_tracker(tmp
, new) == 0) {
382 REPLACE_CURRENT_PTR(tmp
, new);
385 INSERT_CURRENT(new, tmp
);
388 } END_FOR_EACH_PTR(tmp
);
389 add_ptr_list(slist
, new);
392 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
393 struct sm_state
*state
)
395 struct state_list
*slist
;
397 slist
= pop_slist(stack
);
398 overwrite_sm_state(&slist
, state
);
399 push_slist(stack
, slist
);
402 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
403 struct symbol
*sym
, struct smatch_state
*state
)
405 struct sm_state
*tmp
;
406 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
408 FOR_EACH_PTR(*slist
, tmp
) {
409 if (cmp_tracker(tmp
, new) < 0)
411 else if (cmp_tracker(tmp
, new) == 0) {
413 tmp
->my_pools
= NULL
;
414 tmp
->all_pools
= NULL
;
415 tmp
->possible
= NULL
;
416 add_ptr_list(&tmp
->possible
, tmp
);
417 __free_sm_state(new);
420 INSERT_CURRENT(new, tmp
);
423 } END_FOR_EACH_PTR(tmp
);
424 add_ptr_list(slist
, new);
427 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
430 struct sm_state
*state
;
432 FOR_EACH_PTR(*slist
, state
) {
433 if (state
->owner
== owner
&& state
->sym
== sym
434 && !strcmp(state
->name
, name
)){
435 delete_ptr_list_entry((struct ptr_list
**)slist
,
437 __free_sm_state(state
);
440 } END_FOR_EACH_PTR(state
);
444 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
446 add_ptr_list(list_stack
, slist
);
449 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
451 struct state_list
*slist
;
453 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
454 delete_ptr_list_last((struct ptr_list
**)list_stack
);
458 void free_slist(struct state_list
**slist
)
460 __free_ptr_list((struct ptr_list
**)slist
);
463 void del_slist_stack(struct state_list_stack
**slist_stack
)
465 struct state_list
*slist
;
467 FOR_EACH_PTR(*slist_stack
, slist
) {
468 __free_ptr_list((struct ptr_list
**)&slist
);
469 } END_FOR_EACH_PTR(slist
);
470 __free_ptr_list((struct ptr_list
**)slist_stack
);
474 * set_state_stack() sets the state for the top slist on the stack.
476 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
477 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
479 struct state_list
*slist
;
481 slist
= pop_slist(stack
);
482 set_state_slist(&slist
, name
, owner
, sym
, state
);
483 push_slist(stack
, slist
);
487 * get_state_stack() gets the state for the top slist on the stack.
489 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
490 const char *name
, int owner
,
493 struct state_list
*slist
;
494 struct smatch_state
*ret
;
496 slist
= pop_slist(&stack
);
497 ret
= get_state_slist(slist
, name
, owner
, sym
);
498 push_slist(&stack
, slist
);
503 * We want to find which states have been modified inside a branch.
504 * If you have 2 &merged states they could be different states really
505 * and maybe one or both were modified. We say it is unchanged if
506 * the ->state pointers are the same and they belong to the same pools.
507 * If they have been modified on both sides of a branch to the same thing,
508 * it's still OK to say they are the same, because that means they won't
509 * belong to any pools.
511 static int is_really_same(struct sm_state
*one
, struct sm_state
*two
)
513 struct state_list
*tmp1
;
514 struct state_list
*tmp2
;
516 if (one
->state
!= two
->state
)
519 PREPARE_PTR_LIST(one
->my_pools
, tmp1
);
520 PREPARE_PTR_LIST(two
->my_pools
, tmp2
);
526 } else if (tmp1
== tmp2
) {
533 FINISH_PTR_LIST(tmp2
);
534 FINISH_PTR_LIST(tmp1
);
539 * merge_slist() is called whenever paths merge, such as after
540 * an if statement. It takes the two slists and creates one.
542 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
544 struct sm_state
*to_state
, *state
, *tmp
;
545 struct state_list
*results
= NULL
;
546 struct state_list
*implied_to
= NULL
;
547 struct state_list
*implied_from
= NULL
;
554 /* merging a null and nonnull path gives you only the nonnull path */
559 *to
= clone_slist(slist
);
563 implied_to
= clone_slist(*to
);
564 implied_from
= clone_slist(slist
);
566 PREPARE_PTR_LIST(*to
, to_state
);
567 PREPARE_PTR_LIST(slist
, state
);
569 if (!to_state
&& !state
)
571 if (cmp_tracker(to_state
, state
) < 0) {
572 tmp
= merge_sm_states(to_state
, NULL
);
573 add_pool(&tmp
->my_pools
, implied_to
);
574 add_pool(&tmp
->all_pools
, implied_to
);
575 add_ptr_list(&results
, tmp
);
576 NEXT_PTR_LIST(to_state
);
577 } else if (cmp_tracker(to_state
, state
) == 0) {
578 tmp
= merge_sm_states(to_state
, state
);
579 if (!is_really_same(to_state
, state
)) {
580 add_pool(&tmp
->my_pools
, implied_to
);
581 add_pool(&tmp
->my_pools
, implied_from
);
583 add_pool(&tmp
->all_pools
, implied_to
);
584 add_pool(&tmp
->all_pools
, implied_from
);
585 add_ptr_list(&results
, tmp
);
586 NEXT_PTR_LIST(to_state
);
587 NEXT_PTR_LIST(state
);
589 tmp
= merge_sm_states(state
, NULL
);
590 add_pool(&tmp
->my_pools
, implied_from
);
591 add_pool(&tmp
->all_pools
, implied_from
);
592 add_ptr_list(&results
, tmp
);
593 NEXT_PTR_LIST(state
);
596 FINISH_PTR_LIST(state
);
597 FINISH_PTR_LIST(to_state
);
602 push_slist(&implied_pools
, implied_from
);
603 push_slist(&implied_pools
, implied_to
);
606 static int pool_in_pools(struct state_list_stack
*pools
,
607 struct state_list
*pool
)
609 struct state_list
*tmp
;
611 FOR_EACH_PTR(pools
, tmp
) {
614 } END_FOR_EACH_PTR(tmp
);
618 struct state_list
*clone_states_in_pool(struct state_list
*pool
,
619 struct state_list
*cur_slist
)
621 struct sm_state
*state
;
622 struct sm_state
*cur_state
;
623 struct sm_state
*tmp
;
624 struct state_list
*to_slist
= NULL
;
626 FOR_EACH_PTR(pool
, state
) {
627 cur_state
= get_sm_state_slist(cur_slist
, state
->name
,
628 state
->owner
, state
->sym
);
631 if (is_really_same(state
, cur_state
))
633 if (pool_in_pools(cur_state
->all_pools
, pool
)) {
634 tmp
= clone_state(state
);
635 add_ptr_list(&to_slist
, tmp
);
637 } END_FOR_EACH_PTR(state
);
642 * merge_implied() takes an implied state and another possibly implied state
643 * from another pool. It checks that the second pool is reachable from
644 * cur_slist then merges the two states and returns the result.
646 struct sm_state
*merge_implied(struct sm_state
*one
, struct sm_state
*two
,
647 struct state_list
*pool
,
648 struct state_list
*cur_slist
)
650 struct sm_state
*cur_state
;
652 // fixme: do we not need to check this?
653 cur_state
= get_sm_state_slist(cur_slist
, two
->name
, two
->owner
,
656 return NULL
; /* this can't actually happen */
657 if (!pool_in_pools(cur_state
->all_pools
, pool
))
659 return merge_sm_states(one
, two
);
663 * filter() is used to find what states are the same across
664 * a series of slists.
665 * It takes a **slist and a *filter.
666 * It removes everything from **slist that isn't in *filter.
667 * The reason you would want to do this is if you want to
668 * know what other states are true if one state is true. (smatch_implied).
670 void filter(struct state_list
**slist
, struct state_list
*filter
,
671 struct state_list
*cur_slist
)
673 struct sm_state
*s_one
, *s_two
;
674 struct state_list
*results
= NULL
;
675 struct sm_state
*tmp
;
682 PREPARE_PTR_LIST(*slist
, s_one
);
683 PREPARE_PTR_LIST(filter
, s_two
);
685 if (!s_one
|| !s_two
)
687 if (cmp_tracker(s_one
, s_two
) < 0) {
688 NEXT_PTR_LIST(s_one
);
689 } else if (cmp_tracker(s_one
, s_two
) == 0) {
690 tmp
= merge_implied(s_one
, s_two
, filter
, cur_slist
);
692 add_ptr_list(&results
, tmp
);
693 NEXT_PTR_LIST(s_one
);
694 NEXT_PTR_LIST(s_two
);
696 NEXT_PTR_LIST(s_two
);
699 FINISH_PTR_LIST(s_two
);
700 FINISH_PTR_LIST(s_one
);
707 * and_slist_stack() is basically the same as popping the top two slists,
708 * overwriting the one with the other and pushing it back on the stack.
709 * The difference is that it checks to see that a mutually exclusive
710 * state isn't included in both stacks. If smatch sees something like
711 * "if (a && !a)" it prints a warning.
713 void and_slist_stack(struct state_list_stack
**slist_stack
)
715 struct sm_state
*tmp
;
716 struct smatch_state
*tmp_state
;
717 struct state_list
*tmp_slist
= pop_slist(slist_stack
);
719 FOR_EACH_PTR(tmp_slist
, tmp
) {
720 tmp_state
= get_state_stack(*slist_stack
, tmp
->name
,
721 tmp
->owner
, tmp
->sym
);
722 if (tmp_state
&& tmp_state
!= tmp
->state
) {
723 smatch_msg("mutually exclusive 'and' conditions states "
725 tmp
->name
, show_state(tmp_state
),
726 show_state(tmp
->state
));
728 set_state_stack(slist_stack
, tmp
->name
, tmp
->owner
, tmp
->sym
,
730 } END_FOR_EACH_PTR(tmp
);
731 free_slist(&tmp_slist
);
735 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
736 * It pops the two slists from the top of the stack and merges them
737 * together in a way that preserves the things they have in common
738 * but creates a merged state for most of the rest.
739 * You could have code that had: if (foo || foo) { foo->baz;
740 * It's this function which ensures smatch does the right thing.
742 void or_slist_stack(struct state_list_stack
**slist_stack
)
744 struct state_list
*one
;
745 struct state_list
*two
;
746 struct state_list
*res
= NULL
;
747 struct sm_state
*tmp
;
749 struct sm_state
*new_sm
;
751 one
= pop_slist(slist_stack
);
752 two
= pop_slist(slist_stack
);
754 FOR_EACH_PTR(one
, tmp
) {
755 sm
= get_sm_state_slist(two
, tmp
->name
, tmp
->owner
, tmp
->sym
);
756 new_sm
= merge_sm_states(tmp
, sm
);
757 add_ptr_list(&res
, new_sm
);
758 } END_FOR_EACH_PTR(tmp
);
760 FOR_EACH_PTR(two
, tmp
) {
761 sm
= get_sm_state_slist(one
, tmp
->name
, tmp
->owner
, tmp
->sym
);
762 new_sm
= merge_sm_states(tmp
, sm
);
763 add_ptr_list(&res
, new_sm
);
764 } END_FOR_EACH_PTR(tmp
);
766 push_slist(slist_stack
, res
);
773 * get_slist_from_named_stack() is only used for gotos.
775 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
778 struct named_slist
*tmp
;
780 FOR_EACH_PTR(stack
, tmp
) {
781 if (!strcmp(tmp
->name
, name
))
783 } END_FOR_EACH_PTR(tmp
);
787 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
789 struct sm_state
*tmp
;
791 FOR_EACH_PTR(from
, tmp
) {
792 overwrite_sm_state(to
, tmp
);
793 } END_FOR_EACH_PTR(tmp
);