timers: use only a single TimerWrap instance

Hang all timer lists off a single TimerWrap and use the PriorityQueue
to manage expiration priorities. This makes the Timers code clearer,
consumes significantly less resources and improves performance.

PR-URL: https://github.com/nodejs/node/pull/20555
Fixes: https://github.com/nodejs/node/issues/16105
Reviewed-By: Ben Noordhuis <info@bnoordhuis.nl>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>
Reviewed-By: Matteo Collina <matteo.collina@gmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Ruben Bridgewater <ruben@bridgewater.de>

1 files changed, 177 insertions, 198 deletions

diff --git a/lib/timers.js b/lib/timers.js
index e7f13924db..3d200344a4 100644
--- a/lib/timers.js
+++ b/lib/timers.js
@@ -26,16 +26,17 @@ const {
   setupTimers,
 } = process.binding('timer_wrap');
 const L = require('internal/linkedlist');
+const PriorityQueue = require('internal/priority_queue');
 const {
   async_id_symbol,
   trigger_async_id_symbol,
   Timeout,
+  kRefed,
   initAsyncResource,
   validateTimerDuration
 } = require('internal/timers');
 const internalUtil = require('internal/util');
 const { createPromise, promiseResolve } = process.binding('util');
-const assert = require('assert');
 const util = require('util');
 const { ERR_INVALID_CALLBACK } = require('internal/errors').codes;
 const debug = util.debuglog('timer');
@@ -55,8 +56,6 @@ const kHasOutstanding = 2;
 const [immediateInfo, toggleImmediateRef] =
   setupTimers(processImmediate, processTimers);
 
-const kRefed = Symbol('refed');
-
 // HOW and WHY the timers implementation works the way it does.
 //
 // Timers are crucial to Node.js. Internally, any TCP I/O connection creates a
@@ -85,20 +84,17 @@ const kRefed = Symbol('refed');
 //
 // Object maps are kept which contain linked lists keyed by their duration in
 // milliseconds.
-// The linked lists within also have some meta-properties, one of which is a
-// TimerWrap C++ handle, which makes the call after the duration to process the
-// list it is attached to.
 //
 /* eslint-disable node-core/non-ascii-character */
 //
 // ╔════ > Object Map
 // ║
 // ╠══
-// ║ refedLists: { '40': { }, '320': { etc } } (keys of millisecond duration)
-// ╚══          ┌─────────┘
+// ║ lists: { '40': { }, '320': { etc } } (keys of millisecond duration)
+// ╚══          ┌────┘
 //              │
 // ╔══          │
-// ║ TimersList { _idleNext: { }, _idlePrev: (self), _timer: (TimerWrap) }
+// ║ TimersList { _idleNext: { }, _idlePrev: (self) }
 // ║         ┌────────────────┘
 // ║    ╔══  │                              ^
 // ║    ║    { _idleNext: { },  _idlePrev: { }, _onTimeout: (callback) }
@@ -126,36 +122,73 @@ const kRefed = Symbol('refed');
 // always be due to timeout at a later time.
 //
 // Less-than constant time operations are thus contained in two places:
-// TimerWrap's backing libuv timers implementation (a performant heap-based
-// queue), and the object map lookup of a specific list by the duration of
-// timers within (or creation of a new list).
-// However, these operations combined have shown to be trivial in comparison to
-// other alternative timers architectures.
+// The PriorityQueue — an efficient binary heap implementation that does all
+// operations in worst-case O(log n) time — which manages the order of expiring
+// Timeout lists and the object map lookup of a specific list by the duration of
+// timers within (or creation of a new list). However, these operations combined
+// have shown to be trivial in comparison to other timers architectures.
 
 
-// Object maps containing linked lists of timers, keyed and sorted by their
+// Object map containing linked lists of timers, keyed and sorted by their
 // duration in milliseconds.
 //
-// The difference between these two objects is that the former contains timers
-// that will keep the process open if they are the only thing left, while the
-// latter will not.
-//
 // - key = time in milliseconds
 // - value = linked list
-const refedLists = Object.create(null);
-const unrefedLists = Object.create(null);
+const lists = Object.create(null);
+
+// This is a priority queue with a custom sorting function that first compares
+// the expiry times of two lists and if they're the same then compares their
+// individual IDs to determine which list was created first.
+const queue = new PriorityQueue(compareTimersLists, setPosition);
+
+function compareTimersLists(a, b) {
+  const expiryDiff = a.expiry - b.expiry;
+  if (expiryDiff === 0) {
+    if (a.id < b.id)
+      return -1;
+    if (a.id > b.id)
+      return 1;
+  }
+  return expiryDiff;
+}
+
+function setPosition(node, pos) {
+  node.priorityQueuePosition = pos;
+}
 
+let handle = null;
+let nextExpiry = Infinity;
+
+let timerListId = Number.MIN_SAFE_INTEGER;
+let refCount = 0;
+
+function incRefCount() {
+  if (refCount++ === 0)
+    handle.ref();
+}
+
+function decRefCount() {
+  if (--refCount === 0)
+    handle.unref();
+}
+
+function createHandle(refed) {
+  debug('initial run, creating TimerWrap handle');
+  handle = new TimerWrap();
+  if (!refed)
+    handle.unref();
+}
 
 // Schedule or re-schedule a timer.
 // The item must have been enroll()'d first.
 const active = exports.active = function(item) {
-  insert(item, false);
+  insert(item, true, TimerWrap.now());
 };
 
 // Internal APIs that need timeouts should use `_unrefActive()` instead of
 // `active()` so that they do not unnecessarily keep the process open.
 exports._unrefActive = function(item) {
-  insert(item, true);
+  insert(item, false, TimerWrap.now());
 };
 
 
@@ -164,23 +197,27 @@ exports._unrefActive = function(item) {
 // Appends a timer onto the end of an existing timers list, or creates a new
 // TimerWrap backed list if one does not already exist for the specified timeout
 // duration.
-function insert(item, unrefed, start) {
+function insert(item, refed, start) {
   const msecs = item._idleTimeout;
-  if (msecs < 0 || msecs === undefined) return;
-
-  if (typeof start === 'number') {
-    item._idleStart = start;
-  } else {
-    item._idleStart = TimerWrap.now();
-  }
+  if (msecs < 0 || msecs === undefined)
+    return;
 
-  const lists = unrefed === true ? unrefedLists : refedLists;
+  item._idleStart = start;
 
   // Use an existing list if there is one, otherwise we need to make a new one.
   var list = lists[msecs];
   if (list === undefined) {
     debug('no %d list was found in insert, creating a new one', msecs);
-    lists[msecs] = list = new TimersList(msecs, unrefed);
+    const expiry = start + msecs;
+    lists[msecs] = list = new TimersList(expiry, msecs);
+    queue.insert(list);
+
+    if (nextExpiry > expiry) {
+      if (handle === null)
+        createHandle(refed);
+      handle.start(msecs);
+      nextExpiry = expiry;
+    }
   }
 
   if (!item[async_id_symbol] || item._destroyed) {
@@ -188,32 +225,55 @@ function insert(item, unrefed, start) {
     initAsyncResource(item, 'Timeout');
   }
 
+  if (refed === !item[kRefed]) {
+    if (refed)
+      incRefCount();
+    else
+      decRefCount();
+  }
+  item[kRefed] = refed;
+
   L.append(list, item);
-  assert(!L.isEmpty(list)); // list is not empty
 }
 
-function TimersList(msecs, unrefed) {
+function TimersList(expiry, msecs) {
   this._idleNext = this; // Create the list with the linkedlist properties to
   this._idlePrev = this; // prevent any unnecessary hidden class changes.
-  this._unrefed = unrefed;
+  this.expiry = expiry;
+  this.id = timerListId++;
   this.msecs = msecs;
-
-  const timer = this._timer = new TimerWrap();
-  timer._list = this;
-
-  if (unrefed === true)
-    timer.unref();
-  timer.start(msecs);
+  this.priorityQueuePosition = null;
 }
 
+const { _tickCallback: runNextTicks } = process;
 function processTimers(now) {
-  if (this.owner)
-    return unrefdHandle(this.owner, now);
-  return listOnTimeout(this, now);
+  debug('process timer lists %d', now);
+  nextExpiry = Infinity;
+
+  let list, ran;
+  while (list = queue.peek()) {
+    if (list.expiry > now)
+      break;
+    if (ran)
+      runNextTicks();
+    listOnTimeout(list, now);
+    ran = true;
+  }
+
+  if (refCount > 0)
+    handle.ref();
+  else
+    handle.unref();
+
+  if (list !== undefined) {
+    nextExpiry = list.expiry;
+    handle.start(Math.max(nextExpiry - TimerWrap.now(), 1));
+  }
+
+  return true;
 }
 
-function listOnTimeout(handle, now) {
-  const list = handle._list;
+function listOnTimeout(list, now) {
   const msecs = list.msecs;
 
   debug('timeout callback %d', msecs);
@@ -226,78 +286,69 @@ function listOnTimeout(handle, now) {
     // Check if this loop iteration is too early for the next timer.
     // This happens if there are more timers scheduled for later in the list.
     if (diff < msecs) {
-      var timeRemaining = msecs - (TimerWrap.now() - timer._idleStart);
-      if (timeRemaining <= 0) {
-        timeRemaining = 1;
-      }
-      handle.start(timeRemaining);
+      list.expiry = timer._idleStart + msecs;
+      list.id = timerListId++;
+      queue.percolateDown(1);
       debug('%d list wait because diff is %d', msecs, diff);
-      return true;
+      return;
     }
 
     // The actual logic for when a timeout happens.
-
     L.remove(timer);
-    assert(timer !== L.peek(list));
+
+    const asyncId = timer[async_id_symbol];
 
     if (!timer._onTimeout) {
-      if (destroyHooksExist() && !timer._destroyed &&
-            typeof timer[async_id_symbol] === 'number') {
-        emitDestroy(timer[async_id_symbol]);
+      if (timer[kRefed])
+        refCount--;
+      timer[kRefed] = null;
+
+      if (destroyHooksExist() && !timer._destroyed) {
+        emitDestroy(asyncId);
         timer._destroyed = true;
       }
       continue;
     }
 
+    emitBefore(asyncId, timer[trigger_async_id_symbol]);
+
     tryOnTimeout(timer);
+
+    emitAfter(asyncId);
   }
 
   // If `L.peek(list)` returned nothing, the list was either empty or we have
   // called all of the timer timeouts.
-  // As such, we can remove the list and clean up the TimerWrap C++ handle.
+  // As such, we can remove the list from the object map and the PriorityQueue.
   debug('%d list empty', msecs);
-  assert(L.isEmpty(list));
-
-  // Either refedLists[msecs] or unrefedLists[msecs] may have been removed and
-  // recreated since the reference to `list` was created. Make sure they're
-  // the same instance of the list before destroying.
-  if (list._unrefed === true && list === unrefedLists[msecs]) {
-    delete unrefedLists[msecs];
-  } else if (list === refedLists[msecs]) {
-    delete refedLists[msecs];
-  }
-
-  // Do not close the underlying handle if its ownership has changed
-  // (e.g it was unrefed in its callback).
-  if (!handle.owner)
-    handle.close();
 
-  return true;
+  // The current list may have been removed and recreated since the reference
+  // to `list` was created. Make sure they're the same instance of the list
+  // before destroying.
+  if (list === lists[msecs]) {
+    delete lists[msecs];
+    queue.shift();
+  }
 }
 
 
 // An optimization so that the try/finally only de-optimizes (since at least v8
 // 4.7) what is in this smaller function.
 function tryOnTimeout(timer, start) {
-  timer._called = true;
-  const timerAsyncId = (typeof timer[async_id_symbol] === 'number') ?
-    timer[async_id_symbol] : null;
-  var threw = true;
-  if (timerAsyncId !== null)
-    emitBefore(timerAsyncId, timer[trigger_async_id_symbol]);
   if (start === undefined && timer._repeat)
     start = TimerWrap.now();
   try {
     ontimeout(timer);
-    threw = false;
   } finally {
-    if (timerAsyncId !== null) {
-      if (!threw)
-        emitAfter(timerAsyncId);
-      if (timer._repeat) {
-        rearm(timer, start);
-      } else if (destroyHooksExist() && !timer._destroyed) {
-        emitDestroy(timerAsyncId);
+    if (timer._repeat) {
+      rearm(timer, start);
+    } else {
+      if (timer[kRefed])
+        refCount--;
+      timer[kRefed] = null;
+
+      if (destroyHooksExist() && !timer._destroyed) {
+        emitDestroy(timer[async_id_symbol]);
         timer._destroyed = true;
       }
     }
@@ -305,43 +356,35 @@ function tryOnTimeout(timer, start) {
 }
 
 
-// A convenience function for re-using TimerWrap handles more easily.
-//
-// This mostly exists to fix https://github.com/nodejs/node/issues/1264.
-// Handles in libuv take at least one `uv_run` to be registered as unreferenced.
-// Re-using an existing handle allows us to skip that, so that a second `uv_run`
-// will return no active handles, even when running `setTimeout(fn).unref()`.
-function reuse(item) {
-  L.remove(item);
-
-  const list = refedLists[item._idleTimeout];
-  // if empty - reuse the watcher
-  if (list !== undefined && L.isEmpty(list)) {
-    debug('reuse hit');
-    list._timer.stop();
-    delete refedLists[item._idleTimeout];
-    return list._timer;
-  }
-
-  return null;
-}
-
-
 // Remove a timer. Cancels the timeout and resets the relevant timer properties.
 function unenroll(item) {
   // Fewer checks may be possible, but these cover everything.
   if (destroyHooksExist() &&
-      typeof item[async_id_symbol] === 'number' &&
+      item[async_id_symbol] !== undefined &&
       !item._destroyed) {
     emitDestroy(item[async_id_symbol]);
     item._destroyed = true;
   }
 
-  const handle = reuse(item);
-  if (handle !== null) {
-    debug('unenroll: list empty');
-    handle.close();
+  L.remove(item);
+
+  // We only delete refed lists because unrefed ones are incredibly likely
+  // to come from http and be recreated shortly after.
+  // TODO: Long-term this could instead be handled by creating an internal
+  // clearTimeout that makes it clear that the list should not be deleted.
+  // That function could then be used by http and other similar modules.
+  if (item[kRefed]) {
+    const list = lists[item._idleTimeout];
+    if (list !== undefined && L.isEmpty(list)) {
+      debug('unenroll: list empty');
+      queue.removeAt(list.priorityQueuePosition);
+      delete lists[list.msecs];
+    }
+
+    decRefCount();
   }
+  item[kRefed] = null;
+
   // if active is called later, then we want to make sure not to insert again
   item._idleTimeout = -1;
 }
@@ -403,7 +446,7 @@ function setTimeout(callback, after, arg1, arg2, arg3) {
       break;
   }
 
-  const timeout = new Timeout(callback, after, args, false, false);
+  const timeout = new Timeout(callback, after, args, false);
   active(timeout);
 
   return timeout;
@@ -411,7 +454,7 @@ function setTimeout(callback, after, arg1, arg2, arg3) {
 
 setTimeout[internalUtil.promisify.custom] = function(after, value) {
   const promise = createPromise();
-  const timeout = new Timeout(promise, after, [value], false, false);
+  const timeout = new Timeout(promise, after, [value], false);
   active(timeout);
 
   return promise;
@@ -430,36 +473,20 @@ function ontimeout(timer) {
     Reflect.apply(timer._onTimeout, timer, args);
 }
 
-function rearm(timer, start = TimerWrap.now()) {
+function rearm(timer, start) {
   // // Do not re-arm unenroll'd or closed timers.
-  if (timer._idleTimeout === -1) return;
-
-  // If timer is unref'd (or was - it's permanently removed from the list.)
-  if (timer._handle && timer instanceof Timeout) {
-    timer._handle.start(timer._repeat);
-  } else {
-    timer._idleTimeout = timer._repeat;
+  if (timer._idleTimeout === -1)
+    return;
 
-    const duration = TimerWrap.now() - start;
-    if (duration >= timer._repeat) {
-      // If callback duration >= timer._repeat,
-      // add 1 ms to avoid blocking eventloop
-      insert(timer, false, start + duration - timer._repeat + 1);
-    } else {
-      insert(timer, false, start);
-    }
-  }
+  timer._idleTimeout = timer._repeat;
+  insert(timer, timer[kRefed], start);
 }
 
 
 const clearTimeout = exports.clearTimeout = function clearTimeout(timer) {
   if (timer && timer._onTimeout) {
     timer._onTimeout = null;
-    if (timer instanceof Timeout) {
-      timer.close(); // for after === 0
-    } else {
-      unenroll(timer);
-    }
+    unenroll(timer);
   }
 };
 
@@ -490,7 +517,7 @@ exports.setInterval = function setInterval(callback, repeat, arg1, arg2, arg3) {
       break;
   }
 
-  const timeout = new Timeout(callback, repeat, args, true, false);
+  const timeout = new Timeout(callback, repeat, args, true);
   active(timeout);
 
   return timeout;
@@ -503,73 +530,25 @@ exports.clearInterval = function clearInterval(timer) {
   clearTimeout(timer);
 };
 
-function unrefdHandle(timer, now) {
-  try {
-    // Don't attempt to call the callback if it is not a function.
-    if (typeof timer._onTimeout === 'function') {
-      tryOnTimeout(timer, now);
-    }
-  } finally {
-    // Make sure we clean up if the callback is no longer a function
-    // even if the timer is an interval.
-    if (!timer._repeat || typeof timer._onTimeout !== 'function') {
-      timer.close();
-    }
-  }
-
-  return true;
-}
-
 
 Timeout.prototype.unref = function() {
-  if (this._handle) {
-    this._handle.unref();
-  } else if (typeof this._onTimeout === 'function') {
-    const now = TimerWrap.now();
-    if (!this._idleStart) this._idleStart = now;
-    var delay = this._idleStart + this._idleTimeout - now;
-    if (delay < 0) delay = 0;
-
-    // Prevent running cb again when unref() is called during the same cb
-    if (this._called && !this._repeat) {
-      unenroll(this);
-      return;
-    }
-
-    const handle = reuse(this);
-    if (handle !== null) {
-      handle._list = undefined;
-    }
-
-    this._handle = handle || new TimerWrap();
-    this._handle.owner = this;
-    this._handle.start(delay);
-    this._handle.unref();
+  if (this[kRefed]) {
+    this[kRefed] = false;
+    decRefCount();
   }
   return this;
 };
 
 Timeout.prototype.ref = function() {
-  if (this._handle)
-    this._handle.ref();
+  if (this[kRefed] === false) {
+    this[kRefed] = true;
+    incRefCount();
+  }
   return this;
 };
 
 Timeout.prototype.close = function() {
-  this._onTimeout = null;
-  if (this._handle) {
-    if (destroyHooksExist() &&
-        typeof this[async_id_symbol] === 'number' &&
-        !this._destroyed) {
-      emitDestroy(this[async_id_symbol]);
-      this._destroyed = true;
-    }
-
-    this._idleTimeout = -1;
-    this._handle.close();
-  } else {
-    unenroll(this);
-  }
+  clearTimeout(this);
   return this;
 };