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 char *show_sm(struct sm_state
*sm
)
31 pos
= snprintf(buf
, sizeof(buf
), "[%s] '%s' = %s (",
32 check_name(sm
->owner
), sm
->name
, show_state(sm
->state
));
34 FOR_EACH_PTR(sm
->possible
, tmp
) {
36 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, ", ");
37 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, "%s",
38 show_state(tmp
->state
));
39 } END_FOR_EACH_PTR(tmp
);
40 snprintf(buf
+ pos
, sizeof(buf
) - pos
, ")");
45 void __print_slist(struct state_list
*slist
)
49 printf("dumping slist at %d\n", get_lineno());
50 FOR_EACH_PTR(slist
, sm
) {
51 printf("%s\n", show_sm(sm
));
52 } END_FOR_EACH_PTR(sm
);
56 /* NULL states go at the end to simplify merge_slist */
57 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
68 if (a
->owner
> b
->owner
)
70 if (a
->owner
< b
->owner
)
73 ret
= strcmp(a
->name
, b
->name
);
77 if (!b
->sym
&& a
->sym
)
79 if (!a
->sym
&& b
->sym
)
89 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
93 ret
= cmp_tracker(a
, b
);
97 /* todo: add hook for smatch_extra.c */
98 if (a
->state
> b
->state
)
100 if (a
->state
< b
->state
)
105 static struct sm_state
*alloc_sm_state(int owner
, const char *name
,
106 struct symbol
*sym
, struct smatch_state
*state
)
108 struct sm_state
*sm_state
= __alloc_sm_state(0);
112 sm_state
->name
= alloc_sname(name
);
113 sm_state
->owner
= owner
;
115 sm_state
->state
= state
;
116 sm_state
->line
= get_lineno();
117 sm_state
->merged
= 0;
118 sm_state
->implied
= 0;
119 sm_state
->my_pool
= NULL
;
120 sm_state
->left
= NULL
;
121 sm_state
->right
= NULL
;
122 sm_state
->nr_children
= 1;
123 sm_state
->possible
= NULL
;
124 add_ptr_list(&sm_state
->possible
, sm_state
);
128 static struct sm_state
*alloc_state_no_name(int owner
, const char *name
,
130 struct smatch_state
*state
)
132 struct sm_state
*tmp
;
134 tmp
= alloc_sm_state(owner
, NULL
, sym
, state
);
139 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
141 struct sm_state
*tmp
;
143 FOR_EACH_PTR(*slist
, tmp
) {
144 if (cmp_sm_states(tmp
, new) < 0)
146 else if (cmp_sm_states(tmp
, new) == 0) {
149 INSERT_CURRENT(new, tmp
);
152 } END_FOR_EACH_PTR(tmp
);
153 add_ptr_list(slist
, new);
156 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
158 struct sm_state
*tmp
;
159 struct sm_state
*tmp2
;
161 FOR_EACH_PTR(new->possible
, tmp
) {
162 tmp2
= alloc_state_no_name(tmp
->owner
, tmp
->name
, tmp
->sym
,
164 tmp2
->line
= tmp
->line
;
165 add_sm_state_slist(&sm
->possible
, tmp2
);
166 } END_FOR_EACH_PTR(tmp
);
169 char *alloc_sname(const char *str
)
175 tmp
= __alloc_sname(strlen(str
) + 1);
183 * I decided to use 50M here based on trial and error.
184 * It works out OK for the kernel and so it should work
185 * for most other projects as well.
187 if (sm_state_counter
* sizeof(struct sm_state
) >= 50000000)
192 static void free_sm_state(struct sm_state
*sm
)
194 free_slist(&sm
->possible
);
196 * fixme. Free the actual state.
197 * Right now we leave it until the end of the function
198 * because we don't want to double free it.
199 * Use the freelist to not double free things
203 static void free_all_sm_states(struct allocation_blob
*blob
)
205 unsigned int size
= sizeof(struct sm_state
);
206 unsigned int offset
= 0;
208 while (offset
< blob
->offset
) {
209 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
214 /* At the end of every function we free all the sm_states */
215 void free_every_single_sm_state(void)
217 struct allocator_struct
*desc
= &sm_state_allocator
;
218 struct allocation_blob
*blob
= desc
->blobs
;
221 desc
->allocations
= 0;
222 desc
->total_bytes
= 0;
223 desc
->useful_bytes
= 0;
224 desc
->freelist
= NULL
;
226 struct allocation_blob
*next
= blob
->next
;
227 free_all_sm_states(blob
);
228 blob_free(blob
, desc
->chunking
);
233 sm_state_counter
= 0;
236 struct sm_state
*clone_sm(struct sm_state
*s
)
238 struct sm_state
*ret
;
240 ret
= alloc_state_no_name(s
->owner
, s
->name
, s
->sym
, s
->state
);
241 ret
->merged
= s
->merged
;
242 ret
->implied
= s
->implied
;
244 /* clone_sm() doesn't copy the my_pools. Each state needs to have
246 ret
->possible
= clone_slist(s
->possible
);
248 ret
->right
= s
->right
;
249 ret
->nr_children
= s
->nr_children
;
253 int is_merged(struct sm_state
*sm
)
258 int is_implied(struct sm_state
*sm
)
263 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
265 struct sm_state
*tmp
;
267 FOR_EACH_PTR(slist
, tmp
) {
268 if (tmp
->state
== state
)
270 } END_FOR_EACH_PTR(tmp
);
274 static void check_order(struct state_list
*slist
)
278 struct sm_state
*last
= NULL
;
281 FOR_EACH_PTR(slist
, sm
) {
282 if (last
&& cmp_tracker(sm
, last
) <= 0) {
283 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
284 "%s vs %s\n", last
->owner
, sm
->owner
,
285 last
->sym
, sm
->sym
, last
->name
, sm
->name
);
289 } END_FOR_EACH_PTR(sm
);
296 struct state_list
*clone_slist(struct state_list
*from_slist
)
299 struct state_list
*to_slist
= NULL
;
301 FOR_EACH_PTR(from_slist
, sm
) {
302 add_ptr_list(&to_slist
, sm
);
303 } END_FOR_EACH_PTR(sm
);
304 check_order(to_slist
);
308 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
310 struct state_list
*slist
;
311 struct state_list_stack
*to_stack
= NULL
;
313 FOR_EACH_PTR(from_stack
, slist
) {
314 push_slist(&to_stack
, slist
);
315 } END_FOR_EACH_PTR(slist
);
319 struct smatch_state
*merge_states(int owner
, const char *name
,
321 struct smatch_state
*state1
,
322 struct smatch_state
*state2
)
324 struct smatch_state
*ret
;
326 if (state1
== state2
)
328 else if (__has_merge_function(owner
))
329 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
330 else if (!state1
|| !state2
)
338 * add_pool() adds a slist to ->pools. If the slist has already been
339 * added earlier then it doesn't get added a second time.
341 void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
343 struct state_list
*tmp
;
345 FOR_EACH_PTR(*pools
, tmp
) {
348 else if (tmp
== new) {
351 INSERT_CURRENT(new, tmp
);
354 } END_FOR_EACH_PTR(tmp
);
355 add_ptr_list(pools
, new);
358 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
360 struct smatch_state
*s
;
361 struct sm_state
*result
;
365 s
= merge_states(one
->owner
, one
->name
, one
->sym
, one
->state
, two
->state
);
366 result
= alloc_state_no_name(one
->owner
, one
->name
, one
->sym
, s
);
370 result
->nr_children
= one
->nr_children
+ two
->nr_children
;
371 add_possible(result
, one
);
372 add_possible(result
, two
);
375 struct sm_state
*tmp
;
378 printf("%d merge name='%s' [%s] %s(L %d) + %s(L %d) => %s (",
379 get_lineno(), one
->name
, check_name(one
->owner
),
380 show_state(one
->state
), one
->line
,
381 show_state(two
->state
), two
->line
,
384 FOR_EACH_PTR(result
->possible
, tmp
) {
387 printf("%s", show_state(tmp
->state
));
388 } END_FOR_EACH_PTR(tmp
);
395 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, int owner
, const char *name
,
403 FOR_EACH_PTR(slist
, sm
) {
404 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
))
406 } END_FOR_EACH_PTR(sm
);
410 struct smatch_state
*get_state_slist(struct state_list
*slist
,
411 int owner
, const char *name
,
416 sm
= get_sm_state_slist(slist
, owner
, name
, sym
);
422 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
424 struct sm_state
*tmp
;
426 FOR_EACH_PTR(*slist
, tmp
) {
427 if (cmp_tracker(tmp
, new) < 0)
429 else if (cmp_tracker(tmp
, new) == 0) {
430 REPLACE_CURRENT_PTR(tmp
, new);
433 INSERT_CURRENT(new, tmp
);
436 } END_FOR_EACH_PTR(tmp
);
437 add_ptr_list(slist
, new);
440 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
443 struct state_list
*slist
;
445 slist
= pop_slist(stack
);
446 overwrite_sm_state(&slist
, sm
);
447 push_slist(stack
, slist
);
450 struct sm_state
*set_state_slist(struct state_list
**slist
, int owner
, const char *name
,
451 struct symbol
*sym
, struct smatch_state
*state
)
453 struct sm_state
*tmp
;
454 struct sm_state
*new = alloc_sm_state(owner
, name
, sym
, state
);
456 FOR_EACH_PTR(*slist
, tmp
) {
457 if (cmp_tracker(tmp
, new) < 0)
459 else if (cmp_tracker(tmp
, new) == 0) {
460 REPLACE_CURRENT_PTR(tmp
, new);
463 INSERT_CURRENT(new, tmp
);
466 } END_FOR_EACH_PTR(tmp
);
467 add_ptr_list(slist
, new);
471 void delete_state_slist(struct state_list
**slist
, int owner
, const char *name
,
476 FOR_EACH_PTR(*slist
, sm
) {
477 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
)) {
478 DELETE_CURRENT_PTR(sm
);
481 } END_FOR_EACH_PTR(sm
);
484 void delete_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
487 struct state_list
*slist
;
489 slist
= pop_slist(stack
);
490 delete_state_slist(&slist
, owner
, name
, sym
);
491 push_slist(stack
, slist
);
494 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
496 add_ptr_list(list_stack
, slist
);
499 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
501 struct state_list
*slist
;
503 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
504 delete_ptr_list_last((struct ptr_list
**)list_stack
);
508 void free_slist(struct state_list
**slist
)
510 __free_ptr_list((struct ptr_list
**)slist
);
513 void free_stack(struct state_list_stack
**stack
)
515 __free_ptr_list((struct ptr_list
**)stack
);
518 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
520 struct state_list
*slist
;
522 FOR_EACH_PTR(*slist_stack
, slist
) {
524 } END_FOR_EACH_PTR(slist
);
525 free_stack(slist_stack
);
529 * set_state_stack() sets the state for the top slist on the stack.
531 struct sm_state
*set_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
532 struct symbol
*sym
, struct smatch_state
*state
)
534 struct state_list
*slist
;
537 slist
= pop_slist(stack
);
538 sm
= set_state_slist(&slist
, owner
, name
, sym
, state
);
539 push_slist(stack
, slist
);
545 * get_sm_state_stack() gets the state for the top slist on the stack.
547 struct sm_state
*get_sm_state_stack(struct state_list_stack
*stack
,
548 int owner
, const char *name
,
551 struct state_list
*slist
;
552 struct sm_state
*ret
;
554 slist
= pop_slist(&stack
);
555 ret
= get_sm_state_slist(slist
, owner
, name
, sym
);
556 push_slist(&stack
, slist
);
560 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
561 int owner
, const char *name
,
566 sm
= get_sm_state_stack(stack
, owner
, name
, sym
);
572 static void match_states(struct state_list
**one
, struct state_list
**two
)
574 struct sm_state
*one_sm
;
575 struct sm_state
*two_sm
;
576 struct sm_state
*tmp
;
577 struct smatch_state
*tmp_state
;
578 struct state_list
*add_to_one
= NULL
;
579 struct state_list
*add_to_two
= NULL
;
581 PREPARE_PTR_LIST(*one
, one_sm
);
582 PREPARE_PTR_LIST(*two
, two_sm
);
584 if (!one_sm
&& !two_sm
)
586 if (cmp_tracker(one_sm
, two_sm
) < 0) {
587 tmp_state
= __client_unmatched_state_function(one_sm
);
588 tmp
= alloc_state_no_name(one_sm
->owner
, one_sm
->name
,
589 one_sm
->sym
, tmp_state
);
590 add_ptr_list(&add_to_two
, tmp
);
591 NEXT_PTR_LIST(one_sm
);
592 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
593 NEXT_PTR_LIST(one_sm
);
594 NEXT_PTR_LIST(two_sm
);
596 tmp_state
= __client_unmatched_state_function(two_sm
);
597 tmp
= alloc_state_no_name(two_sm
->owner
, two_sm
->name
,
598 two_sm
->sym
, tmp_state
);
599 add_ptr_list(&add_to_one
, tmp
);
600 NEXT_PTR_LIST(two_sm
);
603 FINISH_PTR_LIST(two_sm
);
604 FINISH_PTR_LIST(one_sm
);
606 overwrite_slist(add_to_one
, one
);
607 overwrite_slist(add_to_two
, two
);
610 static void clone_pool_havers(struct state_list
*slist
)
613 struct sm_state
*new;
615 FOR_EACH_PTR(slist
, sm
) {
618 REPLACE_CURRENT_PTR(sm
, new);
620 } END_FOR_EACH_PTR(sm
);
624 * merge_slist() is called whenever paths merge, such as after
625 * an if statement. It takes the two slists and creates one.
627 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
629 struct sm_state
*one_sm
, *two_sm
, *tmp
;
630 struct state_list
*results
= NULL
;
631 struct state_list
*implied_one
= NULL
;
632 struct state_list
*implied_two
= NULL
;
640 /* merging a null and nonnull path gives you only the nonnull path */
645 *to
= clone_slist(slist
);
649 implied_one
= clone_slist(*to
);
650 implied_two
= clone_slist(slist
);
652 match_states(&implied_one
, &implied_two
);
654 clone_pool_havers(implied_one
);
655 clone_pool_havers(implied_two
);
657 PREPARE_PTR_LIST(implied_one
, one_sm
);
658 PREPARE_PTR_LIST(implied_two
, two_sm
);
660 if (!one_sm
&& !two_sm
)
662 if (cmp_tracker(one_sm
, two_sm
) < 0) {
663 sm_msg("error: Internal smatch error.");
664 NEXT_PTR_LIST(one_sm
);
665 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
666 if (one_sm
!= two_sm
) {
667 one_sm
->my_pool
= implied_one
;
668 two_sm
->my_pool
= implied_two
;
671 tmp
= merge_sm_states(one_sm
, two_sm
);
672 add_ptr_list(&results
, tmp
);
673 NEXT_PTR_LIST(one_sm
);
674 NEXT_PTR_LIST(two_sm
);
676 sm_msg("error: Internal smatch error.");
677 NEXT_PTR_LIST(two_sm
);
680 FINISH_PTR_LIST(two_sm
);
681 FINISH_PTR_LIST(one_sm
);
688 * filter_slist() removes any sm states "slist" holds in common with "filter"
690 void filter_slist(struct state_list
**slist
, struct state_list
*filter
)
692 struct sm_state
*one_sm
, *two_sm
;
693 struct state_list
*results
= NULL
;
695 PREPARE_PTR_LIST(*slist
, one_sm
);
696 PREPARE_PTR_LIST(filter
, two_sm
);
698 if (!one_sm
&& !two_sm
)
700 if (cmp_tracker(one_sm
, two_sm
) < 0) {
701 add_ptr_list(&results
, one_sm
);
702 NEXT_PTR_LIST(one_sm
);
703 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
704 if (one_sm
!= two_sm
)
705 add_ptr_list(&results
, one_sm
);
706 NEXT_PTR_LIST(one_sm
);
707 NEXT_PTR_LIST(two_sm
);
709 NEXT_PTR_LIST(two_sm
);
712 FINISH_PTR_LIST(two_sm
);
713 FINISH_PTR_LIST(one_sm
);
720 * and_slist_stack() pops the top two slists, overwriting the one with
721 * the other and pushing it back on the stack.
723 void and_slist_stack(struct state_list_stack
**slist_stack
)
725 struct sm_state
*tmp
;
726 struct state_list
*right_slist
= pop_slist(slist_stack
);
728 FOR_EACH_PTR(right_slist
, tmp
) {
729 overwrite_sm_state_stack(slist_stack
, tmp
);
730 } END_FOR_EACH_PTR(tmp
);
731 free_slist(&right_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
**pre_conds
,
743 struct state_list
*cur_slist
,
744 struct state_list_stack
**slist_stack
)
746 struct state_list
*new;
747 struct state_list
*old
;
748 struct state_list
*pre_slist
;
749 struct state_list
*res
;
750 struct state_list
*tmp_slist
;
752 new = pop_slist(slist_stack
);
753 old
= pop_slist(slist_stack
);
755 pre_slist
= pop_slist(pre_conds
);
756 push_slist(pre_conds
, clone_slist(pre_slist
));
758 res
= clone_slist(pre_slist
);
759 overwrite_slist(old
, &res
);
761 tmp_slist
= clone_slist(cur_slist
);
762 overwrite_slist(new, &tmp_slist
);
764 merge_slist(&res
, tmp_slist
);
765 filter_slist(&res
, pre_slist
);
767 push_slist(slist_stack
, res
);
768 free_slist(&tmp_slist
);
769 free_slist(&pre_slist
);
775 * get_slist_from_named_stack() is only used for gotos.
777 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
780 struct named_slist
*tmp
;
782 FOR_EACH_PTR(stack
, tmp
) {
783 if (!strcmp(tmp
->name
, name
))
785 } END_FOR_EACH_PTR(tmp
);
789 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
791 struct sm_state
*tmp
;
793 FOR_EACH_PTR(from
, tmp
) {
794 overwrite_sm_state(to
, tmp
);
795 } END_FOR_EACH_PTR(tmp
);