From nobody Sun Feb 8 07:07:42 2026 Received: from mail-ej1-f73.google.com (mail-ej1-f73.google.com [209.85.218.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 297F01FC0ED for ; Wed, 12 Nov 2025 12:47:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951653; cv=none; b=gUzcejHlYo68Xo6xNDD2D6RyLtFabitEnLhPX6KNLaHuIm0Ovrb2aLOmImkQuzqD7GtZ+e/zlqpf6IyW3pP9Gh8EOu0zX4K3WyRJwXjFINIiYVfxeWErjZwUtVbUP4k87FA+O3TV7Nn0B3mWpvxvMD/ZBhNzQ5LdVEFtBUDVR5o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951653; c=relaxed/simple; bh=X6NcK0k/Pyfy97JmdhmqAaR+ITlI48wDQZzcDWzyNW4=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=qa5SSY61i7OSgIOBsde9XmzJPefU0s44hv5bTg3SvNmA+7bLrNOBliWalUhLfgaQheRGQyxiCHPQe9l/1PGuj++wnZne28ZnkGV4fs5dgEVOJi85kdpWWusJ6WAfKcn3MCROVQoXXB2YgMTFlfhJBXPAXS2VKPwdisgL5Lb+rVc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=WCdV5CUf; arc=none smtp.client-ip=209.85.218.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="WCdV5CUf" Received: by mail-ej1-f73.google.com with SMTP id a640c23a62f3a-b72a8546d73so118774466b.2 for ; Wed, 12 Nov 2025 04:47:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1762951649; x=1763556449; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=SAPT0u/fN1O7Tqhzk10/gAmec0w5iUVWhVAvyTNB5a0=; b=WCdV5CUfCoDOHciCeSvkgvhOG2XmyllQcRTvgheH4PmFcAa+3vHZiK4ojlEHOqOebN MHck/rNWncaK3aMH9M3t4FE0gYLQ90LehIVRxe2WYuxBYJH1/a7MGSZZO0dnmQv01yUt 9z7NZie8ErJPKFHKWTbmnLA6ccU2aLo2RaQjB8bLZuK/OGc1+PNR0A2OZwfsSxjc89U1 jT9bDD9cEz5An5go2o524FAJ6RXPDGoc2DTHoHIRqtvDWsJ1dpo/s6+s0QuJU7SoHMI/ 1sQnP1uSULiVaUGiWkUnl5TxrcKaztMYfbERszHNerRyJ4rfYFMDchSSNC1s+9sUSext Wi8g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762951649; x=1763556449; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=SAPT0u/fN1O7Tqhzk10/gAmec0w5iUVWhVAvyTNB5a0=; b=FjKe6Ix5PCXaRwD75p/+pHXs9UyO+cn23pf2S65CPaAZzVZAON4s3OqTjdHZwWLIwI JH40PsGNc2NUH+Si7uM/ixZWhujyhwwIhlwnfbrkSUUMyfLIGqvcW/PRP/TAaZh+5yMg LKDKMFXLDswrHDHWwY1ClIZtTmDX+ndfjoYYPjg80njQuDPpshffecc51QsbHwo2Xs5D gkQY9oxDWRBMa52tYIDuTExiPrBkKkV/e8xfPqLgBWvZQIOEjco8i9aProdjIS+AGYef NkQBT51XB4ufHSIcmHuEIK9chCTyjizgfPHfm9ghn1ij7hhKYdC6HpBG5UFYl3XjWhQn sIyg== X-Forwarded-Encrypted: i=1; AJvYcCX0IPTFQe7IHS8bvP3KTRH+F0ZGXwy2r6dRMSCOLefCe0m/jdEMt6NcG6Oympwm/D5PIGMBPz2gwdXWzAE=@vger.kernel.org X-Gm-Message-State: AOJu0Yx3LhMVoKs2h/d2y1+5S3iyqsjQJBxCIK4h+9F3xjB4iEavcHl9 Uz/jlpPshSqbyG7fTbKpB0y7uIK8G0F4bIAegtvf77igM45j6QmsAf9R1GJbO3MxzB7G1LUk56O kRjG7Yx+T8g6hNYEj6g== X-Google-Smtp-Source: AGHT+IG+oxkk381YdnPvrV9XYVT4rT4ROPIVKK58YXIC3EtMv/V8BsKNVnhPtKxqkj30PTF6s2NWb4Q3M5opdnc= X-Received: from ede24.prod.google.com ([2002:a05:6402:20d8:b0:643:1228:ed3]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a17:907:da6:b0:b3f:a960:e057 with SMTP id a640c23a62f3a-b7331a6c6e9mr333748766b.31.1762951649439; Wed, 12 Nov 2025 04:47:29 -0800 (PST) Date: Wed, 12 Nov 2025 12:47:19 +0000 In-Reply-To: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=8727; i=aliceryhl@google.com; h=from:subject:message-id; bh=X6NcK0k/Pyfy97JmdhmqAaR+ITlI48wDQZzcDWzyNW4=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpFIHetSDI36a0nOIE5ti0/UIKWfmiLVbAsSvTx w7Q9pAQrjKJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaRSB3gAKCRAEWL7uWMY5 RuTvD/9NTldWQsFQlXyOqAySTx0JjNgRFEDdOijOfGUIlLSwtqqkKq9d1WiyJigNglAbFLf+5z2 PFkSu5BioTGBrtJqLr4ujndUnTUertv+F9nglShuwAB+TDidXE2B2fIMGmSToRyqS14+ZK7Gh8C uHycMOYvradgzer6ArWg4ZowlJQR/T3pWN6EYy4jH8PYlbyLkWuxeftT6n1LOSbhtpwaO6YtNLW c3PAAdmkNG4cSgrn0hNTWvAgaChtSmWGf/Kfeb8oAYIrmIM8L6jAfwjFjtW+JsfqMUoVFpTZyMd uSJg3bZ0jkZItFGGeapPfLptj/nz6q5f6eqqDycWWppCag8LEkyXH8QKPOkEj9xWZzJecaWvUD7 jj2xMqPBXfHi2Ociro+N4Q1od/Z0scD+OGJxxFcOpWNTl66qIhgvQRpnq2rVgn1mITfpLWprun6 nZdjI8PID9ELFepR2pL/yatSGCodqRuJn0uNq0pvEXJgnAGgMpIYKrJH2gqt5rM+vr8oFC3nnjM phDwo7L0L2vxnmyt/RXXTXjewGdqa76FjQDyy0xxUflqmaDrlpM+ehayvqSg65LOrfB+VBWWWFC 3Dh9fsX40wmdrAqLrE0T20CZVPae3D6HmZiJu7BHwC9F0xIF0tGNGPNVNR6bPAyz+8aeDSaLy3u nVDybgz3LO/0Chg== X-Mailer: b4 0.14.2 Message-ID: <20251112-binder-bitmap-v5-1-8b9d7c7eca82@google.com> Subject: [PATCH v5 1/6] rust: bitmap: add MAX_LEN and MAX_INLINE_LEN constants From: Alice Ryhl To: Greg Kroah-Hartman , Yury Norov Cc: "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Burak Emir , Miguel Ojeda , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable To avoid hard-coding these values in drivers, define constants for them that drivers can reference. Also, update all instances in bitmap.rs and id_pool.rs that use these values to use the new constants. Signed-off-by: Alice Ryhl --- rust/kernel/bitmap.rs | 33 +++++++++++++++++++-------------- rust/kernel/id_pool.rs | 29 ++++++++++++++--------------- 2 files changed, 33 insertions(+), 29 deletions(-) diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index aa8fc7bf06fc99865ae755d8694e4bec3dc8e7f0..0705646c6251a49f213a45f1f01= 3cb9eb2ed81de 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -12,8 +12,6 @@ use crate::pr_err; use core::ptr::NonNull; =20 -const BITS_PER_LONG: usize =3D bindings::BITS_PER_LONG as usize; - /// Represents a C bitmap. Wraps underlying C bitmap API. /// /// # Invariants @@ -149,14 +147,14 @@ macro_rules! bitmap_assert_return { /// /// # Invariants /// -/// * `nbits` is `<=3D i32::MAX` and never changes. -/// * if `nbits <=3D bindings::BITS_PER_LONG`, then `repr` is a `usize`. +/// * `nbits` is `<=3D MAX_LEN`. +/// * if `nbits <=3D MAX_INLINE_LEN`, then `repr` is a `usize`. /// * otherwise, `repr` holds a non-null pointer to an initialized /// array of `unsigned long` that is large enough to hold `nbits` bits. pub struct BitmapVec { /// Representation of bitmap. repr: BitmapRepr, - /// Length of this bitmap. Must be `<=3D i32::MAX`. + /// Length of this bitmap. Must be `<=3D MAX_LEN`. nbits: usize, } =20 @@ -164,7 +162,7 @@ impl core::ops::Deref for BitmapVec { type Target =3D Bitmap; =20 fn deref(&self) -> &Bitmap { - let ptr =3D if self.nbits <=3D BITS_PER_LONG { + let ptr =3D if self.nbits <=3D BitmapVec::MAX_INLINE_LEN { // SAFETY: Bitmap is represented inline. #[allow(unused_unsafe, reason =3D "Safe since Rust 1.92.0")] unsafe { @@ -183,7 +181,7 @@ fn deref(&self) -> &Bitmap { =20 impl core::ops::DerefMut for BitmapVec { fn deref_mut(&mut self) -> &mut Bitmap { - let ptr =3D if self.nbits <=3D BITS_PER_LONG { + let ptr =3D if self.nbits <=3D BitmapVec::MAX_INLINE_LEN { // SAFETY: Bitmap is represented inline. #[allow(unused_unsafe, reason =3D "Safe since Rust 1.92.0")] unsafe { @@ -213,7 +211,7 @@ unsafe impl Sync for BitmapVec {} =20 impl Drop for BitmapVec { fn drop(&mut self) { - if self.nbits <=3D BITS_PER_LONG { + if self.nbits <=3D BitmapVec::MAX_INLINE_LEN { return; } // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`. @@ -226,23 +224,29 @@ fn drop(&mut self) { } =20 impl BitmapVec { + /// The maximum possible length of a `BitmapVec`. + pub const MAX_LEN: usize =3D i32::MAX as usize; + + /// The maximum length that uses the inline representation. + pub const MAX_INLINE_LEN: usize =3D usize::BITS as usize; + /// Constructs a new [`BitmapVec`]. /// /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allo= cated. This - /// includes the case when `nbits` is greater than `i32::MAX`. + /// includes the case when `nbits` is greater than `MAX_LEN`. #[inline] pub fn new(nbits: usize, flags: Flags) -> Result { - if nbits <=3D BITS_PER_LONG { + if nbits <=3D BitmapVec::MAX_INLINE_LEN { return Ok(BitmapVec { repr: BitmapRepr { bitmap: 0 }, nbits, }); } - if nbits > i32::MAX.try_into().unwrap() { + if nbits > Self::MAX_LEN { return Err(AllocError); } let nbits_u32 =3D u32::try_from(nbits).unwrap(); - // SAFETY: `BITS_PER_LONG < nbits` and `nbits <=3D i32::MAX`. + // SAFETY: `MAX_INLINE_LEN < nbits` and `nbits <=3D MAX_LEN`. let ptr =3D unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_r= aw()) }; let ptr =3D NonNull::new(ptr).ok_or(AllocError)?; // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` chec= ked. @@ -495,9 +499,10 @@ mod tests { #[test] fn bitmap_borrow() { let fake_bitmap: [usize; 2] =3D [0, 0]; + let fake_bitmap_len =3D 2 * usize::BITS as usize; // SAFETY: `fake_c_bitmap` is an array of expected length. - let b =3D unsafe { Bitmap::from_raw(fake_bitmap.as_ptr(), 2 * BITS= _PER_LONG) }; - assert_eq!(2 * BITS_PER_LONG, b.len()); + let b =3D unsafe { Bitmap::from_raw(fake_bitmap.as_ptr(), fake_bit= map_len) }; + assert_eq!(fake_bitmap_len, b.len()); assert_eq!(None, b.next_bit(0)); } =20 diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index a41a3404213ca92d53b14c80101afff6ac8c416e..8f68b45a3da1f62dd0d01048083= 7de49b9a343ba 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -7,8 +7,6 @@ use crate::alloc::{AllocError, Flags}; use crate::bitmap::BitmapVec; =20 -const BITS_PER_LONG: usize =3D bindings::BITS_PER_LONG as usize; - /// Represents a dynamic ID pool backed by a [`BitmapVec`]. /// /// Clients acquire and release IDs from unset bits in a bitmap. @@ -97,13 +95,12 @@ pub fn realloc(&self, flags: Flags) -> Result { impl IdPool { /// Constructs a new [`IdPool`]. /// - /// A capacity below [`BITS_PER_LONG`] is adjusted to - /// [`BITS_PER_LONG`]. + /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LE= N`]. /// - /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h + /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN #[inline] pub fn new(num_ids: usize, flags: Flags) -> Result { - let num_ids =3D core::cmp::max(num_ids, BITS_PER_LONG); + let num_ids =3D usize::max(num_ids, BitmapVec::MAX_INLINE_LEN); let map =3D BitmapVec::new(num_ids, flags)?; Ok(Self { map }) } @@ -116,9 +113,9 @@ pub fn capacity(&self) -> usize { =20 /// Returns a [`ReallocRequest`] if the [`IdPool`] can be shrunk, [`No= ne`] otherwise. /// - /// The capacity of an [`IdPool`] cannot be shrunk below [`BITS_PER_LO= NG`]. + /// The capacity of an [`IdPool`] cannot be shrunk below [`MAX_INLINE_= LEN`]. /// - /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h + /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN /// /// # Examples /// @@ -130,14 +127,14 @@ pub fn capacity(&self) -> usize { /// let alloc_request =3D pool.shrink_request().ok_or(AllocError)?; /// let resizer =3D alloc_request.realloc(GFP_KERNEL)?; /// pool.shrink(resizer); - /// assert_eq!(pool.capacity(), kernel::bindings::BITS_PER_LONG as usi= ze); + /// assert_eq!(pool.capacity(), kernel::BitmapVec::MAX_INLINE_LEN); /// # Ok::<(), AllocError>(()) /// ``` #[inline] pub fn shrink_request(&self) -> Option { let cap =3D self.capacity(); - // Shrinking below [`BITS_PER_LONG`] is never possible. - if cap <=3D BITS_PER_LONG { + // Shrinking below `MAX_INLINE_LEN` is never possible. + if cap <=3D BitmapVec::MAX_INLINE_LEN { return None; } // Determine if the bitmap can shrink based on the position of @@ -146,13 +143,13 @@ pub fn shrink_request(&self) -> Option { // bitmap should shrink to half its current size. let Some(bit) =3D self.map.last_bit() else { return Some(ReallocRequest { - num_ids: BITS_PER_LONG, + num_ids: BitmapVec::MAX_INLINE_LEN, }); }; if bit >=3D (cap / 4) { return None; } - let num_ids =3D usize::max(BITS_PER_LONG, cap / 2); + let num_ids =3D usize::max(BitmapVec::MAX_INLINE_LEN, cap / 2); Some(ReallocRequest { num_ids }) } =20 @@ -177,11 +174,13 @@ pub fn shrink(&mut self, mut resizer: PoolResizer) { =20 /// Returns a [`ReallocRequest`] for growing this [`IdPool`], if possi= ble. /// - /// The capacity of an [`IdPool`] cannot be grown above [`i32::MAX`]. + /// The capacity of an [`IdPool`] cannot be grown above [`MAX_LEN`]. + /// + /// [`MAX_LEN`]: BitmapVec::MAX_LEN #[inline] pub fn grow_request(&self) -> Option { let num_ids =3D self.capacity() * 2; - if num_ids > i32::MAX.try_into().unwrap() { + if num_ids > BitmapVec::MAX_LEN { return None; } Some(ReallocRequest { num_ids }) --=20 2.51.2.1041.gc1ab5b90ca-goog From nobody Sun Feb 8 07:07:42 2026 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2928A31326C for ; Wed, 12 Nov 2025 12:47:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951653; cv=none; b=oxN+m7/yOLvZNThxA0JMpNr7UE+PAcfaYDTDp8/3JV2HKXFt5kfYklVrkAGD+4Je0PTtSEV8top5IumZbKScJ5SdbT3wCwKgHoSg2BTiqK+WXd4XcRNgNXuHSWbFdueQsjel6zgwRzJo/5TClpEsUECVjyBkWLFG9WIXZBpd0x0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951653; c=relaxed/simple; bh=jU12ZpgtH991h5e7ZBwBatZK4g5q1U/xD8yC7I7uHME=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=qXVCdD/TroQj9WZYZKDeJfI4ExGFoyc+p/oGsJwMQuESXQ/x44hlM3uMovbpL9B/vkPhxuCOFVRT3ZKd+oSSFpZQOl02kwrhVGZaKPaYaeJWgD3R41zeKJatElcplE1J8PbYTShWOCqT0GAO5IkZFf90Pvc3BPijN9hdxBHIi84= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=lgTP+NTr; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="lgTP+NTr" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-47775585257so7067715e9.1 for ; Wed, 12 Nov 2025 04:47:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1762951650; x=1763556450; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=FAyL6DXdlWMMZNXZ5ef4zX5oC6lp6MOoZedmRmCWqCk=; b=lgTP+NTr/M8Gm48Yj8XGLAlp4oF/HO5/6RgojVAbh0MclKXN8XHna3ugrq01wJt+c8 g5Jt3JnuK757V9rJcbGpAKup+19Fnfbk4DWyJiqW48r17Nyvj5ku8ZbEsW8242dc3fHe BV3Wi98AZVhzmdjsFUDhJyMA5k4JckbCUo8UveMFl+2YmNjJoQM7epzzWhzGM4lXRHm4 xRdyxIVQBVxGNlXMpqLezvFxvcq1tuPvg2bhJWwHv1WkWHhlP/BWm/D1h2BvsPY30v8b +1L/q0jRNGQJQjvmwx8AYnYAgH7xuhNuVoCQgmDMj1V5Q9WUER0hQbeuu8JD4MHoBHm0 U67Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762951650; x=1763556450; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=FAyL6DXdlWMMZNXZ5ef4zX5oC6lp6MOoZedmRmCWqCk=; b=TYpz+3DmO8UO3MYb6v3dw4llz6+wOxGX+KDYYtDH5fsUUo80RbjlyLyAkHDZlYSVFh z8H28tynI99dpxCKdz6ucyJSB7WBicgaCOoKNOKU0+xa444KjdbqrsQdX8mDg8N4kRRb 5a5oSGX+PXc9l/CTiaLnhvcKW33CJwHDHShXQpMTvcDfZzVTEj6q/04Kk88izDl4iCmV 69Dx6HRxKgY1yY0QYKL1ww1sRj2tlsfJvIMoIAoYYhdpSHXgD/bxXCc9cgU7R/jfzvd4 8UXxfcJVOYBl9vAhsTwK3azekM5jvuVSAmbwWmpyWF9Qskoa2ZJe77s2JW1raATfMTQj 3a/Q== X-Forwarded-Encrypted: i=1; AJvYcCW6mn26HZOeLJ4Q0kgPVJKdUDamxzLiGTURZ5WUwFxsxtdi4zhvJD2qvgoBx9rhWaTEbCRlyD9q94Swbg0=@vger.kernel.org X-Gm-Message-State: AOJu0Yzf8bzakYywwoaB4Uj5RZh2BNvMoXZUQ3txQqLVPM+WFLAoO4vx Jg7IzQ2IyhkiL3JeV96f5XM1lXPgdSTp2vvS5/OND9d37mHTadUvOiWP2qUDobWwxHDlNI41Qyw UMcsdBWTegxp4qNWwEA== X-Google-Smtp-Source: AGHT+IFI26OUAU30HxN4N5ESdqUbkEvk5F+6vXXL6DPLRxYyP/If0dVPFSht9YaKcqDMKtTuRH20LVUf6M5dr2I= X-Received: from wmbbd13.prod.google.com ([2002:a05:600c:1f0d:b0:477:63a3:2748]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:1d0a:b0:46e:32f7:98fc with SMTP id 5b1f17b1804b1-477870962bemr26756645e9.21.1762951650641; Wed, 12 Nov 2025 04:47:30 -0800 (PST) Date: Wed, 12 Nov 2025 12:47:20 +0000 In-Reply-To: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1308; i=aliceryhl@google.com; h=from:subject:message-id; bh=jU12ZpgtH991h5e7ZBwBatZK4g5q1U/xD8yC7I7uHME=; b=kA0DAAoBBFi+7ljGOUYByyZiAGkUgd7IN5ZSHLCDpzD9Me3XDUof+vZJ+MpQbPfrpbDnUcnSn IkCMwQAAQoAHRYhBIOSopRNZAcK8Ui9sgRYvu5YxjlGBQJpFIHeAAoJEARYvu5YxjlG66kQALG6 l36BdIAxhSaLv06Oh8rVycDqelTzLAe/S4UyL1ibV4SbA2OwlkMe1W/qXjTWofTFjUE+G0d0We+ mBmiFe5ANObGJoqifL+V/FCeZeyOeGzrL0toiPTwkJ4ORfsfxDy55Ej4QdjqHCb3qrjpHuBgXO7 pRPNtoy+DH7Lk0ATI4MBx8tYnWPt+WtljVLTPTWkJw0KSn1Q34JSD6klKWRNWseBj5IIvR0Rnxz Dmv7Ij6knxHf81G0HLeK1CdLar8KUiDVSateJ4BlG7DG86XU6+lgx3yVqlck1XUqg7wtr2O9XV1 Ysi1YB/Y6wwe1nHzlhM4afN26AumEWw1iiT3njn5ZSme+lP3pi+48cl3vixgPwv0+aofx0yk1ON 4WbDuhL7bxF8pDc6/5Ckb+/T5smMsG/YQmaci46CjIruPXLU5ko+RheAsb1WaKBqhExIZF5+ZYb ODExzuaiMAqeT7nNrnFGhvWiVLolpxyb4SLJjeJED0AWsWJAJDpmFlXFw1+a8liVZ0fiDCihCqo lbdpxmbpSTy5OBenoTAD8Pl7jLe4rs7cNMFkCwBbwg4wguJv+3hDSFNkhH7wvRpEzvxu3kmhEBL LiIrQVH8CxKOFQ2l8dEPV0zTWWNUxvw46PsnL37KhDG5px+2+lhodpg5CbF9s1oURhYI+Y3W854 hp7x9 X-Mailer: b4 0.14.2 Message-ID: <20251112-binder-bitmap-v5-2-8b9d7c7eca82@google.com> Subject: [PATCH v5 2/6] rust: bitmap: add BitmapVec::new_inline() From: Alice Ryhl To: Greg Kroah-Hartman , Yury Norov Cc: "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Burak Emir , Miguel Ojeda , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable This constructor is useful when you just want to create a BitmapVec without allocating but don't care how large it is. Acked-by: Yury Norov (NVIDIA) Reviewed-by: Burak Emir Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl --- rust/kernel/bitmap.rs | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index 0705646c6251a49f213a45f1f013cb9eb2ed81de..bbbf0f9e5d9251953584581af57= 042143447b996 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -230,6 +230,16 @@ impl BitmapVec { /// The maximum length that uses the inline representation. pub const MAX_INLINE_LEN: usize =3D usize::BITS as usize; =20 + /// Construct a longest possible inline [`BitmapVec`]. + #[inline] + pub fn new_inline() -> Self { + // INVARIANT: `nbits <=3D NO_ALLOC_MAX_LEN`, so an inline bitmap i= s the right repr. + BitmapVec { + repr: BitmapRepr { bitmap: 0 }, + nbits: BitmapVec::NO_ALLOC_MAX_LEN, + } + } + /// Constructs a new [`BitmapVec`]. /// /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allo= cated. This --=20 2.51.2.1041.gc1ab5b90ca-goog From nobody Sun Feb 8 07:07:42 2026 Received: from mail-ed1-f73.google.com (mail-ed1-f73.google.com [209.85.208.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 892CD336ECC for ; Wed, 12 Nov 2025 12:47:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951655; cv=none; b=H4AUIXG7fodtFX6/FE06ggl7WQApfN2nAxqGF9zIQJH1t+6dBFvHQ2JCiMIpg+fnG2BhXT1PCr/OvnV2ISQFOs+eV3LFObzkuZ4zs0eb407N3jXq0Xs/DL4afTP7J1iCr0/ZUot9zsjnXy5JZQv+7OZ39DHwKcZ6gBaRyU/5I5g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951655; c=relaxed/simple; bh=hKaPMy9+GEI/b3Oq8xi/5gaYtlyCO77NYnlh7ZIaMpw=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=OeW00m7OzvWzdPAfdRxD+QtDVMl0bTtqSlm1/jtw4L2RqsKqABhEXCexo21/yBmllewbmjNiRQEV5h/uId5LMTsut6eVd+tZ6xX1hwMbzDVZ3Mmu6OqPv9AMbr1YYbHYPSEibsLUFLbiPOrIrT45JZXdAt1ChAjJeyVTBMxSKw4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=Lr/4Yxiq; arc=none smtp.client-ip=209.85.208.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="Lr/4Yxiq" Received: by mail-ed1-f73.google.com with SMTP id 4fb4d7f45d1cf-640cc916e65so1206988a12.1 for ; Wed, 12 Nov 2025 04:47:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1762951652; x=1763556452; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=q4UBJCHM5aA25nWu21zr/8ZKj4a6mo6pSN1iH3EBauU=; b=Lr/4YxiqJFOgOamqPnrFeA4bOq1yzl5XAt16+O36lD8g7kzKHzgkkisU1BGRmlbtec ybBI2L5DgMXuLR4Cmz4ZKZx19D99uMNXyhD/fWrngK4R4gKU0ReZD/IQmgKYzyYD6q2S K3hGgERNMycTu/FGSAzmq6Lg6N9jZ2fOI8oFjy9HKOf8TuWsemtqX+0CDjYuvayEVzLC nr+w8JGu0uc4igr7Rw2MHrrg+A3zLEKdOradZTf2mvU3WD/kxQ+7qtSfSzNUhOgg+53n ZWv1BTY8AMSN0gCsud+sX/MHFQ7YTht0mxuZ0P7W8YMQ35vrPvDW0qicLJr0BvXAsLJ6 HbzA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762951652; x=1763556452; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=q4UBJCHM5aA25nWu21zr/8ZKj4a6mo6pSN1iH3EBauU=; b=gSJFIQTVAKd437IOw8EZVDqW6tXuW0/27MRI2hlCd5GgPEv5o1vqfQe87o5kQbFVra +IVHDsaOplQIYELkYwi5oqG0apwWfcjrXXqcou8JR/FyIsYxgf27YSAmGjLZTpsX1Q8i Dn+WaYd9O9EfTNrTYQb6uDFGB5+KSAgeBg7lc8wEAO93082f36JnKCZMB3xoBPhAVA2U KcN1Xdsc7K1qgCn1nPKQOHJU/gr9GXSHWOHUKp/DCHrWj/tF3eFHML1XzA+68RANDjDo 4XmaJhPYs6HQK9XOV4d5O+Q9HXRFwGZe8gEFDxdk68M30ae8KMoa4upZnqQOi4ZDp7MH HKFw== X-Forwarded-Encrypted: i=1; AJvYcCW35m6251FTrSEXSQY7XUpW5OutYs9xCYKlQLZ8FwJXiJcf6ZFF2rirptj/8RdI8eVcght2sYcEgTkfeVQ=@vger.kernel.org X-Gm-Message-State: AOJu0YzqWH5mtS+ztJlZI/SoInEB99HQvVOu+cpAS4oUAsiR0r3FNhQy iM4ylk3LrtDSvAnBlEndGAxdFUNRagB+04oPZRug152A13A48nFCNbX82jrUAE1wNEjF0/yjyim Exf9ePLmzB8cyP9eafg== X-Google-Smtp-Source: AGHT+IHxrwjiNI/+r47De2XruyMMvKVXWthxfhc+G7EBXTftcxSNxu1BR123UupilsNII15IfXeoMMP7ssWXVIo= X-Received: from edi12.prod.google.com ([2002:a05:6402:304c:b0:641:92ae:b59b]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6402:254c:b0:640:948e:7da4 with SMTP id 4fb4d7f45d1cf-6431a561bb6mr2237679a12.29.1762951651735; Wed, 12 Nov 2025 04:47:31 -0800 (PST) Date: Wed, 12 Nov 2025 12:47:21 +0000 In-Reply-To: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=2409; i=aliceryhl@google.com; h=from:subject:message-id; bh=hKaPMy9+GEI/b3Oq8xi/5gaYtlyCO77NYnlh7ZIaMpw=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpFIHeFXZ2PL2RerOIjW5w3K+2z5Ixlz4dZRF5f v1uZDU8i6iJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaRSB3gAKCRAEWL7uWMY5 RirOD/0U3Rlj9i0S+NJHFFYvnCIpbHdOCpzHotQsXuGX+YxJX7s8lVY4rxGJ5VbIFENTfyG96S4 SDSHoVT9Z34zf/ehrodn0xU4HTkFMwQoXG66Xml+9432Re/2sRXFO75N2lcSWJpoBnfOPhSpseV vvTLwzWEL2TGM86usmVGaKKsdmyTOXZIUz1w3qwXlMdh6rnPxi+Zb24dazPNaz0jL1+a7t84q7Y vj0fzZ9p7GFQOsbvgnvIFnBvthnd8qEWqffJl16wMQHDdq7/keeI/lUZcolitLo+SEZjMf62VXo oZZr7P89hSX3RCQpKHXofnYbrpDqAkIX1JXJVETLTLuuoKhzqLkmDLuuMmuFMkAQ8VqblvGK379 8EZQo06tt6WvU5Q9IcU3wXJz+komB/IoLow2A/20tPERkQ1H6mOXuhxwjyeVFCcnrPYJaZMvfpU RXxv62dZ0xg+uEJKnOc/5eM6Iuk+pynJvtlFGU6d7tudJNLlHJ2mos1TaL+c7uZgX4jgkD/OVMX uuLqEHjfMa6MVi8A79lPgA+y8wQD7TiO5Cdz8R0wpxJZe6vLlrB32PBwFzqL8oyFM7oJV4W61r4 fnV7izyl4zvfcRfZyl+D+N39EtClHoJvK0B6p6kA6bkLzrMBmJZgkl9JCQ2rGGBfJS/OeXydvKx o4ZljuhUUwZ1L1g== X-Mailer: b4 0.14.2 Message-ID: <20251112-binder-bitmap-v5-3-8b9d7c7eca82@google.com> Subject: [PATCH v5 3/6] rust: bitmap: rename IdPool::new() to with_capacity() From: Alice Ryhl To: Greg Kroah-Hartman , Yury Norov Cc: "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Burak Emir , Miguel Ojeda , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable We want to change ::new() to take no parameters and produce a pool that is as large as possible while also being inline because that is the constructor that Rust Binder actually needs. However, to avoid complications in examples, we still need the current constructor. So rename it to with_capacity(), which is the idiomatic Rust name for this kind constructor. Reviewed-by: Burak Emir Signed-off-by: Alice Ryhl --- rust/kernel/id_pool.rs | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index 8f68b45a3da1f62dd0d010480837de49b9a343ba..90836b05c6155f98ab8393c8291= 749f408dbd4da 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -26,7 +26,7 @@ /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; /// use kernel::id_pool::IdPool; /// -/// let mut pool =3D IdPool::new(64, GFP_KERNEL)?; +/// let mut pool =3D IdPool::with_capacity(64, GFP_KERNEL)?; /// for i in 0..64 { /// assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?); /// } @@ -93,14 +93,14 @@ pub fn realloc(&self, flags: Flags) -> Result { } =20 impl IdPool { - /// Constructs a new [`IdPool`]. + /// Constructs a new [`IdPool`] with space for a specific number of bi= ts. /// /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LE= N`]. /// /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN #[inline] - pub fn new(num_ids: usize, flags: Flags) -> Result { - let num_ids =3D usize::max(num_ids, BitmapVec::MAX_INLINE_LEN); + pub fn with_capacity(num_ids: usize, flags: Flags) -> Result { + let num_ids =3D usize::max(num_ids, BITS_PER_LONG); let map =3D BitmapVec::new(num_ids, flags)?; Ok(Self { map }) } @@ -123,7 +123,7 @@ pub fn capacity(&self) -> usize { /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; /// use kernel::id_pool::{ReallocRequest, IdPool}; /// - /// let mut pool =3D IdPool::new(1024, GFP_KERNEL)?; + /// let mut pool =3D IdPool::with_capacity(1024, GFP_KERNEL)?; /// let alloc_request =3D pool.shrink_request().ok_or(AllocError)?; /// let resizer =3D alloc_request.realloc(GFP_KERNEL)?; /// pool.shrink(resizer); --=20 2.51.2.1041.gc1ab5b90ca-goog From nobody Sun Feb 8 07:07:42 2026 Received: from mail-ed1-f74.google.com (mail-ed1-f74.google.com [209.85.208.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CFBBC334C1B for ; Wed, 12 Nov 2025 12:47:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951656; cv=none; b=ap5NOpGx+l+UnKSv3/8YJc+Q9+AFFnwC9LDbRgxX6FE2X6WTj+xqJD1OaWNL6Z/X/Ww76xjeCnC3AQN7GYjV2EPal0Ebwb+hVHiu2eBiDsq324CA001EieLNxsrU5DLT2r0zUdk4LqZ9lG2zVYgbg7gUogK6mjTLIUJFfiTwX38= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951656; c=relaxed/simple; bh=Us/zLvFyE9k9qHI3mL8Iz47DL6Q8odLnYIznsT0OSFA=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=cVwRKI80IUCk1Clj6qvvB5oTrUoo3Ex643xFEt5ZYhHD/i505oZnncRvNfD7TZKAEmGlXshVG8JxhnmPdN40iXPwkhuTABv1ZH8U5YxOSe1ucLW6IYvYhkGW5OaEz4VUC0FK2bxrsgwAJBrg0IGICEk9b7dyAsuxay6/yylFmqM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=ZiEUORbE; arc=none smtp.client-ip=209.85.208.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="ZiEUORbE" Received: by mail-ed1-f74.google.com with SMTP id 4fb4d7f45d1cf-6417a4b67f9so728244a12.3 for ; Wed, 12 Nov 2025 04:47:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1762951653; x=1763556453; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=3f3ldoO9R08QIpB/BHNyvJNE4LJaL87gT6nQsr/65nY=; b=ZiEUORbEAuMUeogWj2YlqN4aVNJ7lY8zBGMCV3AsOe4VThZDLZYt7IcVtqgsQI0hy3 nolHH3kZDziSlCxzX3PdhBUkE9YzbQJy/q7VN9J35qk9NHKefOz2MtavoCjVNcdPhXgf zoG39fCo/YDV3CFlvufcmenXvl89djj57nGjNOeMTO+VPSsRrhAcDyAAOsfNc2S7YiM9 /uCsiT5PS7cjRFAfhzbKVpfZttsP5ylkQ06yL/r8p+8AT3IhoR2WNEycdkEbzkHroBu2 NoSgxwUWpD48eZ3qJW11Y5Vb09+j5iVhaAQl3ZKE9yqUz05du4yaDOt2GHuNvTlf+ME6 I13w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762951653; x=1763556453; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=3f3ldoO9R08QIpB/BHNyvJNE4LJaL87gT6nQsr/65nY=; b=F0NQ9UQHrXo/AxV5ALjmhJozx1jQMxnJOLntAffJFlFvWeZQ3xTRBbE4wBGR0SWodT ctroMMJKhczVGBO2rDSYj/1D5nE4/bc9mTSLNOwFPG0yvUTMnaZa+8kNV6F7BU3arr1e wWQ7vclqa+D5G4kmgyY6xtgbbQrFzY5eGSW2OPmDu2RlBt+lDrOooJ0lwWLRkT8vv+FJ e0KSxXyzHm1Ofx+cp6pJmi5VF6E2/3EjWFWee1Vmoq8t0BU1FfLAZw2YMk2ozVHHYsUJ 0znmFa9XpIzBNV2sGhwOSxAthXSTXkT/Bdr1yvWm7GjzAByxgUe+8q7NTB37eaj8iMCx 3ppA== X-Forwarded-Encrypted: i=1; AJvYcCXO386Nr2ooLbK8FSEVO4pofERMZLPj/F67HG65LDTU2f2f7FA8uLxeimWfMs4/PS3g9eu2ATSXaHQOowo=@vger.kernel.org X-Gm-Message-State: AOJu0YyqILyvIZ1QtDiJbX6HZisETQw0/R+jFvhcVzHcrjpJomp2J06M dMv3eDbPBWGF7wiWThL3X3yVsu6PrE8pWaot/+z+T/k+sNCnv0sOdr/XwwXSzCpiKqXr/F9wuQU lnO9/+rfdXfwHrV3K4w== X-Google-Smtp-Source: AGHT+IH29rIcpbeIT3goMzCDhfweeIVyGKOaeO+HjU4VdSeG5f8TlrA77kWhpxkYNjptpYv78x0JsOJF84UEb6c= X-Received: from edaa9.prod.google.com ([2002:a05:6402:24c9:b0:643:add:e1c0]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6402:2682:b0:640:a03a:af98 with SMTP id 4fb4d7f45d1cf-6431a52ffc6mr2420889a12.18.1762951653173; Wed, 12 Nov 2025 04:47:33 -0800 (PST) Date: Wed, 12 Nov 2025 12:47:22 +0000 In-Reply-To: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1713; i=aliceryhl@google.com; h=from:subject:message-id; bh=Us/zLvFyE9k9qHI3mL8Iz47DL6Q8odLnYIznsT0OSFA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpFIHfc7CzR4SxgRNX8ioWyORnLUfzvrYfKI4v+ cRiUWGPoQOJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaRSB3wAKCRAEWL7uWMY5 RowRD/0aRa47W4TvjdH1/jgUrSCq7q2C0cUfnbeyWGUCsg82SeCDLmnnpAzTKBivWMOVYS4qii3 8FO9TGsBIh1Rzq6YK7SVZHez3NC/lVGY9rTn4WB/VKe8CUjhBSWIEzOvBoerWvneoEH3E/gPUFZ cLrAFl/lL/Dq8MwgwRFuKHPI64cwzkKuE3DgsG6k/4lDDECobNO+kcAQ0x8O6XrZXURd2yDvRIZ IOdfikmSE57eQYZsmqrC5yeP3vYPTIYlMSiB2N68Rd69W/J7BvgDmxP7q9bfxy6qv75ZvqthlMH 9LnVxNgyhj/X0kxbweAnLUg9tU0glvYRFv/cl6xJia7GlJ5S2Efk/ThQQ9L04HHzxeM/XBE4wl1 tdnIZ+Yb84KP8+/IqSWSV4kLC7+Q7i6roEjQlRkSxdWjCj+tgIqKKm2XsHgEyhXbii/txvV2AdI AFUVr4u3o5WnyYBBfTfCQq4cwQ+onY0UKjiHHu8uGoK2k46o+IaW1GjgIwCYV8dyJ2hfML9nEyw VVwgp5GMeSShzwusxIIcprO6NuJ9u+DJfKVTAf6G3rnlDxHDKRL7yQAeOBwfw/F7biQmDy4Tg/R HajzGoMwM+HDFl4l9Xj9bc/eYVcusshKUBwZb1p4G7doYj1uOhhytizCwYKANhD2CgRYAI+hLyx GPjWvySP41qQiiA== X-Mailer: b4 0.14.2 Message-ID: <20251112-binder-bitmap-v5-4-8b9d7c7eca82@google.com> Subject: [PATCH v5 4/6] rust: id_pool: do not supply starting capacity From: Alice Ryhl To: Greg Kroah-Hartman , Yury Norov Cc: "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Burak Emir , Miguel Ojeda , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Rust Binder wants to use inline bitmaps whenever possible to avoid allocations, so introduce a constructor for an IdPool with arbitrary capacity that stores the bitmap inline. The existing constructor could be renamed to with_capacity() to match constructors for other similar types, but it is removed as there is currently no user for it. Acked-by: Yury Norov (NVIDIA) Reviewed-by: Burak Emir Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl --- rust/kernel/id_pool.rs | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index 90836b05c6155f98ab8393c8291749f408dbd4da..dc856fc68f4cf38971332f15e63= 440f27868a3b6 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -93,6 +93,18 @@ pub fn realloc(&self, flags: Flags) -> Result { } =20 impl IdPool { + /// Constructs a new [`IdPool`]. + /// + /// The pool will have a capacity of [`NO_ALLOC_MAX_LEN`]. + /// + /// [`NO_ALLOC_MAX_LEN`]: BitmapVec::NO_ALLOC_MAX_LEN + #[inline] + pub fn new() -> Self { + Self { + map: BitmapVec::new_inline(), + } + } + /// Constructs a new [`IdPool`] with space for a specific number of bi= ts. /// /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LE= N`]. @@ -223,3 +235,10 @@ pub fn release_id(&mut self, id: usize) { self.map.clear_bit(id); } } + +impl Default for IdPool { + #[inline] + fn default() -> Self { + Self::new() + } +} --=20 2.51.2.1041.gc1ab5b90ca-goog From nobody Sun Feb 8 07:07:42 2026 Received: from mail-wr1-f74.google.com (mail-wr1-f74.google.com [209.85.221.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 34A6C3385B8 for ; Wed, 12 Nov 2025 12:47:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951658; cv=none; b=oa5d7jpR5KYHVyyM+clb5Ud6wHFpSsOfQr6INHa22TXZ+kmDi6FJiU7ZesmedBkBBaDNqaeyfPgk8PvwPyv94uk0Ajl267ugelkINC98d//BRSiJLc2hhd+f3n05W2WjsyB0ECtTq1/8jjhDtTAjIqcIos18DZc53/Zu3CVqQ5I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951658; c=relaxed/simple; bh=6MeYm25HociD581vSqYtJ2eptFsvAZ44ncTNn+Udga4=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=GcLdW4Pt4i6yRV0mB91E2rJk9/f+PRWRqK4e5Q2dcIgLiJamRNrE2pncnX+AI1hcZ34X4Jg2aUi8G5WRr8h/EGmqHUpysJXCs2WYBYh0ziBU9LkUpgDyj8BUaIV5ZhZ67cCPEBihrPeT6zbd9Of+P9Ve2f1oPzPzEINMNHksU44= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=hOKp3Js0; arc=none smtp.client-ip=209.85.221.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="hOKp3Js0" Received: by mail-wr1-f74.google.com with SMTP id ffacd0b85a97d-429c5da68e5so474253f8f.1 for ; Wed, 12 Nov 2025 04:47:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1762951654; x=1763556454; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=3QATGzgIOoHBhOcPYuGxb2KGfX2Q3a4/bHnK1FxMmdk=; b=hOKp3Js0djsTm6iPQ9M0p8KRFqp93+fgPHbyZKBYRnqtc4t6Jpn/cLOksgk/FYDCRf bszPhDECozvuH3hfNwQ2JWKzEtqbjDyajMr10IC8fb8gh0I36jLqlbaIjxHkYkvlj06D 81csjewvJul5qwmLBtgAi+yL9oxOEZp0b9oAS30vK0Qx17x+6BUUZbyf71/04xrCxN9a zC4Q4XfEoJEo5VrHY93cdpJx8E7Uw3w7lWrgs866iDiIizljs+BXaxme6ZW5xJgkORv9 UtVvxjwkos3dqQOzmSGTiPYwluWGXw4hFxMm6KMcrUwHsWUUjFBqGnEdc+9ZXzo+u0ou qsZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762951654; x=1763556454; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=3QATGzgIOoHBhOcPYuGxb2KGfX2Q3a4/bHnK1FxMmdk=; b=JaWLalj7Y/9BQzGX6RJgS5lHXLHQpejsKqepv/wMi5plmrdBdUmg19dauOZI2VnlBS PLNU2YDzIGmYlOhctYB/NX29+GfMir9qgFfU2AmlOAW4vbNTMpBcdyVFDwAKxQ2UBkrS LqJdXVO4Z/v16Y5SLUa0FDk22E8+udvs3UZHer5i1yt7Mgx46QaTwne2t1yghGdgprKx zQmq+bGajnrorJv4RyFMW4FhfrBniE6NdrGFyNEKhwAnAmBcPDSYjwa7BKbBR5IdDZq/ DwvHSluveCKIjvgctuT3iFsKbbv7VwJvQG03rBL+NyxMMMbPJuh4gdiu7EuVbCfA+O4I fOrw== X-Forwarded-Encrypted: i=1; AJvYcCWqoi380SPt+F+/DZ7OutPyChZYjYKQLO1tmtVB2A0s+Uj1T3x/zcPuHzmrrCiGR+QRrIjLoXXgei/yD54=@vger.kernel.org X-Gm-Message-State: AOJu0YwsAiBHyL0IBcLvWcOKV744PgiXm5CeBqEJdBlody7AYkYfEfBK DGmyapaipwS8gu1KHoVcUPd+9mNPugstOZM05gz59KGP5ASRgGuPNDGE4Td6psb6HdSAmqFFhq+ VegZcR+vudziY3aKZ3Q== X-Google-Smtp-Source: AGHT+IGwiUuX9VtxNziIMNKFP7L3vhGfq/C2gnxBaVZw9+q+Hgp8MO4PmqGJrM1wwjJ1aM0vSDKzaVr3lt7Es4Y= X-Received: from wrbfr8.prod.google.com ([2002:a05:6000:2a88:b0:429:c639:ae9d]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6000:1862:b0:3e7:428f:d33 with SMTP id ffacd0b85a97d-42b4ba7581cmr3109209f8f.16.1762951654322; Wed, 12 Nov 2025 04:47:34 -0800 (PST) Date: Wed, 12 Nov 2025 12:47:23 +0000 In-Reply-To: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4865; i=aliceryhl@google.com; h=from:subject:message-id; bh=6MeYm25HociD581vSqYtJ2eptFsvAZ44ncTNn+Udga4=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpFIHfLA8vn0C1oY1F+euOlddJEO00TimBmnEge +5HciDEBouJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaRSB3wAKCRAEWL7uWMY5 RnUjD/0c7M1eODfqPcBGXBo+T+rTzLyzomD0QAN+EJQW7ks75vDyr8vXUY0fccukmGf72vM83jX TetEr9WGw8TYvNjBfe6OeE05kpyYNiJT2D2LD54B/NmzJ+C14fLKd9q6PD55KfmfueF9EFDfTRF vf4vbISE4CdjluR84fNh7ec7rfvOFT8UiPgV5dpGgN4eqV/T8bYbQtpiihbqJdhJ5nVgG0kWFHk IwFl9Rll22aMRJiYuXV/oOH+4BPCmcewgXzOS8lJt2F0jGe4EyCn+klDZwVCOvdlh1ikRAcBKST gXVTdtGPNQUe4HVyLMrzutiSqdYyduj3Urii+6+EmLzp8x13zKmavDuNK7TWk6D5if7ykzb9BTu hAiJ5qde1qOOGO2tI97d5fYpnAkdZNAeiWUsqplx2gdBOMxgccpUS1kv/dk4SbJgB0ZCdNUz7Hy YKpdkEAS5/md9jyA+5fcw/XMiVqqv3cMJFGmCPsMxEol7ty11xYstMPwOG3xpxoIqeB5Y8A6qvJ qTNLp/MX9Gaf8bwT3GnuM5OxHcnrrP/4GdUx5tKQgY82+Jx1mRAMVgXbS5WiSFPpPEvRzAvwZev 4Mls9REFDU4/LslOYobd3och2d6/SeTonlxiN1lxNRPyJ1WFiKIkSE7GVx7rkUJVukqU74Hx+Xd oYkefAVkH06Ln4g== X-Mailer: b4 0.14.2 Message-ID: <20251112-binder-bitmap-v5-5-8b9d7c7eca82@google.com> Subject: [PATCH v5 5/6] rust: id_pool: do not immediately acquire new ids From: Alice Ryhl To: Greg Kroah-Hartman , Yury Norov Cc: "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Burak Emir , Miguel Ojeda , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable When Rust Binder assigns a new ID, it performs various fallible operations before it "commits" to actually using the new ID. To support this pattern, change acquire_next_id() so that it does not immediately call set_bit(), but instead returns an object that may be used to call set_bit() later. The UnusedId type holds a exclusive reference to the IdPool, so it's guaranteed that nobody else can call find_unused_id() while the UnusedId object is live. Reviewed-by: Burak Emir Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl --- rust/kernel/id_pool.rs | 75 ++++++++++++++++++++++++++++++++++++++++------= ---- 1 file changed, 60 insertions(+), 15 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index dc856fc68f4cf38971332f15e63440f27868a3b6..114e39176cb48b3806797aba48e= 4d43e0c42e3d2 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -23,8 +23,8 @@ /// Basic usage /// /// ``` -/// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; -/// use kernel::id_pool::IdPool; +/// use kernel::alloc::AllocError; +/// use kernel::id_pool::{IdPool, UnusedId}; /// /// let mut pool =3D IdPool::with_capacity(64, GFP_KERNEL)?; /// for i in 0..64 { @@ -32,13 +32,13 @@ /// } /// /// pool.release_id(23); -/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?); +/// assert_eq!(23, pool.find_unused_id(0).ok_or(ENOSPC)?.acquire()); /// -/// assert_eq!(None, pool.acquire_next_id(0)); // time to realloc. +/// assert!(pool.find_unused_id(0).is_none()); // time to realloc. /// let resizer =3D pool.grow_request().ok_or(ENOSPC)?.realloc(GFP_KERNEL)= ?; /// pool.grow(resizer); /// -/// assert_eq!(pool.acquire_next_id(0), Some(64)); +/// assert_eq!(pool.find_unused_id(0).ok_or(ENOSPC)?.acquire(), 64); /// # Ok::<(), Error>(()) /// ``` /// @@ -52,8 +52,8 @@ /// fn get_id_maybe_realloc(guarded_pool: &SpinLock) -> Result { /// let mut pool =3D guarded_pool.lock(); /// loop { -/// match pool.acquire_next_id(0) { -/// Some(index) =3D> return Ok(index), +/// match pool.find_unused_id(0) { +/// Some(index) =3D> return Ok(index.acquire()), /// None =3D> { /// let alloc_request =3D pool.grow_request(); /// drop(pool); @@ -215,18 +215,18 @@ pub fn grow(&mut self, mut resizer: PoolResizer) { self.map =3D resizer.new; } =20 - /// Acquires a new ID by finding and setting the next zero bit in the - /// bitmap. + /// Finds an unused ID in the bitmap. /// /// Upon success, returns its index. Otherwise, returns [`None`] /// to indicate that a [`Self::grow_request`] is needed. #[inline] - pub fn acquire_next_id(&mut self, offset: usize) -> Option { - let next_zero_bit =3D self.map.next_zero_bit(offset); - if let Some(nr) =3D next_zero_bit { - self.map.set_bit(nr); - } - next_zero_bit + #[must_use] + pub fn find_unused_id(&mut self, offset: usize) -> Option= > { + // INVARIANT: `next_zero_bit()` returns None or an integer less th= an `map.len()` + Some(UnusedId { + id: self.map.next_zero_bit(offset)?, + pool: self, + }) } =20 /// Releases an ID. @@ -236,6 +236,51 @@ pub fn release_id(&mut self, id: usize) { } } =20 +/// Represents an unused id in an [`IdPool`]. +/// +/// # Invariants +/// +/// The value of `id` is less than `pool.map.len()`. +pub struct UnusedId<'pool> { + id: usize, + pool: &'pool mut IdPool, +} + +impl<'pool> UnusedId<'pool> { + /// Get the unused id as an usize. + /// + /// Be aware that the id has not yet been acquired in the pool. The + /// [`acquire`] method must be called to prevent others from taking th= e id. + /// + /// [`acquire`]: UnusedId::acquire() + #[inline] + #[must_use] + pub fn as_usize(&self) -> usize { + self.id + } + + /// Get the unused id as an u32. + /// + /// Be aware that the id has not yet been acquired in the pool. The + /// [`acquire`] method must be called to prevent others from taking th= e id. + /// + /// [`acquire`]: UnusedId::acquire() + #[inline] + #[must_use] + pub fn as_u32(&self) -> u32 { + // CAST: By the type invariants: + // `self.id < pool.map.len() <=3D BitmapVec::MAX_LEN =3D i32::MAX`. + self.id as u32 + } + + /// Acquire the unused id. + #[inline] + pub fn acquire(self) -> usize { + self.pool.map.set_bit(self.id); + self.id + } +} + impl Default for IdPool { #[inline] fn default() -> Self { --=20 2.51.2.1041.gc1ab5b90ca-goog From nobody Sun Feb 8 07:07:42 2026 Received: from mail-ed1-f73.google.com (mail-ed1-f73.google.com [209.85.208.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2109A338F23 for ; Wed, 12 Nov 2025 12:47:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951659; cv=none; b=GQdLO8k4XGZR7zD9O2ZTS+kY02GIFoNpV3B5pKMpNll+1l/kxiFYgNMRTMOGCXvKd0PCJaxzYMY/qyex0k/Z970LbF9PrKIrm300+noeiyqSFYJ7LeJCdXEE6GxEBTYHSI3SZIYs2mYSi0AEnEYeK8w9pVn6mKadRXcVJ5k7xOQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1762951659; c=relaxed/simple; bh=7993m8OvBem5aU3JmUxqvYCw1dEJgILWjzrL2R/Lw9k=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=HNnUFbYSltIyEl/NzTAdJ+8ZBJtoBeRKAAbLE/YhabVZiHPtUGO+iIWYW/PAlCJOxESPf4v9n1X37M6nijxH9PB1dA1YrBiS05yyoQXxwbpFV0TMOJZ8YOmDwrUa/N2gNqmxGr44MHjUAEhWtYsQl5/eUBBTDgoUoMEXSY0ep7U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=EiYc/p/B; arc=none smtp.client-ip=209.85.208.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="EiYc/p/B" Received: by mail-ed1-f73.google.com with SMTP id 4fb4d7f45d1cf-64161017e34so934633a12.1 for ; Wed, 12 Nov 2025 04:47:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1762951655; x=1763556455; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=tSGXuP7AugTGZlYmteSMimkU/xIm9yUQuBQEE4/o9H4=; b=EiYc/p/Bebh2mGSss8X+0tmIkj9sofnkpCThpDG+Bb1+wi0EwnDR9Pd7Ri8y1cl5mN RzA6EoiHLIKKKc3DdFh/Gf7iYspThRkiTCV6Zq5VJsnEaJpF03OWTtBm5KovX64TF0uq CVEkuZ0IZJplsgkvoyzYaH+ZMzz7fKW3lDDEq/1q7tOMUCct58B8GRmQFfoT3WhkNrnU 9ASvzS321Sq0jCqsH2Ggql2dJDmB+KwOP3OqzqLZPS7nvOBz7QZDGwTiZNkFlhYtCo7W O2TxqRrtX+gW3Xyl+PcNMXjR1+TIB3aTka+F8ELVl3oSMhNj8YzQbXYc6QN9msdxtA5D lasw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1762951655; x=1763556455; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=tSGXuP7AugTGZlYmteSMimkU/xIm9yUQuBQEE4/o9H4=; b=Y72thAFxKkiqgh4PH2edFupSPMH0QUI2AYKqJw61+GlreJUe7CD1klgyFS/i5V4ZE4 0phRK+O7MxwQAvp5jn7ojact9Lo8Z+OoOF3gSbgBGJuE69uRHBuNE5Dqo3wd99QBWs1l QNxBaoiptRbpcHT0zlHVQKjMl1x5aB8aTq5U1yN7Jt7KZcfwQ3/FYqvc7XDSUo2k2mSA qIDDUp+O9406NfqCDp55DkEfwonkURo7OEsL8TZxJRjhTNERitXmuFj0LQzoQTxVuRy3 9d54JDZamLBsoyd8owQcCPx8pWqA7CAm5pXR2geKdKwrugx3GeabQOLYF6l3U+acu3pU RGYA== X-Forwarded-Encrypted: i=1; AJvYcCXtcTf4O2A5nw9BjWKhNrXGWzXpAxw1JySW3kbMzWuBWFURuTtDogGcsRyZZph3rAFGw1W3oZWLUOPzT3I=@vger.kernel.org X-Gm-Message-State: AOJu0YxnApWTJtXoflaM6i8Bik7IZQBIsGHp7TRqh3MuDI/m0UjlZYmk v8XEH+d2wG8hX8G41UoOwwRHnnjqU6FZFV66K+9Xxbae5VsbC3w26k7fwG8BFdjPK8M272hyRQi HjDtWovFbISamdliGiA== X-Google-Smtp-Source: AGHT+IEy759MKaPGI2654Ynt2AeYqR1Q+U51y6PIqyWtN/FW0QjSbKYn/cnewpGhFjEZmbceiGWFu/CxCbtY/Z0= X-Received: from edaa13.prod.google.com ([2002:a05:6402:24cd:b0:641:4e96:ca96]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6402:2111:b0:640:976f:13b0 with SMTP id 4fb4d7f45d1cf-6431a4b3b46mr2630907a12.12.1762951655524; Wed, 12 Nov 2025 04:47:35 -0800 (PST) Date: Wed, 12 Nov 2025 12:47:24 +0000 In-Reply-To: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=6263; i=aliceryhl@google.com; h=from:subject:message-id; bh=7993m8OvBem5aU3JmUxqvYCw1dEJgILWjzrL2R/Lw9k=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpFIHfP1ioXJwPrlND7Tla2uYLkuZFJQ0Av10lr s39fKs/uZSJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaRSB3wAKCRAEWL7uWMY5 RjlMD/wLULd/jxmYFkhyWU/z7yy/xQKcsW9l0KKM+P1I5MAogFkXt80QhZx3cUaUmfFoWoqUYRR wmLZxfRhnB6XtwDDmajbQkjWLA+557FhkRakTyMVpK2YDhzamoLBGnFWbPqDUCvvD5onHSWA08w YTkGjQa810BzXKe5A0dfzqrSfKuQOVD44/8TTVyNF7Fny8yyD/A5UvbNzV6eDcNBEpfCMgku8Qj E1dpRX3EVpL3sL2b5YkrDcWw2T9mXeVp7WKJtPaTaEYoHGOZz0h8LkD+Er/bCNgWU9JOaukr8xG WH7s/sn12VDXJylHnYEKCL4gQtBgnOzI4KOA3KUR/Z/G9zFSY/rgj1WJZab2UdSeTO/q6yQh3gG nukVS3TX5S5RR/6mi0xRP9PQpB7sdYcORbBpK980w6BIaQJTOsfXXwGf3jJrf6ppaiChcUm2vau cLC/P9Ivp1Cl8OSWNp0loDKyLQrPkIDE7mhjfu3g1vWyoCv6gj38KvZOcsynvUdKiymdgvoUyFY Cam6JL5BQ2H3E/TLa7F0fecSQJ2YwaqKbovEB3B5FnkGstmq2Org7sOnGVQI3J6ZyTM+J8UXotQ NK9jBWL/ikgKPCscAoSwdkjtYOSa6FdNrQZcniTD7BUgEVe1PoQNBjz7BFD/XbAS2mhnvtJxD+W 5omNTnn984rat7Q== X-Mailer: b4 0.14.2 Message-ID: <20251112-binder-bitmap-v5-6-8b9d7c7eca82@google.com> Subject: [PATCH v5 6/6] rust_binder: use bitmap for allocation of handles From: Alice Ryhl To: Greg Kroah-Hartman , Yury Norov Cc: "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Christian Brauner , Carlos Llamas , Suren Baghdasaryan , Burak Emir , Miguel Ojeda , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable To find an unused Binder handle, Rust Binder currently iterates the red/black tree from the beginning until it finds a gap in the keys. This is extremely slow. To improve the performance, add a bitmap that keeps track of which indices are actually in use. This allows us to quickly find an unused key in the red/black tree. This logic matches the approach used by C Binder. It was chosen partially because it's the most memory efficient solution. Reviewed-by: Burak Emir Acked-by: Carlos Llamas Signed-off-by: Alice Ryhl --- drivers/android/binder/process.rs | 63 ++++++++++++++++++++++++++++-------= ---- 1 file changed, 46 insertions(+), 17 deletions(-) diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/pro= cess.rs index f13a747e784c84a0fb09cbf47442712106eba07c..933b0f737b38ffac536b19c9330= dfc63ffc72f2b 100644 --- a/drivers/android/binder/process.rs +++ b/drivers/android/binder/process.rs @@ -19,6 +19,7 @@ cred::Credential, error::Error, fs::file::{self, File}, + id_pool::IdPool, list::{List, ListArc, ListArcField, ListLinks}, mm, prelude::*, @@ -367,6 +368,8 @@ impl ListItem<{Self::LIST_NODE}> for NodeRefInfo { struct ProcessNodeRefs { /// Used to look up nodes using the 32-bit id that this process knows = it by. by_handle: RBTree>, + /// Used to quickly find unused ids in `by_handle`. + handle_is_present: IdPool, /// Used to look up nodes without knowing their local 32-bit id. The u= size is the address of /// the underlying `Node` struct as returned by `Node::global_id`. by_node: RBTree, @@ -381,6 +384,7 @@ impl ProcessNodeRefs { fn new() -> Self { Self { by_handle: RBTree::new(), + handle_is_present: IdPool::new(), by_node: RBTree::new(), freeze_listeners: RBTree::new(), } @@ -775,7 +779,7 @@ pub(crate) fn get_node( pub(crate) fn insert_or_update_handle( self: ArcBorrow<'_, Process>, node_ref: NodeRef, - is_mananger: bool, + is_manager: bool, ) -> Result { { let mut refs =3D self.node_refs.lock(); @@ -794,7 +798,32 @@ pub(crate) fn insert_or_update_handle( let reserve2 =3D RBTreeNodeReservation::new(GFP_KERNEL)?; let info =3D UniqueArc::new_uninit(GFP_KERNEL)?; =20 - let mut refs =3D self.node_refs.lock(); + let mut refs_lock =3D self.node_refs.lock(); + let mut refs =3D &mut *refs_lock; + + let (unused_id, by_handle_slot) =3D loop { + // ID 0 may only be used by the manager. + let start =3D if is_manager { 0 } else { 1 }; + + if let Some(res) =3D refs.handle_is_present.find_unused_id(sta= rt) { + match refs.by_handle.entry(res.as_u32()) { + rbtree::Entry::Vacant(entry) =3D> break (res, entry), + rbtree::Entry::Occupied(_) =3D> { + pr_err!("Detected mismatch between handle_is_prese= nt and by_handle"); + res.acquire(); + continue; + } + } + } + + let grow_request =3D refs.handle_is_present.grow_request().ok_= or(ENOMEM)?; + drop(refs_lock); + let resizer =3D grow_request.realloc(GFP_KERNEL)?; + refs_lock =3D self.node_refs.lock(); + refs =3D &mut *refs_lock; + refs.handle_is_present.grow(resizer); + }; + let handle =3D unused_id.as_u32(); =20 // Do a lookup again as node may have been inserted before the loc= k was reacquired. if let Some(handle_ref) =3D refs.by_node.get(&node_ref.node.global= _id()) { @@ -804,20 +833,9 @@ pub(crate) fn insert_or_update_handle( return Ok(handle); } =20 - // Find id. - let mut target: u32 =3D if is_mananger { 0 } else { 1 }; - for handle in refs.by_handle.keys() { - if *handle > target { - break; - } - if *handle =3D=3D target { - target =3D target.checked_add(1).ok_or(ENOMEM)?; - } - } - let gid =3D node_ref.node.global_id(); let (info_proc, info_node) =3D { - let info_init =3D NodeRefInfo::new(node_ref, target, self.into= ()); + let info_init =3D NodeRefInfo::new(node_ref, handle, self.into= ()); match info.pin_init_with(info_init) { Ok(info) =3D> ListArc::pair_from_pin_unique(info), // error is infallible @@ -838,9 +856,10 @@ pub(crate) fn insert_or_update_handle( // `info_node` into the right node's `refs` list. unsafe { info_proc.node_ref2().node.insert_node_info(info_node) }; =20 - refs.by_node.insert(reserve1.into_node(gid, target)); - refs.by_handle.insert(reserve2.into_node(target, info_proc)); - Ok(target) + refs.by_node.insert(reserve1.into_node(gid, handle)); + by_handle_slot.insert(info_proc, reserve2); + unused_id.acquire(); + Ok(handle) } =20 pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult= { @@ -905,6 +924,16 @@ pub(crate) fn update_ref( let id =3D info.node_ref().node.global_id(); refs.by_handle.remove(&handle); refs.by_node.remove(&id); + refs.handle_is_present.release_id(handle as usize); + + if let Some(shrink) =3D refs.handle_is_present.shrink_requ= est() { + drop(refs); + // This intentionally ignores allocation failures. + if let Ok(new_bitmap) =3D shrink.realloc(GFP_KERNEL) { + refs =3D self.node_refs.lock(); + refs.handle_is_present.shrink(new_bitmap); + } + } } } else { // All refs are cleared in process exit, so this warning is ex= pected in that case. --=20 2.51.2.1041.gc1ab5b90ca-goog