comparison: some small cleanups
[smatch.git] / smatch_slist.c
blob4cdbb044e20cf5e663a2bb04ff397c9aa8d82813
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, 1, 4, "state names", sname);
22 static int sm_state_counter;
24 char *show_sm(struct sm_state *sm)
26 static char buf[256];
27 struct sm_state *tmp;
28 int pos;
29 int i;
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))
34 goto truncate;
36 i = 0;
37 FOR_EACH_PTR(sm->possible, tmp) {
38 if (i++)
39 pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
40 if (pos > sizeof(buf))
41 goto truncate;
42 pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
43 show_state(tmp->state));
44 if (pos > sizeof(buf))
45 goto truncate;
46 } END_FOR_EACH_PTR(tmp);
47 snprintf(buf + pos, sizeof(buf) - pos, ")");
49 return buf;
51 truncate:
52 for (i = 0; i < 3; i++)
53 buf[sizeof(buf) - 2 - i] = '.';
54 return buf;
57 void __print_slist(struct state_list *slist)
59 struct sm_state *sm;
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);
65 printf("---\n");
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)
71 int ret;
73 if (a == b)
74 return 0;
75 if (!b)
76 return -1;
77 if (!a)
78 return 1;
80 if (a->owner > b->owner)
81 return -1;
82 if (a->owner < b->owner)
83 return 1;
85 ret = strcmp(a->name, b->name);
86 if (ret)
87 return ret;
89 if (!b->sym && a->sym)
90 return -1;
91 if (!a->sym && b->sym)
92 return 1;
93 if (a->sym > b->sym)
94 return -1;
95 if (a->sym < b->sym)
96 return 1;
98 return 0;
101 static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b, int preserve)
103 int ret;
105 ret = cmp_tracker(a, b);
106 if (ret)
107 return ret;
109 /* todo: add hook for smatch_extra.c */
110 if (a->state > b->state)
111 return -1;
112 if (a->state < b->state)
113 return 1;
114 /* This is obviously a massive disgusting hack but we need to preserve
115 * the unmerged states for smatch extra because we use them in
116 * smatch_db.c. Meanwhile if we preserve all the other unmerged states
117 * then it uses a lot of memory and we don't use it. Hence this hack.
119 * Also sometimes even just preserving every possible SMATCH_EXTRA state
120 * takes too much resources so we have to cap that. Capping is probably
121 * not often a problem in real life.
123 if (a->owner == SMATCH_EXTRA && preserve) {
124 if (a == b)
125 return 0;
126 if (a->merged == 1 && b->merged == 0)
127 return -1;
128 if (a->merged == 0)
129 return 1;
132 return 0;
135 static struct sm_state *alloc_sm_state(int owner, const char *name,
136 struct symbol *sym, struct smatch_state *state)
138 struct sm_state *sm_state = __alloc_sm_state(0);
140 sm_state_counter++;
142 sm_state->name = alloc_sname(name);
143 sm_state->owner = owner;
144 sm_state->sym = sym;
145 sm_state->state = state;
146 sm_state->line = get_lineno();
147 sm_state->merged = 0;
148 sm_state->implied = 0;
149 sm_state->pool = NULL;
150 sm_state->left = NULL;
151 sm_state->right = NULL;
152 sm_state->nr_children = 1;
153 sm_state->possible = NULL;
154 add_ptr_list(&sm_state->possible, sm_state);
155 return sm_state;
158 static struct sm_state *alloc_state_no_name(int owner, const char *name,
159 struct symbol *sym,
160 struct smatch_state *state)
162 struct sm_state *tmp;
164 tmp = alloc_sm_state(owner, NULL, sym, state);
165 tmp->name = name;
166 return tmp;
169 int too_many_possible(struct sm_state *sm)
171 if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
172 return 1;
173 return 0;
176 void add_possible_sm(struct sm_state *to, struct sm_state *new)
178 struct sm_state *tmp;
179 int preserve = 1;
181 if (too_many_possible(to))
182 preserve = 0;
184 FOR_EACH_PTR(to->possible, tmp) {
185 if (cmp_sm_states(tmp, new, preserve) < 0)
186 continue;
187 else if (cmp_sm_states(tmp, new, preserve) == 0) {
188 return;
189 } else {
190 INSERT_CURRENT(new, tmp);
191 return;
193 } END_FOR_EACH_PTR(tmp);
194 add_ptr_list(&to->possible, new);
197 static void copy_possibles(struct sm_state *to, struct sm_state *from)
199 struct sm_state *tmp;
201 FOR_EACH_PTR(from->possible, tmp) {
202 add_possible_sm(to, tmp);
203 } END_FOR_EACH_PTR(tmp);
206 char *alloc_sname(const char *str)
208 char *tmp;
210 if (!str)
211 return NULL;
212 tmp = __alloc_sname(strlen(str) + 1);
213 strcpy(tmp, str);
214 return tmp;
217 int out_of_memory()
220 * I decided to use 50M here based on trial and error.
221 * It works out OK for the kernel and so it should work
222 * for most other projects as well.
224 if (sm_state_counter * sizeof(struct sm_state) >= 50000000)
225 return 1;
226 return 0;
229 int low_on_memory(void)
231 if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
232 return 1;
233 return 0;
236 static void free_sm_state(struct sm_state *sm)
238 free_slist(&sm->possible);
240 * fixme. Free the actual state.
241 * Right now we leave it until the end of the function
242 * because we don't want to double free it.
243 * Use the freelist to not double free things
247 static void free_all_sm_states(struct allocation_blob *blob)
249 unsigned int size = sizeof(struct sm_state);
250 unsigned int offset = 0;
252 while (offset < blob->offset) {
253 free_sm_state((struct sm_state *)(blob->data + offset));
254 offset += size;
258 /* At the end of every function we free all the sm_states */
259 void free_every_single_sm_state(void)
261 struct allocator_struct *desc = &sm_state_allocator;
262 struct allocation_blob *blob = desc->blobs;
264 desc->blobs = NULL;
265 desc->allocations = 0;
266 desc->total_bytes = 0;
267 desc->useful_bytes = 0;
268 desc->freelist = NULL;
269 while (blob) {
270 struct allocation_blob *next = blob->next;
271 free_all_sm_states(blob);
272 blob_free(blob, desc->chunking);
273 blob = next;
275 clear_sname_alloc();
276 clear_smatch_state_alloc();
278 sm_state_counter = 0;
281 struct sm_state *clone_sm(struct sm_state *s)
283 struct sm_state *ret;
285 ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
286 ret->merged = s->merged;
287 ret->implied = s->implied;
288 ret->line = s->line;
289 /* clone_sm() doesn't copy the pools. Each state needs to have
290 only one pool. */
291 ret->possible = clone_slist(s->possible);
292 ret->left = s->left;
293 ret->right = s->right;
294 ret->nr_children = s->nr_children;
295 return ret;
298 int is_merged(struct sm_state *sm)
300 return sm->merged;
303 int is_implied(struct sm_state *sm)
305 return sm->implied;
308 int slist_has_state(struct state_list *slist, struct smatch_state *state)
310 struct sm_state *tmp;
312 FOR_EACH_PTR(slist, tmp) {
313 if (tmp->state == state)
314 return 1;
315 } END_FOR_EACH_PTR(tmp);
316 return 0;
319 static void check_order(struct state_list *slist)
321 #ifdef CHECKORDER
322 struct sm_state *sm;
323 struct sm_state *last = NULL;
324 int printed = 0;
326 FOR_EACH_PTR(slist, sm) {
327 if (last && cmp_tracker(sm, last) <= 0) {
328 printf("Error. Unsorted slist %d vs %d, %p vs %p, "
329 "%s vs %s\n", last->owner, sm->owner,
330 last->sym, sm->sym, last->name, sm->name);
331 printed = 1;
333 last = sm;
334 } END_FOR_EACH_PTR(sm);
336 if (printed)
337 printf("======\n");
338 #endif
341 struct state_list *clone_slist(struct state_list *from_slist)
343 struct sm_state *sm;
344 struct state_list *to_slist = NULL;
346 FOR_EACH_PTR(from_slist, sm) {
347 add_ptr_list(&to_slist, sm);
348 } END_FOR_EACH_PTR(sm);
349 return to_slist;
352 struct state_list_stack *clone_stack(struct state_list_stack *from_stack)
354 struct state_list *slist;
355 struct state_list_stack *to_stack = NULL;
357 FOR_EACH_PTR(from_stack, slist) {
358 push_slist(&to_stack, slist);
359 } END_FOR_EACH_PTR(slist);
360 return to_stack;
363 struct smatch_state *merge_states(int owner, const char *name,
364 struct symbol *sym,
365 struct smatch_state *state1,
366 struct smatch_state *state2)
368 struct smatch_state *ret;
370 if (state1 == state2)
371 ret = state1;
372 else if (__has_merge_function(owner))
373 ret = __client_merge_function(owner, state1, state2);
374 else if (!state1 || !state2)
375 ret = &undefined;
376 else
377 ret = &merged;
378 return ret;
381 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
383 struct smatch_state *s;
384 struct sm_state *result;
386 if (one == two)
387 return one;
388 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
389 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
390 result->merged = 1;
391 result->left = one;
392 result->right = two;
393 result->nr_children = one->nr_children + two->nr_children;
394 copy_possibles(result, one);
395 copy_possibles(result, two);
397 if (option_debug ||
398 strcmp(check_name(one->owner), option_debug_check) == 0) {
399 struct sm_state *tmp;
400 int i = 0;
402 printf("%d merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
403 get_lineno(), check_name(one->owner), one->name,
404 show_state(one->state), one->line,
405 show_state(two->state), two->line,
406 show_state(s));
408 FOR_EACH_PTR(result->possible, tmp) {
409 if (i++)
410 printf(", ");
411 printf("%s", show_state(tmp->state));
412 } END_FOR_EACH_PTR(tmp);
413 printf(")\n");
416 return result;
419 struct sm_state *get_sm_state_slist(struct state_list *slist, int owner, const char *name,
420 struct symbol *sym)
422 struct sm_state *sm;
424 if (!name)
425 return NULL;
427 FOR_EACH_PTR(slist, sm) {
428 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name))
429 return sm;
430 } END_FOR_EACH_PTR(sm);
431 return NULL;
434 struct smatch_state *get_state_slist(struct state_list *slist,
435 int owner, const char *name,
436 struct symbol *sym)
438 struct sm_state *sm;
440 sm = get_sm_state_slist(slist, owner, name, sym);
441 if (sm)
442 return sm->state;
443 return NULL;
446 void overwrite_sm_state(struct state_list **slist, struct sm_state *new)
448 struct sm_state *tmp;
450 FOR_EACH_PTR(*slist, tmp) {
451 if (cmp_tracker(tmp, new) < 0)
452 continue;
453 else if (cmp_tracker(tmp, new) == 0) {
454 REPLACE_CURRENT_PTR(tmp, new);
455 return;
456 } else {
457 INSERT_CURRENT(new, tmp);
458 return;
460 } END_FOR_EACH_PTR(tmp);
461 add_ptr_list(slist, new);
464 void overwrite_sm_state_stack(struct state_list_stack **stack,
465 struct sm_state *sm)
467 struct state_list *slist;
469 slist = pop_slist(stack);
470 overwrite_sm_state(&slist, sm);
471 push_slist(stack, slist);
474 struct sm_state *set_state_slist(struct state_list **slist, int owner, const char *name,
475 struct symbol *sym, struct smatch_state *state)
477 struct sm_state *tmp;
478 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
480 FOR_EACH_PTR(*slist, tmp) {
481 if (cmp_tracker(tmp, new) < 0)
482 continue;
483 else if (cmp_tracker(tmp, new) == 0) {
484 REPLACE_CURRENT_PTR(tmp, new);
485 return new;
486 } else {
487 INSERT_CURRENT(new, tmp);
488 return new;
490 } END_FOR_EACH_PTR(tmp);
491 add_ptr_list(slist, new);
492 return new;
495 void delete_state_slist(struct state_list **slist, int owner, const char *name,
496 struct symbol *sym)
498 struct sm_state *sm;
500 FOR_EACH_PTR(*slist, sm) {
501 if (sm->owner == owner && sm->sym == sym && !strcmp(sm->name, name)) {
502 DELETE_CURRENT_PTR(sm);
503 return;
505 } END_FOR_EACH_PTR(sm);
508 void delete_state_stack(struct state_list_stack **stack, int owner, const char *name,
509 struct symbol *sym)
511 struct state_list *slist;
513 slist = pop_slist(stack);
514 delete_state_slist(&slist, owner, name, sym);
515 push_slist(stack, slist);
518 void push_slist(struct state_list_stack **list_stack, struct state_list *slist)
520 add_ptr_list(list_stack, slist);
523 struct state_list *pop_slist(struct state_list_stack **list_stack)
525 struct state_list *slist;
527 slist = last_ptr_list((struct ptr_list *)*list_stack);
528 delete_ptr_list_last((struct ptr_list **)list_stack);
529 return slist;
532 void free_slist(struct state_list **slist)
534 __free_ptr_list((struct ptr_list **)slist);
537 void free_stack(struct state_list_stack **stack)
539 __free_ptr_list((struct ptr_list **)stack);
542 void free_stack_and_slists(struct state_list_stack **slist_stack)
544 struct state_list *slist;
546 FOR_EACH_PTR(*slist_stack, slist) {
547 free_slist(&slist);
548 } END_FOR_EACH_PTR(slist);
549 free_stack(slist_stack);
553 * set_state_stack() sets the state for the top slist on the stack.
555 struct sm_state *set_state_stack(struct state_list_stack **stack, int owner, const char *name,
556 struct symbol *sym, struct smatch_state *state)
558 struct state_list *slist;
559 struct sm_state *sm;
561 slist = pop_slist(stack);
562 sm = set_state_slist(&slist, owner, name, sym, state);
563 push_slist(stack, slist);
565 return sm;
569 * get_sm_state_stack() gets the state for the top slist on the stack.
571 struct sm_state *get_sm_state_stack(struct state_list_stack *stack,
572 int owner, const char *name,
573 struct symbol *sym)
575 struct state_list *slist;
576 struct sm_state *ret;
578 slist = pop_slist(&stack);
579 ret = get_sm_state_slist(slist, owner, name, sym);
580 push_slist(&stack, slist);
581 return ret;
584 struct smatch_state *get_state_stack(struct state_list_stack *stack,
585 int owner, const char *name,
586 struct symbol *sym)
588 struct sm_state *sm;
590 sm = get_sm_state_stack(stack, owner, name, sym);
591 if (sm)
592 return sm->state;
593 return NULL;
596 static void match_states(struct state_list **one, struct state_list **two)
598 struct sm_state *one_sm;
599 struct sm_state *two_sm;
600 struct sm_state *tmp;
601 struct smatch_state *tmp_state;
602 struct state_list *add_to_one = NULL;
603 struct state_list *add_to_two = NULL;
605 PREPARE_PTR_LIST(*one, one_sm);
606 PREPARE_PTR_LIST(*two, two_sm);
607 for (;;) {
608 if (!one_sm && !two_sm)
609 break;
610 if (cmp_tracker(one_sm, two_sm) < 0) {
611 __set_fake_cur_slist_fast(*two);
612 tmp_state = __client_unmatched_state_function(one_sm);
613 __pop_fake_cur_slist_fast();
614 tmp = alloc_state_no_name(one_sm->owner, one_sm->name,
615 one_sm->sym, tmp_state);
616 add_ptr_list(&add_to_two, tmp);
617 NEXT_PTR_LIST(one_sm);
618 } else if (cmp_tracker(one_sm, two_sm) == 0) {
619 NEXT_PTR_LIST(one_sm);
620 NEXT_PTR_LIST(two_sm);
621 } else {
622 __set_fake_cur_slist_fast(*one);
623 tmp_state = __client_unmatched_state_function(two_sm);
624 __pop_fake_cur_slist_fast();
625 tmp = alloc_state_no_name(two_sm->owner, two_sm->name,
626 two_sm->sym, tmp_state);
627 add_ptr_list(&add_to_one, tmp);
628 NEXT_PTR_LIST(two_sm);
631 FINISH_PTR_LIST(two_sm);
632 FINISH_PTR_LIST(one_sm);
634 overwrite_slist(add_to_one, one);
635 overwrite_slist(add_to_two, two);
638 static void clone_pool_havers(struct state_list *slist)
640 struct sm_state *sm;
641 struct sm_state *new;
643 FOR_EACH_PTR(slist, sm) {
644 if (sm->pool) {
645 new = clone_sm(sm);
646 REPLACE_CURRENT_PTR(sm, new);
648 } END_FOR_EACH_PTR(sm);
651 int __slist_id;
653 * Sets the first state to the slist_id.
655 static void set_slist_id(struct state_list *slist)
657 struct smatch_state *state;
658 struct sm_state *tmp, *new;
660 state = alloc_state_num(++__slist_id);
661 new = alloc_sm_state(-1, "unnull_path", NULL, state);
663 FOR_EACH_PTR(slist, tmp) {
664 if (tmp->owner != (unsigned short)-1)
665 return;
666 REPLACE_CURRENT_PTR(tmp, new);
667 return;
668 } END_FOR_EACH_PTR(tmp);
671 int get_slist_id(struct state_list *slist)
673 struct sm_state *tmp;
675 FOR_EACH_PTR(slist, tmp) {
676 if (tmp->owner != (unsigned short)-1)
677 return 0;
678 return PTR_INT(tmp->state->data);
679 } END_FOR_EACH_PTR(tmp);
680 return 0;
684 * merge_slist() is called whenever paths merge, such as after
685 * an if statement. It takes the two slists and creates one.
687 void merge_slist(struct state_list **to, struct state_list *slist)
689 struct sm_state *one_sm, *two_sm, *tmp;
690 struct state_list *results = NULL;
691 struct state_list *implied_one = NULL;
692 struct state_list *implied_two = NULL;
694 if (out_of_memory())
695 return;
697 check_order(*to);
698 check_order(slist);
700 /* merging a null and nonnull path gives you only the nonnull path */
701 if (!slist)
702 return;
704 if (!*to) {
705 *to = clone_slist(slist);
706 return;
709 implied_one = clone_slist(*to);
710 implied_two = clone_slist(slist);
712 match_states(&implied_one, &implied_two);
714 clone_pool_havers(implied_one);
715 clone_pool_havers(implied_two);
717 set_slist_id(implied_one);
718 set_slist_id(implied_two);
720 PREPARE_PTR_LIST(implied_one, one_sm);
721 PREPARE_PTR_LIST(implied_two, two_sm);
722 for (;;) {
723 if (!one_sm && !two_sm)
724 break;
725 if (cmp_tracker(one_sm, two_sm) < 0) {
726 sm_msg("error: Internal smatch error.");
727 NEXT_PTR_LIST(one_sm);
728 } else if (cmp_tracker(one_sm, two_sm) == 0) {
729 if (one_sm != two_sm) {
730 one_sm->pool = implied_one;
731 two_sm->pool = implied_two;
734 tmp = merge_sm_states(one_sm, two_sm);
735 add_ptr_list(&results, tmp);
736 NEXT_PTR_LIST(one_sm);
737 NEXT_PTR_LIST(two_sm);
738 } else {
739 sm_msg("error: Internal smatch error.");
740 NEXT_PTR_LIST(two_sm);
743 FINISH_PTR_LIST(two_sm);
744 FINISH_PTR_LIST(one_sm);
746 free_slist(to);
747 *to = results;
751 * filter_slist() removes any sm states "slist" holds in common with "filter"
753 void filter_slist(struct state_list **slist, struct state_list *filter)
755 struct sm_state *one_sm, *two_sm;
756 struct state_list *results = NULL;
758 PREPARE_PTR_LIST(*slist, one_sm);
759 PREPARE_PTR_LIST(filter, two_sm);
760 for (;;) {
761 if (!one_sm && !two_sm)
762 break;
763 if (cmp_tracker(one_sm, two_sm) < 0) {
764 add_ptr_list(&results, one_sm);
765 NEXT_PTR_LIST(one_sm);
766 } else if (cmp_tracker(one_sm, two_sm) == 0) {
767 if (one_sm != two_sm)
768 add_ptr_list(&results, one_sm);
769 NEXT_PTR_LIST(one_sm);
770 NEXT_PTR_LIST(two_sm);
771 } else {
772 NEXT_PTR_LIST(two_sm);
775 FINISH_PTR_LIST(two_sm);
776 FINISH_PTR_LIST(one_sm);
778 free_slist(slist);
779 *slist = results;
783 * and_slist_stack() pops the top two slists, overwriting the one with
784 * the other and pushing it back on the stack.
786 void and_slist_stack(struct state_list_stack **slist_stack)
788 struct sm_state *tmp;
789 struct state_list *right_slist = pop_slist(slist_stack);
791 FOR_EACH_PTR(right_slist, tmp) {
792 overwrite_sm_state_stack(slist_stack, tmp);
793 } END_FOR_EACH_PTR(tmp);
794 free_slist(&right_slist);
798 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
799 * It pops the two slists from the top of the stack and merges them
800 * together in a way that preserves the things they have in common
801 * but creates a merged state for most of the rest.
802 * You could have code that had: if (foo || foo) { foo->baz;
803 * It's this function which ensures smatch does the right thing.
805 void or_slist_stack(struct state_list_stack **pre_conds,
806 struct state_list *cur_slist,
807 struct state_list_stack **slist_stack)
809 struct state_list *new;
810 struct state_list *old;
811 struct state_list *pre_slist;
812 struct state_list *res;
813 struct state_list *tmp_slist;
815 new = pop_slist(slist_stack);
816 old = pop_slist(slist_stack);
818 pre_slist = pop_slist(pre_conds);
819 push_slist(pre_conds, clone_slist(pre_slist));
821 res = clone_slist(pre_slist);
822 overwrite_slist(old, &res);
824 tmp_slist = clone_slist(cur_slist);
825 overwrite_slist(new, &tmp_slist);
827 merge_slist(&res, tmp_slist);
828 filter_slist(&res, pre_slist);
830 push_slist(slist_stack, res);
831 free_slist(&tmp_slist);
832 free_slist(&pre_slist);
833 free_slist(&new);
834 free_slist(&old);
838 * get_slist_from_named_stack() is only used for gotos.
840 struct state_list **get_slist_from_named_stack(struct named_stack *stack,
841 const char *name)
843 struct named_slist *tmp;
845 FOR_EACH_PTR(stack, tmp) {
846 if (!strcmp(tmp->name, name))
847 return &tmp->slist;
848 } END_FOR_EACH_PTR(tmp);
849 return NULL;
852 void overwrite_slist(struct state_list *from, struct state_list **to)
854 struct sm_state *tmp;
856 FOR_EACH_PTR(from, tmp) {
857 overwrite_sm_state(to, tmp);
858 } END_FOR_EACH_PTR(tmp);