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 static int sm_state_counter
;
24 void __print_slist(struct state_list
*slist
)
26 struct sm_state
*state
;
27 struct sm_state
*poss
;
30 printf("dumping slist at %d\n", get_lineno());
31 FOR_EACH_PTR(slist
, state
) {
32 printf("[%s] '%s'=%s (", check_name(state
->owner
), state
->name
,
33 show_state(state
->state
));
35 FOR_EACH_PTR(state
->possible
, poss
) {
38 printf("%s", show_state(poss
->state
));
39 } END_FOR_EACH_PTR(poss
);
41 } END_FOR_EACH_PTR(state
);
46 /* NULL states go at the end to simplify merge_slist */
47 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
58 if (a
->owner
> b
->owner
)
60 if (a
->owner
< b
->owner
)
63 ret
= strcmp(a
->name
, b
->name
);
67 if (!b
->sym
&& a
->sym
)
69 if (!a
->sym
&& b
->sym
)
79 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
83 ret
= cmp_tracker(a
, b
);
87 /* todo: add hook for smatch_extra.c */
88 if (a
->state
> b
->state
)
90 if (a
->state
< b
->state
)
95 static struct sm_state
*alloc_sm_state(int owner
, const char *name
,
96 struct symbol
*sym
, struct smatch_state
*state
)
98 struct sm_state
*sm_state
= __alloc_sm_state(0);
102 sm_state
->name
= alloc_sname(name
);
103 sm_state
->owner
= owner
;
105 sm_state
->state
= state
;
106 sm_state
->line
= get_lineno();
107 sm_state
->merged
= 0;
108 sm_state
->implied
= 0;
109 sm_state
->my_pool
= NULL
;
110 sm_state
->left
= NULL
;
111 sm_state
->right
= NULL
;
112 sm_state
->nr_children
= 1;
113 sm_state
->possible
= NULL
;
114 add_ptr_list(&sm_state
->possible
, sm_state
);
118 static struct sm_state
*alloc_state_no_name(int owner
, const char *name
,
120 struct smatch_state
*state
)
122 struct sm_state
*tmp
;
124 tmp
= alloc_sm_state(owner
, NULL
, sym
, state
);
129 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
131 struct sm_state
*tmp
;
133 FOR_EACH_PTR(*slist
, tmp
) {
134 if (cmp_sm_states(tmp
, new) < 0)
136 else if (cmp_sm_states(tmp
, new) == 0) {
139 INSERT_CURRENT(new, tmp
);
142 } END_FOR_EACH_PTR(tmp
);
143 add_ptr_list(slist
, new);
146 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
148 struct sm_state
*tmp
;
149 struct sm_state
*tmp2
;
151 FOR_EACH_PTR(new->possible
, tmp
) {
152 tmp2
= alloc_state_no_name(tmp
->owner
,tmp
->name
, tmp
->sym
,
154 tmp2
->line
= tmp
->line
;
155 add_sm_state_slist(&sm
->possible
, tmp2
);
156 } END_FOR_EACH_PTR(tmp
);
159 char *alloc_sname(const char *str
)
165 tmp
= __alloc_sname(strlen(str
) + 1);
173 * I decided to use 50M here based on trial and error.
174 * It works out OK for the kernel and so it should work
175 * for most other projects as well.
177 if (sm_state_counter
* sizeof(struct sm_state
) >= 50000000)
182 static void free_sm_state(struct sm_state
*sm
)
184 free_slist(&sm
->possible
);
186 * fixme. Free the actual state.
187 * Right now we leave it until the end of the function
188 * because we don't want to double free it.
189 * Use the freelist to not double free things
193 static void free_all_sm_states(struct allocation_blob
*blob
)
195 unsigned int size
= sizeof(struct sm_state
);
196 unsigned int offset
= 0;
198 while (offset
< blob
->offset
) {
199 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
204 /* At the end of every function we free all the sm_states */
205 void free_every_single_sm_state(void)
207 struct allocator_struct
*desc
= &sm_state_allocator
;
208 struct allocation_blob
*blob
= desc
->blobs
;
211 desc
->allocations
= 0;
212 desc
->total_bytes
= 0;
213 desc
->useful_bytes
= 0;
214 desc
->freelist
= NULL
;
216 struct allocation_blob
*next
= blob
->next
;
217 free_all_sm_states(blob
);
218 blob_free(blob
, desc
->chunking
);
223 sm_state_counter
= 0;;
226 struct sm_state
*clone_sm(struct sm_state
*s
)
228 struct sm_state
*ret
;
230 ret
= alloc_state_no_name(s
->owner
, s
->name
, s
->sym
, s
->state
);
231 ret
->merged
= s
->merged
;
232 ret
->implied
= s
->implied
;
234 /* clone_sm() doesn't copy the my_pools. Each state needs to have
236 ret
->possible
= clone_slist(s
->possible
);
238 ret
->right
= s
->right
;
239 ret
->nr_children
= s
->nr_children
;
243 int is_merged(struct sm_state
*sm
)
248 int is_implied(struct sm_state
*sm
)
253 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
255 struct sm_state
*tmp
;
257 FOR_EACH_PTR(slist
, tmp
) {
258 if (tmp
->state
== state
)
260 } END_FOR_EACH_PTR(tmp
);
264 static void check_order(struct state_list
*slist
)
268 struct sm_state
*last
= NULL
;
271 FOR_EACH_PTR(slist
, sm
) {
272 if (last
&& cmp_tracker(sm
, last
) <= 0) {
273 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
274 "%s vs %s\n", last
->owner
, sm
->owner
,
275 last
->sym
, sm
->sym
, last
->name
, sm
->name
);
279 } END_FOR_EACH_PTR(sm
);
286 struct state_list
*clone_slist(struct state_list
*from_slist
)
289 struct state_list
*to_slist
= NULL
;
291 FOR_EACH_PTR(from_slist
, sm
) {
292 add_ptr_list(&to_slist
, sm
);
293 } END_FOR_EACH_PTR(sm
);
294 check_order(to_slist
);
298 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
300 struct state_list
*slist
;
301 struct state_list_stack
*to_stack
= NULL
;
303 FOR_EACH_PTR(from_stack
, slist
) {
304 push_slist(&to_stack
, slist
);
305 } END_FOR_EACH_PTR(slist
);
309 struct smatch_state
*merge_states(int owner
, const char *name
,
311 struct smatch_state
*state1
,
312 struct smatch_state
*state2
)
314 struct smatch_state
*ret
;
316 if (state1
== state2
)
318 else if (__has_merge_function(owner
))
319 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
320 else if (!state1
|| !state2
)
328 * add_pool() adds a slist to ->pools. If the slist has already been
329 * added earlier then it doesn't get added a second time.
331 void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
333 struct state_list
*tmp
;
335 FOR_EACH_PTR(*pools
, tmp
) {
338 else if (tmp
== new) {
341 INSERT_CURRENT(new, tmp
);
344 } END_FOR_EACH_PTR(tmp
);
345 add_ptr_list(pools
, new);
348 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
350 struct smatch_state
*s
;
351 struct sm_state
*result
;
355 s
= merge_states(one
->owner
, one
->name
, one
->sym
, one
->state
, two
->state
);
356 result
= alloc_state_no_name(one
->owner
, one
->name
, one
->sym
, s
);
360 result
->nr_children
= one
->nr_children
+ two
->nr_children
;
361 add_possible(result
, one
);
362 add_possible(result
, two
);
365 struct sm_state
*tmp
;
368 printf("%d merge name='%s' [%s] %s(L %d) + %s(L %d) => %s (",
369 get_lineno(), one
->name
, check_name(one
->owner
),
370 show_state(one
->state
), one
->line
,
371 show_state(two
->state
), two
->line
,
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
, int owner
, const char *name
,
394 FOR_EACH_PTR(slist
, sm
) {
395 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
))
397 } END_FOR_EACH_PTR(sm
);
401 struct smatch_state
*get_state_slist(struct state_list
*slist
,
402 int owner
, const char *name
,
407 sm
= get_sm_state_slist(slist
, owner
, name
, sym
);
413 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
415 struct sm_state
*tmp
;
417 FOR_EACH_PTR(*slist
, tmp
) {
418 if (cmp_tracker(tmp
, new) < 0)
420 else if (cmp_tracker(tmp
, new) == 0) {
421 REPLACE_CURRENT_PTR(tmp
, new);
424 INSERT_CURRENT(new, tmp
);
427 } END_FOR_EACH_PTR(tmp
);
428 add_ptr_list(slist
, new);
431 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
434 struct state_list
*slist
;
436 slist
= pop_slist(stack
);
437 overwrite_sm_state(&slist
, sm
);
438 push_slist(stack
, slist
);
441 struct sm_state
*set_state_slist(struct state_list
**slist
, int owner
, const char *name
,
442 struct symbol
*sym
, struct smatch_state
*state
)
444 struct sm_state
*tmp
;
445 struct sm_state
*new = alloc_sm_state(owner
, name
, sym
, state
);
447 FOR_EACH_PTR(*slist
, tmp
) {
448 if (cmp_tracker(tmp
, new) < 0)
450 else if (cmp_tracker(tmp
, new) == 0) {
451 REPLACE_CURRENT_PTR(tmp
, new);
454 INSERT_CURRENT(new, tmp
);
457 } END_FOR_EACH_PTR(tmp
);
458 add_ptr_list(slist
, new);
462 void delete_state_slist(struct state_list
**slist
, int owner
, const char *name
,
467 FOR_EACH_PTR(*slist
, sm
) {
468 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
)){
469 DELETE_CURRENT_PTR(sm
);
472 } END_FOR_EACH_PTR(sm
);
475 void delete_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
478 struct state_list
*slist
;
480 slist
= pop_slist(stack
);
481 delete_state_slist(&slist
, owner
, name
, sym
);
482 push_slist(stack
, slist
);
485 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
487 add_ptr_list(list_stack
, slist
);
490 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
492 struct state_list
*slist
;
494 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
495 delete_ptr_list_last((struct ptr_list
**)list_stack
);
499 void free_slist(struct state_list
**slist
)
501 __free_ptr_list((struct ptr_list
**)slist
);
504 void free_stack(struct state_list_stack
**stack
)
506 __free_ptr_list((struct ptr_list
**)stack
);
509 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
511 struct state_list
*slist
;
513 FOR_EACH_PTR(*slist_stack
, slist
) {
515 } END_FOR_EACH_PTR(slist
);
516 free_stack(slist_stack
);
520 * set_state_stack() sets the state for the top slist on the stack.
522 struct sm_state
*set_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
523 struct symbol
*sym
, struct smatch_state
*state
)
525 struct state_list
*slist
;
528 slist
= pop_slist(stack
);
529 sm
= set_state_slist(&slist
, owner
, name
, sym
, state
);
530 push_slist(stack
, slist
);
536 * get_sm_state_stack() gets the state for the top slist on the stack.
538 struct sm_state
*get_sm_state_stack(struct state_list_stack
*stack
,
539 int owner
, const char *name
,
542 struct state_list
*slist
;
543 struct sm_state
*ret
;
545 slist
= pop_slist(&stack
);
546 ret
= get_sm_state_slist(slist
, owner
, name
, sym
);
547 push_slist(&stack
, slist
);
552 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
553 int owner
, const char *name
,
558 sm
= get_sm_state_stack(stack
, owner
, name
, sym
);
564 static void match_states(struct state_list
**one
, struct state_list
**two
)
566 struct sm_state
*one_sm
;
567 struct sm_state
*two_sm
;
568 struct sm_state
*tmp
;
569 struct smatch_state
*tmp_state
;
570 struct state_list
*add_to_one
= NULL
;
571 struct state_list
*add_to_two
= NULL
;
573 PREPARE_PTR_LIST(*one
, one_sm
);
574 PREPARE_PTR_LIST(*two
, two_sm
);
576 if (!one_sm
&& !two_sm
)
578 if (cmp_tracker(one_sm
, two_sm
) < 0) {
579 tmp_state
= __client_unmatched_state_function(one_sm
);
580 tmp
= alloc_state_no_name(one_sm
->owner
, one_sm
->name
,
581 one_sm
->sym
, tmp_state
);
582 add_ptr_list(&add_to_two
, tmp
);
583 NEXT_PTR_LIST(one_sm
);
584 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
585 NEXT_PTR_LIST(one_sm
);
586 NEXT_PTR_LIST(two_sm
);
588 tmp_state
= __client_unmatched_state_function(two_sm
);
589 tmp
= alloc_state_no_name(two_sm
->owner
, two_sm
->name
,
590 two_sm
->sym
, tmp_state
);
591 add_ptr_list(&add_to_one
, tmp
);
592 NEXT_PTR_LIST(two_sm
);
595 FINISH_PTR_LIST(two_sm
);
596 FINISH_PTR_LIST(one_sm
);
598 overwrite_slist(add_to_one
, one
);
599 overwrite_slist(add_to_two
, two
);
602 static void clone_pool_havers(struct state_list
*slist
)
605 struct sm_state
*new;
607 FOR_EACH_PTR(slist
, sm
) {
610 REPLACE_CURRENT_PTR(sm
, new);
612 } END_FOR_EACH_PTR(sm
);
616 * merge_slist() is called whenever paths merge, such as after
617 * an if statement. It takes the two slists and creates one.
619 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
621 struct sm_state
*one_sm
, *two_sm
, *tmp
;
622 struct state_list
*results
= NULL
;
623 struct state_list
*implied_one
= NULL
;
624 struct state_list
*implied_two
= NULL
;
632 /* merging a null and nonnull path gives you only the nonnull path */
637 *to
= clone_slist(slist
);
641 implied_one
= clone_slist(*to
);
642 implied_two
= clone_slist(slist
);
644 match_states(&implied_one
, &implied_two
);
646 clone_pool_havers(implied_one
);
647 clone_pool_havers(implied_two
);
649 PREPARE_PTR_LIST(implied_one
, one_sm
);
650 PREPARE_PTR_LIST(implied_two
, two_sm
);
652 if (!one_sm
&& !two_sm
)
654 if (cmp_tracker(one_sm
, two_sm
) < 0) {
655 sm_msg("error: Internal smatch error.");
656 NEXT_PTR_LIST(one_sm
);
657 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
658 if (one_sm
!= two_sm
) {
659 one_sm
->my_pool
= implied_one
;
660 two_sm
->my_pool
= implied_two
;
663 tmp
= merge_sm_states(one_sm
, two_sm
);
664 add_ptr_list(&results
, tmp
);
665 NEXT_PTR_LIST(one_sm
);
666 NEXT_PTR_LIST(two_sm
);
668 sm_msg("error: Internal smatch error.");
669 NEXT_PTR_LIST(two_sm
);
672 FINISH_PTR_LIST(two_sm
);
673 FINISH_PTR_LIST(one_sm
);
680 * filter_slist() removes any sm states "slist" holds in common with "filter"
682 void filter_slist(struct state_list
**slist
, struct state_list
*filter
)
684 struct sm_state
*one_sm
, *two_sm
;
685 struct state_list
*results
= NULL
;
687 PREPARE_PTR_LIST(*slist
, one_sm
);
688 PREPARE_PTR_LIST(filter
, two_sm
);
690 if (!one_sm
&& !two_sm
)
692 if (cmp_tracker(one_sm
, two_sm
) < 0) {
693 add_ptr_list(&results
, one_sm
);
694 NEXT_PTR_LIST(one_sm
);
695 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
696 if (one_sm
!= two_sm
)
697 add_ptr_list(&results
, one_sm
);
698 NEXT_PTR_LIST(one_sm
);
699 NEXT_PTR_LIST(two_sm
);
701 NEXT_PTR_LIST(two_sm
);
704 FINISH_PTR_LIST(two_sm
);
705 FINISH_PTR_LIST(one_sm
);
712 * and_slist_stack() pops the top two slists, overwriting the one with
713 * the other and pushing it back on the stack.
715 void and_slist_stack(struct state_list_stack
**slist_stack
)
717 struct sm_state
*tmp
;
718 struct state_list
*right_slist
= pop_slist(slist_stack
);
720 FOR_EACH_PTR(right_slist
, tmp
) {
721 overwrite_sm_state_stack(slist_stack
, tmp
);
722 } END_FOR_EACH_PTR(tmp
);
723 free_slist(&right_slist
);
727 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
728 * It pops the two slists from the top of the stack and merges them
729 * together in a way that preserves the things they have in common
730 * but creates a merged state for most of the rest.
731 * You could have code that had: if (foo || foo) { foo->baz;
732 * It's this function which ensures smatch does the right thing.
734 void or_slist_stack(struct state_list_stack
**pre_conds
,
735 struct state_list
*cur_slist
,
736 struct state_list_stack
**slist_stack
)
738 struct state_list
*new;
739 struct state_list
*old
;
740 struct state_list
*pre_slist
;
741 struct state_list
*res
;
742 struct state_list
*tmp_slist
;
744 new = pop_slist(slist_stack
);
745 old
= pop_slist(slist_stack
);
747 pre_slist
= pop_slist(pre_conds
);
748 push_slist(pre_conds
, clone_slist(pre_slist
));
750 res
= clone_slist(pre_slist
);
751 overwrite_slist(old
, &res
);
753 tmp_slist
= clone_slist(cur_slist
);
754 overwrite_slist(new, &tmp_slist
);
756 merge_slist(&res
, tmp_slist
);
757 filter_slist(&res
, pre_slist
);
759 push_slist(slist_stack
, res
);
760 free_slist(&tmp_slist
);
761 free_slist(&pre_slist
);
767 * get_slist_from_named_stack() is only used for gotos.
769 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
772 struct named_slist
*tmp
;
774 FOR_EACH_PTR(stack
, tmp
) {
775 if (!strcmp(tmp
->name
, name
))
777 } END_FOR_EACH_PTR(tmp
);
781 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
783 struct sm_state
*tmp
;
785 FOR_EACH_PTR(from
, tmp
) {
786 overwrite_sm_state(to
, tmp
);
787 } END_FOR_EACH_PTR(tmp
);