Adding upstream version 110.0.1.upstream/110.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

7 files changed, 1407 insertions, 0 deletions

diff --git a/third_party/rust/tokio-timer/src/timer/atomic_stack.rs b/third_party/rust/tokio-timer/src/timer/atomic_stack.rs
new file mode 100644
index 0000000000..4e7d8ed6ec
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/atomic_stack.rs
@@ -0,0 +1,124 @@
+use super::Entry;
+use Error;
+
+use std::ptr;
+use std::sync::atomic::AtomicPtr;
+use std::sync::atomic::Ordering::SeqCst;
+use std::sync::Arc;
+
+/// A stack of `Entry` nodes
+#[derive(Debug)]
+pub(crate) struct AtomicStack {
+    /// Stack head
+    head: AtomicPtr<Entry>,
+}
+
+/// Entries that were removed from the stack
+#[derive(Debug)]
+pub(crate) struct AtomicStackEntries {
+    ptr: *mut Entry,
+}
+
+/// Used to indicate that the timer has shutdown.
+const SHUTDOWN: *mut Entry = 1 as *mut _;
+
+impl AtomicStack {
+    pub fn new() -> AtomicStack {
+        AtomicStack {
+            head: AtomicPtr::new(ptr::null_mut()),
+        }
+    }
+
+    /// Push an entry onto the stack.
+    ///
+    /// Returns `true` if the entry was pushed, `false` if the entry is already
+    /// on the stack, `Err` if the timer is shutdown.
+    pub fn push(&self, entry: &Arc<Entry>) -> Result<bool, Error> {
+        // First, set the queued bit on the entry
+        let queued = entry.queued.fetch_or(true, SeqCst).into();
+
+        if queued {
+            // Already queued, nothing more to do
+            return Ok(false);
+        }
+
+        let ptr = Arc::into_raw(entry.clone()) as *mut _;
+
+        let mut curr = self.head.load(SeqCst);
+
+        loop {
+            if curr == SHUTDOWN {
+                // Don't leak the entry node
+                let _ = unsafe { Arc::from_raw(ptr) };
+
+                return Err(Error::shutdown());
+            }
+
+            // Update the `next` pointer. This is safe because setting the queued
+            // bit is a "lock" on this field.
+            unsafe {
+                *(entry.next_atomic.get()) = curr;
+            }
+
+            let actual = self.head.compare_and_swap(curr, ptr, SeqCst);
+
+            if actual == curr {
+                break;
+            }
+
+            curr = actual;
+        }
+
+        Ok(true)
+    }
+
+    /// Take all entries from the stack
+    pub fn take(&self) -> AtomicStackEntries {
+        let ptr = self.head.swap(ptr::null_mut(), SeqCst);
+        AtomicStackEntries { ptr }
+    }
+
+    /// Drain all remaining nodes in the stack and prevent any new nodes from
+    /// being pushed onto the stack.
+    pub fn shutdown(&self) {
+        // Shutdown the processing queue
+        let ptr = self.head.swap(SHUTDOWN, SeqCst);
+
+        // Let the drop fn of `AtomicStackEntries` handle draining the stack
+        drop(AtomicStackEntries { ptr });
+    }
+}
+
+// ===== impl AtomicStackEntries =====
+
+impl Iterator for AtomicStackEntries {
+    type Item = Arc<Entry>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.ptr.is_null() {
+            return None;
+        }
+
+        // Convert the pointer to an `Arc<Entry>`
+        let entry = unsafe { Arc::from_raw(self.ptr) };
+
+        // Update `self.ptr` to point to the next element of the stack
+        self.ptr = unsafe { (*entry.next_atomic.get()) };
+
+        // Unset the queued flag
+        let res = entry.queued.fetch_and(false, SeqCst);
+        debug_assert!(res);
+
+        // Return the entry
+        Some(entry)
+    }
+}
+
+impl Drop for AtomicStackEntries {
+    fn drop(&mut self) {
+        while let Some(entry) = self.next() {
+            // Flag the entry as errored
+            entry.error();
+        }
+    }
+}
diff --git a/third_party/rust/tokio-timer/src/timer/entry.rs b/third_party/rust/tokio-timer/src/timer/entry.rs
new file mode 100644
index 0000000000..40979afaec
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/entry.rs
@@ -0,0 +1,394 @@
+use atomic::AtomicU64;
+use timer::{HandlePriv, Inner};
+use Error;
+
+use crossbeam_utils::CachePadded;
+use futures::task::AtomicTask;
+use futures::Poll;
+
+use std::cell::UnsafeCell;
+use std::ptr;
+use std::sync::atomic::AtomicBool;
+use std::sync::atomic::Ordering::{Relaxed, SeqCst};
+use std::sync::{Arc, Weak};
+use std::time::{Duration, Instant};
+use std::u64;
+
+/// Internal state shared between a `Delay` instance and the timer.
+///
+/// This struct is used as a node in two intrusive data structures:
+///
+/// * An atomic stack used to signal to the timer thread that the entry state
+///   has changed. The timer thread will observe the entry on this stack and
+///   perform any actions as necessary.
+///
+/// * A doubly linked list used **only** by the timer thread. Each slot in the
+///   timer wheel is a head pointer to the list of entries that must be
+///   processed during that timer tick.
+#[derive(Debug)]
+pub(crate) struct Entry {
+    /// Only accessed from `Registration`.
+    time: CachePadded<UnsafeCell<Time>>,
+
+    /// Timer internals. Using a weak pointer allows the timer to shutdown
+    /// without all `Delay` instances having completed.
+    ///
+    /// When `None`, the entry has not yet been linked with a timer instance.
+    inner: Option<Weak<Inner>>,
+
+    /// Tracks the entry state. This value contains the following information:
+    ///
+    /// * The deadline at which the entry must be "fired".
+    /// * A flag indicating if the entry has already been fired.
+    /// * Whether or not the entry transitioned to the error state.
+    ///
+    /// When an `Entry` is created, `state` is initialized to the instant at
+    /// which the entry must be fired. When a timer is reset to a different
+    /// instant, this value is changed.
+    state: AtomicU64,
+
+    /// Task to notify once the deadline is reached.
+    task: AtomicTask,
+
+    /// True when the entry is queued in the "process" stack. This value
+    /// is set before pushing the value and unset after popping the value.
+    ///
+    /// TODO: This could possibly be rolled up into `state`.
+    pub(super) queued: AtomicBool,
+
+    /// Next entry in the "process" linked list.
+    ///
+    /// Access to this field is coordinated by the `queued` flag.
+    ///
+    /// Represents a strong Arc ref.
+    pub(super) next_atomic: UnsafeCell<*mut Entry>,
+
+    /// When the entry expires, relative to the `start` of the timer
+    /// (Inner::start). This is only used by the timer.
+    ///
+    /// A `Delay` instance can be reset to a different deadline by the thread
+    /// that owns the `Delay` instance. In this case, the timer thread will not
+    /// immediately know that this has happened. The timer thread must know the
+    /// last deadline that it saw as it uses this value to locate the entry in
+    /// its wheel.
+    ///
+    /// Once the timer thread observes that the instant has changed, it updates
+    /// the wheel and sets this value. The idea is that this value eventually
+    /// converges to the value of `state` as the timer thread makes updates.
+    when: UnsafeCell<Option<u64>>,
+
+    /// Next entry in the State's linked list.
+    ///
+    /// This is only accessed by the timer
+    pub(super) next_stack: UnsafeCell<Option<Arc<Entry>>>,
+
+    /// Previous entry in the State's linked list.
+    ///
+    /// This is only accessed by the timer and is used to unlink a canceled
+    /// entry.
+    ///
+    /// This is a weak reference.
+    pub(super) prev_stack: UnsafeCell<*const Entry>,
+}
+
+/// Stores the info for `Delay`.
+#[derive(Debug)]
+pub(crate) struct Time {
+    pub(crate) deadline: Instant,
+    pub(crate) duration: Duration,
+}
+
+/// Flag indicating a timer entry has elapsed
+const ELAPSED: u64 = 1 << 63;
+
+/// Flag indicating a timer entry has reached an error state
+const ERROR: u64 = u64::MAX;
+
+// ===== impl Entry =====
+
+impl Entry {
+    pub fn new(deadline: Instant, duration: Duration) -> Entry {
+        Entry {
+            time: CachePadded::new(UnsafeCell::new(Time { deadline, duration })),
+            inner: None,
+            task: AtomicTask::new(),
+            state: AtomicU64::new(0),
+            queued: AtomicBool::new(false),
+            next_atomic: UnsafeCell::new(ptr::null_mut()),
+            when: UnsafeCell::new(None),
+            next_stack: UnsafeCell::new(None),
+            prev_stack: UnsafeCell::new(ptr::null_mut()),
+        }
+    }
+
+    /// Only called by `Registration`
+    pub fn time_ref(&self) -> &Time {
+        unsafe { &*self.time.get() }
+    }
+
+    /// Only called by `Registration`
+    pub fn time_mut(&self) -> &mut Time {
+        unsafe { &mut *self.time.get() }
+    }
+
+    /// Returns `true` if the `Entry` is currently associated with a timer
+    /// instance.
+    pub fn is_registered(&self) -> bool {
+        self.inner.is_some()
+    }
+
+    /// Only called by `Registration`
+    pub fn register(me: &mut Arc<Self>) {
+        let handle = match HandlePriv::try_current() {
+            Ok(handle) => handle,
+            Err(_) => {
+                // Could not associate the entry with a timer, transition the
+                // state to error
+                Arc::get_mut(me).unwrap().transition_to_error();
+
+                return;
+            }
+        };
+
+        Entry::register_with(me, handle)
+    }
+
+    /// Only called by `Registration`
+    pub fn register_with(me: &mut Arc<Self>, handle: HandlePriv) {
+        assert!(!me.is_registered(), "only register an entry once");
+
+        let deadline = me.time_ref().deadline;
+
+        let inner = match handle.inner() {
+            Some(inner) => inner,
+            None => {
+                // Could not associate the entry with a timer, transition the
+                // state to error
+                Arc::get_mut(me).unwrap().transition_to_error();
+
+                return;
+            }
+        };
+
+        // Increment the number of active timeouts
+        if inner.increment().is_err() {
+            Arc::get_mut(me).unwrap().transition_to_error();
+
+            return;
+        }
+
+        // Associate the entry with the timer
+        Arc::get_mut(me).unwrap().inner = Some(handle.into_inner());
+
+        let when = inner.normalize_deadline(deadline);
+
+        // Relaxed OK: At this point, there are no other threads that have
+        // access to this entry.
+        if when <= inner.elapsed() {
+            me.state.store(ELAPSED, Relaxed);
+            return;
+        } else {
+            me.state.store(when, Relaxed);
+        }
+
+        if inner.queue(me).is_err() {
+            // The timer has shutdown, transition the entry to the error state.
+            me.error();
+        }
+    }
+
+    fn transition_to_error(&mut self) {
+        self.inner = Some(Weak::new());
+        self.state = AtomicU64::new(ERROR);
+    }
+
+    /// The current entry state as known by the timer. This is not the value of
+    /// `state`, but lets the timer know how to converge its state to `state`.
+    pub fn when_internal(&self) -> Option<u64> {
+        unsafe { (*self.when.get()) }
+    }
+
+    pub fn set_when_internal(&self, when: Option<u64>) {
+        unsafe {
+            (*self.when.get()) = when;
+        }
+    }
+
+    /// Called by `Timer` to load the current value of `state` for processing
+    pub fn load_state(&self) -> Option<u64> {
+        let state = self.state.load(SeqCst);
+
+        if is_elapsed(state) {
+            None
+        } else {
+            Some(state)
+        }
+    }
+
+    pub fn is_elapsed(&self) -> bool {
+        let state = self.state.load(SeqCst);
+        is_elapsed(state)
+    }
+
+    pub fn fire(&self, when: u64) {
+        let mut curr = self.state.load(SeqCst);
+
+        loop {
+            if is_elapsed(curr) || curr > when {
+                return;
+            }
+
+            let next = ELAPSED | curr;
+            let actual = self.state.compare_and_swap(curr, next, SeqCst);
+
+            if curr == actual {
+                break;
+            }
+
+            curr = actual;
+        }
+
+        self.task.notify();
+    }
+
+    pub fn error(&self) {
+        // Only transition to the error state if not currently elapsed
+        let mut curr = self.state.load(SeqCst);
+
+        loop {
+            if is_elapsed(curr) {
+                return;
+            }
+
+            let next = ERROR;
+
+            let actual = self.state.compare_and_swap(curr, next, SeqCst);
+
+            if curr == actual {
+                break;
+            }
+
+            curr = actual;
+        }
+
+        self.task.notify();
+    }
+
+    pub fn cancel(entry: &Arc<Entry>) {
+        let state = entry.state.fetch_or(ELAPSED, SeqCst);
+
+        if is_elapsed(state) {
+            // Nothing more to do
+            return;
+        }
+
+        // If registered with a timer instance, try to upgrade the Arc.
+        let inner = match entry.upgrade_inner() {
+            Some(inner) => inner,
+            None => return,
+        };
+
+        let _ = inner.queue(entry);
+    }
+
+    pub fn poll_elapsed(&self) -> Poll<(), Error> {
+        use futures::Async::NotReady;
+
+        let mut curr = self.state.load(SeqCst);
+
+        if is_elapsed(curr) {
+            if curr == ERROR {
+                return Err(Error::shutdown());
+            } else {
+                return Ok(().into());
+            }
+        }
+
+        self.task.register();
+
+        curr = self.state.load(SeqCst).into();
+
+        if is_elapsed(curr) {
+            if curr == ERROR {
+                return Err(Error::shutdown());
+            } else {
+                return Ok(().into());
+            }
+        }
+
+        Ok(NotReady)
+    }
+
+    /// Only called by `Registration`
+    pub fn reset(entry: &mut Arc<Entry>) {
+        if !entry.is_registered() {
+            return;
+        }
+
+        let inner = match entry.upgrade_inner() {
+            Some(inner) => inner,
+            None => return,
+        };
+
+        let deadline = entry.time_ref().deadline;
+        let when = inner.normalize_deadline(deadline);
+        let elapsed = inner.elapsed();
+
+        let mut curr = entry.state.load(SeqCst);
+        let mut notify;
+
+        loop {
+            // In these two cases, there is no work to do when resetting the
+            // timer. If the `Entry` is in an error state, then it cannot be
+            // used anymore. If resetting the entry to the current value, then
+            // the reset is a noop.
+            if curr == ERROR || curr == when {
+                return;
+            }
+
+            let next;
+
+            if when <= elapsed {
+                next = ELAPSED;
+                notify = !is_elapsed(curr);
+            } else {
+                next = when;
+                notify = true;
+            }
+
+            let actual = entry.state.compare_and_swap(curr, next, SeqCst);
+
+            if curr == actual {
+                break;
+            }
+
+            curr = actual;
+        }
+
+        if notify {
+            let _ = inner.queue(entry);
+        }
+    }
+
+    fn upgrade_inner(&self) -> Option<Arc<Inner>> {
+        self.inner.as_ref().and_then(|inner| inner.upgrade())
+    }
+}
+
+fn is_elapsed(state: u64) -> bool {
+    state & ELAPSED == ELAPSED
+}
+
+impl Drop for Entry {
+    fn drop(&mut self) {
+        let inner = match self.upgrade_inner() {
+            Some(inner) => inner,
+            None => return,
+        };
+
+        inner.decrement();
+    }
+}
+
+unsafe impl Send for Entry {}
+unsafe impl Sync for Entry {}
diff --git a/third_party/rust/tokio-timer/src/timer/handle.rs b/third_party/rust/tokio-timer/src/timer/handle.rs
new file mode 100644
index 0000000000..4c444d8a66
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/handle.rs
@@ -0,0 +1,201 @@
+use timer::Inner;
+use {Deadline, Delay, Error, Interval, Timeout};
+
+use tokio_executor::Enter;
+
+use std::cell::RefCell;
+use std::fmt;
+use std::sync::{Arc, Weak};
+use std::time::{Duration, Instant};
+
+/// Handle to timer instance.
+///
+/// The `Handle` allows creating `Delay` instances that are driven by the
+/// associated timer.
+///
+/// A `Handle` is obtained by calling [`Timer::handle`], [`Handle::current`], or
+/// [`Handle::default`].
+///
+/// * [`Timer::handle`]: returns a handle associated with the specific timer.
+///   The handle will always reference the same timer.
+///
+/// * [`Handle::current`]: returns a handle to the timer for the execution
+///   context **at the time the function is called**. This function must be
+///   called from a runtime that has an associated timer or it will panic.
+///   The handle will always reference the same timer.
+///
+/// * [`Handle::default`]: returns a handle to the timer for the execution
+///   context **at the time the handle is used**. This function is safe to call
+///   at any time. The handle may reference different specific timer instances.
+///   Calling `Handle::default().delay(...)` is always equivalent to
+///   `Delay::new(...)`.
+///
+/// [`Timer::handle`]: struct.Timer.html#method.handle
+/// [`Handle::current`]: #method.current
+/// [`Handle::default`]: #method.default
+#[derive(Debug, Clone)]
+pub struct Handle {
+    inner: Option<HandlePriv>,
+}
+
+/// Like `Handle` but never `None`.
+#[derive(Clone)]
+pub(crate) struct HandlePriv {
+    inner: Weak<Inner>,
+}
+
+/// A guard that resets the current timer to `None` when dropped.
+#[derive(Debug)]
+pub struct DefaultGuard {
+    _p: (),
+}
+
+thread_local! {
+    /// Tracks the timer for the current execution context.
+    static CURRENT_TIMER: RefCell<Option<HandlePriv>> = RefCell::new(None)
+}
+
+/// Set the default timer for the duration of the closure.
+///
+/// From within the closure, [`Delay`] instances that are created via
+/// [`Delay::new`] can be used.
+///
+/// # Panics
+///
+/// This function panics if there already is a default timer set.
+///
+/// [`Delay`]: ../struct.Delay.html
+/// [`Delay::new`]: ../struct.Delay.html#method.new
+pub fn with_default<F, R>(handle: &Handle, enter: &mut Enter, f: F) -> R
+where
+    F: FnOnce(&mut Enter) -> R,
+{
+    let _guard = set_default(handle);
+    f(enter)
+}
+
+/// Sets `handle` as the default timer, returning a guard that unsets it on drop.
+///
+/// # Panics
+///
+/// This function panics if there already is a default timer set.
+pub fn set_default(handle: &Handle) -> DefaultGuard {
+    CURRENT_TIMER.with(|current| {
+        let mut current = current.borrow_mut();
+
+        assert!(
+            current.is_none(),
+            "default Tokio timer already set \
+             for execution context"
+        );
+
+        let handle = handle
+            .as_priv()
+            .unwrap_or_else(|| panic!("`handle` does not reference a timer"));
+
+        *current = Some(handle.clone());
+    });
+    DefaultGuard { _p: () }
+}
+
+impl Handle {
+    pub(crate) fn new(inner: Weak<Inner>) -> Handle {
+        let inner = HandlePriv { inner };
+        Handle { inner: Some(inner) }
+    }
+
+    /// Returns a handle to the current timer.
+    ///
+    /// The current timer is the timer that is currently set as default using
+    /// [`with_default`].
+    ///
+    /// This function should only be called from within the context of
+    /// [`with_default`]. Calling this function from outside of this context
+    /// will return a `Handle` that does not reference a timer. `Delay`
+    /// instances created with this handle will error.
+    ///
+    /// See [type] level documentation for more ways to obtain a `Handle` value.
+    ///
+    /// [`with_default`]: ../fn.with_default.html
+    /// [type]: #
+    pub fn current() -> Handle {
+        let private =
+            HandlePriv::try_current().unwrap_or_else(|_| HandlePriv { inner: Weak::new() });
+
+        Handle {
+            inner: Some(private),
+        }
+    }
+
+    /// Create a `Delay` driven by this handle's associated `Timer`.
+    pub fn delay(&self, deadline: Instant) -> Delay {
+        match self.inner {
+            Some(ref handle_priv) => Delay::new_with_handle(deadline, handle_priv.clone()),
+            None => Delay::new(deadline),
+        }
+    }
+
+    #[doc(hidden)]
+    #[deprecated(since = "0.2.11", note = "use timeout instead")]
+    pub fn deadline<T>(&self, future: T, deadline: Instant) -> Deadline<T> {
+        Deadline::new_with_delay(future, self.delay(deadline))
+    }
+
+    /// Create a `Timeout` driven by this handle's associated `Timer`.
+    pub fn timeout<T>(&self, value: T, deadline: Instant) -> Timeout<T> {
+        Timeout::new_with_delay(value, self.delay(deadline))
+    }
+
+    /// Create a new `Interval` that starts at `at` and yields every `duration`
+    /// interval after that.
+    pub fn interval(&self, at: Instant, duration: Duration) -> Interval {
+        Interval::new_with_delay(self.delay(at), duration)
+    }
+
+    fn as_priv(&self) -> Option<&HandlePriv> {
+        self.inner.as_ref()
+    }
+}
+
+impl Default for Handle {
+    fn default() -> Handle {
+        Handle { inner: None }
+    }
+}
+
+impl HandlePriv {
+    /// Try to get a handle to the current timer.
+    ///
+    /// Returns `Err` if no handle is found.
+    pub(crate) fn try_current() -> Result<HandlePriv, Error> {
+        CURRENT_TIMER.with(|current| match *current.borrow() {
+            Some(ref handle) => Ok(handle.clone()),
+            None => Err(Error::shutdown()),
+        })
+    }
+
+    /// Try to return a strong ref to the inner
+    pub(crate) fn inner(&self) -> Option<Arc<Inner>> {
+        self.inner.upgrade()
+    }
+
+    /// Consume the handle, returning the weak Inner ref.
+    pub(crate) fn into_inner(self) -> Weak<Inner> {
+        self.inner
+    }
+}
+
+impl fmt::Debug for HandlePriv {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "HandlePriv")
+    }
+}
+
+impl Drop for DefaultGuard {
+    fn drop(&mut self) {
+        let _ = CURRENT_TIMER.try_with(|current| {
+            let mut current = current.borrow_mut();
+            *current = None;
+        });
+    }
+}
diff --git a/third_party/rust/tokio-timer/src/timer/mod.rs b/third_party/rust/tokio-timer/src/timer/mod.rs
new file mode 100644
index 0000000000..31eb0afbb1
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/mod.rs
@@ -0,0 +1,490 @@
+//! Timer implementation.
+//!
+//! This module contains the types needed to run a timer.
+//!
+//! The [`Timer`] type runs the timer logic. It holds all the necessary state
+//! to track all associated [`Delay`] instances and delivering notifications
+//! once the deadlines are reached.
+//!
+//! The [`Handle`] type is a reference to a [`Timer`] instance. This type is
+//! `Clone`, `Send`, and `Sync`. This type is used to create instances of
+//! [`Delay`].
+//!
+//! The [`Now`] trait describes how to get an [`Instant`] representing the
+//! current moment in time. [`SystemNow`] is the default implementation, where
+//! [`Now::now`] is implemented by calling [`Instant::now`].
+//!
+//! [`Timer`] is generic over [`Now`]. This allows the source of time to be
+//! customized. This ability is especially useful in tests and any environment
+//! where determinism is necessary.
+//!
+//! Note, when using the Tokio runtime, the [`Timer`] does not need to be manually
+//! setup as the runtime comes pre-configured with a [`Timer`] instance.
+//!
+//! [`Timer`]: struct.Timer.html
+//! [`Handle`]: struct.Handle.html
+//! [`Delay`]: ../struct.Delay.html
+//! [`Now`]: ../clock/trait.Now.html
+//! [`Now::now`]: ../clock/trait.Now.html#method.now
+//! [`SystemNow`]: struct.SystemNow.html
+//! [`Instant`]: https://doc.rust-lang.org/std/time/struct.Instant.html
+//! [`Instant::now`]: https://doc.rust-lang.org/std/time/struct.Instant.html#method.now
+
+// This allows the usage of the old `Now` trait.
+#![allow(deprecated)]
+
+mod atomic_stack;
+mod entry;
+mod handle;
+mod now;
+mod registration;
+mod stack;
+
+use self::atomic_stack::AtomicStack;
+use self::entry::Entry;
+use self::stack::Stack;
+
+pub(crate) use self::handle::HandlePriv;
+pub use self::handle::{set_default, with_default, DefaultGuard, Handle};
+pub use self::now::{Now, SystemNow};
+pub(crate) use self::registration::Registration;
+
+use atomic::AtomicU64;
+use wheel;
+use Error;
+
+use tokio_executor::park::{Park, ParkThread, Unpark};
+
+use std::sync::atomic::AtomicUsize;
+use std::sync::atomic::Ordering::SeqCst;
+use std::sync::Arc;
+use std::time::{Duration, Instant};
+use std::usize;
+use std::{cmp, fmt};
+
+/// Timer implementation that drives [`Delay`], [`Interval`], and [`Timeout`].
+///
+/// A `Timer` instance tracks the state necessary for managing time and
+/// notifying the [`Delay`] instances once their deadlines are reached.
+///
+/// It is expected that a single `Timer` instance manages many individual
+/// [`Delay`] instances. The `Timer` implementation is thread-safe and, as such,
+/// is able to handle callers from across threads.
+///
+/// Callers do not use `Timer` directly to create [`Delay`] instances.  Instead,
+/// [`Handle`][Handle.struct] is used. A handle for the timer instance is obtained by calling
+/// [`handle`]. [`Handle`][Handle.struct] is the type that implements `Clone` and is `Send +
+/// Sync`.
+///
+/// After creating the `Timer` instance, the caller must repeatedly call
+/// [`turn`]. The timer will perform no work unless [`turn`] is called
+/// repeatedly.
+///
+/// The `Timer` has a resolution of one millisecond. Any unit of time that falls
+/// between milliseconds are rounded up to the next millisecond.
+///
+/// When the `Timer` instance is dropped, any outstanding [`Delay`] instance that
+/// has not elapsed will be notified with an error. At this point, calling
+/// `poll` on the [`Delay`] instance will result in `Err` being returned.
+///
+/// # Implementation
+///
+/// `Timer` is based on the [paper by Varghese and Lauck][paper].
+///
+/// A hashed timing wheel is a vector of slots, where each slot handles a time
+/// slice. As time progresses, the timer walks over the slot for the current
+/// instant, and processes each entry for that slot. When the timer reaches the
+/// end of the wheel, it starts again at the beginning.
+///
+/// The `Timer` implementation maintains six wheels arranged in a set of levels.
+/// As the levels go up, the slots of the associated wheel represent larger
+/// intervals of time. At each level, the wheel has 64 slots. Each slot covers a
+/// range of time equal to the wheel at the lower level. At level zero, each
+/// slot represents one millisecond of time.
+///
+/// The wheels are:
+///
+/// * Level 0: 64 x 1 millisecond slots.
+/// * Level 1: 64 x 64 millisecond slots.
+/// * Level 2: 64 x ~4 second slots.
+/// * Level 3: 64 x ~4 minute slots.
+/// * Level 4: 64 x ~4 hour slots.
+/// * Level 5: 64 x ~12 day slots.
+///
+/// When the timer processes entries at level zero, it will notify all the
+/// [`Delay`] instances as their deadlines have been reached. For all higher
+/// levels, all entries will be redistributed across the wheel at the next level
+/// down. Eventually, as time progresses, entries will [`Delay`] instances will
+/// either be canceled (dropped) or their associated entries will reach level
+/// zero and be notified.
+///
+/// [`Delay`]: ../struct.Delay.html
+/// [`Interval`]: ../struct.Interval.html
+/// [`Timeout`]: ../struct.Timeout.html
+/// [paper]: http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
+/// [`handle`]: #method.handle
+/// [`turn`]: #method.turn
+/// [Handle.struct]: struct.Handle.html
+#[derive(Debug)]
+pub struct Timer<T, N = SystemNow> {
+    /// Shared state
+    inner: Arc<Inner>,
+
+    /// Timer wheel
+    wheel: wheel::Wheel<Stack>,
+
+    /// Thread parker. The `Timer` park implementation delegates to this.
+    park: T,
+
+    /// Source of "now" instances
+    now: N,
+}
+
+/// Return value from the `turn` method on `Timer`.
+///
+/// Currently this value doesn't actually provide any functionality, but it may
+/// in the future give insight into what happened during `turn`.
+#[derive(Debug)]
+pub struct Turn(());
+
+/// Timer state shared between `Timer`, `Handle`, and `Registration`.
+pub(crate) struct Inner {
+    /// The instant at which the timer started running.
+    start: Instant,
+
+    /// The last published timer `elapsed` value.
+    elapsed: AtomicU64,
+
+    /// Number of active timeouts
+    num: AtomicUsize,
+
+    /// Head of the "process" linked list.
+    process: AtomicStack,
+
+    /// Unparks the timer thread.
+    unpark: Box<dyn Unpark>,
+}
+
+/// Maximum number of timeouts the system can handle concurrently.
+const MAX_TIMEOUTS: usize = usize::MAX >> 1;
+
+// ===== impl Timer =====
+
+impl<T> Timer<T>
+where
+    T: Park,
+{
+    /// Create a new `Timer` instance that uses `park` to block the current
+    /// thread.
+    ///
+    /// Once the timer has been created, a handle can be obtained using
+    /// [`handle`]. The handle is used to create `Delay` instances.
+    ///
+    /// Use `default` when constructing a `Timer` using the default `park`
+    /// instance.
+    ///
+    /// [`handle`]: #method.handle
+    pub fn new(park: T) -> Self {
+        Timer::new_with_now(park, SystemNow::new())
+    }
+}
+
+impl<T, N> Timer<T, N> {
+    /// Returns a reference to the underlying `Park` instance.
+    pub fn get_park(&self) -> &T {
+        &self.park
+    }
+
+    /// Returns a mutable reference to the underlying `Park` instance.
+    pub fn get_park_mut(&mut self) -> &mut T {
+        &mut self.park
+    }
+}
+
+impl<T, N> Timer<T, N>
+where
+    T: Park,
+    N: Now,
+{
+    /// Create a new `Timer` instance that uses `park` to block the current
+    /// thread and `now` to get the current `Instant`.
+    ///
+    /// Specifying the source of time is useful when testing.
+    pub fn new_with_now(park: T, mut now: N) -> Self {
+        let unpark = Box::new(park.unpark());
+
+        Timer {
+            inner: Arc::new(Inner::new(now.now(), unpark)),
+            wheel: wheel::Wheel::new(),
+            park,
+            now,
+        }
+    }
+
+    /// Returns a handle to the timer.
+    ///
+    /// The `Handle` is how `Delay` instances are created. The `Delay` instances
+    /// can either be created directly or the `Handle` instance can be passed to
+    /// `with_default`, setting the timer as the default timer for the execution
+    /// context.
+    pub fn handle(&self) -> Handle {
+        Handle::new(Arc::downgrade(&self.inner))
+    }
+
+    /// Performs one iteration of the timer loop.
+    ///
+    /// This function must be called repeatedly in order for the `Timer`
+    /// instance to make progress. This is where the work happens.
+    ///
+    /// The `Timer` will use the `Park` instance that was specified in [`new`]
+    /// to block the current thread until the next `Delay` instance elapses. One
+    /// call to `turn` results in at most one call to `park.park()`.
+    ///
+    /// # Return
+    ///
+    /// On success, `Ok(Turn)` is returned, where `Turn` is a placeholder type
+    /// that currently does nothing but may, in the future, have functions add
+    /// to provide information about the call to `turn`.
+    ///
+    /// If the call to `park.park()` fails, then `Err` is returned with the
+    /// error.
+    ///
+    /// [`new`]: #method.new
+    pub fn turn(&mut self, max_wait: Option<Duration>) -> Result<Turn, T::Error> {
+        match max_wait {
+            Some(timeout) => self.park_timeout(timeout)?,
+            None => self.park()?,
+        }
+
+        Ok(Turn(()))
+    }
+
+    /// Converts an `Expiration` to an `Instant`.
+    fn expiration_instant(&self, when: u64) -> Instant {
+        self.inner.start + Duration::from_millis(when)
+    }
+
+    /// Run timer related logic
+    fn process(&mut self) {
+        let now = ::ms(self.now.now() - self.inner.start, ::Round::Down);
+        let mut poll = wheel::Poll::new(now);
+
+        while let Some(entry) = self.wheel.poll(&mut poll, &mut ()) {
+            let when = entry.when_internal().expect("invalid internal entry state");
+
+            // Fire the entry
+            entry.fire(when);
+
+            // Track that the entry has been fired
+            entry.set_when_internal(None);
+        }
+
+        // Update the elapsed cache
+        self.inner.elapsed.store(self.wheel.elapsed(), SeqCst);
+    }
+
+    /// Process the entry queue
+    ///
+    /// This handles adding and canceling timeouts.
+    fn process_queue(&mut self) {
+        for entry in self.inner.process.take() {
+            match (entry.when_internal(), entry.load_state()) {
+                (None, None) => {
+                    // Nothing to do
+                }
+                (Some(_), None) => {
+                    // Remove the entry
+                    self.clear_entry(&entry);
+                }
+                (None, Some(when)) => {
+                    // Queue the entry
+                    self.add_entry(entry, when);
+                }
+                (Some(_), Some(next)) => {
+                    self.clear_entry(&entry);
+                    self.add_entry(entry, next);
+                }
+            }
+        }
+    }
+
+    fn clear_entry(&mut self, entry: &Arc<Entry>) {
+        self.wheel.remove(entry, &mut ());
+        entry.set_when_internal(None);
+    }
+
+    /// Fire the entry if it needs to, otherwise queue it to be processed later.
+    ///
+    /// Returns `None` if the entry was fired.
+    fn add_entry(&mut self, entry: Arc<Entry>, when: u64) {
+        use wheel::InsertError;
+
+        entry.set_when_internal(Some(when));
+
+        match self.wheel.insert(when, entry, &mut ()) {
+            Ok(_) => {}
+            Err((entry, InsertError::Elapsed)) => {
+                // The entry's deadline has elapsed, so fire it and update the
+                // internal state accordingly.
+                entry.set_when_internal(None);
+                entry.fire(when);
+            }
+            Err((entry, InsertError::Invalid)) => {
+                // The entry's deadline is invalid, so error it and update the
+                // internal state accordingly.
+                entry.set_when_internal(None);
+                entry.error();
+            }
+        }
+    }
+}
+
+impl Default for Timer<ParkThread, SystemNow> {
+    fn default() -> Self {
+        Timer::new(ParkThread::new())
+    }
+}
+
+impl<T, N> Park for Timer<T, N>
+where
+    T: Park,
+    N: Now,
+{
+    type Unpark = T::Unpark;
+    type Error = T::Error;
+
+    fn unpark(&self) -> Self::Unpark {
+        self.park.unpark()
+    }
+
+    fn park(&mut self) -> Result<(), Self::Error> {
+        self.process_queue();
+
+        match self.wheel.poll_at() {
+            Some(when) => {
+                let now = self.now.now();
+                let deadline = self.expiration_instant(when);
+
+                if deadline > now {
+                    self.park.park_timeout(deadline - now)?;
+                } else {
+                    self.park.park_timeout(Duration::from_secs(0))?;
+                }
+            }
+            None => {
+                self.park.park()?;
+            }
+        }
+
+        self.process();
+
+        Ok(())
+    }
+
+    fn park_timeout(&mut self, duration: Duration) -> Result<(), Self::Error> {
+        self.process_queue();
+
+        match self.wheel.poll_at() {
+            Some(when) => {
+                let now = self.now.now();
+                let deadline = self.expiration_instant(when);
+
+                if deadline > now {
+                    self.park.park_timeout(cmp::min(deadline - now, duration))?;
+                } else {
+                    self.park.park_timeout(Duration::from_secs(0))?;
+                }
+            }
+            None => {
+                self.park.park_timeout(duration)?;
+            }
+        }
+
+        self.process();
+
+        Ok(())
+    }
+}
+
+impl<T, N> Drop for Timer<T, N> {
+    fn drop(&mut self) {
+        use std::u64;
+
+        // Shutdown the stack of entries to process, preventing any new entries
+        // from being pushed.
+        self.inner.process.shutdown();
+
+        // Clear the wheel, using u64::MAX allows us to drain everything
+        let mut poll = wheel::Poll::new(u64::MAX);
+
+        while let Some(entry) = self.wheel.poll(&mut poll, &mut ()) {
+            entry.error();
+        }
+    }
+}
+
+// ===== impl Inner =====
+
+impl Inner {
+    fn new(start: Instant, unpark: Box<dyn Unpark>) -> Inner {
+        Inner {
+            num: AtomicUsize::new(0),
+            elapsed: AtomicU64::new(0),
+            process: AtomicStack::new(),
+            start,
+            unpark,
+        }
+    }
+
+    fn elapsed(&self) -> u64 {
+        self.elapsed.load(SeqCst)
+    }
+
+    /// Increment the number of active timeouts
+    fn increment(&self) -> Result<(), Error> {
+        let mut curr = self.num.load(SeqCst);
+
+        loop {
+            if curr == MAX_TIMEOUTS {
+                return Err(Error::at_capacity());
+            }
+
+            let actual = self.num.compare_and_swap(curr, curr + 1, SeqCst);
+
+            if curr == actual {
+                return Ok(());
+            }
+
+            curr = actual;
+        }
+    }
+
+    /// Decrement the number of active timeouts
+    fn decrement(&self) {
+        let prev = self.num.fetch_sub(1, SeqCst);
+        debug_assert!(prev <= MAX_TIMEOUTS);
+    }
+
+    fn queue(&self, entry: &Arc<Entry>) -> Result<(), Error> {
+        if self.process.push(entry)? {
+            // The timer is notified so that it can process the timeout
+            self.unpark.unpark();
+        }
+
+        Ok(())
+    }
+
+    fn normalize_deadline(&self, deadline: Instant) -> u64 {
+        if deadline < self.start {
+            return 0;
+        }
+
+        ::ms(deadline - self.start, ::Round::Up)
+    }
+}
+
+impl fmt::Debug for Inner {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt.debug_struct("Inner").finish()
+    }
+}
diff --git a/third_party/rust/tokio-timer/src/timer/now.rs b/third_party/rust/tokio-timer/src/timer/now.rs
new file mode 100644
index 0000000000..9f23bad711
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/now.rs
@@ -0,0 +1,10 @@
+use std::time::Instant;
+
+#[doc(hidden)]
+#[deprecated(since = "0.2.4", note = "use clock::Now instead")]
+pub trait Now {
+    /// Returns an instant corresponding to "now".
+    fn now(&mut self) -> Instant;
+}
+
+pub use clock::Clock as SystemNow;
diff --git a/third_party/rust/tokio-timer/src/timer/registration.rs b/third_party/rust/tokio-timer/src/timer/registration.rs
new file mode 100644
index 0000000000..dad1355dcd
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/registration.rs
@@ -0,0 +1,67 @@
+use clock::now;
+use timer::{Entry, HandlePriv};
+use Error;
+
+use futures::Poll;
+
+use std::sync::Arc;
+use std::time::{Duration, Instant};
+
+/// Registration with a timer.
+///
+/// The association between a `Delay` instance and a timer is done lazily in
+/// `poll`
+#[derive(Debug)]
+pub(crate) struct Registration {
+    entry: Arc<Entry>,
+}
+
+impl Registration {
+    pub fn new(deadline: Instant, duration: Duration) -> Registration {
+        fn is_send<T: Send + Sync>() {}
+        is_send::<Registration>();
+
+        Registration {
+            entry: Arc::new(Entry::new(deadline, duration)),
+        }
+    }
+
+    pub fn deadline(&self) -> Instant {
+        self.entry.time_ref().deadline
+    }
+
+    pub fn register(&mut self) {
+        if !self.entry.is_registered() {
+            Entry::register(&mut self.entry)
+        }
+    }
+
+    pub fn register_with(&mut self, handle: HandlePriv) {
+        Entry::register_with(&mut self.entry, handle)
+    }
+
+    pub fn reset(&mut self, deadline: Instant) {
+        self.entry.time_mut().deadline = deadline;
+        Entry::reset(&mut self.entry);
+    }
+
+    pub fn reset_timeout(&mut self) {
+        let deadline = now() + self.entry.time_ref().duration;
+        self.entry.time_mut().deadline = deadline;
+        Entry::reset(&mut self.entry);
+    }
+
+    pub fn is_elapsed(&self) -> bool {
+        self.entry.is_elapsed()
+    }
+
+    pub fn poll_elapsed(&self) -> Poll<(), Error> {
+        self.entry.poll_elapsed()
+    }
+}
+
+impl Drop for Registration {
+    fn drop(&mut self) {
+        Entry::cancel(&self.entry);
+    }
+}
diff --git a/third_party/rust/tokio-timer/src/timer/stack.rs b/third_party/rust/tokio-timer/src/timer/stack.rs
new file mode 100644
index 0000000000..c63eed971b
--- /dev/null
+++ b/third_party/rust/tokio-timer/src/timer/stack.rs
@@ -0,0 +1,121 @@
+use super::Entry;
+use wheel;
+
+use std::ptr;
+use std::sync::Arc;
+
+/// A doubly linked stack
+#[derive(Debug)]
+pub(crate) struct Stack {
+    head: Option<Arc<Entry>>,
+}
+
+impl Default for Stack {
+    fn default() -> Stack {
+        Stack { head: None }
+    }
+}
+
+impl wheel::Stack for Stack {
+    type Owned = Arc<Entry>;
+    type Borrowed = Entry;
+    type Store = ();
+
+    fn is_empty(&self) -> bool {
+        self.head.is_none()
+    }
+
+    fn push(&mut self, entry: Self::Owned, _: &mut Self::Store) {
+        // Get a pointer to the entry to for the prev link
+        let ptr: *const Entry = &*entry as *const _;
+
+        // Remove the old head entry
+        let old = self.head.take();
+
+        unsafe {
+            // Ensure the entry is not already in a stack.
+            debug_assert!((*entry.next_stack.get()).is_none());
+            debug_assert!((*entry.prev_stack.get()).is_null());
+
+            if let Some(ref entry) = old.as_ref() {
+                debug_assert!({
+                    // The head is not already set to the entry
+                    ptr != &***entry as *const _
+                });
+
+                // Set the previous link on the old head
+                *entry.prev_stack.get() = ptr;
+            }
+
+            // Set this entry's next pointer
+            *entry.next_stack.get() = old;
+        }
+
+        // Update the head pointer
+        self.head = Some(entry);
+    }
+
+    /// Pop an item from the stack
+    fn pop(&mut self, _: &mut ()) -> Option<Arc<Entry>> {
+        let entry = self.head.take();
+
+        unsafe {
+            if let Some(entry) = entry.as_ref() {
+                self.head = (*entry.next_stack.get()).take();
+
+                if let Some(entry) = self.head.as_ref() {
+                    *entry.prev_stack.get() = ptr::null();
+                }
+
+                *entry.prev_stack.get() = ptr::null();
+            }
+        }
+
+        entry
+    }
+
+    fn remove(&mut self, entry: &Entry, _: &mut ()) {
+        unsafe {
+            // Ensure that the entry is in fact contained by the stack
+            debug_assert!({
+                // This walks the full linked list even if an entry is found.
+                let mut next = self.head.as_ref();
+                let mut contains = false;
+
+                while let Some(n) = next {
+                    if entry as *const _ == &**n as *const _ {
+                        debug_assert!(!contains);
+                        contains = true;
+                    }
+
+                    next = (*n.next_stack.get()).as_ref();
+                }
+
+                contains
+            });
+
+            // Unlink `entry` from the next node
+            let next = (*entry.next_stack.get()).take();
+
+            if let Some(next) = next.as_ref() {
+                (*next.prev_stack.get()) = *entry.prev_stack.get();
+            }
+
+            // Unlink `entry` from the prev node
+
+            if let Some(prev) = (*entry.prev_stack.get()).as_ref() {
+                *prev.next_stack.get() = next;
+            } else {
+                // It is the head
+                self.head = next;
+            }
+
+            // Unset the prev pointer
+            *entry.prev_stack.get() = ptr::null();
+        }
+    }
+
+    fn when(item: &Entry, _: &()) -> u64 {
+        item.when_internal().expect("invalid internal state")
+    }
+}