diff options
author | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2022-06-15 21:43:43 +0000 |
---|---|---|
committer | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | 2022-06-15 21:43:43 +0000 |
commit | 4881d8c0192f0f7a06e94320dd86e1694573dc07 (patch) | |
tree | 048a394b1b0781fc24475e632c353d36a982f439 | |
parent | b02dad368009ec6700d05e802089b785bae23fa9 (diff) | |
parent | 8a698f122a7264b15fc46930b2653709d48c6e53 (diff) | |
download | crossbeam-deque-aml_tz3_314012050.tar.gz |
Snap for 8730993 from 8a698f122a7264b15fc46930b2653709d48c6e53 to mainline-tzdata3-releaseaml_tz3_314012070aml_tz3_314012050aml_tz3_314012010aml_tz3_313110000aml_tz3_312511020aml_tz3_312511010aml_tz3_312410020aml_tz3_312410010android12-mainline-tzdata3-releaseaml_tz3_314012010
Change-Id: Icb8e532d13bd667e461e09071211ae4e914bed18
-rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
-rw-r--r-- | Android.bp | 76 | ||||
-rw-r--r-- | CHANGELOG.md | 5 | ||||
-rw-r--r-- | Cargo.toml | 14 | ||||
-rw-r--r-- | Cargo.toml.orig | 7 | ||||
-rw-r--r-- | METADATA | 10 | ||||
-rw-r--r-- | README.md | 6 | ||||
-rw-r--r-- | TEST_MAPPING | 45 | ||||
-rw-r--r-- | cargo2android.json | 5 | ||||
-rw-r--r-- | src/deque.rs | 135 | ||||
-rw-r--r-- | src/lib.rs | 9 | ||||
-rw-r--r-- | tests/fifo.rs | 20 | ||||
-rw-r--r-- | tests/injector.rs | 12 | ||||
-rw-r--r-- | tests/lifo.rs | 20 |
14 files changed, 102 insertions, 264 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index 9716123..08632f0 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,5 @@ { "git": { - "sha1": "0e2a930eac3586ab52498413310c45af6c67d830" + "sha1": "d9dfc9e1ffabcb3c01addad14878f16c2795c371" } } @@ -1,4 +1,4 @@ -// This file is generated by cargo2android.py --config cargo2android.json. +// This file is generated by cargo2android.py --run --device --dependencies. // Do not modify this file as changes will be overridden on upgrade. package { @@ -39,75 +39,10 @@ license { ], } -rust_defaults { - name: "crossbeam-deque_test_defaults", - crate_name: "crossbeam_deque", - cargo_env_compat: true, - cargo_pkg_version: "0.8.1", - test_suites: ["general-tests"], - auto_gen_config: true, - edition: "2018", - features: [ - "crossbeam-epoch", - "crossbeam-utils", - "default", - "std", - ], - rustlibs: [ - "libcfg_if", - "libcrossbeam_deque", - "libcrossbeam_epoch", - "libcrossbeam_utils", - "librand", - ], -} - -rust_test { - name: "crossbeam-deque_test_tests_fifo", - defaults: ["crossbeam-deque_test_defaults"], - host_supported: true, - srcs: ["tests/fifo.rs"], - test_options: { - unit_test: true, - }, -} - -rust_test { - name: "crossbeam-deque_test_tests_injector", - defaults: ["crossbeam-deque_test_defaults"], - host_supported: true, - srcs: ["tests/injector.rs"], - test_options: { - unit_test: true, - }, -} - -rust_test { - name: "crossbeam-deque_test_tests_lifo", - defaults: ["crossbeam-deque_test_defaults"], - host_supported: true, - srcs: ["tests/lifo.rs"], - test_options: { - unit_test: true, - }, -} - -rust_test { - name: "crossbeam-deque_test_tests_steal", - defaults: ["crossbeam-deque_test_defaults"], - host_supported: true, - srcs: ["tests/steal.rs"], - test_options: { - unit_test: true, - }, -} - rust_library { name: "libcrossbeam_deque", host_supported: true, crate_name: "crossbeam_deque", - cargo_env_compat: true, - cargo_pkg_version: "0.8.1", srcs: ["src/lib.rs"], edition: "2018", features: [ @@ -122,3 +57,12 @@ rust_library { "libcrossbeam_utils", ], } + +// dependent_library ["feature_list"] +// autocfg-1.0.1 +// cfg-if-1.0.0 +// crossbeam-epoch-0.9.3 "alloc,lazy_static,std" +// crossbeam-utils-0.8.3 "lazy_static,std" +// lazy_static-1.4.0 +// memoffset-0.6.1 "default" +// scopeguard-1.1.0 diff --git a/CHANGELOG.md b/CHANGELOG.md index 14dcc20..da37edc 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,8 +1,3 @@ -# Version 0.8.1 - -- Fix deque steal race condition. (#726) -- Add `Stealer::len` method. (#708) - # Version 0.8.0 - Bump the minimum supported Rust version to 1.36. @@ -3,20 +3,22 @@ # When uploading crates to the registry Cargo will automatically # "normalize" Cargo.toml files for maximal compatibility # with all versions of Cargo and also rewrite `path` dependencies -# to registry (e.g., crates.io) dependencies. +# to registry (e.g., crates.io) dependencies # -# If you are reading this file be aware that the original Cargo.toml -# will likely look very different (and much more reasonable). -# See Cargo.toml.orig for the original contents. +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) [package] edition = "2018" name = "crossbeam-deque" -version = "0.8.1" +version = "0.8.0" authors = ["The Crossbeam Project Developers"] description = "Concurrent work-stealing deque" homepage = "https://github.com/crossbeam-rs/crossbeam/tree/master/crossbeam-deque" documentation = "https://docs.rs/crossbeam-deque" +readme = "README.md" keywords = ["chase-lev", "lock-free", "scheduler", "scheduling"] categories = ["algorithms", "concurrency", "data-structures"] license = "MIT OR Apache-2.0" @@ -34,7 +36,7 @@ version = "0.8" optional = true default-features = false [dev-dependencies.rand] -version = "0.8" +version = "0.7.3" [features] default = ["std"] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 572ddfd..8d38e22 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -4,10 +4,11 @@ name = "crossbeam-deque" # - Update CHANGELOG.md # - Update README.md # - Create "crossbeam-deque-X.Y.Z" git tag -version = "0.8.1" +version = "0.8.0" authors = ["The Crossbeam Project Developers"] edition = "2018" license = "MIT OR Apache-2.0" +readme = "README.md" repository = "https://github.com/crossbeam-rs/crossbeam" homepage = "https://github.com/crossbeam-rs/crossbeam/tree/master/crossbeam-deque" documentation = "https://docs.rs/crossbeam-deque" @@ -20,8 +21,6 @@ default = ["std"] # Enable to use APIs that require `std`. # This is enabled by default. -# -# NOTE: Disabling `std` feature is not supported yet. std = ["crossbeam-epoch/std", "crossbeam-utils/std"] [dependencies] @@ -40,4 +39,4 @@ default-features = false optional = true [dev-dependencies] -rand = "0.8" +rand = "0.7.3" @@ -7,13 +7,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/crossbeam-deque/crossbeam-deque-0.8.1.crate" + value: "https://static.crates.io/crates/crossbeam-deque/crossbeam-deque-0.8.0.crate" } - version: "0.8.1" + version: "0.8.0" license_type: NOTICE last_upgrade_date { - year: 2021 - month: 8 - day: 9 + year: 2020 + month: 12 + day: 21 } } @@ -2,7 +2,7 @@ [![Build Status](https://github.com/crossbeam-rs/crossbeam/workflows/CI/badge.svg)]( https://github.com/crossbeam-rs/crossbeam/actions) -[![License](https://img.shields.io/badge/license-MIT_OR_Apache--2.0-blue.svg)]( +[![License](https://img.shields.io/badge/license-MIT%20OR%20Apache--2.0-blue.svg)]( https://github.com/crossbeam-rs/crossbeam/tree/master/crossbeam-deque#license) [![Cargo](https://img.shields.io/crates/v/crossbeam-deque.svg)]( https://crates.io/crates/crossbeam-deque) @@ -10,7 +10,7 @@ https://crates.io/crates/crossbeam-deque) https://docs.rs/crossbeam-deque) [![Rust 1.36+](https://img.shields.io/badge/rust-1.36+-lightgray.svg)]( https://www.rust-lang.org) -[![chat](https://img.shields.io/discord/569610676205781012.svg?logo=discord)](https://discord.com/invite/JXYwgWZ) +[![chat](https://img.shields.io/discord/569610676205781012.svg?logo=discord)](https://discord.gg/BBYwKq) This crate provides work-stealing deques, which are primarily intended for building task schedulers. @@ -21,7 +21,7 @@ Add this to your `Cargo.toml`: ```toml [dependencies] -crossbeam-deque = "0.8" +crossbeam-deque = "0.7" ``` ## Compatibility diff --git a/TEST_MAPPING b/TEST_MAPPING deleted file mode 100644 index 3601da1..0000000 --- a/TEST_MAPPING +++ /dev/null @@ -1,45 +0,0 @@ -// Generated by update_crate_tests.py for tests that depend on this crate. -{ - "imports": [ - { - "path": "external/rust/crates/base64" - }, - { - "path": "external/rust/crates/tinytemplate" - }, - { - "path": "external/rust/crates/tinyvec" - }, - { - "path": "external/rust/crates/unicode-xid" - } - ], - "presubmit": [ - { - "name": "crossbeam-deque_test_tests_fifo" - }, - { - "name": "crossbeam-deque_test_tests_injector" - }, - { - "name": "crossbeam-deque_test_tests_lifo" - }, - { - "name": "crossbeam-deque_test_tests_steal" - } - ], - "presubmit-rust": [ - { - "name": "crossbeam-deque_test_tests_fifo" - }, - { - "name": "crossbeam-deque_test_tests_injector" - }, - { - "name": "crossbeam-deque_test_tests_lifo" - }, - { - "name": "crossbeam-deque_test_tests_steal" - } - ] -} diff --git a/cargo2android.json b/cargo2android.json deleted file mode 100644 index d36fb44..0000000 --- a/cargo2android.json +++ /dev/null @@ -1,5 +0,0 @@ -{ - "device": true, - "run": true, - "tests": true -}
\ No newline at end of file diff --git a/src/deque.rs b/src/deque.rs index 802a2fe..fcd6f9f 100644 --- a/src/deque.rs +++ b/src/deque.rs @@ -1,3 +1,7 @@ +// TODO(@jeehoonkang): we mutates `batch_size` inside `for i in 0..batch_size {}`. It is difficult +// to read because we're mutating the range bound. +#![allow(clippy::mut_range_bound)] + use std::cell::{Cell, UnsafeCell}; use std::cmp; use std::fmt; @@ -588,27 +592,6 @@ impl<T> Stealer<T> { b.wrapping_sub(f) <= 0 } - /// Returns the number of tasks in the deque. - /// - /// ``` - /// use crossbeam_deque::Worker; - /// - /// let w = Worker::new_lifo(); - /// let s = w.stealer(); - /// - /// assert_eq!(s.len(), 0); - /// w.push(1); - /// assert_eq!(s.len(), 1); - /// w.push(2); - /// assert_eq!(s.len(), 2); - /// ``` - pub fn len(&self) -> usize { - let f = self.inner.front.load(Ordering::Acquire); - atomic::fence(Ordering::SeqCst); - let b = self.inner.back.load(Ordering::Acquire); - b.wrapping_sub(f).max(0) as usize - } - /// Steals a task from the queue. /// /// # Examples @@ -652,13 +635,11 @@ impl<T> Stealer<T> { let task = unsafe { buffer.deref().read(f) }; // Try incrementing the front index to steal the task. - // If the buffer has been swapped or the increment fails, we retry. - if self.inner.buffer.load(Ordering::Acquire, guard) != buffer - || self - .inner - .front - .compare_exchange(f, f.wrapping_add(1), Ordering::SeqCst, Ordering::Relaxed) - .is_err() + if self + .inner + .front + .compare_exchange(f, f.wrapping_add(1), Ordering::SeqCst, Ordering::Relaxed) + .is_err() { // We didn't steal this task, forget it. mem::forget(task); @@ -760,18 +741,16 @@ impl<T> Stealer<T> { } // Try incrementing the front index to steal the batch. - // If the buffer has been swapped or the increment fails, we retry. - if self.inner.buffer.load(Ordering::Acquire, guard) != buffer - || self - .inner - .front - .compare_exchange( - f, - f.wrapping_add(batch_size), - Ordering::SeqCst, - Ordering::Relaxed, - ) - .is_err() + if self + .inner + .front + .compare_exchange( + f, + f.wrapping_add(batch_size), + Ordering::SeqCst, + Ordering::Relaxed, + ) + .is_err() { return Steal::Retry; } @@ -781,12 +760,7 @@ impl<T> Stealer<T> { // Steal a batch of tasks from the front one by one. Flavor::Lifo => { - // This loop may modify the batch_size, which triggers a clippy lint warning. - // Use a new variable to avoid the warning, and to make it clear we aren't - // modifying the loop exit condition during iteration. - let original_batch_size = batch_size; - - for i in 0..original_batch_size { + for i in 0..batch_size { // If this is not the first steal, check whether the queue is empty. if i > 0 { // We've already got the current front index. Now execute the fence to @@ -807,18 +781,11 @@ impl<T> Stealer<T> { let task = unsafe { buffer.deref().read(f) }; // Try incrementing the front index to steal the task. - // If the buffer has been swapped or the increment fails, we retry. - if self.inner.buffer.load(Ordering::Acquire, guard) != buffer - || self - .inner - .front - .compare_exchange( - f, - f.wrapping_add(1), - Ordering::SeqCst, - Ordering::Relaxed, - ) - .is_err() + if self + .inner + .front + .compare_exchange(f, f.wrapping_add(1), Ordering::SeqCst, Ordering::Relaxed) + .is_err() { // We didn't steal this task, forget it and break from the loop. mem::forget(task); @@ -960,19 +927,17 @@ impl<T> Stealer<T> { } } - // Try incrementing the front index to steal the task. - // If the buffer has been swapped or the increment fails, we retry. - if self.inner.buffer.load(Ordering::Acquire, guard) != buffer - || self - .inner - .front - .compare_exchange( - f, - f.wrapping_add(batch_size + 1), - Ordering::SeqCst, - Ordering::Relaxed, - ) - .is_err() + // Try incrementing the front index to steal the batch. + if self + .inner + .front + .compare_exchange( + f, + f.wrapping_add(batch_size + 1), + Ordering::SeqCst, + Ordering::Relaxed, + ) + .is_err() { // We didn't steal this task, forget it. mem::forget(task); @@ -1000,12 +965,7 @@ impl<T> Stealer<T> { f = f.wrapping_add(1); // Repeat the same procedure for the batch steals. - // - // This loop may modify the batch_size, which triggers a clippy lint warning. - // Use a new variable to avoid the warning, and to make it clear we aren't - // modifying the loop exit condition during iteration. - let original_batch_size = batch_size; - for i in 0..original_batch_size { + for i in 0..batch_size { // We've already got the current front index. Now execute the fence to // synchronize with other threads. atomic::fence(Ordering::SeqCst); @@ -1023,18 +983,11 @@ impl<T> Stealer<T> { let tmp = unsafe { buffer.deref().read(f) }; // Try incrementing the front index to steal the task. - // If the buffer has been swapped or the increment fails, we retry. - if self.inner.buffer.load(Ordering::Acquire, guard) != buffer - || self - .inner - .front - .compare_exchange( - f, - f.wrapping_add(1), - Ordering::SeqCst, - Ordering::Relaxed, - ) - .is_err() + if self + .inner + .front + .compare_exchange(f, f.wrapping_add(1), Ordering::SeqCst, Ordering::Relaxed) + .is_err() { // We didn't steal this task, forget it and break from the loop. mem::forget(tmp); @@ -1414,9 +1367,7 @@ impl<T> Injector<T> { // Destroy the block if we've reached the end, or if another thread wanted to destroy // but couldn't because we were busy reading from the slot. - if (offset + 1 == BLOCK_CAP) - || (slot.state.fetch_or(READ, Ordering::AcqRel) & DESTROY != 0) - { + if (offset + 1 == BLOCK_CAP) || (slot.state.fetch_or(READ, Ordering::AcqRel) & DESTROY != 0) { Block::destroy(block, offset); } @@ -89,13 +89,10 @@ allow(dead_code, unused_assignments, unused_variables) ) ))] -#![warn( - missing_docs, - missing_debug_implementations, - rust_2018_idioms, - unreachable_pub -)] +#![warn(missing_docs, missing_debug_implementations, rust_2018_idioms)] #![cfg_attr(not(feature = "std"), no_std)] +// matches! requires Rust 1.42 +#![allow(clippy::match_like_matches_macro)] use cfg_if::cfg_if; diff --git a/tests/fifo.rs b/tests/fifo.rs index e2365fb..19a1f58 100644 --- a/tests/fifo.rs +++ b/tests/fifo.rs @@ -167,7 +167,7 @@ fn stress() { hits.fetch_add(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { hits.fetch_add(1, SeqCst); } } @@ -177,8 +177,8 @@ fn stress() { let mut rng = rand::thread_rng(); let mut expected = 0; while expected < COUNT { - if rng.gen_range(0..3) == 0 { - while w.pop().is_some() { + if rng.gen_range(0, 3) == 0 { + while let Some(_) = w.pop() { hits.fetch_add(1, SeqCst); } } else { @@ -188,7 +188,7 @@ fn stress() { } while hits.load(SeqCst) < COUNT { - while w.pop().is_some() { + while let Some(_) = w.pop() { hits.fetch_add(1, SeqCst); } } @@ -227,7 +227,7 @@ fn no_starvation() { hits.fetch_add(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { hits.fetch_add(1, SeqCst); } } @@ -237,9 +237,9 @@ fn no_starvation() { let mut rng = rand::thread_rng(); let mut my_hits = 0; loop { - for i in 0..rng.gen_range(0..COUNT) { - if rng.gen_range(0..3) == 0 && my_hits == 0 { - while w.pop().is_some() { + for i in 0..rng.gen_range(0, COUNT) { + if rng.gen_range(0, 3) == 0 && my_hits == 0 { + while let Some(_) = w.pop() { my_hits += 1; } } else { @@ -300,7 +300,7 @@ fn destructors() { remaining.fetch_sub(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { cnt += 1; remaining.fetch_sub(1, SeqCst); } @@ -309,7 +309,7 @@ fn destructors() { } for _ in 0..STEPS { - if w.pop().is_some() { + if let Some(_) = w.pop() { remaining.fetch_sub(1, SeqCst); } } diff --git a/tests/injector.rs b/tests/injector.rs index 3f74d1b..0165e1a 100644 --- a/tests/injector.rs +++ b/tests/injector.rs @@ -178,7 +178,7 @@ fn stress() { hits.fetch_add(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { hits.fetch_add(1, SeqCst); } } @@ -188,7 +188,7 @@ fn stress() { let mut rng = rand::thread_rng(); let mut expected = 0; while expected < COUNT { - if rng.gen_range(0..3) == 0 { + if rng.gen_range(0, 3) == 0 { while let Success(_) = q.steal() { hits.fetch_add(1, SeqCst); } @@ -238,7 +238,7 @@ fn no_starvation() { hits.fetch_add(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { hits.fetch_add(1, SeqCst); } } @@ -248,8 +248,8 @@ fn no_starvation() { let mut rng = rand::thread_rng(); let mut my_hits = 0; loop { - for i in 0..rng.gen_range(0..COUNT) { - if rng.gen_range(0..3) == 0 && my_hits == 0 { + for i in 0..rng.gen_range(0, COUNT) { + if rng.gen_range(0, 3) == 0 && my_hits == 0 { while let Success(_) = q.steal() { my_hits += 1; } @@ -311,7 +311,7 @@ fn destructors() { remaining.fetch_sub(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { cnt += 1; remaining.fetch_sub(1, SeqCst); } diff --git a/tests/lifo.rs b/tests/lifo.rs index 3e99e95..d7e498a 100644 --- a/tests/lifo.rs +++ b/tests/lifo.rs @@ -167,7 +167,7 @@ fn stress() { hits.fetch_add(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { hits.fetch_add(1, SeqCst); } } @@ -177,8 +177,8 @@ fn stress() { let mut rng = rand::thread_rng(); let mut expected = 0; while expected < COUNT { - if rng.gen_range(0..3) == 0 { - while w.pop().is_some() { + if rng.gen_range(0, 3) == 0 { + while let Some(_) = w.pop() { hits.fetch_add(1, SeqCst); } } else { @@ -188,7 +188,7 @@ fn stress() { } while hits.load(SeqCst) < COUNT { - while w.pop().is_some() { + while let Some(_) = w.pop() { hits.fetch_add(1, SeqCst); } } @@ -227,7 +227,7 @@ fn no_starvation() { hits.fetch_add(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { hits.fetch_add(1, SeqCst); } } @@ -237,9 +237,9 @@ fn no_starvation() { let mut rng = rand::thread_rng(); let mut my_hits = 0; loop { - for i in 0..rng.gen_range(0..COUNT) { - if rng.gen_range(0..3) == 0 && my_hits == 0 { - while w.pop().is_some() { + for i in 0..rng.gen_range(0, COUNT) { + if rng.gen_range(0, 3) == 0 && my_hits == 0 { + while let Some(_) = w.pop() { my_hits += 1; } } else { @@ -300,7 +300,7 @@ fn destructors() { remaining.fetch_sub(1, SeqCst); } - while w2.pop().is_some() { + while let Some(_) = w2.pop() { cnt += 1; remaining.fetch_sub(1, SeqCst); } @@ -309,7 +309,7 @@ fn destructors() { } for _ in 0..STEPS { - if w.pop().is_some() { + if let Some(_) = w.pop() { remaining.fetch_sub(1, SeqCst); } } |