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(feature = "rust1", since = "1.0.0")]
  12
  13 //! Thread-safe reference-counting pointers.
  14 //!
  15 //! See the [`Arc<T>`][arc] documentation for more details.
  16 //!
  17 //! [arc]: struct.Arc.html
  18
  19 use boxed::Box;
  20
  21 use core::sync::atomic;
  22 use core::sync::atomic::Ordering::{Acquire, Relaxed, Release, SeqCst};
  23 use core::borrow;
  24 use core::fmt;
  25 use core::cmp::Ordering;
  26 use core::intrinsics::abort;
  27 use core::mem;
  28 use core::mem::uninitialized;
  29 use core::ops::Deref;
  30 use core::ops::CoerceUnsized;
  31 use core::ptr::{self, Shared};
  32 use core::marker::Unsize;
  33 use core::hash::{Hash, Hasher};
  34 use core::{isize, usize};
  35 use core::convert::From;
  36
  37 use heap::{Heap, Alloc, Layout};
  38
  39 /// A soft limit on the amount of references that may be made to an `Arc`.
  40 ///
  41 /// Going above this limit will abort your program (although not
  42 /// necessarily) at _exactly_ `MAX_REFCOUNT + 1` references.
  43 const MAX_REFCOUNT: usize = (isize::MAX) as usize;
  44
  45 /// A thread-safe reference-counting pointer. 'Arc' stands for 'Atomically
  46 /// Reference Counted'.
  47 ///
  48 /// The type `Arc<T>` provides shared ownership of a value of type `T`,
  49 /// allocated in the heap. Invoking [`clone`][clone] on `Arc` produces
  50 /// a new pointer to the same value in the heap. When the last `Arc`
  51 /// pointer to a given value is destroyed, the pointed-to value is
  52 /// also destroyed.
  53 ///
  54 /// Shared references in Rust disallow mutation by default, and `Arc` is no
  55 /// exception. If you need to mutate through an `Arc`, use [`Mutex`][mutex],
  56 /// [`RwLock`][rwlock], or one of the [`Atomic`][atomic] types.
  57 ///
  58 /// ## Thread Safety
  59 ///
  60 /// Unlike [`Rc<T>`], `Arc<T>` uses atomic operations for its reference
  61 /// counting  This means that it is thread-safe. The disadvantage is that
  62 /// atomic operations are more expensive than ordinary memory accesses. If you
  63 /// are not sharing reference-counted values between threads, consider using
  64 /// [`Rc<T>`] for lower overhead. [`Rc<T>`] is a safe default, because the
  65 /// compiler will catch any attempt to send an [`Rc<T>`] between threads.
  66 /// However, a library might choose `Arc<T>` in order to give library consumers
  67 /// more flexibility.
  68 ///
  69 /// `Arc<T>` will implement [`Send`] and [`Sync`] as long as the `T` implements
  70 /// [`Send`] and [`Sync`]. Why can't you put a non-thread-safe type `T` in an
  71 /// `Arc<T>` to make it thread-safe? This may be a bit counter-intuitive at
  72 /// first: after all, isn't the point of `Arc<T>` thread safety? The key is
  73 /// this: `Arc<T>` makes it thread safe to have multiple ownership of the same
  74 /// data, but it  doesn't add thread safety to its data. Consider
  75 /// `Arc<RefCell<T>>`. `RefCell<T>` isn't [`Sync`], and if `Arc<T>` was always
  76 /// [`Send`], `Arc<RefCell<T>>` would be as well. But then we'd have a problem:
  77 /// `RefCell<T>` is not thread safe; it keeps track of the borrowing count using
  78 /// non-atomic operations.
  79 ///
  80 /// In the end, this means that you may need to pair `Arc<T>` with some sort of
  81 /// `std::sync` type, usually `Mutex<T>`.
  82 ///
  83 /// ## Breaking cycles with `Weak`
  84 ///
  85 /// The [`downgrade`][downgrade] method can be used to create a non-owning
  86 /// [`Weak`][weak] pointer. A [`Weak`][weak] pointer can be [`upgrade`][upgrade]d
  87 /// to an `Arc`, but this will return [`None`] if the value has already been
  88 /// dropped.
  89 ///
  90 /// A cycle between `Arc` pointers will never be deallocated. For this reason,
  91 /// [`Weak`][weak] is used to break cycles. For example, a tree could have
  92 /// strong `Arc` pointers from parent nodes to children, and [`Weak`][weak]
  93 /// pointers from children back to their parents.
  94 ///
  95 /// # Cloning references
  96 ///
  97 /// Creating a new reference from an existing reference counted pointer is done using the
  98 /// `Clone` trait implemented for [`Arc<T>`][arc] and [`Weak<T>`][weak].
  99 ///
 100 /// ```
 101 /// use std::sync::Arc;
 102 /// let foo = Arc::new(vec![1.0, 2.0, 3.0]);
 103 /// // The two syntaxes below are equivalent.
 104 /// let a = foo.clone();
 105 /// let b = Arc::clone(&foo);
 106 /// // a and b both point to the same memory location as foo.
 107 /// ```
 108 ///
 109 /// The `Arc::clone(&from)` syntax is the most idiomatic because it conveys more explicitly
 110 /// the meaning of the code. In the example above, this syntax makes it easier to see that
 111 /// this code is creating a new reference rather than copying the whole content of foo.
 112 ///
 113 /// ## `Deref` behavior
 114 ///
 115 /// `Arc<T>` automatically dereferences to `T` (via the [`Deref`][deref] trait),
 116 /// so you can call `T`'s methods on a value of type `Arc<T>`. To avoid name
 117 /// clashes with `T`'s methods, the methods of `Arc<T>` itself are [associated
 118 /// functions][assoc], called using function-like syntax:
 119 ///
 120 /// ```
 121 /// use std::sync::Arc;
 122 /// let my_arc = Arc::new(());
 123 ///
 124 /// Arc::downgrade(&my_arc);
 125 /// ```
 126 ///
 127 /// [`Weak<T>`][weak] does not auto-dereference to `T`, because the value may have
 128 /// already been destroyed.
 129 ///
 130 /// [arc]: struct.Arc.html
 131 /// [weak]: struct.Weak.html
 132 /// [`Rc<T>`]: ../../std/rc/struct.Rc.html
 133 /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 134 /// [mutex]: ../../std/sync/struct.Mutex.html
 135 /// [rwlock]: ../../std/sync/struct.RwLock.html
 136 /// [atomic]: ../../std/sync/atomic/index.html
 137 /// [`Send`]: ../../std/marker/trait.Send.html
 138 /// [`Sync`]: ../../std/marker/trait.Sync.html
 139 /// [deref]: ../../std/ops/trait.Deref.html
 140 /// [downgrade]: struct.Arc.html#method.downgrade
 141 /// [upgrade]: struct.Weak.html#method.upgrade
 142 /// [`None`]: ../../std/option/enum.Option.html#variant.None
 143 /// [assoc]: ../../book/first-edition/method-syntax.html#associated-functions
 144 ///
 145 /// # Examples
 146 ///
 147 /// Sharing some immutable data between threads:
 148 ///
 149 // Note that we **do not** run these tests here. The windows builders get super
 150 // unhappy if a thread outlives the main thread and then exits at the same time
 151 // (something deadlocks) so we just avoid this entirely by not running these
 152 // tests.
 153 /// ```no_run
 154 /// use std::sync::Arc;
 155 /// use std::thread;
 156 ///
 157 /// let five = Arc::new(5);
 158 ///
 159 /// for _ in 0..10 {
 160 ///     let five = Arc::clone(&five);
 161 ///
 162 ///     thread::spawn(move || {
 163 ///         println!("{:?}", five);
 164 ///     });
 165 /// }
 166 /// ```
 167 ///
 168 /// Sharing a mutable [`AtomicUsize`]:
 169 ///
 170 /// [`AtomicUsize`]: ../../std/sync/atomic/struct.AtomicUsize.html
 171 ///
 172 /// ```no_run
 173 /// use std::sync::Arc;
 174 /// use std::sync::atomic::{AtomicUsize, Ordering};
 175 /// use std::thread;
 176 ///
 177 /// let val = Arc::new(AtomicUsize::new(5));
 178 ///
 179 /// for _ in 0..10 {
 180 ///     let val = Arc::clone(&val);
 181 ///
 182 ///     thread::spawn(move || {
 183 ///         let v = val.fetch_add(1, Ordering::SeqCst);
 184 ///         println!("{:?}", v);
 185 ///     });
 186 /// }
 187 /// ```
 188 ///
 189 /// See the [`rc` documentation][rc_examples] for more examples of reference
 190 /// counting in general.
 191 ///
 192 /// [rc_examples]: ../../std/rc/index.html#examples
 193 #[stable(feature = "rust1", since = "1.0.0")]
 194 pub struct Arc<T: ?Sized> {
 195     ptr: Shared<ArcInner<T>>,
 196 }
 197
 198 #[stable(feature = "rust1", since = "1.0.0")]
 199 unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> {}
 200 #[stable(feature = "rust1", since = "1.0.0")]
 201 unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> {}
 202
 203 #[unstable(feature = "coerce_unsized", issue = "27732")]
 204 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Arc<U>> for Arc<T> {}
 205
 206 /// `Weak` is a version of [`Arc`] that holds a non-owning reference to the
 207 /// managed value. The value is accessed by calling [`upgrade`] on the `Weak`
 208 /// pointer, which returns an [`Option`]`<`[`Arc`]`<T>>`.
 209 ///
 210 /// Since a `Weak` reference does not count towards ownership, it will not
 211 /// prevent the inner value from being dropped, and `Weak` itself makes no
 212 /// guarantees about the value still being present and may return [`None`]
 213 /// when [`upgrade`]d.
 214 ///
 215 /// A `Weak` pointer is useful for keeping a temporary reference to the value
 216 /// within [`Arc`] without extending its lifetime. It is also used to prevent
 217 /// circular references between [`Arc`] pointers, since mutual owning references
 218 /// would never allow either [`Arc`] to be dropped. For example, a tree could
 219 /// have strong [`Arc`] pointers from parent nodes to children, and `Weak`
 220 /// pointers from children back to their parents.
 221 ///
 222 /// The typical way to obtain a `Weak` pointer is to call [`Arc::downgrade`].
 223 ///
 224 /// [`Arc`]: struct.Arc.html
 225 /// [`Arc::downgrade`]: struct.Arc.html#method.downgrade
 226 /// [`upgrade`]: struct.Weak.html#method.upgrade
 227 /// [`Option`]: ../../std/option/enum.Option.html
 228 /// [`None`]: ../../std/option/enum.Option.html#variant.None
 229 #[stable(feature = "arc_weak", since = "1.4.0")]
 230 pub struct Weak<T: ?Sized> {
 231     ptr: Shared<ArcInner<T>>,
 232 }
 233
 234 #[stable(feature = "arc_weak", since = "1.4.0")]
 235 unsafe impl<T: ?Sized + Sync + Send> Send for Weak<T> {}
 236 #[stable(feature = "arc_weak", since = "1.4.0")]
 237 unsafe impl<T: ?Sized + Sync + Send> Sync for Weak<T> {}
 238
 239 #[unstable(feature = "coerce_unsized", issue = "27732")]
 240 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Weak<U>> for Weak<T> {}
 241
 242 #[stable(feature = "arc_weak", since = "1.4.0")]
 243 impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
 244     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 245         write!(f, "(Weak)")
 246     }
 247 }
 248
 249 struct ArcInner<T: ?Sized> {
 250     strong: atomic::AtomicUsize,
 251
 252     // the value usize::MAX acts as a sentinel for temporarily "locking" the
 253     // ability to upgrade weak pointers or downgrade strong ones; this is used
 254     // to avoid races in `make_mut` and `get_mut`.
 255     weak: atomic::AtomicUsize,
 256
 257     data: T,
 258 }
 259
 260 unsafe impl<T: ?Sized + Sync + Send> Send for ArcInner<T> {}
 261 unsafe impl<T: ?Sized + Sync + Send> Sync for ArcInner<T> {}
 262
 263 impl<T> Arc<T> {
 264     /// Constructs a new `Arc<T>`.
 265     ///
 266     /// # Examples
 267     ///
 268     /// ```
 269     /// use std::sync::Arc;
 270     ///
 271     /// let five = Arc::new(5);
 272     /// ```
 273     #[inline]
 274     #[stable(feature = "rust1", since = "1.0.0")]
 275     pub fn new(data: T) -> Arc<T> {
 276         // Start the weak pointer count as 1 which is the weak pointer that's
 277         // held by all the strong pointers (kinda), see std/rc.rs for more info
 278         let x: Box<_> = box ArcInner {
 279             strong: atomic::AtomicUsize::new(1),
 280             weak: atomic::AtomicUsize::new(1),
 281             data: data,
 282         };
 283         Arc { ptr: Shared::from(Box::into_unique(x)) }
 284     }
 285
 286     /// Returns the contained value, if the `Arc` has exactly one strong reference.
 287     ///
 288     /// Otherwise, an [`Err`][result] is returned with the same `Arc` that was
 289     /// passed in.
 290     ///
 291     /// This will succeed even if there are outstanding weak references.
 292     ///
 293     /// [result]: ../../std/result/enum.Result.html
 294     ///
 295     /// # Examples
 296     ///
 297     /// ```
 298     /// use std::sync::Arc;
 299     ///
 300     /// let x = Arc::new(3);
 301     /// assert_eq!(Arc::try_unwrap(x), Ok(3));
 302     ///
 303     /// let x = Arc::new(4);
 304     /// let _y = Arc::clone(&x);
 305     /// assert_eq!(*Arc::try_unwrap(x).unwrap_err(), 4);
 306     /// ```
 307     #[inline]
 308     #[stable(feature = "arc_unique", since = "1.4.0")]
 309     pub fn try_unwrap(this: Self) -> Result<T, Self> {
 310         // See `drop` for why all these atomics are like this
 311         if this.inner().strong.compare_exchange(1, 0, Release, Relaxed).is_err() {
 312             return Err(this);
 313         }
 314
 315         atomic::fence(Acquire);
 316
 317         unsafe {
 318             let elem = ptr::read(&this.ptr.as_ref().data);
 319
 320             // Make a weak pointer to clean up the implicit strong-weak reference
 321             let _weak = Weak { ptr: this.ptr };
 322             mem::forget(this);
 323
 324             Ok(elem)
 325         }
 326     }
 327
 328     /// Consumes the `Arc`, returning the wrapped pointer.
 329     ///
 330     /// To avoid a memory leak the pointer must be converted back to an `Arc` using
 331     /// [`Arc::from_raw`][from_raw].
 332     ///
 333     /// [from_raw]: struct.Arc.html#method.from_raw
 334     ///
 335     /// # Examples
 336     ///
 337     /// ```
 338     /// use std::sync::Arc;
 339     ///
 340     /// let x = Arc::new(10);
 341     /// let x_ptr = Arc::into_raw(x);
 342     /// assert_eq!(unsafe { *x_ptr }, 10);
 343     /// ```
 344     #[stable(feature = "rc_raw", since = "1.17.0")]
 345     pub fn into_raw(this: Self) -> *const T {
 346         let ptr: *const T = &*this;
 347         mem::forget(this);
 348         ptr
 349     }
 350
 351     /// Constructs an `Arc` from a raw pointer.
 352     ///
 353     /// The raw pointer must have been previously returned by a call to a
 354     /// [`Arc::into_raw`][into_raw].
 355     ///
 356     /// This function is unsafe because improper use may lead to memory problems. For example, a
 357     /// double-free may occur if the function is called twice on the same raw pointer.
 358     ///
 359     /// [into_raw]: struct.Arc.html#method.into_raw
 360     ///
 361     /// # Examples
 362     ///
 363     /// ```
 364     /// use std::sync::Arc;
 365     ///
 366     /// let x = Arc::new(10);
 367     /// let x_ptr = Arc::into_raw(x);
 368     ///
 369     /// unsafe {
 370     ///     // Convert back to an `Arc` to prevent leak.
 371     ///     let x = Arc::from_raw(x_ptr);
 372     ///     assert_eq!(*x, 10);
 373     ///
 374     ///     // Further calls to `Arc::from_raw(x_ptr)` would be memory unsafe.
 375     /// }
 376     ///
 377     /// // The memory was freed when `x` went out of scope above, so `x_ptr` is now dangling!
 378     /// ```
 379     #[stable(feature = "rc_raw", since = "1.17.0")]
 380     pub unsafe fn from_raw(ptr: *const T) -> Self {
 381         // To find the corresponding pointer to the `ArcInner` we need to subtract the offset of the
 382         // `data` field from the pointer.
 383         let ptr = (ptr as *const u8).offset(-offset_of!(ArcInner<T>, data));
 384         Arc {
 385             ptr: Shared::new_unchecked(ptr as *mut u8 as *mut _),
 386         }
 387     }
 388 }
 389
 390 impl<T: ?Sized> Arc<T> {
 391     /// Creates a new [`Weak`][weak] pointer to this value.
 392     ///
 393     /// [weak]: struct.Weak.html
 394     ///
 395     /// # Examples
 396     ///
 397     /// ```
 398     /// use std::sync::Arc;
 399     ///
 400     /// let five = Arc::new(5);
 401     ///
 402     /// let weak_five = Arc::downgrade(&five);
 403     /// ```
 404     #[stable(feature = "arc_weak", since = "1.4.0")]
 405     pub fn downgrade(this: &Self) -> Weak<T> {
 406         // This Relaxed is OK because we're checking the value in the CAS
 407         // below.
 408         let mut cur = this.inner().weak.load(Relaxed);
 409
 410         loop {
 411             // check if the weak counter is currently "locked"; if so, spin.
 412             if cur == usize::MAX {
 413                 cur = this.inner().weak.load(Relaxed);
 414                 continue;
 415             }
 416
 417             // NOTE: this code currently ignores the possibility of overflow
 418             // into usize::MAX; in general both Rc and Arc need to be adjusted
 419             // to deal with overflow.
 420
 421             // Unlike with Clone(), we need this to be an Acquire read to
 422             // synchronize with the write coming from `is_unique`, so that the
 423             // events prior to that write happen before this read.
 424             match this.inner().weak.compare_exchange_weak(cur, cur + 1, Acquire, Relaxed) {
 425                 Ok(_) => return Weak { ptr: this.ptr },
 426                 Err(old) => cur = old,
 427             }
 428         }
 429     }
 430
 431     /// Gets the number of [`Weak`][weak] pointers to this value.
 432     ///
 433     /// [weak]: struct.Weak.html
 434     ///
 435     /// # Safety
 436     ///
 437     /// This method by itself is safe, but using it correctly requires extra care.
 438     /// Another thread can change the weak count at any time,
 439     /// including potentially between calling this method and acting on the result.
 440     ///
 441     /// # Examples
 442     ///
 443     /// ```
 444     /// use std::sync::Arc;
 445     ///
 446     /// let five = Arc::new(5);
 447     /// let _weak_five = Arc::downgrade(&five);
 448     ///
 449     /// // This assertion is deterministic because we haven't shared
 450     /// // the `Arc` or `Weak` between threads.
 451     /// assert_eq!(1, Arc::weak_count(&five));
 452     /// ```
 453     #[inline]
 454     #[stable(feature = "arc_counts", since = "1.15.0")]
 455     pub fn weak_count(this: &Self) -> usize {
 456         let cnt = this.inner().weak.load(SeqCst);
 457         // If the weak count is currently locked, the value of the
 458         // count was 0 just before taking the lock.
 459         if cnt == usize::MAX { 0 } else { cnt - 1 }
 460     }
 461
 462     /// Gets the number of strong (`Arc`) pointers to this value.
 463     ///
 464     /// # Safety
 465     ///
 466     /// This method by itself is safe, but using it correctly requires extra care.
 467     /// Another thread can change the strong count at any time,
 468     /// including potentially between calling this method and acting on the result.
 469     ///
 470     /// # Examples
 471     ///
 472     /// ```
 473     /// use std::sync::Arc;
 474     ///
 475     /// let five = Arc::new(5);
 476     /// let _also_five = Arc::clone(&five);
 477     ///
 478     /// // This assertion is deterministic because we haven't shared
 479     /// // the `Arc` between threads.
 480     /// assert_eq!(2, Arc::strong_count(&five));
 481     /// ```
 482     #[inline]
 483     #[stable(feature = "arc_counts", since = "1.15.0")]
 484     pub fn strong_count(this: &Self) -> usize {
 485         this.inner().strong.load(SeqCst)
 486     }
 487
 488     #[inline]
 489     fn inner(&self) -> &ArcInner<T> {
 490         // This unsafety is ok because while this arc is alive we're guaranteed
 491         // that the inner pointer is valid. Furthermore, we know that the
 492         // `ArcInner` structure itself is `Sync` because the inner data is
 493         // `Sync` as well, so we're ok loaning out an immutable pointer to these
 494         // contents.
 495         unsafe { self.ptr.as_ref() }
 496     }
 497
 498     // Non-inlined part of `drop`.
 499     #[inline(never)]
 500     unsafe fn drop_slow(&mut self) {
 501         let ptr = self.ptr.as_ptr();
 502
 503         // Destroy the data at this time, even though we may not free the box
 504         // allocation itself (there may still be weak pointers lying around).
 505         ptr::drop_in_place(&mut self.ptr.as_mut().data);
 506
 507         if self.inner().weak.fetch_sub(1, Release) == 1 {
 508             atomic::fence(Acquire);
 509             Heap.dealloc(ptr as *mut u8, Layout::for_value(&*ptr))
 510         }
 511     }
 512
 513     #[inline]
 514     #[stable(feature = "ptr_eq", since = "1.17.0")]
 515     /// Returns true if the two `Arc`s point to the same value (not
 516     /// just values that compare as equal).
 517     ///
 518     /// # Examples
 519     ///
 520     /// ```
 521     /// use std::sync::Arc;
 522     ///
 523     /// let five = Arc::new(5);
 524     /// let same_five = Arc::clone(&five);
 525     /// let other_five = Arc::new(5);
 526     ///
 527     /// assert!(Arc::ptr_eq(&five, &same_five));
 528     /// assert!(!Arc::ptr_eq(&five, &other_five));
 529     /// ```
 530     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
 531         this.ptr.as_ptr() == other.ptr.as_ptr()
 532     }
 533 }
 534
 535 #[stable(feature = "rust1", since = "1.0.0")]
 536 impl<T: ?Sized> Clone for Arc<T> {
 537     /// Makes a clone of the `Arc` pointer.
 538     ///
 539     /// This creates another pointer to the same inner value, increasing the
 540     /// strong reference count.
 541     ///
 542     /// # Examples
 543     ///
 544     /// ```
 545     /// use std::sync::Arc;
 546     ///
 547     /// let five = Arc::new(5);
 548     ///
 549     /// Arc::clone(&five);
 550     /// ```
 551     #[inline]
 552     fn clone(&self) -> Arc<T> {
 553         // Using a relaxed ordering is alright here, as knowledge of the
 554         // original reference prevents other threads from erroneously deleting
 555         // the object.
 556         //
 557         // As explained in the [Boost documentation][1], Increasing the
 558         // reference counter can always be done with memory_order_relaxed: New
 559         // references to an object can only be formed from an existing
 560         // reference, and passing an existing reference from one thread to
 561         // another must already provide any required synchronization.
 562         //
 563         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 564         let old_size = self.inner().strong.fetch_add(1, Relaxed);
 565
 566         // However we need to guard against massive refcounts in case someone
 567         // is `mem::forget`ing Arcs. If we don't do this the count can overflow
 568         // and users will use-after free. We racily saturate to `isize::MAX` on
 569         // the assumption that there aren't ~2 billion threads incrementing
 570         // the reference count at once. This branch will never be taken in
 571         // any realistic program.
 572         //
 573         // We abort because such a program is incredibly degenerate, and we
 574         // don't care to support it.
 575         if old_size > MAX_REFCOUNT {
 576             unsafe {
 577                 abort();
 578             }
 579         }
 580
 581         Arc { ptr: self.ptr }
 582     }
 583 }
 584
 585 #[stable(feature = "rust1", since = "1.0.0")]
 586 impl<T: ?Sized> Deref for Arc<T> {
 587     type Target = T;
 588
 589     #[inline]
 590     fn deref(&self) -> &T {
 591         &self.inner().data
 592     }
 593 }
 594
 595 impl<T: Clone> Arc<T> {
 596     /// Makes a mutable reference into the given `Arc`.
 597     ///
 598     /// If there are other `Arc` or [`Weak`][weak] pointers to the same value,
 599     /// then `make_mut` will invoke [`clone`][clone] on the inner value to
 600     /// ensure unique ownership. This is also referred to as clone-on-write.
 601     ///
 602     /// See also [`get_mut`][get_mut], which will fail rather than cloning.
 603     ///
 604     /// [weak]: struct.Weak.html
 605     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 606     /// [get_mut]: struct.Arc.html#method.get_mut
 607     ///
 608     /// # Examples
 609     ///
 610     /// ```
 611     /// use std::sync::Arc;
 612     ///
 613     /// let mut data = Arc::new(5);
 614     ///
 615     /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
 616     /// let mut other_data = Arc::clone(&data); // Won't clone inner data
 617     /// *Arc::make_mut(&mut data) += 1;         // Clones inner data
 618     /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
 619     /// *Arc::make_mut(&mut other_data) *= 2;   // Won't clone anything
 620     ///
 621     /// // Now `data` and `other_data` point to different values.
 622     /// assert_eq!(*data, 8);
 623     /// assert_eq!(*other_data, 12);
 624     /// ```
 625     #[inline]
 626     #[stable(feature = "arc_unique", since = "1.4.0")]
 627     pub fn make_mut(this: &mut Self) -> &mut T {
 628         // Note that we hold both a strong reference and a weak reference.
 629         // Thus, releasing our strong reference only will not, by itself, cause
 630         // the memory to be deallocated.
 631         //
 632         // Use Acquire to ensure that we see any writes to `weak` that happen
 633         // before release writes (i.e., decrements) to `strong`. Since we hold a
 634         // weak count, there's no chance the ArcInner itself could be
 635         // deallocated.
 636         if this.inner().strong.compare_exchange(1, 0, Acquire, Relaxed).is_err() {
 637             // Another strong pointer exists; clone
 638             *this = Arc::new((**this).clone());
 639         } else if this.inner().weak.load(Relaxed) != 1 {
 640             // Relaxed suffices in the above because this is fundamentally an
 641             // optimization: we are always racing with weak pointers being
 642             // dropped. Worst case, we end up allocated a new Arc unnecessarily.
 643
 644             // We removed the last strong ref, but there are additional weak
 645             // refs remaining. We'll move the contents to a new Arc, and
 646             // invalidate the other weak refs.
 647
 648             // Note that it is not possible for the read of `weak` to yield
 649             // usize::MAX (i.e., locked), since the weak count can only be
 650             // locked by a thread with a strong reference.
 651
 652             // Materialize our own implicit weak pointer, so that it can clean
 653             // up the ArcInner as needed.
 654             let weak = Weak { ptr: this.ptr };
 655
 656             // mark the data itself as already deallocated
 657             unsafe {
 658                 // there is no data race in the implicit write caused by `read`
 659                 // here (due to zeroing) because data is no longer accessed by
 660                 // other threads (due to there being no more strong refs at this
 661                 // point).
 662                 let mut swap = Arc::new(ptr::read(&weak.ptr.as_ref().data));
 663                 mem::swap(this, &mut swap);
 664                 mem::forget(swap);
 665             }
 666         } else {
 667             // We were the sole reference of either kind; bump back up the
 668             // strong ref count.
 669             this.inner().strong.store(1, Release);
 670         }
 671
 672         // As with `get_mut()`, the unsafety is ok because our reference was
 673         // either unique to begin with, or became one upon cloning the contents.
 674         unsafe {
 675             &mut this.ptr.as_mut().data
 676         }
 677     }
 678 }
 679
 680 impl<T: ?Sized> Arc<T> {
 681     /// Returns a mutable reference to the inner value, if there are
 682     /// no other `Arc` or [`Weak`][weak] pointers to the same value.
 683     ///
 684     /// Returns [`None`][option] otherwise, because it is not safe to
 685     /// mutate a shared value.
 686     ///
 687     /// See also [`make_mut`][make_mut], which will [`clone`][clone]
 688     /// the inner value when it's shared.
 689     ///
 690     /// [weak]: struct.Weak.html
 691     /// [option]: ../../std/option/enum.Option.html
 692     /// [make_mut]: struct.Arc.html#method.make_mut
 693     /// [clone]: ../../std/clone/trait.Clone.html#tymethod.clone
 694     ///
 695     /// # Examples
 696     ///
 697     /// ```
 698     /// use std::sync::Arc;
 699     ///
 700     /// let mut x = Arc::new(3);
 701     /// *Arc::get_mut(&mut x).unwrap() = 4;
 702     /// assert_eq!(*x, 4);
 703     ///
 704     /// let _y = Arc::clone(&x);
 705     /// assert!(Arc::get_mut(&mut x).is_none());
 706     /// ```
 707     #[inline]
 708     #[stable(feature = "arc_unique", since = "1.4.0")]
 709     pub fn get_mut(this: &mut Self) -> Option<&mut T> {
 710         if this.is_unique() {
 711             // This unsafety is ok because we're guaranteed that the pointer
 712             // returned is the *only* pointer that will ever be returned to T. Our
 713             // reference count is guaranteed to be 1 at this point, and we required
 714             // the Arc itself to be `mut`, so we're returning the only possible
 715             // reference to the inner data.
 716             unsafe {
 717                 Some(&mut this.ptr.as_mut().data)
 718             }
 719         } else {
 720             None
 721         }
 722     }
 723
 724     /// Determine whether this is the unique reference (including weak refs) to
 725     /// the underlying data.
 726     ///
 727     /// Note that this requires locking the weak ref count.
 728     fn is_unique(&mut self) -> bool {
 729         // lock the weak pointer count if we appear to be the sole weak pointer
 730         // holder.
 731         //
 732         // The acquire label here ensures a happens-before relationship with any
 733         // writes to `strong` prior to decrements of the `weak` count (via drop,
 734         // which uses Release).
 735         if self.inner().weak.compare_exchange(1, usize::MAX, Acquire, Relaxed).is_ok() {
 736             // Due to the previous acquire read, this will observe any writes to
 737             // `strong` that were due to upgrading weak pointers; only strong
 738             // clones remain, which require that the strong count is > 1 anyway.
 739             let unique = self.inner().strong.load(Relaxed) == 1;
 740
 741             // The release write here synchronizes with a read in `downgrade`,
 742             // effectively preventing the above read of `strong` from happening
 743             // after the write.
 744             self.inner().weak.store(1, Release); // release the lock
 745             unique
 746         } else {
 747             false
 748         }
 749     }
 750 }
 751
 752 #[stable(feature = "rust1", since = "1.0.0")]
 753 unsafe impl<#[may_dangle] T: ?Sized> Drop for Arc<T> {
 754     /// Drops the `Arc`.
 755     ///
 756     /// This will decrement the strong reference count. If the strong reference
 757     /// count reaches zero then the only other references (if any) are
 758     /// [`Weak`][weak], so we `drop` the inner value.
 759     ///
 760     /// [weak]: struct.Weak.html
 761     ///
 762     /// # Examples
 763     ///
 764     /// ```
 765     /// use std::sync::Arc;
 766     ///
 767     /// struct Foo;
 768     ///
 769     /// impl Drop for Foo {
 770     ///     fn drop(&mut self) {
 771     ///         println!("dropped!");
 772     ///     }
 773     /// }
 774     ///
 775     /// let foo  = Arc::new(Foo);
 776     /// let foo2 = Arc::clone(&foo);
 777     ///
 778     /// drop(foo);    // Doesn't print anything
 779     /// drop(foo2);   // Prints "dropped!"
 780     /// ```
 781     #[inline]
 782     fn drop(&mut self) {
 783         // Because `fetch_sub` is already atomic, we do not need to synchronize
 784         // with other threads unless we are going to delete the object. This
 785         // same logic applies to the below `fetch_sub` to the `weak` count.
 786         if self.inner().strong.fetch_sub(1, Release) != 1 {
 787             return;
 788         }
 789
 790         // This fence is needed to prevent reordering of use of the data and
 791         // deletion of the data.  Because it is marked `Release`, the decreasing
 792         // of the reference count synchronizes with this `Acquire` fence. This
 793         // means that use of the data happens before decreasing the reference
 794         // count, which happens before this fence, which happens before the
 795         // deletion of the data.
 796         //
 797         // As explained in the [Boost documentation][1],
 798         //
 799         // > It is important to enforce any possible access to the object in one
 800         // > thread (through an existing reference) to *happen before* deleting
 801         // > the object in a different thread. This is achieved by a "release"
 802         // > operation after dropping a reference (any access to the object
 803         // > through this reference must obviously happened before), and an
 804         // > "acquire" operation before deleting the object.
 805         //
 806         // In particular, while the contents of an Arc are usually immutable, it's
 807         // possible to have interior writes to something like a Mutex<T>. Since a
 808         // Mutex is not acquired when it is deleted, we can't rely on its
 809         // synchronization logic to make writes in thread A visible to a destructor
 810         // running in thread B.
 811         //
 812         // Also note that the Acquire fence here could probably be replaced with an
 813         // Acquire load, which could improve performance in highly-contended
 814         // situations. See [2].
 815         //
 816         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 817         // [2]: (https://github.com/rust-lang/rust/pull/41714)
 818         atomic::fence(Acquire);
 819
 820         unsafe {
 821             self.drop_slow();
 822         }
 823     }
 824 }
 825
 826 impl<T> Weak<T> {
 827     /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing
 828     /// it. Calling [`upgrade`] on the return value always gives [`None`].
 829     ///
 830     /// [`upgrade`]: struct.Weak.html#method.upgrade
 831     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 832     ///
 833     /// # Examples
 834     ///
 835     /// ```
 836     /// use std::sync::Weak;
 837     ///
 838     /// let empty: Weak<i64> = Weak::new();
 839     /// assert!(empty.upgrade().is_none());
 840     /// ```
 841     #[stable(feature = "downgraded_weak", since = "1.10.0")]
 842     pub fn new() -> Weak<T> {
 843         unsafe {
 844             Weak {
 845                 ptr: Shared::from(Box::into_unique(box ArcInner {
 846                     strong: atomic::AtomicUsize::new(0),
 847                     weak: atomic::AtomicUsize::new(1),
 848                     data: uninitialized(),
 849                 })),
 850             }
 851         }
 852     }
 853 }
 854
 855 impl<T: ?Sized> Weak<T> {
 856     /// Attempts to upgrade the `Weak` pointer to an [`Arc`], extending
 857     /// the lifetime of the value if successful.
 858     ///
 859     /// Returns [`None`] if the value has since been dropped.
 860     ///
 861     /// [`Arc`]: struct.Arc.html
 862     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 863     ///
 864     /// # Examples
 865     ///
 866     /// ```
 867     /// use std::sync::Arc;
 868     ///
 869     /// let five = Arc::new(5);
 870     ///
 871     /// let weak_five = Arc::downgrade(&five);
 872     ///
 873     /// let strong_five: Option<Arc<_>> = weak_five.upgrade();
 874     /// assert!(strong_five.is_some());
 875     ///
 876     /// // Destroy all strong pointers.
 877     /// drop(strong_five);
 878     /// drop(five);
 879     ///
 880     /// assert!(weak_five.upgrade().is_none());
 881     /// ```
 882     #[stable(feature = "arc_weak", since = "1.4.0")]
 883     pub fn upgrade(&self) -> Option<Arc<T>> {
 884         // We use a CAS loop to increment the strong count instead of a
 885         // fetch_add because once the count hits 0 it must never be above 0.
 886         let inner = self.inner();
 887
 888         // Relaxed load because any write of 0 that we can observe
 889         // leaves the field in a permanently zero state (so a
 890         // "stale" read of 0 is fine), and any other value is
 891         // confirmed via the CAS below.
 892         let mut n = inner.strong.load(Relaxed);
 893
 894         loop {
 895             if n == 0 {
 896                 return None;
 897             }
 898
 899             // See comments in `Arc::clone` for why we do this (for `mem::forget`).
 900             if n > MAX_REFCOUNT {
 901                 unsafe {
 902                     abort();
 903                 }
 904             }
 905
 906             // Relaxed is valid for the same reason it is on Arc's Clone impl
 907             match inner.strong.compare_exchange_weak(n, n + 1, Relaxed, Relaxed) {
 908                 Ok(_) => return Some(Arc { ptr: self.ptr }),
 909                 Err(old) => n = old,
 910             }
 911         }
 912     }
 913
 914     #[inline]
 915     fn inner(&self) -> &ArcInner<T> {
 916         // See comments above for why this is "safe"
 917         unsafe { self.ptr.as_ref() }
 918     }
 919 }
 920
 921 #[stable(feature = "arc_weak", since = "1.4.0")]
 922 impl<T: ?Sized> Clone for Weak<T> {
 923     /// Makes a clone of the `Weak` pointer that points to the same value.
 924     ///
 925     /// # Examples
 926     ///
 927     /// ```
 928     /// use std::sync::{Arc, Weak};
 929     ///
 930     /// let weak_five = Arc::downgrade(&Arc::new(5));
 931     ///
 932     /// Weak::clone(&weak_five);
 933     /// ```
 934     #[inline]
 935     fn clone(&self) -> Weak<T> {
 936         // See comments in Arc::clone() for why this is relaxed.  This can use a
 937         // fetch_add (ignoring the lock) because the weak count is only locked
 938         // where are *no other* weak pointers in existence. (So we can't be
 939         // running this code in that case).
 940         let old_size = self.inner().weak.fetch_add(1, Relaxed);
 941
 942         // See comments in Arc::clone() for why we do this (for mem::forget).
 943         if old_size > MAX_REFCOUNT {
 944             unsafe {
 945                 abort();
 946             }
 947         }
 948
 949         return Weak { ptr: self.ptr };
 950     }
 951 }
 952
 953 #[stable(feature = "downgraded_weak", since = "1.10.0")]
 954 impl<T> Default for Weak<T> {
 955     /// Constructs a new `Weak<T>`, allocating memory for `T` without initializing
 956     /// it. Calling [`upgrade`] on the return value always gives [`None`].
 957     ///
 958     /// [`upgrade`]: struct.Weak.html#method.upgrade
 959     /// [`None`]: ../../std/option/enum.Option.html#variant.None
 960     ///
 961     /// # Examples
 962     ///
 963     /// ```
 964     /// use std::sync::Weak;
 965     ///
 966     /// let empty: Weak<i64> = Default::default();
 967     /// assert!(empty.upgrade().is_none());
 968     /// ```
 969     fn default() -> Weak<T> {
 970         Weak::new()
 971     }
 972 }
 973
 974 #[stable(feature = "arc_weak", since = "1.4.0")]
 975 impl<T: ?Sized> Drop for Weak<T> {
 976     /// Drops the `Weak` pointer.
 977     ///
 978     /// # Examples
 979     ///
 980     /// ```
 981     /// use std::sync::{Arc, Weak};
 982     ///
 983     /// struct Foo;
 984     ///
 985     /// impl Drop for Foo {
 986     ///     fn drop(&mut self) {
 987     ///         println!("dropped!");
 988     ///     }
 989     /// }
 990     ///
 991     /// let foo = Arc::new(Foo);
 992     /// let weak_foo = Arc::downgrade(&foo);
 993     /// let other_weak_foo = Weak::clone(&weak_foo);
 994     ///
 995     /// drop(weak_foo);   // Doesn't print anything
 996     /// drop(foo);        // Prints "dropped!"
 997     ///
 998     /// assert!(other_weak_foo.upgrade().is_none());
 999     /// ```
1000     fn drop(&mut self) {
1001         let ptr = self.ptr.as_ptr();
1002
1003         // If we find out that we were the last weak pointer, then its time to
1004         // deallocate the data entirely. See the discussion in Arc::drop() about
1005         // the memory orderings
1006         //
1007         // It's not necessary to check for the locked state here, because the
1008         // weak count can only be locked if there was precisely one weak ref,
1009         // meaning that drop could only subsequently run ON that remaining weak
1010         // ref, which can only happen after the lock is released.
1011         if self.inner().weak.fetch_sub(1, Release) == 1 {
1012             atomic::fence(Acquire);
1013             unsafe {
1014                 Heap.dealloc(ptr as *mut u8, Layout::for_value(&*ptr))
1015             }
1016         }
1017     }
1018 }
1019
1020 #[stable(feature = "rust1", since = "1.0.0")]
1021 impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
1022     /// Equality for two `Arc`s.
1023     ///
1024     /// Two `Arc`s are equal if their inner values are equal.
1025     ///
1026     /// # Examples
1027     ///
1028     /// ```
1029     /// use std::sync::Arc;
1030     ///
1031     /// let five = Arc::new(5);
1032     ///
1033     /// assert!(five == Arc::new(5));
1034     /// ```
1035     fn eq(&self, other: &Arc<T>) -> bool {
1036         *(*self) == *(*other)
1037     }
1038
1039     /// Inequality for two `Arc`s.
1040     ///
1041     /// Two `Arc`s are unequal if their inner values are unequal.
1042     ///
1043     /// # Examples
1044     ///
1045     /// ```
1046     /// use std::sync::Arc;
1047     ///
1048     /// let five = Arc::new(5);
1049     ///
1050     /// assert!(five != Arc::new(6));
1051     /// ```
1052     fn ne(&self, other: &Arc<T>) -> bool {
1053         *(*self) != *(*other)
1054     }
1055 }
1056 #[stable(feature = "rust1", since = "1.0.0")]
1057 impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
1058     /// Partial comparison for two `Arc`s.
1059     ///
1060     /// The two are compared by calling `partial_cmp()` on their inner values.
1061     ///
1062     /// # Examples
1063     ///
1064     /// ```
1065     /// use std::sync::Arc;
1066     /// use std::cmp::Ordering;
1067     ///
1068     /// let five = Arc::new(5);
1069     ///
1070     /// assert_eq!(Some(Ordering::Less), five.partial_cmp(&Arc::new(6)));
1071     /// ```
1072     fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
1073         (**self).partial_cmp(&**other)
1074     }
1075
1076     /// Less-than comparison for two `Arc`s.
1077     ///
1078     /// The two are compared by calling `<` on their inner values.
1079     ///
1080     /// # Examples
1081     ///
1082     /// ```
1083     /// use std::sync::Arc;
1084     ///
1085     /// let five = Arc::new(5);
1086     ///
1087     /// assert!(five < Arc::new(6));
1088     /// ```
1089     fn lt(&self, other: &Arc<T>) -> bool {
1090         *(*self) < *(*other)
1091     }
1092
1093     /// 'Less than or equal to' comparison for two `Arc`s.
1094     ///
1095     /// The two are compared by calling `<=` on their inner values.
1096     ///
1097     /// # Examples
1098     ///
1099     /// ```
1100     /// use std::sync::Arc;
1101     ///
1102     /// let five = Arc::new(5);
1103     ///
1104     /// assert!(five <= Arc::new(5));
1105     /// ```
1106     fn le(&self, other: &Arc<T>) -> bool {
1107         *(*self) <= *(*other)
1108     }
1109
1110     /// Greater-than comparison for two `Arc`s.
1111     ///
1112     /// The two are compared by calling `>` on their inner values.
1113     ///
1114     /// # Examples
1115     ///
1116     /// ```
1117     /// use std::sync::Arc;
1118     ///
1119     /// let five = Arc::new(5);
1120     ///
1121     /// assert!(five > Arc::new(4));
1122     /// ```
1123     fn gt(&self, other: &Arc<T>) -> bool {
1124         *(*self) > *(*other)
1125     }
1126
1127     /// 'Greater than or equal to' comparison for two `Arc`s.
1128     ///
1129     /// The two are compared by calling `>=` on their inner values.
1130     ///
1131     /// # Examples
1132     ///
1133     /// ```
1134     /// use std::sync::Arc;
1135     ///
1136     /// let five = Arc::new(5);
1137     ///
1138     /// assert!(five >= Arc::new(5));
1139     /// ```
1140     fn ge(&self, other: &Arc<T>) -> bool {
1141         *(*self) >= *(*other)
1142     }
1143 }
1144 #[stable(feature = "rust1", since = "1.0.0")]
1145 impl<T: ?Sized + Ord> Ord for Arc<T> {
1146     /// Comparison for two `Arc`s.
1147     ///
1148     /// The two are compared by calling `cmp()` on their inner values.
1149     ///
1150     /// # Examples
1151     ///
1152     /// ```
1153     /// use std::sync::Arc;
1154     /// use std::cmp::Ordering;
1155     ///
1156     /// let five = Arc::new(5);
1157     ///
1158     /// assert_eq!(Ordering::Less, five.cmp(&Arc::new(6)));
1159     /// ```
1160     fn cmp(&self, other: &Arc<T>) -> Ordering {
1161         (**self).cmp(&**other)
1162     }
1163 }
1164 #[stable(feature = "rust1", since = "1.0.0")]
1165 impl<T: ?Sized + Eq> Eq for Arc<T> {}
1166
1167 #[stable(feature = "rust1", since = "1.0.0")]
1168 impl<T: ?Sized + fmt::Display> fmt::Display for Arc<T> {
1169     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1170         fmt::Display::fmt(&**self, f)
1171     }
1172 }
1173
1174 #[stable(feature = "rust1", since = "1.0.0")]
1175 impl<T: ?Sized + fmt::Debug> fmt::Debug for Arc<T> {
1176     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1177         fmt::Debug::fmt(&**self, f)
1178     }
1179 }
1180
1181 #[stable(feature = "rust1", since = "1.0.0")]
1182 impl<T: ?Sized> fmt::Pointer for Arc<T> {
1183     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1184         fmt::Pointer::fmt(&self.ptr, f)
1185     }
1186 }
1187
1188 #[stable(feature = "rust1", since = "1.0.0")]
1189 impl<T: Default> Default for Arc<T> {
1190     /// Creates a new `Arc<T>`, with the `Default` value for `T`.
1191     ///
1192     /// # Examples
1193     ///
1194     /// ```
1195     /// use std::sync::Arc;
1196     ///
1197     /// let x: Arc<i32> = Default::default();
1198     /// assert_eq!(*x, 0);
1199     /// ```
1200     fn default() -> Arc<T> {
1201         Arc::new(Default::default())
1202     }
1203 }
1204
1205 #[stable(feature = "rust1", since = "1.0.0")]
1206 impl<T: ?Sized + Hash> Hash for Arc<T> {
1207     fn hash<H: Hasher>(&self, state: &mut H) {
1208         (**self).hash(state)
1209     }
1210 }
1211
1212 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
1213 impl<T> From<T> for Arc<T> {
1214     fn from(t: T) -> Self {
1215         Arc::new(t)
1216     }
1217 }
1218
1219 #[cfg(test)]
1220 mod tests {
1221     use std::clone::Clone;
1222     use std::sync::mpsc::channel;
1223     use std::mem::drop;
1224     use std::ops::Drop;
1225     use std::option::Option;
1226     use std::option::Option::{None, Some};
1227     use std::sync::atomic;
1228     use std::sync::atomic::Ordering::{Acquire, SeqCst};
1229     use std::thread;
1230     use std::sync::Mutex;
1231     use std::convert::From;
1232
1233     use super::{Arc, Weak};
1234     use vec::Vec;
1235
1236     struct Canary(*mut atomic::AtomicUsize);
1237
1238     impl Drop for Canary {
1239         fn drop(&mut self) {
1240             unsafe {
1241                 match *self {
1242                     Canary(c) => {
1243                         (*c).fetch_add(1, SeqCst);
1244                     }
1245                 }
1246             }
1247         }
1248     }
1249
1250     #[test]
1251     #[cfg_attr(target_os = "emscripten", ignore)]
1252     fn manually_share_arc() {
1253         let v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1254         let arc_v = Arc::new(v);
1255
1256         let (tx, rx) = channel();
1257
1258         let _t = thread::spawn(move || {
1259             let arc_v: Arc<Vec<i32>> = rx.recv().unwrap();
1260             assert_eq!((*arc_v)[3], 4);
1261         });
1262
1263         tx.send(arc_v.clone()).unwrap();
1264
1265         assert_eq!((*arc_v)[2], 3);
1266         assert_eq!((*arc_v)[4], 5);
1267     }
1268
1269     #[test]
1270     fn test_arc_get_mut() {
1271         let mut x = Arc::new(3);
1272         *Arc::get_mut(&mut x).unwrap() = 4;
1273         assert_eq!(*x, 4);
1274         let y = x.clone();
1275         assert!(Arc::get_mut(&mut x).is_none());
1276         drop(y);
1277         assert!(Arc::get_mut(&mut x).is_some());
1278         let _w = Arc::downgrade(&x);
1279         assert!(Arc::get_mut(&mut x).is_none());
1280     }
1281
1282     #[test]
1283     fn try_unwrap() {
1284         let x = Arc::new(3);
1285         assert_eq!(Arc::try_unwrap(x), Ok(3));
1286         let x = Arc::new(4);
1287         let _y = x.clone();
1288         assert_eq!(Arc::try_unwrap(x), Err(Arc::new(4)));
1289         let x = Arc::new(5);
1290         let _w = Arc::downgrade(&x);
1291         assert_eq!(Arc::try_unwrap(x), Ok(5));
1292     }
1293
1294     #[test]
1295     fn into_from_raw() {
1296         let x = Arc::new(box "hello");
1297         let y = x.clone();
1298
1299         let x_ptr = Arc::into_raw(x);
1300         drop(y);
1301         unsafe {
1302             assert_eq!(**x_ptr, "hello");
1303
1304             let x = Arc::from_raw(x_ptr);
1305             assert_eq!(**x, "hello");
1306
1307             assert_eq!(Arc::try_unwrap(x).map(|x| *x), Ok("hello"));
1308         }
1309     }
1310
1311     #[test]
1312     fn test_cowarc_clone_make_mut() {
1313         let mut cow0 = Arc::new(75);
1314         let mut cow1 = cow0.clone();
1315         let mut cow2 = cow1.clone();
1316
1317         assert!(75 == *Arc::make_mut(&mut cow0));
1318         assert!(75 == *Arc::make_mut(&mut cow1));
1319         assert!(75 == *Arc::make_mut(&mut cow2));
1320
1321         *Arc::make_mut(&mut cow0) += 1;
1322         *Arc::make_mut(&mut cow1) += 2;
1323         *Arc::make_mut(&mut cow2) += 3;
1324
1325         assert!(76 == *cow0);
1326         assert!(77 == *cow1);
1327         assert!(78 == *cow2);
1328
1329         // none should point to the same backing memory
1330         assert!(*cow0 != *cow1);
1331         assert!(*cow0 != *cow2);
1332         assert!(*cow1 != *cow2);
1333     }
1334
1335     #[test]
1336     fn test_cowarc_clone_unique2() {
1337         let mut cow0 = Arc::new(75);
1338         let cow1 = cow0.clone();
1339         let cow2 = cow1.clone();
1340
1341         assert!(75 == *cow0);
1342         assert!(75 == *cow1);
1343         assert!(75 == *cow2);
1344
1345         *Arc::make_mut(&mut cow0) += 1;
1346         assert!(76 == *cow0);
1347         assert!(75 == *cow1);
1348         assert!(75 == *cow2);
1349
1350         // cow1 and cow2 should share the same contents
1351         // cow0 should have a unique reference
1352         assert!(*cow0 != *cow1);
1353         assert!(*cow0 != *cow2);
1354         assert!(*cow1 == *cow2);
1355     }
1356
1357     #[test]
1358     fn test_cowarc_clone_weak() {
1359         let mut cow0 = Arc::new(75);
1360         let cow1_weak = Arc::downgrade(&cow0);
1361
1362         assert!(75 == *cow0);
1363         assert!(75 == *cow1_weak.upgrade().unwrap());
1364
1365         *Arc::make_mut(&mut cow0) += 1;
1366
1367         assert!(76 == *cow0);
1368         assert!(cow1_weak.upgrade().is_none());
1369     }
1370
1371     #[test]
1372     fn test_live() {
1373         let x = Arc::new(5);
1374         let y = Arc::downgrade(&x);
1375         assert!(y.upgrade().is_some());
1376     }
1377
1378     #[test]
1379     fn test_dead() {
1380         let x = Arc::new(5);
1381         let y = Arc::downgrade(&x);
1382         drop(x);
1383         assert!(y.upgrade().is_none());
1384     }
1385
1386     #[test]
1387     fn weak_self_cyclic() {
1388         struct Cycle {
1389             x: Mutex<Option<Weak<Cycle>>>,
1390         }
1391
1392         let a = Arc::new(Cycle { x: Mutex::new(None) });
1393         let b = Arc::downgrade(&a.clone());
1394         *a.x.lock().unwrap() = Some(b);
1395
1396         // hopefully we don't double-free (or leak)...
1397     }
1398
1399     #[test]
1400     fn drop_arc() {
1401         let mut canary = atomic::AtomicUsize::new(0);
1402         let x = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
1403         drop(x);
1404         assert!(canary.load(Acquire) == 1);
1405     }
1406
1407     #[test]
1408     fn drop_arc_weak() {
1409         let mut canary = atomic::AtomicUsize::new(0);
1410         let arc = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
1411         let arc_weak = Arc::downgrade(&arc);
1412         assert!(canary.load(Acquire) == 0);
1413         drop(arc);
1414         assert!(canary.load(Acquire) == 1);
1415         drop(arc_weak);
1416     }
1417
1418     #[test]
1419     fn test_strong_count() {
1420         let a = Arc::new(0);
1421         assert!(Arc::strong_count(&a) == 1);
1422         let w = Arc::downgrade(&a);
1423         assert!(Arc::strong_count(&a) == 1);
1424         let b = w.upgrade().expect("");
1425         assert!(Arc::strong_count(&b) == 2);
1426         assert!(Arc::strong_count(&a) == 2);
1427         drop(w);
1428         drop(a);
1429         assert!(Arc::strong_count(&b) == 1);
1430         let c = b.clone();
1431         assert!(Arc::strong_count(&b) == 2);
1432         assert!(Arc::strong_count(&c) == 2);
1433     }
1434
1435     #[test]
1436     fn test_weak_count() {
1437         let a = Arc::new(0);
1438         assert!(Arc::strong_count(&a) == 1);
1439         assert!(Arc::weak_count(&a) == 0);
1440         let w = Arc::downgrade(&a);
1441         assert!(Arc::strong_count(&a) == 1);
1442         assert!(Arc::weak_count(&a) == 1);
1443         let x = w.clone();
1444         assert!(Arc::weak_count(&a) == 2);
1445         drop(w);
1446         drop(x);
1447         assert!(Arc::strong_count(&a) == 1);
1448         assert!(Arc::weak_count(&a) == 0);
1449         let c = a.clone();
1450         assert!(Arc::strong_count(&a) == 2);
1451         assert!(Arc::weak_count(&a) == 0);
1452         let d = Arc::downgrade(&c);
1453         assert!(Arc::weak_count(&c) == 1);
1454         assert!(Arc::strong_count(&c) == 2);
1455
1456         drop(a);
1457         drop(c);
1458         drop(d);
1459     }
1460
1461     #[test]
1462     fn show_arc() {
1463         let a = Arc::new(5);
1464         assert_eq!(format!("{:?}", a), "5");
1465     }
1466
1467     // Make sure deriving works with Arc<T>
1468     #[derive(Eq, Ord, PartialEq, PartialOrd, Clone, Debug, Default)]
1469     struct Foo {
1470         inner: Arc<i32>,
1471     }
1472
1473     #[test]
1474     fn test_unsized() {
1475         let x: Arc<[i32]> = Arc::new([1, 2, 3]);
1476         assert_eq!(format!("{:?}", x), "[1, 2, 3]");
1477         let y = Arc::downgrade(&x.clone());
1478         drop(x);
1479         assert!(y.upgrade().is_none());
1480     }
1481
1482     #[test]
1483     fn test_from_owned() {
1484         let foo = 123;
1485         let foo_arc = Arc::from(foo);
1486         assert!(123 == *foo_arc);
1487     }
1488
1489     #[test]
1490     fn test_new_weak() {
1491         let foo: Weak<usize> = Weak::new();
1492         assert!(foo.upgrade().is_none());
1493     }
1494
1495     #[test]
1496     fn test_ptr_eq() {
1497         let five = Arc::new(5);
1498         let same_five = five.clone();
1499         let other_five = Arc::new(5);
1500
1501         assert!(Arc::ptr_eq(&five, &same_five));
1502         assert!(!Arc::ptr_eq(&five, &other_five));
1503     }
1504
1505     #[test]
1506     #[cfg_attr(target_os = "emscripten", ignore)]
1507     fn test_weak_count_locked() {
1508         let mut a = Arc::new(atomic::AtomicBool::new(false));
1509         let a2 = a.clone();
1510         let t = thread::spawn(move || {
1511             for _i in 0..1000000 {
1512                 Arc::get_mut(&mut a);
1513             }
1514             a.store(true, SeqCst);
1515         });
1516
1517         while !a2.load(SeqCst) {
1518             let n = Arc::weak_count(&a2);
1519             assert!(n < 2, "bad weak count: {}", n);
1520         }
1521         t.join().unwrap();
1522     }
1523 }
1524
1525 #[stable(feature = "rust1", since = "1.0.0")]
1526 impl<T: ?Sized> borrow::Borrow<T> for Arc<T> {
1527     fn borrow(&self) -> &T {
1528         &**self
1529     }
1530 }
1531
1532 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1533 impl<T: ?Sized> AsRef<T> for Arc<T> {
1534     fn as_ref(&self) -> &T {
1535         &**self
1536     }
1537 }