diff options
Diffstat (limited to 'erts')
| -rw-r--r-- | erts/emulator/beam/erl_db_catree.c | 343 | ||||
| -rw-r--r-- | erts/emulator/beam/erl_lock_check.c | 7 |
2 files changed, 1 insertions, 349 deletions
diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index 1b4e5d45e7..d433a5b56e 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -242,30 +242,6 @@ static ERTS_INLINE Sint cmp_key_route(Eterm key, return CMP(key, GET_ROUTE_NODE_KEY(obj)); } -static ERTS_INLINE void push_node_dyn_array(DbTable *tb, - CATreeNodeStack *stack, - DbTableCATreeNode *node) -{ - int i; - if (stack->pos == stack->size) { - DbTableCATreeNode **newArray = - erts_db_alloc(ERTS_ALC_T_DB_STK, tb, - sizeof(DbTableCATreeNode*) * (stack->size*2)); - for (i = 0; i < stack->pos; i++) { - newArray[i] = stack->array[i]; - } - if (stack->size > STACK_NEED) { - /* Dynamically allocated array that needs to be deallocated */ - erts_db_free(ERTS_ALC_T_DB_STK, tb, - stack->array, - sizeof(DbTableCATreeNode *) * stack->size); - } - stack->array = newArray; - stack->size = stack->size*2; - } - PUSH_NODE(stack, node); -} - /* * Used by the split_tree function */ @@ -914,20 +890,6 @@ static DbTableCATreeNode *create_base_node(DbTableCATree *tb, return p; } -static ERTS_INLINE -DbTableCATreeNode *create_wlocked_base_node(DbTableCATree *tb, - TreeDbTerm* root, - Eterm lc_key) -{ - DbTableCATreeNode* p = create_base_node(tb, root, lc_key); - ethr_rwmutex_rwlock(&p->u.base.lock.rwmtx); -#ifdef ERTS_ENABLE_LOCK_CHECK - erts_lc_trylock_flg(-1, &p->u.base.lock.lc, ERTS_LOCK_OPTIONS_RDWR); -#endif - return p; -} - - static ERTS_INLINE Uint sizeof_route_node(Uint key_size) { return (offsetof(DbTableCATreeNode, u.route.key.heap) @@ -1075,126 +1037,6 @@ rightmost_route_node(DbTableCATreeNode *root) return prev_node; } -static ERTS_INLINE DbTableCATreeNode* -leftmost_base_node_and_path(DbTableCATreeNode *root, CATreeNodeStack * stack) -{ - DbTableCATreeNode * node = root; - while (!node->is_base_node) { - PUSH_NODE(stack, node); - node = GET_LEFT_ACQB(node); - } - return node; -} - -static ERTS_INLINE DbTableCATreeNode* -get_next_base_node_and_path(DbTableCATreeNode *base_node, - CATreeNodeStack *stack) -{ - if (EMPTY_NODE(stack)) { /* The parent of b is the root */ - return NULL; - } else { - if (GET_LEFT(TOP_NODE(stack)) == base_node) { - return leftmost_base_node_and_path( - GET_RIGHT_ACQB(TOP_NODE(stack)), - stack); - } else { - Eterm pkey = - TOP_NODE(stack)->u.route.key.term; /* pKey = key of parent */ - POP_NODE(stack); - while (!EMPTY_NODE(stack)) { - if (TOP_NODE(stack)->u.route.is_valid && - cmp_key_route(pkey, TOP_NODE(stack)) <= 0) { - return leftmost_base_node_and_path(GET_RIGHT_ACQB(TOP_NODE(stack)), stack); - } else { - POP_NODE(stack); - } - } - } - return NULL; - } -} - -static ERTS_INLINE void -clone_stack(CATreeNodeStack *search_stack_ptr, - CATreeNodeStack *search_stack_copy_ptr) -{ - int i; - search_stack_copy_ptr->pos = search_stack_ptr->pos; - for (i = 0; i < search_stack_ptr->pos; i++) { - search_stack_copy_ptr->array[i] = search_stack_ptr->array[i]; - } -} - -static ERTS_INLINE DbTableCATreeBaseNode* -find_and_lock_next_base_node_and_path(DbTable *tbl, - CATreeNodeStack **search_stack_ptr_ptr, - CATreeNodeStack **search_stack_copy_ptr_ptr, - CATreeNodeStack *locked_base_nodes_stack_ptr) -{ - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - CATreeNodeStack * tmp_stack_ptr; - - while (1) { - current_node = TOP_NODE(locked_base_nodes_stack_ptr); - clone_stack(*search_stack_ptr_ptr, *search_stack_copy_ptr_ptr); - current_node = - get_next_base_node_and_path(current_node, *search_stack_ptr_ptr); - if (current_node == NULL) { - return NULL; - } - base_node = ¤t_node->u.base; - rlock_base_node(base_node); - if (base_node->is_valid) - break; - - /* Retry */ - runlock_base_node(base_node); - /* Revert to previous state */ - current_node = TOP_NODE(locked_base_nodes_stack_ptr); - tmp_stack_ptr = *search_stack_ptr_ptr; - *search_stack_ptr_ptr = *search_stack_copy_ptr_ptr; - *search_stack_copy_ptr_ptr = tmp_stack_ptr; - } - - push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node); - return base_node; -} - -static ERTS_INLINE -void unlock_and_release_locked_base_node_stack(DbTable *tbl, - CATreeNodeStack *locked_base_nodes_stack_ptr) -{ - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - int i; - for (i = 0; i < locked_base_nodes_stack_ptr->pos; i++) { - current_node = locked_base_nodes_stack_ptr->array[i]; - base_node = ¤t_node->u.base; - if (locked_base_nodes_stack_ptr->pos > 1) { - base_node->lock_statistics = /* This is not atomic which is fine as */ - base_node->lock_statistics + /* correctness does not depend on that. */ - ERL_DB_CATREE_LOCK_MORE_THAN_ONE_CONTRIBUTION; - } - runlock_base_node(base_node); - } - if (locked_base_nodes_stack_ptr->size > STACK_NEED) { - erts_db_free(ERTS_ALC_T_DB_STK, tbl, - locked_base_nodes_stack_ptr->array, - sizeof(DbTableCATreeNode *) * locked_base_nodes_stack_ptr->size); - } -} - -static ERTS_INLINE -void init_stack(CATreeNodeStack *stack, - DbTableCATreeNode **stack_array, - Uint init_size) -{ - stack->array = stack_array; - stack->pos = 0; - stack->size = init_size; -} - static ERTS_INLINE void init_tree_stack(DbTreeStack *stack, TreeDbTerm **stack_array, @@ -1205,191 +1047,6 @@ void init_tree_stack(DbTreeStack *stack, stack->slot = init_slot; } -#define DEC_ROUTE_NODE_STACK_AND_ARRAY(STACK_NAME) \ - CATreeNodeStack STACK_NAME; \ - CATreeNodeStack * STACK_NAME##_ptr = &(STACK_NAME); \ - DbTableCATreeNode *STACK_NAME##_array[STACK_NEED]; - -#define DECLARE_AND_INIT_BASE_NODE_SEARCH_STACKS \ -DEC_ROUTE_NODE_STACK_AND_ARRAY(search_stack) \ -DEC_ROUTE_NODE_STACK_AND_ARRAY(search_stack_copy) \ -DEC_ROUTE_NODE_STACK_AND_ARRAY(locked_base_nodes_stack) \ -init_stack(&search_stack, search_stack_array, 0); \ -init_stack(&search_stack_copy, search_stack_copy_array, 0); \ -init_stack(&locked_base_nodes_stack, locked_base_nodes_stack_array, STACK_NEED);/* Abuse as stack array size*/ - -/* - * Locks and returns the base node that contains the specified key if - * it is present. The function saves the search path to the found base - * node in search_stack_ptr and adds the found base node to - * locked_base_nodes_stack_ptr. - */ -static ERTS_INLINE DbTableCATreeBaseNode * -lock_base_node_with_key(DbTable *tbl, - Eterm key, - CATreeNodeStack * search_stack_ptr, - CATreeNodeStack * locked_base_nodes_stack_ptr) -{ - int retry; - DbTableCATreeNode *current_node; - DbTableCATreeBaseNode *base_node; - DbTableCATree* tb = &tbl->catree; - do { - retry = 0; - current_node = GET_ROOT_ACQB(tb); - while ( ! current_node->is_base_node ) { - PUSH_NODE(search_stack_ptr, current_node); - if( cmp_key_route(key,current_node) < 0 ) { - current_node = GET_LEFT_ACQB(current_node); - } else { - current_node = GET_RIGHT_ACQB(current_node); - } - } - base_node = ¤t_node->u.base; - rlock_base_node(base_node); - if ( ! base_node->is_valid ) { - /* Retry */ - runlock_base_node(base_node); - retry = 1; - } - } while(retry); - push_node_dyn_array(tbl, locked_base_nodes_stack_ptr, current_node); - return base_node; -} - -/* - * Joins a base node with it's right neighbor. Returns the base node - * resulting from the join in locked state or NULL if there is no base - * node to join with. - */ -static DbTableCATreeNode* -erl_db_catree_force_join_right(DbTableCATree *tb, - DbTableCATreeNode *parent, - DbTableCATreeNode *thiz, - DbTableCATreeNode **result_parent_wb) -{ - DbTableCATreeNode *gparent; - DbTableCATreeNode *neighbor; - DbTableCATreeNode *new_neighbor; - DbTableCATreeNode *neighbor_parent; - TreeDbTerm* new_root; - - if (parent == NULL) { - return NULL; - } - ASSERT(thiz == GET_LEFT(parent)); - while (1) { - neighbor = leftmost_base_node(GET_RIGHT_ACQB(parent)); - wlock_base_node_no_stats(&neighbor->u.base); - if (neighbor->u.base.is_valid) - break; - wunlock_base_node(&neighbor->u.base); - } - lock_route_node(parent); - parent->u.route.is_valid = 0; - neighbor->u.base.is_valid = 0; - thiz->u.base.is_valid = 0; - while (1) { - gparent = parent_of(tb, parent); - if (gparent == NULL) - break; - lock_route_node(gparent); - if (gparent->u.route.is_valid) - break; - unlock_route_node(gparent); - } - if (gparent == NULL) { - SET_ROOT_RELB(tb, GET_RIGHT(parent)); - } else if (GET_LEFT(gparent) == parent) { - SET_LEFT_RELB(gparent, GET_RIGHT(parent)); - } else { - SET_RIGHT_RELB(gparent, GET_RIGHT(parent)); - } - unlock_route_node(parent); - if (gparent != NULL) { - unlock_route_node(gparent); - } - - new_root = join_trees(thiz->u.base.root, neighbor->u.base.root); - new_neighbor = create_wlocked_base_node(tb, new_root, - LC_ORDER(thiz->u.base.lc_key.term)); - - if (GET_RIGHT(parent) == neighbor) { - neighbor_parent = gparent; - } else { - neighbor_parent = leftmost_route_node(GET_RIGHT(parent)); - } - if(neighbor_parent == NULL) { - SET_ROOT_RELB(tb, new_neighbor); - } else if (GET_LEFT(neighbor_parent) == neighbor) { - SET_LEFT_RELB(neighbor_parent, new_neighbor); - } else { - SET_RIGHT_RELB(neighbor_parent, new_neighbor); - } - wunlock_base_node(&thiz->u.base); - wunlock_base_node(&neighbor->u.base); - /* Free the parent and base */ - erts_schedule_db_free(&tb->common, - do_free_route_node, - parent, - &parent->u.route.free_item, - sizeof_route_node(parent->u.route.key.size)); - erts_schedule_db_free(&tb->common, - do_free_base_node, - thiz, - &thiz->u.base.free_item, - sizeof_base_node(thiz->u.base.lc_key.size)); - erts_schedule_db_free(&tb->common, - do_free_base_node, - neighbor, - &neighbor->u.base.free_item, - sizeof_base_node(neighbor->u.base.lc_key.size)); - - *result_parent_wb = neighbor_parent; - return new_neighbor; -} - -/* - * Used to merge together all base nodes for operations such as last - * and select_*. Returns the base node resulting from the merge in - * locked state. - */ -static DbTableCATreeNode * -merge_to_one_locked_base_node(DbTableCATree* tb) -{ - DbTableCATreeNode *parent; - DbTableCATreeNode *new_parent; - DbTableCATreeNode *base; - DbTableCATreeNode *new_base; - int is_not_valid; - /* Find first base node */ - do { - parent = NULL; - base = GET_ROOT_ACQB(tb); - while ( ! base->is_base_node ) { - parent = base; - base = GET_LEFT_ACQB(base); - } - wlock_base_node_no_stats(&(base->u.base)); - is_not_valid = ! base->u.base.is_valid; - if (is_not_valid) { - wunlock_base_node(&(base->u.base)); - } - } while(is_not_valid); - do { - new_base = erl_db_catree_force_join_right(tb, - parent, - base, - &new_parent); - if (new_base != NULL) { - base = new_base; - parent = new_parent; - } - } while(new_base != NULL); - return base; -} - - static void join_catree(DbTableCATree *tb, DbTableCATreeNode *parent, DbTableCATreeNode *thiz) diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c index 987e370341..018c82aabb 100644 --- a/erts/emulator/beam/erl_lock_check.c +++ b/erts/emulator/beam/erl_lock_check.c @@ -1034,11 +1034,6 @@ erts_lc_trylock_force_busy_flg(erts_lc_lock_t *lck, erts_lock_options_t options) #endif } -/* - * locked = 0 trylock failed - * locked > 0 trylock succeeded - * locked < 0 prelocking of newly created lock (no lock order check) - */ void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t options, char *file, unsigned int line) { @@ -1069,7 +1064,7 @@ void erts_lc_trylock_flg_x(int locked, erts_lc_lock_t *lck, erts_lock_options_t for (tl_lck = thr->locked.last; tl_lck; tl_lck = tl_lck->prev) { int order = compare_locked_by_id_extra(tl_lck, lck); if (order <= 0) { - if (order == 0 && locked >= 0) + if (order == 0) lock_twice("Trylocking", thr, lck, options); if (locked) { ll->next = tl_lck->next; |