From 4324d0a42124a9e9be42c8bb2879db4660acb9e9 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 3 Oct 2018 17:17:57 +0200 Subject: erts: Add lock order check for route nodes Lock order is reverse tree depth, from leafs toward root. This solution may eventually fail if running too long as route nodes do not increase their 'lc_order' in a join operation when they move up in the tree. But who runs a VM with lock-checker for such a long time? --- erts/emulator/beam/erl_db_catree.c | 34 ++++++++++++++++++++++++---------- erts/emulator/beam/erl_db_catree.h | 3 +++ erts/emulator/beam/erl_lock_check.c | 2 +- 3 files changed, 28 insertions(+), 11 deletions(-) (limited to 'erts/emulator') diff --git a/erts/emulator/beam/erl_db_catree.c b/erts/emulator/beam/erl_db_catree.c index cadfc3b405..77fd07277f 100644 --- a/erts/emulator/beam/erl_db_catree.c +++ b/erts/emulator/beam/erl_db_catree.c @@ -786,11 +786,11 @@ void unlock_route_node(DbTableCATreeNode *route_node) # define sizeof_base_node(KEY_SZ) \ (offsetof(DbTableCATreeNode, u.base.lc.key_heap) \ + (KEY_SZ)*sizeof(Eterm)) -# define LC_KEY(KEY) KEY +# define LC_ORDER(ORDER) ORDER #else # define sizeof_base_node(KEY_SZ) \ offsetof(DbTableCATreeNode, u.base.end_of_struct__) -# define LC_KEY(KEY) NIL +# define LC_ORDER(ORDER) NIL #endif static DbTableCATreeNode *create_base_node(DbTableCATree *tb, @@ -857,7 +857,8 @@ static DbTableCATreeNode* create_route_node(DbTableCATree *tb, DbTableCATreeNode *left, DbTableCATreeNode *right, - DbTerm * keyTerm) + DbTerm * keyTerm, + DbTableCATreeNode* lc_parent) { Eterm* top; Eterm key = GETKEY(tb,keyTerm->tpl); @@ -882,8 +883,20 @@ create_route_node(DbTableCATree *tb, p->u.route.is_valid = 1; erts_atomic_init_nob(&p->u.route.left, (erts_aint_t)left); erts_atomic_init_nob(&p->u.route.right, (erts_aint_t)right); +#ifdef ERTS_ENABLE_LOCK_CHECK + /* Route node lock order is inverse tree depth (from leafs toward root) */ + p->u.route.lc_order = (lc_parent == NULL ? MAX_SMALL : + lc_parent->u.route.lc_order - 1); + /* + * This assert may eventually fail as we don't increase 'lc_order' in join + * operations when route nodes move up in the tree. + * Tough luck if you run a lock-checking VM for such a long time on 32-bit. + */ + ERTS_LC_ASSERT(p->u.route.lc_order >= 0); +#endif erts_mtx_init(&p->u.route.lock, "erl_db_catree_route_node", - NIL, ERTS_LOCK_FLAGS_CATEGORY_DB); + LC_ORDER(make_small(p->u.route.lc_order)), + ERTS_LOCK_FLAGS_CATEGORY_DB); return p; } @@ -1266,7 +1279,7 @@ erl_db_catree_force_join_right(DbTableCATree *tb, TreeDbTerm* new_root = join_trees(thiz->u.base.root, neighbor->u.base.root); new_neighbor = create_wlocked_base_node(tb, new_root, - LC_KEY(thiz->u.base.lc.key)); + LC_ORDER(thiz->u.base.lc.key)); } if (GET_RIGHT(parent) == neighbor) { @@ -1407,7 +1420,7 @@ static void join_catree(DbTableCATree *tb, TreeDbTerm* new_root = join_trees(thiz->u.base.root, neighbor->u.base.root); new_neighbor = create_base_node(tb, new_root, - LC_KEY(thiz->u.base.lc.key)); + LC_ORDER(thiz->u.base.lc.key)); } if (GET_RIGHT(parent) == neighbor) { neighbor_parent = gparent; @@ -1460,7 +1473,7 @@ static void join_catree(DbTableCATree *tb, TreeDbTerm* new_root = join_trees(neighbor->u.base.root, thiz->u.base.root); new_neighbor = create_base_node(tb, new_root, - LC_KEY(thiz->u.base.lc.key)); + LC_ORDER(thiz->u.base.lc.key)); } if (GET_LEFT(parent) == neighbor) { neighbor_parent = gparent; @@ -1518,13 +1531,14 @@ static void split_catree(DbTableCATree *tb, &left_tree, &right_tree); new_left = create_base_node(tb, left_tree, - LC_KEY(GETKEY(tb, left_tree->dbterm.tpl))); + LC_ORDER(GETKEY(tb, left_tree->dbterm.tpl))); new_right = create_base_node(tb, right_tree, - LC_KEY(GETKEY(tb, right_tree->dbterm.tpl))); + LC_ORDER(GETKEY(tb, right_tree->dbterm.tpl))); new_route = create_route_node(tb, new_left, new_right, - &splitOutWriteBack->dbterm); + &splitOutWriteBack->dbterm, + parent); if (parent == NULL) { SET_ROOT_RELB(tb, new_route); } else if(GET_LEFT(parent) == base) { diff --git a/erts/emulator/beam/erl_db_catree.h b/erts/emulator/beam/erl_db_catree.h index 07a48d5bd3..0ad921d880 100644 --- a/erts/emulator/beam/erl_db_catree.h +++ b/erts/emulator/beam/erl_db_catree.h @@ -53,6 +53,9 @@ typedef struct { } DbTableCATreeBaseNode; typedef struct { +#ifdef ERTS_ENABLE_LOCK_CHECK + Sint lc_order; +#endif ErtsThrPrgrLaterOp free_item; /* Used when freeing using thread progress */ erts_mtx_t lock; /* Used when joining route nodes */ int is_valid; /* If this route node is still valid */ diff --git a/erts/emulator/beam/erl_lock_check.c b/erts/emulator/beam/erl_lock_check.c index 7cc347f810..d68ddcc748 100644 --- a/erts/emulator/beam/erl_lock_check.c +++ b/erts/emulator/beam/erl_lock_check.c @@ -93,7 +93,7 @@ static erts_lc_lock_order_t erts_lock_order[] = { { "db_tab_fix", "address" }, { "db_hash_slot", "address" }, { "erl_db_catree_base_node", "term" }, - { "erl_db_catree_route_node", "dynamic" }, + { "erl_db_catree_route_node", "index" }, { "resource_monitors", "address" }, { "driver_list", NULL }, { "proc_msgq", "pid" }, -- cgit v1.2.3