From 5214acd3d9dec56ee159544f0f6bf9834a62c097 Mon Sep 17 00:00:00 2001 From: Ben Noordhuis Date: Wed, 14 Apr 2021 21:10:48 +0200 Subject: refactor: move timers to deno_timers op crate (#10179) Move timers out of runtime/ and into a standalone op crate. --- Cargo.lock | 9 + Cargo.toml | 1 + op_crates/timers/01_timers.js | 579 ++++++++++++++++++++++++++++++++++++++++++ op_crates/timers/Cargo.toml | 18 ++ op_crates/timers/README.md | 5 + op_crates/timers/lib.rs | 165 ++++++++++++ runtime/Cargo.toml | 14 +- runtime/build.rs | 2 + runtime/js/11_timers.js | 561 ---------------------------------------- runtime/ops/timers.rs | 171 ++----------- runtime/permissions.rs | 11 + 11 files changed, 817 insertions(+), 719 deletions(-) create mode 100644 op_crates/timers/01_timers.js create mode 100644 op_crates/timers/Cargo.toml create mode 100644 op_crates/timers/README.md create mode 100644 op_crates/timers/lib.rs delete mode 100644 runtime/js/11_timers.js diff --git a/Cargo.lock b/Cargo.lock index 665a46b0e..f53edf434 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -674,6 +674,7 @@ dependencies = [ "deno_crypto", "deno_fetch", "deno_file", + "deno_timers", "deno_url", "deno_web", "deno_webgpu", @@ -710,6 +711,14 @@ dependencies = [ "winres", ] +[[package]] +name = "deno_timers" +version = "0.1.0" +dependencies = [ + "deno_core", + "tokio", +] + [[package]] name = "deno_url" version = "0.3.0" diff --git a/Cargo.toml b/Cargo.toml index d99f66fd3..b5ffb58f5 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -10,6 +10,7 @@ members = [ "test_util", "op_crates/crypto", "op_crates/fetch", + "op_crates/timers", "op_crates/url", "op_crates/web", "op_crates/webgpu", diff --git a/op_crates/timers/01_timers.js b/op_crates/timers/01_timers.js new file mode 100644 index 000000000..d6d6436fe --- /dev/null +++ b/op_crates/timers/01_timers.js @@ -0,0 +1,579 @@ +// Copyright 2018-2021 the Deno authors. All rights reserved. MIT license. +"use strict"; + +((window) => { + const core = window.Deno.core; + + // Shamelessly cribbed from op_crates/fetch/11_streams.js + class AssertionError extends Error { + constructor(msg) { + super(msg); + this.name = "AssertionError"; + } + } + + /** + * @param {unknown} cond + * @param {string=} msg + * @returns {asserts cond} + */ + function assert(cond, msg = "Assertion failed.") { + if (!cond) { + throw new AssertionError(msg); + } + } + + function opStopGlobalTimer() { + core.opSync("op_global_timer_stop"); + } + + function opStartGlobalTimer(timeout) { + return core.opSync("op_global_timer_start", timeout); + } + + async function opWaitGlobalTimer() { + await core.opAsync("op_global_timer"); + } + + function opNow() { + return core.opSync("op_now"); + } + + function sleepSync(millis = 0) { + return core.opSync("op_sleep_sync", millis); + } + + // Derived from https://github.com/vadimg/js_bintrees. MIT Licensed. + + class RBNode { + constructor(data) { + this.data = data; + this.left = null; + this.right = null; + this.red = true; + } + + getChild(dir) { + return dir ? this.right : this.left; + } + + setChild(dir, val) { + if (dir) { + this.right = val; + } else { + this.left = val; + } + } + } + + class RBTree { + #comparator = null; + #root = null; + + constructor(comparator) { + this.#comparator = comparator; + this.#root = null; + } + + /** Returns `null` if tree is empty. */ + min() { + let res = this.#root; + if (res === null) { + return null; + } + while (res.left !== null) { + res = res.left; + } + return res.data; + } + + /** Returns node `data` if found, `null` otherwise. */ + find(data) { + let res = this.#root; + while (res !== null) { + const c = this.#comparator(data, res.data); + if (c === 0) { + return res.data; + } else { + res = res.getChild(c > 0); + } + } + return null; + } + + /** returns `true` if inserted, `false` if duplicate. */ + insert(data) { + let ret = false; + + if (this.#root === null) { + // empty tree + this.#root = new RBNode(data); + ret = true; + } else { + const head = new RBNode(null); // fake tree root + + let dir = 0; + let last = 0; + + // setup + let gp = null; // grandparent + let ggp = head; // grand-grand-parent + let p = null; // parent + let node = this.#root; + ggp.right = this.#root; + + // search down + while (true) { + if (node === null) { + // insert new node at the bottom + node = new RBNode(data); + p.setChild(dir, node); + ret = true; + } else if (isRed(node.left) && isRed(node.right)) { + // color flip + node.red = true; + node.left.red = false; + node.right.red = false; + } + + // fix red violation + if (isRed(node) && isRed(p)) { + const dir2 = ggp.right === gp; + + assert(gp); + if (node === p.getChild(last)) { + ggp.setChild(dir2, singleRotate(gp, !last)); + } else { + ggp.setChild(dir2, doubleRotate(gp, !last)); + } + } + + const cmp = this.#comparator(node.data, data); + + // stop if found + if (cmp === 0) { + break; + } + + last = dir; + dir = Number(cmp < 0); // Fix type + + // update helpers + if (gp !== null) { + ggp = gp; + } + gp = p; + p = node; + node = node.getChild(dir); + } + + // update root + this.#root = head.right; + } + + // make root black + this.#root.red = false; + + return ret; + } + + /** Returns `true` if removed, `false` if not found. */ + remove(data) { + if (this.#root === null) { + return false; + } + + const head = new RBNode(null); // fake tree root + let node = head; + node.right = this.#root; + let p = null; // parent + let gp = null; // grand parent + let found = null; // found item + let dir = 1; + + while (node.getChild(dir) !== null) { + const last = dir; + + // update helpers + gp = p; + p = node; + node = node.getChild(dir); + + const cmp = this.#comparator(data, node.data); + + dir = cmp > 0; + + // save found node + if (cmp === 0) { + found = node; + } + + // push the red node down + if (!isRed(node) && !isRed(node.getChild(dir))) { + if (isRed(node.getChild(!dir))) { + const sr = singleRotate(node, dir); + p.setChild(last, sr); + p = sr; + } else if (!isRed(node.getChild(!dir))) { + const sibling = p.getChild(!last); + if (sibling !== null) { + if ( + !isRed(sibling.getChild(!last)) && + !isRed(sibling.getChild(last)) + ) { + // color flip + p.red = false; + sibling.red = true; + node.red = true; + } else { + assert(gp); + const dir2 = gp.right === p; + + if (isRed(sibling.getChild(last))) { + gp.setChild(dir2, doubleRotate(p, last)); + } else if (isRed(sibling.getChild(!last))) { + gp.setChild(dir2, singleRotate(p, last)); + } + + // ensure correct coloring + const gpc = gp.getChild(dir2); + assert(gpc); + gpc.red = true; + node.red = true; + assert(gpc.left); + gpc.left.red = false; + assert(gpc.right); + gpc.right.red = false; + } + } + } + } + } + + // replace and remove if found + if (found !== null) { + found.data = node.data; + assert(p); + p.setChild(p.right === node, node.getChild(node.left === null)); + } + + // update root and make it black + this.#root = head.right; + if (this.#root !== null) { + this.#root.red = false; + } + + return found !== null; + } + } + + function isRed(node) { + return node !== null && node.red; + } + + function singleRotate(root, dir) { + const save = root.getChild(!dir); + assert(save); + + root.setChild(!dir, save.getChild(dir)); + save.setChild(dir, root); + + root.red = true; + save.red = false; + + return save; + } + + function doubleRotate(root, dir) { + root.setChild(!dir, singleRotate(root.getChild(!dir), !dir)); + return singleRotate(root, dir); + } + + const { console } = globalThis; + const OriginalDateNow = Date.now; + + // Timeout values > TIMEOUT_MAX are set to 1. + const TIMEOUT_MAX = 2 ** 31 - 1; + + let globalTimeoutDue = null; + + let nextTimerId = 1; + const idMap = new Map(); + const dueTree = new RBTree((a, b) => a.due - b.due); + + function clearGlobalTimeout() { + globalTimeoutDue = null; + opStopGlobalTimer(); + } + + let pendingEvents = 0; + const pendingFireTimers = []; + + /** Process and run a single ready timer macrotask. + * This function should be registered through Deno.core.setMacrotaskCallback. + * Returns true when all ready macrotasks have been processed, false if more + * ready ones are available. The Isolate future would rely on the return value + * to repeatedly invoke this function until depletion. Multiple invocations + * of this function one at a time ensures newly ready microtasks are processed + * before next macrotask timer callback is invoked. */ + function handleTimerMacrotask() { + if (pendingFireTimers.length > 0) { + fire(pendingFireTimers.shift()); + return pendingFireTimers.length === 0; + } + return true; + } + + async function setGlobalTimeout(due, now) { + // Since JS and Rust don't use the same clock, pass the time to rust as a + // relative time value. On the Rust side we'll turn that into an absolute + // value again. + const timeout = due - now; + assert(timeout >= 0); + // Send message to the backend. + globalTimeoutDue = due; + pendingEvents++; + // FIXME(bartlomieju): this is problematic, because `clearGlobalTimeout` + // is synchronous. That means that timer is cancelled, but this promise is still pending + // until next turn of event loop. This leads to "leaking of async ops" in tests; + // because `clearTimeout/clearInterval` might be the last statement in test function + // `opSanitizer` will immediately complain that there is pending op going on, unless + // some timeout/defer is put in place to allow promise resolution. + // Ideally `clearGlobalTimeout` doesn't return until this op is resolved, but + // I'm not if that's possible. + opStartGlobalTimer(timeout); + await opWaitGlobalTimer(); + pendingEvents--; + // eslint-disable-next-line @typescript-eslint/no-use-before-define + prepareReadyTimers(); + } + + function prepareReadyTimers() { + const now = OriginalDateNow(); + // Bail out if we're not expecting the global timer to fire. + if (globalTimeoutDue === null || pendingEvents > 0) { + return; + } + // After firing the timers that are due now, this will hold the first timer + // list that hasn't fired yet. + let nextDueNode; + while ((nextDueNode = dueTree.min()) !== null && nextDueNode.due <= now) { + dueTree.remove(nextDueNode); + // Fire all the timers in the list. + for (const timer of nextDueNode.timers) { + // With the list dropped, the timer is no longer scheduled. + timer.scheduled = false; + // Place the callback to pending timers to fire. + pendingFireTimers.push(timer); + } + } + setOrClearGlobalTimeout(nextDueNode && nextDueNode.due, now); + } + + function setOrClearGlobalTimeout(due, now) { + if (due == null) { + clearGlobalTimeout(); + } else { + setGlobalTimeout(due, now); + } + } + + function schedule(timer, now) { + assert(!timer.scheduled); + assert(now <= timer.due); + // Find or create the list of timers that will fire at point-in-time `due`. + const maybeNewDueNode = { due: timer.due, timers: [] }; + let dueNode = dueTree.find(maybeNewDueNode); + if (dueNode === null) { + dueTree.insert(maybeNewDueNode); + dueNode = maybeNewDueNode; + } + // Append the newly scheduled timer to the list and mark it as scheduled. + dueNode.timers.push(timer); + timer.scheduled = true; + // If the new timer is scheduled to fire before any timer that existed before, + // update the global timeout to reflect this. + if (globalTimeoutDue === null || globalTimeoutDue > timer.due) { + setOrClearGlobalTimeout(timer.due, now); + } + } + + function unschedule(timer) { + // Check if our timer is pending scheduling or pending firing. + // If either is true, they are not in tree, and their idMap entry + // will be deleted soon. Remove it from queue. + let index = -1; + if ((index = pendingFireTimers.indexOf(timer)) >= 0) { + pendingFireTimers.splice(index); + return; + } + // If timer is not in the 2 pending queues and is unscheduled, + // it is not in the tree. + if (!timer.scheduled) { + return; + } + const searchKey = { due: timer.due, timers: [] }; + // Find the list of timers that will fire at point-in-time `due`. + const list = dueTree.find(searchKey).timers; + if (list.length === 1) { + // Time timer is the only one in the list. Remove the entire list. + assert(list[0] === timer); + dueTree.remove(searchKey); + // If the unscheduled timer was 'next up', find when the next timer that + // still exists is due, and update the global alarm accordingly. + if (timer.due === globalTimeoutDue) { + const nextDueNode = dueTree.min(); + setOrClearGlobalTimeout( + nextDueNode && nextDueNode.due, + OriginalDateNow(), + ); + } + } else { + // Multiple timers that are due at the same point in time. + // Remove this timer from the list. + const index = list.indexOf(timer); + assert(index > -1); + list.splice(index, 1); + } + } + + function fire(timer) { + // If the timer isn't found in the ID map, that means it has been cancelled + // between the timer firing and the promise callback (this function). + if (!idMap.has(timer.id)) { + return; + } + // Reschedule the timer if it is a repeating one, otherwise drop it. + if (!timer.repeat) { + // One-shot timer: remove the timer from this id-to-timer map. + idMap.delete(timer.id); + } else { + // Interval timer: compute when timer was supposed to fire next. + // However make sure to never schedule the next interval in the past. + const now = OriginalDateNow(); + timer.due = Math.max(now, timer.due + timer.delay); + schedule(timer, now); + } + // Call the user callback. Intermediate assignment is to avoid leaking `this` + // to it, while also keeping the stack trace neat when it shows up in there. + const callback = timer.callback; + if ("function" === typeof callback) { + callback(); + } else { + (0, eval)(callback); + } + } + + function checkThis(thisArg) { + if (thisArg !== null && thisArg !== undefined && thisArg !== globalThis) { + throw new TypeError("Illegal invocation"); + } + } + + function setTimer( + cb, + delay, + args, + repeat, + ) { + // If the callack is a function, bind `args` to the callback and bind `this` to globalThis(global). + // otherwise call `String` on it, and `eval` it on calls; do not pass variardic args to the string + let callback; + + if ("function" === typeof cb) { + callback = Function.prototype.bind.call(cb, globalThis, ...args); + } else { + callback = String(cb); + args = []; // args are ignored + } + // In the browser, the delay value must be coercible to an integer between 0 + // and INT32_MAX. Any other value will cause the timer to fire immediately. + // We emulate this behavior. + const now = OriginalDateNow(); + if (delay > TIMEOUT_MAX) { + console.warn( + `${delay} does not fit into` + + " a 32-bit signed integer." + + "\nTimeout duration was set to 1.", + ); + delay = 1; + } + delay = Math.max(0, delay | 0); + + // Create a new, unscheduled timer object. + const timer = { + id: nextTimerId++, + callback, + args, + delay, + due: now + delay, + repeat, + scheduled: false, + }; + // Register the timer's existence in the id-to-timer map. + idMap.set(timer.id, timer); + // Schedule the timer in the due table. + schedule(timer, now); + return timer.id; + } + + function setTimeout( + cb, + delay = 0, + ...args + ) { + delay >>>= 0; + checkThis(this); + return setTimer(cb, delay, args, false); + } + + function setInterval( + cb, + delay = 0, + ...args + ) { + delay >>>= 0; + checkThis(this); + return setTimer(cb, delay, args, true); + } + + function clearTimer(id) { + id >>>= 0; + const timer = idMap.get(id); + if (timer === undefined) { + // Timer doesn't exist any more or never existed. This is not an error. + return; + } + // Unschedule the timer if it is currently scheduled, and forget about it. + unschedule(timer); + idMap.delete(timer.id); + } + + function clearTimeout(id = 0) { + id >>>= 0; + if (id === 0) { + return; + } + clearTimer(id); + } + + function clearInterval(id = 0) { + id >>>= 0; + if (id === 0) { + return; + } + clearTimer(id); + } + + window.__bootstrap.timers = { + clearInterval, + setInterval, + clearTimeout, + setTimeout, + handleTimerMacrotask, + opStopGlobalTimer, + opStartGlobalTimer, + opNow, + sleepSync, + }; +})(this); diff --git a/op_crates/timers/Cargo.toml b/op_crates/timers/Cargo.toml new file mode 100644 index 000000000..31d5645f2 --- /dev/null +++ b/op_crates/timers/Cargo.toml @@ -0,0 +1,18 @@ +# Copyright 2018-2021 the Deno authors. All rights reserved. MIT license. + +[package] +name = "deno_timers" +version = "0.1.0" +edition = "2018" +description = "Timers API implementation for Deno" +authors = ["the Deno authors"] +license = "MIT" +readme = "README.md" +repository = "https://github.com/denoland/deno" + +[lib] +path = "lib.rs" + +[dependencies] +deno_core = { version = "0.84.0", path = "../../core" } +tokio = { version = "1.4.0", features = ["full"] } diff --git a/op_crates/timers/README.md b/op_crates/timers/README.md new file mode 100644 index 000000000..5a2a8e516 --- /dev/null +++ b/op_crates/timers/README.md @@ -0,0 +1,5 @@ +# deno_timers + +This crate implements the timers API. + +Spec: https://html.spec.whatwg.org/multipage/timers-and-user-prompts.html#timers diff --git a/op_crates/timers/lib.rs b/op_crates/timers/lib.rs new file mode 100644 index 000000000..047b6923c --- /dev/null +++ b/op_crates/timers/lib.rs @@ -0,0 +1,165 @@ +// Copyright 2018-2021 the Deno authors. All rights reserved. MIT license. + +//! This module helps deno implement timers. +//! +//! As an optimization, we want to avoid an expensive calls into rust for every +//! setTimeout in JavaScript. Thus in //js/timers.ts a data structure is +//! implemented that calls into Rust for only the smallest timeout. Thus we +//! only need to be able to start, cancel and await a single timer (or Delay, as Tokio +//! calls it) for an entire Isolate. This is what is implemented here. + +use deno_core::error::AnyError; +use deno_core::futures; +use deno_core::futures::channel::oneshot; +use deno_core::futures::FutureExt; +use deno_core::futures::TryFutureExt; +use deno_core::OpState; +use deno_core::ZeroCopyBuf; +use std::cell::RefCell; +use std::future::Future; +use std::pin::Pin; +use std::rc::Rc; +use std::thread::sleep; +use std::time::Duration; +use std::time::Instant; + +pub trait TimersPermission { + fn allow_hrtime(&mut self) -> bool; + fn check_unstable(&self, state: &OpState, api_name: &'static str); +} + +pub fn init(rt: &mut deno_core::JsRuntime) { + rt.execute( + "deno:op_crates/timers/01_timers.js", + include_str!("01_timers.js"), + ) + .unwrap(); +} + +pub type StartTime = Instant; + +type TimerFuture = Pin>>>; + +#[derive(Default)] +pub struct GlobalTimer { + tx: Option>, + pub future: Option, +} + +impl GlobalTimer { + pub fn cancel(&mut self) { + if let Some(tx) = self.tx.take() { + tx.send(()).ok(); + } + } + + pub fn new_timeout(&mut self, deadline: Instant) { + if self.tx.is_some() { + self.cancel(); + } + assert!(self.tx.is_none()); + self.future.take(); + + let (tx, rx) = oneshot::channel(); + self.tx = Some(tx); + + let delay = tokio::time::sleep_until(deadline.into()).boxed_local(); + let rx = rx + .map_err(|err| panic!("Unexpected error in receiving channel {:?}", err)); + + let fut = futures::future::select(delay, rx) + .then(|_| futures::future::ok(())) + .boxed_local(); + self.future = Some(fut); + } +} + +#[allow(clippy::unnecessary_wraps)] +pub fn op_global_timer_stop( + state: &mut OpState, + _args: (), + _zero_copy: Option, +) -> Result<(), AnyError> { + let global_timer = state.borrow_mut::(); + global_timer.cancel(); + Ok(()) +} + +// Set up a timer that will be later awaited by JS promise. +// It's a separate op, because canceling a timeout immediately +// after setting it caused a race condition (because Tokio timeout) +// might have been registered after next event loop tick. +// +// See https://github.com/denoland/deno/issues/7599 for more +// details. +#[allow(clippy::unnecessary_wraps)] +pub fn op_global_timer_start( + state: &mut OpState, + timeout: u64, + _zero_copy: Option, +) -> Result<(), AnyError> { + let deadline = Instant::now() + Duration::from_millis(timeout); + let global_timer = state.borrow_mut::(); + global_timer.new_timeout(deadline); + Ok(()) +} + +pub async fn op_global_timer( + state: Rc>, + _args: (), + _zero_copy: Option, +) -> Result<(), AnyError> { + let maybe_timer_fut = { + let mut s = state.borrow_mut(); + let global_timer = s.borrow_mut::(); + global_timer.future.take() + }; + if let Some(timer_fut) = maybe_timer_fut { + let _ = timer_fut.await; + } + Ok(()) +} + +// Returns a milliseconds and nanoseconds subsec +// since the start time of the deno runtime. +// If the High precision flag is not set, the +// nanoseconds are rounded on 2ms. +#[allow(clippy::unnecessary_wraps)] +pub fn op_now( + state: &mut OpState, + _argument: (), + _zero_copy: Option, +) -> Result +where + TP: TimersPermission + 'static, +{ + let start_time = state.borrow::(); + let seconds = start_time.elapsed().as_secs(); + let mut subsec_nanos = start_time.elapsed().subsec_nanos() as f64; + let reduced_time_precision = 2_000_000.0; // 2ms in nanoseconds + + // If the permission is not enabled + // Round the nano result on 2 milliseconds + // see: https://developer.mozilla.org/en-US/docs/Web/API/DOMHighResTimeStamp#Reduced_time_precision + if !state.borrow_mut::().allow_hrtime() { + subsec_nanos -= subsec_nanos % reduced_time_precision; + } + + let result = (seconds * 1_000) as f64 + (subsec_nanos / 1_000_000.0); + + Ok(result) +} + +#[allow(clippy::unnecessary_wraps)] +pub fn op_sleep_sync( + state: &mut OpState, + millis: u64, + _zero_copy: Option, +) -> Result<(), AnyError> +where + TP: TimersPermission + 'static, +{ + state.borrow::().check_unstable(state, "Deno.sleepSync"); + sleep(Duration::from_millis(millis)); + Ok(()) +} diff --git a/runtime/Cargo.toml b/runtime/Cargo.toml index f44ed64bb..b69d67838 100644 --- a/runtime/Cargo.toml +++ b/runtime/Cargo.toml @@ -18,32 +18,34 @@ name = "hello_runtime" path = "examples/hello_runtime.rs" [build-dependencies] -deno_core = { path = "../core", version = "0.84.0" } deno_console = { path = "../op_crates/console", version = "0.3.0" } +deno_core = { path = "../core", version = "0.84.0" } deno_crypto = { path = "../op_crates/crypto", version = "0.17.0" } deno_fetch = { path = "../op_crates/fetch", version = "0.25.0" } deno_file = { path = "../op_crates/file", version = "0.2.0" } -deno_web = { path = "../op_crates/web", version = "0.33.0" } +deno_timers = { path = "../op_crates/timers", version = "0.1.0" } deno_url = { path = "../op_crates/url", version = "0.3.0" } +deno_web = { path = "../op_crates/web", version = "0.33.0" } +deno_webgpu = { path = "../op_crates/webgpu", version = "0.4.0" } deno_webidl = { path = "../op_crates/webidl", version = "0.3.0" } deno_websocket = { path = "../op_crates/websocket", version = "0.8.0" } -deno_webgpu = { path = "../op_crates/webgpu", version = "0.4.0" } [target.'cfg(windows)'.build-dependencies] winres = "0.1.11" winapi = "0.3.9" [dependencies] -deno_core = { path = "../core", version = "0.84.0" } deno_console = { path = "../op_crates/console", version = "0.3.0" } +deno_core = { path = "../core", version = "0.84.0" } deno_crypto = { path = "../op_crates/crypto", version = "0.17.0" } deno_fetch = { path = "../op_crates/fetch", version = "0.25.0" } deno_file = { path = "../op_crates/file", version = "0.2.0" } -deno_web = { path = "../op_crates/web", version = "0.33.0" } +deno_timers = { path = "../op_crates/timers", version = "0.1.0" } deno_url = { path = "../op_crates/url", version = "0.3.0" } +deno_web = { path = "../op_crates/web", version = "0.33.0" } +deno_webgpu = { path = "../op_crates/webgpu", version = "0.4.0" } deno_webidl = { path = "../op_crates/webidl", version = "0.3.0" } deno_websocket = { path = "../op_crates/websocket", version = "0.8.0" } -deno_webgpu = { path = "../op_crates/webgpu", version = "0.4.0" } atty = "0.2.14" bytes = "1" diff --git a/runtime/build.rs b/runtime/build.rs index d7d8cb78f..efa949493 100644 --- a/runtime/build.rs +++ b/runtime/build.rs @@ -13,8 +13,10 @@ fn create_snapshot( snapshot_path: &Path, files: Vec, ) { + // Initialization order matters. deno_webidl::init(&mut js_runtime); deno_console::init(&mut js_runtime); + deno_timers::init(&mut js_runtime); deno_url::init(&mut js_runtime); deno_web::init(&mut js_runtime); deno_file::init(&mut js_runtime); diff --git a/runtime/js/11_timers.js b/runtime/js/11_timers.js deleted file mode 100644 index cfd9ad72d..000000000 --- a/runtime/js/11_timers.js +++ /dev/null @@ -1,561 +0,0 @@ -// Copyright 2018-2021 the Deno authors. All rights reserved. MIT license. -"use strict"; - -((window) => { - const assert = window.__bootstrap.util.assert; - const core = window.Deno.core; - - function opStopGlobalTimer() { - core.opSync("op_global_timer_stop"); - } - - function opStartGlobalTimer(timeout) { - return core.opSync("op_global_timer_start", timeout); - } - - async function opWaitGlobalTimer() { - await core.opAsync("op_global_timer"); - } - - function opNow() { - return core.opSync("op_now"); - } - - function sleepSync(millis = 0) { - return core.opSync("op_sleep_sync", millis); - } - - // Derived from https://github.com/vadimg/js_bintrees. MIT Licensed. - - class RBNode { - constructor(data) { - this.data = data; - this.left = null; - this.right = null; - this.red = true; - } - - getChild(dir) { - return dir ? this.right : this.left; - } - - setChild(dir, val) { - if (dir) { - this.right = val; - } else { - this.left = val; - } - } - } - - class RBTree { - #comparator = null; - #root = null; - - constructor(comparator) { - this.#comparator = comparator; - this.#root = null; - } - - /** Returns `null` if tree is empty. */ - min() { - let res = this.#root; - if (res === null) { - return null; - } - while (res.left !== null) { - res = res.left; - } - return res.data; - } - - /** Returns node `data` if found, `null` otherwise. */ - find(data) { - let res = this.#root; - while (res !== null) { - const c = this.#comparator(data, res.data); - if (c === 0) { - return res.data; - } else { - res = res.getChild(c > 0); - } - } - return null; - } - - /** returns `true` if inserted, `false` if duplicate. */ - insert(data) { - let ret = false; - - if (this.#root === null) { - // empty tree - this.#root = new RBNode(data); - ret = true; - } else { - const head = new RBNode(null); // fake tree root - - let dir = 0; - let last = 0; - - // setup - let gp = null; // grandparent - let ggp = head; // grand-grand-parent - let p = null; // parent - let node = this.#root; - ggp.right = this.#root; - - // search down - while (true) { - if (node === null) { - // insert new node at the bottom - node = new RBNode(data); - p.setChild(dir, node); - ret = true; - } else if (isRed(node.left) && isRed(node.right)) { - // color flip - node.red = true; - node.left.red = false; - node.right.red = false; - } - - // fix red violation - if (isRed(node) && isRed(p)) { - const dir2 = ggp.right === gp; - - assert(gp); - if (node === p.getChild(last)) { - ggp.setChild(dir2, singleRotate(gp, !last)); - } else { - ggp.setChild(dir2, doubleRotate(gp, !last)); - } - } - - const cmp = this.#comparator(node.data, data); - - // stop if found - if (cmp === 0) { - break; - } - - last = dir; - dir = Number(cmp < 0); // Fix type - - // update helpers - if (gp !== null) { - ggp = gp; - } - gp = p; - p = node; - node = node.getChild(dir); - } - - // update root - this.#root = head.right; - } - - // make root black - this.#root.red = false; - - return ret; - } - - /** Returns `true` if removed, `false` if not found. */ - remove(data) { - if (this.#root === null) { - return false; - } - - const head = new RBNode(null); // fake tree root - let node = head; - node.right = this.#root; - let p = null; // parent - let gp = null; // grand parent - let found = null; // found item - let dir = 1; - - while (node.getChild(dir) !== null) { - const last = dir; - - // update helpers - gp = p; - p = node; - node = node.getChild(dir); - - const cmp = this.#comparator(data, node.data); - - dir = cmp > 0; - - // save found node - if (cmp === 0) { - found = node; - } - - // push the red node down - if (!isRed(node) && !isRed(node.getChild(dir))) { - if (isRed(node.getChild(!dir))) { - const sr = singleRotate(node, dir); - p.setChild(last, sr); - p = sr; - } else if (!isRed(node.getChild(!dir))) { - const sibling = p.getChild(!last); - if (sibling !== null) { - if ( - !isRed(sibling.getChild(!last)) && - !isRed(sibling.getChild(last)) - ) { - // color flip - p.red = false; - sibling.red = true; - node.red = true; - } else { - assert(gp); - const dir2 = gp.right === p; - - if (isRed(sibling.getChild(last))) { - gp.setChild(dir2, doubleRotate(p, last)); - } else if (isRed(sibling.getChild(!last))) { - gp.setChild(dir2, singleRotate(p, last)); - } - - // ensure correct coloring - const gpc = gp.getChild(dir2); - assert(gpc); - gpc.red = true; - node.red = true; - assert(gpc.left); - gpc.left.red = false; - assert(gpc.right); - gpc.right.red = false; - } - } - } - } - } - - // replace and remove if found - if (found !== null) { - found.data = node.data; - assert(p); - p.setChild(p.right === node, node.getChild(node.left === null)); - } - - // update root and make it black - this.#root = head.right; - if (this.#root !== null) { - this.#root.red = false; - } - - return found !== null; - } - } - - function isRed(node) { - return node !== null && node.red; - } - - function singleRotate(root, dir) { - const save = root.getChild(!dir); - assert(save); - - root.setChild(!dir, save.getChild(dir)); - save.setChild(dir, root); - - root.red = true; - save.red = false; - - return save; - } - - function doubleRotate(root, dir) { - root.setChild(!dir, singleRotate(root.getChild(!dir), !dir)); - return singleRotate(root, dir); - } - - const { console } = globalThis; - const OriginalDateNow = Date.now; - - // Timeout values > TIMEOUT_MAX are set to 1. - const TIMEOUT_MAX = 2 ** 31 - 1; - - let globalTimeoutDue = null; - - let nextTimerId = 1; - const idMap = new Map(); - const dueTree = new RBTree((a, b) => a.due - b.due); - - function clearGlobalTimeout() { - globalTimeoutDue = null; - opStopGlobalTimer(); - } - - let pendingEvents = 0; - const pendingFireTimers = []; - - /** Process and run a single ready timer macrotask. - * This function should be registered through Deno.core.setMacrotaskCallback. - * Returns true when all ready macrotasks have been processed, false if more - * ready ones are available. The Isolate future would rely on the return value - * to repeatedly invoke this function until depletion. Multiple invocations - * of this function one at a time ensures newly ready microtasks are processed - * before next macrotask timer callback is invoked. */ - function handleTimerMacrotask() { - if (pendingFireTimers.length > 0) { - fire(pendingFireTimers.shift()); - return pendingFireTimers.length === 0; - } - return true; - } - - async function setGlobalTimeout(due, now) { - // Since JS and Rust don't use the same clock, pass the time to rust as a - // relative time value. On the Rust side we'll turn that into an absolute - // value again. - const timeout = due - now; - assert(timeout >= 0); - // Send message to the backend. - globalTimeoutDue = due; - pendingEvents++; - // FIXME(bartlomieju): this is problematic, because `clearGlobalTimeout` - // is synchronous. That means that timer is cancelled, but this promise is still pending - // until next turn of event loop. This leads to "leaking of async ops" in tests; - // because `clearTimeout/clearInterval` might be the last statement in test function - // `opSanitizer` will immediately complain that there is pending op going on, unless - // some timeout/defer is put in place to allow promise resolution. - // Ideally `clearGlobalTimeout` doesn't return until this op is resolved, but - // I'm not if that's possible. - opStartGlobalTimer(timeout); - await opWaitGlobalTimer(); - pendingEvents--; - // eslint-disable-next-line @typescript-eslint/no-use-before-define - prepareReadyTimers(); - } - - function prepareReadyTimers() { - const now = OriginalDateNow(); - // Bail out if we're not expecting the global timer to fire. - if (globalTimeoutDue === null || pendingEvents > 0) { - return; - } - // After firing the timers that are due now, this will hold the first timer - // list that hasn't fired yet. - let nextDueNode; - while ((nextDueNode = dueTree.min()) !== null && nextDueNode.due <= now) { - dueTree.remove(nextDueNode); - // Fire all the timers in the list. - for (const timer of nextDueNode.timers) { - // With the list dropped, the timer is no longer scheduled. - timer.scheduled = false; - // Place the callback to pending timers to fire. - pendingFireTimers.push(timer); - } - } - setOrClearGlobalTimeout(nextDueNode && nextDueNode.due, now); - } - - function setOrClearGlobalTimeout(due, now) { - if (due == null) { - clearGlobalTimeout(); - } else { - setGlobalTimeout(due, now); - } - } - - function schedule(timer, now) { - assert(!timer.scheduled); - assert(now <= timer.due); - // Find or create the list of timers that will fire at point-in-time `due`. - const maybeNewDueNode = { due: timer.due, timers: [] }; - let dueNode = dueTree.find(maybeNewDueNode); - if (dueNode === null) { - dueTree.insert(maybeNewDueNode); - dueNode = maybeNewDueNode; - } - // Append the newly scheduled timer to the list and mark it as scheduled. - dueNode.timers.push(timer); - timer.scheduled = true; - // If the new timer is scheduled to fire before any timer that existed before, - // update the global timeout to reflect this. - if (globalTimeoutDue === null || globalTimeoutDue > timer.due) { - setOrClearGlobalTimeout(timer.due, now); - } - } - - function unschedule(timer) { - // Check if our timer is pending scheduling or pending firing. - // If either is true, they are not in tree, and their idMap entry - // will be deleted soon. Remove it from queue. - let index = -1; - if ((index = pendingFireTimers.indexOf(timer)) >= 0) { - pendingFireTimers.splice(index); - return; - } - // If timer is not in the 2 pending queues and is unscheduled, - // it is not in the tree. - if (!timer.scheduled) { - return; - } - const searchKey = { due: timer.due, timers: [] }; - // Find the list of timers that will fire at point-in-time `due`. - const list = dueTree.find(searchKey).timers; - if (list.length === 1) { - // Time timer is the only one in the list. Remove the entire list. - assert(list[0] === timer); - dueTree.remove(searchKey); - // If the unscheduled timer was 'next up', find when the next timer that - // still exists is due, and update the global alarm accordingly. - if (timer.due === globalTimeoutDue) { - const nextDueNode = dueTree.min(); - setOrClearGlobalTimeout( - nextDueNode && nextDueNode.due, - OriginalDateNow(), - ); - } - } else { - // Multiple timers that are due at the same point in time. - // Remove this timer from the list. - const index = list.indexOf(timer); - assert(index > -1); - list.splice(index, 1); - } - } - - function fire(timer) { - // If the timer isn't found in the ID map, that means it has been cancelled - // between the timer firing and the promise callback (this function). - if (!idMap.has(timer.id)) { - return; - } - // Reschedule the timer if it is a repeating one, otherwise drop it. - if (!timer.repeat) { - // One-shot timer: remove the timer from this id-to-timer map. - idMap.delete(timer.id); - } else { - // Interval timer: compute when timer was supposed to fire next. - // However make sure to never schedule the next interval in the past. - const now = OriginalDateNow(); - timer.due = Math.max(now, timer.due + timer.delay); - schedule(timer, now); - } - // Call the user callback. Intermediate assignment is to avoid leaking `this` - // to it, while also keeping the stack trace neat when it shows up in there. - const callback = timer.callback; - if ("function" === typeof callback) { - callback(); - } else { - (0, eval)(callback); - } - } - - function checkThis(thisArg) { - if (thisArg !== null && thisArg !== undefined && thisArg !== globalThis) { - throw new TypeError("Illegal invocation"); - } - } - - function setTimer( - cb, - delay, - args, - repeat, - ) { - // If the callack is a function, bind `args` to the callback and bind `this` to globalThis(global). - // otherwise call `String` on it, and `eval` it on calls; do not pass variardic args to the string - let callback; - - if ("function" === typeof cb) { - callback = Function.prototype.bind.call(cb, globalThis, ...args); - } else { - callback = String(cb); - args = []; // args are ignored - } - // In the browser, the delay value must be coercible to an integer between 0 - // and INT32_MAX. Any other value will cause the timer to fire immediately. - // We emulate this behavior. - const now = OriginalDateNow(); - if (delay > TIMEOUT_MAX) { - console.warn( - `${delay} does not fit into` + - " a 32-bit signed integer." + - "\nTimeout duration was set to 1.", - ); - delay = 1; - } - delay = Math.max(0, delay | 0); - - // Create a new, unscheduled timer object. - const timer = { - id: nextTimerId++, - callback, - args, - delay, - due: now + delay, - repeat, - scheduled: false, - }; - // Register the timer's existence in the id-to-timer map. - idMap.set(timer.id, timer); - // Schedule the timer in the due table. - schedule(timer, now); - return timer.id; - } - - function setTimeout( - cb, - delay = 0, - ...args - ) { - delay >>>= 0; - checkThis(this); - return setTimer(cb, delay, args, false); - } - - function setInterval( - cb, - delay = 0, - ...args - ) { - delay >>>= 0; - checkThis(this); - return setTimer(cb, delay, args, true); - } - - function clearTimer(id) { - id >>>= 0; - const timer = idMap.get(id); - if (timer === undefined) { - // Timer doesn't exist any more or never existed. This is not an error. - return; - } - // Unschedule the timer if it is currently scheduled, and forget about it. - unschedule(timer); - idMap.delete(timer.id); - } - - function clearTimeout(id = 0) { - id >>>= 0; - if (id === 0) { - return; - } - clearTimer(id); - } - - function clearInterval(id = 0) { - id >>>= 0; - if (id === 0) { - return; - } - clearTimer(id); - } - - window.__bootstrap.timers = { - clearInterval, - setInterval, - clearTimeout, - setTimeout, - handleTimerMacrotask, - opStopGlobalTimer, - opStartGlobalTimer, - opNow, - sleepSync, - }; -})(this); diff --git a/runtime/ops/timers.rs b/runtime/ops/timers.rs index 8e709440e..3401c36f1 100644 --- a/runtime/ops/timers.rs +++ b/runtime/ops/timers.rs @@ -1,161 +1,28 @@ // Copyright 2018-2021 the Deno authors. All rights reserved. MIT license. - -//! This module helps deno implement timers. -//! -//! As an optimization, we want to avoid an expensive calls into rust for every -//! setTimeout in JavaScript. Thus in //js/timers.ts a data structure is -//! implemented that calls into Rust for only the smallest timeout. Thus we -//! only need to be able to start, cancel and await a single timer (or Delay, as Tokio -//! calls it) for an entire Isolate. This is what is implemented here. - use crate::permissions::Permissions; -use deno_core::error::AnyError; -use deno_core::futures; -use deno_core::futures::channel::oneshot; -use deno_core::futures::FutureExt; -use deno_core::futures::TryFutureExt; -use deno_core::OpState; -use deno_core::ZeroCopyBuf; -use std::cell::RefCell; -use std::future::Future; -use std::pin::Pin; -use std::rc::Rc; -use std::thread::sleep; -use std::time::Duration; -use std::time::Instant; - -pub type StartTime = Instant; - -type TimerFuture = Pin>>>; - -#[derive(Default)] -pub struct GlobalTimer { - tx: Option>, - pub future: Option, -} - -impl GlobalTimer { - pub fn cancel(&mut self) { - if let Some(tx) = self.tx.take() { - tx.send(()).ok(); - } - } - - pub fn new_timeout(&mut self, deadline: Instant) { - if self.tx.is_some() { - self.cancel(); - } - assert!(self.tx.is_none()); - self.future.take(); - - let (tx, rx) = oneshot::channel(); - self.tx = Some(tx); - - let delay = tokio::time::sleep_until(deadline.into()).boxed_local(); - let rx = rx - .map_err(|err| panic!("Unexpected error in receiving channel {:?}", err)); - - let fut = futures::future::select(delay, rx) - .then(|_| futures::future::ok(())) - .boxed_local(); - self.future = Some(fut); - } -} pub fn init(rt: &mut deno_core::JsRuntime) { { let op_state = rt.op_state(); let mut state = op_state.borrow_mut(); - state.put::(GlobalTimer::default()); - state.put::(StartTime::now()); + state.put(deno_timers::GlobalTimer::default()); + state.put(deno_timers::StartTime::now()); } - super::reg_sync(rt, "op_global_timer_stop", op_global_timer_stop); - super::reg_sync(rt, "op_global_timer_start", op_global_timer_start); - super::reg_async(rt, "op_global_timer", op_global_timer); - super::reg_sync(rt, "op_now", op_now); - super::reg_sync(rt, "op_sleep_sync", op_sleep_sync); -} - -#[allow(clippy::unnecessary_wraps)] -fn op_global_timer_stop( - state: &mut OpState, - _args: (), - _zero_copy: Option, -) -> Result<(), AnyError> { - let global_timer = state.borrow_mut::(); - global_timer.cancel(); - Ok(()) -} - -// Set up a timer that will be later awaited by JS promise. -// It's a separate op, because canceling a timeout immediately -// after setting it caused a race condition (because Tokio timeout) -// might have been registered after next event loop tick. -// -// See https://github.com/denoland/deno/issues/7599 for more -// details. -#[allow(clippy::unnecessary_wraps)] -fn op_global_timer_start( - state: &mut OpState, - timeout: u64, - _zero_copy: Option, -) -> Result<(), AnyError> { - let deadline = Instant::now() + Duration::from_millis(timeout); - let global_timer = state.borrow_mut::(); - global_timer.new_timeout(deadline); - Ok(()) -} - -async fn op_global_timer( - state: Rc>, - _args: (), - _zero_copy: Option, -) -> Result<(), AnyError> { - let maybe_timer_fut = { - let mut s = state.borrow_mut(); - let global_timer = s.borrow_mut::(); - global_timer.future.take() - }; - if let Some(timer_fut) = maybe_timer_fut { - let _ = timer_fut.await; - } - Ok(()) -} - -// Returns a milliseconds and nanoseconds subsec -// since the start time of the deno runtime. -// If the High precision flag is not set, the -// nanoseconds are rounded on 2ms. -#[allow(clippy::unnecessary_wraps)] -fn op_now( - op_state: &mut OpState, - _argument: (), - _zero_copy: Option, -) -> Result { - let start_time = op_state.borrow::(); - let seconds = start_time.elapsed().as_secs(); - let mut subsec_nanos = start_time.elapsed().subsec_nanos() as f64; - let reduced_time_precision = 2_000_000.0; // 2ms in nanoseconds - - // If the permission is not enabled - // Round the nano result on 2 milliseconds - // see: https://developer.mozilla.org/en-US/docs/Web/API/DOMHighResTimeStamp#Reduced_time_precision - if op_state.borrow_mut::().hrtime.check().is_err() { - subsec_nanos -= subsec_nanos % reduced_time_precision; - } - - let result = (seconds * 1_000) as f64 + (subsec_nanos / 1_000_000.0); - - Ok(result) -} - -#[allow(clippy::unnecessary_wraps)] -fn op_sleep_sync( - state: &mut OpState, - millis: u64, - _zero_copy: Option, -) -> Result<(), AnyError> { - super::check_unstable(state, "Deno.sleepSync"); - sleep(Duration::from_millis(millis)); - Ok(()) + super::reg_sync( + rt, + "op_global_timer_stop", + deno_timers::op_global_timer_stop, + ); + super::reg_sync( + rt, + "op_global_timer_start", + deno_timers::op_global_timer_start, + ); + super::reg_async(rt, "op_global_timer", deno_timers::op_global_timer); + super::reg_sync(rt, "op_now", deno_timers::op_now::); + super::reg_sync( + rt, + "op_sleep_sync", + deno_timers::op_sleep_sync::, + ); } diff --git a/runtime/permissions.rs b/runtime/permissions.rs index e43e0eaa0..3bdfd16bb 100644 --- a/runtime/permissions.rs +++ b/runtime/permissions.rs @@ -9,6 +9,7 @@ use deno_core::serde::Deserialize; use deno_core::serde::Serialize; use deno_core::url; use deno_core::ModuleSpecifier; +use deno_core::OpState; use log::debug; use std::collections::HashSet; use std::fmt; @@ -968,6 +969,16 @@ impl deno_fetch::FetchPermissions for Permissions { } } +impl deno_timers::TimersPermission for Permissions { + fn allow_hrtime(&mut self) -> bool { + self.hrtime.check().is_ok() + } + + fn check_unstable(&self, state: &OpState, api_name: &'static str) { + crate::ops::check_unstable(state, api_name); + } +} + impl deno_websocket::WebSocketPermissions for Permissions { fn check_net_url(&mut self, url: &url::Url) -> Result<(), AnyError> { self.net.check_url(url) -- cgit v1.2.3