From 1b6a04ca5504955c571d1c97504fb45ea0befee4 Mon Sep 17 00:00:00 2001
From: Valentin Popov <valentin@popov.link>
Date: Mon, 8 Jan 2024 01:21:28 +0400
Subject: Initial vendor packages
Signed-off-by: Valentin Popov <valentin@popov.link>
---
vendor/crossbeam-utils/src/sync/sharded_lock.rs | 636 ++++++++++++++++++++++++
1 file changed, 636 insertions(+)
create mode 100644 vendor/crossbeam-utils/src/sync/sharded_lock.rs
(limited to 'vendor/crossbeam-utils/src/sync/sharded_lock.rs')
diff --git a/vendor/crossbeam-utils/src/sync/sharded_lock.rs b/vendor/crossbeam-utils/src/sync/sharded_lock.rs
new file mode 100644
index 0000000..5aee56f
--- /dev/null
+++ b/vendor/crossbeam-utils/src/sync/sharded_lock.rs
@@ -0,0 +1,636 @@
+use std::cell::UnsafeCell;
+use std::collections::HashMap;
+use std::fmt;
+use std::marker::PhantomData;
+use std::mem;
+use std::ops::{Deref, DerefMut};
+use std::panic::{RefUnwindSafe, UnwindSafe};
+use std::sync::{LockResult, PoisonError, TryLockError, TryLockResult};
+use std::sync::{Mutex, RwLock, RwLockReadGuard, RwLockWriteGuard};
+use std::thread::{self, ThreadId};
+
+use crate::sync::once_lock::OnceLock;
+use crate::CachePadded;
+
+/// The number of shards per sharded lock. Must be a power of two.
+const NUM_SHARDS: usize = 8;
+
+/// A shard containing a single reader-writer lock.
+struct Shard {
+ /// The inner reader-writer lock.
+ lock: RwLock<()>,
+
+ /// The write-guard keeping this shard locked.
+ ///
+ /// Write operations will lock each shard and store the guard here. These guards get dropped at
+ /// the same time the big guard is dropped.
+ write_guard: UnsafeCell<Option<RwLockWriteGuard<'static, ()>>>,
+}
+
+/// A sharded reader-writer lock.
+///
+/// This lock is equivalent to [`RwLock`], except read operations are faster and write operations
+/// are slower.
+///
+/// A `ShardedLock` is internally made of a list of *shards*, each being a [`RwLock`] occupying a
+/// single cache line. Read operations will pick one of the shards depending on the current thread
+/// and lock it. Write operations need to lock all shards in succession.
+///
+/// By splitting the lock into shards, concurrent read operations will in most cases choose
+/// different shards and thus update different cache lines, which is good for scalability. However,
+/// write operations need to do more work and are therefore slower than usual.
+///
+/// The priority policy of the lock is dependent on the underlying operating system's
+/// implementation, and this type does not guarantee that any particular policy will be used.
+///
+/// # Poisoning
+///
+/// A `ShardedLock`, like [`RwLock`], will become poisoned on a panic. Note that it may only be
+/// poisoned if a panic occurs while a write operation is in progress. If a panic occurs in any
+/// read operation, the lock will not be poisoned.
+///
+/// # Examples
+///
+/// ```
+/// use crossbeam_utils::sync::ShardedLock;
+///
+/// let lock = ShardedLock::new(5);
+///
+/// // Any number of read locks can be held at once.
+/// {
+/// let r1 = lock.read().unwrap();
+/// let r2 = lock.read().unwrap();
+/// assert_eq!(*r1, 5);
+/// assert_eq!(*r2, 5);
+/// } // Read locks are dropped at this point.
+///
+/// // However, only one write lock may be held.
+/// {
+/// let mut w = lock.write().unwrap();
+/// *w += 1;
+/// assert_eq!(*w, 6);
+/// } // Write lock is dropped here.
+/// ```
+///
+/// [`RwLock`]: std::sync::RwLock
+pub struct ShardedLock<T: ?Sized> {
+ /// A list of locks protecting the internal data.
+ shards: Box<[CachePadded<Shard>]>,
+
+ /// The internal data.
+ value: UnsafeCell<T>,
+}
+
+unsafe impl<T: ?Sized + Send> Send for ShardedLock<T> {}
+unsafe impl<T: ?Sized + Send + Sync> Sync for ShardedLock<T> {}
+
+impl<T: ?Sized> UnwindSafe for ShardedLock<T> {}
+impl<T: ?Sized> RefUnwindSafe for ShardedLock<T> {}
+
+impl<T> ShardedLock<T> {
+ /// Creates a new sharded reader-writer lock.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ ///
+ /// let lock = ShardedLock::new(5);
+ /// ```
+ pub fn new(value: T) -> ShardedLock<T> {
+ ShardedLock {
+ shards: (0..NUM_SHARDS)
+ .map(|_| {
+ CachePadded::new(Shard {
+ lock: RwLock::new(()),
+ write_guard: UnsafeCell::new(None),
+ })
+ })
+ .collect::<Box<[_]>>(),
+ value: UnsafeCell::new(value),
+ }
+ }
+
+ /// Consumes this lock, returning the underlying data.
+ ///
+ /// # Errors
+ ///
+ /// This method will return an error if the lock is poisoned. A lock gets poisoned when a write
+ /// operation panics.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ ///
+ /// let lock = ShardedLock::new(String::new());
+ /// {
+ /// let mut s = lock.write().unwrap();
+ /// *s = "modified".to_owned();
+ /// }
+ /// assert_eq!(lock.into_inner().unwrap(), "modified");
+ /// ```
+ pub fn into_inner(self) -> LockResult<T> {
+ let is_poisoned = self.is_poisoned();
+ let inner = self.value.into_inner();
+
+ if is_poisoned {
+ Err(PoisonError::new(inner))
+ } else {
+ Ok(inner)
+ }
+ }
+}
+
+impl<T: ?Sized> ShardedLock<T> {
+ /// Returns `true` if the lock is poisoned.
+ ///
+ /// If another thread can still access the lock, it may become poisoned at any time. A `false`
+ /// result should not be trusted without additional synchronization.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ /// use std::sync::Arc;
+ /// use std::thread;
+ ///
+ /// let lock = Arc::new(ShardedLock::new(0));
+ /// let c_lock = lock.clone();
+ ///
+ /// let _ = thread::spawn(move || {
+ /// let _lock = c_lock.write().unwrap();
+ /// panic!(); // the lock gets poisoned
+ /// }).join();
+ /// assert_eq!(lock.is_poisoned(), true);
+ /// ```
+ pub fn is_poisoned(&self) -> bool {
+ self.shards[0].lock.is_poisoned()
+ }
+
+ /// Returns a mutable reference to the underlying data.
+ ///
+ /// Since this call borrows the lock mutably, no actual locking needs to take place.
+ ///
+ /// # Errors
+ ///
+ /// This method will return an error if the lock is poisoned. A lock gets poisoned when a write
+ /// operation panics.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ ///
+ /// let mut lock = ShardedLock::new(0);
+ /// *lock.get_mut().unwrap() = 10;
+ /// assert_eq!(*lock.read().unwrap(), 10);
+ /// ```
+ pub fn get_mut(&mut self) -> LockResult<&mut T> {
+ let is_poisoned = self.is_poisoned();
+ let inner = unsafe { &mut *self.value.get() };
+
+ if is_poisoned {
+ Err(PoisonError::new(inner))
+ } else {
+ Ok(inner)
+ }
+ }
+
+ /// Attempts to acquire this lock with shared read access.
+ ///
+ /// If the access could not be granted at this time, an error is returned. Otherwise, a guard
+ /// is returned which will release the shared access when it is dropped. This method does not
+ /// provide any guarantees with respect to the ordering of whether contentious readers or
+ /// writers will acquire the lock first.
+ ///
+ /// # Errors
+ ///
+ /// This method will return an error if the lock is poisoned. A lock gets poisoned when a write
+ /// operation panics.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ ///
+ /// let lock = ShardedLock::new(1);
+ ///
+ /// match lock.try_read() {
+ /// Ok(n) => assert_eq!(*n, 1),
+ /// Err(_) => unreachable!(),
+ /// };
+ /// ```
+ pub fn try_read(&self) -> TryLockResult<ShardedLockReadGuard<'_, T>> {
+ // Take the current thread index and map it to a shard index. Thread indices will tend to
+ // distribute shards among threads equally, thus reducing contention due to read-locking.
+ let current_index = current_index().unwrap_or(0);
+ let shard_index = current_index & (self.shards.len() - 1);
+
+ match self.shards[shard_index].lock.try_read() {
+ Ok(guard) => Ok(ShardedLockReadGuard {
+ lock: self,
+ _guard: guard,
+ _marker: PhantomData,
+ }),
+ Err(TryLockError::Poisoned(err)) => {
+ let guard = ShardedLockReadGuard {
+ lock: self,
+ _guard: err.into_inner(),
+ _marker: PhantomData,
+ };
+ Err(TryLockError::Poisoned(PoisonError::new(guard)))
+ }
+ Err(TryLockError::WouldBlock) => Err(TryLockError::WouldBlock),
+ }
+ }
+
+ /// Locks with shared read access, blocking the current thread until it can be acquired.
+ ///
+ /// The calling thread will be blocked until there are no more writers which hold the lock.
+ /// There may be other readers currently inside the lock when this method returns. This method
+ /// does not provide any guarantees with respect to the ordering of whether contentious readers
+ /// or writers will acquire the lock first.
+ ///
+ /// Returns a guard which will release the shared access when dropped.
+ ///
+ /// # Errors
+ ///
+ /// This method will return an error if the lock is poisoned. A lock gets poisoned when a write
+ /// operation panics.
+ ///
+ /// # Panics
+ ///
+ /// This method might panic when called if the lock is already held by the current thread.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ /// use std::sync::Arc;
+ /// use std::thread;
+ ///
+ /// let lock = Arc::new(ShardedLock::new(1));
+ /// let c_lock = lock.clone();
+ ///
+ /// let n = lock.read().unwrap();
+ /// assert_eq!(*n, 1);
+ ///
+ /// thread::spawn(move || {
+ /// let r = c_lock.read();
+ /// assert!(r.is_ok());
+ /// }).join().unwrap();
+ /// ```
+ pub fn read(&self) -> LockResult<ShardedLockReadGuard<'_, T>> {
+ // Take the current thread index and map it to a shard index. Thread indices will tend to
+ // distribute shards among threads equally, thus reducing contention due to read-locking.
+ let current_index = current_index().unwrap_or(0);
+ let shard_index = current_index & (self.shards.len() - 1);
+
+ match self.shards[shard_index].lock.read() {
+ Ok(guard) => Ok(ShardedLockReadGuard {
+ lock: self,
+ _guard: guard,
+ _marker: PhantomData,
+ }),
+ Err(err) => Err(PoisonError::new(ShardedLockReadGuard {
+ lock: self,
+ _guard: err.into_inner(),
+ _marker: PhantomData,
+ })),
+ }
+ }
+
+ /// Attempts to acquire this lock with exclusive write access.
+ ///
+ /// If the access could not be granted at this time, an error is returned. Otherwise, a guard
+ /// is returned which will release the exclusive access when it is dropped. This method does
+ /// not provide any guarantees with respect to the ordering of whether contentious readers or
+ /// writers will acquire the lock first.
+ ///
+ /// # Errors
+ ///
+ /// This method will return an error if the lock is poisoned. A lock gets poisoned when a write
+ /// operation panics.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ ///
+ /// let lock = ShardedLock::new(1);
+ ///
+ /// let n = lock.read().unwrap();
+ /// assert_eq!(*n, 1);
+ ///
+ /// assert!(lock.try_write().is_err());
+ /// ```
+ pub fn try_write(&self) -> TryLockResult<ShardedLockWriteGuard<'_, T>> {
+ let mut poisoned = false;
+ let mut blocked = None;
+
+ // Write-lock each shard in succession.
+ for (i, shard) in self.shards.iter().enumerate() {
+ let guard = match shard.lock.try_write() {
+ Ok(guard) => guard,
+ Err(TryLockError::Poisoned(err)) => {
+ poisoned = true;
+ err.into_inner()
+ }
+ Err(TryLockError::WouldBlock) => {
+ blocked = Some(i);
+ break;
+ }
+ };
+
+ // Store the guard into the shard.
+ unsafe {
+ let guard: RwLockWriteGuard<'static, ()> = mem::transmute(guard);
+ let dest: *mut _ = shard.write_guard.get();
+ *dest = Some(guard);
+ }
+ }
+
+ if let Some(i) = blocked {
+ // Unlock the shards in reverse order of locking.
+ for shard in self.shards[0..i].iter().rev() {
+ unsafe {
+ let dest: *mut _ = shard.write_guard.get();
+ let guard = (*dest).take();
+ drop(guard);
+ }
+ }
+ Err(TryLockError::WouldBlock)
+ } else if poisoned {
+ let guard = ShardedLockWriteGuard {
+ lock: self,
+ _marker: PhantomData,
+ };
+ Err(TryLockError::Poisoned(PoisonError::new(guard)))
+ } else {
+ Ok(ShardedLockWriteGuard {
+ lock: self,
+ _marker: PhantomData,
+ })
+ }
+ }
+
+ /// Locks with exclusive write access, blocking the current thread until it can be acquired.
+ ///
+ /// The calling thread will be blocked until there are no more writers which hold the lock.
+ /// There may be other readers currently inside the lock when this method returns. This method
+ /// does not provide any guarantees with respect to the ordering of whether contentious readers
+ /// or writers will acquire the lock first.
+ ///
+ /// Returns a guard which will release the exclusive access when dropped.
+ ///
+ /// # Errors
+ ///
+ /// This method will return an error if the lock is poisoned. A lock gets poisoned when a write
+ /// operation panics.
+ ///
+ /// # Panics
+ ///
+ /// This method might panic when called if the lock is already held by the current thread.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use crossbeam_utils::sync::ShardedLock;
+ ///
+ /// let lock = ShardedLock::new(1);
+ ///
+ /// let mut n = lock.write().unwrap();
+ /// *n = 2;
+ ///
+ /// assert!(lock.try_read().is_err());
+ /// ```
+ pub fn write(&self) -> LockResult<ShardedLockWriteGuard<'_, T>> {
+ let mut poisoned = false;
+
+ // Write-lock each shard in succession.
+ for shard in self.shards.iter() {
+ let guard = match shard.lock.write() {
+ Ok(guard) => guard,
+ Err(err) => {
+ poisoned = true;
+ err.into_inner()
+ }
+ };
+
+ // Store the guard into the shard.
+ unsafe {
+ let guard: RwLockWriteGuard<'_, ()> = guard;
+ let guard: RwLockWriteGuard<'static, ()> = mem::transmute(guard);
+ let dest: *mut _ = shard.write_guard.get();
+ *dest = Some(guard);
+ }
+ }
+
+ if poisoned {
+ Err(PoisonError::new(ShardedLockWriteGuard {
+ lock: self,
+ _marker: PhantomData,
+ }))
+ } else {
+ Ok(ShardedLockWriteGuard {
+ lock: self,
+ _marker: PhantomData,
+ })
+ }
+ }
+}
+
+impl<T: ?Sized + fmt::Debug> fmt::Debug for ShardedLock<T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self.try_read() {
+ Ok(guard) => f
+ .debug_struct("ShardedLock")
+ .field("data", &&*guard)
+ .finish(),
+ Err(TryLockError::Poisoned(err)) => f
+ .debug_struct("ShardedLock")
+ .field("data", &&**err.get_ref())
+ .finish(),
+ Err(TryLockError::WouldBlock) => {
+ struct LockedPlaceholder;
+ impl fmt::Debug for LockedPlaceholder {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.write_str("<locked>")
+ }
+ }
+ f.debug_struct("ShardedLock")
+ .field("data", &LockedPlaceholder)
+ .finish()
+ }
+ }
+ }
+}
+
+impl<T: Default> Default for ShardedLock<T> {
+ fn default() -> ShardedLock<T> {
+ ShardedLock::new(Default::default())
+ }
+}
+
+impl<T> From<T> for ShardedLock<T> {
+ fn from(t: T) -> Self {
+ ShardedLock::new(t)
+ }
+}
+
+/// A guard used to release the shared read access of a [`ShardedLock`] when dropped.
+#[clippy::has_significant_drop]
+pub struct ShardedLockReadGuard<'a, T: ?Sized> {
+ lock: &'a ShardedLock<T>,
+ _guard: RwLockReadGuard<'a, ()>,
+ _marker: PhantomData<RwLockReadGuard<'a, T>>,
+}
+
+unsafe impl<T: ?Sized + Sync> Sync for ShardedLockReadGuard<'_, T> {}
+
+impl<T: ?Sized> Deref for ShardedLockReadGuard<'_, T> {
+ type Target = T;
+
+ fn deref(&self) -> &T {
+ unsafe { &*self.lock.value.get() }
+ }
+}
+
+impl<T: fmt::Debug> fmt::Debug for ShardedLockReadGuard<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("ShardedLockReadGuard")
+ .field("lock", &self.lock)
+ .finish()
+ }
+}
+
+impl<T: ?Sized + fmt::Display> fmt::Display for ShardedLockReadGuard<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ (**self).fmt(f)
+ }
+}
+
+/// A guard used to release the exclusive write access of a [`ShardedLock`] when dropped.
+#[clippy::has_significant_drop]
+pub struct ShardedLockWriteGuard<'a, T: ?Sized> {
+ lock: &'a ShardedLock<T>,
+ _marker: PhantomData<RwLockWriteGuard<'a, T>>,
+}
+
+unsafe impl<T: ?Sized + Sync> Sync for ShardedLockWriteGuard<'_, T> {}
+
+impl<T: ?Sized> Drop for ShardedLockWriteGuard<'_, T> {
+ fn drop(&mut self) {
+ // Unlock the shards in reverse order of locking.
+ for shard in self.lock.shards.iter().rev() {
+ unsafe {
+ let dest: *mut _ = shard.write_guard.get();
+ let guard = (*dest).take();
+ drop(guard);
+ }
+ }
+ }
+}
+
+impl<T: fmt::Debug> fmt::Debug for ShardedLockWriteGuard<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("ShardedLockWriteGuard")
+ .field("lock", &self.lock)
+ .finish()
+ }
+}
+
+impl<T: ?Sized + fmt::Display> fmt::Display for ShardedLockWriteGuard<'_, T> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ (**self).fmt(f)
+ }
+}
+
+impl<T: ?Sized> Deref for ShardedLockWriteGuard<'_, T> {
+ type Target = T;
+
+ fn deref(&self) -> &T {
+ unsafe { &*self.lock.value.get() }
+ }
+}
+
+impl<T: ?Sized> DerefMut for ShardedLockWriteGuard<'_, T> {
+ fn deref_mut(&mut self) -> &mut T {
+ unsafe { &mut *self.lock.value.get() }
+ }
+}
+
+/// Returns a `usize` that identifies the current thread.
+///
+/// Each thread is associated with an 'index'. While there are no particular guarantees, indices
+/// usually tend to be consecutive numbers between 0 and the number of running threads.
+///
+/// Since this function accesses TLS, `None` might be returned if the current thread's TLS is
+/// tearing down.
+#[inline]
+fn current_index() -> Option<usize> {
+ REGISTRATION.try_with(|reg| reg.index).ok()
+}
+
+/// The global registry keeping track of registered threads and indices.
+struct ThreadIndices {
+ /// Mapping from `ThreadId` to thread index.
+ mapping: HashMap<ThreadId, usize>,
+
+ /// A list of free indices.
+ free_list: Vec<usize>,
+
+ /// The next index to allocate if the free list is empty.
+ next_index: usize,
+}
+
+fn thread_indices() -> &'static Mutex<ThreadIndices> {
+ static THREAD_INDICES: OnceLock<Mutex<ThreadIndices>> = OnceLock::new();
+ fn init() -> Mutex<ThreadIndices> {
+ Mutex::new(ThreadIndices {
+ mapping: HashMap::new(),
+ free_list: Vec::new(),
+ next_index: 0,
+ })
+ }
+ THREAD_INDICES.get_or_init(init)
+}
+
+/// A registration of a thread with an index.
+///
+/// When dropped, unregisters the thread and frees the reserved index.
+struct Registration {
+ index: usize,
+ thread_id: ThreadId,
+}
+
+impl Drop for Registration {
+ fn drop(&mut self) {
+ let mut indices = thread_indices().lock().unwrap();
+ indices.mapping.remove(&self.thread_id);
+ indices.free_list.push(self.index);
+ }
+}
+
+thread_local! {
+ static REGISTRATION: Registration = {
+ let thread_id = thread::current().id();
+ let mut indices = thread_indices().lock().unwrap();
+
+ let index = match indices.free_list.pop() {
+ Some(i) => i,
+ None => {
+ let i = indices.next_index;
+ indices.next_index += 1;
+ i
+ }
+ };
+ indices.mapping.insert(thread_id, index);
+
+ Registration {
+ index,
+ thread_id,
+ }
+ };
+}
--
cgit v1.2.3