Implementation of true asynchronous signaling between processes

Communication between Erlang processes has conceptually always been
performed through asynchronous signaling. The runtime system
implementation has however previously preformed most operation
synchronously. In a system with only one true thread of execution, this
is not problematic (often the opposite). In a system with multiple threads
of execution (as current runtime system implementation with SMP support)
it becomes problematic. This since it often involves locking of structures
when updating them which in turn cause resource contention. Utilizing
true asynchronous communication often avoids these resource contention
issues.

The case that triggered this change was contention on the link lock due
to frequent updates of the monitor trees during communication with a
frequently used server. The signal order delivery guarantees of the
language makes it hard to change the implementation of only some signals
to use true asynchronous signaling. Therefore the implementations
of (almost) all signals have been changed.

Currently the following signals have been implemented as true
asynchronous signals:
- Message signals
- Exit signals
- Monitor signals
- Demonitor signals
- Monitor triggered signals (DOWN, CHANGE, etc)
- Link signals
- Unlink signals
- Group leader signals

All of the above already defined as asynchronous signals in the
language. The implementation of messages signals was quite
asynchronous to begin with, but had quite strict delivery constraints
due to the ordering guarantees of signals between a pair of processes.

The previously used message queue partitioned into two halves has been
replaced by a more general signal queue partitioned into three parts
that service all kinds of signals. More details regarding the signal
queue can be found in comments in the erl_proc_sig_queue.h file.

The monitor and link implementations have also been completely replaced
in order to fit the new asynchronous signaling implementation as good
as possible. More details regarding the new monitor and link
implementations can be found in the erl_monitor_link.h file.

1 files changed, 163 insertions, 18 deletions

diff --git a/erts/emulator/beam/erl_rbtree.h b/erts/emulator/beam/erl_rbtree.h
index e59d6900b0..e50abf5cec 100644
--- a/erts/emulator/beam/erl_rbtree.h
+++ b/erts/emulator/beam/erl_rbtree.h
@@ -1,7 +1,7 @@
 /*
  * %CopyrightBegin%
  * 
- * Copyright Ericsson AB 2015-2017. All Rights Reserved.
+ * Copyright Ericsson AB 2015-2018. All Rights Reserved.
  * 
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -50,8 +50,14 @@
  * - ERTS_RBT_GET_LEFT(T) - Get left child node.
  * - ERTS_RBT_SET_LEFT(T, L) - Set left child node.
  * - ERTS_RBT_GET_KEY(T) - Get key of node.
- * - ERTS_RBT_IS_LT(KX, KY) - Is key KX less than key KY?
- * - ERTS_RBT_IS_EQ(KX, KY) - Is key KX equal to key KY?
+ * Either:
+ *   - ERTS_RBT_CMP_KEYS(KX, KY) - Compare keys...
+ * or:
+ *   - ERTS_RBT_IS_LT(KX, KY) - Is key KX less than key KY?
+ *   - ERTS_RBT_IS_EQ(KX, KY) - Is key KX equal to key KY?
+ *
+ * If ERTS_RBT_CMP_KEYS is defined ERTS_RBT_IS_LT and
+ * ERTS_RBT_IS_EQ will be redefined using ERTS_RBT_CMP_KEYS
  *
  * Optional defines:
  *
@@ -337,6 +343,15 @@
  *         Should only be used for debuging.
  */
 
+#ifdef ERTS_RBT_CMP_KEYS
+
+#  undef ERTS_RBT_IS_LT
+#  define ERTS_RBT_IS_LT(KX, KY) (ERTS_RBT_CMP_KEYS((KX), (KY)) < 0)
+
+#  undef ERTS_RBT_IS_EQ
+#  define ERTS_RBT_IS_EQ(KX, KY) (ERTS_RBT_CMP_KEYS((KX), (KY)) == 0)
+
+#endif
 
 /*
  * Check that we have all mandatory defines
@@ -396,6 +411,16 @@
 #  error Missing definition of ERTS_RBT_IS_EQ
 #endif
 
+#undef ERTS_RBT_IS_GT__
+#ifdef ERTS_RBT_CMP_KEYS
+#  define ERTS_RBT_IS_GT__(KX, KY) \
+    (ERTS_RBT_CMP_KEYS((KX), (KY)) > 0)
+#else
+#  define ERTS_RBT_IS_GT__(KX, KY) \
+    (!ERTS_RBT_IS_LT((KX), (KY)) && !ERTS_RBT_IS_EQ((KX), (KY)))
+
+#endif
+
 #if defined(ERTS_RBT_HARD_DEBUG) || defined(DEBUG)
 #  ifndef ERTS_RBT_DEBUG
 #    define ERTS_RBT_DEBUG 1
@@ -1007,19 +1032,30 @@ ERTS_RBT_FUNC__(insert_aux__)(ERTS_RBT_T **root, ERTS_RBT_T *n, int lookup)
 	ERTS_RBT_T *p, *x = *root;
 
 	while (1) {
-	    ERTS_RBT_KEY_T kx;
+	    ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x);
 	    ERTS_RBT_T *c;
+            int kres;
+#ifdef ERTS_RBT_CMP_KEYS
+            int kcmp = ERTS_RBT_CMP_KEYS(kn, kx);
+            kres = kcmp == 0;
+#else
+            kres = ERTS_RBT_IS_EQ(kn, kx);
+#endif
 
-	    kx = ERTS_RBT_GET_KEY(x);
-
-	    if (lookup && ERTS_RBT_IS_EQ(kn, kx)) {
+	    if (lookup && kres) {
 
 		ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL);
 
 		return x;
 	    }
 
-	    if (ERTS_RBT_IS_LT(kn, kx)) {
+#ifdef ERTS_RBT_CMP_KEYS
+            kres = kcmp < 0;
+#else
+            kres = ERTS_RBT_IS_LT(kn, kx);
+#endif
+
+	    if (kres) {
 		c = ERTS_RBT_GET_LEFT(x);
 		if (!c) {
 		    ERTS_RBT_SET_PARENT(n, x);
@@ -1075,6 +1111,101 @@ ERTS_RBT_FUNC__(insert)(ERTS_RBT_T **root, ERTS_RBT_T *n)
 
 #endif /* ERTS_RBT_WANT_INSERT */
 
+#ifdef ERTS_RBT_WANT_LOOKUP_CREATE
+static ERTS_INLINE ERTS_RBT_T *
+ERTS_RBT_FUNC__(lookup_create)(ERTS_RBT_T **root,
+                               ERTS_RBT_KEY_T kn,
+                               ERTS_RBT_T *(*create)(ERTS_RBT_KEY_T, void *),
+                               void *arg,
+                               int *created)
+{
+    ERTS_RBT_T *n;
+    ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL);
+
+    if (!*root) {
+        n = (*create)(kn, arg);
+        ERTS_RBT_INIT_EMPTY_TNODE(n);
+        ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+	ERTS_RBT_SET_BLACK(n);
+	*root = n;
+        *created = !0;
+#ifdef ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT
+	ERTS_RBT_UPDATE_ATTACHED_DATA_CHGROOT(NULL, n);
+#endif
+    }
+    else {
+	ERTS_RBT_T *p, *x = *root;
+
+	while (1) {
+	    ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x);
+	    ERTS_RBT_T *c;
+            int kres;
+#ifdef ERTS_RBT_CMP_KEYS
+            int kcmp = ERTS_RBT_CMP_KEYS(kn, kx);
+            kres = kcmp == 0;
+#else
+            kres = ERTS_RBT_IS_EQ(kn, kx);
+#endif
+
+	    if (kres) {
+
+		ERTS_RBT_HDBG_CHECK_TREE__(*root, NULL);
+
+                *created = 0;
+		return x;
+	    }
+
+#ifdef ERTS_RBT_CMP_KEYS
+            kres = kcmp < 0;
+#else
+            kres = ERTS_RBT_IS_LT(kn, kx);
+#endif
+
+	    if (kres) {
+		c = ERTS_RBT_GET_LEFT(x);
+		if (!c) {
+                    n = (*create)(kn, arg);
+                    ERTS_RBT_INIT_EMPTY_TNODE(n);
+                    ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+                    *created = !0;
+		    ERTS_RBT_SET_PARENT(n, x);
+		    ERTS_RBT_SET_LEFT(x, n);
+		    p = x;
+		    break;
+		}
+	    }
+	    else {
+		c = ERTS_RBT_GET_RIGHT(x);
+		if (!c) {
+                    n = (*create)(kn, arg);
+                    ERTS_RBT_INIT_EMPTY_TNODE(n);
+                    ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+                    *created = !0;
+		    ERTS_RBT_SET_PARENT(n, x);
+		    ERTS_RBT_SET_RIGHT(x, n);
+		    p = x;
+		    break;
+		}
+	    }
+
+	    x = c;
+	}
+
+        ERTS_RBT_ASSERT(ERTS_RBT_IS_EQ(ERTS_RBT_GET_KEY(n), kn));
+	ERTS_RBT_ASSERT(p);
+
+	ERTS_RBT_SET_RED(n);
+	if (ERTS_RBT_IS_RED(p))
+	    ERTS_RBT_FUNC__(insert_fixup__)(root, n);
+    }
+
+    ERTS_RBT_HDBG_CHECK_TREE__(*root, n);
+
+    return n;
+}
+
+#endif /* ERTS_RBT_WANT_LOOKUP_CREATE */
+
 #ifdef ERTS_RBT_WANT_LOOKUP
 
 static ERTS_RBT_API_INLINE__ ERTS_RBT_T *
@@ -1088,11 +1219,24 @@ ERTS_RBT_FUNC__(lookup)(ERTS_RBT_T *root, ERTS_RBT_KEY_T key)
     while (1) {
 	ERTS_RBT_KEY_T kx = ERTS_RBT_GET_KEY(x);
 	ERTS_RBT_T *c;
+        int kres;
+#ifdef ERTS_RBT_CMP_KEYS
+        int kcmp = ERTS_RBT_CMP_KEYS(key, kx);
+        kres = kcmp == 0;
+#else
+        kres = ERTS_RBT_IS_EQ(key, kx);
+#endif
 
-	if (ERTS_RBT_IS_EQ(key, kx))
+	if (kres)
 	    return x;
 
-	if (ERTS_RBT_IS_LT(key, kx)) {
+#ifdef ERTS_RBT_CMP_KEYS
+        kres = kcmp < 0;
+#else
+        kres = ERTS_RBT_IS_LT(key, kx);
+#endif
+
+	if (kres) {
 	    c = ERTS_RBT_GET_LEFT(x);
 	    if (!c)
 		return NULL;
@@ -1426,14 +1570,14 @@ ERTS_RBT_FUNC__(foreach_large)(ERTS_RBT_T *root,
 
 #ifdef ERTS_RBT_WANT_FOREACH_YIELDING
 
-static ERTS_RBT_API_INLINE__ void
+static ERTS_RBT_API_INLINE__ int
 ERTS_RBT_FUNC__(foreach_yielding)(ERTS_RBT_T *root,
 				  void (*op)(ERTS_RBT_T *, void *),
 				  void *arg,
 				  ERTS_RBT_YIELD_STATE_T__ *ystate,
 				  Sint ylimit)
 {
-    (void) ERTS_RBT_FUNC__(foreach_unordered__)(*root, 0, op, arg,
+    return ERTS_RBT_FUNC__(foreach_unordered__)(&root, 0, op, arg,
 						1, ystate, ylimit);
 }
 
@@ -1630,8 +1774,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
 		kx = ERTS_RBT_GET_KEY(x);
 		kc = ERTS_RBT_GET_KEY(c);
 
-		ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kc, kx)
-				|| ERTS_RBT_IS_EQ(kc, kx));
+                ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kc, kx));
 
 		x = c;
 	    }
@@ -1649,8 +1792,8 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
 	    kx = ERTS_RBT_GET_KEY(x);
 	    kc = ERTS_RBT_GET_KEY(c);
 
-	    ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kx, kc)
-			    || ERTS_RBT_IS_EQ(kx, kc));
+            ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kx, kc));
+
 	    x = c;
 	}
 
@@ -1672,8 +1815,8 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
 		    kx = ERTS_RBT_GET_KEY(x);
 		    kc = ERTS_RBT_GET_KEY(c);
 
-		    ERTS_RBT_ASSERT(ERTS_RBT_IS_LT(kx, kc)
-				    || ERTS_RBT_IS_EQ(kx, kc));
+                    ERTS_RBT_ASSERT(!ERTS_RBT_IS_GT__(kx, kc));
+
 		    /* Go down tree of x's sibling... */
 		    x = c;
 		    break;
@@ -1707,6 +1850,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
 #undef ERTS_RBT_NEED_FOREACH_ORDERED__
 #undef ERTS_RBT_NEED_HDBG_CHECK_TREE__
 #undef ERTS_RBT_HDBG_CHECK_TREE__
+#undef ERTS_RBT_IS_GT__
 
 #ifdef ERTS_RBT_UNDEF
 #  undef ERTS_RBT_PREFIX
@@ -1727,6 +1871,7 @@ ERTS_RBT_FUNC__(hdbg_check_tree)(ERTS_RBT_T *root, ERTS_RBT_T *n)
 #  undef ERTS_RBT_GET_LEFT
 #  undef ERTS_RBT_SET_LEFT
 #  undef ERTS_RBT_GET_KEY
+#  undef ERTS_RBT_CMP_KEYS
 #  undef ERTS_RBT_IS_LT
 #  undef ERTS_RBT_IS_EQ
 #  undef ERTS_RBT_UNDEF