1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289
//! # `conc` — An efficient concurrent reclamation system //! //! `conc` builds upon hazard pointers to create a extremely performant system for concurrently //! handling memory. It is a general, convenient, memory light — and sometimes faster — alternative //! to epoch-based reclamation (see the trade-off section). //! //! ## Overview //! //! - **High-level API** //! * `Atomic<T>` for an lockless readable and writable container. //! * `sync` for basic datastructures implemented through `conc`. //! - `Treiber<T>` for concurrent stacks. //! - `Stm<T>` for a simple implementation of STM. //! - **Low-level API** //! * `add_garbage()` for queuing destruction of garbage. //! * `Guard<T>` for blocking destruction. //! - **Runtime control** //! * `gc()` for collecting garbage to reduce memory. //! * `settings` for reconfiguring the system on-the-go. //! //! ## Why? //! //! aturon's [blog post](https://aturon.github.io/blog/2015/08/27/epoch/) explains the issues of //! concurrent memory handling very well, although it take basis in epoch-based reclamation, which //! this crate is an alternative for. //! //! The gist essentially is that you need to delete objects in most concurrent data structure //! (otherwise there would be memory leaks), however cannot safely do so, as there is no way to //! know if another thread is accessing the object in question. This (and other reclamation //! systems) provides a solution to this problem. //! //! ## Usage //! //! While the low-level API is available, it is generally sufficient to use the `conc::Atomic<T>` //! abstraction. This acts much like familiar Rust APIs. It allows the programmer to concurrently //! access a value through references, as well as update it, and more. Refer to the respective docs //! for more information. //! //! If you are interested in implementing your own structures with `conc`, you must learn how to //! use `Guard<T>` and `add_garbage`. In short, //! //! - `conc::add_garbage()` adds a destructor with a pointer, which will be run eventually, when no //! one is reading the data anymore. In other words, it acts as a concurrent counterpart to //! `Drop::drop()`. //! - `Guard<T>` "protects" a pointer from being destroyed. That is, it delays destruction (which //! is planned by `conc::add_garbage()`) until the guard is gone. //! //! See their respective API docs for details on usage and behavior. //! //! ### Debugging //! //! Enable feature `debug-tools` and set environment variable `CONC_DEBUG_MODE`. For example, //! `CONC_DEBUG_MODE=1 cargo test --features debug-tools`. To get stacktraces after each message, //! set environment variable `CONC_DEBUG_STACKTRACE`. //! //! ### Examples //! //! See the [`sync` source code](https://github.com/redox-os/tfs/tree/master/conc/src/sync). //! //! ## Tradeoffs - Why not crossbeam/epochs? //! //! Epochs (EBR) are generally faster than this crate, however the major advantage this has over //! epochs is that this doesn't suffer from memory blow-up in intense cases. //! //! The issue with most other and faster solutions is that, if there is a non-trivial amount of //! threads (say 16) constantly reading/storing some pointer, it will never get to a state, where //! it can be reclaimed. //! //! In other words, given sufficient amount of threads and frequency, the gaps between the //! reclamation might be very very long, causing very high memory usage, and potentially OOM //! crashes. //! //! These issues are not hypothetical. It happened to me while testing the caching system of TFS. //! Essentially, the to-be-destroyed garbage accumulated several gigabytes, without ever being open //! to a collection cycle. //! //! It reminds of the MongoDB debate. It might very well be the fastest solution¹, but if it can't //! even ensure consistency in these cases, what is the point? //! //! That being said, there are cases where the other libraries are perfectly fine (e.g. if you have //! a bounded number of thread and a medium-long interval between accesses) and also faster. //! //! ¹If you want a super fast memory reclamation system, you should try NOP™, and not calling //! destructors. //! //! ### Other advantages //! //! - The API of `conc` is - by design - more lightweight interface-wise, as it doesn't require the //! call side to pin epochs or similar. This is particularly nice when you design more //! complicated structures. //! - `conc` objects (`Guard<T>`) is not bound to a lifetime or similar, meaning that it is //! `future-rs` compatible among other. //! - In `conc`, threads can export garbage while there are active objects, meaning that memory //! won't accumulate on non-stopping usage. //! - `conc` is runtime configurable through the `settings` module. //! - Better debugging tools. //! - More-well tested and well-documented. //! - More fine-grained control over the runtime. //! - Access to low-level API. //! //! ### Disadvantages //! //! - In many cases, it is slower. //! - Fewer pre-implemented data structures (for now). //! //! ## Design & internals //! //! It based on hazard pointers, although there are several differences. The idea is essentially //! that the system keeps track of some number of "hazards". As long as a hazard protects some //! object, the object cannot be deleted. //! //! Once in a while, a thread performs a garbage collection by scanning the hazards and finding the //! objects not currently protected by any hazard. These objects are then deleted. //! //! To improve performance, we use a layered approach: Both garbage (objects to be deleted //! eventually) and hazards are cached thread locally. This reduces the amount of atomic operations //! and cache misses. //! //! For more details, see [this blog //! post](https://ticki.github.io/blog/fearless-concurrency-with-hazard-pointers/). //! //! ## Garbage collection //! //! Garbage collection of the concurrently managed object is done automatically between every `n` //! frees where `n` is chosen from some probability distribution. //! //! Note that a garbage collection cycle might not clear all objects. For example, some objects //! could be protected by hazards. Others might not have been exported from the thread-local cache //! yet. //! //! ## Performance //! //! It is worth noting that atomic reads through this library usually requires three atomic CPU //! instruction, this means that if you are traversing a list or something like that, this library //! might not be for you. //! //! ## Settings //! //! You can reconfigure the system on-the-go through the `settings` module. //! //! There are also presets. For example, if you experience high memory usage, you can do: //! //! ```rust //! conc::settings::set_local(conc::settings::Settings::low_memory()); //! ``` #![feature(thread_local_state, const_fn)] #![deny(missing_docs)] #[macro_use] extern crate lazy_static; extern crate rand; extern crate spin; mod atomic; mod debug; mod garbage; mod global; mod guard; mod hazard; mod local; mod mpsc; pub mod settings; pub mod sync; pub use atomic::Atomic; pub use guard::Guard; use std::mem; use garbage::Garbage; /// Attempt to collect garbage. /// /// This function does two things: /// /// 1. Export garbage from current thread to the global queue. /// 2. Collect all the garbage and run destructors on the unused items. /// /// If another thread is currently doing 2., it will be skipped. This makes it different from /// `conc::gc()`, which will block. /// /// If 2. fails (that is, another thread is garbage collecting), `Err(())` is returned. Otherwise /// `Ok(())` is returned. /// /// # Use case /// /// Note that it is not necessary to call this manually, it will do so automatically after some /// time has passed. /// /// However, it can be nice if you have just trashed a very memory-hungry item in the current /// thread, and want to attempt to GC it. /// /// # Other threads /// /// This cannot collect un-propagated garbage accumulated locally in other threads. This will only /// attempt to collect the accumulated local and global (propagated) garbage. /// /// # Panic /// /// If a destructor panics during the garbage collection, theis function will panic aswell. pub fn try_gc() -> Result<(), ()> { // Export the local garbage to ensure that the garbage of the current thread gets collected. local::export_garbage(); // Run the global GC. global::try_gc() } /// Collect garbage. /// /// This function does two things: /// /// 1. Export garbage from current thread to the global queue. /// 2. Collect all the garbage and run destructors on the unused items. /// /// If another thread is currently doing 2., it will block until it can be done. This makes it /// different from `conc::try_gc()`, which will skip the step. /// /// # Use case /// /// This is really only neccesary in one case: If you want to ensure that all the destructors of /// inactive hazards in the current thread are run. If the destructors hold some special logic, you /// want to execute, this will force the (inactive) ones to run these destructors and thus execute /// the logic. /// /// If you just want to reduce memory usage, you will probably be better off with `conc::try_gc()`. /// /// # Other threads /// /// This cannot collect un-propagated garbage accumulated locally in other threads. This will only /// collect the accumulated local and global (propagated) garbage. /// /// # Panic /// /// If a destructor panics during the garbage collection, theis function will panic aswell. pub fn gc() { // Export the local garbage to ensure that the garbage of the current thread gets collected. local::export_garbage(); // Try to garbage collect until it succeeds. while let Err(()) = global::try_gc() {} } /// Declare a pointer unreachable garbage to be deleted eventually. /// /// This adds `ptr` to the queue of garbage, which eventually will be destroyed through its /// destructor given in `dtor`. This is ensured to happen at some point _after_ the last guard /// protecting the pointer is dropped. /// /// It is legal for `ptr` to be invalidated by `dtor`, such that accessing it is undefined after /// `dtor` has been run. This means that `dtor` can safely (there are exceptions, see below) run a /// destructor of `ptr`'s data. /// /// # Unreachability criterion /// /// If you invalidate `ptr` in the destructor, it is extremely important that `ptr` is no longer /// reachable from any data structure: It should be impossible to create _new_ guard representing /// `ptr` from now on, as such thing can mean that new guards can be created after it is dropped /// causing use-after-free. /// /// # Constraints /// /// The `T: Sync` constraint is added to account for the fact that `dtor` might be called in /// another thread, meaning that it could cause thread-insafety if the pointer couldn't be shared. /// /// # Destruction /// /// If the destructor provided panics under execution, it will cause panic in the garbage /// collection, and the destructor won't run again. pub fn add_garbage<T: Sync>(ptr: &'static T, dtor: fn(&'static T)) { local::add_garbage(unsafe { Garbage::new(ptr as *const T as *const u8 as *mut u8, mem::transmute(dtor)) }); } /// Add a heap-allocated `Box<T>` as garbage. /// /// This adds a `Box<T>` represented by pointer `ptr` to the to-be-destroyed garbage queue. /// /// For more details, see `add_garbage`, which this method is a specialization of. /// /// # Safety /// /// This is unsafe as the pointer could be aliased or invalid. To satisfy invariants, the pointer /// shall be a valid object, allocated through `Box::new(x)` or alike, and shall only be used as /// long as there are hazard protecting it. pub unsafe fn add_garbage_box<T>(ptr: *const T) { local::add_garbage( Garbage::new_box(ptr) ); }