// Copyright Joyent, Inc. and other Node contributors. // // Permission is hereby granted, free of charge, to any person obtaining a // copy of this software and associated documentation files (the // "Software"), to deal in the Software without restriction, including // without limitation the rights to use, copy, modify, merge, publish, // distribute, sublicense, and/or sell copies of the Software, and to permit // persons to whom the Software is furnished to do so, subject to the // following conditions: // // The above copyright notice and this permission notice shall be included // in all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN // NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, // DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR // OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE // USE OR OTHER DEALINGS IN THE SOFTWARE. 'use strict'; const async_wrap = process.binding('async_wrap'); const TimerWrap = process.binding('timer_wrap').Timer; const L = require('internal/linkedlist'); const internalUtil = require('internal/util'); const { createPromise, promiseResolve } = process.binding('util'); const assert = require('assert'); const util = require('util'); const errors = require('internal/errors'); const debug = util.debuglog('timer'); const kOnTimeout = TimerWrap.kOnTimeout | 0; // Two arrays that share state between C++ and JS. const { async_hook_fields, async_id_fields } = async_wrap; const { initTriggerId, // The needed emit*() functions. emitInit, emitBefore, emitAfter, emitDestroy } = require('async_hooks'); // Grab the constants necessary for working with internal arrays. const { kInit, kDestroy, kAsyncIdCounter } = async_wrap.constants; // Symbols for storing async id state. const async_id_symbol = Symbol('asyncId'); const trigger_async_id_symbol = Symbol('triggerAsyncId'); // Timeout values > TIMEOUT_MAX are set to 1. const TIMEOUT_MAX = 2147483647; // 2^31-1 // 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 // timer so that we can time out of connections. Additionally, many user // libraries and applications also use timers. As such there may be a // significantly large amount of timeouts scheduled at any given time. // Therefore, it is very important that the timers implementation is performant // and efficient. // // Note: It is suggested you first read though the lib/internal/linkedlist.js // linked list implementation, since timers depend on it extensively. It can be // somewhat counter-intuitive at first, as it is not actually a class. Instead, // it is a set of helpers that operate on an existing object. // // In order to be as performant as possible, the architecture and data // structures are designed so that they are optimized to handle the following // use cases as efficiently as possible: // - Adding a new timer. (insert) // - Removing an existing timer. (remove) // - Handling a timer timing out. (timeout) // // Whenever possible, the implementation tries to make the complexity of these // operations as close to constant-time as possible. // (So that performance is not impacted by the number of scheduled timers.) // // 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. // // // ╔════ > Object Map // ║ // ╠══ // ║ refedLists: { '40': { }, '320': { etc } } (keys of millisecond duration) // ╚══ ┌─────────┘ // │ // ╔══ │ // ║ TimersList { _idleNext: { }, _idlePrev: (self), _timer: (TimerWrap) } // ║ ┌────────────────┘ // ║ ╔══ │ ^ // ║ ║ { _idleNext: { }, _idlePrev: { }, _onTimeout: (callback) } // ║ ║ ┌───────────┘ // ║ ║ │ ^ // ║ ║ { _idleNext: { etc }, _idlePrev: { }, _onTimeout: (callback) } // ╠══ ╠══ // ║ ║ // ║ ╚════ > Actual JavaScript timeouts // ║ // ╚════ > Linked List // // // With this, virtually constant-time insertion (append), removal, and timeout // is possible in the JavaScript layer. Any one list of timers is able to be // sorted by just appending to it because all timers within share the same // duration. Therefore, any timer added later will always have been scheduled to // timeout later, thus only needing to be appended. // Removal from an object-property linked list is also virtually constant-time // as can be seen in the lib/internal/linkedlist.js implementation. // Timeouts only need to process any timers currently due to expire, which will // always be at the beginning of the list for reasons stated above. Any timers // after the first one encountered that does not yet need to timeout will also // 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. // Object maps 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); // Schedule or re-schedule a timer. // The item must have been enroll()'d first. const active = exports.active = function(item) { insert(item, false); }; // 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); }; // 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 // TimerWrap backed list if one does not already exist for the specified timeout // duration. function insert(item, unrefed) { const msecs = item._idleTimeout; if (msecs < 0 || msecs === undefined) return; item._idleStart = TimerWrap.now(); const lists = unrefed === true ? unrefedLists : refedLists; // Use an existing list if there is one, otherwise we need to make a new one. var list = lists[msecs]; if (!list) { debug('no %d list was found in insert, creating a new one', msecs); lists[msecs] = list = createTimersList(msecs, unrefed); } if (!item[async_id_symbol] || item._destroyed) { item._destroyed = false; item[async_id_symbol] = ++async_id_fields[kAsyncIdCounter]; item[trigger_async_id_symbol] = initTriggerId(); if (async_hook_fields[kInit] > 0) emitInit( item[async_id_symbol], 'Timeout', item[trigger_async_id_symbol], item ); } L.append(list, item); assert(!L.isEmpty(list)); // list is not empty } function createTimersList(msecs, unrefed) { // Make a new linked list of timers, and create a TimerWrap to schedule // processing for the list. const list = new TimersList(msecs, unrefed); L.init(list); list._timer._list = list; if (unrefed === true) list._timer.unref(); list._timer.start(msecs); list._timer[kOnTimeout] = listOnTimeout; return list; } function TimersList(msecs, unrefed) { this._idleNext = null; // Create the list with the linkedlist properties to this._idlePrev = null; // prevent any unnecessary hidden class changes. this._timer = new TimerWrap(); this._unrefed = unrefed; this.msecs = msecs; this.nextTick = false; } function listOnTimeout() { var list = this._list; var msecs = list.msecs; if (list.nextTick) { list.nextTick = false; process.nextTick(listOnTimeoutNT, list); return; } debug('timeout callback %d', msecs); var now = TimerWrap.now(); debug('now: %d', now); var diff, timer; 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) { var timeRemaining = msecs - (TimerWrap.now() - timer._idleStart); if (timeRemaining < 0) { timeRemaining = 1; } this.start(timeRemaining); debug('%d list wait because diff is %d', msecs, diff); return; } // The actual logic for when a timeout happens. L.remove(timer); assert(timer !== L.peek(list)); if (!timer._onTimeout) { if (async_hook_fields[kDestroy] > 0 && !timer._destroyed && typeof timer[async_id_symbol] === 'number') { emitDestroy(timer[async_id_symbol]); timer._destroyed = true; } continue; } var domain = timer.domain; if (domain) { domain.enter(); } tryOnTimeout(timer, list); if (domain) domain.exit(); } // 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. 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 (this.owner) return; this.close(); } // 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, list) { 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]); try { ontimeout(timer); threw = false; } finally { if (timerAsyncId !== null) { if (!threw) emitAfter(timerAsyncId); if (!timer._repeat && async_hook_fields[kDestroy] > 0 && !timer._destroyed) { emitDestroy(timerAsyncId); timer._destroyed = true; } } if (!threw) return; // Postpone all later list events to next tick. We need to do this // so that the events are called in the order they were created. const lists = list._unrefed === true ? unrefedLists : refedLists; for (var key in lists) { if (key > list.msecs) { lists[key].nextTick = true; } } // We need to continue processing after domain error handling // is complete, but not by using whatever domain was left over // when the timeout threw its exception. const domain = process.domain; process.domain = null; // If we threw, we need to process the rest of the list in nextTick. process.nextTick(listOnTimeoutNT, list); process.domain = domain; } } function listOnTimeoutNT(list) { list._timer[kOnTimeout](); } // 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); var list = refedLists[item._idleTimeout]; // if empty - reuse the watcher if (list && 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. const unenroll = exports.unenroll = function(item) { // Fewer checks may be possible, but these cover everything. if (async_hook_fields[kDestroy] > 0 && item && typeof item[async_id_symbol] === 'number' && !item._destroyed) { emitDestroy(item[async_id_symbol]); item._destroyed = true; } var handle = reuse(item); if (handle) { debug('unenroll: list empty'); handle.close(); } // if active is called later, then we want to make sure not to insert again item._idleTimeout = -1; }; // Make a regular object able to act as a timer by setting some properties. // This function does not start the timer, see `active()`. // Using existing objects as timers slightly reduces object overhead. exports.enroll = function(item, msecs) { if (typeof msecs !== 'number') { throw new errors.TypeError('ERR_INVALID_ARG_TYPE', 'msecs', 'number', msecs); } if (msecs < 0 || !isFinite(msecs)) { throw new errors.RangeError('ERR_VALUE_OUT_OF_RANGE', 'msecs', 'a non-negative finite number', msecs); } // if this item was already in a list somewhere // then we should unenroll it from that if (item._idleNext) unenroll(item); // Ensure that msecs fits into signed int32 if (msecs > TIMEOUT_MAX) { process.emitWarning(`${msecs} does not fit into a 32-bit signed integer.` + `\nTimer duration was truncated to ${TIMEOUT_MAX}.`, 'TimeoutOverflowWarning'); msecs = TIMEOUT_MAX; } item._idleTimeout = msecs; L.init(item); }; /* * DOM-style timers */ function setTimeout(callback, after, arg1, arg2, arg3) { if (typeof callback !== 'function') { throw new errors.TypeError('ERR_INVALID_CALLBACK'); } var len = arguments.length; var args; if (len === 3) { args = [arg1]; } else if (len === 4) { args = [arg1, arg2]; } else if (len > 4) { args = [arg1, arg2, arg3]; for (var i = 5; i < len; i++) // extend array dynamically, makes .apply run much faster in v6.0.0 args[i - 2] = arguments[i]; } return createSingleTimeout(callback, after, args); } setTimeout[internalUtil.promisify.custom] = function(after, value) { const promise = createPromise(); createSingleTimeout(promise, after, [value]); return promise; }; exports.setTimeout = setTimeout; function createSingleTimeout(callback, after, args) { after *= 1; // coalesce to number or NaN if (!(after >= 1 && after <= TIMEOUT_MAX)) { if (after > TIMEOUT_MAX) { process.emitWarning(`${after} does not fit into` + ' a 32-bit signed integer.' + '\nTimeout duration was set to 1.', 'TimeoutOverflowWarning'); } after = 1; // schedule on next tick, follows browser behavior } var timer = new Timeout(after, callback, args); if (process.domain) timer.domain = process.domain; active(timer); return timer; } function ontimeout(timer) { var args = timer._timerArgs; var callback = timer._onTimeout; if (typeof callback !== 'function') return promiseResolve(callback, args[0]); if (!args) timer._onTimeout(); else { switch (args.length) { case 1: timer._onTimeout(args[0]); break; case 2: timer._onTimeout(args[0], args[1]); break; case 3: timer._onTimeout(args[0], args[1], args[2]); break; default: Function.prototype.apply.call(callback, timer, args); } } if (timer._repeat) rearm(timer); } function rearm(timer) { // // 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; active(timer); } } const clearTimeout = exports.clearTimeout = function(timer) { if (timer && (timer[kOnTimeout] || timer._onTimeout)) { timer[kOnTimeout] = timer._onTimeout = null; if (timer instanceof Timeout) { timer.close(); // for after === 0 } else { unenroll(timer); } } }; exports.setInterval = function(callback, repeat, arg1, arg2, arg3) { if (typeof callback !== 'function') { throw new errors.TypeError('ERR_INVALID_CALLBACK'); } var len = arguments.length; var args; if (len === 3) { args = [arg1]; } else if (len === 4) { args = [arg1, arg2]; } else if (len > 4) { args = [arg1, arg2, arg3]; for (var i = 5; i < len; i++) // extend array dynamically, makes .apply run much faster in v6.0.0 args[i - 2] = arguments[i]; } return createRepeatTimeout(callback, repeat, args); }; function createRepeatTimeout(callback, repeat, args) { repeat *= 1; // coalesce to number or NaN if (!(repeat >= 1 && repeat <= TIMEOUT_MAX)) { if (repeat > TIMEOUT_MAX) { process.emitWarning(`${repeat} does not fit into` + ' a 32-bit signed integer.' + '\nInterval duration was set to 1.', 'TimeoutOverflowWarning'); } repeat = 1; // schedule on next tick, follows browser behavior } var timer = new Timeout(repeat, callback, args); timer._repeat = repeat; if (process.domain) timer.domain = process.domain; active(timer); return timer; } exports.clearInterval = function(timer) { if (timer && timer._repeat) { timer._repeat = null; clearTimeout(timer); } }; function Timeout(after, callback, args) { this._called = false; this._idleTimeout = after; this._idlePrev = this; this._idleNext = this; this._idleStart = null; this._onTimeout = callback; this._timerArgs = args; this._repeat = null; this._destroyed = false; this[async_id_symbol] = ++async_id_fields[kAsyncIdCounter]; this[trigger_async_id_symbol] = initTriggerId(); if (async_hook_fields[kInit] > 0) emitInit( this[async_id_symbol], 'Timeout', this[trigger_async_id_symbol], this ); } function unrefdHandle() { // Don't attempt to call the callback if it is not a function. if (typeof this.owner._onTimeout === 'function') { ontimeout(this.owner); } // Make sure we clean up if the callback is no longer a function // even if the timer is an interval. if (!this.owner._repeat || typeof this.owner._onTimeout !== 'function') { this.owner.close(); } } Timeout.prototype.unref = function() { if (this._handle) { this._handle.unref(); } else if (typeof this._onTimeout === 'function') { var 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; } var handle = reuse(this); if (handle) { handle._list = undefined; } this._handle = handle || new TimerWrap(); this._handle.owner = this; this._handle[kOnTimeout] = unrefdHandle; this._handle.start(delay); this._handle.domain = this.domain; this._handle.unref(); } return this; }; Timeout.prototype.ref = function() { if (this._handle) this._handle.ref(); return this; }; Timeout.prototype.close = function() { this._onTimeout = null; if (this._handle) { // Fewer checks may be possible, but these cover everything. if (async_hook_fields[kDestroy] > 0 && this && typeof this[async_id_symbol] === 'number' && !this._destroyed) { emitDestroy(this[async_id_symbol]); this._destroyed = true; } this._idleTimeout = -1; this._handle[kOnTimeout] = null; this._handle.close(); } else { unenroll(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) { 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) { item._idleNext._idlePrev = item._idlePrev; } if (item._idlePrev) { 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 var immediateQueue = new ImmediateList(); function processImmediate() { var immediate = immediateQueue.head; var tail = immediateQueue.tail; var domain; // Clear the linked list early in case new `setImmediate()` calls occur while // immediate callbacks are executed immediateQueue.head = immediateQueue.tail = null; while (immediate) { domain = immediate.domain; if (!immediate._onImmediate) { immediate = immediate._idleNext; continue; } if (domain) domain.enter(); // Save next in case `clearImmediate(immediate)` is called from callback var next = immediate._idleNext; tryOnImmediate(immediate, tail); if (domain) domain.exit(); // If `clearImmediate(immediate)` wasn't called from the callback, use the // `immediate`'s next item if (immediate._idleNext) immediate = immediate._idleNext; else immediate = next; } // Only round-trip to C++ land if we have to. Calling clearImmediate() on an // immediate that's in |queue| is okay. Worst case is we make a superfluous // call to NeedImmediateCallbackSetter(). if (!immediateQueue.head) { process._needImmediateCallback = false; } } // An optimization so that the try/finally only de-optimizes (since at least v8 // 4.7) what is in this smaller function. function tryOnImmediate(immediate, oldTail) { var threw = true; emitBefore(immediate[async_id_symbol], immediate[trigger_async_id_symbol]); try { // make the actual call outside the try/finally to allow it to be optimized runCallback(immediate); threw = false; } finally { // clearImmediate checks _onImmediate === null for kDestroy hooks. immediate._onImmediate = null; if (!threw) emitAfter(immediate[async_id_symbol]); if (async_hook_fields[kDestroy] > 0 && !immediate._destroyed) { emitDestroy(immediate[async_id_symbol]); immediate._destroyed = true; } if (threw && immediate._idleNext) { // Handle any remaining on next tick, assuming we're still alive to do so. const curHead = immediateQueue.head; const next = immediate._idleNext; if (curHead) { curHead._idlePrev = oldTail; oldTail._idleNext = curHead; next._idlePrev = null; immediateQueue.head = next; } else { immediateQueue.head = next; immediateQueue.tail = oldTail; } process.nextTick(processImmediate); } } } function runCallback(timer) { const argv = timer._argv; const argc = argv ? argv.length : 0; if (typeof timer._onImmediate !== 'function') return promiseResolve(timer._onImmediate, argv[0]); switch (argc) { // fast-path callbacks with 0-3 arguments case 0: return timer._onImmediate(); case 1: return timer._onImmediate(argv[0]); case 2: return timer._onImmediate(argv[0], argv[1]); case 3: return timer._onImmediate(argv[0], argv[1], argv[2]); // more than 3 arguments run slower with .apply default: return Function.prototype.apply.call(timer._onImmediate, timer, argv); } } function Immediate() { // assigning the callback here can cause optimize/deoptimize thrashing // so have caller annotate the object (node v6.0.0, v8 5.0.71.35) this._idleNext = null; this._idlePrev = null; this._onImmediate = null; this._argv = null; this._onImmediate = null; this._destroyed = false; this.domain = process.domain; this[async_id_symbol] = ++async_id_fields[kAsyncIdCounter]; this[trigger_async_id_symbol] = initTriggerId(); if (async_hook_fields[kInit] > 0) emitInit( this[async_id_symbol], 'Immediate', this[trigger_async_id_symbol], this ); } function setImmediate(callback, arg1, arg2, arg3) { if (typeof callback !== 'function') { throw new errors.TypeError('ERR_INVALID_CALLBACK'); } var i, args; switch (arguments.length) { // fast cases case 1: break; case 2: args = [arg1]; break; case 3: args = [arg1, arg2]; break; default: args = [arg1, arg2, arg3]; for (i = 4; i < arguments.length; i++) // extend array dynamically, makes .apply run much faster in v6.0.0 args[i - 1] = arguments[i]; break; } return createImmediate(args, callback); } setImmediate[internalUtil.promisify.custom] = function(value) { const promise = createPromise(); createImmediate([value], promise); return promise; }; exports.setImmediate = setImmediate; function createImmediate(args, callback) { // declaring it `const immediate` causes v6.0.0 to deoptimize this function var immediate = new Immediate(); immediate._argv = args; immediate._onImmediate = callback; if (!process._needImmediateCallback) { process._needImmediateCallback = true; process._immediateCallback = processImmediate; } immediateQueue.append(immediate); return immediate; } exports.clearImmediate = function(immediate) { if (!immediate) return; if (async_hook_fields[kDestroy] > 0 && immediate._onImmediate !== null && !immediate._destroyed) { emitDestroy(immediate[async_id_symbol]); immediate._destroyed = true; } immediate._onImmediate = null; immediateQueue.remove(immediate); if (!immediateQueue.head) { process._needImmediateCallback = false; } };