aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--erts/emulator/beam/erl_db_catree.c280
-rw-r--r--erts/emulator/beam/erl_db_catree.h4
2 files changed, 136 insertions, 148 deletions
diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c
index 8a89eb72df..2d213baa25 100644
--- a/erts/emulator/beam/erl_db_catree.c
+++ b/erts/emulator/beam/erl_db_catree.c
@@ -90,9 +90,9 @@
** Forward declarations
*/
-static SWord do_free_base_node_cont(DbTableCATree *tb, SWord num_left);
-static SWord do_free_routing_nodes_catree_cont(DbTableCATree *tb, SWord num_left);
-static DbTableCATreeNode *catree_first_base_node_from_free_list(DbTableCATree *tb);
+static SWord do_delete_base_node_cont(DbTableCATree *tb,
+ DbTableCATreeNode *base_node,
+ SWord num_left);
/* Method interface functions */
static int db_first_catree(Process *p, DbTable *tbl,
@@ -1364,113 +1364,152 @@ static void split_catree(DbTableCATree *tb,
}
}
-/*
- * Helper functions for removing the table
+/* @brief Free the entire catree and its sub-trees.
+ *
+ * @param reds Reductions to spend.
+ * @return Reductions left. Negative value if not done.
*/
-
-static void catree_add_base_node_to_free_list(
- DbTableCATree *tb,
- DbTableCATreeNode *base_node_container)
+static SWord db_free_table_continue_catree(DbTable *tbl, SWord reds)
{
- base_node_container->u.base.next =
- tb->base_nodes_to_free_list;
- tb->base_nodes_to_free_list = base_node_container;
-}
+ DbTableCATree *tb = &tbl->catree;
+ DbTableCATreeNode *node;
+ DbTableCATreeNode *parent;
+ CATreeNodeStack rnode_stack;
+ DbTableCATreeNode *rnode_stack_array[STACK_NEED];
-static void catree_deque_base_node_from_free_list(DbTableCATree *tb)
-{
- if (tb->base_nodes_to_free_list == NULL) {
- return; /* List empty */
- } else {
- DbTableCATreeNode *first = tb->base_nodes_to_free_list;
- tb->base_nodes_to_free_list = first->u.base.next;
+ if (!tb->deletion) {
+ /* First call */
+ tb->deletion = 1;
+ tb->nr_of_deleted_items = 0;
}
-}
-static DbTableCATreeNode *catree_first_base_node_from_free_list(
- DbTableCATree *tb)
-{
- return tb->base_nodes_to_free_list;
-}
+ /*
+ * The route tree is traversed and freed while keeping it consistent
+ * during yields.
+ */
+ rnode_stack.array = rnode_stack_array;
+ rnode_stack.pos = 0;
+ rnode_stack.size = STACK_NEED;
-static SWord do_free_routing_nodes_catree_cont(DbTableCATree *tb, SWord num_left)
-{
- DbTableCATreeNode *root;
- DbTableCATreeNode *p;
- for (;;) {
- root = POP_NODE(&tb->free_stack_rnodes);
- if (root == NULL) break;
- else if(root->is_base_node) {
- catree_add_base_node_to_free_list(tb, root);
- break;
+ node = GET_ROOT(tb);
+ if (node->is_base_node) {
+ if (node->u.base.root) {
+ reds = do_delete_base_node_cont(tb, node, reds);
+ if (reds < 0)
+ return reds; /* Yield */
}
- for (;;) {
- if ((GET_LEFT(root) != NULL) &&
- (p = GET_LEFT(root))->is_base_node) {
- SET_LEFT(root, NULL);
- catree_add_base_node_to_free_list(tb, p);
- } else if ((GET_RIGHT(root) != NULL) &&
- (p = GET_RIGHT(root))->is_base_node) {
- SET_RIGHT(root, NULL);
- catree_add_base_node_to_free_list(tb, p);
- } else if ((p = GET_LEFT(root)) != NULL) {
- SET_LEFT(root, NULL);
- PUSH_NODE(&tb->free_stack_rnodes, root);
- root = p;
- } else if ((p = GET_RIGHT(root)) != NULL) {
- SET_RIGHT(root, NULL);
- PUSH_NODE(&tb->free_stack_rnodes, root);
- root = p;
- } else {
- free_catree_route_node(tb, root);
- if (--num_left >= 0) {
+ free_catree_base_node(tb, node);
+ }
+ else {
+ for (;;) {
+ DbTableCATreeNode* left = GET_LEFT(node);
+ DbTableCATreeNode* right = GET_RIGHT(node);
+
+ if (!left->is_base_node) {
+ PUSH_NODE(&rnode_stack, node);
+ node = left;
+ }
+ else if (!right->is_base_node) {
+ PUSH_NODE(&rnode_stack, node);
+ node = right;
+ }
+ else {
+ if (left->u.base.root) {
+ reds = do_delete_base_node_cont(tb, left, reds);
+ if (reds < 0)
+ return reds; /* Yield */
+ }
+ if (right->u.base.root) {
+ reds = do_delete_base_node_cont(tb, right, reds);
+ if (reds < 0)
+ return reds; /* Yield */
+ }
+
+ free_catree_base_node(tb, right);
+ free_catree_route_node(tb, node);
+ /*
+ * Keep empty left base node to join with its grandparent
+ * for tree consistency during yields.
+ */
+
+ parent = POP_NODE(&rnode_stack);
+ if (parent) {
+ if (node == GET_LEFT(parent)) {
+ SET_LEFT(parent, left);
+ }
+ else {
+ ASSERT(node == GET_RIGHT(parent));
+ SET_RIGHT(parent, left);
+ }
+
+ reds -= 2;
+ if (reds < 0)
+ return reds; /* Yield */
+
+ node = parent;
+ }
+ else { /* Done */
+ free_catree_base_node(tb, left);
break;
- } else {
- return num_left; /* Done enough for now */
}
}
}
}
- return num_left;
+
+ ASSERT(reds >= 0);
+ SET_ROOT(tb, NULL);
+ return reds;
}
-static SWord do_free_base_node_cont(DbTableCATree *tb, SWord num_left)
+/* @brief Free all objects of a base node, but keep the base node.
+ *
+ * @param reds Reductions to spend.
+ * @return Reductions left. Negative value if not done.
+ */
+static SWord do_delete_base_node_cont(DbTableCATree *tb,
+ DbTableCATreeNode *base_node,
+ SWord reds)
{
- TreeDbTerm *root;
TreeDbTerm *p;
- DbTableCATreeNode *base_node_container =
- catree_first_base_node_from_free_list(tb);
+ DbTreeStack stack;
+ TreeDbTerm* stack_array[STACK_NEED];
+
+ stack.pos = 0;
+ stack.array = stack_array;
+
+ p = base_node->u.base.root;
for (;;) {
- root = POP_NODE(&tb->free_stack_elems);
- if (root == NULL) break;
- for (;;) {
- if ((p = root->left) != NULL) {
- root->left = NULL;
- PUSH_NODE(&tb->free_stack_elems, root);
- root = p;
- } else if ((p = root->right) != NULL) {
- root->right = NULL;
- PUSH_NODE(&tb->free_stack_elems, root);
- root = p;
- } else {
- DEC_NITEMS((DbTable*)tb);
- tb->nr_of_deleted_items++;
- free_term((DbTable*)tb, root);
- if (--num_left >= 0) {
- break;
- } else {
- return num_left; /* Done enough for now */
- }
+ if (p->left) {
+ PUSH_NODE(&stack, p);
+ p = p->left;
+ }
+ else if (p->right) {
+ PUSH_NODE(&stack, p);
+ p = p->right;
+ }
+ else {
+ TreeDbTerm *parent;
+
+ DEC_NITEMS((DbTable*)tb);
+ tb->nr_of_deleted_items++;
+ free_term((DbTable*)tb, p);
+
+ parent = POP_NODE(&stack);
+ if (!parent)
+ break;
+ if (parent->left == p)
+ parent->left = NULL;
+ else {
+ ASSERT(parent->right == p);
+ parent->right = NULL;
}
+ if (--reds < 0)
+ return reds; /* Yield */
+ p = parent;
}
}
- catree_deque_base_node_from_free_list(tb);
- free_catree_base_node(tb, base_node_container);
- base_node_container = catree_first_base_node_from_free_list(tb);
- if (base_node_container != NULL) {
- PUSH_NODE(&tb->free_stack_elems, base_node_container->u.base.root);
- }
- return num_left;
+ base_node->u.base.root = NULL;
+ return reds;
}
@@ -1494,7 +1533,6 @@ int db_create_catree(Process *p, DbTable *tbl)
root = create_base_node(tb, NULL);
tb->deletion = 0;
- tb->base_nodes_to_free_list = NULL;
tb->nr_of_deleted_items = 0;
#ifdef DEBUG
tbl->common.status |= DB_CATREE_DEBUG_RANDOM_SPLIT_JOIN;
@@ -2131,57 +2169,6 @@ static int db_free_table_catree(DbTable *tbl)
return 1;
}
-static SWord db_free_table_continue_catree(DbTable *tbl, SWord reds)
-{
- DbTableCATreeNode *first_base_node;
- DbTableCATree *tb = &tbl->catree;
- if (!tb->deletion) {
- tb->deletion = 1;
- tb->free_stack_elems.array =
- erts_db_alloc(ERTS_ALC_T_DB_STK,
- (DbTable *) tb,
- sizeof(TreeDbTerm *) * STACK_NEED);
- tb->free_stack_elems.pos = 0;
- tb->free_stack_elems.slot = 0;
- tb->free_stack_rnodes.array =
- erts_db_alloc(ERTS_ALC_T_DB_STK,
- (DbTable *) tb,
- sizeof(DbTableCATreeNode *) * STACK_NEED);
- tb->free_stack_rnodes.pos = 0;
- tb->free_stack_rnodes.size = STACK_NEED;
- PUSH_NODE(&tb->free_stack_rnodes, GET_ROOT(tb));
- tb->is_routing_nodes_freed = 0;
- tb->base_nodes_to_free_list = NULL;
- tb->nr_of_deleted_items = 0;
- }
- if ( ! tb->is_routing_nodes_freed ) {
- reds = do_free_routing_nodes_catree_cont(tb, reds);
- if (reds < 0) {
- return reds; /* Not finished */
- } else {
- tb->is_routing_nodes_freed = 1; /* Ready with the routing nodes */
- first_base_node = catree_first_base_node_from_free_list(tb);
- PUSH_NODE(&tb->free_stack_elems, first_base_node->u.base.root);
- }
- }
- while (catree_first_base_node_from_free_list(tb) != NULL) {
- reds = do_free_base_node_cont(tb, reds);
- if (reds < 0) {
- return reds; /* Continue later */
- }
- }
- /* Time to free the main structure*/
- erts_db_free(ERTS_ALC_T_DB_STK,
- (DbTable *) tb,
- (void *) tb->free_stack_elems.array,
- sizeof(TreeDbTerm *) * STACK_NEED);
- erts_db_free(ERTS_ALC_T_DB_STK,
- (DbTable *) tb,
- (void *) tb->free_stack_rnodes.array,
- sizeof(DbTableCATreeNode *) * STACK_NEED);
- return 1;
-}
-
static
int db_catree_nr_of_items_deleted_wb_dtor(Binary *context_bin) {
(void)context_bin;
@@ -2258,10 +2245,15 @@ static void db_foreach_offheap_catree(DbTable *tbl,
void (*func)(ErlOffHeap *, void *),
void *arg)
{
+ DbTableCATree* tb = &tbl->catree;
CATreeRootIterator iter;
TreeDbTerm** root;
- init_root_iterator(&tbl->catree, &iter, 1);
+ if (!GET_ROOT(tb)) {
+ ASSERT(tb->common.status & DB_DELETE);
+ return;
+ }
+ init_root_iterator(tb, &iter, 1);
root = catree_find_first_root(&iter);
do {
db_foreach_offheap_tree_common(*root, func, arg);
@@ -2269,7 +2261,7 @@ static void db_foreach_offheap_catree(DbTable *tbl,
} while (root);
destroy_root_iterator(&iter);
- do_for_route_nodes(GET_ROOT(&tbl->catree), func, arg);
+ do_for_route_nodes(GET_ROOT(tb), func, arg);
}
static int db_lookup_dbterm_catree(Process *p, DbTable *tbl, Eterm key, Eterm obj,
diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h
index 2ede85e04e..00141ef86d 100644
--- a/erts/emulator/beam/erl_db_catree.h
+++ b/erts/emulator/beam/erl_db_catree.h
@@ -46,7 +46,6 @@ typedef struct {
int is_valid; /* If this base node is still valid */
TreeDbTerm *root; /* The root of the sequential tree */
ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */
- struct DbTableCATreeNode * next; /* Used when gradually deleting */
char end_of_struct__;
} DbTableCATreeBaseNode;
@@ -83,9 +82,6 @@ typedef struct db_table_catree {
/* CA Tree-specific fields */
erts_atomic_t root; /* The tree root (DbTableCATreeNode*) */
Uint deletion; /* Being deleted */
- DbTreeStack free_stack_elems;/* Used for deletion ...*/
- CATreeNodeStack free_stack_rnodes;
- DbTableCATreeNode *base_nodes_to_free_list;
int is_routing_nodes_freed;
/* The fields below are used by delete_all_objects and
select_delete(DeleteAll)*/