Print this page
11506 smatch resync
@@ -94,13 +94,13 @@
if (!b)
return -1;
if (!a)
return 1;
- if (a->owner > b->owner)
- return -1;
if (a->owner < b->owner)
+ return -1;
+ if (a->owner > b->owner)
return 1;
ret = strcmp(a->name, b->name);
if (ret < 0)
return -1;
@@ -117,42 +117,71 @@
return 1;
return 0;
}
-static int cmp_sm_states(const struct sm_state *a, const struct sm_state *b, int preserve)
+int *dynamic_states;
+void allocate_dynamic_states_array(int num_checks)
{
+ dynamic_states = calloc(num_checks + 1, sizeof(int));
+}
+
+void set_dynamic_states(unsigned short owner)
+{
+ dynamic_states[owner] = true;
+}
+
+bool has_dynamic_states(unsigned short owner)
+{
+ if (owner >= num_checks)
+ return false;
+ return dynamic_states[owner];
+}
+
+static int cmp_possible_sm(const struct sm_state *a, const struct sm_state *b, int preserve)
+{
int ret;
- ret = cmp_tracker(a, b);
- if (ret)
- return ret;
+ if (a == b)
+ return 0;
- /* todo: add hook for smatch_extra.c */
+ if (!has_dynamic_states(a->owner)) {
if (a->state > b->state)
return -1;
if (a->state < b->state)
return 1;
- /* This is obviously a massive disgusting hack but we need to preserve
- * the unmerged states for smatch extra because we use them in
- * smatch_db.c. Meanwhile if we preserve all the other unmerged states
- * then it uses a lot of memory and we don't use it. Hence this hack.
+ return 0;
+ }
+
+ if (a->owner == SMATCH_EXTRA) {
+ /*
+ * In Smatch extra you can have borrowed implications.
*
- * Also sometimes even just preserving every possible SMATCH_EXTRA state
- * takes too much resources so we have to cap that. Capping is probably
- * not often a problem in real life.
+ * FIXME: review how borrowed implications work and if they
+ * are the best way. See also smatch_implied.c.
+ *
*/
- if (a->owner == SMATCH_EXTRA && preserve) {
- if (a == b)
- return 0;
- if (a->merged == 1 && b->merged == 0)
+ ret = cmp_tracker(a, b);
+ if (ret)
+ return ret;
+
+ /*
+ * We want to preserve leaf states. They're use to split
+ * returns in smatch_db.c.
+ *
+ */
+ if (preserve) {
+ if (a->merged && !b->merged)
return -1;
- if (a->merged == 0)
+ if (!a->merged)
return 1;
}
-
+ }
+ if (!a->state->name || !b->state->name)
return 0;
+
+ return strcmp(a->state->name, b->state->name);
}
struct sm_state *alloc_sm_state(int owner, const char *name,
struct symbol *sym, struct smatch_state *state)
{
@@ -167,11 +196,10 @@
sm_state->line = get_lineno();
sm_state->merged = 0;
sm_state->pool = NULL;
sm_state->left = NULL;
sm_state->right = NULL;
- sm_state->nr_children = 1;
sm_state->possible = NULL;
add_ptr_list(&sm_state->possible, sm_state);
return sm_state;
}
@@ -195,32 +223,50 @@
void add_possible_sm(struct sm_state *to, struct sm_state *new)
{
struct sm_state *tmp;
int preserve = 1;
+ int cmp;
if (too_many_possible(to))
preserve = 0;
FOR_EACH_PTR(to->possible, tmp) {
- if (cmp_sm_states(tmp, new, preserve) < 0)
+ cmp = cmp_possible_sm(tmp, new, preserve);
+ if (cmp < 0)
continue;
- else if (cmp_sm_states(tmp, new, preserve) == 0) {
+ else if (cmp == 0) {
return;
} else {
INSERT_CURRENT(new, tmp);
return;
}
} END_FOR_EACH_PTR(tmp);
add_ptr_list(&to->possible, new);
}
-static void copy_possibles(struct sm_state *to, struct sm_state *from)
+static void copy_possibles(struct sm_state *to, struct sm_state *one, struct sm_state *two)
{
+ struct sm_state *large = one;
+ struct sm_state *small = two;
struct sm_state *tmp;
- FOR_EACH_PTR(from->possible, tmp) {
+ /*
+ * We spend a lot of time copying the possible lists. I've tried to
+ * optimize the process a bit.
+ *
+ */
+
+ if (ptr_list_size((struct ptr_list *)two->possible) >
+ ptr_list_size((struct ptr_list *)one->possible)) {
+ large = two;
+ small = one;
+ }
+
+ to->possible = clone_slist(large->possible);
+ add_possible_sm(to, to);
+ FOR_EACH_PTR(small->possible, tmp) {
add_possible_sm(to, tmp);
} END_FOR_EACH_PTR(tmp);
}
char *alloc_sname(const char *str)
@@ -232,19 +278,43 @@
tmp = __alloc_sname(strlen(str) + 1);
strcpy(tmp, str);
return tmp;
}
+static struct symbol *oom_func;
+static int oom_limit = 3000000; /* Start with a 3GB limit */
int out_of_memory(void)
{
+ if (oom_func)
+ return 1;
+
/*
* I decided to use 50M here based on trial and error.
* It works out OK for the kernel and so it should work
* for most other projects as well.
*/
if (sm_state_counter * sizeof(struct sm_state) >= 100000000)
return 1;
+
+ /*
+ * We're reading from statm to figure out how much memory we
+ * are using. The problem is that at the end of the function
+ * we release the memory, so that it can be re-used but it
+ * stays in cache, it's not released to the OS. So then if
+ * we allocate memory for different purposes we can easily
+ * hit the 3GB limit on the next function, so that's why I give
+ * the next function an extra 100MB to work with.
+ *
+ */
+ if (get_mem_kb() > oom_limit) {
+ oom_func = cur_func_sym;
+ final_pass++;
+ sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter);
+ final_pass--;
+ return 1;
+ }
+
return 0;
}
int low_on_memory(void)
{
@@ -295,10 +365,14 @@
clear_sname_alloc();
clear_smatch_state_alloc();
free_stack_and_strees(&all_pools);
sm_state_counter = 0;
+ if (oom_func) {
+ oom_limit += 100000;
+ oom_func = NULL;
+ }
}
unsigned long get_pool_count(void)
{
return ptr_list_size((struct ptr_list *)all_pools);
@@ -314,11 +388,10 @@
/* clone_sm() doesn't copy the pools. Each state needs to have
only one pool. */
ret->possible = clone_slist(s->possible);
ret->left = s->left;
ret->right = s->right;
- ret->nr_children = s->nr_children;
return ret;
}
int is_merged(struct sm_state *sm)
{
@@ -392,14 +465,13 @@
s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
result = alloc_state_no_name(one->owner, one->name, one->sym, s);
result->merged = 1;
result->left = one;
result->right = two;
- result->nr_children = one->nr_children + two->nr_children;
- copy_possibles(result, one);
- copy_possibles(result, two);
+ copy_possibles(result, one, two);
+
/*
* The ->line information is used by deref_check where we complain about
* checking pointers that have already been dereferenced. Let's say we
* dereference a pointer on both the true and false paths and then merge
* the states here. The result state is &derefed, but the ->line number
@@ -716,11 +788,11 @@
struct stree *results = NULL;
struct stree *implied_one = NULL;
struct stree *implied_two = NULL;
AvlIter one_iter;
AvlIter two_iter;
- struct sm_state *tmp_sm;
+ struct sm_state *one, *two, *res;
if (out_of_memory())
return;
/* merging a null and nonnull path gives you only the nonnull path */
@@ -759,33 +831,35 @@
avl_iter_begin(&two_iter, implied_two, FORWARD);
for (;;) {
if (!one_iter.sm || !two_iter.sm)
break;
- if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
- sm_perror(" in %s", __func__);
- avl_iter_next(&one_iter);
- } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
- if (add_pool && one_iter.sm != two_iter.sm) {
- one_iter.sm->pool = implied_one;
+
+ one = one_iter.sm;
+ two = two_iter.sm;
+
+ if (one == two) {
+ avl_insert(&results, one);
+ goto next;
+ }
+
+ if (add_pool) {
+ one->pool = implied_one;
if (implied_one->base_stree)
- one_iter.sm->pool = implied_one->base_stree;
- two_iter.sm->pool = implied_two;
+ one->pool = implied_one->base_stree;
+ two->pool = implied_two;
if (implied_two->base_stree)
- two_iter.sm->pool = implied_two->base_stree;
+ two->pool = implied_two->base_stree;
}
- tmp_sm = merge_sm_states(one_iter.sm, two_iter.sm);
- add_possible_sm(tmp_sm, one_iter.sm);
- add_possible_sm(tmp_sm, two_iter.sm);
- avl_insert(&results, tmp_sm);
+ res = merge_sm_states(one, two);
+ add_possible_sm(res, one);
+ add_possible_sm(res, two);
+ avl_insert(&results, res);
+next:
avl_iter_next(&one_iter);
avl_iter_next(&two_iter);
- } else {
- sm_perror(" in %s", __func__);
- avl_iter_next(&two_iter);
}
- }
free_stree(to);
*to = results;
}