From 9918693037dce8aa4bb6f08741b6812923486c18 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 19 Jun 2024 11:26:03 +0200 Subject: Merging upstream version 1.76.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/sharded-slab/.cargo-checksum.json | 2 +- vendor/sharded-slab/CHANGELOG.md | 35 ++++ vendor/sharded-slab/Cargo.toml | 44 ++++- vendor/sharded-slab/README.md | 8 +- vendor/sharded-slab/benches/bench.rs | 2 +- vendor/sharded-slab/flake.lock | 85 +++++++++ vendor/sharded-slab/flake.nix | 28 +++ vendor/sharded-slab/rust-toolchain.toml | 7 + vendor/sharded-slab/src/iter.rs | 14 +- vendor/sharded-slab/src/lib.rs | 26 ++- vendor/sharded-slab/src/page/mod.rs | 4 +- vendor/sharded-slab/src/page/slot.rs | 18 +- vendor/sharded-slab/src/shard.rs | 14 +- vendor/sharded-slab/src/tests/custom_config.rs | 78 ++++++++ vendor/sharded-slab/src/tests/loom_slab.rs | 4 +- vendor/sharded-slab/src/tests/mod.rs | 4 + vendor/sharded-slab/src/tests/properties.rs | 244 ++++++++++++++++++++++++ vendor/sharded-slab/src/tid.rs | 20 +- vendor/sharded-slab/tests/reserved_bits_leak.rs | 26 +++ 19 files changed, 617 insertions(+), 46 deletions(-) create mode 100644 vendor/sharded-slab/flake.lock create mode 100644 vendor/sharded-slab/flake.nix create mode 100644 vendor/sharded-slab/rust-toolchain.toml create mode 100644 vendor/sharded-slab/src/tests/custom_config.rs create mode 100644 vendor/sharded-slab/src/tests/properties.rs create mode 100644 vendor/sharded-slab/tests/reserved_bits_leak.rs (limited to 'vendor/sharded-slab') 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 @@ + +### 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)) + + + + +## 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)) + + + + +## 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)) + + + ### 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 "] -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 MultithreadedBench { 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, C>, pub(super) pages: slice::Iter<'a, page::Shared, C>>, pub(super) slots: Option>, } -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 { test_println!("UniqueIter::next"); loop { @@ -37,3 +41,5 @@ impl<'a, T, C: crate::cfg::Config> Iterator for UniqueIter<'a, T, C> { } } } + +impl 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 Slab { } /// Returns an iterator over all the items in the slab. + /// + /// Because this iterator exclusively borrows the slab (i.e. it holds an + /// `&mut Slab`), 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> { - 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, C>) -> Option<&'a T>) @@ -402,7 +402,7 @@ impl Ord for Addr { impl Clone for Addr { 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 Slot { // 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 Ord for Generation { impl Clone for Generation { fn clone(&self) -> Self { - Self::new(self.value) + *self } } @@ -747,7 +748,7 @@ impl Ord for RefCount { impl Clone for RefCount { fn clone(&self) -> Self { - Self::from_usize(self.value) + *self } } @@ -875,7 +876,8 @@ impl InitGuard { 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::(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::::from_packed(idx).as_usize(), self.tid); let (addr, page_index) = page::indices::(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::::from_packed(idx).as_usize(), self.tid); let (addr, page_index) = page::indices::(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::::from_packed(idx).as_usize(), self.tid); let (addr, page_index) = page::indices::(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::::from_packed(idx).as_usize(), self.tid); let (addr, page_index) = page::indices::(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::::from_packed(idx).as_usize(), self.tid); let (addr, page_index) = page::indices::(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::::from_packed(idx).as_usize(), self.tid); let (addr, page_index) = page::indices::(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, mut rhs: Slab) { + let mut lhs_vec = lhs.unique_iter().collect::>(); + lhs_vec.sort_unstable(); + let mut rhs_vec = rhs.unique_iter().collect::>(); + 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::::new(); + let custom_slab = Slab::::new_with_config::(); + + 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::::new(); + let custom_slab = Slab::::new_with_config::(); + + 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 = 1..4; +const ACTIONS: Range = 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 { + 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, + prev_value: u32, +} + +impl Active { + fn next_value(&mut self) -> u32 { + self.prev_value += 1; + self.prev_value + } + + fn get(&self, key: usize) -> Option { + 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 { + 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 + '_ { + self.map.drain(..) + } +} + +fn used_bits(key: usize) -> usize { + assert_eq!( + C::RESERVED_BITS + Slab::::USED_BITS, + std::mem::size_of::() * 8 + ); + key & ((!0) >> C::RESERVED_BITS) +} + +fn apply_action( + slab: &Arc>, + 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::(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::(key), key); + entry.insert(value); + active.insert(key, value); + } + ActionKind::RemoveRandom(key) => { + let used_key = used_bits::(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::(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::(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(actions: Vec) -> Result<(), TestCaseError> { + let mut slab = Arc::new(Slab::new_with_config::()); + 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::(&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::>(); + 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::(actions)?; + } + + #[test] + fn custom_config(actions in prop::collection::vec(action_strategy(), ACTIONS)) { + run::(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 Eq for Tid {} impl Clone for Tid { 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(tid: usize, f: impl FnOnce() -> R) -> R { + struct Guard(Option); + + 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::(); + 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); + } +} -- cgit v1.2.3