summaryrefslogtreecommitdiffstats
path: root/vendor/sharded-slab
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-06-19 09:26:03 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-06-19 09:26:03 +0000
commit9918693037dce8aa4bb6f08741b6812923486c18 (patch)
tree21d2b40bec7e6a7ea664acee056eb3d08e15a1cf /vendor/sharded-slab
parentReleasing progress-linux version 1.75.0+dfsg1-5~progress7.99u1. (diff)
downloadrustc-9918693037dce8aa4bb6f08741b6812923486c18.tar.xz
rustc-9918693037dce8aa4bb6f08741b6812923486c18.zip
Merging upstream version 1.76.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/sharded-slab')
-rw-r--r--vendor/sharded-slab/.cargo-checksum.json2
-rw-r--r--vendor/sharded-slab/CHANGELOG.md35
-rw-r--r--vendor/sharded-slab/Cargo.toml44
-rw-r--r--vendor/sharded-slab/README.md8
-rw-r--r--vendor/sharded-slab/benches/bench.rs2
-rw-r--r--vendor/sharded-slab/flake.lock85
-rw-r--r--vendor/sharded-slab/flake.nix28
-rw-r--r--vendor/sharded-slab/rust-toolchain.toml7
-rw-r--r--vendor/sharded-slab/src/iter.rs14
-rw-r--r--vendor/sharded-slab/src/lib.rs26
-rw-r--r--vendor/sharded-slab/src/page/mod.rs4
-rw-r--r--vendor/sharded-slab/src/page/slot.rs18
-rw-r--r--vendor/sharded-slab/src/shard.rs14
-rw-r--r--vendor/sharded-slab/src/tests/custom_config.rs78
-rw-r--r--vendor/sharded-slab/src/tests/loom_slab.rs4
-rw-r--r--vendor/sharded-slab/src/tests/mod.rs4
-rw-r--r--vendor/sharded-slab/src/tests/properties.rs244
-rw-r--r--vendor/sharded-slab/src/tid.rs20
-rw-r--r--vendor/sharded-slab/tests/reserved_bits_leak.rs26
19 files changed, 617 insertions, 46 deletions
diff --git a/vendor/sharded-slab/.cargo-checksum.json b/vendor/sharded-slab/.cargo-checksum.json
index 2b594b836..6845015d1 100644
--- a/vendor/sharded-slab/.cargo-checksum.json
+++ b/vendor/sharded-slab/.cargo-checksum.json
@@ -1 +1 @@
-{"files":{"CHANGELOG.md":"9c0e06d18ed28fa4c4f0e010e392c0b3562c8ada22fcc2f22133d654686c7f15","Cargo.toml":"5967b83356e0272aa80a10f37dbec0bc2968f08bee6626c83a5be74d32ce767e","IMPLEMENTATION.md":"c192c8288dffc0ecbf41d59ae8b1664ea9b323b3dd16f99f3041019b464fb55e","LICENSE":"eafbfa606bc005ed7fd2f623d65af17ffe4ef7c017221ac14405bf4140771ea9","README.md":"4406c839a896217ab92e2f17d9162270d57b24204bcbbb12284a66cc72f3a40a","benches/bench.rs":"dd2b45ae38b3480537649d8fef80d566aa71c21933b59f3bb2200eb1793adc3b","bin/loom.sh":"903241204befb0f1f6e7ea98e2a24244c98e8567595c03af42f65b78a4b231c1","src/cfg.rs":"b26b129bd1e27f279f76b4ce3a7e2d22b092077be50dab3cfde195d6ea662d2d","src/clear.rs":"765537aa6a4c65d9b42d6eb46b3dd801c2723b5c5b6bcdcabf671d63278f938e","src/implementation.rs":"dec81aebb88e006ab405256fb16e8ecca6b07c3582c1c803bdfcc2a84b1d21cf","src/iter.rs":"a6880250c411471842cac8b9d28b7cbba4600ef33958530fd39ab54fbe2fdbe0","src/lib.rs":"b881289761889e91f7963a5e6d7d12377dc4600cac7b63fd69b06c8e2054d178","src/macros.rs":"3d22bc75b29c551e8a8cde347e61ebe7c981862190ca82bbf5f529ff7ec1d1dd","src/page/mod.rs":"1c61f1b42e2fab7e402ee22edac0dc71101da833fe4139651f4c79139e42d277","src/page/slot.rs":"053f3090af39e5d5205a969b808bf29eda34ce31e1c40c79b9e4ccfd60220332","src/page/stack.rs":"549853d1a2c1c15987eee89d4327c4592f274c3cc1c5b695e419bd460f61c5c4","src/pool.rs":"cf04cec4e24984a40c9300dc86baf6fb79432be7cd3a2276ad69a0c932be4098","src/shard.rs":"dd2e97d1357f7792b56a37d09e9598ccecfab3e3f8e602a3cf562978fa20e888","src/sync.rs":"9ad35bbb515f7e56c62b9e5e048a147a3490b419e2ebe79f66047674953f1689","src/tests/loom_pool.rs":"363bb7fbd6b99b870cc51ae3eb5b5a9cc02e5ef7ba0e5b83a495d7f1aab58dcc","src/tests/loom_slab.rs":"3d230cdf0048f02fc5046038e1574bc9c5f61972952aa21d86992e856161d3e6","src/tests/mod.rs":"44808a038c645f16ec26658a835fee815850f06563a2e680136b0fdbe6e44e39","src/tid.rs":"6a87728bebb947a47a9593d0274d1c332f4f6c4ffc733211546dc447de55d913"},"package":"900fba806f70c630b0a382d0d825e17a0f19fcd059a2ade1ff237bcddf446b31"} \ No newline at end of file
+{"files":{"CHANGELOG.md":"7e3afcfd86e5fb650b0193a4c6e5247bf8d82ca2162202883cdba2a55d1b1452","Cargo.toml":"972705c4e87d779dd18458a39b16c9d8438d32d22bbbbcf6065fdf281c7924b2","IMPLEMENTATION.md":"c192c8288dffc0ecbf41d59ae8b1664ea9b323b3dd16f99f3041019b464fb55e","LICENSE":"eafbfa606bc005ed7fd2f623d65af17ffe4ef7c017221ac14405bf4140771ea9","README.md":"51409ab641f970e4bb7e04286344f38ba6b12b6d676e1e26211234b717e60da9","benches/bench.rs":"456f5e671097eaecfa65f828a7e7eae99765d7b63e3c385cf849897c3dcb2c22","bin/loom.sh":"903241204befb0f1f6e7ea98e2a24244c98e8567595c03af42f65b78a4b231c1","flake.lock":"4db51b12a0e28f1580d1c352f0296f335fbee21b8317e9cb96ef5bb6381a625c","flake.nix":"50a7df609933d62aff26d31e5814fee12e9ef67a6a2de6e5753400d2f1193956","rust-toolchain.toml":"390f502d778894a0073b46950ad61b78fa7ce285a9ef2dd26a88b65d5bce591b","src/cfg.rs":"b26b129bd1e27f279f76b4ce3a7e2d22b092077be50dab3cfde195d6ea662d2d","src/clear.rs":"765537aa6a4c65d9b42d6eb46b3dd801c2723b5c5b6bcdcabf671d63278f938e","src/implementation.rs":"dec81aebb88e006ab405256fb16e8ecca6b07c3582c1c803bdfcc2a84b1d21cf","src/iter.rs":"7abf7e6d283e04aabee5e8abc391540c4e731c2b26ab9a1a62d915fbf772abfc","src/lib.rs":"6cf3dbf8b7f5d7f5a8a3f6570990a943befccaee9e0fe1f710734b0bf3537642","src/macros.rs":"3d22bc75b29c551e8a8cde347e61ebe7c981862190ca82bbf5f529ff7ec1d1dd","src/page/mod.rs":"07e1d1fd2f02d97cd251c20b6c258df55c866c991ddc8fae46e29f23a1baf57a","src/page/slot.rs":"c9b815d074a76a47c146d9e5ee1a0414595db520ff7367ccbd640a9a05b74de2","src/page/stack.rs":"549853d1a2c1c15987eee89d4327c4592f274c3cc1c5b695e419bd460f61c5c4","src/pool.rs":"cf04cec4e24984a40c9300dc86baf6fb79432be7cd3a2276ad69a0c932be4098","src/shard.rs":"b2ac1b210b778ffa312b7013948735b3c5b73f65f2f8356ffef5ce4797ea8fdc","src/sync.rs":"9ad35bbb515f7e56c62b9e5e048a147a3490b419e2ebe79f66047674953f1689","src/tests/custom_config.rs":"4776d2eea5c4bcfc8d2767c184a54a885caaeed0f4cb9779975ec0e36aa0bd1e","src/tests/loom_pool.rs":"363bb7fbd6b99b870cc51ae3eb5b5a9cc02e5ef7ba0e5b83a495d7f1aab58dcc","src/tests/loom_slab.rs":"8106d494eda2be06e9fb69625c4e0bec463c64b8971c09a137acb3b8ad342403","src/tests/mod.rs":"d809497c204d674e7178f0fd41249b554905d8c6bf88e12dc997a951ae42ce2d","src/tests/properties.rs":"7e80ae17631dc0319266b7af080465c821c7b81f5f6baa045195a67675156908","src/tid.rs":"a8ba7c3f1a397e3a55d83ba32f9f1cc24137c249700cf44cb3cd0d2ed14f8065","tests/reserved_bits_leak.rs":"94b027496efdc63bae420b3f52b5114c9e1ac226ec0f96844d158fecc6cd1a3f"},"package":"f40ca3c46823713e0d4209592e8d6e826aa57e928f09752619fc696c499637f6"} \ No newline at end of file
diff --git a/vendor/sharded-slab/CHANGELOG.md b/vendor/sharded-slab/CHANGELOG.md
index 9dc7c2f70..6b6ed2d1c 100644
--- a/vendor/sharded-slab/CHANGELOG.md
+++ b/vendor/sharded-slab/CHANGELOG.md
@@ -1,3 +1,38 @@
+<a name="v0.1.7"></a>
+### v0.1.7 (2023-10-04)
+
+
+#### Bug Fixes
+
+* index out of bounds in `get()` and `get_owned()` (#88) ([fdbc930f](https://github.com/hawkw/sharded-slab/commit/fdbc930fb14b0f6f8b77cd6efdad5a1bdf8d3c04))
+* **unique_iter:** prevent panics if a slab is empty (#88) ([bd599e0b](https://github.com/hawkw/sharded-slab/commit/bd599e0b2a60a953f25f27ba1fa86682150e05c2), closes [#73](https://github.com/hawkw/sharded-slab/issues/73))
+
+
+
+<a name="0.1.6"></a>
+## 0.1.6 (2023-09-27)
+
+
+#### Features
+
+* publicly export `UniqueIter` (#87) ([e4d6482d](https://github.com/hawkw/sharded-slab/commit/e4d6482db05d5767b47eae1b0217faad30f2ebd5), closes [#77](https://github.com/hawkw/sharded-slab/issues/77))
+
+#### Bug Fixes
+
+* use a smaller `CustomConfig` for 32-bit tests (#84) ([828ffff9](https://github.com/hawkw/sharded-slab/commit/828ffff9f82cfc41ed66b4743563c4dddc97c1ce), closes [#82](https://github.com/hawkw/sharded-slab/issues/82))
+
+
+
+<a name="0.1.5"></a>
+## 0.1.5 (2023-08-28)
+
+
+#### Bug Fixes
+
+* **Slab:** invalid generation in case of custom config (#80) ([ca090279](https://github.com/hawkw/sharded-slab/commit/ca09027944812d024676029a3dde62d27ef22015))
+
+
+
<a name="0.1.4"></a>
### 0.1.4 (2021-10-12)
diff --git a/vendor/sharded-slab/Cargo.toml b/vendor/sharded-slab/Cargo.toml
index 210621ade..83d792d3d 100644
--- a/vendor/sharded-slab/Cargo.toml
+++ b/vendor/sharded-slab/Cargo.toml
@@ -11,41 +11,67 @@
[package]
edition = "2018"
+rust-version = "1.42.0"
name = "sharded-slab"
-version = "0.1.4"
+version = "0.1.7"
authors = ["Eliza Weisman <eliza@buoyant.io>"]
-description = "A lock-free concurrent slab.\n"
+description = """
+A lock-free concurrent slab.
+"""
homepage = "https://github.com/hawkw/sharded-slab"
-documentation = "https://docs.rs/sharded-slab/0.1.4/sharded_slab"
+documentation = "https://docs.rs/sharded-slab/"
readme = "README.md"
-keywords = ["slab", "allocator", "lock-free", "atomic"]
-categories = ["memory-management", "data-structures", "concurrency"]
+keywords = [
+ "slab",
+ "allocator",
+ "lock-free",
+ "atomic",
+]
+categories = [
+ "memory-management",
+ "data-structures",
+ "concurrency",
+]
license = "MIT"
repository = "https://github.com/hawkw/sharded-slab"
+
[package.metadata.docs.rs]
all-features = true
-rustdoc-args = ["--cfg", "docsrs"]
+rustdoc-args = [
+ "--cfg",
+ "docsrs",
+]
[[bench]]
name = "bench"
harness = false
+
[dependencies.lazy_static]
version = "1"
+
[dev-dependencies.criterion]
version = "0.3"
-[dev-dependencies.loom]
-version = "0.5"
-features = ["checkpoint"]
+[dev-dependencies.indexmap]
+version = "1"
+
+[dev-dependencies.memory-stats]
+version = "1"
[dev-dependencies.proptest]
version = "1"
[dev-dependencies.slab]
version = "0.4.2"
+
[target."cfg(loom)".dependencies.loom]
version = "0.5"
features = ["checkpoint"]
optional = true
+
+[target."cfg(loom)".dev-dependencies.loom]
+version = "0.5"
+features = ["checkpoint"]
+
[badges.maintenance]
status = "experimental"
diff --git a/vendor/sharded-slab/README.md b/vendor/sharded-slab/README.md
index ea4be64ea..45274b4b0 100644
--- a/vendor/sharded-slab/README.md
+++ b/vendor/sharded-slab/README.md
@@ -11,7 +11,7 @@ A lock-free concurrent slab.
[crates-badge]: https://img.shields.io/crates/v/sharded-slab.svg
[crates-url]: https://crates.io/crates/sharded-slab
[docs-badge]: https://docs.rs/sharded-slab/badge.svg
-[docs-url]: https://docs.rs/sharded-slab/0.1.4/sharded_slab
+[docs-url]: https://docs.rs/sharded-slab/latest
[ci-badge]: https://github.com/hawkw/sharded-slab/workflows/CI/badge.svg
[ci-url]: https://github.com/hawkw/sharded-slab/actions?workflow=CI
[license-badge]: https://img.shields.io/crates/l/sharded-slab
@@ -35,7 +35,7 @@ optimization, and there may still be some lurking bugs.
First, add this to your `Cargo.toml`:
```toml
-sharded-slab = "0.1.1"
+sharded-slab = "0.1.7"
```
This crate provides two types, [`Slab`] and [`Pool`], which provide slightly
@@ -127,7 +127,7 @@ assert_eq!(hello.as_str(), "hello everyone!");
## Comparison with Similar Crates
-- [`slab`]: Carl Lerche's `slab` crate provides a slab implementation with a
+- [`slab`][slab crate]: Carl Lerche's `slab` crate provides a slab implementation with a
similar API, implemented by storing all data in a single vector.
Unlike `sharded-slab`, inserting and removing elements from the slab requires
@@ -150,7 +150,7 @@ assert_eq!(hello.as_str(), "hello everyone!");
concurrent use-cases, while `slab` should be preferred in single-threaded
use-cases.
-[`slab`]: https://crates.io/crates/slab
+[slab crate]: https://crates.io/crates/slab
## Safety and Correctness
diff --git a/vendor/sharded-slab/benches/bench.rs b/vendor/sharded-slab/benches/bench.rs
index c95bd4e38..21879c14c 100644
--- a/vendor/sharded-slab/benches/bench.rs
+++ b/vendor/sharded-slab/benches/bench.rs
@@ -26,7 +26,7 @@ impl<T: Send + Sync + 'static> MultithreadedBench<T> {
let end = self.end.clone();
let slab = self.slab.clone();
thread::spawn(move || {
- f(&*start, &*slab);
+ f(&start, &*slab);
end.wait();
});
self
diff --git a/vendor/sharded-slab/flake.lock b/vendor/sharded-slab/flake.lock
new file mode 100644
index 000000000..cfcd9939c
--- /dev/null
+++ b/vendor/sharded-slab/flake.lock
@@ -0,0 +1,85 @@
+{
+ "nodes": {
+ "flake-utils": {
+ "inputs": {
+ "systems": "systems"
+ },
+ "locked": {
+ "lastModified": 1692799911,
+ "narHash": "sha256-3eihraek4qL744EvQXsK1Ha6C3CR7nnT8X2qWap4RNk=",
+ "owner": "numtide",
+ "repo": "flake-utils",
+ "rev": "f9e7cf818399d17d347f847525c5a5a8032e4e44",
+ "type": "github"
+ },
+ "original": {
+ "owner": "numtide",
+ "repo": "flake-utils",
+ "type": "github"
+ }
+ },
+ "nixpkgs": {
+ "locked": {
+ "lastModified": 1693158576,
+ "narHash": "sha256-aRTTXkYvhXosGx535iAFUaoFboUrZSYb1Ooih/auGp0=",
+ "owner": "NixOS",
+ "repo": "nixpkgs",
+ "rev": "a999c1cc0c9eb2095729d5aa03e0d8f7ed256780",
+ "type": "github"
+ },
+ "original": {
+ "owner": "NixOS",
+ "ref": "nixos-unstable",
+ "repo": "nixpkgs",
+ "type": "github"
+ }
+ },
+ "root": {
+ "inputs": {
+ "flake-utils": "flake-utils",
+ "nixpkgs": "nixpkgs",
+ "rust-overlay": "rust-overlay"
+ }
+ },
+ "rust-overlay": {
+ "inputs": {
+ "flake-utils": [
+ "flake-utils"
+ ],
+ "nixpkgs": [
+ "nixpkgs"
+ ]
+ },
+ "locked": {
+ "lastModified": 1693188660,
+ "narHash": "sha256-F8vlVcYoEBRJqV3pN2QNSCI/A2i77ad5R9iiZ4llt1A=",
+ "owner": "oxalica",
+ "repo": "rust-overlay",
+ "rev": "23756b2c5594da5c1ad2f40ae2440b9f8a2165b7",
+ "type": "github"
+ },
+ "original": {
+ "owner": "oxalica",
+ "repo": "rust-overlay",
+ "type": "github"
+ }
+ },
+ "systems": {
+ "locked": {
+ "lastModified": 1681028828,
+ "narHash": "sha256-Vy1rq5AaRuLzOxct8nz4T6wlgyUR7zLU309k9mBC768=",
+ "owner": "nix-systems",
+ "repo": "default",
+ "rev": "da67096a3b9bf56a91d16901293e51ba5b49a27e",
+ "type": "github"
+ },
+ "original": {
+ "owner": "nix-systems",
+ "repo": "default",
+ "type": "github"
+ }
+ }
+ },
+ "root": "root",
+ "version": 7
+}
diff --git a/vendor/sharded-slab/flake.nix b/vendor/sharded-slab/flake.nix
new file mode 100644
index 000000000..a38cc2a10
--- /dev/null
+++ b/vendor/sharded-slab/flake.nix
@@ -0,0 +1,28 @@
+# in flake.nix
+{
+ description =
+ "Flake containing a development shell for the `sharded-slab` crate";
+
+ inputs = {
+ nixpkgs.url = "github:NixOS/nixpkgs/nixos-unstable";
+ flake-utils.url = "github:numtide/flake-utils";
+ rust-overlay = {
+ url = "github:oxalica/rust-overlay";
+ inputs = {
+ nixpkgs.follows = "nixpkgs";
+ flake-utils.follows = "flake-utils";
+ };
+ };
+ };
+
+ outputs = { self, nixpkgs, flake-utils, rust-overlay }:
+ flake-utils.lib.eachDefaultSystem (system:
+ let
+ overlays = [ (import rust-overlay) ];
+ pkgs = import nixpkgs { inherit system overlays; };
+ rustToolchain = pkgs.pkgsBuildHost.rust-bin.stable.latest.default;
+ nativeBuildInputs = with pkgs; [ rustToolchain pkg-config ];
+ in with pkgs; {
+ devShells.default = mkShell { inherit nativeBuildInputs; };
+ });
+}
diff --git a/vendor/sharded-slab/rust-toolchain.toml b/vendor/sharded-slab/rust-toolchain.toml
new file mode 100644
index 000000000..9a1c30690
--- /dev/null
+++ b/vendor/sharded-slab/rust-toolchain.toml
@@ -0,0 +1,7 @@
+[toolchain]
+channel = "stable"
+profile = "default"
+targets = [
+ "i686-unknown-linux-musl",
+ "x86_64-unknown-linux-gnu",
+] \ No newline at end of file
diff --git a/vendor/sharded-slab/src/iter.rs b/vendor/sharded-slab/src/iter.rs
index 54189aa57..e70bebe16 100644
--- a/vendor/sharded-slab/src/iter.rs
+++ b/vendor/sharded-slab/src/iter.rs
@@ -1,15 +1,19 @@
-use crate::{page, shard};
-use std::slice;
+use std::{iter::FusedIterator, slice};
+use crate::{cfg, page, shard};
+
+/// An exclusive fused iterator over the items in a [`Slab`](crate::Slab).
+#[must_use = "iterators are lazy and do nothing unless consumed"]
#[derive(Debug)]
-pub struct UniqueIter<'a, T, C: crate::cfg::Config> {
+pub struct UniqueIter<'a, T, C: cfg::Config> {
pub(super) shards: shard::IterMut<'a, Option<T>, C>,
pub(super) pages: slice::Iter<'a, page::Shared<Option<T>, C>>,
pub(super) slots: Option<page::Iter<'a, T, C>>,
}
-impl<'a, T, C: crate::cfg::Config> Iterator for UniqueIter<'a, T, C> {
+impl<'a, T, C: cfg::Config> Iterator for UniqueIter<'a, T, C> {
type Item = &'a T;
+
fn next(&mut self) -> Option<Self::Item> {
test_println!("UniqueIter::next");
loop {
@@ -37,3 +41,5 @@ impl<'a, T, C: crate::cfg::Config> Iterator for UniqueIter<'a, T, C> {
}
}
}
+
+impl<T, C: cfg::Config> FusedIterator for UniqueIter<'_, T, C> {}
diff --git a/vendor/sharded-slab/src/lib.rs b/vendor/sharded-slab/src/lib.rs
index e57cf50e2..ea9b66de3 100644
--- a/vendor/sharded-slab/src/lib.rs
+++ b/vendor/sharded-slab/src/lib.rs
@@ -215,8 +215,11 @@ mod page;
mod shard;
mod tid;
-pub use cfg::{Config, DefaultConfig};
-pub use clear::Clear;
+pub use self::{
+ cfg::{Config, DefaultConfig},
+ clear::Clear,
+ iter::UniqueIter,
+};
#[doc(inline)]
pub use pool::Pool;
@@ -735,15 +738,26 @@ impl<T, C: cfg::Config> Slab<T, C> {
}
/// Returns an iterator over all the items in the slab.
+ ///
+ /// Because this iterator exclusively borrows the slab (i.e. it holds an
+ /// `&mut Slab<T>`), elements will not be added or removed while the
+ /// iteration is in progress.
pub fn unique_iter(&mut self) -> iter::UniqueIter<'_, T, C> {
let mut shards = self.shards.iter_mut();
- let shard = shards.next().expect("must be at least 1 shard");
- let mut pages = shard.iter();
- let slots = pages.next().and_then(page::Shared::iter);
+
+ let (pages, slots) = match shards.next() {
+ Some(shard) => {
+ let mut pages = shard.iter();
+ let slots = pages.next().and_then(page::Shared::iter);
+ (pages, slots)
+ }
+ None => ([].iter(), None),
+ };
+
iter::UniqueIter {
shards,
- slots,
pages,
+ slots,
}
}
}
diff --git a/vendor/sharded-slab/src/page/mod.rs b/vendor/sharded-slab/src/page/mod.rs
index 0499fb535..a82c247d2 100644
--- a/vendor/sharded-slab/src/page/mod.rs
+++ b/vendor/sharded-slab/src/page/mod.rs
@@ -247,7 +247,7 @@ where
}
pub(crate) fn iter(&self) -> Option<Iter<'a, T, C>> {
- let slab = self.slab.with(|slab| unsafe { (&*slab).as_ref() });
+ let slab = self.slab.with(|slab| unsafe { (*slab).as_ref() });
slab.map(|slab| {
slab.iter()
.filter_map(Shared::make_ref as fn(&'a Slot<Option<T>, C>) -> Option<&'a T>)
@@ -402,7 +402,7 @@ impl<C: cfg::Config> Ord for Addr<C> {
impl<C: cfg::Config> Clone for Addr<C> {
fn clone(&self) -> Self {
- Self::from_usize(self.addr)
+ *self
}
}
diff --git a/vendor/sharded-slab/src/page/slot.rs b/vendor/sharded-slab/src/page/slot.rs
index 3387d5388..bb3f9ac13 100644
--- a/vendor/sharded-slab/src/page/slot.rs
+++ b/vendor/sharded-slab/src/page/slot.rs
@@ -134,7 +134,7 @@ where
let new_refs = refs.incr()?;
match self.lifecycle.compare_exchange(
lifecycle,
- new_refs.pack(current_gen.pack(state.pack(0))),
+ new_refs.pack(lifecycle),
Ordering::AcqRel,
Ordering::Acquire,
) {
@@ -242,7 +242,7 @@ where
let mut spin_exp = 0;
let next_gen = gen.advance();
loop {
- let current_gen = Generation::from_packed(lifecycle);
+ let current_gen = LifecycleGen::from_packed(lifecycle).0;
test_println!("-> release_with; lifecycle={:#x}; expected_gen={:?}; current_gen={:?}; next_gen={:?};",
lifecycle,
gen,
@@ -261,7 +261,7 @@ where
match self.lifecycle.compare_exchange(
lifecycle,
- next_gen.pack(lifecycle),
+ LifecycleGen(next_gen).pack(lifecycle),
Ordering::AcqRel,
Ordering::Acquire,
) {
@@ -499,8 +499,9 @@ impl<T, C: cfg::Config> Slot<T, C> {
// Are we the last guard, and is the slot marked for removal?
let dropping = refs.value == 1 && state == State::Marked;
let new_lifecycle = if dropping {
- // If so, we want to advance the state to "removing"
- gen.pack(State::Removing as usize)
+ // If so, we want to advance the state to "removing".
+ // Also, reset the ref count to 0.
+ LifecycleGen(gen).pack(State::Removing as usize)
} else {
// Otherwise, just subtract 1 from the ref count.
refs.decr().pack(lifecycle)
@@ -583,7 +584,7 @@ impl<C: cfg::Config> Ord for Generation<C> {
impl<C: cfg::Config> Clone for Generation<C> {
fn clone(&self) -> Self {
- Self::new(self.value)
+ *self
}
}
@@ -747,7 +748,7 @@ impl<C: cfg::Config> Ord for RefCount<C> {
impl<C: cfg::Config> Clone for RefCount<C> {
fn clone(&self) -> Self {
- Self::from_usize(self.value)
+ *self
}
}
@@ -875,7 +876,8 @@ impl<T, C: cfg::Config> InitGuard<T, C> {
debug_assert!(state == State::Marked || thread::panicking(), "state was not MARKED; someone else has removed the slot while we have exclusive access!\nactual={:?}", state);
debug_assert!(refs.value == 0 || thread::panicking(), "ref count was not 0; someone else has referenced the slot while we have exclusive access!\nactual={:?}", refs);
- let new_lifecycle = self.generation().pack(State::Removing as usize);
+
+ let new_lifecycle = LifecycleGen(self.generation()).pack(State::Removing as usize);
match slot.lifecycle.compare_exchange(
curr_lifecycle,
diff --git a/vendor/sharded-slab/src/shard.rs b/vendor/sharded-slab/src/shard.rs
index 0d054d7e5..b77a9fcb0 100644
--- a/vendor/sharded-slab/src/shard.rs
+++ b/vendor/sharded-slab/src/shard.rs
@@ -77,7 +77,7 @@ where
let (addr, page_index) = page::indices::<C>(idx);
test_println!("-> {:?}", addr);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return None;
}
@@ -132,7 +132,7 @@ where
debug_assert_eq_in_drop!(Tid::<C>::from_packed(idx).as_usize(), self.tid);
let (addr, page_index) = page::indices::<C>(idx);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return false;
}
@@ -143,7 +143,7 @@ where
debug_assert_eq_in_drop!(Tid::<C>::from_packed(idx).as_usize(), self.tid);
let (addr, page_index) = page::indices::<C>(idx);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return false;
}
@@ -183,7 +183,7 @@ where
debug_assert_eq_in_drop!(Tid::<C>::from_packed(idx).as_usize(), self.tid);
let (addr, page_index) = page::indices::<C>(idx);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return false;
}
@@ -194,7 +194,7 @@ where
debug_assert_eq_in_drop!(Tid::<C>::from_packed(idx).as_usize(), self.tid);
let (addr, page_index) = page::indices::<C>(idx);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return false;
}
@@ -221,7 +221,7 @@ where
debug_assert_eq_in_drop!(Tid::<C>::from_packed(idx).as_usize(), self.tid);
let (addr, page_index) = page::indices::<C>(idx);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return false;
}
@@ -232,7 +232,7 @@ where
debug_assert_eq_in_drop!(Tid::<C>::from_packed(idx).as_usize(), self.tid);
let (addr, page_index) = page::indices::<C>(idx);
- if page_index > self.shared.len() {
+ if page_index >= self.shared.len() {
return false;
}
diff --git a/vendor/sharded-slab/src/tests/custom_config.rs b/vendor/sharded-slab/src/tests/custom_config.rs
new file mode 100644
index 000000000..77f725935
--- /dev/null
+++ b/vendor/sharded-slab/src/tests/custom_config.rs
@@ -0,0 +1,78 @@
+//! Ensures that a custom config behaves as the default config, until limits are reached.
+//! Prevents regression after #80.
+
+use crate::{cfg::CfgPrivate, Config, Slab};
+
+struct CustomConfig;
+
+#[cfg(target_pointer_width = "64")]
+impl Config for CustomConfig {
+ const INITIAL_PAGE_SIZE: usize = 32;
+ const MAX_PAGES: usize = 15;
+ const MAX_THREADS: usize = 256;
+ const RESERVED_BITS: usize = 24;
+}
+
+#[cfg(not(target_pointer_width = "64"))]
+impl Config for CustomConfig {
+ const INITIAL_PAGE_SIZE: usize = 16;
+ const MAX_PAGES: usize = 6;
+ const MAX_THREADS: usize = 128;
+ const RESERVED_BITS: usize = 12;
+}
+
+// We should repeat actions several times to detect invalid lifecycle changes.
+const ITERS: u64 = 5;
+
+#[track_caller]
+fn slab_eq(mut lhs: Slab<u64, impl Config>, mut rhs: Slab<u64, impl Config>) {
+ let mut lhs_vec = lhs.unique_iter().collect::<Vec<_>>();
+ lhs_vec.sort_unstable();
+ let mut rhs_vec = rhs.unique_iter().collect::<Vec<_>>();
+ rhs_vec.sort_unstable();
+ assert_eq!(lhs_vec, rhs_vec);
+}
+
+/// Calls `insert(); remove()` multiple times to detect invalid releasing.
+/// Initially, it revealed bugs in the `Slot::release_with()` implementation.
+#[test]
+fn insert_remove() {
+ eprintln!("bits={}; config={:#?}", usize::BITS, CustomConfig::debug());
+
+ let default_slab = Slab::<u64, _>::new();
+ let custom_slab = Slab::<u64, _>::new_with_config::<CustomConfig>();
+
+ for i in 0..=ITERS {
+ let idx = default_slab.insert(i).unwrap();
+ assert!(default_slab.remove(idx));
+
+ let idx = custom_slab.insert(i).unwrap();
+ assert!(custom_slab.remove(idx));
+ }
+
+ slab_eq(custom_slab, default_slab);
+}
+
+/// Calls `get()` multiple times to detect invalid ref counting.
+/// Initially, it revealed bugs in the `Slot::get()` implementation.
+#[test]
+fn double_get() {
+ eprintln!("bits={}; config={:#?}", usize::BITS, CustomConfig::debug());
+
+ let default_slab = Slab::<u64, _>::new();
+ let custom_slab = Slab::<u64, _>::new_with_config::<CustomConfig>();
+
+ for i in 0..=ITERS {
+ let idx = default_slab.insert(i).unwrap();
+ assert!(default_slab.get(idx).is_some());
+ assert!(default_slab.get(idx).is_some());
+ assert!(default_slab.remove(idx));
+
+ let idx = custom_slab.insert(i).unwrap();
+ assert!(custom_slab.get(idx).is_some());
+ assert!(custom_slab.get(idx).is_some());
+ assert!(custom_slab.remove(idx));
+ }
+
+ slab_eq(custom_slab, default_slab);
+}
diff --git a/vendor/sharded-slab/src/tests/loom_slab.rs b/vendor/sharded-slab/src/tests/loom_slab.rs
index 58422f9a0..1cfeb8463 100644
--- a/vendor/sharded-slab/src/tests/loom_slab.rs
+++ b/vendor/sharded-slab/src/tests/loom_slab.rs
@@ -381,7 +381,7 @@ fn remove_remote_during_insert() {
#[test]
fn unique_iter() {
run_model("unique_iter", || {
- let mut slab = std::sync::Arc::new(Slab::new());
+ let mut slab = Arc::new(Slab::new());
let s = slab.clone();
let t1 = thread::spawn(move || {
@@ -398,7 +398,7 @@ fn unique_iter() {
t1.join().expect("thread 1 should not panic");
t2.join().expect("thread 2 should not panic");
- let slab = std::sync::Arc::get_mut(&mut slab).expect("other arcs should be dropped");
+ let slab = Arc::get_mut(&mut slab).expect("other arcs should be dropped");
let items: Vec<_> = slab.unique_iter().map(|&i| i).collect();
assert!(items.contains(&1), "items: {:?}", items);
assert!(items.contains(&2), "items: {:?}", items);
diff --git a/vendor/sharded-slab/src/tests/mod.rs b/vendor/sharded-slab/src/tests/mod.rs
index be153b573..4bc9fb389 100644
--- a/vendor/sharded-slab/src/tests/mod.rs
+++ b/vendor/sharded-slab/src/tests/mod.rs
@@ -65,7 +65,11 @@ pub(crate) mod util {
}
}
+#[cfg(not(loom))]
+mod custom_config;
#[cfg(loom)]
mod loom_pool;
#[cfg(loom)]
mod loom_slab;
+#[cfg(not(loom))]
+mod properties;
diff --git a/vendor/sharded-slab/src/tests/properties.rs b/vendor/sharded-slab/src/tests/properties.rs
new file mode 100644
index 000000000..8f14085a9
--- /dev/null
+++ b/vendor/sharded-slab/src/tests/properties.rs
@@ -0,0 +1,244 @@
+//! This module contains property-based tests against the public API:
+//! * API never panics.
+//! * Active entries cannot be overridden until removed.
+//! * The slab doesn't produce overlapping keys.
+//! * The slab doesn't leave "lost" keys.
+//! * `get()`, `get_owned`, and `contains()` are consistent.
+//! * `RESERVED_BITS` are actually not used.
+//!
+//! The test is supposed to be deterministic, so it doesn't spawn real threads
+//! and uses `tid::with()` to override the TID for the current thread.
+
+use std::{ops::Range, sync::Arc};
+
+use indexmap::IndexMap;
+use proptest::prelude::*;
+
+use crate::{tid, Config, DefaultConfig, Slab};
+
+const THREADS: Range<usize> = 1..4;
+const ACTIONS: Range<usize> = 1..1000;
+
+#[derive(Debug, Clone)]
+struct Action {
+ tid: usize,
+ kind: ActionKind,
+}
+
+#[derive(Debug, Clone)]
+enum ActionKind {
+ Insert,
+ VacantEntry,
+ RemoveRandom(usize), // key
+ RemoveExistent(usize), // seed
+ TakeRandom(usize), // key
+ TakeExistent(usize), // seed
+ GetRandom(usize), // key
+ GetExistent(usize), // seed
+}
+
+prop_compose! {
+ fn action_strategy()(tid in THREADS, kind in action_kind_strategy()) -> Action {
+ Action { tid, kind }
+ }
+}
+
+fn action_kind_strategy() -> impl Strategy<Value = ActionKind> {
+ prop_oneof![
+ 1 => Just(ActionKind::Insert),
+ 1 => Just(ActionKind::VacantEntry),
+ 1 => prop::num::usize::ANY.prop_map(ActionKind::RemoveRandom),
+ 1 => prop::num::usize::ANY.prop_map(ActionKind::RemoveExistent),
+ 1 => prop::num::usize::ANY.prop_map(ActionKind::TakeRandom),
+ 1 => prop::num::usize::ANY.prop_map(ActionKind::TakeExistent),
+ // Produce `GetRandom` and `GetExistent` more often.
+ 5 => prop::num::usize::ANY.prop_map(ActionKind::GetRandom),
+ 5 => prop::num::usize::ANY.prop_map(ActionKind::GetExistent),
+ ]
+}
+
+/// Stores active entries (added and not yet removed).
+#[derive(Default)]
+struct Active {
+ // Use `IndexMap` to preserve determinism.
+ map: IndexMap<usize, u32>,
+ prev_value: u32,
+}
+
+impl Active {
+ fn next_value(&mut self) -> u32 {
+ self.prev_value += 1;
+ self.prev_value
+ }
+
+ fn get(&self, key: usize) -> Option<u32> {
+ self.map.get(&key).copied()
+ }
+
+ fn get_any(&self, seed: usize) -> Option<(usize, u32)> {
+ if self.map.is_empty() {
+ return None;
+ }
+
+ let index = seed % self.map.len();
+ self.map.get_index(index).map(|(k, v)| (*k, *v))
+ }
+
+ fn insert(&mut self, key: usize, value: u32) {
+ assert_eq!(
+ self.map.insert(key, value),
+ None,
+ "keys of active entries must be unique"
+ );
+ }
+
+ fn remove(&mut self, key: usize) -> Option<u32> {
+ self.map.swap_remove(&key)
+ }
+
+ fn remove_any(&mut self, seed: usize) -> Option<(usize, u32)> {
+ if self.map.is_empty() {
+ return None;
+ }
+
+ let index = seed % self.map.len();
+ self.map.swap_remove_index(index)
+ }
+
+ fn drain(&mut self) -> impl Iterator<Item = (usize, u32)> + '_ {
+ self.map.drain(..)
+ }
+}
+
+fn used_bits<C: Config>(key: usize) -> usize {
+ assert_eq!(
+ C::RESERVED_BITS + Slab::<u32, C>::USED_BITS,
+ std::mem::size_of::<usize>() * 8
+ );
+ key & ((!0) >> C::RESERVED_BITS)
+}
+
+fn apply_action<C: Config>(
+ slab: &Arc<Slab<u32, C>>,
+ active: &mut Active,
+ action: ActionKind,
+) -> Result<(), TestCaseError> {
+ match action {
+ ActionKind::Insert => {
+ let value = active.next_value();
+ let key = slab.insert(value).expect("unexpectedly exhausted slab");
+ prop_assert_eq!(used_bits::<C>(key), key);
+ active.insert(key, value);
+ }
+ ActionKind::VacantEntry => {
+ let value = active.next_value();
+ let entry = slab.vacant_entry().expect("unexpectedly exhausted slab");
+ let key = entry.key();
+ prop_assert_eq!(used_bits::<C>(key), key);
+ entry.insert(value);
+ active.insert(key, value);
+ }
+ ActionKind::RemoveRandom(key) => {
+ let used_key = used_bits::<C>(key);
+ prop_assert_eq!(slab.get(key).map(|e| *e), slab.get(used_key).map(|e| *e));
+ prop_assert_eq!(slab.remove(key), active.remove(used_key).is_some());
+ }
+ ActionKind::RemoveExistent(seed) => {
+ if let Some((key, _value)) = active.remove_any(seed) {
+ prop_assert!(slab.contains(key));
+ prop_assert!(slab.remove(key));
+ }
+ }
+ ActionKind::TakeRandom(key) => {
+ let used_key = used_bits::<C>(key);
+ prop_assert_eq!(slab.get(key).map(|e| *e), slab.get(used_key).map(|e| *e));
+ prop_assert_eq!(slab.take(key), active.remove(used_key));
+ }
+ ActionKind::TakeExistent(seed) => {
+ if let Some((key, value)) = active.remove_any(seed) {
+ prop_assert!(slab.contains(key));
+ prop_assert_eq!(slab.take(key), Some(value));
+ }
+ }
+ ActionKind::GetRandom(key) => {
+ let used_key = used_bits::<C>(key);
+ prop_assert_eq!(slab.get(key).map(|e| *e), slab.get(used_key).map(|e| *e));
+ prop_assert_eq!(slab.get(key).map(|e| *e), active.get(used_key));
+ prop_assert_eq!(
+ slab.clone().get_owned(key).map(|e| *e),
+ active.get(used_key)
+ );
+ }
+ ActionKind::GetExistent(seed) => {
+ if let Some((key, value)) = active.get_any(seed) {
+ prop_assert!(slab.contains(key));
+ prop_assert_eq!(slab.get(key).map(|e| *e), Some(value));
+ prop_assert_eq!(slab.clone().get_owned(key).map(|e| *e), Some(value));
+ }
+ }
+ }
+
+ Ok(())
+}
+
+fn run<C: Config>(actions: Vec<Action>) -> Result<(), TestCaseError> {
+ let mut slab = Arc::new(Slab::new_with_config::<C>());
+ let mut active = Active::default();
+
+ // Apply all actions.
+ for action in actions {
+ // Override the TID for the current thread instead of using multiple real threads
+ // to preserve determinism. We're not checking concurrency issues here, they should be
+ // covered by loom tests anyway. Thus, it's fine to run all actions consequently.
+ tid::with(action.tid, || {
+ apply_action::<C>(&slab, &mut active, action.kind)
+ })?;
+ }
+
+ // Ensure the slab contains all remaining entries.
+ let mut expected_values = Vec::new();
+ for (key, value) in active.drain() {
+ prop_assert!(slab.contains(key));
+ prop_assert_eq!(slab.get(key).map(|e| *e), Some(value));
+ prop_assert_eq!(slab.clone().get_owned(key).map(|e| *e), Some(value));
+ expected_values.push(value);
+ }
+ expected_values.sort();
+
+ // Ensure `unique_iter()` returns all remaining entries.
+ let slab = Arc::get_mut(&mut slab).unwrap();
+ let mut actual_values = slab.unique_iter().copied().collect::<Vec<_>>();
+ actual_values.sort();
+ prop_assert_eq!(actual_values, expected_values);
+
+ Ok(())
+}
+
+proptest! {
+ #[test]
+ fn default_config(actions in prop::collection::vec(action_strategy(), ACTIONS)) {
+ run::<DefaultConfig>(actions)?;
+ }
+
+ #[test]
+ fn custom_config(actions in prop::collection::vec(action_strategy(), ACTIONS)) {
+ run::<CustomConfig>(actions)?;
+ }
+}
+
+struct CustomConfig;
+
+#[cfg(target_pointer_width = "64")]
+impl Config for CustomConfig {
+ const INITIAL_PAGE_SIZE: usize = 32;
+ const MAX_PAGES: usize = 15;
+ const MAX_THREADS: usize = 256;
+ const RESERVED_BITS: usize = 24;
+}
+#[cfg(target_pointer_width = "32")]
+impl Config for CustomConfig {
+ const INITIAL_PAGE_SIZE: usize = 16;
+ const MAX_PAGES: usize = 6;
+ const MAX_THREADS: usize = 128;
+ const RESERVED_BITS: usize = 12;
+}
diff --git a/vendor/sharded-slab/src/tid.rs b/vendor/sharded-slab/src/tid.rs
index 57d64f970..f2cb7e0d9 100644
--- a/vendor/sharded-slab/src/tid.rs
+++ b/vendor/sharded-slab/src/tid.rs
@@ -12,7 +12,6 @@ use std::{
collections::VecDeque,
fmt,
marker::PhantomData,
- sync::PoisonError,
};
/// Uniquely identifies a thread.
@@ -123,7 +122,7 @@ impl<C> Eq for Tid<C> {}
impl<C: cfg::Config> Clone for Tid<C> {
fn clone(&self) -> Self {
- Self::new(self.id)
+ *self
}
}
@@ -186,9 +185,26 @@ impl Registration {
#[cfg(not(all(loom, any(feature = "loom", test))))]
impl Drop for Registration {
fn drop(&mut self) {
+ use std::sync::PoisonError;
+
if let Some(id) = self.0.get() {
let mut free_list = REGISTRY.free.lock().unwrap_or_else(PoisonError::into_inner);
free_list.push_back(id);
}
}
}
+
+#[cfg(all(test, not(loom)))]
+pub(crate) fn with<R>(tid: usize, f: impl FnOnce() -> R) -> R {
+ struct Guard(Option<usize>);
+
+ impl Drop for Guard {
+ fn drop(&mut self) {
+ REGISTRATION.with(|r| r.0.set(self.0.take()));
+ }
+ }
+
+ let prev = REGISTRATION.with(|r| r.0.replace(Some(tid)));
+ let _guard = Guard(prev);
+ f()
+}
diff --git a/vendor/sharded-slab/tests/reserved_bits_leak.rs b/vendor/sharded-slab/tests/reserved_bits_leak.rs
new file mode 100644
index 000000000..623839300
--- /dev/null
+++ b/vendor/sharded-slab/tests/reserved_bits_leak.rs
@@ -0,0 +1,26 @@
+// Reproduces https://github.com/hawkw/sharded-slab/issues/83
+use memory_stats::memory_stats;
+use sharded_slab::Config;
+use sharded_slab::Slab;
+
+struct CustomConfig;
+impl Config for CustomConfig {
+ const RESERVED_BITS: usize = 1; // This is the cause.
+}
+
+#[test]
+fn reserved_bits_doesnt_leak() {
+ let slab = Slab::new_with_config::<CustomConfig>();
+ for n in 0..1000 {
+ let mem_before = memory_stats().unwrap();
+ let key = slab.insert(0).unwrap();
+ slab.remove(key);
+ let usage = memory_stats().unwrap();
+ eprintln!(
+ "n: {n:<4}\tkey: {key:#08x} rss: {:>16} vs:{:>16}",
+ usage.physical_mem, usage.virtual_mem
+ );
+
+ assert_eq!(mem_before.virtual_mem, usage.virtual_mem);
+ }
+}