diff options
| -rw-r--r-- | .cargo_vcs_info.json | 6 | ||||
| -rw-r--r-- | .clog.toml | 26 | ||||
| -rw-r--r-- | .envrc | 1 | ||||
| -rw-r--r-- | .github/FUNDING.yml | 12 | ||||
| -rw-r--r-- | .github/workflows/ci.yml | 154 | ||||
| -rw-r--r-- | .github/workflows/release.yml | 22 | ||||
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | Android.bp | 2 | ||||
| -rw-r--r-- | CHANGELOG.md | 35 | ||||
| -rw-r--r-- | Cargo.toml | 44 | ||||
| -rw-r--r-- | Cargo.toml.orig | 23 | ||||
| -rw-r--r-- | METADATA | 25 | ||||
| -rw-r--r-- | README.md | 8 | ||||
| -rw-r--r-- | benches/bench.rs | 2 | ||||
| -rw-r--r-- | flake.lock | 85 | ||||
| -rw-r--r-- | flake.nix | 28 | ||||
| -rw-r--r-- | rust-toolchain.toml | 7 | ||||
| -rw-r--r-- | src/iter.rs | 14 | ||||
| -rw-r--r-- | src/lib.rs | 26 | ||||
| -rw-r--r-- | src/page/mod.rs | 4 | ||||
| -rw-r--r-- | src/page/slot.rs | 18 | ||||
| -rw-r--r-- | src/shard.rs | 14 | ||||
| -rw-r--r-- | src/tests/custom_config.rs | 78 | ||||
| -rw-r--r-- | src/tests/loom_slab.rs | 4 | ||||
| -rw-r--r-- | src/tests/mod.rs | 4 | ||||
| -rw-r--r-- | src/tests/properties.rs | 244 | ||||
| -rw-r--r-- | src/tid.rs | 20 | ||||
| -rw-r--r-- | tests/reserved_bits_leak.rs | 26 |
28 files changed, 873 insertions, 62 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..8fba46f --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,6 @@ +{ + "git": { + "sha1": "40579b92debe2ef283a455eb379945e023080ff3" + }, + "path_in_vcs": "" +}
\ No newline at end of file diff --git a/.clog.toml b/.clog.toml new file mode 100644 index 0000000..eda9b6d --- /dev/null +++ b/.clog.toml @@ -0,0 +1,26 @@ +[clog] +# A repository link with the trailing '.git' which will be used to generate +# all commit and issue links +repository = "https://github.com/hawkw/sharded-slab" +# A constant release title +# subtitle = "sharded-slab" + +# specify the style of commit links to generate, defaults to "github" if omitted +link-style = "github" + +# The preferred way to set a constant changelog. This file will be read for old changelog +# data, then prepended to for new changelog data. It's the equivilant to setting +# both infile and outfile to the same file. +# +# Do not use with outfile or infile fields! +# +# Defaults to stdout when omitted +changelog = "CHANGELOG.md" + +# This sets the output format. There are two options "json" or "markdown" and +# defaults to "markdown" when omitted +output-format = "markdown" + +# If you use tags, you can set the following if you wish to only pick +# up changes since your latest tag +from-latest-tag = true @@ -0,0 +1 @@ +use flake;
\ No newline at end of file diff --git a/.github/FUNDING.yml b/.github/FUNDING.yml new file mode 100644 index 0000000..d6b3d15 --- /dev/null +++ b/.github/FUNDING.yml @@ -0,0 +1,12 @@ +# These are supported funding model platforms + +github: [hawkw] +patreon: # Replace with a single Patreon username +open_collective: # Replace with a single Open Collective username +ko_fi: # Replace with a single Ko-fi username +tidelift: # Replace with a single Tidelift platform-name/package-name e.g., npm/babel +community_bridge: # Replace with a single Community Bridge project-name e.g., cloud-foundry +liberapay: # Replace with a single Liberapay username +issuehunt: # Replace with a single IssueHunt username +otechie: # Replace with a single Otechie username +custom: # Replace with up to 4 custom sponsorship URLs e.g., ['link1', 'link2'] diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..d15cd6a --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,154 @@ +name: CI + +on: + push: + branches: ["main"] + pull_request: + +env: + RUSTFLAGS: -Dwarnings + RUST_BACKTRACE: 1 + MSRV: 1.42.0 + +jobs: + build: + name: Build (stable, ${{ matrix.target }}) + runs-on: ubuntu-latest + strategy: + matrix: + target: + - x86_64-unknown-linux-gnu + - i686-unknown-linux-musl + steps: + - uses: actions/checkout@master + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: stable + target: ${{ matrix.target }} + override: true + - name: cargo build --target ${{ matrix.target }} + uses: actions-rs/cargo@v1 + with: + command: build + args: --all-targets --target ${{ matrix.target }} + + build-msrv: + name: Build (MSRV) + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@master + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: ${{ env.MSRV }} + override: true + - name: cargo +${{ env.MSRV }} build + uses: actions-rs/cargo@v1 + with: + command: build + env: + RUSTFLAGS: "" # remove -Dwarnings + + build-nightly: + name: Build (nightly) + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@master + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: nightly + override: true + - name: cargo +nightly build + uses: actions-rs/cargo@v1 + with: + command: build + env: + RUSTFLAGS: "" # remove -Dwarnings + + test: + name: Tests (stable) + needs: build + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@master + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: stable + override: true + - name: Run tests + run: cargo test + + test-loom: + name: Loom tests (stable) + needs: build + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@master + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: stable + override: true + - name: Run Loom tests + run: ./bin/loom.sh + + clippy: + name: Clippy (stable) + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: stable + components: clippy + override: true + - name: cargo clippy --all-targets --all-features + uses: actions-rs/clippy-check@v1 + with: + token: ${{ secrets.GITHUB_TOKEN }} + args: --all-targets --all-features + + rustfmt: + name: Rustfmt (stable) + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - name: Install toolchain + uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: stable + components: rustfmt + override: true + - name: Run rustfmt + uses: actions-rs/cargo@v1 + with: + command: fmt + args: -- --check + + all-systems-go: + name: "all systems go!" + needs: + - build + - build-msrv + # Note: we explicitly *don't* require the `build-nightly` job to pass, + # since the nightly Rust compiler is unstable. We don't want nightly + # regressions to break our build --- this CI job is intended for + # informational reasons rather than as a gatekeeper for merging PRs. + - test + - test-loom + - clippy + - rustfmt + runs-on: ubuntu-latest + steps: + - run: exit 0 diff --git a/.github/workflows/release.yml b/.github/workflows/release.yml new file mode 100644 index 0000000..13cc969 --- /dev/null +++ b/.github/workflows/release.yml @@ -0,0 +1,22 @@ +name: Release + +on: + push: + tags: + - v[0-9]+.* + +jobs: + create-release: + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - uses: taiki-e/create-gh-release-action@v1 + with: + # Path to changelog. + changelog: CHANGELOG.md + # Reject releases from commits not contained in branches + # that match the specified pattern (regular expression) + branch: main + env: + # (Required) GitHub token for creating GitHub Releases. + GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
\ No newline at end of file diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..49b7b01 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +target +Cargo.lock +.direnv
\ No newline at end of file @@ -6,7 +6,7 @@ rust_library { host_supported: true, crate_name: "sharded_slab", cargo_env_compat: true, - cargo_pkg_version: "0.1.4", + cargo_pkg_version: "0.1.7", srcs: ["src/lib.rs"], edition: "2018", rustlibs: ["liblazy_static"], diff --git a/CHANGELOG.md b/CHANGELOG.md index 9dc7c2f..6b6ed2d 100644 --- a/CHANGELOG.md +++ b/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) @@ -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/Cargo.toml.orig b/Cargo.toml.orig index 5b3d627..a43d3b9 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -1,18 +1,29 @@ [package] name = "sharded-slab" -version = "0.1.4" +version = "0.1.7" authors = ["Eliza Weisman <eliza@buoyant.io>"] edition = "2018" -documentation = "https://docs.rs/sharded-slab/0.1.4/sharded_slab" +documentation = "https://docs.rs/sharded-slab/" homepage = "https://github.com/hawkw/sharded-slab" repository = "https://github.com/hawkw/sharded-slab" readme = "README.md" +rust-version = "1.42.0" license = "MIT" keywords = ["slab", "allocator", "lock-free", "atomic"] categories = ["memory-management", "data-structures", "concurrency"] description = """ A lock-free concurrent slab. """ +ignore = [ + "flake.nix", + "flake.lock", + ".envrc", + ".clog.toml", + ".cargo", + ".github", + ".direnv", + "bin", +] [badges] maintenance = { status = "experimental" } @@ -25,14 +36,18 @@ harness = false lazy_static = "1" [dev-dependencies] -loom = { version = "0.5", features = ["checkpoint"] } proptest = "1" criterion = "0.3" slab = "0.4.2" +memory-stats = "1" +indexmap = "1" # newer versions lead to "candidate versions found which didn't match" on 1.42.0 [target.'cfg(loom)'.dependencies] loom = { version = "0.5", features = ["checkpoint"], optional = true } +[target.'cfg(loom)'.dev-dependencies] +loom = { version = "0.5", features = ["checkpoint"] } + [package.metadata.docs.rs] all-features = true -rustdoc-args = ["--cfg", "docsrs"]
\ No newline at end of file +rustdoc-args = ["--cfg", "docsrs"] @@ -1,19 +1,20 @@ +# This project was upgraded with external_updater. +# Usage: tools/external_updater/updater.sh update external/rust/crates/sharded-slab +# For more info, check https://cs.android.com/android/platform/superproject/+/main:tools/external_updater/README.md + name: "sharded-slab" description: "A lock-free concurrent slab." third_party { - url { - type: HOMEPAGE - value: "https://crates.io/crates/sharded-slab" - } - url { - type: ARCHIVE - value: "https://static.crates.io/crates/sharded-slab/sharded-slab-0.1.4.crate" - } - version: "0.1.4" license_type: NOTICE last_upgrade_date { - year: 2023 - month: 7 - day: 28 + year: 2024 + month: 2 + day: 5 + } + homepage: "https://crates.io/crates/sharded-slab" + identifier { + type: "Archive" + value: "https://static.crates.io/crates/sharded-slab/sharded-slab-0.1.7.crate" + version: "0.1.7" } } @@ -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/benches/bench.rs b/benches/bench.rs index c95bd4e..21879c1 100644 --- a/benches/bench.rs +++ b/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/flake.lock b/flake.lock new file mode 100644 index 0000000..cfcd993 --- /dev/null +++ b/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/flake.nix b/flake.nix new file mode 100644 index 0000000..a38cc2a --- /dev/null +++ b/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/rust-toolchain.toml b/rust-toolchain.toml new file mode 100644 index 0000000..9a1c306 --- /dev/null +++ b/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/src/iter.rs b/src/iter.rs index 54189aa..e70bebe 100644 --- a/src/iter.rs +++ b/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> {} @@ -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/src/page/mod.rs b/src/page/mod.rs index 0499fb5..a82c247 100644 --- a/src/page/mod.rs +++ b/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/src/page/slot.rs b/src/page/slot.rs index 3387d53..bb3f9ac 100644 --- a/src/page/slot.rs +++ b/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/src/shard.rs b/src/shard.rs index 0d054d7..b77a9fc 100644 --- a/src/shard.rs +++ b/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/src/tests/custom_config.rs b/src/tests/custom_config.rs new file mode 100644 index 0000000..77f7259 --- /dev/null +++ b/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/src/tests/loom_slab.rs b/src/tests/loom_slab.rs index 58422f9..1cfeb84 100644 --- a/src/tests/loom_slab.rs +++ b/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/src/tests/mod.rs b/src/tests/mod.rs index be153b5..4bc9fb3 100644 --- a/src/tests/mod.rs +++ b/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/src/tests/properties.rs b/src/tests/properties.rs new file mode 100644 index 0000000..8f14085 --- /dev/null +++ b/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; +} @@ -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/tests/reserved_bits_leak.rs b/tests/reserved_bits_leak.rs new file mode 100644 index 0000000..6238393 --- /dev/null +++ b/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); + } +} |