Merge branch 'rickard/timer-optimization/OTP-12650'

* rickard/timer-optimization/OTP-12650:
  Optimized timer implementation
  Reusable red-black tree implementation

Conflicts:
	erts/emulator/beam/erl_bif_timer.c

1 files changed, 72 insertions, 20 deletions

diff --git a/erts/emulator/beam/erl_process_lock.h b/erts/emulator/beam/erl_process_lock.h
index 052d992d3f..8957e7773b 100644
--- a/erts/emulator/beam/erl_process_lock.h
+++ b/erts/emulator/beam/erl_process_lock.h
@@ -65,7 +65,7 @@
 
 #endif
 
-#define ERTS_PROC_LOCK_MAX_BIT 3
+#define ERTS_PROC_LOCK_MAX_BIT 4
 
 typedef erts_aint32_t ErtsProcLocks;
 
@@ -81,17 +81,18 @@ typedef struct erts_proc_lock_t_ {
     erts_lcnt_lock_t lcnt_main;
     erts_lcnt_lock_t lcnt_link;
     erts_lcnt_lock_t lcnt_msgq;
+    erts_lcnt_lock_t lcnt_btm;
     erts_lcnt_lock_t lcnt_status;
 #endif
 #elif ERTS_PROC_LOCK_RAW_MUTEX_IMPL
     erts_mtx_t main;
     erts_mtx_t link;
     erts_mtx_t msgq;
+    erts_mtx_t btm;
     erts_mtx_t status;
 #else
 #  error "no implementation"
 #endif
-    erts_atomic32_t refc;
 #ifdef ERTS_PROC_LOCK_DEBUG
     erts_smp_atomic32_t locked[ERTS_PROC_LOCK_MAX_BIT+1];
 #endif
@@ -120,11 +121,17 @@ typedef struct erts_proc_lock_t_ {
  * Message queue lock:
  *   Protects the following fields in the process structure:
  *   * msg_inq
- *   * bif_timers
  */
 #define ERTS_PROC_LOCK_MSGQ		(((ErtsProcLocks) 1) << 2)
 
 /*
+ * Bif timer lock:
+ *   Protects the following fields in the process structure:
+ *   * bif_timers
+ */
+#define ERTS_PROC_LOCK_BTM		(((ErtsProcLocks) 1) << 3)
+
+/*
  * Status lock:
  *   Protects the following fields in the process structure:
  *   * pending_suspenders
@@ -463,6 +470,9 @@ erts_smp_proc_raw_trylock__(Process *p, ErtsProcLocks locks)
     if (locks & ERTS_PROC_LOCK_MSGQ)
 	if (erts_mtx_trylock(&p->lock.msgq) == EBUSY)
 	    goto busy_msgq;
+    if (locks & ERTS_PROC_LOCK_BTM)
+	if (erts_mtx_trylock(&p->lock.btm) == EBUSY)
+	    goto busy_btm;
     if (locks & ERTS_PROC_LOCK_STATUS)
 	if (erts_mtx_trylock(&p->lock.status) == EBUSY)
 	    goto busy_status;
@@ -470,6 +480,9 @@ erts_smp_proc_raw_trylock__(Process *p, ErtsProcLocks locks)
     return 0;
 
 busy_status:
+    if (locks & ERTS_PROC_LOCK_BTM)
+	erts_mtx_unlock(&p->lock.btm);
+busy_btm:
     if (locks & ERTS_PROC_LOCK_MSGQ)
 	erts_mtx_unlock(&p->lock.msgq);
 busy_msgq:
@@ -549,6 +562,8 @@ erts_smp_proc_lock__(Process *p,
 	erts_mtx_lock(&p->lock.link);
     if (locks & ERTS_PROC_LOCK_MSGQ)
 	erts_mtx_lock(&p->lock.msgq);
+    if (locks & ERTS_PROC_LOCK_BTM)
+	erts_mtx_lock(&p->lock.btm);
     if (locks & ERTS_PROC_LOCK_STATUS)
 	erts_mtx_lock(&p->lock.status);
 
@@ -638,6 +653,8 @@ erts_smp_proc_unlock__(Process *p,
 
     if (locks & ERTS_PROC_LOCK_STATUS)
 	erts_mtx_unlock(&p->lock.status);
+    if (locks & ERTS_PROC_LOCK_BTM)
+	erts_mtx_unlock(&p->lock.btm);
     if (locks & ERTS_PROC_LOCK_MSGQ)
 	erts_mtx_unlock(&p->lock.msgq);
     if (locks & ERTS_PROC_LOCK_LINK)
@@ -752,9 +769,10 @@ ERTS_GLB_INLINE void erts_smp_proc_lock(Process *, ErtsProcLocks);
 ERTS_GLB_INLINE void erts_smp_proc_unlock(Process *, ErtsProcLocks);
 ERTS_GLB_INLINE int erts_smp_proc_trylock(Process *, ErtsProcLocks);
 
-ERTS_GLB_INLINE void erts_smp_proc_inc_refc(Process *);
-ERTS_GLB_INLINE void erts_smp_proc_dec_refc(Process *);
-ERTS_GLB_INLINE void erts_smp_proc_add_refc(Process *, Sint32);
+ERTS_GLB_INLINE void erts_proc_inc_refc(Process *);
+ERTS_GLB_INLINE void erts_proc_dec_refc(Process *);
+ERTS_GLB_INLINE void erts_proc_add_refc(Process *, Sint);
+ERTS_GLB_INLINE Sint erts_proc_read_refc(Process *);
 
 #if ERTS_GLB_INLINE_INCL_FUNC_DEF
 
@@ -814,28 +832,59 @@ erts_smp_proc_trylock(Process *p, ErtsProcLocks locks)
 #endif
 }
 
-ERTS_GLB_INLINE void erts_smp_proc_inc_refc(Process *p)
+ERTS_GLB_INLINE void erts_proc_inc_refc(Process *p)
 {
+    ASSERT(!(erts_smp_atomic32_read_nob(&p->state) & ERTS_PSFLG_PROXY));
 #ifdef ERTS_SMP
+    erts_ptab_atmc_inc_refc(&p->common);
+#else
     erts_ptab_inc_refc(&p->common);
 #endif
 }
 
-ERTS_GLB_INLINE void erts_smp_proc_dec_refc(Process *p)
+ERTS_GLB_INLINE void erts_proc_dec_refc(Process *p)
 {
+    Sint referred;
+    ASSERT(!(erts_smp_atomic32_read_nob(&p->state) & ERTS_PSFLG_PROXY));
 #ifdef ERTS_SMP
-    int referred = erts_ptab_dec_test_refc(&p->common);
-    if (!referred)
-	erts_free_proc(p);
+    referred = erts_ptab_atmc_dec_test_refc(&p->common);
+#else
+    referred = erts_ptab_dec_test_refc(&p->common);
 #endif
+    if (!referred) {
+	ASSERT(ERTS_PROC_IS_EXITING(p));
+	ASSERT(ERTS_AINT_NULL
+	       == erts_ptab_pix2intptr_ddrb(&erts_proc,
+					    internal_pid_index(p->common.id)));
+	erts_free_proc(p);
+    }
 }
 
-ERTS_GLB_INLINE void erts_smp_proc_add_refc(Process *p, Sint32 add_refc)
+ERTS_GLB_INLINE void erts_proc_add_refc(Process *p, Sint add_refc)
 {
+    Sint referred;
+    ASSERT(!(erts_smp_atomic32_read_nob(&p->state) & ERTS_PSFLG_PROXY));
 #ifdef ERTS_SMP
-    int referred = erts_ptab_add_test_refc(&p->common, add_refc);
-    if (!referred)
+    referred = erts_ptab_atmc_add_test_refc(&p->common, add_refc);
+#else
+    referred = erts_ptab_add_test_refc(&p->common, add_refc);
+#endif
+    if (!referred) {
+	ASSERT(ERTS_PROC_IS_EXITING(p));
+	ASSERT(ERTS_AINT_NULL
+	       == erts_ptab_pix2intptr_ddrb(&erts_proc,
+					    internal_pid_index(p->common.id)));
 	erts_free_proc(p);
+    }
+}
+
+ERTS_GLB_INLINE Sint erts_proc_read_refc(Process *p)
+{
+    ASSERT(!(erts_smp_atomic32_read_nob(&p->state) & ERTS_PSFLG_PROXY));
+#ifdef ERTS_SMP
+    return erts_ptab_atmc_read_refc(&p->common);
+#else
+    return erts_ptab_read_refc(&p->common);
 #endif
 }
 
@@ -868,7 +917,7 @@ void erts_proc_safelock(Process *a_proc,
 
 #define ERTS_P2P_FLG_ALLOW_OTHER_X	(1 <<  0)
 #define ERTS_P2P_FLG_TRY_LOCK		(1 <<  1)
-#define ERTS_P2P_FLG_SMP_INC_REFC	(1 <<  2)
+#define ERTS_P2P_FLG_INC_REFC		(1 <<  2)
 
 #define ERTS_PROC_LOCK_BUSY ((Process *) &erts_invalid_process)
 
@@ -928,11 +977,14 @@ erts_pid2proc_opt(Process *c_p_unused,
 		  int flags)
 {
     Process *proc = erts_proc_lookup_raw(pid);
-    return ((!(flags & ERTS_P2P_FLG_ALLOW_OTHER_X)
-	     && proc
-	     && ERTS_PROC_IS_EXITING(proc))
-	    ? NULL
-	    : proc);
+    if (!proc)
+	return NULL;
+    if (!(flags & ERTS_P2P_FLG_ALLOW_OTHER_X)
+	&& ERTS_PROC_IS_EXITING(proc))
+	return NULL;
+    if (flags & ERTS_P2P_FLG_INC_REFC)
+	erts_proc_inc_refc(proc);
+    return proc;
 }
 #endif /* !ERTS_SMP */