From 23a56e0c28cd828ef0cabb05b30e03cc8cb57dd5 Mon Sep 17 00:00:00 2001 From: Anatoli Papirovski Date: Sat, 5 May 2018 19:50:21 +0200 Subject: 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 Reviewed-By: Jeremiah Senkpiel Reviewed-By: Matteo Collina Reviewed-By: James M Snell Reviewed-By: Ruben Bridgewater --- lib/timers.js | 375 +++++++++++++++++++++++++++------------------------------- 1 file changed, 177 insertions(+), 198 deletions(-) (limited to 'lib/timers.js') 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; }; -- cgit v1.2.3