src/liballoc/arc.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 #![stable]
  12
  13 //! Concurrency-enabled mechanisms for sharing mutable and/or immutable state
  14 //! between tasks.
  15
  16 use core::atomic;
  17 use core::clone::Clone;
  18 use core::fmt::{mod, Show};
  19 use core::cmp::{Eq, Ord, PartialEq, PartialOrd, Ordering};
  20 use core::default::Default;
  21 use core::kinds::{Sync, Send};
  22 use core::mem::{min_align_of, size_of, drop};
  23 use core::mem;
  24 use core::ops::{Drop, Deref};
  25 use core::option::Option;
  26 use core::option::Option::{Some, None};
  27 use core::ptr::RawPtr;
  28 use core::ptr;
  29 use heap::deallocate;
  30
  31 /// An atomically reference counted wrapper for shared state.
  32 ///
  33 /// # Example
  34 ///
  35 /// In this example, a large vector of floats is shared between several tasks.
  36 /// With simple pipes, without `Arc`, a copy would have to be made for each
  37 /// task.
  38 ///
  39 /// ```rust
  40 /// use std::sync::Arc;
  41 ///
  42 /// fn main() {
  43 ///     let numbers = Vec::from_fn(100, |i| i as f32);
  44 ///     let shared_numbers = Arc::new(numbers);
  45 ///
  46 ///     for _ in range(0u, 10) {
  47 ///         let child_numbers = shared_numbers.clone();
  48 ///
  49 ///         spawn(proc() {
  50 ///             let local_numbers = child_numbers.as_slice();
  51 ///
  52 ///             // Work with the local numbers
  53 ///         });
  54 ///     }
  55 /// }
  56 /// ```
  57 #[unsafe_no_drop_flag]
  58 #[stable]
  59 pub struct Arc<T> {
  60     // FIXME #12808: strange name to try to avoid interfering with
  61     // field accesses of the contained type via Deref
  62     _ptr: *mut ArcInner<T>,
  63 }
  64
  65 /// A weak pointer to an `Arc`.
  66 ///
  67 /// Weak pointers will not keep the data inside of the `Arc` alive, and can be
  68 /// used to break cycles between `Arc` pointers.
  69 #[unsafe_no_drop_flag]
  70 #[experimental = "Weak pointers may not belong in this module."]
  71 pub struct Weak<T> {
  72     // FIXME #12808: strange name to try to avoid interfering with
  73     // field accesses of the contained type via Deref
  74     _ptr: *mut ArcInner<T>,
  75 }
  76
  77 struct ArcInner<T> {
  78     strong: atomic::AtomicUint,
  79     weak: atomic::AtomicUint,
  80     data: T,
  81 }
  82
  83 impl<T: Sync + Send> Arc<T> {
  84     /// Creates an atomically reference counted wrapper.
  85     #[inline]
  86     #[stable]
  87     pub fn new(data: T) -> Arc<T> {
  88         // Start the weak pointer count as 1 which is the weak pointer that's
  89         // held by all the strong pointers (kinda), see std/rc.rs for more info
  90         let x = box ArcInner {
  91             strong: atomic::AtomicUint::new(1),
  92             weak: atomic::AtomicUint::new(1),
  93             data: data,
  94         };
  95         Arc { _ptr: unsafe { mem::transmute(x) } }
  96     }
  97
  98     /// Downgrades a strong pointer to a weak pointer.
  99     ///
 100     /// Weak pointers will not keep the data alive. Once all strong references
 101     /// to the underlying data have been dropped, the data itself will be
 102     /// destroyed.
 103     #[experimental = "Weak pointers may not belong in this module."]
 104     pub fn downgrade(&self) -> Weak<T> {
 105         // See the clone() impl for why this is relaxed
 106         self.inner().weak.fetch_add(1, atomic::Relaxed);
 107         Weak { _ptr: self._ptr }
 108     }
 109 }
 110
 111 impl<T> Arc<T> {
 112     #[inline]
 113     fn inner(&self) -> &ArcInner<T> {
 114         // This unsafety is ok because while this arc is alive we're guaranteed
 115         // that the inner pointer is valid. Furthermore, we know that the
 116         // `ArcInner` structure itself is `Sync` because the inner data is
 117         // `Sync` as well, so we're ok loaning out an immutable pointer to
 118         // these contents.
 119         unsafe { &*self._ptr }
 120     }
 121 }
 122
 123 /// Get the number of weak references to this value.
 124 #[inline]
 125 #[experimental]
 126 pub fn weak_count<T>(this: &Arc<T>) -> uint { this.inner().weak.load(atomic::SeqCst) - 1 }
 127
 128 /// Get the number of strong references to this value.
 129 #[inline]
 130 #[experimental]
 131 pub fn strong_count<T>(this: &Arc<T>) -> uint { this.inner().strong.load(atomic::SeqCst) }
 132
 133 #[unstable = "waiting on stability of Clone"]
 134 impl<T> Clone for Arc<T> {
 135     /// Duplicate an atomically reference counted wrapper.
 136     ///
 137     /// The resulting two `Arc` objects will point to the same underlying data
 138     /// object. However, one of the `Arc` objects can be sent to another task,
 139     /// allowing them to share the underlying data.
 140     #[inline]
 141     fn clone(&self) -> Arc<T> {
 142         // Using a relaxed ordering is alright here, as knowledge of the
 143         // original reference prevents other threads from erroneously deleting
 144         // the object.
 145         //
 146         // As explained in the [Boost documentation][1], Increasing the
 147         // reference counter can always be done with memory_order_relaxed: New
 148         // references to an object can only be formed from an existing
 149         // reference, and passing an existing reference from one thread to
 150         // another must already provide any required synchronization.
 151         //
 152         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 153         self.inner().strong.fetch_add(1, atomic::Relaxed);
 154         Arc { _ptr: self._ptr }
 155     }
 156 }
 157
 158 #[experimental = "Deref is experimental."]
 159 impl<T> Deref<T> for Arc<T> {
 160     #[inline]
 161     fn deref(&self) -> &T {
 162         &self.inner().data
 163     }
 164 }
 165
 166 impl<T: Send + Sync + Clone> Arc<T> {
 167     /// Acquires a mutable pointer to the inner contents by guaranteeing that
 168     /// the reference count is one (no sharing is possible).
 169     ///
 170     /// This is also referred to as a copy-on-write operation because the inner
 171     /// data is cloned if the reference count is greater than one.
 172     #[inline]
 173     #[experimental]
 174     pub fn make_unique(&mut self) -> &mut T {
 175         // Note that we hold a strong reference, which also counts as
 176         // a weak reference, so we only clone if there is an
 177         // additional reference of either kind.
 178         if self.inner().strong.load(atomic::SeqCst) != 1 ||
 179            self.inner().weak.load(atomic::SeqCst) != 1 {
 180             *self = Arc::new((**self).clone())
 181         }
 182         // This unsafety is ok because we're guaranteed that the pointer
 183         // returned is the *only* pointer that will ever be returned to T. Our
 184         // reference count is guaranteed to be 1 at this point, and we required
 185         // the Arc itself to be `mut`, so we're returning the only possible
 186         // reference to the inner data.
 187         let inner = unsafe { &mut *self._ptr };
 188         &mut inner.data
 189     }
 190 }
 191
 192 #[unsafe_destructor]
 193 #[experimental = "waiting on stability of Drop"]
 194 impl<T: Sync + Send> Drop for Arc<T> {
 195     fn drop(&mut self) {
 196         // This structure has #[unsafe_no_drop_flag], so this drop glue may run
 197         // more than once (but it is guaranteed to be zeroed after the first if
 198         // it's run more than once)
 199         if self._ptr.is_null() { return }
 200
 201         // Because `fetch_sub` is already atomic, we do not need to synchronize
 202         // with other threads unless we are going to delete the object. This
 203         // same logic applies to the below `fetch_sub` to the `weak` count.
 204         if self.inner().strong.fetch_sub(1, atomic::Release) != 1 { return }
 205
 206         // This fence is needed to prevent reordering of use of the data and
 207         // deletion of the data. Because it is marked `Release`, the
 208         // decreasing of the reference count synchronizes with this `Acquire`
 209         // fence. This means that use of the data happens before decreasing
 210         // the reference count, which happens before this fence, which
 211         // happens before the deletion of the data.
 212         //
 213         // As explained in the [Boost documentation][1],
 214         //
 215         // It is important to enforce any possible access to the object in
 216         // one thread (through an existing reference) to *happen before*
 217         // deleting the object in a different thread. This is achieved by a
 218         // "release" operation after dropping a reference (any access to the
 219         // object through this reference must obviously happened before),
 220         // and an "acquire" operation before deleting the object.
 221         //
 222         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 223         atomic::fence(atomic::Acquire);
 224
 225         // Destroy the data at this time, even though we may not free the box
 226         // allocation itself (there may still be weak pointers lying around).
 227         unsafe { drop(ptr::read(&self.inner().data)); }
 228
 229         if self.inner().weak.fetch_sub(1, atomic::Release) == 1 {
 230             atomic::fence(atomic::Acquire);
 231             unsafe { deallocate(self._ptr as *mut u8, size_of::<ArcInner<T>>(),
 232                                 min_align_of::<ArcInner<T>>()) }
 233         }
 234     }
 235 }
 236
 237 #[experimental = "Weak pointers may not belong in this module."]
 238 impl<T: Sync + Send> Weak<T> {
 239     /// Attempts to upgrade this weak reference to a strong reference.
 240     ///
 241     /// This method will not upgrade this reference if the strong reference count has already
 242     /// reached 0, but if there are still other active strong references this function will return
 243     /// a new strong reference to the data.
 244     pub fn upgrade(&self) -> Option<Arc<T>> {
 245         // We use a CAS loop to increment the strong count instead of a
 246         // fetch_add because once the count hits 0 is must never be above 0.
 247         let inner = self.inner();
 248         loop {
 249             let n = inner.strong.load(atomic::SeqCst);
 250             if n == 0 { return None }
 251             let old = inner.strong.compare_and_swap(n, n + 1, atomic::SeqCst);
 252             if old == n { return Some(Arc { _ptr: self._ptr }) }
 253         }
 254     }
 255
 256     #[inline]
 257     fn inner(&self) -> &ArcInner<T> {
 258         // See comments above for why this is "safe"
 259         unsafe { &*self._ptr }
 260     }
 261 }
 262
 263 #[experimental = "Weak pointers may not belong in this module."]
 264 impl<T: Sync + Send> Clone for Weak<T> {
 265     #[inline]
 266     fn clone(&self) -> Weak<T> {
 267         // See comments in Arc::clone() for why this is relaxed
 268         self.inner().weak.fetch_add(1, atomic::Relaxed);
 269         Weak { _ptr: self._ptr }
 270     }
 271 }
 272
 273 #[unsafe_destructor]
 274 #[experimental = "Weak pointers may not belong in this module."]
 275 impl<T: Sync + Send> Drop for Weak<T> {
 276     fn drop(&mut self) {
 277         // see comments above for why this check is here
 278         if self._ptr.is_null() { return }
 279
 280         // If we find out that we were the last weak pointer, then its time to
 281         // deallocate the data entirely. See the discussion in Arc::drop() about
 282         // the memory orderings
 283         if self.inner().weak.fetch_sub(1, atomic::Release) == 1 {
 284             atomic::fence(atomic::Acquire);
 285             unsafe { deallocate(self._ptr as *mut u8, size_of::<ArcInner<T>>(),
 286                                 min_align_of::<ArcInner<T>>()) }
 287         }
 288     }
 289 }
 290
 291 #[unstable = "waiting on PartialEq"]
 292 impl<T: PartialEq> PartialEq for Arc<T> {
 293     fn eq(&self, other: &Arc<T>) -> bool { *(*self) == *(*other) }
 294     fn ne(&self, other: &Arc<T>) -> bool { *(*self) != *(*other) }
 295 }
 296 #[unstable = "waiting on PartialOrd"]
 297 impl<T: PartialOrd> PartialOrd for Arc<T> {
 298     fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
 299         (**self).partial_cmp(&**other)
 300     }
 301     fn lt(&self, other: &Arc<T>) -> bool { *(*self) < *(*other) }
 302     fn le(&self, other: &Arc<T>) -> bool { *(*self) <= *(*other) }
 303     fn ge(&self, other: &Arc<T>) -> bool { *(*self) >= *(*other) }
 304     fn gt(&self, other: &Arc<T>) -> bool { *(*self) > *(*other) }
 305 }
 306 #[unstable = "waiting on Ord"]
 307 impl<T: Ord> Ord for Arc<T> {
 308     fn cmp(&self, other: &Arc<T>) -> Ordering { (**self).cmp(&**other) }
 309 }
 310 #[unstable = "waiting on Eq"]
 311 impl<T: Eq> Eq for Arc<T> {}
 312
 313 impl<T: fmt::Show> fmt::Show for Arc<T> {
 314     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 315         (**self).fmt(f)
 316     }
 317 }
 318
 319 impl<T: Default + Sync + Send> Default for Arc<T> {
 320     fn default() -> Arc<T> { Arc::new(Default::default()) }
 321 }
 322
 323 #[cfg(test)]
 324 #[allow(experimental)]
 325 mod tests {
 326     use std::clone::Clone;
 327     use std::comm::channel;
 328     use std::mem::drop;
 329     use std::ops::Drop;
 330     use std::option::Option;
 331     use std::option::Option::{Some, None};
 332     use std::str::Str;
 333     use std::sync::atomic;
 334     use std::task;
 335     use std::vec::Vec;
 336     use super::{Arc, Weak, weak_count, strong_count};
 337     use std::sync::Mutex;
 338
 339     struct Canary(*mut atomic::AtomicUint);
 340
 341     impl Drop for Canary
 342     {
 343         fn drop(&mut self) {
 344             unsafe {
 345                 match *self {
 346                     Canary(c) => {
 347                         (*c).fetch_add(1, atomic::SeqCst);
 348                     }
 349                 }
 350             }
 351         }
 352     }
 353
 354     #[test]
 355     fn manually_share_arc() {
 356         let v = vec!(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
 357         let arc_v = Arc::new(v);
 358
 359         let (tx, rx) = channel();
 360
 361         task::spawn(proc() {
 362             let arc_v: Arc<Vec<int>> = rx.recv();
 363             assert_eq!((*arc_v)[3], 4);
 364         });
 365
 366         tx.send(arc_v.clone());
 367
 368         assert_eq!((*arc_v)[2], 3);
 369         assert_eq!((*arc_v)[4], 5);
 370     }
 371
 372     #[test]
 373     fn test_cowarc_clone_make_unique() {
 374         let mut cow0 = Arc::new(75u);
 375         let mut cow1 = cow0.clone();
 376         let mut cow2 = cow1.clone();
 377
 378         assert!(75 == *cow0.make_unique());
 379         assert!(75 == *cow1.make_unique());
 380         assert!(75 == *cow2.make_unique());
 381
 382         *cow0.make_unique() += 1;
 383         *cow1.make_unique() += 2;
 384         *cow2.make_unique() += 3;
 385
 386         assert!(76 == *cow0);
 387         assert!(77 == *cow1);
 388         assert!(78 == *cow2);
 389
 390         // none should point to the same backing memory
 391         assert!(*cow0 != *cow1);
 392         assert!(*cow0 != *cow2);
 393         assert!(*cow1 != *cow2);
 394     }
 395
 396     #[test]
 397     fn test_cowarc_clone_unique2() {
 398         let mut cow0 = Arc::new(75u);
 399         let cow1 = cow0.clone();
 400         let cow2 = cow1.clone();
 401
 402         assert!(75 == *cow0);
 403         assert!(75 == *cow1);
 404         assert!(75 == *cow2);
 405
 406         *cow0.make_unique() += 1;
 407
 408         assert!(76 == *cow0);
 409         assert!(75 == *cow1);
 410         assert!(75 == *cow2);
 411
 412         // cow1 and cow2 should share the same contents
 413         // cow0 should have a unique reference
 414         assert!(*cow0 != *cow1);
 415         assert!(*cow0 != *cow2);
 416         assert!(*cow1 == *cow2);
 417     }
 418
 419     #[test]
 420     fn test_cowarc_clone_weak() {
 421         let mut cow0 = Arc::new(75u);
 422         let cow1_weak = cow0.downgrade();
 423
 424         assert!(75 == *cow0);
 425         assert!(75 == *cow1_weak.upgrade().unwrap());
 426
 427         *cow0.make_unique() += 1;
 428
 429         assert!(76 == *cow0);
 430         assert!(cow1_weak.upgrade().is_none());
 431     }
 432
 433     #[test]
 434     fn test_live() {
 435         let x = Arc::new(5i);
 436         let y = x.downgrade();
 437         assert!(y.upgrade().is_some());
 438     }
 439
 440     #[test]
 441     fn test_dead() {
 442         let x = Arc::new(5i);
 443         let y = x.downgrade();
 444         drop(x);
 445         assert!(y.upgrade().is_none());
 446     }
 447
 448     #[test]
 449     fn weak_self_cyclic() {
 450         struct Cycle {
 451             x: Mutex<Option<Weak<Cycle>>>
 452         }
 453
 454         let a = Arc::new(Cycle { x: Mutex::new(None) });
 455         let b = a.clone().downgrade();
 456         *a.x.lock() = Some(b);
 457
 458         // hopefully we don't double-free (or leak)...
 459     }
 460
 461     #[test]
 462     fn drop_arc() {
 463         let mut canary = atomic::AtomicUint::new(0);
 464         let x = Arc::new(Canary(&mut canary as *mut atomic::AtomicUint));
 465         drop(x);
 466         assert!(canary.load(atomic::Acquire) == 1);
 467     }
 468
 469     #[test]
 470     fn drop_arc_weak() {
 471         let mut canary = atomic::AtomicUint::new(0);
 472         let arc = Arc::new(Canary(&mut canary as *mut atomic::AtomicUint));
 473         let arc_weak = arc.downgrade();
 474         assert!(canary.load(atomic::Acquire) == 0);
 475         drop(arc);
 476         assert!(canary.load(atomic::Acquire) == 1);
 477         drop(arc_weak);
 478     }
 479
 480     #[test]
 481     fn test_strong_count() {
 482         let a = Arc::new(0u32);
 483         assert!(strong_count(&a) == 1);
 484         let w = a.downgrade();
 485         assert!(strong_count(&a) == 1);
 486         let b = w.upgrade().expect("");
 487         assert!(strong_count(&b) == 2);
 488         assert!(strong_count(&a) == 2);
 489         drop(w);
 490         drop(a);
 491         assert!(strong_count(&b) == 1);
 492         let c = b.clone();
 493         assert!(strong_count(&b) == 2);
 494         assert!(strong_count(&c) == 2);
 495     }
 496
 497     #[test]
 498     fn test_weak_count() {
 499         let a = Arc::new(0u32);
 500         assert!(strong_count(&a) == 1);
 501         assert!(weak_count(&a) == 0);
 502         let w = a.downgrade();
 503         assert!(strong_count(&a) == 1);
 504         assert!(weak_count(&a) == 1);
 505         let x = w.clone();
 506         assert!(weak_count(&a) == 2);
 507         drop(w);
 508         drop(x);
 509         assert!(strong_count(&a) == 1);
 510         assert!(weak_count(&a) == 0);
 511         let c = a.clone();
 512         assert!(strong_count(&a) == 2);
 513         assert!(weak_count(&a) == 0);
 514         let d = c.downgrade();
 515         assert!(weak_count(&c) == 1);
 516         assert!(strong_count(&c) == 2);
 517
 518         drop(a);
 519         drop(c);
 520         drop(d);
 521     }
 522
 523     #[test]
 524     fn show_arc() {
 525         let a = Arc::new(5u32);
 526         assert!(format!("{}", a) == "5")
 527     }
 528
 529     // Make sure deriving works with Arc<T>
 530     #[deriving(Eq, Ord, PartialEq, PartialOrd, Clone, Show, Default)]
 531     struct Foo { inner: Arc<int> }
 532 }