aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_db_catree.c
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2018-10-03 17:17:57 +0200
committerSverker Eriksson <[email protected]>2018-10-03 19:00:53 +0200
commit4324d0a42124a9e9be42c8bb2879db4660acb9e9 (patch)
treef85781c0b4d9491443802bf550c714b6ea366ba4 /erts/emulator/beam/erl_db_catree.c
parentd988f91307b2922de79f92d3b9aa160ac947b44c (diff)
downloadotp-4324d0a42124a9e9be42c8bb2879db4660acb9e9.tar.gz
otp-4324d0a42124a9e9be42c8bb2879db4660acb9e9.tar.bz2
otp-4324d0a42124a9e9be42c8bb2879db4660acb9e9.zip
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?
Diffstat (limited to 'erts/emulator/beam/erl_db_catree.c')
-rw-r--r--erts/emulator/beam/erl_db_catree.c34
1 files changed, 24 insertions, 10 deletions
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) {