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 ptr = *self._ptr;
 559         // if ptr.is_null() { return }
 560         if ptr as *mut u8 as usize == 0 || ptr as *mut u8 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
 714         // see comments above for why this check is here
 715         if ptr as *mut u8 as usize == 0 || ptr as *mut u8 as usize == mem::POST_DROP_USIZE {
 716             return;
 717         }
 718
 719         // If we find out that we were the last weak pointer, then its time to
 720         // deallocate the data entirely. See the discussion in Arc::drop() about
 721         // the memory orderings
 722         //
 723         // It's not necessary to check for the locked state here, because the
 724         // weak count can only be locked if there was precisely one weak ref,
 725         // meaning that drop could only subsequently run ON that remaining weak
 726         // ref, which can only happen after the lock is released.
 727         if self.inner().weak.fetch_sub(1, Release) == 1 {
 728             atomic::fence(Acquire);
 729             unsafe { deallocate(ptr as *mut u8, size_of_val(&*ptr), align_of_val(&*ptr)) }
 730         }
 731     }
 732 }
 733
 734 #[stable(feature = "rust1", since = "1.0.0")]
 735 impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
 736     /// Equality for two `Arc<T>`s.
 737     ///
 738     /// Two `Arc<T>`s are equal if their inner value are equal.
 739     ///
 740     /// # Examples
 741     ///
 742     /// ```
 743     /// use std::sync::Arc;
 744     ///
 745     /// let five = Arc::new(5);
 746     ///
 747     /// five == Arc::new(5);
 748     /// ```
 749     fn eq(&self, other: &Arc<T>) -> bool {
 750         *(*self) == *(*other)
 751     }
 752
 753     /// Inequality for two `Arc<T>`s.
 754     ///
 755     /// Two `Arc<T>`s are unequal if their inner value are unequal.
 756     ///
 757     /// # Examples
 758     ///
 759     /// ```
 760     /// use std::sync::Arc;
 761     ///
 762     /// let five = Arc::new(5);
 763     ///
 764     /// five != Arc::new(5);
 765     /// ```
 766     fn ne(&self, other: &Arc<T>) -> bool {
 767         *(*self) != *(*other)
 768     }
 769 }
 770 #[stable(feature = "rust1", since = "1.0.0")]
 771 impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
 772     /// Partial comparison for two `Arc<T>`s.
 773     ///
 774     /// The two are compared by calling `partial_cmp()` on their inner values.
 775     ///
 776     /// # Examples
 777     ///
 778     /// ```
 779     /// use std::sync::Arc;
 780     ///
 781     /// let five = Arc::new(5);
 782     ///
 783     /// five.partial_cmp(&Arc::new(5));
 784     /// ```
 785     fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
 786         (**self).partial_cmp(&**other)
 787     }
 788
 789     /// Less-than comparison for two `Arc<T>`s.
 790     ///
 791     /// The two are compared by calling `<` on their inner values.
 792     ///
 793     /// # Examples
 794     ///
 795     /// ```
 796     /// use std::sync::Arc;
 797     ///
 798     /// let five = Arc::new(5);
 799     ///
 800     /// five < Arc::new(5);
 801     /// ```
 802     fn lt(&self, other: &Arc<T>) -> bool {
 803         *(*self) < *(*other)
 804     }
 805
 806     /// 'Less-than or equal to' comparison for two `Arc<T>`s.
 807     ///
 808     /// The two are compared by calling `<=` on their inner values.
 809     ///
 810     /// # Examples
 811     ///
 812     /// ```
 813     /// use std::sync::Arc;
 814     ///
 815     /// let five = Arc::new(5);
 816     ///
 817     /// five <= Arc::new(5);
 818     /// ```
 819     fn le(&self, other: &Arc<T>) -> bool {
 820         *(*self) <= *(*other)
 821     }
 822
 823     /// Greater-than comparison for two `Arc<T>`s.
 824     ///
 825     /// The two are compared by calling `>` on their inner values.
 826     ///
 827     /// # Examples
 828     ///
 829     /// ```
 830     /// use std::sync::Arc;
 831     ///
 832     /// let five = Arc::new(5);
 833     ///
 834     /// five > Arc::new(5);
 835     /// ```
 836     fn gt(&self, other: &Arc<T>) -> bool {
 837         *(*self) > *(*other)
 838     }
 839
 840     /// 'Greater-than or equal to' comparison for two `Arc<T>`s.
 841     ///
 842     /// The two are compared by calling `>=` on their inner values.
 843     ///
 844     /// # Examples
 845     ///
 846     /// ```
 847     /// use std::sync::Arc;
 848     ///
 849     /// let five = Arc::new(5);
 850     ///
 851     /// five >= Arc::new(5);
 852     /// ```
 853     fn ge(&self, other: &Arc<T>) -> bool {
 854         *(*self) >= *(*other)
 855     }
 856 }
 857 #[stable(feature = "rust1", since = "1.0.0")]
 858 impl<T: ?Sized + Ord> Ord for Arc<T> {
 859     fn cmp(&self, other: &Arc<T>) -> Ordering {
 860         (**self).cmp(&**other)
 861     }
 862 }
 863 #[stable(feature = "rust1", since = "1.0.0")]
 864 impl<T: ?Sized + Eq> Eq for Arc<T> {}
 865
 866 #[stable(feature = "rust1", since = "1.0.0")]
 867 impl<T: ?Sized + fmt::Display> fmt::Display for Arc<T> {
 868     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 869         fmt::Display::fmt(&**self, f)
 870     }
 871 }
 872
 873 #[stable(feature = "rust1", since = "1.0.0")]
 874 impl<T: ?Sized + fmt::Debug> fmt::Debug for Arc<T> {
 875     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 876         fmt::Debug::fmt(&**self, f)
 877     }
 878 }
 879
 880 #[stable(feature = "rust1", since = "1.0.0")]
 881 impl<T> fmt::Pointer for Arc<T> {
 882     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 883         fmt::Pointer::fmt(&*self._ptr, f)
 884     }
 885 }
 886
 887 #[stable(feature = "rust1", since = "1.0.0")]
 888 impl<T: Default> Default for Arc<T> {
 889     fn default() -> Arc<T> {
 890         Arc::new(Default::default())
 891     }
 892 }
 893
 894 #[stable(feature = "rust1", since = "1.0.0")]
 895 impl<T: ?Sized + Hash> Hash for Arc<T> {
 896     fn hash<H: Hasher>(&self, state: &mut H) {
 897         (**self).hash(state)
 898     }
 899 }
 900
 901 #[stable(feature = "from_for_ptrs", since = "1.6.0")]
 902 impl<T> From<T> for Arc<T> {
 903     fn from(t: T) -> Self {
 904         Arc::new(t)
 905     }
 906 }
 907
 908 impl<T> Weak<T> {
 909     /// Constructs a new `Weak<T>` without an accompanying instance of T.
 910     ///
 911     /// This allocates memory for T, but does not initialize it. Calling
 912     /// Weak<T>::upgrade() on the return value always gives None.
 913     ///
 914     /// # Examples
 915     ///
 916     /// ```
 917     /// #![feature(downgraded_weak)]
 918     ///
 919     /// use std::sync::Weak;
 920     ///
 921     /// let empty: Weak<i64> = Weak::new();
 922     /// ```
 923     #[unstable(feature = "downgraded_weak",
 924                reason = "recently added",
 925                issue = "30425")]
 926     pub fn new() -> Weak<T> {
 927         unsafe {
 928             Weak { _ptr: Shared::new(Box::into_raw(box ArcInner {
 929                 strong: atomic::AtomicUsize::new(0),
 930                 weak: atomic::AtomicUsize::new(1),
 931                 data: uninitialized(),
 932             }))}
 933         }
 934     }
 935 }
 936
 937 #[cfg(test)]
 938 mod tests {
 939     use std::clone::Clone;
 940     use std::sync::mpsc::channel;
 941     use std::mem::drop;
 942     use std::ops::Drop;
 943     use std::option::Option;
 944     use std::option::Option::{Some, None};
 945     use std::sync::atomic;
 946     use std::sync::atomic::Ordering::{Acquire, SeqCst};
 947     use std::thread;
 948     use std::vec::Vec;
 949     use super::{Arc, Weak};
 950     use std::sync::Mutex;
 951     use std::convert::From;
 952
 953     struct Canary(*mut atomic::AtomicUsize);
 954
 955     impl Drop for Canary {
 956         fn drop(&mut self) {
 957             unsafe {
 958                 match *self {
 959                     Canary(c) => {
 960                         (*c).fetch_add(1, SeqCst);
 961                     }
 962                 }
 963             }
 964         }
 965     }
 966
 967     #[test]
 968     fn manually_share_arc() {
 969         let v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 970         let arc_v = Arc::new(v);
 971
 972         let (tx, rx) = channel();
 973
 974         let _t = thread::spawn(move || {
 975             let arc_v: Arc<Vec<i32>> = rx.recv().unwrap();
 976             assert_eq!((*arc_v)[3], 4);
 977         });
 978
 979         tx.send(arc_v.clone()).unwrap();
 980
 981         assert_eq!((*arc_v)[2], 3);
 982         assert_eq!((*arc_v)[4], 5);
 983     }
 984
 985     #[test]
 986     fn test_arc_get_mut() {
 987         let mut x = Arc::new(3);
 988         *Arc::get_mut(&mut x).unwrap() = 4;
 989         assert_eq!(*x, 4);
 990         let y = x.clone();
 991         assert!(Arc::get_mut(&mut x).is_none());
 992         drop(y);
 993         assert!(Arc::get_mut(&mut x).is_some());
 994         let _w = Arc::downgrade(&x);
 995         assert!(Arc::get_mut(&mut x).is_none());
 996     }
 997
 998     #[test]
 999     fn try_unwrap() {
1000         let x = Arc::new(3);
1001         assert_eq!(Arc::try_unwrap(x), Ok(3));
1002         let x = Arc::new(4);
1003         let _y = x.clone();
1004         assert_eq!(Arc::try_unwrap(x), Err(Arc::new(4)));
1005         let x = Arc::new(5);
1006         let _w = Arc::downgrade(&x);
1007         assert_eq!(Arc::try_unwrap(x), Ok(5));
1008     }
1009
1010     #[test]
1011     fn test_cowarc_clone_make_mut() {
1012         let mut cow0 = Arc::new(75);
1013         let mut cow1 = cow0.clone();
1014         let mut cow2 = cow1.clone();
1015
1016         assert!(75 == *Arc::make_mut(&mut cow0));
1017         assert!(75 == *Arc::make_mut(&mut cow1));
1018         assert!(75 == *Arc::make_mut(&mut cow2));
1019
1020         *Arc::make_mut(&mut cow0) += 1;
1021         *Arc::make_mut(&mut cow1) += 2;
1022         *Arc::make_mut(&mut cow2) += 3;
1023
1024         assert!(76 == *cow0);
1025         assert!(77 == *cow1);
1026         assert!(78 == *cow2);
1027
1028         // none should point to the same backing memory
1029         assert!(*cow0 != *cow1);
1030         assert!(*cow0 != *cow2);
1031         assert!(*cow1 != *cow2);
1032     }
1033
1034     #[test]
1035     fn test_cowarc_clone_unique2() {
1036         let mut cow0 = Arc::new(75);
1037         let cow1 = cow0.clone();
1038         let cow2 = cow1.clone();
1039
1040         assert!(75 == *cow0);
1041         assert!(75 == *cow1);
1042         assert!(75 == *cow2);
1043
1044         *Arc::make_mut(&mut cow0) += 1;
1045         assert!(76 == *cow0);
1046         assert!(75 == *cow1);
1047         assert!(75 == *cow2);
1048
1049         // cow1 and cow2 should share the same contents
1050         // cow0 should have a unique reference
1051         assert!(*cow0 != *cow1);
1052         assert!(*cow0 != *cow2);
1053         assert!(*cow1 == *cow2);
1054     }
1055
1056     #[test]
1057     fn test_cowarc_clone_weak() {
1058         let mut cow0 = Arc::new(75);
1059         let cow1_weak = Arc::downgrade(&cow0);
1060
1061         assert!(75 == *cow0);
1062         assert!(75 == *cow1_weak.upgrade().unwrap());
1063
1064         *Arc::make_mut(&mut cow0) += 1;
1065
1066         assert!(76 == *cow0);
1067         assert!(cow1_weak.upgrade().is_none());
1068     }
1069
1070     #[test]
1071     fn test_live() {
1072         let x = Arc::new(5);
1073         let y = Arc::downgrade(&x);
1074         assert!(y.upgrade().is_some());
1075     }
1076
1077     #[test]
1078     fn test_dead() {
1079         let x = Arc::new(5);
1080         let y = Arc::downgrade(&x);
1081         drop(x);
1082         assert!(y.upgrade().is_none());
1083     }
1084
1085     #[test]
1086     fn weak_self_cyclic() {
1087         struct Cycle {
1088             x: Mutex<Option<Weak<Cycle>>>,
1089         }
1090
1091         let a = Arc::new(Cycle { x: Mutex::new(None) });
1092         let b = Arc::downgrade(&a.clone());
1093         *a.x.lock().unwrap() = Some(b);
1094
1095         // hopefully we don't double-free (or leak)...
1096     }
1097
1098     #[test]
1099     fn drop_arc() {
1100         let mut canary = atomic::AtomicUsize::new(0);
1101         let x = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
1102         drop(x);
1103         assert!(canary.load(Acquire) == 1);
1104     }
1105
1106     #[test]
1107     fn drop_arc_weak() {
1108         let mut canary = atomic::AtomicUsize::new(0);
1109         let arc = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
1110         let arc_weak = Arc::downgrade(&arc);
1111         assert!(canary.load(Acquire) == 0);
1112         drop(arc);
1113         assert!(canary.load(Acquire) == 1);
1114         drop(arc_weak);
1115     }
1116
1117     #[test]
1118     fn test_strong_count() {
1119         let a = Arc::new(0u32);
1120         assert!(Arc::strong_count(&a) == 1);
1121         let w = Arc::downgrade(&a);
1122         assert!(Arc::strong_count(&a) == 1);
1123         let b = w.upgrade().expect("");
1124         assert!(Arc::strong_count(&b) == 2);
1125         assert!(Arc::strong_count(&a) == 2);
1126         drop(w);
1127         drop(a);
1128         assert!(Arc::strong_count(&b) == 1);
1129         let c = b.clone();
1130         assert!(Arc::strong_count(&b) == 2);
1131         assert!(Arc::strong_count(&c) == 2);
1132     }
1133
1134     #[test]
1135     fn test_weak_count() {
1136         let a = Arc::new(0u32);
1137         assert!(Arc::strong_count(&a) == 1);
1138         assert!(Arc::weak_count(&a) == 0);
1139         let w = Arc::downgrade(&a);
1140         assert!(Arc::strong_count(&a) == 1);
1141         assert!(Arc::weak_count(&a) == 1);
1142         let x = w.clone();
1143         assert!(Arc::weak_count(&a) == 2);
1144         drop(w);
1145         drop(x);
1146         assert!(Arc::strong_count(&a) == 1);
1147         assert!(Arc::weak_count(&a) == 0);
1148         let c = a.clone();
1149         assert!(Arc::strong_count(&a) == 2);
1150         assert!(Arc::weak_count(&a) == 0);
1151         let d = Arc::downgrade(&c);
1152         assert!(Arc::weak_count(&c) == 1);
1153         assert!(Arc::strong_count(&c) == 2);
1154
1155         drop(a);
1156         drop(c);
1157         drop(d);
1158     }
1159
1160     #[test]
1161     fn show_arc() {
1162         let a = Arc::new(5u32);
1163         assert_eq!(format!("{:?}", a), "5");
1164     }
1165
1166     // Make sure deriving works with Arc<T>
1167     #[derive(Eq, Ord, PartialEq, PartialOrd, Clone, Debug, Default)]
1168     struct Foo {
1169         inner: Arc<i32>,
1170     }
1171
1172     #[test]
1173     fn test_unsized() {
1174         let x: Arc<[i32]> = Arc::new([1, 2, 3]);
1175         assert_eq!(format!("{:?}", x), "[1, 2, 3]");
1176         let y = Arc::downgrade(&x.clone());
1177         drop(x);
1178         assert!(y.upgrade().is_none());
1179     }
1180
1181     #[test]
1182     fn test_from_owned() {
1183         let foo = 123;
1184         let foo_arc = Arc::from(foo);
1185         assert!(123 == *foo_arc);
1186     }
1187
1188     #[test]
1189     fn test_new_weak() {
1190         let foo: Weak<usize> = Weak::new();
1191         assert!(foo.upgrade().is_none());
1192     }
1193 }
1194
1195 #[stable(feature = "rust1", since = "1.0.0")]
1196 impl<T: ?Sized> borrow::Borrow<T> for Arc<T> {
1197     fn borrow(&self) -> &T {
1198         &**self
1199     }
1200 }
1201
1202 #[stable(since = "1.5.0", feature = "smart_ptr_as_ref")]
1203 impl<T: ?Sized> AsRef<T> for Arc<T> {
1204     fn as_ref(&self) -> &T {
1205         &**self
1206     }
1207 }