Upgrade rust/crates/thread_local to 1.1.3 am: c37c85bc7a am: eff59296dc am: 1ca7eb5dcf am: 535cf3a070

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/thread_local/+/1581973

MUST ONLY BE SUBMITTED BY AUTOMERGER

Change-Id: I87b7446ea0aae1ac8183976228348c8dde906887

10 files changed, 252 insertions, 110 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 6382fe2..e9cf727 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "d9e93cbc8b8ff57351c65eb432323808da67744d"
+    "sha1": "c7d8dcdf4b93a5d80ec4075c3d8e7351c1a32012"
   }
 }
diff --git a/.travis.yml b/.travis.yml
index 1698520..16bf2d2 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -5,7 +5,7 @@ rust:
 - nightly
 - beta
 - stable
-- 1.28.0
+- 1.36.0
 
 before_script:
 - |
@@ -15,8 +15,9 @@ before_script:
 script:
 - travis-cargo build
 - travis-cargo test
-# Criterion doesn't build on 1.28.0
-- travis-cargo --skip 1.28.0 bench -- --features criterion
+- travis-cargo bench -- --features criterion
+# Criterion may drop support for 1.36.0 in the future. If it does, replace the above line with this:
+# - travis-cargo --skip 1.36.0 bench -- --features criterion
 - travis-cargo doc -- --no-deps
 
 after_success:
diff --git a/Android.bp b/Android.bp
index c73378b..1ebe227 100644
--- a/Android.bp
+++ b/Android.bp
@@ -40,9 +40,9 @@ rust_library_host {
     name: "libthread_local",
     crate_name: "thread_local",
     srcs: ["src/lib.rs"],
-    edition: "2015",
+    edition: "2018",
     rustlibs: [
-        "liblazy_static",
+        "libonce_cell",
     ],
 }
 
@@ -52,11 +52,14 @@ rust_test_host {
     srcs: ["src/lib.rs"],
     test_suites: ["general-tests"],
     auto_gen_config: true,
-    edition: "2015",
+    test_options: {
+        unit_test: true,
+    },
+    edition: "2018",
     rustlibs: [
-        "liblazy_static",
+        "libonce_cell",
     ],
 }
 
 // dependent_library ["feature_list"]
-//   lazy_static-1.4.0
+//   once_cell-1.5.2 "alloc,default,std"
diff --git a/Cargo.toml b/Cargo.toml
index 5f47295..3e76c4c 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,11 +11,12 @@
 # will likely look very different (and much more reasonable)
 
 [package]
+edition = "2018"
 name = "thread_local"
-version = "1.1.0"
+version = "1.1.3"
 authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
 description = "Per-object thread-local storage"
-documentation = "https://amanieu.github.io/thread_local-rs/thread_local/index.html"
+documentation = "https://docs.rs/thread_local/"
 readme = "README.md"
 keywords = ["thread_local", "concurrent", "thread"]
 license = "Apache-2.0/MIT"
@@ -29,8 +30,8 @@ required-features = ["criterion"]
 version = "0.3.3"
 optional = true
 
-[dependencies.lazy_static]
-version = "1.0"
+[dependencies.once_cell]
+version = "1.5.2"
 
 [dev-dependencies]
 [badges.travis-ci]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index d81a344..a56288f 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,19 +1,20 @@
 [package]
 name = "thread_local"
-version = "1.1.0"
+version = "1.1.3"
 authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
 description = "Per-object thread-local storage"
-documentation = "https://amanieu.github.io/thread_local-rs/thread_local/index.html"
+documentation = "https://docs.rs/thread_local/"
 license = "Apache-2.0/MIT"
 repository = "https://github.com/Amanieu/thread_local-rs"
 readme = "README.md"
 keywords = ["thread_local", "concurrent", "thread"]
+edition = "2018"
 
 [badges]
 travis-ci = { repository = "Amanieu/thread_local-rs" }
 
 [dependencies]
-lazy_static = "1.0"
+once_cell = "1.5.2"
 
 # This is actually a dev-dependency, see https://github.com/rust-lang/cargo/issues/1596
 criterion = { version = "0.3.3", optional = true }
diff --git a/METADATA b/METADATA
index 38d053b..ef2ed7c 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/thread_local/thread_local-1.1.0.crate"
+    value: "https://static.crates.io/crates/thread_local/thread_local-1.1.3.crate"
   }
-  version: "1.1.0"
+  version: "1.1.3"
   license_type: NOTICE
   last_upgrade_date {
     year: 2021
-    month: 1
-    day: 7
+    month: 2
+    day: 9
   }
 }
diff --git a/README.md b/README.md
index 891e168..6560356 100644
--- a/README.md
+++ b/README.md
@@ -8,7 +8,7 @@ object to be used for each thread. This allows for per-object thread-local
 storage, unlike the standard library's `thread_local!` macro which only allows
 static thread-local storage.
 
-[Documentation](https://amanieu.github.io/thread_local-rs/thread_local/index.html)
+[Documentation](https://docs.rs/thread_local/)
 
 ## Usage
 
@@ -16,18 +16,12 @@ Add this to your `Cargo.toml`:
 
 ```toml
 [dependencies]
-thread_local = "1.0"
-```
-
-and this to your crate root:
-
-```rust
-extern crate thread_local;
+thread_local = "1.1"
 ```
 
 ## Minimum Rust version
 
-This crate's minimum supported Rust version (MSRV) is 1.28.0.
+This crate's minimum supported Rust version (MSRV) is 1.36.0.
 
 ## License
 
diff --git a/TEST_MAPPING b/TEST_MAPPING
new file mode 100644
index 0000000..6551257
--- /dev/null
+++ b/TEST_MAPPING
@@ -0,0 +1,12 @@
+// Generated by update_crate_tests.py for tests that depend on this crate.
+{
+  "presubmit": [
+    {
+      "name": "keystore2_test"
+    },
+    {
+      "name": "libsqlite3-sys_device_test_src_lib"
+    }
+  ]
+}
+
diff --git a/src/lib.rs b/src/lib.rs
index 78bdcc3..f26f6ed 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -66,9 +66,6 @@
 #![warn(missing_docs)]
 #![allow(clippy::mutex_atomic)]
 
-#[macro_use]
-extern crate lazy_static;
-
 mod cached;
 mod thread_id;
 mod unreachable;
@@ -78,14 +75,15 @@ pub use cached::{CachedIntoIter, CachedIterMut, CachedThreadLocal};
 
 use std::cell::UnsafeCell;
 use std::fmt;
-use std::marker::PhantomData;
+use std::iter::FusedIterator;
 use std::mem;
+use std::mem::MaybeUninit;
 use std::panic::UnwindSafe;
 use std::ptr;
-use std::sync::atomic::{AtomicPtr, Ordering};
+use std::sync::atomic::{AtomicBool, AtomicPtr, AtomicUsize, Ordering};
 use std::sync::Mutex;
 use thread_id::Thread;
-use unreachable::{UncheckedOptionExt, UncheckedResultExt};
+use unreachable::UncheckedResultExt;
 
 // Use usize::BITS once it has stabilized and the MSRV has been bumped.
 #[cfg(target_pointer_width = "16")]
@@ -104,13 +102,31 @@ const BUCKETS: usize = (POINTER_WIDTH + 1) as usize;
 pub struct ThreadLocal<T: Send> {
     /// The buckets in the thread local. The nth bucket contains `2^(n-1)`
     /// elements. Each bucket is lazily allocated.
-    buckets: [AtomicPtr<UnsafeCell<Option<T>>>; BUCKETS],
+    buckets: [AtomicPtr<Entry<T>>; BUCKETS],
+
+    /// The number of values in the thread local. This can be less than the real number of values,
+    /// but is never more.
+    values: AtomicUsize,
 
     /// Lock used to guard against concurrent modifications. This is taken when
     /// there is a possibility of allocating a new bucket, which only occurs
-    /// when inserting values. This also guards the counter for the total number
-    /// of values in the thread local.
-    lock: Mutex<usize>,
+    /// when inserting values.
+    lock: Mutex<()>,
+}
+
+struct Entry<T> {
+    present: AtomicBool,
+    value: UnsafeCell<MaybeUninit<T>>,
+}
+
+impl<T> Drop for Entry<T> {
+    fn drop(&mut self) {
+        unsafe {
+            if *self.present.get_mut() {
+                ptr::drop_in_place((*self.value.get()).as_mut_ptr());
+            }
+        }
+    }
 }
 
 // ThreadLocal is always Sync, even if T isn't
@@ -173,7 +189,8 @@ impl<T: Send> ThreadLocal<T> {
             // Safety: AtomicPtr has the same representation as a pointer and arrays have the same
             // representation as a sequence of their inner type.
             buckets: unsafe { mem::transmute(buckets) },
-            lock: Mutex::new(0),
+            values: AtomicUsize::new(0),
+            lock: Mutex::new(()),
         }
     }
 
@@ -215,14 +232,21 @@ impl<T: Send> ThreadLocal<T> {
         if bucket_ptr.is_null() {
             return None;
         }
-        unsafe { (&*(&*bucket_ptr.add(thread.index)).get()).as_ref() }
+        unsafe {
+            let entry = &*bucket_ptr.add(thread.index);
+            // Read without atomic operations as only this thread can set the value.
+            if (&entry.present as *const _ as *const bool).read() {
+                Some(&*(&*entry.value.get()).as_ptr())
+            } else {
+                None
+            }
+        }
     }
 
     #[cold]
     fn insert(&self, thread: Thread, data: T) -> &T {
         // Lock the Mutex to ensure only a single thread is allocating buckets at once
-        let mut count = self.lock.lock().unwrap();
-        *count += 1;
+        let _guard = self.lock.lock().unwrap();
 
         let bucket_atomic_ptr = unsafe { self.buckets.get_unchecked(thread.bucket) };
 
@@ -236,25 +260,30 @@ impl<T: Send> ThreadLocal<T> {
             bucket_ptr
         };
 
-        drop(count);
+        drop(_guard);
 
         // Insert the new element into the bucket
-        unsafe {
-            let value_ptr = (&*bucket_ptr.add(thread.index)).get();
-            *value_ptr = Some(data);
-            (&*value_ptr).as_ref().unchecked_unwrap()
-        }
+        let entry = unsafe { &*bucket_ptr.add(thread.index) };
+        let value_ptr = entry.value.get();
+        unsafe { value_ptr.write(MaybeUninit::new(data)) };
+        entry.present.store(true, Ordering::Release);
+
+        self.values.fetch_add(1, Ordering::Release);
+
+        unsafe { &*(&*value_ptr).as_ptr() }
     }
 
-    fn raw_iter(&mut self) -> RawIter<T> {
-        RawIter {
-            remaining: *self.lock.get_mut().unwrap(),
-            buckets: unsafe {
-                *(&self.buckets as *const _ as *const [*const UnsafeCell<Option<T>>; BUCKETS])
-            },
-            bucket: 0,
-            bucket_size: 1,
-            index: 0,
+    /// Returns an iterator over the local values of all threads in unspecified
+    /// order.
+    ///
+    /// This call can be done safely, as `T` is required to implement [`Sync`].
+    pub fn iter(&self) -> Iter<'_, T>
+    where
+        T: Sync,
+    {
+        Iter {
+            thread_local: self,
+            raw: RawIter::new(),
         }
     }
 
@@ -266,8 +295,8 @@ impl<T: Send> ThreadLocal<T> {
     /// threads are currently accessing their associated values.
     pub fn iter_mut(&mut self) -> IterMut<T> {
         IterMut {
-            raw: self.raw_iter(),
-            marker: PhantomData,
+            thread_local: self,
+            raw: RawIter::new(),
         }
     }
 
@@ -286,15 +315,24 @@ impl<T: Send> IntoIterator for ThreadLocal<T> {
     type Item = T;
     type IntoIter = IntoIter<T>;
 
-    fn into_iter(mut self) -> IntoIter<T> {
+    fn into_iter(self) -> IntoIter<T> {
         IntoIter {
-            raw: self.raw_iter(),
-            _thread_local: self,
+            thread_local: self,
+            raw: RawIter::new(),
         }
     }
 }
 
-impl<'a, T: Send + 'a> IntoIterator for &'a mut ThreadLocal<T> {
+impl<'a, T: Send + Sync> IntoIterator for &'a ThreadLocal<T> {
+    type Item = &'a T;
+    type IntoIter = Iter<'a, T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, T: Send> IntoIterator for &'a mut ThreadLocal<T> {
     type Item = &'a mut T;
     type IntoIter = IterMut<'a, T>;
 
@@ -319,102 +357,171 @@ impl<T: Send + fmt::Debug> fmt::Debug for ThreadLocal<T> {
 
 impl<T: Send + UnwindSafe> UnwindSafe for ThreadLocal<T> {}
 
-struct RawIter<T: Send> {
-    remaining: usize,
-    buckets: [*const UnsafeCell<Option<T>>; BUCKETS],
+#[derive(Debug)]
+struct RawIter {
+    yielded: usize,
     bucket: usize,
     bucket_size: usize,
     index: usize,
 }
+impl RawIter {
+    #[inline]
+    fn new() -> Self {
+        Self {
+            yielded: 0,
+            bucket: 0,
+            bucket_size: 1,
+            index: 0,
+        }
+    }
 
-impl<T: Send> Iterator for RawIter<T> {
-    type Item = *mut Option<T>;
+    fn next<'a, T: Send + Sync>(&mut self, thread_local: &'a ThreadLocal<T>) -> Option<&'a T> {
+        while self.bucket < BUCKETS {
+            let bucket = unsafe { thread_local.buckets.get_unchecked(self.bucket) };
+            let bucket = bucket.load(Ordering::Relaxed);
 
-    fn next(&mut self) -> Option<Self::Item> {
-        if self.remaining == 0 {
+            if !bucket.is_null() {
+                while self.index < self.bucket_size {
+                    let entry = unsafe { &*bucket.add(self.index) };
+                    self.index += 1;
+                    if entry.present.load(Ordering::Acquire) {
+                        self.yielded += 1;
+                        return Some(unsafe { &*(&*entry.value.get()).as_ptr() });
+                    }
+                }
+            }
+
+            self.next_bucket();
+        }
+        None
+    }
+    fn next_mut<'a, T: Send>(
+        &mut self,
+        thread_local: &'a mut ThreadLocal<T>,
+    ) -> Option<&'a mut Entry<T>> {
+        if *thread_local.values.get_mut() == self.yielded {
             return None;
         }
 
         loop {
-            let bucket = unsafe { *self.buckets.get_unchecked(self.bucket) };
+            let bucket = unsafe { thread_local.buckets.get_unchecked_mut(self.bucket) };
+            let bucket = *bucket.get_mut();
 
             if !bucket.is_null() {
                 while self.index < self.bucket_size {
-                    let item = unsafe { (&*bucket.add(self.index)).get() };
-
+                    let entry = unsafe { &mut *bucket.add(self.index) };
                     self.index += 1;
-
-                    if unsafe { &*item }.is_some() {
-                        self.remaining -= 1;
-                        return Some(item);
+                    if *entry.present.get_mut() {
+                        self.yielded += 1;
+                        return Some(entry);
                     }
                 }
             }
 
-            if self.bucket != 0 {
-                self.bucket_size <<= 1;
-            }
-            self.bucket += 1;
+            self.next_bucket();
+        }
+    }
 
-            self.index = 0;
+    #[inline]
+    fn next_bucket(&mut self) {
+        if self.bucket != 0 {
+            self.bucket_size <<= 1;
         }
+        self.bucket += 1;
+        self.index = 0;
+    }
+
+    fn size_hint<T: Send>(&self, thread_local: &ThreadLocal<T>) -> (usize, Option<usize>) {
+        let total = thread_local.values.load(Ordering::Acquire);
+        (total - self.yielded, None)
+    }
+    fn size_hint_frozen<T: Send>(&self, thread_local: &ThreadLocal<T>) -> (usize, Option<usize>) {
+        let total = unsafe { *(&thread_local.values as *const AtomicUsize as *const usize) };
+        let remaining = total - self.yielded;
+        (remaining, Some(remaining))
     }
+}
+
+/// Iterator over the contents of a `ThreadLocal`.
+#[derive(Debug)]
+pub struct Iter<'a, T: Send + Sync> {
+    thread_local: &'a ThreadLocal<T>,
+    raw: RawIter,
+}
 
+impl<'a, T: Send + Sync> Iterator for Iter<'a, T> {
+    type Item = &'a T;
+    fn next(&mut self) -> Option<Self::Item> {
+        self.raw.next(self.thread_local)
+    }
     fn size_hint(&self) -> (usize, Option<usize>) {
-        (self.remaining, Some(self.remaining))
+        self.raw.size_hint(self.thread_local)
     }
 }
+impl<T: Send + Sync> FusedIterator for Iter<'_, T> {}
 
 /// Mutable iterator over the contents of a `ThreadLocal`.
-pub struct IterMut<'a, T: Send + 'a> {
-    raw: RawIter<T>,
-    marker: PhantomData<&'a mut ThreadLocal<T>>,
+pub struct IterMut<'a, T: Send> {
+    thread_local: &'a mut ThreadLocal<T>,
+    raw: RawIter,
 }
 
-impl<'a, T: Send + 'a> Iterator for IterMut<'a, T> {
+impl<'a, T: Send> Iterator for IterMut<'a, T> {
     type Item = &'a mut T;
-
     fn next(&mut self) -> Option<&'a mut T> {
         self.raw
-            .next()
-            .map(|x| unsafe { &mut *(*x).as_mut().unchecked_unwrap() })
+            .next_mut(self.thread_local)
+            .map(|entry| unsafe { &mut *(&mut *entry.value.get()).as_mut_ptr() })
     }
-
     fn size_hint(&self) -> (usize, Option<usize>) {
-        self.raw.size_hint()
+        self.raw.size_hint_frozen(self.thread_local)
     }
 }
 
-impl<'a, T: Send + 'a> ExactSizeIterator for IterMut<'a, T> {}
+impl<T: Send> ExactSizeIterator for IterMut<'_, T> {}
+impl<T: Send> FusedIterator for IterMut<'_, T> {}
+
+// Manual impl so we don't call Debug on the ThreadLocal, as doing so would create a reference to
+// this thread's value that potentially aliases with a mutable reference we have given out.
+impl<'a, T: Send + fmt::Debug> fmt::Debug for IterMut<'a, T> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("IterMut").field("raw", &self.raw).finish()
+    }
+}
 
 /// An iterator that moves out of a `ThreadLocal`.
+#[derive(Debug)]
 pub struct IntoIter<T: Send> {
-    raw: RawIter<T>,
-    _thread_local: ThreadLocal<T>,
+    thread_local: ThreadLocal<T>,
+    raw: RawIter,
 }
 
 impl<T: Send> Iterator for IntoIter<T> {
     type Item = T;
-
     fn next(&mut self) -> Option<T> {
-        self.raw
-            .next()
-            .map(|x| unsafe { (*x).take().unchecked_unwrap() })
+        self.raw.next_mut(&mut self.thread_local).map(|entry| {
+            *entry.present.get_mut() = false;
+            unsafe {
+                std::mem::replace(&mut *entry.value.get(), MaybeUninit::uninit()).assume_init()
+            }
+        })
     }
-
     fn size_hint(&self) -> (usize, Option<usize>) {
-        self.raw.size_hint()
+        self.raw.size_hint_frozen(&self.thread_local)
     }
 }
 
 impl<T: Send> ExactSizeIterator for IntoIter<T> {}
+impl<T: Send> FusedIterator for IntoIter<T> {}
 
-fn allocate_bucket<T>(size: usize) -> *mut UnsafeCell<Option<T>> {
+fn allocate_bucket<T>(size: usize) -> *mut Entry<T> {
     Box::into_raw(
         (0..size)
-            .map(|_| UnsafeCell::new(None::<T>))
-            .collect::<Vec<_>>()
-            .into_boxed_slice(),
+            .map(|_| Entry::<T> {
+                present: AtomicBool::new(false),
+                value: UnsafeCell::new(MaybeUninit::uninit()),
+            })
+            .collect(),
     ) as *mut _
 }
 
@@ -491,15 +598,38 @@ mod tests {
         .unwrap();
 
         let mut tls = Arc::try_unwrap(tls).unwrap();
+
+        let mut v = tls.iter().map(|x| **x).collect::<Vec<i32>>();
+        v.sort_unstable();
+        assert_eq!(vec![1, 2, 3], v);
+
         let mut v = tls.iter_mut().map(|x| **x).collect::<Vec<i32>>();
         v.sort_unstable();
         assert_eq!(vec![1, 2, 3], v);
+
         let mut v = tls.into_iter().map(|x| *x).collect::<Vec<i32>>();
         v.sort_unstable();
         assert_eq!(vec![1, 2, 3], v);
     }
 
     #[test]
+    fn test_drop() {
+        let local = ThreadLocal::new();
+        struct Dropped(Arc<AtomicUsize>);
+        impl Drop for Dropped {
+            fn drop(&mut self) {
+                self.0.fetch_add(1, Relaxed);
+            }
+        }
+
+        let dropped = Arc::new(AtomicUsize::new(0));
+        local.get_or(|| Dropped(dropped.clone()));
+        assert_eq!(dropped.load(Relaxed), 0);
+        drop(local);
+        assert_eq!(dropped.load(Relaxed), 1);
+    }
+
+    #[test]
     fn is_sync() {
         fn foo<T: Sync>() {}
         foo::<ThreadLocal<String>>();
diff --git a/src/thread_id.rs b/src/thread_id.rs
index 397f772..6eb0f61 100644
--- a/src/thread_id.rs
+++ b/src/thread_id.rs
@@ -5,11 +5,12 @@
 // http://opensource.org/licenses/MIT>, at your option. This file may not be
 // copied, modified, or distributed except according to those terms.
 
+use crate::POINTER_WIDTH;
+use once_cell::sync::Lazy;
 use std::cmp::Reverse;
 use std::collections::BinaryHeap;
 use std::sync::Mutex;
 use std::usize;
-use POINTER_WIDTH;
 
 /// Thread ID manager which allocates thread IDs. It attempts to aggressively
 /// reuse thread IDs where possible to avoid cases where a ThreadLocal grows
@@ -41,9 +42,8 @@ impl ThreadIdManager {
         self.free_list.push(Reverse(id));
     }
 }
-lazy_static! {
-    static ref THREAD_ID_MANAGER: Mutex<ThreadIdManager> = Mutex::new(ThreadIdManager::new());
-}
+static THREAD_ID_MANAGER: Lazy<Mutex<ThreadIdManager>> =
+    Lazy::new(|| Mutex::new(ThreadIdManager::new()));
 
 /// Data which is unique to the current thread while it is running.
 /// A thread ID may be reused after a thread exits.