extra, db: record a dummy output for every function call
[smatch.git] / smatch_slist.c
blobfe1cd07d1437b2554f97578f4be833f5c98fbbf9
1 /*
2 * sparse/smatch_slist.c
4 * Copyright (C) 2008,2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
8 */
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include "smatch.h"
13 #include "smatch_slist.h"
15 #undef CHECKORDER
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;
28 int i;
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));
34 i = 0;
35 FOR_EACH_PTR(state->possible, poss) {
36 if (i++)
37 printf(", ");
38 printf("%s", show_state(poss->state));
39 } END_FOR_EACH_PTR(poss);
40 printf(")\n");
41 } END_FOR_EACH_PTR(state);
42 printf("---\n");
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)
49 int ret;
51 if (a == b)
52 return 0;
53 if (!b)
54 return -1;
55 if (!a)
56 return 1;
58 if (a->owner > b->owner)
59 return -1;
60 if (a->owner < b->owner)
61 return 1;
63 ret = strcmp(a->name, b->name);
64 if (ret)
65 return ret;
67 if (!b->sym && a->sym)
68 return -1;
69 if (!a->sym && b->sym)
70 return 1;
71 if (a->sym > b->sym)
72 return -1;
73 if (a->sym < b->sym)
74 return 1;
76 return 0;
79 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b)
81 int ret;
83 ret = cmp_tracker(a, b);
84 if (ret)
85 return ret;
87 /* todo: add hook for smatch_extra.c */
88 if (a->state > b->state)
89 return -1;
90 if (a->state < b->state)
91 return 1;
92 return 0;
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);
100 sm_state_counter++;
102 sm_state->name = alloc_sname(name);
103 sm_state->owner = owner;
104 sm_state->sym = sym;
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);
115 return sm_state;
118 static struct sm_state *alloc_state_no_name(int owner, const char *name,
119 struct symbol *sym,
120 struct smatch_state *state)
122 struct sm_state *tmp;
124 tmp = alloc_sm_state(owner, NULL, sym, state);
125 tmp->name = name;
126 return tmp;
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)
135 continue;
136 else if (cmp_sm_states(tmp, new) == 0) {
137 return;
138 } else {
139 INSERT_CURRENT(new, tmp);
140 return;
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,
153 tmp->state);
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)
161 char *tmp;
163 if (!str)
164 return NULL;
165 tmp = __alloc_sname(strlen(str) + 1);
166 strcpy(tmp, str);
167 return tmp;
170 int out_of_memory()
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)
178 return 1;
179 return 0;
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));
200 offset += size;
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;
210 desc->blobs = NULL;
211 desc->allocations = 0;
212 desc->total_bytes = 0;
213 desc->useful_bytes = 0;
214 desc->freelist = NULL;
215 while (blob) {
216 struct allocation_blob *next = blob->next;
217 free_all_sm_states(blob);
218 blob_free(blob, desc->chunking);
219 blob = next;
221 clear_sname_alloc();
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;
233 ret->line = s->line;
234 /* clone_sm() doesn't copy the my_pools. Each state needs to have
235 only one my_pool. */
236 ret->possible = clone_slist(s->possible);
237 ret->left = s->left;
238 ret->right = s->right;
239 ret->nr_children = s->nr_children;
240 return ret;
243 int is_merged(struct sm_state *sm)
245 return sm->merged;
248 int is_implied(struct sm_state *sm)
250 return sm->implied;
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)
259 return 1;
260 } END_FOR_EACH_PTR(tmp);
261 return 0;
264 static void check_order(struct state_list *slist)
266 #ifdef CHECKORDER
267 struct sm_state *sm;
268 struct sm_state *last = NULL;
269 int printed = 0;
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);
276 printed = 1;
278 last = state;
279 } END_FOR_EACH_PTR(sm);
281 if (printed)
282 printf("======\n");
283 #endif
286 struct state_list *clone_slist(struct state_list *from_slist)
288 struct sm_state *sm;
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);
295 return 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);
306 return to_stack;
309 struct smatch_state *merge_states(int owner, const char *name,
310 struct symbol *sym,
311 struct smatch_state *state1,
312 struct smatch_state *state2)
314 struct smatch_state *ret;
316 if (state1 == state2)
317 ret = state1;
318 else if (__has_merge_function(owner))
319 ret = __client_merge_function(owner, name, sym, state1, state2);
320 else if (!state1 || !state2)
321 ret = &undefined;
322 else
323 ret = &merged;
324 return ret;
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) {
336 if (tmp < new)
337 continue;
338 else if (tmp == new) {
339 return;
340 } else {
341 INSERT_CURRENT(new, tmp);
342 return;
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;
353 if (one == two)
354 return one;
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);
357 result->merged = 1;
358 result->left = one;
359 result->right = two;
360 result->nr_children = one->nr_children + two->nr_children;
361 add_possible(result, one);
362 add_possible(result, two);
364 if (option_debug) {
365 struct sm_state *tmp;
366 int i = 0;
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,
372 show_state(s));
374 FOR_EACH_PTR(result->possible, tmp) {
375 if (i++) {
376 printf(", ");
378 printf("%s", show_state(tmp->state));
379 } END_FOR_EACH_PTR(tmp);
380 printf(")\n");
383 return result;
386 struct sm_state *get_sm_state_slist(struct state_list *slist, int owner, const char *name,
387 struct symbol *sym)
389 struct sm_state *sm;
391 if (!name)
392 return NULL;
394 FOR_EACH_PTR(slist, sm) {
395 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name))
396 return sm;
397 } END_FOR_EACH_PTR(sm);
398 return NULL;
401 struct smatch_state *get_state_slist(struct state_list *slist,
402 int owner, const char *name,
403 struct symbol *sym)
405 struct sm_state *sm;
407 sm = get_sm_state_slist(slist, owner, name, sym);
408 if (sm)
409 return sm->state;
410 return NULL;
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)
419 continue;
420 else if (cmp_tracker(tmp, new) == 0) {
421 REPLACE_CURRENT_PTR(tmp, new);
422 return;
423 } else {
424 INSERT_CURRENT(new, tmp);
425 return;
427 } END_FOR_EACH_PTR(tmp);
428 add_ptr_list(slist, new);
431 void overwrite_sm_state_stack(struct state_list_stack **stack,
432 struct sm_state *sm)
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)
449 continue;
450 else if (cmp_tracker(tmp, new) == 0) {
451 REPLACE_CURRENT_PTR(tmp, new);
452 return new;
453 } else {
454 INSERT_CURRENT(new, tmp);
455 return new;
457 } END_FOR_EACH_PTR(tmp);
458 add_ptr_list(slist, new);
459 return new;
462 void delete_state_slist(struct state_list **slist, int owner, const char *name,
463 struct symbol *sym)
465 struct sm_state *sm;
467 FOR_EACH_PTR(*slist, sm) {
468 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name)){
469 DELETE_CURRENT_PTR(sm);
470 return;
472 } END_FOR_EACH_PTR(sm);
475 void delete_state_stack(struct state_list_stack **stack, int owner, const char *name,
476 struct symbol *sym)
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);
496 return slist;
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) {
514 free_slist(&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;
526 struct sm_state *sm;
528 slist = pop_slist(stack);
529 sm = set_state_slist(&slist, owner, name, sym, state);
530 push_slist(stack, slist);
532 return sm;
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,
540 struct symbol *sym)
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);
548 return ret;
552 struct smatch_state *get_state_stack(struct state_list_stack *stack,
553 int owner, const char *name,
554 struct symbol *sym)
556 struct sm_state *sm;
558 sm = get_sm_state_stack(stack, owner, name, sym);
559 if (sm)
560 return sm->state;
561 return NULL;
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);
575 for (;;) {
576 if (!one_sm && !two_sm)
577 break;
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);
587 } else {
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)
604 struct sm_state *sm;
605 struct sm_state *new;
607 FOR_EACH_PTR(slist, sm) {
608 if (sm->my_pool) {
609 new = clone_sm(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;
626 if (out_of_memory())
627 return;
629 check_order(*to);
630 check_order(slist);
632 /* merging a null and nonnull path gives you only the nonnull path */
633 if (!slist) {
634 return;
636 if (!*to) {
637 *to = clone_slist(slist);
638 return;
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);
651 for (;;) {
652 if (!one_sm && !two_sm)
653 break;
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);
667 } else {
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);
675 free_slist(to);
676 *to = results;
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);
689 for (;;) {
690 if (!one_sm && !two_sm)
691 break;
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);
700 } else {
701 NEXT_PTR_LIST(two_sm);
704 FINISH_PTR_LIST(two_sm);
705 FINISH_PTR_LIST(one_sm);
707 free_slist(slist);
708 *slist = results;
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);
762 free_slist(&new);
763 free_slist(&old);
767 * get_slist_from_named_stack() is only used for gotos.
769 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
770 const char *name)
772 struct named_slist *tmp;
774 FOR_EACH_PTR(stack, tmp) {
775 if (!strcmp(tmp->name, name))
776 return &tmp->slist;
777 } END_FOR_EACH_PTR(tmp);
778 return NULL;
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);