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 //! Threadsafe reference-counted boxes (the `Arc<T>` type).
  14 //!
  15 //! The `Arc<T>` type provides shared ownership of an immutable value.
  16 //! Destruction is deterministic, and will occur as soon as the last owner is
  17 //! gone. It is marked as `Send` because it uses atomic reference counting.
  18 //!
  19 //! If you do not need thread-safety, and just need shared ownership, consider
  20 //! the [`Rc<T>` type](../rc/struct.Rc.html). It is the same as `Arc<T>`, but
  21 //! does not use atomics, making it both thread-unsafe as well as significantly
  22 //! faster when updating the reference count.
  23 //!
  24 //! The `downgrade` method can be used to create a non-owning `Weak<T>` pointer
  25 //! to the box. A `Weak<T>` pointer can be upgraded to an `Arc<T>` pointer, but
  26 //! will return `None` if the value has already been dropped.
  27 //!
  28 //! For example, a tree with parent pointers can be represented by putting the
  29 //! nodes behind strong `Arc<T>` pointers, and then storing the parent pointers
  30 //! as `Weak<T>` pointers.
  31 //!
  32 //! # Examples
  33 //!
  34 //! Sharing some immutable data between threads:
  35 //!
  36 //! ```no_run
  37 //! use std::sync::Arc;
  38 //! use std::thread;
  39 //!
  40 //! let five = Arc::new(5);
  41 //!
  42 //! for _ in 0..10 {
  43 //!     let five = five.clone();
  44 //!
  45 //!     thread::spawn(move || {
  46 //!         println!("{:?}", five);
  47 //!     });
  48 //! }
  49 //! ```
  50 //!
  51 //! Sharing mutable data safely between threads with a `Mutex`:
  52 //!
  53 //! ```no_run
  54 //! use std::sync::{Arc, Mutex};
  55 //! use std::thread;
  56 //!
  57 //! let five = Arc::new(Mutex::new(5));
  58 //!
  59 //! for _ in 0..10 {
  60 //!     let five = five.clone();
  61 //!
  62 //!     thread::spawn(move || {
  63 //!         let mut number = five.lock().unwrap();
  64 //!
  65 //!         *number += 1;
  66 //!
  67 //!         println!("{}", *number); // prints 6
  68 //!     });
  69 //! }
  70 //! ```
  71
  72 use boxed::Box;
  73
  74 use core::sync::atomic;
  75 use core::sync::atomic::Ordering::{Relaxed, Release, Acquire, SeqCst};
  76 use core::borrow;
  77 use core::fmt;
  78 use core::cmp::Ordering;
  79 use core::mem::{align_of_val, size_of_val};
  80 use core::intrinsics::abort;
  81 use core::mem;
  82 use core::mem::uninitialized;
  83 use core::ops::Deref;
  84 use core::ops::CoerceUnsized;
  85 use core::ptr::{self, Shared};
  86 use core::marker::Unsize;
  87 use core::hash::{Hash, Hasher};
  88 use core::{usize, isize};
  89 use core::convert::From;
  90 use heap::deallocate;
  91
  92 const MAX_REFCOUNT: usize = (isize::MAX) as usize;
  93
  94 /// An atomically reference counted wrapper for shared state.
  95 ///
  96 /// # Examples
  97 ///
  98 /// In this example, a large vector is shared between several threads.
  99 /// With simple pipes, without `Arc`, a copy would have to be made for each
 100 /// thread.
 101 ///
 102 /// When you clone an `Arc<T>`, it will create another pointer to the data and
 103 /// increase the reference counter.
 104 ///
 105 /// ```
 106 /// use std::sync::Arc;
 107 /// use std::thread;
 108 ///
 109 /// fn main() {
 110 ///     let numbers: Vec<_> = (0..100u32).collect();
 111 ///     let shared_numbers = Arc::new(numbers);
 112 ///
 113 ///     for _ in 0..10 {
 114 ///         let child_numbers = shared_numbers.clone();
 115 ///
 116 ///         thread::spawn(move || {
 117 ///             let local_numbers = &child_numbers[..];
 118 ///
 119 ///             // Work with the local numbers
 120 ///         });
 121 ///     }
 122 /// }
 123 /// ```
 124 #[unsafe_no_drop_flag]
 125 #[stable(feature = "rust1", since = "1.0.0")]
 126 pub struct Arc<T: ?Sized> {
 127     // FIXME #12808: strange name to try to avoid interfering with
 128     // field accesses of the contained type via Deref
 129     _ptr: Shared<ArcInner<T>>,
 130 }
 131
 132 #[stable(feature = "rust1", since = "1.0.0")]
 133 unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> {}
 134 #[stable(feature = "rust1", since = "1.0.0")]
 135 unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> {}
 136
 137 #[unstable(feature = "coerce_unsized", issue = "27732")]
 138 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Arc<U>> for Arc<T> {}
 139
 140 /// A weak pointer to an `Arc`.
 141 ///
 142 /// Weak pointers will not keep the data inside of the `Arc` alive, and can be
 143 /// used to break cycles between `Arc` pointers.
 144 #[unsafe_no_drop_flag]
 145 #[stable(feature = "arc_weak", since = "1.4.0")]
 146 pub struct Weak<T: ?Sized> {
 147     // FIXME #12808: strange name to try to avoid interfering with
 148     // field accesses of the contained type via Deref
 149     _ptr: Shared<ArcInner<T>>,
 150 }
 151
 152 #[stable(feature = "rust1", since = "1.0.0")]
 153 unsafe impl<T: ?Sized + Sync + Send> Send for Weak<T> {}
 154 #[stable(feature = "rust1", since = "1.0.0")]
 155 unsafe impl<T: ?Sized + Sync + Send> Sync for Weak<T> {}
 156
 157 #[unstable(feature = "coerce_unsized", issue = "27732")]
 158 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Weak<U>> for Weak<T> {}
 159
 160 #[stable(feature = "rust1", since = "1.0.0")]
 161 impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
 162     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 163         write!(f, "(Weak)")
 164     }
 165 }
 166
 167 struct ArcInner<T: ?Sized> {
 168     strong: atomic::AtomicUsize,
 169
 170     // the value usize::MAX acts as a sentinel for temporarily "locking" the
 171     // ability to upgrade weak pointers or downgrade strong ones; this is used
 172     // to avoid races in `make_mut` and `get_mut`.
 173     weak: atomic::AtomicUsize,
 174
 175     data: T,
 176 }
 177
 178 unsafe impl<T: ?Sized + Sync + Send> Send for ArcInner<T> {}
 179 unsafe impl<T: ?Sized + Sync + Send> Sync for ArcInner<T> {}
 180
 181 impl<T> Arc<T> {
 182     /// Constructs a new `Arc<T>`.
 183     ///
 184     /// # Examples
 185     ///
 186     /// ```
 187     /// use std::sync::Arc;
 188     ///
 189     /// let five = Arc::new(5);
 190     /// ```
 191     #[inline]
 192     #[stable(feature = "rust1", since = "1.0.0")]
 193     pub fn new(data: T) -> Arc<T> {
 194         // Start the weak pointer count as 1 which is the weak pointer that's
 195         // held by all the strong pointers (kinda), see std/rc.rs for more info
 196         let x: Box<_> = box ArcInner {
 197             strong: atomic::AtomicUsize::new(1),
 198             weak: atomic::AtomicUsize::new(1),
 199             data: data,
 200         };
 201         Arc { _ptr: unsafe { Shared::new(Box::into_raw(x)) } }
 202     }
 203
 204     /// Unwraps the contained value if the `Arc<T>` has only one strong reference.
 205     /// This will succeed even if there are outstanding weak references.
 206     ///
 207     /// Otherwise, an `Err` is returned with the same `Arc<T>`.
 208     ///
 209     /// # Examples
 210     ///
 211     /// ```
 212     /// use std::sync::Arc;
 213     ///
 214     /// let x = Arc::new(3);
 215     /// assert_eq!(Arc::try_unwrap(x), Ok(3));
 216     ///
 217     /// let x = Arc::new(4);
 218     /// let _y = x.clone();
 219     /// assert_eq!(Arc::try_unwrap(x), Err(Arc::new(4)));
 220     /// ```
 221     #[inline]
 222     #[stable(feature = "arc_unique", since = "1.4.0")]
 223     pub fn try_unwrap(this: Self) -> Result<T, Self> {
 224         // See `drop` for why all these atomics are like this
 225         if this.inner().strong.compare_and_swap(1, 0, Release) != 1 {
 226             return Err(this);
 227         }
 228
 229         atomic::fence(Acquire);
 230
 231         unsafe {
 232             let ptr = *this._ptr;
 233             let elem = ptr::read(&(*ptr).data);
 234
 235             // Make a weak pointer to clean up the implicit strong-weak reference
 236             let _weak = Weak { _ptr: this._ptr };
 237             mem::forget(this);
 238
 239             Ok(elem)
 240         }
 241     }
 242 }
 243
 244 impl<T: ?Sized> Arc<T> {
 245     /// Downgrades the `Arc<T>` to a `Weak<T>` reference.
 246     ///
 247     /// # Examples
 248     ///
 249     /// ```
 250     /// use std::sync::Arc;
 251     ///
 252     /// let five = Arc::new(5);
 253     ///
 254     /// let weak_five = Arc::downgrade(&five);
 255     /// ```
 256     #[stable(feature = "arc_weak", since = "1.4.0")]
 257     pub fn downgrade(this: &Self) -> Weak<T> {
 258         loop {
 259             // This Relaxed is OK because we're checking the value in the CAS
 260             // below.
 261             let cur = this.inner().weak.load(Relaxed);
 262
 263             // check if the weak counter is currently "locked"; if so, spin.
 264             if cur == usize::MAX {
 265                 continue;
 266             }
 267
 268             // NOTE: this code currently ignores the possibility of overflow
 269             // into usize::MAX; in general both Rc and Arc need to be adjusted
 270             // to deal with overflow.
 271
 272             // Unlike with Clone(), we need this to be an Acquire read to
 273             // synchronize with the write coming from `is_unique`, so that the
 274             // events prior to that write happen before this read.
 275             if this.inner().weak.compare_and_swap(cur, cur + 1, Acquire) == cur {
 276                 return Weak { _ptr: this._ptr };
 277             }
 278         }
 279     }
 280
 281     /// Get the number of weak references to this value.
 282     #[inline]
 283     #[unstable(feature = "arc_counts", reason = "not clearly useful, and racy",
 284                issue = "28356")]
 285     pub fn weak_count(this: &Self) -> usize {
 286         this.inner().weak.load(SeqCst) - 1
 287     }
 288
 289     /// Get the number of strong references to this value.
 290     #[inline]
 291     #[unstable(feature = "arc_counts", reason = "not clearly useful, and racy",
 292                issue = "28356")]
 293     pub fn strong_count(this: &Self) -> usize {
 294         this.inner().strong.load(SeqCst)
 295     }
 296
 297     #[inline]
 298     fn inner(&self) -> &ArcInner<T> {
 299         // This unsafety is ok because while this arc is alive we're guaranteed
 300         // that the inner pointer is valid. Furthermore, we know that the
 301         // `ArcInner` structure itself is `Sync` because the inner data is
 302         // `Sync` as well, so we're ok loaning out an immutable pointer to these
 303         // contents.
 304         unsafe { &**self._ptr }
 305     }
 306
 307     // Non-inlined part of `drop`.
 308     #[inline(never)]
 309     unsafe fn drop_slow(&mut self) {
 310         let ptr = *self._ptr;
 311
 312         // Destroy the data at this time, even though we may not free the box
 313         // allocation itself (there may still be weak pointers lying around).
 314         ptr::drop_in_place(&mut (*ptr).data);
 315
 316         if self.inner().weak.fetch_sub(1, Release) == 1 {
 317             atomic::fence(Acquire);
 318             deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr))
 319         }
 320     }
 321 }
 322
 323 #[stable(feature = "rust1", since = "1.0.0")]
 324 impl<T: ?Sized> Clone for Arc<T> {
 325     /// Makes a clone of the `Arc<T>`.
 326     ///
 327     /// This increases the strong reference count.
 328     ///
 329     /// # Examples
 330     ///
 331     /// ```
 332     /// use std::sync::Arc;
 333     ///
 334     /// let five = Arc::new(5);
 335     ///
 336     /// five.clone();
 337     /// ```
 338     #[inline]
 339     fn clone(&self) -> Arc<T> {
 340         // Using a relaxed ordering is alright here, as knowledge of the
 341         // original reference prevents other threads from erroneously deleting
 342         // the object.
 343         //
 344         // As explained in the [Boost documentation][1], Increasing the
 345         // reference counter can always be done with memory_order_relaxed: New
 346         // references to an object can only be formed from an existing
 347         // reference, and passing an existing reference from one thread to
 348         // another must already provide any required synchronization.
 349         //
 350         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 351         let old_size = self.inner().strong.fetch_add(1, Relaxed);
 352
 353         // However we need to guard against massive refcounts in case someone
 354         // is `mem::forget`ing Arcs. If we don't do this the count can overflow
 355         // and users will use-after free. We racily saturate to `isize::MAX` on
 356         // the assumption that there aren't ~2 billion threads incrementing
 357         // the reference count at once. This branch will never be taken in
 358         // any realistic program.
 359         //
 360         // We abort because such a program is incredibly degenerate, and we
 361         // don't care to support it.
 362         if old_size > MAX_REFCOUNT {
 363             unsafe {
 364                 abort();
 365             }
 366         }
 367
 368         Arc { _ptr: self._ptr }
 369     }
 370 }
 371
 372 #[stable(feature = "rust1", since = "1.0.0")]
 373 impl<T: ?Sized> Deref for Arc<T> {
 374     type Target = T;
 375
 376     #[inline]
 377     fn deref(&self) -> &T {
 378         &self.inner().data
 379     }
 380 }
 381
 382 impl<T: Clone> Arc<T> {
 383     /// Make a mutable reference into the given `Arc<T>` by cloning the inner
 384     /// data if the `Arc<T>` doesn't have one strong reference and no weak
 385     /// references.
 386     ///
 387     /// This is also referred to as a copy-on-write.
 388     ///
 389     /// # Examples
 390     ///
 391     /// ```
 392     /// use std::sync::Arc;
 393     ///
 394     /// let mut data = Arc::new(5);
 395     ///
 396     /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
 397     /// let mut other_data = data.clone();      // Won't clone inner data
 398     /// *Arc::make_mut(&mut data) += 1;         // Clones inner data
 399     /// *Arc::make_mut(&mut data) += 1;         // Won't clone anything
 400     /// *Arc::make_mut(&mut other_data) *= 2;   // Won't clone anything
 401     ///
 402     /// // Note: data and other_data now point to different numbers
 403     /// assert_eq!(*data, 8);
 404     /// assert_eq!(*other_data, 12);
 405     ///
 406     /// ```
 407     #[inline]
 408     #[stable(feature = "arc_unique", since = "1.4.0")]
 409     pub fn make_mut(this: &mut Self) -> &mut T {
 410         // Note that we hold both a strong reference and a weak reference.
 411         // Thus, releasing our strong reference only will not, by itself, cause
 412         // the memory to be deallocated.
 413         //
 414         // Use Acquire to ensure that we see any writes to `weak` that happen
 415         // before release writes (i.e., decrements) to `strong`. Since we hold a
 416         // weak count, there's no chance the ArcInner itself could be
 417         // deallocated.
 418         if this.inner().strong.compare_and_swap(1, 0, Acquire) != 1 {
 419             // Another strong pointer exists; clone
 420             *this = Arc::new((**this).clone());
 421         } else if this.inner().weak.load(Relaxed) != 1 {
 422             // Relaxed suffices in the above because this is fundamentally an
 423             // optimization: we are always racing with weak pointers being
 424             // dropped. Worst case, we end up allocated a new Arc unnecessarily.
 425
 426             // We removed the last strong ref, but there are additional weak
 427             // refs remaining. We'll move the contents to a new Arc, and
 428             // invalidate the other weak refs.
 429
 430             // Note that it is not possible for the read of `weak` to yield
 431             // usize::MAX (i.e., locked), since the weak count can only be
 432             // locked by a thread with a strong reference.
 433
 434             // Materialize our own implicit weak pointer, so that it can clean
 435             // up the ArcInner as needed.
 436             let weak = Weak { _ptr: this._ptr };
 437
 438             // mark the data itself as already deallocated
 439             unsafe {
 440                 // there is no data race in the implicit write caused by `read`
 441                 // here (due to zeroing) because data is no longer accessed by
 442                 // other threads (due to there being no more strong refs at this
 443                 // point).
 444                 let mut swap = Arc::new(ptr::read(&(**weak._ptr).data));
 445                 mem::swap(this, &mut swap);
 446                 mem::forget(swap);
 447             }
 448         } else {
 449             // We were the sole reference of either kind; bump back up the
 450             // strong ref count.
 451             this.inner().strong.store(1, Release);
 452         }
 453
 454         // As with `get_mut()`, the unsafety is ok because our reference was
 455         // either unique to begin with, or became one upon cloning the contents.
 456         unsafe {
 457             let inner = &mut **this._ptr;
 458             &mut inner.data
 459         }
 460     }
 461 }
 462
 463 impl<T: ?Sized> Arc<T> {
 464     /// Returns a mutable reference to the contained value if the `Arc<T>` has
 465     /// one strong reference and no weak references.
 466     ///
 467     /// # Examples
 468     ///
 469     /// ```
 470     /// use std::sync::Arc;
 471     ///
 472     /// let mut x = Arc::new(3);
 473     /// *Arc::get_mut(&mut x).unwrap() = 4;
 474     /// assert_eq!(*x, 4);
 475     ///
 476     /// let _y = x.clone();
 477     /// assert!(Arc::get_mut(&mut x).is_none());
 478     /// ```
 479     #[inline]
 480     #[stable(feature = "arc_unique", since = "1.4.0")]
 481     pub fn get_mut(this: &mut Self) -> Option<&mut T> {
 482         if this.is_unique() {
 483             // This unsafety is ok because we're guaranteed that the pointer
 484             // returned is the *only* pointer that will ever be returned to T. Our
 485             // reference count is guaranteed to be 1 at this point, and we required
 486             // the Arc itself to be `mut`, so we're returning the only possible
 487             // reference to the inner data.
 488             unsafe {
 489                 let inner = &mut **this._ptr;
 490                 Some(&mut inner.data)
 491             }
 492         } else {
 493             None
 494         }
 495     }
 496
 497     /// Determine whether this is the unique reference (including weak refs) to
 498     /// the underlying data.
 499     ///
 500     /// Note that this requires locking the weak ref count.
 501     fn is_unique(&mut self) -> bool {
 502         // lock the weak pointer count if we appear to be the sole weak pointer
 503         // holder.
 504         //
 505         // The acquire label here ensures a happens-before relationship with any
 506         // writes to `strong` prior to decrements of the `weak` count (via drop,
 507         // which uses Release).
 508         if self.inner().weak.compare_and_swap(1, usize::MAX, Acquire) == 1 {
 509             // Due to the previous acquire read, this will observe any writes to
 510             // `strong` that were due to upgrading weak pointers; only strong
 511             // clones remain, which require that the strong count is > 1 anyway.
 512             let unique = self.inner().strong.load(Relaxed) == 1;
 513
 514             // The release write here synchronizes with a read in `downgrade`,
 515             // effectively preventing the above read of `strong` from happening
 516             // after the write.
 517             self.inner().weak.store(1, Release); // release the lock
 518             unique
 519         } else {
 520             false
 521         }
 522     }
 523 }
 524
 525 #[stable(feature = "rust1", since = "1.0.0")]
 526 impl<T: ?Sized> Drop for Arc<T> {
 527     /// Drops the `Arc<T>`.
 528     ///
 529     /// This will decrement the strong reference count. If the strong reference
 530     /// count becomes zero and the only other references are `Weak<T>` ones,
 531     /// `drop`s the inner value.
 532     ///
 533     /// # Examples
 534     ///
 535     /// ```
 536     /// use std::sync::Arc;
 537     ///
 538     /// {
 539     ///     let five = Arc::new(5);
 540     ///
 541     ///     // stuff
 542     ///
 543     ///     drop(five); // explicit drop
 544     /// }
 545     /// {
 546     ///     let five = Arc::new(5);
 547     ///
 548     ///     // stuff
 549     ///
 550     /// } // implicit drop
 551     /// ```
 552     #[unsafe_destructor_blind_to_params]
 553     #[inline]
 554     fn drop(&mut self) {
 555         // This structure has #[unsafe_no_drop_flag], so this drop glue may run
 556         // more than once (but it is guaranteed to be zeroed after the first if
 557         // it's run more than once)
 558         let thin = *self._ptr as *const ();
 559
 560         if thin as usize == mem::POST_DROP_USIZE {
 561             return;
 562         }
 563
 564         // Because `fetch_sub` is already atomic, we do not need to synchronize
 565         // with other threads unless we are going to delete the object. This
 566         // same logic applies to the below `fetch_sub` to the `weak` count.
 567         if self.inner().strong.fetch_sub(1, Release) != 1 {
 568             return;
 569         }
 570
 571         // This fence is needed to prevent reordering of use of the data and
 572         // deletion of the data.  Because it is marked `Release`, the decreasing
 573         // of the reference count synchronizes with this `Acquire` fence. This
 574         // means that use of the data happens before decreasing the reference
 575         // count, which happens before this fence, which happens before the
 576         // deletion of the data.
 577         //
 578         // As explained in the [Boost documentation][1],
 579         //
 580         // > It is important to enforce any possible access to the object in one
 581         // > thread (through an existing reference) to *happen before* deleting
 582         // > the object in a different thread. This is achieved by a "release"
 583         // > operation after dropping a reference (any access to the object
 584         // > through this reference must obviously happened before), and an
 585         // > "acquire" operation before deleting the object.
 586         //
 587         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 588         atomic::fence(Acquire);
 589
 590         unsafe {
 591             self.drop_slow();
 592         }
 593     }
 594 }
 595
 596 impl<T: ?Sized> Weak<T> {
 597     /// Upgrades a weak reference to a strong reference.
 598     ///
 599     /// Upgrades the `Weak<T>` reference to an `Arc<T>`, if possible.
 600     ///
 601     /// Returns `None` if there were no strong references and the data was
 602     /// destroyed.
 603     ///
 604     /// # Examples
 605     ///
 606     /// ```
 607     /// use std::sync::Arc;
 608     ///
 609     /// let five = Arc::new(5);
 610     ///
 611     /// let weak_five = Arc::downgrade(&five);
 612     ///
 613     /// let strong_five: Option<Arc<_>> = weak_five.upgrade();
 614     /// ```
 615     #[stable(feature = "arc_weak", since = "1.4.0")]
 616     pub fn upgrade(&self) -> Option<Arc<T>> {
 617         // We use a CAS loop to increment the strong count instead of a
 618         // fetch_add because once the count hits 0 it must never be above 0.
 619         let inner = self.inner();
 620         loop {
 621             // Relaxed load because any write of 0 that we can observe
 622             // leaves the field in a permanently zero state (so a
 623             // "stale" read of 0 is fine), and any other value is
 624             // confirmed via the CAS below.
 625             let n = inner.strong.load(Relaxed);
 626             if n == 0 {
 627                 return None;
 628             }
 629
 630             // See comments in `Arc::clone` for why we do this (for `mem::forget`).
 631             if n > MAX_REFCOUNT {
 632                 unsafe { abort(); }
 633             }
 634
 635             // Relaxed is valid for the same reason it is on Arc's Clone impl
 636             let old = inner.strong.compare_and_swap(n, n + 1, Relaxed);
 637             if old == n {
 638                 return Some(Arc { _ptr: self._ptr });
 639             }
 640         }
 641     }
 642
 643     #[inline]
 644     fn inner(&self) -> &ArcInner<T> {
 645         // See comments above for why this is "safe"
 646         unsafe { &**self._ptr }
 647     }
 648 }
 649
 650 #[stable(feature = "arc_weak", since = "1.4.0")]
 651 impl<T: ?Sized> Clone for Weak<T> {
 652     /// Makes a clone of the `Weak<T>`.
 653     ///
 654     /// This increases the weak reference count.
 655     ///
 656     /// # Examples
 657     ///
 658     /// ```
 659     /// use std::sync::Arc;
 660     ///
 661     /// let weak_five = Arc::downgrade(&Arc::new(5));
 662     ///
 663     /// weak_five.clone();
 664     /// ```
 665     #[inline]
 666     fn clone(&self) -> Weak<T> {
 667         // See comments in Arc::clone() for why this is relaxed.  This can use a
 668         // fetch_add (ignoring the lock) because the weak count is only locked
 669         // where are *no other* weak pointers in existence. (So we can't be
 670         // running this code in that case).
 671         let old_size = self.inner().weak.fetch_add(1, Relaxed);
 672
 673         // See comments in Arc::clone() for why we do this (for mem::forget).
 674         if old_size > MAX_REFCOUNT {
 675             unsafe {
 676                 abort();
 677             }
 678         }
 679
 680         return Weak { _ptr: self._ptr };
 681     }
 682 }
 683
 684 #[stable(feature = "rust1", since = "1.0.0")]
 685 impl<T: ?Sized> Drop for Weak<T> {
 686     /// Drops the `Weak<T>`.
 687     ///
 688     /// This will decrement the weak reference count.
 689     ///
 690     /// # Examples
 691     ///
 692     /// ```
 693     /// use std::sync::Arc;
 694     ///
 695     /// {
 696     ///     let five = Arc::new(5);
 697     ///     let weak_five = Arc::downgrade(&five);
 698     ///
 699     ///     // stuff
 700     ///
 701     ///     drop(weak_five); // explicit drop
 702     /// }
 703     /// {
 704     ///     let five = Arc::new(5);
 705     ///     let weak_five = Arc::downgrade(&five);
 706     ///
 707     ///     // stuff
 708     ///
 709     /// } // implicit drop
 710     /// ```
 711     fn drop(&mut self) {
 712         let ptr = *self._ptr;
 713         let thin = ptr as *const ();
 714
 715         // see comments above for why this check is here
 716         if thin as usize == mem::POST_DROP_USIZE {
 717             return;
 718         }
 719
 720         // If we find out that we were the last weak pointer, then its time to
 721         // deallocate the data entirely. See the discussion in Arc::drop() about
 722         // the memory orderings
 723         //
 724         // It's not necessary to check for the locked state here, because the
 725         // weak count can only be locked if there was precisely one weak ref,
 726         // meaning that drop could only subsequently run ON that remaining weak
 727         // ref, which can only happen after the lock is released.
 728         if self.inner().weak.fetch_sub(1, Release) == 1 {
 729             atomic::fence(Acquire);
 730             unsafe { deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr)) }
 731         }
 732     }
 733 }
 734
 735 #[stable(feature = "rust1", since = "1.0.0")]
 736 impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
 737     /// Equality for two `Arc<T>`s.
 738     ///
 739     /// Two `Arc<T>`s are equal if their inner value are equal.
 740     ///
 741     /// # Examples
 742     ///
 743     /// ```
 744     /// use std::sync::Arc;
 745     ///
 746     /// let five = Arc::new(5);
 747     ///
 748     /// five == Arc::new(5);
 749     /// ```
 750     fn eq(&self, other: &Arc<T>) -> bool {
 751         *(*self) == *(*other)
 752     }
 753
 754     /// Inequality for two `Arc<T>`s.
 755     ///
 756     /// Two `Arc<T>`s are unequal if their inner value are unequal.
 757     ///
 758     /// # Examples
 759     ///
 760     /// ```
 761     /// use std::sync::Arc;
 762     ///
 763     /// let five = Arc::new(5);
 764     ///
 765     /// five != Arc::new(5);
 766     /// ```
 767     fn ne(&self, other: &Arc<T>) -> bool {
 768         *(*self) != *(*other)
 769     }
 770 }
 771 #[stable(feature = "rust1", since = "1.0.0")]
 772 impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
 773     /// Partial comparison for two `Arc<T>`s.
 774     ///
 775     /// The two are compared by calling `partial_cmp()` on their inner values.
 776     ///
 777     /// # Examples
 778     ///
 779     /// ```
 780     /// use std::sync::Arc;
 781     ///
 782     /// let five = Arc::new(5);
 783     ///
 784     /// five.partial_cmp(&Arc::new(5));
 785     /// ```
 786     fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
 787         (**self).partial_cmp(&**other)
 788     }
 789
 790     /// Less-than comparison for two `Arc<T>`s.
 791     ///
 792     /// The two are compared by calling `<` on their inner values.
 793     ///
 794     /// # Examples
 795     ///
 796     /// ```
 797     /// use std::sync::Arc;
 798     ///
 799     /// let five = Arc::new(5);
 800     ///
 801     /// five < Arc::new(5);
 802     /// ```
 803     fn lt(&self, other: &Arc<T>) -> bool {
 804         *(*self) < *(*other)
 805     }
 806
 807     /// 'Less-than or equal to' comparison for two `Arc<T>`s.
 808     ///
 809     /// The two are compared by calling `<=` on their inner values.
 810     ///
 811     /// # Examples
 812     ///
 813     /// ```
 814     /// use std::sync::Arc;
 815     ///
 816     /// let five = Arc::new(5);
 817     ///
 818     /// five <= Arc::new(5);
 819     /// ```
 820     fn le(&self, other: &Arc<T>) -> bool {
 821         *(*self) <= *(*other)
 822     }
 823
 824     /// Greater-than comparison for two `Arc<T>`s.
 825     ///
 826     /// The two are compared by calling `>` on their inner values.
 827     ///
 828     /// # Examples
 829     ///
 830     /// ```
 831     /// use std::sync::Arc;
 832     ///
 833     /// let five = Arc::new(5);
 834     ///
 835     /// five > Arc::new(5);
 836     /// ```
 837     fn gt(&self, other: &Arc<T>) -> bool {
 838         *(*self) > *(*other)
 839     }
 840
 841     /// 'Greater-than or equal to' comparison for two `Arc<T>`s.
 842     ///
 843     /// The two are compared by calling `>=` on their inner values.
 844     ///
 845     /// # Examples
 846     ///
 847     /// ```
 848     /// use std::sync::Arc;
 849     ///
 850     /// let five = Arc::new(5);
 851     ///
 852     /// five >= Arc::new(5);
 853     /// ```
 854     fn ge(&self, other: &Arc<T>) -> bool {
 855         *(*self) >= *(*other)
 856     }
 857 }
 858 #[stable(feature = "rust1", since = "1.0.0")]
 859 impl<T: ?Sized + Ord> Ord for Arc<T> {
 860     fn cmp(&self, other: &Arc<T>) -> Ordering {
 861         (**self).cmp(&**other)
 862     }
 863 }
 864 #[stable(feature = "rust1", since = "1.0.0")]
 865 impl<T: ?Sized + Eq> Eq for Arc<T> {}
 866
 867 #[stable(feature = "rust1", since = "1.0.0")]
 868 impl<T: ?Sized + fmt::Display> fmt::Display for Arc<T> {
 869     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 870         fmt::Display::fmt(&**self, f)
 871     }
 872 }
 873
 874 #[stable(feature = "rust1", since = "1.0.0")]
 875 impl<T: ?Sized + fmt::Debug> fmt::Debug for Arc<T> {
 876     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 877         fmt::Debug::fmt(&**self, f)
 878     }
 879 }
 880
 881 #[stable(feature = "rust1", since = "1.0.0")]
 882 impl<T> fmt::Pointer for Arc<T> {
 883     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 884         fmt::Pointer::fmt(&*self._ptr, f)
 885     }
 886 }
 887
 888 #[stable(feature = "rust1", since = "1.0.0")]
 889 impl<T: Default> Default for Arc<T> {
 890     fn default() -> Arc<T> {
 891         Arc::new(Default::default())
 892     }
 893 }
 894
 895 #[stable(feature = "rust1", since = "1.0.0")]
 896 impl<T: ?Sized + Hash> Hash for Arc<T> {
 897     fn hash<H: Hasher>(&self, state: &mut H) {
 898         (**self).hash(state)
 899     }
 900 }
 901
 902 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
 903 impl<T> From<T> for Arc<T> {
 904     fn from(t: T) -> Self {
 905         Arc::new(t)
 906     }
 907 }
 908
 909 impl<T> Weak<T> {
 910     /// Constructs a new `Weak<T>` without an accompanying instance of T.
 911     ///
 912     /// This allocates memory for T, but does not initialize it. Calling
 913     /// Weak<T>::upgrade() on the return value always gives None.
 914     ///
 915     /// # Examples
 916     ///
 917     /// ```
 918     /// #![feature(downgraded_weak)]
 919     ///
 920     /// use std::sync::Weak;
 921     ///
 922     /// let empty: Weak<i64> = Weak::new();
 923     /// ```
 924     #[unstable(feature = "downgraded_weak",
 925                reason = "recently added",
 926                issue = "30425")]
 927     pub fn new() -> Weak<T> {
 928         unsafe {
 929             Weak { _ptr: Shared::new(Box::into_raw(box ArcInner {
 930                 strong: atomic::AtomicUsize::new(0),
 931                 weak: atomic::AtomicUsize::new(1),
 932                 data: uninitialized(),
 933             }))}
 934         }
 935     }
 936 }
 937
 938 #[cfg(test)]
 939 mod tests {
 940     use std::clone::Clone;
 941     use std::sync::mpsc::channel;
 942     use std::mem::drop;
 943     use std::ops::Drop;
 944     use std::option::Option;
 945     use std::option::Option::{Some, None};
 946     use std::sync::atomic;
 947     use std::sync::atomic::Ordering::{Acquire, SeqCst};
 948     use std::thread;
 949     use std::vec::Vec;
 950     use super::{Arc, Weak};
 951     use std::sync::Mutex;
 952     use std::convert::From;
 953
 954     struct Canary(*mut atomic::AtomicUsize);
 955
 956     impl Drop for Canary {
 957         fn drop(&mut self) {
 958             unsafe {
 959                 match *self {
 960                     Canary(c) => {
 961                         (*c).fetch_add(1, SeqCst);
 962                     }
 963                 }
 964             }
 965         }
 966     }
 967
 968     #[test]
 969     fn manually_share_arc() {
 970         let v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 971         let arc_v = Arc::new(v);
 972
 973         let (tx, rx) = channel();
 974
 975         let _t = thread::spawn(move || {
 976             let arc_v: Arc<Vec<i32>> = rx.recv().unwrap();
 977             assert_eq!((*arc_v)[3], 4);
 978         });
 979
 980         tx.send(arc_v.clone()).unwrap();
 981
 982         assert_eq!((*arc_v)[2], 3);
 983         assert_eq!((*arc_v)[4], 5);
 984     }
 985
 986     #[test]
 987     fn test_arc_get_mut() {
 988         let mut x = Arc::new(3);
 989         *Arc::get_mut(&mut x).unwrap() = 4;
 990         assert_eq!(*x, 4);
 991         let y = x.clone();
 992         assert!(Arc::get_mut(&mut x).is_none());
 993         drop(y);
 994         assert!(Arc::get_mut(&mut x).is_some());
 995         let _w = Arc::downgrade(&x);
 996         assert!(Arc::get_mut(&mut x).is_none());
 997     }
 998
 999     #[test]
1000     fn try_unwrap() {
1001         let x = Arc::new(3);
1002         assert_eq!(Arc::try_unwrap(x), Ok(3));
1003         let x = Arc::new(4);
1004         let _y = x.clone();
1005         assert_eq!(Arc::try_unwrap(x), Err(Arc::new(4)));
1006         let x = Arc::new(5);
1007         let _w = Arc::downgrade(&x);
1008         assert_eq!(Arc::try_unwrap(x), Ok(5));
1009     }
1010
1011     #[test]
1012     fn test_cowarc_clone_make_mut() {
1013         let mut cow0 = Arc::new(75);
1014         let mut cow1 = cow0.clone();
1015         let mut cow2 = cow1.clone();
1016
1017         assert!(75 == *Arc::make_mut(&mut cow0));
1018         assert!(75 == *Arc::make_mut(&mut cow1));
1019         assert!(75 == *Arc::make_mut(&mut cow2));
1020
1021         *Arc::make_mut(&mut cow0) += 1;
1022         *Arc::make_mut(&mut cow1) += 2;
1023         *Arc::make_mut(&mut cow2) += 3;
1024
1025         assert!(76 == *cow0);
1026         assert!(77 == *cow1);
1027         assert!(78 == *cow2);
1028
1029         // none should point to the same backing memory
1030         assert!(*cow0 != *cow1);
1031         assert!(*cow0 != *cow2);
1032         assert!(*cow1 != *cow2);
1033     }
1034
1035     #[test]
1036     fn test_cowarc_clone_unique2() {
1037         let mut cow0 = Arc::new(75);
1038         let cow1 = cow0.clone();
1039         let cow2 = cow1.clone();
1040
1041         assert!(75 == *cow0);
1042         assert!(75 == *cow1);
1043         assert!(75 == *cow2);
1044
1045         *Arc::make_mut(&mut cow0) += 1;
1046         assert!(76 == *cow0);
1047         assert!(75 == *cow1);
1048         assert!(75 == *cow2);
1049
1050         // cow1 and cow2 should share the same contents
1051         // cow0 should have a unique reference
1052         assert!(*cow0 != *cow1);
1053         assert!(*cow0 != *cow2);
1054         assert!(*cow1 == *cow2);
1055     }
1056
1057     #[test]
1058     fn test_cowarc_clone_weak() {
1059         let mut cow0 = Arc::new(75);
1060         let cow1_weak = Arc::downgrade(&cow0);
1061
1062         assert!(75 == *cow0);
1063         assert!(75 == *cow1_weak.upgrade().unwrap());
1064
1065         *Arc::make_mut(&mut cow0) += 1;
1066
1067         assert!(76 == *cow0);
1068         assert!(cow1_weak.upgrade().is_none());
1069     }
1070
1071     #[test]
1072     fn test_live() {
1073         let x = Arc::new(5);
1074         let y = Arc::downgrade(&x);
1075         assert!(y.upgrade().is_some());
1076     }
1077
1078     #[test]
1079     fn test_dead() {
1080         let x = Arc::new(5);
1081         let y = Arc::downgrade(&x);
1082         drop(x);
1083         assert!(y.upgrade().is_none());
1084     }
1085
1086     #[test]
1087     fn weak_self_cyclic() {
1088         struct Cycle {
1089             x: Mutex<Option<Weak<Cycle>>>,
1090         }
1091
1092         let a = Arc::new(Cycle { x: Mutex::new(None) });
1093         let b = Arc::downgrade(&a.clone());
1094         *a.x.lock().unwrap() = Some(b);
1095
1096         // hopefully we don't double-free (or leak)...
1097     }
1098
1099     #[test]
1100     fn drop_arc() {
1101         let mut canary = atomic::AtomicUsize::new(0);
1102         let x = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
1103         drop(x);
1104         assert!(canary.load(Acquire) == 1);
1105     }
1106
1107     #[test]
1108     fn drop_arc_weak() {
1109         let mut canary = atomic::AtomicUsize::new(0);
1110         let arc = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
1111         let arc_weak = Arc::downgrade(&arc);
1112         assert!(canary.load(Acquire) == 0);
1113         drop(arc);
1114         assert!(canary.load(Acquire) == 1);
1115         drop(arc_weak);
1116     }
1117
1118     #[test]
1119     fn test_strong_count() {
1120         let a = Arc::new(0u32);
1121         assert!(Arc::strong_count(&a) == 1);
1122         let w = Arc::downgrade(&a);
1123         assert!(Arc::strong_count(&a) == 1);
1124         let b = w.upgrade().expect("");
1125         assert!(Arc::strong_count(&b) == 2);
1126         assert!(Arc::strong_count(&a) == 2);
1127         drop(w);
1128         drop(a);
1129         assert!(Arc::strong_count(&b) == 1);
1130         let c = b.clone();
1131         assert!(Arc::strong_count(&b) == 2);
1132         assert!(Arc::strong_count(&c) == 2);
1133     }
1134
1135     #[test]
1136     fn test_weak_count() {
1137         let a = Arc::new(0u32);
1138         assert!(Arc::strong_count(&a) == 1);
1139         assert!(Arc::weak_count(&a) == 0);
1140         let w = Arc::downgrade(&a);
1141         assert!(Arc::strong_count(&a) == 1);
1142         assert!(Arc::weak_count(&a) == 1);
1143         let x = w.clone();
1144         assert!(Arc::weak_count(&a) == 2);
1145         drop(w);
1146         drop(x);
1147         assert!(Arc::strong_count(&a) == 1);
1148         assert!(Arc::weak_count(&a) == 0);
1149         let c = a.clone();
1150         assert!(Arc::strong_count(&a) == 2);
1151         assert!(Arc::weak_count(&a) == 0);
1152         let d = Arc::downgrade(&c);
1153         assert!(Arc::weak_count(&c) == 1);
1154         assert!(Arc::strong_count(&c) == 2);
1155
1156         drop(a);
1157         drop(c);
1158         drop(d);
1159     }
1160
1161     #[test]
1162     fn show_arc() {
1163         let a = Arc::new(5u32);
1164         assert_eq!(format!("{:?}", a), "5");
1165     }
1166
1167     // Make sure deriving works with Arc<T>
1168     #[derive(Eq, Ord, PartialEq, PartialOrd, Clone, Debug, Default)]
1169     struct Foo {
1170         inner: Arc<i32>,
1171     }
1172
1173     #[test]
1174     fn test_unsized() {
1175         let x: Arc<[i32]> = Arc::new([1, 2, 3]);
1176         assert_eq!(format!("{:?}", x), "[1, 2, 3]");
1177         let y = Arc::downgrade(&x.clone());
1178         drop(x);
1179         assert!(y.upgrade().is_none());
1180     }
1181
1182     #[test]
1183     fn test_from_owned() {
1184         let foo = 123;
1185         let foo_arc = Arc::from(foo);
1186         assert!(123 == *foo_arc);
1187     }
1188
1189     #[test]
1190     fn test_new_weak() {
1191         let foo: Weak<usize> = Weak::new();
1192         assert!(foo.upgrade().is_none());
1193     }
1194 }
1195
1196 #[stable(feature = "rust1", since = "1.0.0")]
1197 impl<T: ?Sized> borrow::Borrow<T> for Arc<T> {
1198     fn borrow(&self) -> &T {
1199         &**self
1200     }
1201 }
1202
1203 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1204 impl<T: ?Sized> AsRef<T> for Arc<T> {
1205     fn as_ref(&self) -> &T {
1206         &**self
1207     }
1208 }