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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <680923cd.050a0220.2b2efe.cb68@mx.google.com>
Date: Wed, 23 Apr 2025 10:30:51 -0700
From: Boqun Feng <boqun.feng@...il.com>
To: Yury Norov <yury.norov@...il.com>
Cc: Alice Ryhl <aliceryhl@...gle.com>, Burak Emir <bqe@...gle.com>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Viresh Kumar <viresh.kumar@...aro.org>,
	Miguel Ojeda <ojeda@...nel.org>,
	Alex Gaynor <alex.gaynor@...il.com>, Gary Guo <gary@...yguo.net>,
	Björn Roy Baron <bjorn3_gh@...tonmail.com>,
	Benno Lossin <benno.lossin@...ton.me>,
	Andreas Hindborg <a.hindborg@...nel.org>,
	Trevor Gross <tmgross@...ch.edu>, rust-for-linux@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

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@...il.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