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?

3 files changed, 28 insertions, 11 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) {
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"			},