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, 1, 4, "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
));
33 if (pos
> sizeof(buf
))
37 FOR_EACH_PTR(sm
->possible
, tmp
) {
39 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, ", ");
40 if (pos
> sizeof(buf
))
42 pos
+= snprintf(buf
+ pos
, sizeof(buf
) - pos
, "%s",
43 show_state(tmp
->state
));
44 if (pos
> sizeof(buf
))
46 } END_FOR_EACH_PTR(tmp
);
47 snprintf(buf
+ pos
, sizeof(buf
) - pos
, ")");
52 for (i
= 0; i
< 3; i
++)
53 buf
[sizeof(buf
) - 2 - i
] = '.';
57 void __print_slist(struct state_list
*slist
)
61 printf("dumping slist at %d\n", get_lineno());
62 FOR_EACH_PTR(slist
, sm
) {
63 printf("%s\n", show_sm(sm
));
64 } END_FOR_EACH_PTR(sm
);
68 /* NULL states go at the end to simplify merge_slist */
69 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
80 if (a
->owner
> b
->owner
)
82 if (a
->owner
< b
->owner
)
85 ret
= strcmp(a
->name
, b
->name
);
89 if (!b
->sym
&& a
->sym
)
91 if (!a
->sym
&& b
->sym
)
101 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
105 ret
= cmp_tracker(a
, b
);
109 /* todo: add hook for smatch_extra.c */
110 if (a
->state
> b
->state
)
112 if (a
->state
< b
->state
)
117 static struct sm_state
*alloc_sm_state(int owner
, const char *name
,
118 struct symbol
*sym
, struct smatch_state
*state
)
120 struct sm_state
*sm_state
= __alloc_sm_state(0);
124 sm_state
->name
= alloc_sname(name
);
125 sm_state
->owner
= owner
;
127 sm_state
->state
= state
;
128 sm_state
->line
= get_lineno();
129 sm_state
->merged
= 0;
130 sm_state
->implied
= 0;
131 sm_state
->pool
= NULL
;
132 sm_state
->left
= NULL
;
133 sm_state
->right
= NULL
;
134 sm_state
->nr_children
= 1;
135 sm_state
->possible
= NULL
;
136 add_ptr_list(&sm_state
->possible
, sm_state
);
140 static struct sm_state
*alloc_state_no_name(int owner
, const char *name
,
142 struct smatch_state
*state
)
144 struct sm_state
*tmp
;
146 tmp
= alloc_sm_state(owner
, NULL
, sym
, state
);
151 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
153 struct sm_state
*tmp
;
155 FOR_EACH_PTR(*slist
, tmp
) {
156 if (cmp_sm_states(tmp
, new) < 0)
158 else if (cmp_sm_states(tmp
, new) == 0) {
161 INSERT_CURRENT(new, tmp
);
164 } END_FOR_EACH_PTR(tmp
);
165 add_ptr_list(slist
, new);
168 static void copy_possibles(struct sm_state
*to
, struct sm_state
*from
)
170 struct sm_state
*tmp
;
172 FOR_EACH_PTR(from
->possible
, tmp
) {
173 add_sm_state_slist(&to
->possible
, tmp
);
174 } END_FOR_EACH_PTR(tmp
);
177 char *alloc_sname(const char *str
)
183 tmp
= __alloc_sname(strlen(str
) + 1);
191 * I decided to use 50M here based on trial and error.
192 * It works out OK for the kernel and so it should work
193 * for most other projects as well.
195 if (sm_state_counter
* sizeof(struct sm_state
) >= 50000000)
200 int low_on_memory(void)
202 if (sm_state_counter
* sizeof(struct sm_state
) >= 25000000)
207 static void free_sm_state(struct sm_state
*sm
)
209 free_slist(&sm
->possible
);
211 * fixme. Free the actual state.
212 * Right now we leave it until the end of the function
213 * because we don't want to double free it.
214 * Use the freelist to not double free things
218 static void free_all_sm_states(struct allocation_blob
*blob
)
220 unsigned int size
= sizeof(struct sm_state
);
221 unsigned int offset
= 0;
223 while (offset
< blob
->offset
) {
224 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
229 /* At the end of every function we free all the sm_states */
230 void free_every_single_sm_state(void)
232 struct allocator_struct
*desc
= &sm_state_allocator
;
233 struct allocation_blob
*blob
= desc
->blobs
;
236 desc
->allocations
= 0;
237 desc
->total_bytes
= 0;
238 desc
->useful_bytes
= 0;
239 desc
->freelist
= NULL
;
241 struct allocation_blob
*next
= blob
->next
;
242 free_all_sm_states(blob
);
243 blob_free(blob
, desc
->chunking
);
247 clear_smatch_state_alloc();
249 sm_state_counter
= 0;
252 struct sm_state
*clone_sm(struct sm_state
*s
)
254 struct sm_state
*ret
;
256 ret
= alloc_state_no_name(s
->owner
, s
->name
, s
->sym
, s
->state
);
257 ret
->merged
= s
->merged
;
258 ret
->implied
= s
->implied
;
260 /* clone_sm() doesn't copy the pools. Each state needs to have
262 ret
->possible
= clone_slist(s
->possible
);
264 ret
->right
= s
->right
;
265 ret
->nr_children
= s
->nr_children
;
269 int is_merged(struct sm_state
*sm
)
274 int is_implied(struct sm_state
*sm
)
279 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
281 struct sm_state
*tmp
;
283 FOR_EACH_PTR(slist
, tmp
) {
284 if (tmp
->state
== state
)
286 } END_FOR_EACH_PTR(tmp
);
290 static void check_order(struct state_list
*slist
)
294 struct sm_state
*last
= NULL
;
297 FOR_EACH_PTR(slist
, sm
) {
298 if (last
&& cmp_tracker(sm
, last
) <= 0) {
299 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
300 "%s vs %s\n", last
->owner
, sm
->owner
,
301 last
->sym
, sm
->sym
, last
->name
, sm
->name
);
305 } END_FOR_EACH_PTR(sm
);
312 struct state_list
*clone_slist(struct state_list
*from_slist
)
315 struct state_list
*to_slist
= NULL
;
317 FOR_EACH_PTR(from_slist
, sm
) {
318 add_ptr_list(&to_slist
, sm
);
319 } END_FOR_EACH_PTR(sm
);
323 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
325 struct state_list
*slist
;
326 struct state_list_stack
*to_stack
= NULL
;
328 FOR_EACH_PTR(from_stack
, slist
) {
329 push_slist(&to_stack
, slist
);
330 } END_FOR_EACH_PTR(slist
);
334 struct smatch_state
*merge_states(int owner
, const char *name
,
336 struct smatch_state
*state1
,
337 struct smatch_state
*state2
)
339 struct smatch_state
*ret
;
341 if (state1
== state2
)
343 else if (__has_merge_function(owner
))
344 ret
= __client_merge_function(owner
, state1
, state2
);
345 else if (!state1
|| !state2
)
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
;
359 s
= merge_states(one
->owner
, one
->name
, one
->sym
, one
->state
, two
->state
);
360 result
= alloc_state_no_name(one
->owner
, one
->name
, one
->sym
, s
);
364 result
->nr_children
= one
->nr_children
+ two
->nr_children
;
365 copy_possibles(result
, one
);
366 copy_possibles(result
, two
);
369 strcmp(check_name(one
->owner
), option_debug_check
) == 0) {
370 struct sm_state
*tmp
;
373 printf("%d merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
374 get_lineno(), check_name(one
->owner
), one
->name
,
375 show_state(one
->state
), one
->line
,
376 show_state(two
->state
), two
->line
,
379 FOR_EACH_PTR(result
->possible
, tmp
) {
382 printf("%s", show_state(tmp
->state
));
383 } END_FOR_EACH_PTR(tmp
);
390 struct sm_state
*get_sm_state_slist(struct state_list
*slist
, int owner
, const char *name
,
398 FOR_EACH_PTR(slist
, sm
) {
399 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
))
401 } END_FOR_EACH_PTR(sm
);
405 struct smatch_state
*get_state_slist(struct state_list
*slist
,
406 int owner
, const char *name
,
411 sm
= get_sm_state_slist(slist
, owner
, name
, sym
);
417 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
419 struct sm_state
*tmp
;
421 FOR_EACH_PTR(*slist
, tmp
) {
422 if (cmp_tracker(tmp
, new) < 0)
424 else if (cmp_tracker(tmp
, new) == 0) {
425 REPLACE_CURRENT_PTR(tmp
, new);
428 INSERT_CURRENT(new, tmp
);
431 } END_FOR_EACH_PTR(tmp
);
432 add_ptr_list(slist
, new);
435 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
438 struct state_list
*slist
;
440 slist
= pop_slist(stack
);
441 overwrite_sm_state(&slist
, sm
);
442 push_slist(stack
, slist
);
445 struct sm_state
*set_state_slist(struct state_list
**slist
, int owner
, const char *name
,
446 struct symbol
*sym
, struct smatch_state
*state
)
448 struct sm_state
*tmp
;
449 struct sm_state
*new = alloc_sm_state(owner
, name
, sym
, state
);
451 FOR_EACH_PTR(*slist
, tmp
) {
452 if (cmp_tracker(tmp
, new) < 0)
454 else if (cmp_tracker(tmp
, new) == 0) {
455 REPLACE_CURRENT_PTR(tmp
, new);
458 INSERT_CURRENT(new, tmp
);
461 } END_FOR_EACH_PTR(tmp
);
462 add_ptr_list(slist
, new);
466 void delete_state_slist(struct state_list
**slist
, int owner
, const char *name
,
471 FOR_EACH_PTR(*slist
, sm
) {
472 if (sm
->owner
== owner
&& sm
->sym
== sym
&& !strcmp(sm
->name
, name
)) {
473 DELETE_CURRENT_PTR(sm
);
476 } END_FOR_EACH_PTR(sm
);
479 void delete_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
482 struct state_list
*slist
;
484 slist
= pop_slist(stack
);
485 delete_state_slist(&slist
, owner
, name
, sym
);
486 push_slist(stack
, slist
);
489 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
491 add_ptr_list(list_stack
, slist
);
494 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
496 struct state_list
*slist
;
498 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
499 delete_ptr_list_last((struct ptr_list
**)list_stack
);
503 void free_slist(struct state_list
**slist
)
505 __free_ptr_list((struct ptr_list
**)slist
);
508 void free_stack(struct state_list_stack
**stack
)
510 __free_ptr_list((struct ptr_list
**)stack
);
513 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
515 struct state_list
*slist
;
517 FOR_EACH_PTR(*slist_stack
, slist
) {
519 } END_FOR_EACH_PTR(slist
);
520 free_stack(slist_stack
);
524 * set_state_stack() sets the state for the top slist on the stack.
526 struct sm_state
*set_state_stack(struct state_list_stack
**stack
, int owner
, const char *name
,
527 struct symbol
*sym
, struct smatch_state
*state
)
529 struct state_list
*slist
;
532 slist
= pop_slist(stack
);
533 sm
= set_state_slist(&slist
, owner
, name
, sym
, state
);
534 push_slist(stack
, slist
);
540 * get_sm_state_stack() gets the state for the top slist on the stack.
542 struct sm_state
*get_sm_state_stack(struct state_list_stack
*stack
,
543 int owner
, const char *name
,
546 struct state_list
*slist
;
547 struct sm_state
*ret
;
549 slist
= pop_slist(&stack
);
550 ret
= get_sm_state_slist(slist
, owner
, name
, sym
);
551 push_slist(&stack
, slist
);
555 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
556 int owner
, const char *name
,
561 sm
= get_sm_state_stack(stack
, owner
, name
, sym
);
567 static void match_states(struct state_list
**one
, struct state_list
**two
)
569 struct sm_state
*one_sm
;
570 struct sm_state
*two_sm
;
571 struct sm_state
*tmp
;
572 struct smatch_state
*tmp_state
;
573 struct state_list
*add_to_one
= NULL
;
574 struct state_list
*add_to_two
= NULL
;
576 PREPARE_PTR_LIST(*one
, one_sm
);
577 PREPARE_PTR_LIST(*two
, two_sm
);
579 if (!one_sm
&& !two_sm
)
581 if (cmp_tracker(one_sm
, two_sm
) < 0) {
582 __set_fake_cur_slist_fast(*two
);
583 tmp_state
= __client_unmatched_state_function(one_sm
);
584 __pop_fake_cur_slist_fast();
585 tmp
= alloc_state_no_name(one_sm
->owner
, one_sm
->name
,
586 one_sm
->sym
, tmp_state
);
587 add_ptr_list(&add_to_two
, tmp
);
588 NEXT_PTR_LIST(one_sm
);
589 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
590 NEXT_PTR_LIST(one_sm
);
591 NEXT_PTR_LIST(two_sm
);
593 __set_fake_cur_slist_fast(*one
);
594 tmp_state
= __client_unmatched_state_function(two_sm
);
595 __pop_fake_cur_slist_fast();
596 tmp
= alloc_state_no_name(two_sm
->owner
, two_sm
->name
,
597 two_sm
->sym
, tmp_state
);
598 add_ptr_list(&add_to_one
, tmp
);
599 NEXT_PTR_LIST(two_sm
);
602 FINISH_PTR_LIST(two_sm
);
603 FINISH_PTR_LIST(one_sm
);
605 overwrite_slist(add_to_one
, one
);
606 overwrite_slist(add_to_two
, two
);
609 static void clone_pool_havers(struct state_list
*slist
)
612 struct sm_state
*new;
614 FOR_EACH_PTR(slist
, sm
) {
617 REPLACE_CURRENT_PTR(sm
, new);
619 } END_FOR_EACH_PTR(sm
);
624 * Sets the first state to the slist_id.
626 static void set_slist_id(struct state_list
*slist
)
628 struct smatch_state
*state
;
629 struct sm_state
*tmp
, *new;
631 state
= alloc_state_num(++__slist_id
);
632 new = alloc_sm_state(-1, "unnull_path", NULL
, state
);
634 FOR_EACH_PTR(slist
, tmp
) {
635 if (tmp
->owner
!= (unsigned short)-1)
637 REPLACE_CURRENT_PTR(tmp
, new);
639 } END_FOR_EACH_PTR(tmp
);
642 int get_slist_id(struct state_list
*slist
)
644 struct sm_state
*tmp
;
646 FOR_EACH_PTR(slist
, tmp
) {
647 if (tmp
->owner
!= (unsigned short)-1)
649 return PTR_INT(tmp
->state
->data
);
650 } END_FOR_EACH_PTR(tmp
);
655 * merge_slist() is called whenever paths merge, such as after
656 * an if statement. It takes the two slists and creates one.
658 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
660 struct sm_state
*one_sm
, *two_sm
, *tmp
;
661 struct state_list
*results
= NULL
;
662 struct state_list
*implied_one
= NULL
;
663 struct state_list
*implied_two
= NULL
;
671 /* merging a null and nonnull path gives you only the nonnull path */
676 *to
= clone_slist(slist
);
680 implied_one
= clone_slist(*to
);
681 implied_two
= clone_slist(slist
);
683 match_states(&implied_one
, &implied_two
);
685 clone_pool_havers(implied_one
);
686 clone_pool_havers(implied_two
);
688 set_slist_id(implied_one
);
689 set_slist_id(implied_two
);
691 PREPARE_PTR_LIST(implied_one
, one_sm
);
692 PREPARE_PTR_LIST(implied_two
, two_sm
);
694 if (!one_sm
&& !two_sm
)
696 if (cmp_tracker(one_sm
, two_sm
) < 0) {
697 sm_msg("error: Internal smatch error.");
698 NEXT_PTR_LIST(one_sm
);
699 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
700 if (one_sm
!= two_sm
) {
701 one_sm
->pool
= implied_one
;
702 two_sm
->pool
= implied_two
;
705 tmp
= merge_sm_states(one_sm
, two_sm
);
706 add_ptr_list(&results
, tmp
);
707 NEXT_PTR_LIST(one_sm
);
708 NEXT_PTR_LIST(two_sm
);
710 sm_msg("error: Internal smatch error.");
711 NEXT_PTR_LIST(two_sm
);
714 FINISH_PTR_LIST(two_sm
);
715 FINISH_PTR_LIST(one_sm
);
722 * filter_slist() removes any sm states "slist" holds in common with "filter"
724 void filter_slist(struct state_list
**slist
, struct state_list
*filter
)
726 struct sm_state
*one_sm
, *two_sm
;
727 struct state_list
*results
= NULL
;
729 PREPARE_PTR_LIST(*slist
, one_sm
);
730 PREPARE_PTR_LIST(filter
, two_sm
);
732 if (!one_sm
&& !two_sm
)
734 if (cmp_tracker(one_sm
, two_sm
) < 0) {
735 add_ptr_list(&results
, one_sm
);
736 NEXT_PTR_LIST(one_sm
);
737 } else if (cmp_tracker(one_sm
, two_sm
) == 0) {
738 if (one_sm
!= two_sm
)
739 add_ptr_list(&results
, one_sm
);
740 NEXT_PTR_LIST(one_sm
);
741 NEXT_PTR_LIST(two_sm
);
743 NEXT_PTR_LIST(two_sm
);
746 FINISH_PTR_LIST(two_sm
);
747 FINISH_PTR_LIST(one_sm
);
754 * and_slist_stack() pops the top two slists, overwriting the one with
755 * the other and pushing it back on the stack.
757 void and_slist_stack(struct state_list_stack
**slist_stack
)
759 struct sm_state
*tmp
;
760 struct state_list
*right_slist
= pop_slist(slist_stack
);
762 FOR_EACH_PTR(right_slist
, tmp
) {
763 overwrite_sm_state_stack(slist_stack
, tmp
);
764 } END_FOR_EACH_PTR(tmp
);
765 free_slist(&right_slist
);
769 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
770 * It pops the two slists from the top of the stack and merges them
771 * together in a way that preserves the things they have in common
772 * but creates a merged state for most of the rest.
773 * You could have code that had: if (foo || foo) { foo->baz;
774 * It's this function which ensures smatch does the right thing.
776 void or_slist_stack(struct state_list_stack
**pre_conds
,
777 struct state_list
*cur_slist
,
778 struct state_list_stack
**slist_stack
)
780 struct state_list
*new;
781 struct state_list
*old
;
782 struct state_list
*pre_slist
;
783 struct state_list
*res
;
784 struct state_list
*tmp_slist
;
786 new = pop_slist(slist_stack
);
787 old
= pop_slist(slist_stack
);
789 pre_slist
= pop_slist(pre_conds
);
790 push_slist(pre_conds
, clone_slist(pre_slist
));
792 res
= clone_slist(pre_slist
);
793 overwrite_slist(old
, &res
);
795 tmp_slist
= clone_slist(cur_slist
);
796 overwrite_slist(new, &tmp_slist
);
798 merge_slist(&res
, tmp_slist
);
799 filter_slist(&res
, pre_slist
);
801 push_slist(slist_stack
, res
);
802 free_slist(&tmp_slist
);
803 free_slist(&pre_slist
);
809 * get_slist_from_named_stack() is only used for gotos.
811 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
814 struct named_slist
*tmp
;
816 FOR_EACH_PTR(stack
, tmp
) {
817 if (!strcmp(tmp
->name
, name
))
819 } END_FOR_EACH_PTR(tmp
);
823 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
825 struct sm_state
*tmp
;
827 FOR_EACH_PTR(from
, tmp
) {
828 overwrite_sm_state(to
, tmp
);
829 } END_FOR_EACH_PTR(tmp
);