GitHub PullRequestReviewCommentEvent at 2014-01-14 21:03:34
Repository: rust
Actor: alexcrichton
Payload: {"comment":{"url":"https://api.github.com/repos/mozilla/rust/pulls/comments/8875874","id":8875874,"diff_hunk":"@@ -0,0 +1,639 @@\n+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT\n+// file at the top-level directory of this distribution and at\n+// http://rust-lang.org/COPYRIGHT.\n+//\n+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or\n+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license\n+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your\n+// option. This file may not be copied, modified, or distributed\n+// except according to those terms.\n+\n+//! A proper mutex implementation regardless of the \"flavor of task\" which is\n+//! acquiring the lock.\n+\n+// # The implementation of Rust's mutexes\n+//\n+// As hinted in the doc-comment above, the fundamental problem of implementing a\n+// mutex for rust is that you can't \"just use pthreads\". Green tasks are not\n+// allowed to block on a pthread mutex, because this can very easily lead to\n+// deadlock. Otherwise, there are other properties that we would want out of an\n+// \"official mutex\":\n+//\n+// * Any flavor of task can acquire the mutex, green or native\n+// * Any mixing of flavors of tasks can acquire the mutex. It should be possible\n+//   for green and native threads to contend over acquiring the mutex\n+// * This mutex should be \"just as fast\" as pthreads\n+// * Mutexes should be statically initializeable\n+// * Mutexes should really not need to have destructors (see static\n+//   initialization)\n+//\n+// Some properties which have been deemed not critical\n+//\n+// * Enforcing bounded waiting among all tasks acquiring the mutex. Mixing\n+//   green/native tasks is predicted to be a fairly rare case.\n+//\n+// ## Mutexes, take 1\n+//\n+// Within these constraints, the primitives we have available to us for blocking\n+// a task are the `deschedule` and `reawaken` methods on the `rt::Runtime`\n+// trait. These are the obvious choices to use first because they're \"what we\n+// havel already\" and should certainly be efficient.\n+//\n+// The sketch behind this mutex would be to use an intrusive (to avoid\n+// allocations) MPSC queue (the consumer is the lock holder) with some\n+// sprinkling of atomics to wake threads up. Each `BlockedTask` would be stored\n+// in the nodes of the queue.\n+//\n+// This implementation is all fine and dandy for green threads (user space\n+// context switching is fast), but when implemented, it was found that this\n+// implementation was about 50x slower than pthreads for native threads.\n+//\n+// Upon profiling, nearly all time was spent in cvar signal/wait (that's how\n+// native threads implement deschedule/reawaken). The problem was never tracked\n+// down with 100% certainty, but it was able discovered that this huge slowdown\n+// was only on a multicore system, not a single core system. With this knowledge\n+// in hand, plus some idea of how pthread mutexes are implemented, it was\n+// deduced that the kernel essentially knows what's going on when everyone's\n+// contended on the same mutex (as in the pthreads case). The kernel can\n+// cleverly schedule threads to *not* wake up on remote cores because all the\n+// work needs to happen on the same core (that's the whole point of a mutex).\n+// The deschedule/reawaken methods put threads to sleep on localized cvars, so\n+// the kernel had no idea that all our threads were contending *on the same\n+// mutex*.\n+//\n+// With this information in mind, it was concluded that it's impossible to\n+// create a pthreads-competitive mutex with the deschedule/reawaken primitives.\n+// We simply have no way of instructing the kernel that all native threads are\n+// contended on one object and should therefore *not* be spread out on many\n+// cores.\n+//\n+// ## Mutexes, take 2\n+//\n+// Back do the drawing board, the key idea was to actually have this mutex be a\n+// wrapper around a pthreads mutex. This would clearly solve the native threads\n+// problem (we'd be \"just as fast\" as pthreads), but the green problem comes\n+// back into play (you can't just grab the lock).\n+//\n+// The solution found (and the current implementation) ended up having a hybrid\n+// solution of queues/mutexes. The key idea is that green threads only ever\n+// *trylock* and use an internal queue to keep track of who's waiting, and\n+// native threads will simply just call *lock*.\n+//\n+// With this scheme, we get all the benefits of both worlds:\n+//\n+// * Any flavor of task (even mixed) can grab a mutex, pthreads arbitrates among\n+//   all native and the first green tasks, and then green tasks use atomics to\n+//   arbitrate among themselves.\n+// * We're just as fast as pthreads (within a small percentage of course)\n+// * Native mutexes are statically initializeable, and some clever usage of\n+//   atomics can make the green halves of the mutex also statically\n+//   initializeable.\n+// * No destructors are necessary (there is no memory allocation). The caveat\n+//   here is that windows doesn't have statically initialized mutexes, but it is\n+//   predicted that statically initialized mutexes won't be *too* common. Plus,\n+//   the \"free\" happens at program end when cleaning up doesn't matter *that*\n+//   much.\n+//\n+// As you'll find out in the implementation, this approach cannot be fair to\n+// native and green threads. In order to soundly drain the internal queue of\n+// green threads, they *must* be favored over native threads. It was an explicit\n+// non-goal of these mutexes to be completely fair to everyone, so this has been\n+// deemed acceptable.\n+//\n+// ## Mutexes, take 3\n+//\n+// Take 3 uses a more sophisticated atomic state, allowing it to not use yield loops.\n+//\n+// This is the high-level implementation of the mutexes, but the nitty gritty\n+// details can be found in the code below.\n+\n+use ops::Drop;\n+use option::{Option, Some, None};\n+use q = sync::mpsc_intrusive;\n+use result::{Err, Ok};\n+use rt::local::Local;\n+use rt::task::{BlockedTask, Task};\n+use sync::atomics;\n+use unstable::mutex;\n+\n+/// A mutual exclusion primitive useful for protecting shared data\n+///\n+/// This mutex is an implementation of a lock for all flavors of tasks which may\n+/// be grabbing. A common problem with green threads is that they cannot grab\n+/// locks (if they reschedule during the lock a contender could deadlock the\n+/// system), but this mutex does *not* suffer this problem.\n+///\n+/// This mutex will properly block tasks waiting for the lock to become\n+/// available. The mutex can also be statically initialized or created via a\n+/// `new` constructor.\n+///\n+/// # Example\n+///\n+/// ```rust\n+/// use std::sync::Mutex;\n+///\n+/// let mut m = Mutex::new();\n+/// let guard = m.lock();\n+/// // do some work\n+/// drop(guard); // unlock the lock\n+///\n+/// {\n+///     let _g = m.lock();\n+///     // do some work in a scope\n+/// }\n+///\n+/// // now the mutex is unlocked\n+/// ```\n+pub struct Mutex {\n+    priv lock: StaticMutex,\n+}\n+\n+/// The static mutex type is provided to allow for static allocation of mutexes.\n+///\n+/// Note that this is a separate type because using a Mutex correctly means that\n+/// it needs to have a destructor run. In Rust, statics are not allowed to have\n+/// destructors. As a result, a `StaticMutex` has one extra method when compared\n+/// to a `Mutex`, a `destroy` method. This method is unsafe to call, and\n+/// documentation can be found directly on the method.\n+///\n+/// # Example\n+///\n+/// ```rust\n+/// use std::sync::{StaticMutex, MUTEX_INIT};\n+///\n+/// static mut LOCK: StaticMutex = MUTEX_INIT;\n+///\n+/// unsafe {\n+///     let _g = LOCK.lock();\n+///     // do some productive work\n+/// }\n+/// // lock is unlocked here.\n+/// ```\n+pub struct StaticMutex {\n+    /// The OS mutex (pthreads/windows equivalent) that we're wrapping.\n+    priv lock: mutex::Mutex,\n+    /// Internal mutex state\n+    priv state: MutexState,\n+    /// Internal queue that all green threads will be blocked on.\n+    priv q: q::Queue<atomics::AtomicUint>,\n+}\n+\n+/// An RAII implementation of a \"scoped lock\" of a mutex. When this structure is\n+/// dropped (falls out of scope), the lock will be unlocked.\n+pub struct Guard<'a> {\n+    priv lock: &'a mut StaticMutex,\n+}\n+\n+/// Static initialization of a mutex. This constant can be used to initialize\n+/// other mutex constants.\n+pub static MUTEX_INIT: StaticMutex = StaticMutex {\n+    lock: mutex::MUTEX_INIT,\n+    state: INIT_MUTEX_STATE,\n+    q: q::Queue {\n+        producer: atomics::INIT_ATOMIC_UINT,\n+        consumer: 0 as *mut q::Node<atomics::AtomicUint>,\n+    }\n+};\n+\n+/// this is logically an atomic tuple of (lockers, queue_size)\n+/// lockers is the number of tasks about to call lock() or holding the mutex\n+/// queue_size is the number of queued up tasks\n+struct MutexState {\n+    priv state: atomics::AtomicUint // XXX: this needs to become AtomicU64\n+}\n+\n+static INIT_MUTEX_STATE: MutexState = MutexState {state: atomics::INIT_ATOMIC_UINT};\n+\n+static LOCKERS: uint = 1;\n+// XXX: this limits 32-bit tasks to 2^16; we need to use 64-bit atomics on 32-bit too to fix this\n+#[cfg(target_word_size = \"32\")] static QUEUE_SIZE: uint = (1u << 16);\n+#[cfg(target_word_size = \"64\")] static QUEUE_SIZE: uint = (1u << 32);\n+static LOCKERS_MASK: uint = QUEUE_SIZE - LOCKERS;\n+static QUEUE_SIZE_MASK: uint = -QUEUE_SIZE;\n+\n+impl MutexState {\n+    pub fn new() -> MutexState {\n+        MutexState {state: atomics::AtomicUint::new(0)}\n+    }\n+\n+    // if queue_size == 0 {++lockers; true} else {false}\n+    pub fn should_lock(&mut self) -> bool {\n+        // optimistically speculate we have no contention\n+        let mut a = self.state.compare_and_swap(0, LOCKERS, atomics::SeqCst);\n+        if a == 0 {return true;}\n+\n+        loop {\n+            let (b, r) = if (a & QUEUE_SIZE_MASK) != 0 {\n+                return false;\n+            } else {\n+                (a + LOCKERS, true)\n+            };\n+            let v = self.state.compare_and_swap(a, b, atomics::SeqCst);\n+            if a == v {return r;}\n+            a = v;\n+        }\n+    }\n+ \n+    // ++queue_size; if(lockers == 0) {++lockers; true} else {false}\n+    pub fn queue_and_should_lock(&mut self) -> bool {\n+        // optimistically speculate we have only green tasks and nothing queued\n+        let mut a = self.state.compare_and_swap(LOCKERS, LOCKERS + QUEUE_SIZE, atomics::SeqCst);\n+        if a == LOCKERS {return false;}\n+\n+        loop {\n+            let (b, r) = if (a & LOCKERS_MASK) == 0 {\n+                (a + QUEUE_SIZE + LOCKERS, true)\n+            } else {\n+                (a + QUEUE_SIZE, false)\n+            };\n+            let v = self.state.compare_and_swap(a, b, atomics::SeqCst);\n+            if a == v {return r;}\n+            a = v;\n+        }\n+    }\n+\n+    // --queue_size;\n+    pub fn dequeue(&mut self) {\n+        self.state.fetch_sub(QUEUE_SIZE, atomics::SeqCst);","path":"src/libstd/sync/mutex.rs","position":257,"original_position":257,"commit_id":"fb86be7b26b4db7e5d9c58a3616fff046a0773b9","original_commit_id":"fb86be7b26b4db7e5d9c58a3616fff046a0773b9","user":{"login":"alexcrichton","id":64996,"avatar_url":"https://gravatar.com/avatar/477e2098d9864b482d28e5ef8e657f43?d=https%3A%2F%2Fidenticons.github.com%2F621df6a7a3377f22b1ae3afc962c3f68.png&r=x","gravatar_id":"477e2098d9864b482d28e5ef8e657f43","url":"https://api.github.com/users/alexcrichton","html_url":"https://github.com/alexcrichton","followers_url":"https://api.github.com/users/alexcrichton/followers","following_url":"https://api.github.com/users/alexcrichton/following{/other_user}","gists_url":"https://api.github.com/users/alexcrichton/gists{/gist_id}","starred_url":"https://api.github.com/users/alexcrichton/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexcrichton/subscriptions","organizations_url":"https://api.github.com/users/alexcrichton/orgs","repos_url":"https://api.github.com/users/alexcrichton/repos","events_url":"https://api.github.com/users/alexcrichton/events{/privacy}","received_events_url":"https://api.github.com/users/alexcrichton/received_events","type":"User","site_admin":false},"body":"This should assert that it didn't underflow.\r\n\r\nAlso, `fetch_sub(1 << QUEUE_OFFSET)`","created_at":"2014-01-14T21:03:34Z","updated_at":"2014-01-14T21:03:34Z","html_url":"https://github.com/mozilla/rust/pull/11520#discussion_r8875874","pull_request_url":"https://api.github.com/repos/mozilla/rust/pulls/11520","_links":{"self":{"href":"https://api.github.com/repos/mozilla/rust/pulls/comments/8875874"},"html":{"href":"https://github.com/mozilla/rust/pull/11520#discussion_r8875874"},"pull_request":{"href":"https://api.github.com/repos/mozilla/rust/pulls/11520"}}}}