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(smatch_state
, "smatch state");
18 ALLOCATOR(sm_state
, "sm state");
19 ALLOCATOR(named_slist
, "named slist");
20 __DO_ALLOCATOR(char, 0, 1, "state names", sname
);
22 void __print_slist(struct state_list
*slist
)
24 struct sm_state
*state
;
25 struct sm_state
*poss
;
28 printf("dumping slist at %d\n", get_lineno());
29 FOR_EACH_PTR(slist
, state
) {
30 printf("%d '%s'=%s (", state
->owner
, state
->name
,
31 show_state(state
->state
));
33 FOR_EACH_PTR(state
->possible
, poss
) {
36 printf("%s", show_state(poss
->state
));
37 } END_FOR_EACH_PTR(poss
);
39 } END_FOR_EACH_PTR(state
);
44 /* NULL states go at the end to simplify merge_slist */
45 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
56 if (a
->owner
> b
->owner
)
58 if (a
->owner
< b
->owner
)
61 ret
= strcmp(a
->name
, b
->name
);
65 if (!b
->sym
&& a
->sym
)
67 if (!a
->sym
&& b
->sym
)
77 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
81 ret
= cmp_tracker(a
, b
);
85 /* todo: add hook for smatch_extra.c */
86 if (a
->state
> b
->state
)
88 if (a
->state
< b
->state
)
93 static struct sm_state
*alloc_state_no_name(const char *name
, int owner
,
95 struct smatch_state
*state
)
99 tmp
= alloc_state(NULL
, owner
, sym
, state
);
104 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
106 struct sm_state
*tmp
;
108 FOR_EACH_PTR(*slist
, tmp
) {
109 if (cmp_sm_states(tmp
, new) < 0)
111 else if (cmp_sm_states(tmp
, new) == 0) {
114 INSERT_CURRENT(new, tmp
);
117 } END_FOR_EACH_PTR(tmp
);
118 add_ptr_list(slist
, new);
121 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
123 struct sm_state
*tmp
;
124 struct sm_state
*tmp2
;
127 struct smatch_state
*s
;
129 s
= merge_states(sm
->name
, sm
->owner
, sm
->sym
, sm
->state
, NULL
);
130 tmp
= alloc_state_no_name(sm
->name
, sm
->owner
, sm
->sym
, s
);
131 add_sm_state_slist(&sm
->possible
, tmp
);
135 FOR_EACH_PTR(new->possible
, tmp
) {
136 tmp2
= alloc_state_no_name(tmp
->name
, tmp
->owner
, tmp
->sym
,
138 add_sm_state_slist(&sm
->possible
, tmp2
);
139 } END_FOR_EACH_PTR(tmp
);
142 char *alloc_sname(const char *str
)
148 tmp
= __alloc_sname(strlen(str
) + 1);
153 struct sm_state
*alloc_state(const char *name
, int owner
,
154 struct symbol
*sym
, struct smatch_state
*state
)
156 struct sm_state
*sm_state
= __alloc_sm_state(0);
158 sm_state
->name
= alloc_sname(name
);
159 sm_state
->owner
= owner
;
161 sm_state
->state
= state
;
162 sm_state
->line
= get_lineno();
163 sm_state
->merged
= 0;
164 sm_state
->my_pools
= NULL
;
165 sm_state
->pre_left
= NULL
;
166 sm_state
->pre_right
= NULL
;
167 sm_state
->possible
= NULL
;
168 add_ptr_list(&sm_state
->possible
, sm_state
);
172 static void free_sm_state(struct sm_state
*sm
)
174 free_slist(&sm
->possible
);
175 free_stack(&sm
->my_pools
);
177 * fixme. Free the actual state.
178 * Right now we leave it until the end of the function
179 * because we don't want to double free it.
180 * Use the freelist to not double free things
184 static void free_all_sm_states(struct allocation_blob
*blob
)
186 unsigned int size
= sizeof(struct sm_state
);
187 unsigned int offset
= 0;
189 while (offset
< blob
->offset
) {
190 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
195 /* At the end of every function we free all the sm_states */
196 void free_every_single_sm_state(void)
198 struct allocator_struct
*desc
= &sm_state_allocator
;
199 struct allocation_blob
*blob
= desc
->blobs
;
202 desc
->allocations
= 0;
203 desc
->total_bytes
= 0;
204 desc
->useful_bytes
= 0;
205 desc
->freelist
= NULL
;
207 struct allocation_blob
*next
= blob
->next
;
208 free_all_sm_states(blob
);
209 blob_free(blob
, desc
->chunking
);
215 struct sm_state
*clone_state(struct sm_state
*s
)
217 struct sm_state
*ret
;
219 ret
= alloc_state_no_name(s
->name
, s
->owner
, s
->sym
, s
->state
);
221 ret
->merged
= s
->merged
;
222 /* clone_state() doesn't copy the my_pools. Each state needs to have
224 ret
->possible
= clone_slist(s
->possible
);
225 ret
->pre_left
= s
->pre_left
;
226 ret
->pre_right
= s
->pre_right
;
230 int is_merged(struct sm_state
*sm
)
235 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
237 struct sm_state
*tmp
;
239 FOR_EACH_PTR(slist
, tmp
) {
240 if (tmp
->state
== state
)
242 } END_FOR_EACH_PTR(tmp
);
246 static void check_order(struct state_list
*slist
)
249 struct sm_state
*state
;
250 struct sm_state
*last
= NULL
;
253 FOR_EACH_PTR(slist
, state
) {
254 if (last
&& cmp_tracker(state
, last
) <= 0) {
255 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
256 "%s vs %s\n", last
->owner
, state
->owner
,
257 last
->sym
, state
->sym
, last
->name
, state
->name
);
261 } END_FOR_EACH_PTR(state
);
268 struct state_list
*clone_slist(struct state_list
*from_slist
)
270 struct sm_state
*state
;
271 struct state_list
*to_slist
= NULL
;
273 FOR_EACH_PTR(from_slist
, state
) {
274 add_ptr_list(&to_slist
, state
);
275 } END_FOR_EACH_PTR(state
);
276 check_order(to_slist
);
280 struct state_list
*clone_slist_and_states(struct state_list
*from_slist
)
282 struct sm_state
*state
;
283 struct sm_state
*tmp
;
284 struct state_list
*to_slist
= NULL
;
286 FOR_EACH_PTR(from_slist
, state
) {
287 tmp
= clone_state(state
);
288 add_ptr_list(&to_slist
, tmp
);
289 } END_FOR_EACH_PTR(state
);
290 check_order(to_slist
);
294 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
296 struct state_list
*slist
;
297 struct state_list_stack
*to_stack
= NULL
;
299 FOR_EACH_PTR(from_stack
, slist
) {
300 push_slist(&to_stack
, slist
);
301 } END_FOR_EACH_PTR(slist
);
305 struct smatch_state
*merge_states(const char *name
, int owner
,
307 struct smatch_state
*state1
,
308 struct smatch_state
*state2
)
310 struct smatch_state
*ret
;
312 if (state1
== state2
)
314 else if (__has_merge_function(owner
))
315 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
316 else if (!state1
|| !state2
)
324 * add_pool() adds a slist to ->pools. If the slist has already been
325 * added earlier then it doesn't get added a second time.
327 void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
329 struct state_list
*tmp
;
331 FOR_EACH_PTR(*pools
, tmp
) {
334 else if (tmp
== new) {
337 INSERT_CURRENT(new, tmp
);
340 } END_FOR_EACH_PTR(tmp
);
341 add_ptr_list(pools
, new);
344 void merge_pools(struct state_list_stack
**to
, struct state_list_stack
*from
)
346 struct state_list
*tmp
;
348 FOR_EACH_PTR(from
, tmp
) {
350 } END_FOR_EACH_PTR(tmp
);
353 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
355 struct smatch_state
*s
;
356 struct sm_state
*result
;
360 s
= merge_states(one
->name
, one
->owner
, one
->sym
, one
->state
,
361 (two
?two
->state
:NULL
));
362 result
= alloc_state_no_name(one
->name
, one
->owner
, one
->sym
, s
);
363 if (two
&& one
->line
== two
->line
)
364 result
->line
= one
->line
;
366 result
->pre_left
= one
;
367 result
->pre_right
= two
;
368 add_possible(result
, one
);
369 add_possible(result
, two
);
372 struct sm_state
*tmp
;
375 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
376 get_lineno(), one
->name
, one
->owner
,
377 show_state(one
->state
), show_state(two
?two
->state
:NULL
),
380 FOR_EACH_PTR(result
->possible
, tmp
) {
384 printf("%s", show_state(tmp
->state
));
385 } END_FOR_EACH_PTR(tmp
);
392 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, const char *name
,
393 int owner
, struct symbol
*sym
)
395 struct sm_state
*state
;
400 FOR_EACH_PTR(slist
, state
) {
401 if (state
->owner
== owner
&& state
->sym
== sym
402 && !strcmp(state
->name
, name
))
404 } END_FOR_EACH_PTR(state
);
408 struct smatch_state
*get_state_slist(struct state_list
*slist
,
409 const char *name
, int owner
,
412 struct sm_state
*state
;
414 state
= get_sm_state_slist(slist
, name
, owner
, sym
);
420 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
422 struct sm_state
*tmp
;
424 FOR_EACH_PTR(*slist
, tmp
) {
425 if (cmp_tracker(tmp
, new) < 0)
427 else if (cmp_tracker(tmp
, new) == 0) {
428 REPLACE_CURRENT_PTR(tmp
, new);
431 INSERT_CURRENT(new, tmp
);
434 } END_FOR_EACH_PTR(tmp
);
435 add_ptr_list(slist
, new);
438 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
439 struct sm_state
*state
)
441 struct state_list
*slist
;
443 slist
= pop_slist(stack
);
444 overwrite_sm_state(&slist
, state
);
445 push_slist(stack
, slist
);
448 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
449 struct symbol
*sym
, struct smatch_state
*state
)
451 struct sm_state
*tmp
;
452 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
454 FOR_EACH_PTR(*slist
, tmp
) {
455 if (cmp_tracker(tmp
, new) < 0)
457 else if (cmp_tracker(tmp
, new) == 0) {
458 REPLACE_CURRENT_PTR(tmp
, new);
461 INSERT_CURRENT(new, tmp
);
464 } END_FOR_EACH_PTR(tmp
);
465 add_ptr_list(slist
, new);
468 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
471 struct sm_state
*state
;
473 FOR_EACH_PTR(*slist
, state
) {
474 if (state
->owner
== owner
&& state
->sym
== sym
475 && !strcmp(state
->name
, name
)){
476 DELETE_CURRENT_PTR(state
);
479 } END_FOR_EACH_PTR(state
);
483 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
485 add_ptr_list(list_stack
, slist
);
488 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
490 struct state_list
*slist
;
492 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
493 delete_ptr_list_last((struct ptr_list
**)list_stack
);
497 void free_slist(struct state_list
**slist
)
499 __free_ptr_list((struct ptr_list
**)slist
);
502 void free_stack(struct state_list_stack
**stack
)
504 __free_ptr_list((struct ptr_list
**)stack
);
507 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
509 struct state_list
*slist
;
511 FOR_EACH_PTR(*slist_stack
, slist
) {
513 } END_FOR_EACH_PTR(slist
);
514 free_stack(slist_stack
);
518 * set_state_stack() sets the state for the top slist on the stack.
520 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
521 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
523 struct state_list
*slist
;
525 slist
= pop_slist(stack
);
526 set_state_slist(&slist
, name
, owner
, sym
, state
);
527 push_slist(stack
, slist
);
531 * get_sm_state_stack() gets the state for the top slist on the stack.
533 struct sm_state
*get_sm_state_stack(struct state_list_stack
*stack
,
534 const char *name
, int owner
,
537 struct state_list
*slist
;
538 struct sm_state
*ret
;
540 slist
= pop_slist(&stack
);
541 ret
= get_sm_state_slist(slist
, name
, owner
, sym
);
542 push_slist(&stack
, slist
);
547 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
548 const char *name
, int owner
,
551 struct sm_state
*state
;
553 state
= get_sm_state_stack(stack
, name
, owner
, sym
);
559 static void match_states(struct state_list
**one
, struct state_list
**two
)
561 struct sm_state
*one_state
;
562 struct sm_state
*two_state
;
563 struct sm_state
*tmp
;
564 struct smatch_state
*tmp_state
;
565 struct state_list
*add_to_one
= NULL
;
566 struct state_list
*add_to_two
= NULL
;
568 PREPARE_PTR_LIST(*one
, one_state
);
569 PREPARE_PTR_LIST(*two
, two_state
);
571 if (!one_state
&& !two_state
)
573 if (cmp_tracker(one_state
, two_state
) < 0) {
574 tmp_state
= __client_unmatched_state_function(one_state
);
575 tmp
= alloc_state_no_name(one_state
->name
,
577 one_state
->sym
, tmp_state
);
578 add_ptr_list(&add_to_two
, tmp
);
579 NEXT_PTR_LIST(one_state
);
580 } else if (cmp_tracker(one_state
, two_state
) == 0) {
581 NEXT_PTR_LIST(one_state
);
582 NEXT_PTR_LIST(two_state
);
584 tmp_state
= __client_unmatched_state_function(two_state
);
585 tmp
= alloc_state_no_name(two_state
->name
,
587 two_state
->sym
, tmp_state
);
588 add_ptr_list(&add_to_one
, tmp
);
589 NEXT_PTR_LIST(two_state
);
592 FINISH_PTR_LIST(two_state
);
593 FINISH_PTR_LIST(one_state
);
595 overwrite_slist(add_to_one
, one
);
596 overwrite_slist(add_to_two
, two
);
599 static void clone_modified(struct state_list
**one
, struct state_list
**two
)
601 struct sm_state
*one_state
;
602 struct sm_state
*two_state
;
603 struct sm_state
*clone
;
604 struct state_list
*add_to_one
= NULL
;
605 struct state_list
*add_to_two
= NULL
;
607 PREPARE_PTR_LIST(*one
, one_state
);
608 PREPARE_PTR_LIST(*two
, two_state
);
610 if (!one_state
&& !two_state
)
612 if (cmp_tracker(one_state
, two_state
) < 0) {
613 NEXT_PTR_LIST(one_state
);
614 } else if (cmp_tracker(one_state
, two_state
) == 0) {
615 if (one_state
!= two_state
) {
616 clone
= clone_state(one_state
);
617 add_ptr_list(&add_to_one
, clone
);
618 clone
= clone_state(two_state
);
619 add_ptr_list(&add_to_two
, clone
);
621 NEXT_PTR_LIST(one_state
);
622 NEXT_PTR_LIST(two_state
);
624 NEXT_PTR_LIST(two_state
);
627 FINISH_PTR_LIST(two_state
);
628 FINISH_PTR_LIST(one_state
);
630 overwrite_slist(add_to_one
, one
);
631 overwrite_slist(add_to_two
, two
);
634 static void clone_pool_havers(struct state_list
*slist
)
636 struct sm_state
*state
;
637 struct sm_state
*new;
639 FOR_EACH_PTR(slist
, state
) {
640 if (state
->my_pools
) {
641 new = clone_state(state
);
642 REPLACE_CURRENT_PTR(state
, new);
644 } END_FOR_EACH_PTR(state
);
648 * merge_slist() is called whenever paths merge, such as after
649 * an if statement. It takes the two slists and creates one.
651 static void __merge_slist(struct state_list
**to
, struct state_list
*slist
, int clone
)
653 struct sm_state
*to_state
, *state
, *tmp
;
654 struct state_list
*results
= NULL
;
655 struct state_list
*implied_to
= NULL
;
656 struct state_list
*implied_from
= NULL
;
661 /* merging a null and nonnull path gives you only the nonnull path */
666 *to
= clone_slist(slist
);
670 implied_to
= clone_slist(*to
);
671 implied_from
= clone_slist(slist
);
673 match_states(&implied_to
, &implied_from
);
675 clone_modified(&implied_to
, &implied_from
);
676 clone_pool_havers(implied_to
);
677 clone_pool_havers(implied_from
);
679 PREPARE_PTR_LIST(implied_to
, to_state
);
680 PREPARE_PTR_LIST(implied_from
, state
);
682 if (!to_state
&& !state
)
684 if (cmp_tracker(to_state
, state
) < 0) {
685 smatch_msg("error: Internal smatch error.");
686 NEXT_PTR_LIST(to_state
);
687 } else if (cmp_tracker(to_state
, state
) == 0) {
688 if (to_state
!= state
) {
689 if (to_state
->my_pools
)
690 smatch_msg("to_state '%s' has pools", to_state
->name
);
692 smatch_msg("state '%s' has pools", state
->name
);
693 add_pool(&to_state
->my_pools
, implied_to
);
694 add_pool(&state
->my_pools
, implied_from
);
697 tmp
= merge_sm_states(to_state
, state
);
698 add_ptr_list(&results
, tmp
);
699 NEXT_PTR_LIST(to_state
);
700 NEXT_PTR_LIST(state
);
702 smatch_msg("error: Internal smatch error.");
703 NEXT_PTR_LIST(state
);
706 FINISH_PTR_LIST(state
);
707 FINISH_PTR_LIST(to_state
);
713 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
715 __merge_slist(to
, slist
, 0);
718 void merge_slist_clone(struct state_list
**to
, struct state_list
*slist
)
720 __merge_slist(to
, slist
, 1);
724 * and_slist_stack() is basically the same as popping the top two slists,
725 * overwriting the one with the other and pushing it back on the stack.
726 * The difference is that it checks to see that a mutually exclusive
727 * state isn't included in both stacks. If smatch sees something like
728 * "if (a && !a)" it prints a warning.
730 void and_slist_stack(struct state_list_stack
**slist_stack
)
732 struct sm_state
*tmp
;
733 struct state_list
*right_slist
= pop_slist(slist_stack
);
735 FOR_EACH_PTR(right_slist
, tmp
) {
736 overwrite_sm_state_stack(slist_stack
, tmp
);
737 } END_FOR_EACH_PTR(tmp
);
738 free_slist(&right_slist
);
742 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
743 * It pops the two slists from the top of the stack and merges them
744 * together in a way that preserves the things they have in common
745 * but creates a merged state for most of the rest.
746 * You could have code that had: if (foo || foo) { foo->baz;
747 * It's this function which ensures smatch does the right thing.
749 void or_slist_stack(struct state_list_stack
**pre_conds
,
750 struct state_list
*cur_slist
,
751 struct state_list_stack
**slist_stack
)
753 struct state_list
*new;
754 struct state_list
*old
;
755 struct state_list
*res
= NULL
;
756 struct state_list
*tmp_slist
;
758 new = pop_slist(slist_stack
);
759 old
= pop_slist(slist_stack
);
761 tmp_slist
= pop_slist(pre_conds
);
762 res
= clone_slist(tmp_slist
);
763 push_slist(pre_conds
, tmp_slist
);
764 overwrite_slist(old
, &res
);
766 tmp_slist
= clone_slist(cur_slist
);
767 overwrite_slist(new, &tmp_slist
);
769 merge_slist(&res
, tmp_slist
);
771 push_slist(slist_stack
, res
);
772 free_slist(&tmp_slist
);
778 * get_slist_from_named_stack() is only used for gotos.
780 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
783 struct named_slist
*tmp
;
785 FOR_EACH_PTR(stack
, tmp
) {
786 if (!strcmp(tmp
->name
, name
))
788 } END_FOR_EACH_PTR(tmp
);
792 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
794 struct sm_state
*tmp
;
796 FOR_EACH_PTR(from
, tmp
) {
797 overwrite_sm_state(to
, tmp
);
798 } END_FOR_EACH_PTR(tmp
);