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, 41 insertions, 164 deletions

diff --git a/erts/preloaded/src/erlang.erl b/erts/preloaded/src/erlang.erl
index 629702fc1c..4ef4288ead 100644
--- a/erts/preloaded/src/erlang.erl
+++ b/erts/preloaded/src/erlang.erl
@@ -129,10 +129,11 @@
 -export([process_display/2]).
 -export([process_flag/3, process_info/1, processes/0, purge_module/1]).
 -export([put/2, raise/3, read_timer/1, read_timer/2, ref_to_list/1, register/2]).
--export([registered/0, resume_process/1, round/1, self/0, send_after/3]).
+-export([send_after/3, send_after/4, start_timer/3, start_timer/4]).
+-export([registered/0, resume_process/1, round/1, self/0]).
 -export([seq_trace/2, seq_trace_print/1, seq_trace_print/2, setnode/2]).
 -export([setnode/3, size/1, spawn/3, spawn_link/3, split_binary/2]).
--export([start_timer/3, suspend_process/2, system_monitor/0]).
+-export([suspend_process/2, system_monitor/0]).
 -export([system_monitor/1, system_monitor/2, system_profile/0]).
 -export([system_profile/2, throw/1, time/0, trace/3, trace_delivered/1]).
 -export([trace_info/2, trunc/1, tuple_size/1, universaltime/0]).
@@ -427,23 +428,9 @@ call_on_load_function(_P1) ->
 -spec erlang:cancel_timer(TimerRef) -> Time | false when
       TimerRef :: reference(),
       Time :: non_neg_integer().
-cancel_timer(TimerRef) ->
-    try
-	case erts_internal:access_bif_timer(TimerRef) of
-	    undefined ->
-		false;
-	    {BTR, TSrv} ->
-		Req = erlang:make_ref(),
-		TSrv ! {cancel_timeout, BTR, erlang:self(),
-			true, Req, TimerRef},
-		receive
-		    {cancel_timer, Req, Result} ->
-			Result
-		end
-	end
-    catch
-	_:_ -> erlang:error(badarg, [TimerRef])
-    end.
+
+cancel_timer(_TimerRef) ->
+    erlang:nif_error(undefined).
 
 %% cancel_timer/2
 -spec erlang:cancel_timer(TimerRef, Options) -> Time | false | ok when
@@ -451,53 +438,9 @@ cancel_timer(TimerRef) ->
       Option :: {async, boolean()} | {info, boolean()},
       Options :: [Option],
       Time :: non_neg_integer().
-cancel_timer(TimerRef, Options) ->
-    try
-	{Async, Info} = get_cancel_timer_options(Options, false, true),
-	case erts_internal:access_bif_timer(TimerRef) of
-	    undefined ->
-		case {Async, Info} of
-		    {true, true} ->
-			erlang:self() ! {cancel_timer, TimerRef, false}, ok;
-		    {false, true} ->
-			false;
-		    _ ->
-			ok
-		end;
-	    {BTR, TSrv} ->
-		case Async of
-		    true ->
-			TSrv ! {cancel_timeout, BTR, erlang:self(),
-				Info, TimerRef, TimerRef},
-			ok;
-		    false ->
-			Req = erlang:make_ref(),
-			TSrv ! {cancel_timeout, BTR, erlang:self(),
-				true, Req, TimerRef},
-			receive
-			    {cancel_timer, Req, Result} ->
-				case Info of
-				    true -> Result;
-				    false -> ok
-				end
-			end
-		end
-	end
-    catch
-	_:_ -> erlang:error(badarg, [TimerRef, Options])
-    end.
 
-get_cancel_timer_options([], Async, Info) ->
-    {Async, Info};
-get_cancel_timer_options([{async, Bool} | Opts],
-			 _Async, Info) when Bool == true;
-					    Bool == false ->
-    get_cancel_timer_options(Opts, Bool, Info);
-get_cancel_timer_options([{info, Bool} | Opts],
-			 Async, _Info) when Bool == true;
-					    Bool == false ->
-    get_cancel_timer_options(Opts, Async, Bool).
-    
+cancel_timer(_TimerRef, _Options) ->
+    erlang:nif_error(undefined).
 
 %% check_old_code/1
 -spec check_old_code(Module) -> boolean() when
@@ -1538,8 +1481,8 @@ raise(_Class, _Reason, _Stacktrace) ->
 -spec erlang:read_timer(TimerRef) -> non_neg_integer() | false when
       TimerRef :: reference().
 
-read_timer(TimerRef) ->
-    read_timer(TimerRef, []).
+read_timer(_TimerRef) ->
+    erlang:nif_error(undefined).
 
 %% read_timer/2
 -spec erlang:read_timer(TimerRef, Options) -> non_neg_integer() | false | ok when
@@ -1547,43 +1490,8 @@ read_timer(TimerRef) ->
       Option :: {async, boolean()},
       Options :: [Option].
 
-read_timer(TimerRef, Options) ->
-    try
-	Async = get_read_timer_options(Options, false),
-	case erts_internal:access_bif_timer(TimerRef) of
-	    undefined ->
-		case Async of
-		    true ->
-			erlang:self() ! {read_timer, TimerRef, false},
-			ok;
-		    false ->
-			false
-		end;
-	    {BTR, TSrv} ->
-		case Async of
-		    true ->
-			TSrv ! {read_timeout, BTR, erlang:self(),
-				TimerRef, TimerRef},
-			ok;
-		    false ->
-			Req = erlang:make_ref(),
-			TSrv ! {read_timeout, BTR, erlang:self(),
-				Req, TimerRef},
-			receive
-			    {read_timer, Req, Result} ->
-				Result
-			end
-		end
-	end
-    catch
-	_:_ -> erlang:error(badarg, [TimerRef])
-    end.
-
-get_read_timer_options([], Async) ->
-    Async;
-get_read_timer_options([{async, Bool} | Opts],
-		       _Async) when Bool == true; Bool == false ->
-    get_read_timer_options(Opts, Bool).
+read_timer(_TimerRef, _Options) ->
+    erlang:nif_error(undefined).
 
 %% ref_to_list/1
 -spec erlang:ref_to_list(Ref) -> string() when
@@ -1630,35 +1538,20 @@ self() ->
       Msg :: term(),
       TimerRef :: reference().
 
-send_after(0, Dest, Msg) ->
-    try
-	true = ((erlang:is_pid(Dest)
-		 andalso erlang:node(Dest) == erlang:node())
-		orelse (erlang:is_atom(Dest)
-			andalso Dest /= undefined)),
-	try Dest ! Msg catch _:_ -> ok end,
-	erlang:make_ref()
-    catch
-	_:_ ->
-	    erlang:error(badarg, [0, Dest, Msg])
-    end;
-send_after(Time, Dest, Msg) ->
-    Now = erlang:monotonic_time(),
-    try
-	true = ((erlang:is_pid(Dest)
-		 andalso erlang:node(Dest) == erlang:node())
-		orelse (erlang:is_atom(Dest)
-			andalso Dest /= undefined)),
-	true = Time > 0,
-	true = Time < (1 bsl 32), % Maybe lift this restriction...
-	TO = Now + (erts_internal:time_unit()*Time) div 1000,
-	{BTR, TSrv, TRef} = erts_internal:create_bif_timer(),
-	TSrv ! {set_timeout, BTR, Dest, TO, TRef, Msg},
-	TRef
-    catch
-	_:_ ->
-	    erlang:error(badarg, [Time, Dest, Msg])
-    end.
+send_after(_Time, _Dest, _Msg) ->
+    erlang:nif_error(undefined).
+
+%% send_after/4
+-spec erlang:send_after(Time, Dest, Msg, Options) -> TimerRef when
+      Time :: integer(),
+      Dest :: pid() | atom(),
+      Msg :: term(),
+      Options :: [Option],
+      Option :: {abs, boolean()} | {accessor, pid()},
+      TimerRef :: reference().
+
+send_after(_Time, _Dest, _Msg, _Options) ->
+    erlang:nif_error(undefined).
 
 %% seq_trace/2
 -spec erlang:seq_trace(P1, P2) -> seq_trace_info_returns() | {term(), term(), term(), term(), term()} when
@@ -1731,37 +1624,21 @@ split_binary(_Bin, _Pos) ->
       Dest :: pid() | atom(),
       Msg :: term(),
       TimerRef :: reference().
-start_timer(0, Dest, Msg) ->
-    try
-	true = ((erlang:is_pid(Dest)
-		 andalso erlang:node(Dest) == erlang:node())
-		orelse (erlang:is_atom(Dest)
-			andalso Dest /= undefined)),
-	TimerRef = erlang:make_ref(),
-	_ = try Dest ! {timeout, TimerRef, Msg} catch _:_ -> ok end,
-	TimerRef
-    catch
-	_:_ ->
-	    erlang:error(badarg, [0, Dest, Msg])
-    end;
-start_timer(Time, Dest, Msg) ->
-    Now = erlang:monotonic_time(),
-    try
-	true = ((erlang:is_pid(Dest)
-		 andalso erlang:node(Dest) == erlang:node())
-		orelse (erlang:is_atom(Dest)
-			andalso Dest /= undefined)),
-	true = Time > 0,
-	true = Time < (1 bsl 32), % Maybe lift this restriction...
-	TO = Now + (erts_internal:time_unit()*Time) div 1000,
-	{BTR, TSrv, TimerRef} = erts_internal:create_bif_timer(),
-	TSrv ! {set_timeout, BTR, Dest, TO, TimerRef,
-		{timeout, TimerRef, Msg}},
-	TimerRef
-    catch
-	_:_ ->
-	    erlang:error(badarg, [Time, Dest, Msg])
-    end.
+
+start_timer(_Time, _Dest, _Msg) ->
+    erlang:nif_error(undefined).
+
+%% start_timer/4
+-spec erlang:start_timer(Time, Dest, Msg, Options) -> TimerRef when
+      Time :: integer(),
+      Dest :: pid() | atom(),
+      Msg :: term(),
+      Options :: [Option],
+      Option :: {abs, boolean()} | {accessor, pid()},
+      TimerRef :: reference().
+
+start_timer(_Time, _Dest, _Msg, _Options) ->
+    erlang:nif_error(undefined).
 
 %% suspend_process/2
 -spec erlang:suspend_process(Suspendee, OptList) -> boolean() when