[PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Burak Emir]

This series adds a Rust bitmap API for porting the approach from
commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.

The Rust bitmap API provides a safe abstraction to underlying bitmap
and bitops operations. For now, only includes method necessary for
dbitmap.h, more can be added later. We perform bounds checks for
hardening, violations are programmer errors that result in panics.

We include set_bit_atomic and clear_bit_atomic operations. One has
to avoid races with non-atomic operations, which is ensure by the
Rust type system: either callers have shared references &bitmap in
which case the mutations are atomic operations. Or there is a
exclusive reference &mut bitmap, in which case there is no concurrent
access.

This version includes an optimization to represent the bitmap inline,
as suggested by Yury.

We introduce a Rust API that would replace (dbitmap.h) in file id_pool.rs. 
This data structure is tightly coupled to the bitmap API. Includes an example of usage
that requires releasing a spinlock, as expected in Binder driver.

This is v7 of a patch introducing Rust bitmap API [v6]. Thanks
for all the helpful comments, this series has improved significantly
as a result of your work.

Changes v6 --> v7:
- Added separate unit tests in bitmap.rs and benchmark module,
  following the example in find_bit_benchmark.c
- Added discussion about using vendored bitset to commit message.
- Refined warning about naming convention

Changes v5 --> v6:
- Added SAFETY comment for atomic operations.
- Added missing volatile to bitops set_bit and clear_bit bindings.
- Fixed condition on `nbits` to be <= i32::MAX, update SAFETY comments.
- Readability improvements.
- Updated doc comments wording and indentation.

Changes v4 --> v5: (suggested by Yury and Alice)
- rebased on next-20250318
- split MAINTAINERS changes
- no dependencies on [1] and [2] anymore - Viresh,
  please do add a separate section if you want to maintain cpumask.rs
  separately.
- imports atomic and non-atomic variants, introduces a naming convention
  set_bit and set_bit_atomic on the Rust side.
- changed naming and comments. Keeping `new`.
- change dynamic_id_pool to id_pool
- represent bitmap inline when possible
- add some more tests
- add myself to M: line for the Rust abstractions

Changes v3 --> v4:
- Rebased on Viresh's v3 [2].
- split into multiple patches, separate Rust and bindings. (Yury)
- adds dynamic_id_pool.rs to show the Binder use case. (Yury)
- include example usage that requires release of spinlock (Alice)
- changed bounds checks to `assert!`, shorter (Yury)
- fix param names in binding helpers. (Miguel)
- proper rustdoc formatting, and use examples as kunit tests. (Miguel)
- reduce number of Bitmap methods, and simplify API through
  use Option<usize> to handle the "not found" case.
- make Bitmap pointer accessors private, so Rust Bitmap API
  provides an actual abstraction boundary (Tamir)
- we still return `AllocError` in `Bitmap::new` in case client code
  asks for a size that is too large. Intentionally
  different from other bounds checks because it is not about
  access but allocation, and we expect that client code need
  never handle AllocError and nbits > u32::MAX situations
  differently.

Changes v2 --> v3:
- change `bitmap_copy` to `copy_from_bitmap_and_extend` which
  zeroes out extra bits. This enables dbitmap shrink and grow use
  cases while offering a consistent and understandable Rust API for
  other uses (Alice)

Changes v1 --> v2:
- Rebased on Yury's v2 [1] and Viresh's v3 [2] changes related to
  bitmap.
- Removed import of `bindings::*`, keeping only prefix (Miguel)
- Renamed panic methods to make more explicit (Miguel)
- use markdown in doc comments and added example/kunit test (Miguel)
- Added maintainer section for BITOPS API BINDINGS [RUST] (Yury)
- Added M: entry for bitmap.rs which goes to Alice (Viresh, Alice)
- Changed calls from find_* to _find_*, removed helpers (Yury)
- Use non-atomic __set_bit and __clear_bit from Bitmap Rust API (Yury)

Link [1] https://lore.kernel.org/all/20250224233938.3158-1-yury.norov@gmail.com/
Link [2] https://lore.kernel.org/rust-for-linux/cover.1742296835.git.viresh.kumar@linaro.org/
Link [v6] https://lore.kernel.org/rust-for-linux/20250327161617.117748-1-bqe@google.com/ 

Burak Emir (5):
  rust: add bindings for bitmap.h
  rust: add bindings for bitops.h
  rust: add bitmap API.
  rust: add find_bit_benchmark_rust module.
  rust: add dynamic ID pool abstraction for bitmap

 MAINTAINERS                     |  15 ++
 lib/Kconfig.debug               |  15 +-
 lib/Makefile                    |   1 +
 lib/find_bit_benchmark_rust.rs  | 102 ++++++++
 rust/bindings/bindings_helper.h |   2 +
 rust/helpers/bitmap.c           |   9 +
 rust/helpers/bitops.c           |  23 ++
 rust/helpers/helpers.c          |   2 +
 rust/kernel/bitmap.rs           | 410 ++++++++++++++++++++++++++++++++
 rust/kernel/id_pool.rs          | 201 ++++++++++++++++
 rust/kernel/lib.rs              |   2 +
 11 files changed, 781 insertions(+), 1 deletion(-)
 create mode 100644 lib/find_bit_benchmark_rust.rs
 create mode 100644 rust/helpers/bitmap.c
 create mode 100644 rust/helpers/bitops.c
 create mode 100644 rust/kernel/bitmap.rs
 create mode 100644 rust/kernel/id_pool.rs

-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Burak Emir]

This series adds a Rust bitmap API for porting the approach from
commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.

The Rust bitmap API provides a safe abstraction to underlying bitmap
and bitops operations. For now, only includes method necessary for
dbitmap.h, more can be added later. We perform bounds checks for
hardening, violations are programmer errors that result in panics.

We include set_bit_atomic and clear_bit_atomic operations. One has
to avoid races with non-atomic operations, which is ensure by the
Rust type system: either callers have shared references &bitmap in
which case the mutations are atomic operations. Or there is a
exclusive reference &mut bitmap, in which case there is no concurrent
access.

This version includes an optimization to represent the bitmap inline,
as suggested by Yury.

We introduce a Rust API that would replace (dbitmap.h) in file id_pool.rs. 
This data structure is tightly coupled to the bitmap API. Includes an example of usage
that requires releasing a spinlock, as expected in Binder driver.

This is v7 of a patch introducing Rust bitmap API [v6]. Thanks
for all the helpful comments, this series has improved significantly
as a result of your work.

Changes v6 --> v7:
- Added separate unit tests in bitmap.rs and benchmark module,
  following the example in find_bit_benchmark.c
- Added discussion about using vendored bitset to commit message.
- Refined warning about naming convention

Changes v5 --> v6:
- Added SAFETY comment for atomic operations.
- Added missing volatile to bitops set_bit and clear_bit bindings.
- Fixed condition on `nbits` to be <= i32::MAX, update SAFETY comments.
- Readability improvements.
- Updated doc comments wording and indentation.

Changes v4 --> v5: (suggested by Yury and Alice)
- rebased on next-20250318
- split MAINTAINERS changes
- no dependencies on [1] and [2] anymore - Viresh,
  please do add a separate section if you want to maintain cpumask.rs
  separately.
- imports atomic and non-atomic variants, introduces a naming convention
  set_bit and set_bit_atomic on the Rust side.
- changed naming and comments. Keeping `new`.
- change dynamic_id_pool to id_pool
- represent bitmap inline when possible
- add some more tests
- add myself to M: line for the Rust abstractions

Changes v3 --> v4:
- Rebased on Viresh's v3 [2].
- split into multiple patches, separate Rust and bindings. (Yury)
- adds dynamic_id_pool.rs to show the Binder use case. (Yury)
- include example usage that requires release of spinlock (Alice)
- changed bounds checks to `assert!`, shorter (Yury)
- fix param names in binding helpers. (Miguel)
- proper rustdoc formatting, and use examples as kunit tests. (Miguel)
- reduce number of Bitmap methods, and simplify API through
  use Option<usize> to handle the "not found" case.
- make Bitmap pointer accessors private, so Rust Bitmap API
  provides an actual abstraction boundary (Tamir)
- we still return `AllocError` in `Bitmap::new` in case client code
  asks for a size that is too large. Intentionally
  different from other bounds checks because it is not about
  access but allocation, and we expect that client code need
  never handle AllocError and nbits > u32::MAX situations
  differently.

Changes v2 --> v3:
- change `bitmap_copy` to `copy_from_bitmap_and_extend` which
  zeroes out extra bits. This enables dbitmap shrink and grow use
  cases while offering a consistent and understandable Rust API for
  other uses (Alice)

Changes v1 --> v2:
- Rebased on Yury's v2 [1] and Viresh's v3 [2] changes related to
  bitmap.
- Removed import of `bindings::*`, keeping only prefix (Miguel)
- Renamed panic methods to make more explicit (Miguel)
- use markdown in doc comments and added example/kunit test (Miguel)
- Added maintainer section for BITOPS API BINDINGS [RUST] (Yury)
- Added M: entry for bitmap.rs which goes to Alice (Viresh, Alice)
- Changed calls from find_* to _find_*, removed helpers (Yury)
- Use non-atomic __set_bit and __clear_bit from Bitmap Rust API (Yury)

Link [1] https://lore.kernel.org/all/20250224233938.3158-1-yury.norov@gmail.com/
Link [2] https://lore.kernel.org/rust-for-linux/cover.1742296835.git.viresh.kumar@linaro.org/
Link [v6] https://lore.kernel.org/rust-for-linux/20250327161617.117748-1-bqe@google.com/ 

Burak Emir (5):
  rust: add bindings for bitmap.h
  rust: add bindings for bitops.h
  rust: add bitmap API.
  rust: add find_bit_benchmark_rust module.
  rust: add dynamic ID pool abstraction for bitmap

 MAINTAINERS                     |  15 ++
 lib/Kconfig.debug               |  15 +-
 lib/Makefile                    |   1 +
 lib/find_bit_benchmark_rust.rs  | 102 ++++++++
 rust/bindings/bindings_helper.h |   2 +
 rust/helpers/bitmap.c           |   9 +
 rust/helpers/bitops.c           |  23 ++
 rust/helpers/helpers.c          |   2 +
 rust/kernel/bitmap.rs           | 410 ++++++++++++++++++++++++++++++++
 rust/kernel/id_pool.rs          | 201 ++++++++++++++++
 rust/kernel/lib.rs              |   2 +
 11 files changed, 781 insertions(+), 1 deletion(-)
 create mode 100644 lib/find_bit_benchmark_rust.rs
 create mode 100644 rust/helpers/bitmap.c
 create mode 100644 rust/helpers/bitops.c
 create mode 100644 rust/kernel/bitmap.rs
 create mode 100644 rust/kernel/id_pool.rs

-- 
2.49.0.805.g082f7c87e0-goog

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

I received it twice - with timestamps 1:36 and 1:43. Assuming they are
identical, and ignoring the former.

On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> This series adds a Rust bitmap API for porting the approach from
> commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> 
> The Rust bitmap API provides a safe abstraction to underlying bitmap
> and bitops operations. For now, only includes method necessary for
> dbitmap.h, more can be added later. We perform bounds checks for
> hardening, violations are programmer errors that result in panics.
> 
> We include set_bit_atomic and clear_bit_atomic operations. One has
> to avoid races with non-atomic operations, which is ensure by the
> Rust type system: either callers have shared references &bitmap in
> which case the mutations are atomic operations. Or there is a
> exclusive reference &mut bitmap, in which case there is no concurrent
> access.

It's not about shared references only. One can take a mutable
reference, and still may have a race:

CPU1                            CPU2

take mut ref
bitmap.set() // non-atomic
put mut ref     
                                take mut ref
                                bitmap.test() // read as 0
data propagated to memory       
                                bitmap.test() // read as 1

To make this scenario impossible, either put or take mut ref
should imply global cache flush, because bitmap array is not
an internal data for the Bitmap class (only the pointer is).

I already asked you to point me to the specification that states that
taking mutable reference implies flushing all the caches to the point
of coherency, but you didn't share it. And I doubt that compiler does
it, for the performance considerations.

Thanks,
Yury

> This version includes an optimization to represent the bitmap inline,
> as suggested by Yury.
> 
> We introduce a Rust API that would replace (dbitmap.h) in file id_pool.rs. 
> This data structure is tightly coupled to the bitmap API. Includes an example of usage
> that requires releasing a spinlock, as expected in Binder driver.
> 
> This is v7 of a patch introducing Rust bitmap API [v6]. Thanks
> for all the helpful comments, this series has improved significantly
> as a result of your work.
> 
> Changes v6 --> v7:
> - Added separate unit tests in bitmap.rs and benchmark module,
>   following the example in find_bit_benchmark.c
> - Added discussion about using vendored bitset to commit message.
> - Refined warning about naming convention
> 
> Changes v5 --> v6:
> - Added SAFETY comment for atomic operations.
> - Added missing volatile to bitops set_bit and clear_bit bindings.
> - Fixed condition on `nbits` to be <= i32::MAX, update SAFETY comments.
> - Readability improvements.
> - Updated doc comments wording and indentation.
> 
> Changes v4 --> v5: (suggested by Yury and Alice)
> - rebased on next-20250318
> - split MAINTAINERS changes
> - no dependencies on [1] and [2] anymore - Viresh,
>   please do add a separate section if you want to maintain cpumask.rs
>   separately.
> - imports atomic and non-atomic variants, introduces a naming convention
>   set_bit and set_bit_atomic on the Rust side.
> - changed naming and comments. Keeping `new`.
> - change dynamic_id_pool to id_pool
> - represent bitmap inline when possible
> - add some more tests
> - add myself to M: line for the Rust abstractions
> 
> Changes v3 --> v4:
> - Rebased on Viresh's v3 [2].
> - split into multiple patches, separate Rust and bindings. (Yury)
> - adds dynamic_id_pool.rs to show the Binder use case. (Yury)
> - include example usage that requires release of spinlock (Alice)
> - changed bounds checks to `assert!`, shorter (Yury)
> - fix param names in binding helpers. (Miguel)
> - proper rustdoc formatting, and use examples as kunit tests. (Miguel)
> - reduce number of Bitmap methods, and simplify API through
>   use Option<usize> to handle the "not found" case.
> - make Bitmap pointer accessors private, so Rust Bitmap API
>   provides an actual abstraction boundary (Tamir)
> - we still return `AllocError` in `Bitmap::new` in case client code
>   asks for a size that is too large. Intentionally
>   different from other bounds checks because it is not about
>   access but allocation, and we expect that client code need
>   never handle AllocError and nbits > u32::MAX situations
>   differently.
> 
> Changes v2 --> v3:
> - change `bitmap_copy` to `copy_from_bitmap_and_extend` which
>   zeroes out extra bits. This enables dbitmap shrink and grow use
>   cases while offering a consistent and understandable Rust API for
>   other uses (Alice)
> 
> Changes v1 --> v2:
> - Rebased on Yury's v2 [1] and Viresh's v3 [2] changes related to
>   bitmap.
> - Removed import of `bindings::*`, keeping only prefix (Miguel)
> - Renamed panic methods to make more explicit (Miguel)
> - use markdown in doc comments and added example/kunit test (Miguel)
> - Added maintainer section for BITOPS API BINDINGS [RUST] (Yury)
> - Added M: entry for bitmap.rs which goes to Alice (Viresh, Alice)
> - Changed calls from find_* to _find_*, removed helpers (Yury)
> - Use non-atomic __set_bit and __clear_bit from Bitmap Rust API (Yury)
> 
> Link [1] https://lore.kernel.org/all/20250224233938.3158-1-yury.norov@gmail.com/
> Link [2] https://lore.kernel.org/rust-for-linux/cover.1742296835.git.viresh.kumar@linaro.org/
> Link [v6] https://lore.kernel.org/rust-for-linux/20250327161617.117748-1-bqe@google.com/ 
> 
> Burak Emir (5):
>   rust: add bindings for bitmap.h
>   rust: add bindings for bitops.h
>   rust: add bitmap API.
>   rust: add find_bit_benchmark_rust module.
>   rust: add dynamic ID pool abstraction for bitmap
> 
>  MAINTAINERS                     |  15 ++
>  lib/Kconfig.debug               |  15 +-
>  lib/Makefile                    |   1 +
>  lib/find_bit_benchmark_rust.rs  | 102 ++++++++
>  rust/bindings/bindings_helper.h |   2 +
>  rust/helpers/bitmap.c           |   9 +
>  rust/helpers/bitops.c           |  23 ++
>  rust/helpers/helpers.c          |   2 +
>  rust/kernel/bitmap.rs           | 410 ++++++++++++++++++++++++++++++++
>  rust/kernel/id_pool.rs          | 201 ++++++++++++++++
>  rust/kernel/lib.rs              |   2 +
>  11 files changed, 781 insertions(+), 1 deletion(-)
>  create mode 100644 lib/find_bit_benchmark_rust.rs
>  create mode 100644 rust/helpers/bitmap.c
>  create mode 100644 rust/helpers/bitops.c
>  create mode 100644 rust/kernel/bitmap.rs
>  create mode 100644 rust/kernel/id_pool.rs
> 
> -- 
> 2.49.0.805.g082f7c87e0-goog

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Alice Ryhl]

On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> identical, and ignoring the former.
>
> On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > This series adds a Rust bitmap API for porting the approach from
> > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> >
> > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > and bitops operations. For now, only includes method necessary for
> > dbitmap.h, more can be added later. We perform bounds checks for
> > hardening, violations are programmer errors that result in panics.
> >
> > We include set_bit_atomic and clear_bit_atomic operations. One has
> > to avoid races with non-atomic operations, which is ensure by the
> > Rust type system: either callers have shared references &bitmap in
> > which case the mutations are atomic operations. Or there is a
> > exclusive reference &mut bitmap, in which case there is no concurrent
> > access.
>
> It's not about shared references only. One can take a mutable
> reference, and still may have a race:
>
> CPU1                            CPU2
>
> take mut ref
> bitmap.set() // non-atomic
> put mut ref
>                                 take mut ref
>                                 bitmap.test() // read as 0
> data propagated to memory
>                                 bitmap.test() // read as 1
>
> To make this scenario impossible, either put or take mut ref
> should imply global cache flush, because bitmap array is not
> an internal data for the Bitmap class (only the pointer is).
>
> I already asked you to point me to the specification that states that
> taking mutable reference implies flushing all the caches to the point
> of coherency, but you didn't share it. And I doubt that compiler does
> it, for the performance considerations.

The flushing of caches and so on *is* implied. It doesn't happen every
time you take a mutable reference, but for you to be able to take a
mut ref on CPU2 after releasing it on CPU1, there must be a flush
somewhere in between.

I can try to find docs for it ...

Alice

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > identical, and ignoring the former.
> >
> > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > This series adds a Rust bitmap API for porting the approach from
> > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > >
> > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > and bitops operations. For now, only includes method necessary for
> > > dbitmap.h, more can be added later. We perform bounds checks for
> > > hardening, violations are programmer errors that result in panics.
> > >
> > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > to avoid races with non-atomic operations, which is ensure by the
> > > Rust type system: either callers have shared references &bitmap in
> > > which case the mutations are atomic operations. Or there is a
> > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > access.
> >
> > It's not about shared references only. One can take a mutable
> > reference, and still may have a race:
> >
> > CPU1                            CPU2
> >
> > take mut ref
> > bitmap.set() // non-atomic
> > put mut ref
> >                                 take mut ref
> >                                 bitmap.test() // read as 0
> > data propagated to memory
> >                                 bitmap.test() // read as 1
> >
> > To make this scenario impossible, either put or take mut ref
> > should imply global cache flush, because bitmap array is not
> > an internal data for the Bitmap class (only the pointer is).
> >
> > I already asked you to point me to the specification that states that
> > taking mutable reference implies flushing all the caches to the point
> > of coherency, but you didn't share it. And I doubt that compiler does
> > it, for the performance considerations.
> 
> The flushing of caches and so on *is* implied. It doesn't happen every
> time you take a mutable reference, but for you to be able to take a
> mut ref on CPU2 after releasing it on CPU1, there must be a flush
> somewhere in between.
> 

Yeah, and it's not just "flushing of caches", it's making CPU1's memory
operations on the object pointed by "mut ref" observable to CPU2. If
CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
CPU1 and CPU2 sync with a store-release+load-acquire, the
RELEASE-ACQUIRE ordering guarantees that as well.

Regards,
Boqun

> I can try to find docs for it ...
> 
> Alice

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > >
> > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > identical, and ignoring the former.
> > >
> > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > This series adds a Rust bitmap API for porting the approach from
> > > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > > >
> > > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > > and bitops operations. For now, only includes method necessary for
> > > > dbitmap.h, more can be added later. We perform bounds checks for
> > > > hardening, violations are programmer errors that result in panics.
> > > >
> > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > to avoid races with non-atomic operations, which is ensure by the
> > > > Rust type system: either callers have shared references &bitmap in
> > > > which case the mutations are atomic operations. Or there is a
> > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > access.
> > >
> > > It's not about shared references only. One can take a mutable
> > > reference, and still may have a race:
> > >
> > > CPU1                            CPU2
> > >
> > > take mut ref
> > > bitmap.set() // non-atomic
> > > put mut ref
> > >                                 take mut ref
> > >                                 bitmap.test() // read as 0
> > > data propagated to memory
> > >                                 bitmap.test() // read as 1
> > >
> > > To make this scenario impossible, either put or take mut ref
> > > should imply global cache flush, because bitmap array is not
> > > an internal data for the Bitmap class (only the pointer is).
> > >
> > > I already asked you to point me to the specification that states that
> > > taking mutable reference implies flushing all the caches to the point
> > > of coherency, but you didn't share it. And I doubt that compiler does
> > > it, for the performance considerations.
> > 
> > The flushing of caches and so on *is* implied. It doesn't happen every
> > time you take a mutable reference, but for you to be able to take a
> > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > somewhere in between.
> > 
> 
> Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> operations on the object pointed by "mut ref" observable to CPU2. If
> CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> CPU1 and CPU2 sync with a store-release+load-acquire, the
> RELEASE-ACQUIRE ordering guarantees that as well.

Not sure what you mean. Atomic set_bit() and clear() bit are often
implemented in asm, and there's no acquire-release semantic.

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 01:11:21PM -0400, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > >
> > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > identical, and ignoring the former.
> > > >
> > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > This series adds a Rust bitmap API for porting the approach from
> > > > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > > > >
> > > > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > > > and bitops operations. For now, only includes method necessary for
> > > > > dbitmap.h, more can be added later. We perform bounds checks for
> > > > > hardening, violations are programmer errors that result in panics.
> > > > >
> > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > Rust type system: either callers have shared references &bitmap in
> > > > > which case the mutations are atomic operations. Or there is a
> > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > access.
> > > >
> > > > It's not about shared references only. One can take a mutable
> > > > reference, and still may have a race:
> > > >
> > > > CPU1                            CPU2
> > > >
> > > > take mut ref
> > > > bitmap.set() // non-atomic
> > > > put mut ref
> > > >                                 take mut ref
> > > >                                 bitmap.test() // read as 0
> > > > data propagated to memory
> > > >                                 bitmap.test() // read as 1
> > > >
> > > > To make this scenario impossible, either put or take mut ref
> > > > should imply global cache flush, because bitmap array is not
> > > > an internal data for the Bitmap class (only the pointer is).
> > > >
> > > > I already asked you to point me to the specification that states that
> > > > taking mutable reference implies flushing all the caches to the point
> > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > it, for the performance considerations.
> > > 
> > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > time you take a mutable reference, but for you to be able to take a
> > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > somewhere in between.
> > > 
> > 
> > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > operations on the object pointed by "mut ref" observable to CPU2. If
> > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > RELEASE-ACQUIRE ordering guarantees that as well.
> 
> Not sure what you mean. Atomic set_bit() and clear() bit are often
> implemented in asm, and there's no acquire-release semantic.
> 

Well, that's because they are already atomic, therefore no need to
synchronize. Plus if you were to use set_bit() and test_bit() in your
example above, the test_bit() on CPU2 could reads 0, right? I.e. it's
a total different scenario. That is, if you don't synchronize the
operations between two CPUs, you don't get a guarantee of the
observation ordering.

Back the the non-atomic version, taking a very simple example in C,
considering you have:

	struct foo {
		spinlock_t lock;
		long *bitmap;
	}

if you only use non-atomic version i.e. __set_bit() and
__test_bit(), you will need to use lock to synchronize them:

	CPU1			CPU2
	====			====
	spin_lock(&foo->lock);
	__set_bit(foo->bitmap, ...);
	spin_unlock(&foo->lock);
				spin_lock(&foo->lock);
				__test_bit(foo->bitmap, ...);
				// ^ read as 1, because of the lock
				// synchronizes these operations.
				spin_unlock(&foo->lock);

Now if we move to Rust, we will have:

	type Foo = SpinLock<Bitmap>;

and
	CPU1			CPU2
	====
	let foo: &Foo = ...;

	let bitmap: Guard<Bitmap> = foo.lock();

	bitmap.set_bit(); // Guard impls DerefMut

	// lock dropped
				let foo: &Foo = ...;

				let bitmap: Guard<Bitmap> = foo.lock();

				bitmap.test_bit(); // read as 1, same
						   // because of the
						   // lock
						   // synchronization.

So there is nothing different between Rust and C code in this case,
except because in the Rust API, we define that Bitmap::set_bit() and
Bitmap::test_bit() have to take a mutable references, therefore the lock
or some other synchronization has to exist to provide the `&mut Bitmap`,
otherwise you cannot call these functions.

Regards,
Boqun

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 01:11:24PM -0400, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > >
> > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > identical, and ignoring the former.
> > > >
> > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > This series adds a Rust bitmap API for porting the approach from
> > > > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > > > >
> > > > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > > > and bitops operations. For now, only includes method necessary for
> > > > > dbitmap.h, more can be added later. We perform bounds checks for
> > > > > hardening, violations are programmer errors that result in panics.
> > > > >
> > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > Rust type system: either callers have shared references &bitmap in
> > > > > which case the mutations are atomic operations. Or there is a
> > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > access.
> > > >
> > > > It's not about shared references only. One can take a mutable
> > > > reference, and still may have a race:
> > > >
> > > > CPU1                            CPU2
> > > >
> > > > take mut ref
> > > > bitmap.set() // non-atomic
> > > > put mut ref
> > > >                                 take mut ref
> > > >                                 bitmap.test() // read as 0
> > > > data propagated to memory
> > > >                                 bitmap.test() // read as 1
> > > >
> > > > To make this scenario impossible, either put or take mut ref
> > > > should imply global cache flush, because bitmap array is not
> > > > an internal data for the Bitmap class (only the pointer is).
> > > >
> > > > I already asked you to point me to the specification that states that
> > > > taking mutable reference implies flushing all the caches to the point
> > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > it, for the performance considerations.
> > > 
> > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > time you take a mutable reference, but for you to be able to take a
> > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > somewhere in between.
> > > 
> > 
> > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > operations on the object pointed by "mut ref" observable to CPU2. If
> > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > RELEASE-ACQUIRE ordering guarantees that as well.
> 
> Not sure what you mean. Atomic set_bit() and clear() bit are often
> implemented in asm, and there's no acquire-release semantic.

Sorry, hit 'send' preliminary.

> > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > operations on the object pointed by "mut ref" observable to CPU2. If
> > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 

The problem here is that the object pointed by the 'mut ref' is the
rust class Bitmap. The class itself allocates an array, which is used
as an actual storage. The Rust class and C array will likely not share
cache lines.

The pointer is returned from a C call bitmap_zalloc(), so I don't
think it's possible for Rust compiler to realize that the number
stored in Bitmap is a pointer to data of certain size, and that it
should be flushed at "mut ref" put... That's why I guessed a global
flush.

Yeah, would be great to understand how this all works.

As a side question: in regular C spinlocks, can you point me to the
place where the caches get flushed when a lock moves from CPU1 to
CPU2? I spent some time looking at the code, but found nothing myself.
Or this implemented in a different way?

Thanks,
Yury

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 01:34:22PM -0400, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 01:11:24PM -0400, Yury Norov wrote:
> > On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > >
> > > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > > identical, and ignoring the former.
> > > > >
> > > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > > This series adds a Rust bitmap API for porting the approach from
> > > > > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > > > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > > > > >
> > > > > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > > > > and bitops operations. For now, only includes method necessary for
> > > > > > dbitmap.h, more can be added later. We perform bounds checks for
> > > > > > hardening, violations are programmer errors that result in panics.
> > > > > >
> > > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > > Rust type system: either callers have shared references &bitmap in
> > > > > > which case the mutations are atomic operations. Or there is a
> > > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > > access.
> > > > >
> > > > > It's not about shared references only. One can take a mutable
> > > > > reference, and still may have a race:
> > > > >
> > > > > CPU1                            CPU2
> > > > >
> > > > > take mut ref
> > > > > bitmap.set() // non-atomic
> > > > > put mut ref
> > > > >                                 take mut ref
> > > > >                                 bitmap.test() // read as 0
> > > > > data propagated to memory
> > > > >                                 bitmap.test() // read as 1
> > > > >
> > > > > To make this scenario impossible, either put or take mut ref
> > > > > should imply global cache flush, because bitmap array is not
> > > > > an internal data for the Bitmap class (only the pointer is).
> > > > >
> > > > > I already asked you to point me to the specification that states that
> > > > > taking mutable reference implies flushing all the caches to the point
> > > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > > it, for the performance considerations.
> > > > 
> > > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > > time you take a mutable reference, but for you to be able to take a
> > > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > > somewhere in between.
> > > > 
> > > 
> > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > > RELEASE-ACQUIRE ordering guarantees that as well.
> > 
> > Not sure what you mean. Atomic set_bit() and clear() bit are often
> > implemented in asm, and there's no acquire-release semantic.
> 
> Sorry, hit 'send' preliminary.
> 
> > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 
> 
> The problem here is that the object pointed by the 'mut ref' is the
> rust class Bitmap. The class itself allocates an array, which is used
> as an actual storage. The Rust class and C array will likely not share
> cache lines.
> 
> The pointer is returned from a C call bitmap_zalloc(), so I don't
> think it's possible for Rust compiler to realize that the number
> stored in Bitmap is a pointer to data of certain size, and that it
> should be flushed at "mut ref" put... That's why I guessed a global
> flush.
> 

You don't do the flush in the C code either, right? You would rely on
some existing synchronization between threads to make sure CPU2 observes
the memory effect of CPU1 (if that's what you want).

> Yeah, would be great to understand how this all works.
> 
> As a side question: in regular C spinlocks, can you point me to the
> place where the caches get flushed when a lock moves from CPU1 to
> CPU2? I spent some time looking at the code, but found nothing myself.
> Or this implemented in a different way?

Oh I see, the simple answer would be "the fact that cache flushing is
done is implied", now let's take a simple example:

	CPU 1			CPU 2
	=====			=====
	spin_lock();
	x = 1;
	spin_unlock();

				spin_lock();
				r1 = x;		// r1 == 1
				spin_unlock();

that is, if CPU 2 gets the lock later than CPU 1, r1 is guaranteed to be
1, right? Now let's open the box, with a trivial spinlock implementation:

	CPU 1			CPU 2
	=====			=====
	spin_lock();
	x = 1;
	spin_unlock():
	  smp_store_release(lock, 0);

				spin_lock():
				  while (cmpxchg_acquire(lock, 0, 1) != 0) { }
				  
				r1 = x;		// r1 == 1
				spin_unlock();

now, for CPU2 to acquire the lock, the cmpxchg_acquire() has to succeed,
that means a few things:

1. 	CPU2 observes the lock value to be 0, i.e CPU2 observes the
	store of CPU1 on the lock.

2.	Since the smp_store_release() on CPU1, and the cmpxchg_acquire()
	on CPU2, it's guaranteed that CPU2 has observed the memory
	effect before the smp_store_release() on CPU1. And this is the
	"implied" part. In the real hardware cache protocal, what the
	smp_store_release() does is basically "flush/invalidate the
	cache and issue the store", therefore since CPU2 observes the
	store part of the smp_store_release(), it's implied that the
	cache flush/invalidate is observed by CPU2 already. Of course
	the actual hardware cache protocal is more complicated, but this
	is the gist of it.

Based on 1 & 2, normally a programer won't need to reason about where
the cache flush is actually issued, but rather the synchronization built
vi the shared variables (in this case, it's the "lock").

Hope this could help.

Regards,
Boqun


> 
> Thanks,
> Yury

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 10:52:19AM -0700, Boqun Feng wrote:
> On Wed, Apr 23, 2025 at 01:34:22PM -0400, Yury Norov wrote:
> > On Wed, Apr 23, 2025 at 01:11:24PM -0400, Yury Norov wrote:
> > > On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > > > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > >
> > > > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > > > identical, and ignoring the former.
> > > > > >
> > > > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > > > This series adds a Rust bitmap API for porting the approach from
> > > > > > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > > > > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > > > > > >
> > > > > > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > > > > > and bitops operations. For now, only includes method necessary for
> > > > > > > dbitmap.h, more can be added later. We perform bounds checks for
> > > > > > > hardening, violations are programmer errors that result in panics.
> > > > > > >
> > > > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > > > Rust type system: either callers have shared references &bitmap in
> > > > > > > which case the mutations are atomic operations. Or there is a
> > > > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > > > access.
> > > > > >
> > > > > > It's not about shared references only. One can take a mutable
> > > > > > reference, and still may have a race:
> > > > > >
> > > > > > CPU1                            CPU2
> > > > > >
> > > > > > take mut ref
> > > > > > bitmap.set() // non-atomic
> > > > > > put mut ref
> > > > > >                                 take mut ref
> > > > > >                                 bitmap.test() // read as 0
> > > > > > data propagated to memory
> > > > > >                                 bitmap.test() // read as 1
> > > > > >
> > > > > > To make this scenario impossible, either put or take mut ref
> > > > > > should imply global cache flush, because bitmap array is not
> > > > > > an internal data for the Bitmap class (only the pointer is).
> > > > > >
> > > > > > I already asked you to point me to the specification that states that
> > > > > > taking mutable reference implies flushing all the caches to the point
> > > > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > > > it, for the performance considerations.
> > > > > 
> > > > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > > > time you take a mutable reference, but for you to be able to take a
> > > > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > > > somewhere in between.
> > > > > 
> > > > 
> > > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > > > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > > > RELEASE-ACQUIRE ordering guarantees that as well.
> > > 
> > > Not sure what you mean. Atomic set_bit() and clear() bit are often
> > > implemented in asm, and there's no acquire-release semantic.
> > 
> > Sorry, hit 'send' preliminary.
> > 
> > > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 
> > 
> > The problem here is that the object pointed by the 'mut ref' is the
> > rust class Bitmap. The class itself allocates an array, which is used
> > as an actual storage. The Rust class and C array will likely not share
> > cache lines.
> > 
> > The pointer is returned from a C call bitmap_zalloc(), so I don't
> > think it's possible for Rust compiler to realize that the number
> > stored in Bitmap is a pointer to data of certain size, and that it
> > should be flushed at "mut ref" put... That's why I guessed a global
> > flush.
> > 
> 
> You don't do the flush in the C code either, right? You would rely on
> some existing synchronization between threads to make sure CPU2 observes
> the memory effect of CPU1 (if that's what you want).
> 
> > Yeah, would be great to understand how this all works.
> > 
> > As a side question: in regular C spinlocks, can you point me to the
> > place where the caches get flushed when a lock moves from CPU1 to
> > CPU2? I spent some time looking at the code, but found nothing myself.
> > Or this implemented in a different way?
> 
> Oh I see, the simple answer would be "the fact that cache flushing is
> done is implied", now let's take a simple example:
> 
> 	CPU 1			CPU 2
> 	=====			=====
> 	spin_lock();
> 	x = 1;
> 	spin_unlock();
> 
> 				spin_lock();
> 				r1 = x;		// r1 == 1
> 				spin_unlock();
> 
> that is, if CPU 2 gets the lock later than CPU 1, r1 is guaranteed to be
> 1, right? Now let's open the box, with a trivial spinlock implementation:
> 
> 	CPU 1			CPU 2
> 	=====			=====
> 	spin_lock();
> 	x = 1;
> 	spin_unlock():
> 	  smp_store_release(lock, 0);
> 
> 				spin_lock():
> 				  while (cmpxchg_acquire(lock, 0, 1) != 0) { }
> 				  
> 				r1 = x;		// r1 == 1
> 				spin_unlock();
> 
> now, for CPU2 to acquire the lock, the cmpxchg_acquire() has to succeed,
> that means a few things:
> 
> 1. 	CPU2 observes the lock value to be 0, i.e CPU2 observes the
> 	store of CPU1 on the lock.
> 
> 2.	Since the smp_store_release() on CPU1, and the cmpxchg_acquire()
> 	on CPU2, it's guaranteed that CPU2 has observed the memory
> 	effect before the smp_store_release() on CPU1. And this is the
> 	"implied" part. In the real hardware cache protocal, what the
> 	smp_store_release() does is basically "flush/invalidate the
> 	cache and issue the store", therefore since CPU2 observes the
> 	store part of the smp_store_release(), it's implied that the
> 	cache flush/invalidate is observed by CPU2 already. Of course
> 	the actual hardware cache protocal is more complicated, but this
> 	is the gist of it.
> 
> Based on 1 & 2, normally a programer won't need to reason about where
> the cache flush is actually issued, but rather the synchronization built
> vi the shared variables (in this case, it's the "lock").
> 
> Hope this could help.

Yeah, that helped a lot. Thank you!

So, if this Rust mutable reference is implemented similarly to a
regular spinlock, I've no more questions.

Thanks again for the explanation.

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 02:00:50PM -0400, Yury Norov wrote:
[...]
> > > > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 
> > > 
> > > The problem here is that the object pointed by the 'mut ref' is the
> > > rust class Bitmap. The class itself allocates an array, which is used
> > > as an actual storage. The Rust class and C array will likely not share
> > > cache lines.
> > > 
> > > The pointer is returned from a C call bitmap_zalloc(), so I don't
> > > think it's possible for Rust compiler to realize that the number
> > > stored in Bitmap is a pointer to data of certain size, and that it
> > > should be flushed at "mut ref" put... That's why I guessed a global
> > > flush.
> > > 
> > 
> > You don't do the flush in the C code either, right? You would rely on
> > some existing synchronization between threads to make sure CPU2 observes
> > the memory effect of CPU1 (if that's what you want).
> > 
> > > Yeah, would be great to understand how this all works.
> > > 
> > > As a side question: in regular C spinlocks, can you point me to the
> > > place where the caches get flushed when a lock moves from CPU1 to
> > > CPU2? I spent some time looking at the code, but found nothing myself.
> > > Or this implemented in a different way?
> > 
> > Oh I see, the simple answer would be "the fact that cache flushing is
> > done is implied", now let's take a simple example:
> > 
> > 	CPU 1			CPU 2
> > 	=====			=====
> > 	spin_lock();
> > 	x = 1;
> > 	spin_unlock();
> > 
> > 				spin_lock();
> > 				r1 = x;		// r1 == 1
> > 				spin_unlock();
> > 
> > that is, if CPU 2 gets the lock later than CPU 1, r1 is guaranteed to be
> > 1, right? Now let's open the box, with a trivial spinlock implementation:
> > 
> > 	CPU 1			CPU 2
> > 	=====			=====
> > 	spin_lock();
> > 	x = 1;
> > 	spin_unlock():
> > 	  smp_store_release(lock, 0);
> > 
> > 				spin_lock():
> > 				  while (cmpxchg_acquire(lock, 0, 1) != 0) { }
> > 				  
> > 				r1 = x;		// r1 == 1
> > 				spin_unlock();
> > 
> > now, for CPU2 to acquire the lock, the cmpxchg_acquire() has to succeed,
> > that means a few things:
> > 
> > 1. 	CPU2 observes the lock value to be 0, i.e CPU2 observes the
> > 	store of CPU1 on the lock.
> > 
> > 2.	Since the smp_store_release() on CPU1, and the cmpxchg_acquire()
> > 	on CPU2, it's guaranteed that CPU2 has observed the memory
> > 	effect before the smp_store_release() on CPU1. And this is the
> > 	"implied" part. In the real hardware cache protocal, what the
> > 	smp_store_release() does is basically "flush/invalidate the
> > 	cache and issue the store", therefore since CPU2 observes the
> > 	store part of the smp_store_release(), it's implied that the
> > 	cache flush/invalidate is observed by CPU2 already. Of course
> > 	the actual hardware cache protocal is more complicated, but this
> > 	is the gist of it.
> > 
> > Based on 1 & 2, normally a programer won't need to reason about where
> > the cache flush is actually issued, but rather the synchronization built
> > vi the shared variables (in this case, it's the "lock").
> > 
> > Hope this could help.
> 
> Yeah, that helped a lot. Thank you!
> 
> So, if this Rust mutable reference is implemented similarly to a
> regular spinlock, I've no more questions.
> 

Just to be clear, a mutable reference in Rust is just a pointer (with
special compiler treatment for checking and optimzation), so mutable
reference is not "implemented similarly to a regular spinlock", it's
rather that: if you have a shared data, and you want to get a mutable
reference, you will have to use some synchronization, and maybe 90% case
that's a lock.

So here, what Burak did in Bitmap was defining those non-atomic
functions as requiring mutable references, and if we also get the Sync
and Send part, right. A real user would 90% use a lock to access a
mutable reference to `Bitmap`.

Makes sense?

Regards,
Boqun

> Thanks again for the explanation.

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > identical, and ignoring the former.
> >
> > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > This series adds a Rust bitmap API for porting the approach from
> > > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> > >
> > > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > > and bitops operations. For now, only includes method necessary for
> > > dbitmap.h, more can be added later. We perform bounds checks for
> > > hardening, violations are programmer errors that result in panics.
> > >
> > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > to avoid races with non-atomic operations, which is ensure by the
> > > Rust type system: either callers have shared references &bitmap in
> > > which case the mutations are atomic operations. Or there is a
> > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > access.
> >
> > It's not about shared references only. One can take a mutable
> > reference, and still may have a race:
> >
> > CPU1                            CPU2
> >
> > take mut ref
> > bitmap.set() // non-atomic
> > put mut ref
> >                                 take mut ref
> >                                 bitmap.test() // read as 0
> > data propagated to memory
> >                                 bitmap.test() // read as 1
> >
> > To make this scenario impossible, either put or take mut ref
> > should imply global cache flush, because bitmap array is not
> > an internal data for the Bitmap class (only the pointer is).
> >
> > I already asked you to point me to the specification that states that
> > taking mutable reference implies flushing all the caches to the point
> > of coherency, but you didn't share it. And I doubt that compiler does
> > it, for the performance considerations.
> 
> The flushing of caches and so on *is* implied. It doesn't happen every
> time you take a mutable reference, but for you to be able to take a
> mut ref on CPU2 after releasing it on CPU1, there must be a flush
> somewhere in between.

OK, that makes sense.
 
> I can try to find docs for it ...

Yes please, that would help a lot.