timers: refactor timer callback initialization

This patch:

- Moves the timer callback initialization into bootstrap/node.js,
  documents when they will be called, and make the dependency on
  process._tickCallback explicit.
- Moves the initialization of tick callbacks and timer callbacks
  to the end of the bootstrap to make sure the operations
  done before those initializations are synchronous.
- Moves more internals into internal/timers.js from timers.js.

PR-URL: https://github.com/nodejs/node/pull/26583
Refs: https://github.com/nodejs/node/issues/26546
Reviewed-By: Anna Henningsen <anna@addaleax.net>

1 files changed, 15 insertions, 386 deletions

diff --git a/lib/timers.js b/lib/timers.js
index 30bc646698..14d0b92fe5 100644
--- a/lib/timers.js
+++ b/lib/timers.js
@@ -22,28 +22,31 @@
 'use strict';
 
 const {
-  getLibuvNow,
-  setupTimers,
-  scheduleTimer,
-  toggleTimerRef,
   immediateInfo,
   toggleImmediateRef
 } = internalBinding('timers');
 const L = require('internal/linkedlist');
-const PriorityQueue = require('internal/priority_queue');
 const {
   async_id_symbol,
-  trigger_async_id_symbol,
   Timeout,
+  decRefCount,
+  immediateInfoFields: {
+    kCount,
+    kRefCount
+  },
   kRefed,
   initAsyncResource,
-  validateTimerDuration
+  validateTimerDuration,
+  timerListMap,
+  timerListQueue,
+  immediateQueue,
+  active,
+  unrefActive
 } = require('internal/timers');
 const {
   promisify: { custom: customPromisify },
   deprecate
 } = require('internal/util');
-const { inspect } = require('internal/util/inspect');
 const { ERR_INVALID_CALLBACK } = require('internal/errors').codes;
 
 let debuglog;
@@ -57,20 +60,9 @@ function debug(...args) {
 const {
   destroyHooksExist,
   // The needed emit*() functions.
-  emitBefore,
-  emitAfter,
   emitDestroy
 } = require('internal/async_hooks');
 
-// *Must* match Environment::ImmediateInfo::Fields in src/env.h.
-const kCount = 0;
-const kRefCount = 1;
-const kHasOutstanding = 2;
-
-// Call into C++ to assign callbacks that are responsible for processing
-// Immediates and TimerLists.
-setupTimers(processImmediate, processTimers);
-
 // 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
@@ -143,236 +135,6 @@ setupTimers(processImmediate, processTimers);
 // timers within (or creation of a new list). However, these operations combined
 // have shown to be trivial in comparison to other timers architectures.
 
-
-// Object map containing linked lists of timers, keyed and sorted by their
-// duration in milliseconds.
-//
-// - key = time in milliseconds
-// - value = linked list
-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 nextExpiry = Infinity;
-
-let timerListId = Number.MIN_SAFE_INTEGER;
-let refCount = 0;
-
-function incRefCount() {
-  if (refCount++ === 0)
-    toggleTimerRef(true);
-}
-
-function decRefCount() {
-  if (--refCount === 0)
-    toggleTimerRef(false);
-}
-
-// Schedule or re-schedule a timer.
-// The item must have been enroll()'d first.
-function active(item) {
-  insert(item, true, getLibuvNow());
-}
-
-// Internal APIs that need timeouts should use `_unrefActive()` instead of
-// `active()` so that they do not unnecessarily keep the process open.
-function _unrefActive(item) {
-  insert(item, false, getLibuvNow());
-}
-
-// The underlying logic for scheduling or re-scheduling a timer.
-//
-// Appends a timer onto the end of an existing timers list, or creates a new
-// list if one does not already exist for the specified timeout duration.
-function insert(item, refed, start) {
-  let msecs = item._idleTimeout;
-  if (msecs < 0 || msecs === undefined)
-    return;
-
-  // Truncate so that accuracy of sub-milisecond timers is not assumed.
-  msecs = Math.trunc(msecs);
-
-  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);
-    const expiry = start + msecs;
-    lists[msecs] = list = new TimersList(expiry, msecs);
-    queue.insert(list);
-
-    if (nextExpiry > expiry) {
-      scheduleTimer(msecs);
-      nextExpiry = expiry;
-    }
-  }
-
-  if (!item[async_id_symbol] || item._destroyed) {
-    item._destroyed = false;
-    initAsyncResource(item, 'Timeout');
-  }
-
-  if (refed === !item[kRefed]) {
-    if (refed)
-      incRefCount();
-    else
-      decRefCount();
-  }
-  item[kRefed] = refed;
-
-  L.append(list, item);
-}
-
-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.expiry = expiry;
-  this.id = timerListId++;
-  this.msecs = msecs;
-  this.priorityQueuePosition = null;
-}
-
-// Make sure the linked list only shows the minimal necessary information.
-TimersList.prototype[inspect.custom] = function(_, options) {
-  return inspect(this, {
-    ...options,
-    // Only inspect one level.
-    depth: 0,
-    // It should not recurse.
-    customInspect: false
-  });
-};
-
-const { _tickCallback: runNextTicks } = process;
-function processTimers(now) {
-  debug('process timer lists %d', now);
-  nextExpiry = Infinity;
-
-  let list;
-  let ranAtLeastOneList = false;
-  while (list = queue.peek()) {
-    if (list.expiry > now) {
-      nextExpiry = list.expiry;
-      return refCount > 0 ? nextExpiry : -nextExpiry;
-    }
-    if (ranAtLeastOneList)
-      runNextTicks();
-    else
-      ranAtLeastOneList = true;
-    listOnTimeout(list, now);
-  }
-  return 0;
-}
-
-function listOnTimeout(list, now) {
-  const msecs = list.msecs;
-
-  debug('timeout callback %d', msecs);
-
-  var diff, timer;
-  let ranAtLeastOneTimer = false;
-  while (timer = L.peek(list)) {
-    diff = now - timer._idleStart;
-
-    // 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) {
-      list.expiry = Math.max(timer._idleStart + msecs, now + 1);
-      list.id = timerListId++;
-      queue.percolateDown(1);
-      debug('%d list wait because diff is %d', msecs, diff);
-      return;
-    }
-
-    if (ranAtLeastOneTimer)
-      runNextTicks();
-    else
-      ranAtLeastOneTimer = true;
-
-    // The actual logic for when a timeout happens.
-    L.remove(timer);
-
-    const asyncId = timer[async_id_symbol];
-
-    if (!timer._onTimeout) {
-      if (timer[kRefed])
-        refCount--;
-      timer[kRefed] = null;
-
-      if (destroyHooksExist() && !timer._destroyed) {
-        emitDestroy(asyncId);
-        timer._destroyed = true;
-      }
-      continue;
-    }
-
-    emitBefore(asyncId, timer[trigger_async_id_symbol]);
-
-    let start;
-    if (timer._repeat)
-      start = getLibuvNow();
-
-    try {
-      const args = timer._timerArgs;
-      if (args === undefined)
-        timer._onTimeout();
-      else
-        Reflect.apply(timer._onTimeout, timer, args);
-    } finally {
-      if (timer._repeat && timer._idleTimeout !== -1) {
-        timer._idleTimeout = timer._repeat;
-        if (start === undefined)
-          start = getLibuvNow();
-        insert(timer, timer[kRefed], start);
-      } else {
-        if (timer[kRefed])
-          refCount--;
-        timer[kRefed] = null;
-
-        if (destroyHooksExist() && !timer._destroyed) {
-          emitDestroy(timer[async_id_symbol]);
-          timer._destroyed = true;
-        }
-      }
-    }
-
-    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 from the object map and the PriorityQueue.
-  debug('%d list empty', msecs);
-
-  // 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();
-  }
-}
-
-
 // Remove a timer. Cancels the timeout and resets the relevant timer properties.
 function unenroll(item) {
   // Fewer checks may be possible, but these cover everything.
@@ -393,11 +155,11 @@ function unenroll(item) {
   if (item[kRefed]) {
     // Compliment truncation during insert().
     const msecs = Math.trunc(item._idleTimeout);
-    const list = lists[msecs];
+    const list = timerListMap[msecs];
     if (list !== undefined && L.isEmpty(list)) {
       debug('unenroll: list empty');
-      queue.removeAt(list.priorityQueuePosition);
-      delete lists[list.msecs];
+      timerListQueue.removeAt(list.priorityQueuePosition);
+      delete timerListMap[list.msecs];
     }
 
     decRefCount();
@@ -513,144 +275,11 @@ function clearInterval(timer) {
   clearTimeout(timer);
 }
 
-
-Timeout.prototype.unref = function() {
-  if (this[kRefed]) {
-    this[kRefed] = false;
-    decRefCount();
-  }
-  return this;
-};
-
-Timeout.prototype.ref = function() {
-  if (this[kRefed] === false) {
-    this[kRefed] = true;
-    incRefCount();
-  }
-  return this;
-};
-
-Timeout.prototype.hasRef = function() {
-  return !!this[kRefed];
-};
-
 Timeout.prototype.close = function() {
   clearTimeout(this);
   return this;
 };
 
-
-// A linked list for storing `setImmediate()` requests
-function ImmediateList() {
-  this.head = null;
-  this.tail = null;
-}
-
-// Appends an item to the end of the linked list, adjusting the current tail's
-// previous and next pointers where applicable
-ImmediateList.prototype.append = function(item) {
-  if (this.tail !== null) {
-    this.tail._idleNext = item;
-    item._idlePrev = this.tail;
-  } else {
-    this.head = item;
-  }
-  this.tail = item;
-};
-
-// Removes an item from the linked list, adjusting the pointers of adjacent
-// items and the linked list's head or tail pointers as necessary
-ImmediateList.prototype.remove = function(item) {
-  if (item._idleNext !== null) {
-    item._idleNext._idlePrev = item._idlePrev;
-  }
-
-  if (item._idlePrev !== null) {
-    item._idlePrev._idleNext = item._idleNext;
-  }
-
-  if (item === this.head)
-    this.head = item._idleNext;
-  if (item === this.tail)
-    this.tail = item._idlePrev;
-
-  item._idleNext = null;
-  item._idlePrev = null;
-};
-
-// Create a single linked list instance only once at startup
-const immediateQueue = new ImmediateList();
-
-// If an uncaught exception was thrown during execution of immediateQueue,
-// this queue will store all remaining Immediates that need to run upon
-// resolution of all error handling (if process is still alive).
-const outstandingQueue = new ImmediateList();
-
-
-function processImmediate() {
-  const queue = outstandingQueue.head !== null ?
-    outstandingQueue : immediateQueue;
-  var immediate = queue.head;
-
-  // Clear the linked list early in case new `setImmediate()` calls occur while
-  // immediate callbacks are executed
-  if (queue !== outstandingQueue) {
-    queue.head = queue.tail = null;
-    immediateInfo[kHasOutstanding] = 1;
-  }
-
-  let prevImmediate;
-  let ranAtLeastOneImmediate = false;
-  while (immediate !== null) {
-    if (ranAtLeastOneImmediate)
-      runNextTicks();
-    else
-      ranAtLeastOneImmediate = true;
-
-    // It's possible for this current Immediate to be cleared while executing
-    // the next tick queue above, which means we need to use the previous
-    // Immediate's _idleNext which is guaranteed to not have been cleared.
-    if (immediate._destroyed) {
-      outstandingQueue.head = immediate = prevImmediate._idleNext;
-      continue;
-    }
-
-    immediate._destroyed = true;
-
-    immediateInfo[kCount]--;
-    if (immediate[kRefed])
-      immediateInfo[kRefCount]--;
-    immediate[kRefed] = null;
-
-    prevImmediate = immediate;
-
-    const asyncId = immediate[async_id_symbol];
-    emitBefore(asyncId, immediate[trigger_async_id_symbol]);
-
-    try {
-      const argv = immediate._argv;
-      if (!argv)
-        immediate._onImmediate();
-      else
-        Reflect.apply(immediate._onImmediate, immediate, argv);
-    } finally {
-      immediate._onImmediate = null;
-
-      if (destroyHooksExist())
-        emitDestroy(asyncId);
-
-      outstandingQueue.head = immediate = immediate._idleNext;
-    }
-
-    emitAfter(asyncId);
-  }
-
-  if (queue === outstandingQueue)
-    outstandingQueue.head = null;
-  immediateInfo[kHasOutstanding] = 0;
-}
-
-
 const Immediate = class Immediate {
   constructor(callback, args) {
     this._idleNext = null;
@@ -747,7 +376,7 @@ function clearImmediate(immediate) {
 }
 
 module.exports = {
-  _unrefActive,
+  _unrefActive: unrefActive,
   active,
   setTimeout,
   clearTimeout,