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"
18 ALLOCATOR(sm_state
, "smatch state");
19 ALLOCATOR(named_slist
, "named slist");
21 void __print_slist(struct state_list
*slist
)
23 struct sm_state
*state
;
24 struct sm_state
*poss
;
27 printf("dumping slist at %d\n", get_lineno());
28 FOR_EACH_PTR(slist
, state
) {
29 printf("%d '%s'=%s (", state
->owner
, state
->name
,
30 show_state(state
->state
));
32 FOR_EACH_PTR(state
->possible
, poss
) {
35 printf("%s", show_state(poss
->state
));
36 } END_FOR_EACH_PTR(poss
);
38 } END_FOR_EACH_PTR(state
);
43 /* NULL states go at the end to simplify merge_slist */
44 int cmp_tracker(const struct sm_state
*a
, const struct sm_state
*b
)
55 if (a
->owner
> b
->owner
)
57 if (a
->owner
< b
->owner
)
60 ret
= strcmp(a
->name
, b
->name
);
64 if (!b
->sym
&& a
->sym
)
66 if (!a
->sym
&& b
->sym
)
76 static int cmp_sm_states(const struct sm_state
*a
, const struct sm_state
*b
)
80 ret
= cmp_tracker(a
, b
);
84 /* todo: add hook for smatch_extra.c */
85 if (a
->state
> b
->state
)
87 if (a
->state
< b
->state
)
92 void add_sm_state_slist(struct state_list
**slist
, struct sm_state
*new)
96 FOR_EACH_PTR(*slist
, tmp
) {
97 if (cmp_sm_states(tmp
, new) < 0)
99 else if (cmp_sm_states(tmp
, new) == 0) {
102 INSERT_CURRENT(new, tmp
);
105 } END_FOR_EACH_PTR(tmp
);
106 add_ptr_list(slist
, new);
109 static void add_possible(struct sm_state
*sm
, struct sm_state
*new)
111 struct sm_state
*tmp
;
112 struct sm_state
*tmp2
;
115 struct smatch_state
*s
;
117 s
= merge_states(sm
->name
, sm
->owner
, sm
->sym
, sm
->state
, NULL
);
118 tmp
= alloc_state(sm
->name
, sm
->owner
, sm
->sym
, s
);
119 add_sm_state_slist(&sm
->possible
, tmp
);
123 FOR_EACH_PTR(new->possible
, tmp
) {
124 tmp2
= alloc_state(tmp
->name
, tmp
->owner
, tmp
->sym
, tmp
->state
);
125 add_sm_state_slist(&sm
->possible
, tmp2
);
126 } END_FOR_EACH_PTR(tmp
);
129 struct sm_state
*alloc_state(const char *name
, int owner
,
130 struct symbol
*sym
, struct smatch_state
*state
)
132 struct sm_state
*sm_state
= __alloc_sm_state(0);
134 sm_state
->name
= alloc_string(name
);
135 sm_state
->owner
= owner
;
137 sm_state
->state
= state
;
138 sm_state
->line
= get_lineno();
139 sm_state
->my_pools
= NULL
;
140 sm_state
->all_pools
= NULL
;
141 sm_state
->possible
= NULL
;
142 add_ptr_list(&sm_state
->possible
, sm_state
);
146 static void free_sm_state(struct sm_state
*sm
)
148 free_string(sm
->name
);
149 free_slist(&sm
->possible
);
150 free_stack(&sm
->my_pools
);
151 free_stack(&sm
->all_pools
);
153 * fixme. Free the actual state.
154 * Right now we leave it until the end of the function
155 * because we don't want to double free it.
156 * Use the freelist to not double free things
160 static void free_all_sm_states(struct allocation_blob
*blob
)
162 unsigned int size
= sizeof(struct sm_state
);
163 unsigned int offset
= 0;
165 while (offset
< blob
->offset
) {
166 free_sm_state((struct sm_state
*)(blob
->data
+ offset
));
171 /* At the end of every function we free all the sm_states */
172 void free_every_single_sm_state(void)
174 struct allocator_struct
*desc
= &sm_state_allocator
;
175 struct allocation_blob
*blob
= desc
->blobs
;
178 desc
->allocations
= 0;
179 desc
->total_bytes
= 0;
180 desc
->useful_bytes
= 0;
181 desc
->freelist
= NULL
;
183 struct allocation_blob
*next
= blob
->next
;
184 free_all_sm_states(blob
);
185 blob_free(blob
, desc
->chunking
);
190 struct sm_state
*clone_state(struct sm_state
*s
)
192 struct sm_state
*ret
;
193 struct sm_state
*poss
;
195 ret
= alloc_state(s
->name
, s
->owner
, s
->sym
, s
->state
);
197 ret
->my_pools
= clone_stack(s
->my_pools
);
198 ret
->all_pools
= clone_stack(s
->all_pools
);
199 FOR_EACH_PTR(s
->possible
, poss
) {
200 add_sm_state_slist(&ret
->possible
, poss
);
201 } END_FOR_EACH_PTR(poss
);
205 int slist_has_state(struct state_list
*slist
, struct smatch_state
*state
)
207 struct sm_state
*tmp
;
209 FOR_EACH_PTR(slist
, tmp
) {
210 if (tmp
->state
== state
)
212 } END_FOR_EACH_PTR(tmp
);
216 static void check_order(struct state_list
*slist
)
219 struct sm_state
*state
;
220 struct sm_state
*last
= NULL
;
223 FOR_EACH_PTR(slist
, state
) {
224 if (last
&& cmp_tracker(state
, last
) <= 0) {
225 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
226 "%s vs %s\n", last
->owner
, state
->owner
,
227 last
->sym
, state
->sym
, last
->name
, state
->name
);
231 } END_FOR_EACH_PTR(state
);
238 static void check_my_pools(struct sm_state
*sm
)
240 struct sm_state
*poss
;
241 struct state_list
*slist
;
243 if (sm
->state
!= &merged
)
246 FOR_EACH_PTR(sm
->possible
, poss
) {
247 if (poss
->state
== &merged
)
249 FOR_EACH_PTR(sm
->my_pools
, slist
) {
250 if (get_state_slist(slist
, sm
->name
, sm
->owner
, sm
->sym
)
253 } END_FOR_EACH_PTR(slist
);
254 printf("%d pool not found for '%s' possible state \"%s\".\n",
255 get_lineno(), sm
->name
, show_state(poss
->state
));
259 } END_FOR_EACH_PTR(poss
);
263 static void sanity_check_pools(struct state_list
*slist
)
266 struct sm_state
*tmp
;
268 FOR_EACH_PTR(slist
, tmp
) {
270 } END_FOR_EACH_PTR(tmp
);
274 struct state_list
*clone_slist(struct state_list
*from_slist
)
276 struct sm_state
*state
;
277 struct sm_state
*tmp
;
278 struct state_list
*to_slist
= NULL
;
280 FOR_EACH_PTR(from_slist
, state
) {
281 tmp
= clone_state(state
);
282 add_ptr_list(&to_slist
, tmp
);
283 } END_FOR_EACH_PTR(state
);
284 check_order(to_slist
);
288 struct state_list_stack
*clone_stack(struct state_list_stack
*from_stack
)
290 struct state_list
*slist
;
291 struct state_list_stack
*to_stack
= NULL
;
293 FOR_EACH_PTR(from_stack
, slist
) {
294 push_slist(&to_stack
, slist
);
295 } END_FOR_EACH_PTR(slist
);
299 struct smatch_state
*merge_states(const char *name
, int owner
,
301 struct smatch_state
*state1
,
302 struct smatch_state
*state2
)
304 struct smatch_state
*ret
;
306 if (state1
== state2
)
308 else if (__has_merge_function(owner
))
309 ret
= __client_merge_function(owner
, name
, sym
, state1
, state2
);
310 else if (!state1
|| !state2
)
318 * add_pool() adds a slist to ->pools. If the slist has already been
319 * added earlier then it doesn't get added a second time.
321 static void add_pool(struct state_list_stack
**pools
, struct state_list
*new)
323 struct state_list
*tmp
;
325 FOR_EACH_PTR(*pools
, tmp
) {
328 else if (tmp
== new) {
331 INSERT_CURRENT(new, tmp
);
334 } END_FOR_EACH_PTR(tmp
);
335 add_ptr_list(pools
, new);
338 static void copy_pools(struct sm_state
*to
, struct sm_state
*sm
)
340 struct state_list
*tmp
;
345 FOR_EACH_PTR(sm
->my_pools
, tmp
) {
346 add_pool(&to
->my_pools
, tmp
);
347 } END_FOR_EACH_PTR(tmp
);
349 FOR_EACH_PTR(sm
->all_pools
, tmp
) {
350 add_pool(&to
->all_pools
, tmp
);
351 } END_FOR_EACH_PTR(tmp
);
354 struct sm_state
*merge_sm_states(struct sm_state
*one
, struct sm_state
*two
)
356 struct smatch_state
*s
;
357 struct sm_state
*result
;
359 s
= merge_states(one
->name
, one
->owner
, one
->sym
, one
->state
,
360 (two
?two
->state
:NULL
));
361 result
= alloc_state(one
->name
, one
->owner
, one
->sym
, s
);
362 if (two
&& one
->line
== two
->line
)
363 result
->line
= one
->line
;
364 add_possible(result
, one
);
365 add_possible(result
, two
);
366 copy_pools(result
, one
);
367 copy_pools(result
, two
);
370 struct sm_state
*tmp
;
373 printf("%d merge name='%s' owner=%d: %s + %s => %s (",
374 get_lineno(), one
->name
, one
->owner
,
375 show_state(one
->state
), show_state(two
?two
->state
:NULL
),
378 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
, const char *name
,
391 int owner
, struct symbol
*sym
)
393 struct sm_state
*state
;
398 FOR_EACH_PTR(slist
, state
) {
399 if (state
->owner
== owner
&& state
->sym
== sym
400 && !strcmp(state
->name
, name
))
402 } END_FOR_EACH_PTR(state
);
406 struct smatch_state
*get_state_slist(struct state_list
*slist
,
407 const char *name
, int owner
,
410 struct sm_state
*state
;
412 state
= get_sm_state_slist(slist
, name
, owner
, sym
);
418 void overwrite_sm_state(struct state_list
**slist
, struct sm_state
*new)
420 struct sm_state
*tmp
;
422 FOR_EACH_PTR(*slist
, tmp
) {
423 if (cmp_tracker(tmp
, new) < 0)
425 else if (cmp_tracker(tmp
, new) == 0) {
426 REPLACE_CURRENT_PTR(tmp
, new);
429 INSERT_CURRENT(new, tmp
);
432 } END_FOR_EACH_PTR(tmp
);
433 add_ptr_list(slist
, new);
436 void overwrite_sm_state_stack(struct state_list_stack
**stack
,
437 struct sm_state
*state
)
439 struct state_list
*slist
;
441 slist
= pop_slist(stack
);
442 overwrite_sm_state(&slist
, state
);
443 push_slist(stack
, slist
);
446 void set_state_slist(struct state_list
**slist
, const char *name
, int owner
,
447 struct symbol
*sym
, struct smatch_state
*state
)
449 struct sm_state
*tmp
;
450 struct sm_state
*new = alloc_state(name
, owner
, sym
, state
);
452 FOR_EACH_PTR(*slist
, tmp
) {
453 if (cmp_tracker(tmp
, new) < 0)
455 else if (cmp_tracker(tmp
, new) == 0) {
456 REPLACE_CURRENT_PTR(tmp
, new);
459 INSERT_CURRENT(new, tmp
);
462 } END_FOR_EACH_PTR(tmp
);
463 add_ptr_list(slist
, new);
466 void delete_state_slist(struct state_list
**slist
, const char *name
, int owner
,
469 struct sm_state
*state
;
471 FOR_EACH_PTR(*slist
, state
) {
472 if (state
->owner
== owner
&& state
->sym
== sym
473 && !strcmp(state
->name
, name
)){
474 delete_ptr_list_entry((struct ptr_list
**)slist
,
478 } END_FOR_EACH_PTR(state
);
482 void push_slist(struct state_list_stack
**list_stack
, struct state_list
*slist
)
484 add_ptr_list(list_stack
, slist
);
487 struct state_list
*pop_slist(struct state_list_stack
**list_stack
)
489 struct state_list
*slist
;
491 slist
= last_ptr_list((struct ptr_list
*)*list_stack
);
492 delete_ptr_list_last((struct ptr_list
**)list_stack
);
496 void free_slist(struct state_list
**slist
)
498 __free_ptr_list((struct ptr_list
**)slist
);
501 void free_stack(struct state_list_stack
**stack
)
503 __free_ptr_list((struct ptr_list
**)stack
);
506 void free_stack_and_slists(struct state_list_stack
**slist_stack
)
508 struct state_list
*slist
;
510 FOR_EACH_PTR(*slist_stack
, slist
) {
512 } END_FOR_EACH_PTR(slist
);
513 free_stack(slist_stack
);
517 * set_state_stack() sets the state for the top slist on the stack.
519 void set_state_stack(struct state_list_stack
**stack
, const char *name
,
520 int owner
, struct symbol
*sym
, struct smatch_state
*state
)
522 struct state_list
*slist
;
524 slist
= pop_slist(stack
);
525 set_state_slist(&slist
, name
, owner
, sym
, state
);
526 push_slist(stack
, slist
);
530 * get_state_stack() gets the state for the top slist on the stack.
532 struct smatch_state
*get_state_stack(struct state_list_stack
*stack
,
533 const char *name
, int owner
,
536 struct state_list
*slist
;
537 struct smatch_state
*ret
;
539 slist
= pop_slist(&stack
);
540 ret
= get_state_slist(slist
, name
, owner
, sym
);
541 push_slist(&stack
, slist
);
545 static void register_implied_pool(struct state_list
*pool
)
549 FOR_EACH_PTR(pool
, sm
) {
550 if (sm
->state
!= &merged
)
551 free_stack(&sm
->my_pools
);
553 add_pool(&sm
->my_pools
, pool
);
554 add_pool(&sm
->all_pools
, pool
);
555 } END_FOR_EACH_PTR(sm
);
557 push_slist(&implied_pools
, pool
);
560 static void match_states(struct state_list
**one
, struct state_list
**two
)
562 struct sm_state
*one_state
;
563 struct sm_state
*two_state
;
564 struct sm_state
*tmp
;
565 struct smatch_state
*tmp_state
;
566 struct state_list
*add_to_one
= NULL
;
567 struct state_list
*add_to_two
= NULL
;
569 PREPARE_PTR_LIST(*one
, one_state
);
570 PREPARE_PTR_LIST(*two
, two_state
);
572 if (!one_state
&& !two_state
)
574 if (cmp_tracker(one_state
, two_state
) < 0) {
575 tmp_state
= __client_unmatched_state_function(one_state
);
576 tmp
= alloc_state(one_state
->name
, one_state
->owner
,
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(two_state
->name
, two_state
->owner
,
586 two_state
->sym
, tmp_state
);
587 add_ptr_list(&add_to_one
, tmp
);
588 NEXT_PTR_LIST(two_state
);
591 FINISH_PTR_LIST(two_state
);
592 FINISH_PTR_LIST(one_state
);
594 overwrite_slist(add_to_one
, one
);
595 overwrite_slist(add_to_two
, two
);
599 * merge_slist() is called whenever paths merge, such as after
600 * an if statement. It takes the two slists and creates one.
602 void merge_slist(struct state_list
**to
, struct state_list
*slist
)
604 struct sm_state
*to_state
, *state
, *tmp
;
605 struct state_list
*results
= NULL
;
606 struct state_list
*implied_to
= NULL
;
607 struct state_list
*implied_from
= NULL
;
611 sanity_check_pools(*to
);
612 sanity_check_pools(slist
);
614 /* merging a null and nonnull path gives you only the nonnull path */
619 *to
= clone_slist(slist
);
623 implied_to
= clone_slist(*to
);
624 implied_from
= clone_slist(slist
);
626 match_states(&implied_to
, &implied_from
);
628 register_implied_pool(implied_to
);
629 register_implied_pool(implied_from
);
631 PREPARE_PTR_LIST(implied_to
, to_state
);
632 PREPARE_PTR_LIST(implied_from
, state
);
634 if (!to_state
&& !state
)
636 if (cmp_tracker(to_state
, state
) < 0) {
637 smatch_msg("error: Internal smatch error.");
638 NEXT_PTR_LIST(to_state
);
639 } else if (cmp_tracker(to_state
, state
) == 0) {
640 tmp
= merge_sm_states(to_state
, state
);
641 add_ptr_list(&results
, tmp
);
642 NEXT_PTR_LIST(to_state
);
643 NEXT_PTR_LIST(state
);
645 smatch_msg("error: Internal smatch error.");
646 NEXT_PTR_LIST(state
);
649 FINISH_PTR_LIST(state
);
650 FINISH_PTR_LIST(to_state
);
657 * and_slist_stack() is basically the same as popping the top two slists,
658 * overwriting the one with the other and pushing it back on the stack.
659 * The difference is that it checks to see that a mutually exclusive
660 * state isn't included in both stacks. If smatch sees something like
661 * "if (a && !a)" it prints a warning.
663 void and_slist_stack(struct state_list_stack
**slist_stack
)
665 struct sm_state
*tmp
;
666 struct smatch_state
*tmp_state
;
667 struct state_list
*tmp_slist
= pop_slist(slist_stack
);
669 FOR_EACH_PTR(tmp_slist
, tmp
) {
670 tmp_state
= get_state_stack(*slist_stack
, tmp
->name
,
671 tmp
->owner
, tmp
->sym
);
672 if (tmp_state
&& tmp_state
!= tmp
->state
) {
673 SM_DEBUG("mutually exclusive 'and' conditions states "
675 tmp
->name
, show_state(tmp_state
),
676 show_state(tmp
->state
));
678 set_state_stack(slist_stack
, tmp
->name
, tmp
->owner
, tmp
->sym
,
680 } END_FOR_EACH_PTR(tmp
);
681 free_slist(&tmp_slist
);
685 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
686 * It pops the two slists from the top of the stack and merges them
687 * together in a way that preserves the things they have in common
688 * but creates a merged state for most of the rest.
689 * You could have code that had: if (foo || foo) { foo->baz;
690 * It's this function which ensures smatch does the right thing.
692 void or_slist_stack(struct state_list_stack
**pre_conds
,
693 struct state_list
*cur_slist
,
694 struct state_list_stack
**slist_stack
)
696 struct state_list
*new;
697 struct state_list
*old
;
698 struct state_list
*res
= NULL
;
699 struct state_list
*tmp_slist
;
701 new = pop_slist(slist_stack
);
702 old
= pop_slist(slist_stack
);
704 tmp_slist
= pop_slist(pre_conds
);
705 res
= clone_slist(tmp_slist
);
706 push_slist(pre_conds
, tmp_slist
);
707 overwrite_slist(old
, &res
);
709 tmp_slist
= clone_slist(cur_slist
);
710 overwrite_slist(new, &tmp_slist
);
712 merge_slist(&res
, tmp_slist
);
714 push_slist(slist_stack
, res
);
715 free_slist(&tmp_slist
);
721 * get_slist_from_named_stack() is only used for gotos.
723 struct state_list
**get_slist_from_named_stack(struct named_stack
*stack
,
726 struct named_slist
*tmp
;
728 FOR_EACH_PTR(stack
, tmp
) {
729 if (!strcmp(tmp
->name
, name
))
731 } END_FOR_EACH_PTR(tmp
);
735 void overwrite_slist(struct state_list
*from
, struct state_list
**to
)
737 struct sm_state
*tmp
;
739 FOR_EACH_PTR(from
, tmp
) {
740 overwrite_sm_state(to
, tmp
);
741 } END_FOR_EACH_PTR(tmp
);
744 unsigned int __get_allocations()
746 return sm_state_allocator
.allocations
;