From nobody Tue Dec 2 00:02:15 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.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 E1AFF3242A2 for ; Tue, 25 Nov 2025 13:59:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079199; cv=none; b=O1feu46h+WvLgtWF0/djwGDIxg1V6Op6u+fvZeb91vVmIhj5UQy2jIqEVbodl4Sq8SYZ5bTJlS2ZwVRK4e39NoQWr3BwsJLqJKixeMDckcsIrO1ERUtz38tXeAfDnPMvGizeO3tmDcWDBeH9GE6OXyIjJmoke+4zJ9Xti3X+Faw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079199; c=relaxed/simple; bh=emQPdhup99Z5QtiURk30Lj0zFxcNy6czk/mQFRFY1Ec=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=KJFzqt+Agj8qph+InC/dPCIqqlxy1ZslVvvFK4sbJaCJHjFYgSEB+zFClwBuzvO84NRNFZCZsunJ2A1SCsg+bl4/2cL/W7ZoOzIE9zGt5h6Ad/QgP83/aINuUh6c5e4ZKSBXSAxrR+UppdxOd/0tugriRvQov6+W4cuG/3Pxceo= 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=pMPc514y; arc=none smtp.client-ip=209.85.128.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="pMPc514y" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-477cabba65dso23180925e9.2 for ; Tue, 25 Nov 2025 05:59:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1764079195; x=1764683995; 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=chXXKrD+EO5miwbK6PlKXaTfuoU30ukfdCueJLsRgKk=; b=pMPc514y/accauwuPYSqNkZ8tbYH9ESbnXg8KvKQRFkcTTO0Wy7BmDtuErWjbKajMn ODENe/JhQcjyBtTf03PnwumXhDIvPf1vPkmCQ7tYzgqqWs3NvBlF8qkGUJUo7Ib6A5w2 NNRQpkzstPuFlStvSdaRtVsnIttYlrwLh2DZBP3GU1UxSt8sfubLgZ0BPUcw5EzFh+NZ Px2/u7eACknsqU9mdfqwAfhyKsadneb7thLHYpvyBbAn/5W+DPWamlmNCZsOrBdftSC1 FYt7TEm0HAzsy7F8oCmYqEhDDtTyhSuZgNkEObkxt33vVH31fHBUE/XAPubeRYljlL1Z YDmg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764079195; x=1764683995; 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=chXXKrD+EO5miwbK6PlKXaTfuoU30ukfdCueJLsRgKk=; b=ZqGpx5jKCS3ZGVX+k+hoygIPoIAzO1QUOHqaS2d/YPT4E2mEkDGmnWwOemyP4fAdP+ XqdWevba3mv/d7YbZcBm2mnCOaeWGYS56D2esRuYpMfON3N4650ZkOZlON7NQGB+bt/y RbdOfEYN8ib2IAZhqLmf61Nnwn0n9+v0zt8pijT0zT3HQhSl0iL7HSzcg3MCGfkjfOb8 WZEH9yaJIb9wot36ONoYTCu7NGHGqDCtnUHkSxiZZUToYU+S1HHS+x40HdViHCKohgeZ UlPpRhmsNPN5tH0Md07Lpaakc+QKYtUcNqRcJ93Dg36EfmtF8vH/JgwQWKHf3PzOwOzF 8oOQ== X-Forwarded-Encrypted: i=1; AJvYcCWIn7hBMDhqfwEMIdxXzy6+m3eDsneoDyXoXCcJVUxOwK+GFVMo8Sn4qRHr53WNhz5/kMKEjlNviL4jpHs=@vger.kernel.org X-Gm-Message-State: AOJu0YyNTay7G5JZ024sqGCpZ9ldNkDhDRFaY/nzVGo3IjxG4c9ykUZO qVLIyNEh5drEr1mdtFHt/9oHqJ4ra9bFkqnnIq/jA0kXE99ZHH7a0mAkBSnrp9TdhHzsfsIgn1z RE9CmwDRgCcYrQQNYDQ== X-Google-Smtp-Source: AGHT+IGRFXXkiHfta8PSnKNzjAC2VJBxGSZWUgFyXbv+BxfdZofY3oqG0yTSaodz9j8ihSokENMBvq0kn8NmCsI= X-Received: from wmht12.prod.google.com ([2002:a05:600c:41cc:b0:477:9f68:c324]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:154c:b0:477:7b16:5f88 with SMTP id 5b1f17b1804b1-477c0165a5cmr146798485e9.6.1764079195375; Tue, 25 Nov 2025 05:59:55 -0800 (PST) Date: Tue, 25 Nov 2025 13:59:37 +0000 In-Reply-To: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=9078; i=aliceryhl@google.com; h=from:subject:message-id; bh=emQPdhup99Z5QtiURk30Lj0zFxcNy6czk/mQFRFY1Ec=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpJbZYFGwaU4GbCDXqBbs3FZ6Xabk52Z9GLWkzp z424Dg+9aWJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaSW2WAAKCRAEWL7uWMY5 RrTqD/4iDROrp6gmLNwpy1aWZjr/JZps3FQvutW7W2LSYcMrtWW1MkIuJ8Htxf+ve0GnMC4ibd3 4kQPbyfATUR748Y3u95t0akpkkVjicxlrEuq5FbYgN3DBTOoylLtV2hLuYF1qTV1zzNImGbsp83 uxiqVFPN4NeF76Eg0JFfLay62UPWDVXKu6Ona+Wy6bL7gqldojVggQMkWbyjPLRqkieR/JeNXY3 zBK8bOeAjwX+/WK6cCN9WkwvSHIv3z5kzJoBSCBE4MRV1VbG8qsw4K5A4oz7qduVFBC4Li43IKz EVyhuW0pRNC9w8iMWSPPaDTFJKKKF4N393FzKrEOuygS18VM0JF43bXtJPRnRY3F7Mc1IVkw60X s/So/jFxY62vqKF29MX6826V8haRTmMtGg0tvr6Gj1ieePOxKD8dwAxli+/+I9ygAiSw8KXGmjL 4WxeOSYeyCgs/2nINTrzsDG/r0WqFKirYgU27Vmcb8rmOzN1YfRShi0xNI4XfhrF5TWgCenA0Zu 6SohPlBl7npMSS/8K0SohcAfNQ/4wTO62CsPAOYstYJqpjNvr9OjZimUEAP9iHMdh/rLWlyhWYb /IovPGg6WnfHp5cZI5pyteQV0o8Fwii5gzu5Ou/GW+WVxuRkLbzC0cHTfMAvmgjC/LsOVrqw0f5 YS8rxo+0rKF3j3A== X-Mailer: b4 0.14.2 Message-ID: <20251125-binder-bitmap-v6-1-dedaf1d05a98@google.com> Subject: [PATCH v6 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 Reviewed-by: Burak Emir --- rust/kernel/bitmap.rs | 33 +++++++++++++++++++-------------- rust/kernel/id_pool.rs | 39 ++++++++++++++++++++++----------------- 2 files changed, 41 insertions(+), 31 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..0b1f720a1f7df8766a8481f3c0b= 332d4cff3b4ad 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,28 +113,34 @@ 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 /// /// ``` - /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; - /// use kernel::id_pool::{ReallocRequest, IdPool}; + /// use kernel::{ + /// alloc::AllocError, + /// bitmap::BitmapVec, + /// id_pool::{ + /// IdPool, + /// ReallocRequest, + /// }, + /// }; /// /// let mut pool =3D IdPool::new(1024, GFP_KERNEL)?; /// 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(), 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 +149,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 +180,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.52.0.460.gd25c4c69ec-goog From nobody Tue Dec 2 00:02:15 2025 Received: from mail-wr1-f73.google.com (mail-wr1-f73.google.com [209.85.221.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 98976324715 for ; Tue, 25 Nov 2025 13:59:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079200; cv=none; b=ZNyosnVJmpxKBYgiac/ZPENr4op5l24gHnrZIKfGImqX2AxFW4jE9Yi/xPGD1FzM3hqUAA1RDrOuKz6EXlKPkS//d/a85msm070wKkSJ4nrY6EYaJmjxzzQ36HKxHYv/av1bd8crhwy2xW6WGLsOGQnAK3IisWdbKI1vzVrwrkM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079200; c=relaxed/simple; bh=7Lm4L7B0JSXJDytRz3uU8jk5LUez42F7IysaCo6TfkY=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=MvrVxH+9hAReHi5lVgv8eMB4puO0Ht3sqtvWmQQhlVDX1/4QlyqSmkvtBSf730SIkJBBlu5BAtDLglzU8t7zew6ai3ZLlmLzDbzTr9K2qr4YYQKyXwZMQMcaViAkeadDt9mJEihcVnRW7k7oR0tjkQ7cTrq1C5Mui9xemP1tuDE= 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=JqWaxDIn; arc=none smtp.client-ip=209.85.221.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="JqWaxDIn" Received: by mail-wr1-f73.google.com with SMTP id ffacd0b85a97d-42b3339cab7so3703571f8f.0 for ; Tue, 25 Nov 2025 05:59:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1764079197; x=1764683997; 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=PhJL2eYeGqpdi1Nu5380iJU2myJLCzrIUeqE1Vlfi/Q=; b=JqWaxDInF251NR9s2f2rKrZVk8SoRVsLplRVCTqUfy1w9rt2Qf8PaXBU7KJnPiBH0q Wb2BGV3+Qcvy/3r7DY1lc/qDzr1U0sC58Wt8gKny/3EJrZoAxvamqXFSEJgoz6uR4YLz sCdUzzJmTyggw4rRH1hQS3+2ZFxKh9ZzQZN8qL3kG9njiHipQT8C0bAlyZtkoV0inPR7 ncI9ELpbfmdnIsqgkbysp8hhV8CqIoifX8e0YbloQBX5wa6W5KNtu5CKUvA+iUnCLesX EhmHMGdiTKRPaS+N8QHnr0LPg17/Nfyg9uykyck32zSikbDM1tg+5abWG4fVcgZ7XhgZ BX0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764079197; x=1764683997; 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=PhJL2eYeGqpdi1Nu5380iJU2myJLCzrIUeqE1Vlfi/Q=; b=KT8OtSo/Cx+iUh0dRAJmeviVCyeQ/XadPNNJ/IP6jrG+JFRICPxf0FcXN+LyEKmHOZ E6XceovE0X/EiKAoL1zZ221nDv3jpO8Ak94nlmVZEeYgzni8DxZd1YNhx2QXSxdEI3wh Pm4NC9YHIkvPbUMzKDN3WEsXWHZWPA2z9Jazks7gjMTk01W5TiF/ZbvBzkgTW9SdbxgZ 8glKIXlqBU3Y9lyPGzD2w6iexxI9PIZBOWVoOWgbmDxRycN16NQqRrES7Y/Bv12uS5BI oubvmGozx3hkGkr42z+GSOX/hY+I8SgdU1eku8y94O9tRBa7nC2DS3Rh2QU8hSs0vAWj XTjQ== X-Forwarded-Encrypted: i=1; AJvYcCUp9IGFg2V+VlzSxoqi2JcR8BTsrRMS9SlvMNLppUPZ7wmhtNeCWud9unFKuMd6O/I099ExMhJwfKSKq/8=@vger.kernel.org X-Gm-Message-State: AOJu0YxBM+fNSmOJxUhLLdQKpfU0SM3UFMuw1P7fFAYneAXis5UKvm3f RtBysk++cgEfgoBIOjf9t3ZAC+BufT9k2GNUC1HvdJlZwqYmhJ25AuhbJ/Uua8XJyoCIcFfC9es 7AOMwydtoehOOitnQlg== X-Google-Smtp-Source: AGHT+IEyeAgM6t7/dx19tQPq32ePVqS87dUHrJkZnfELERMnuGJQ+/H1zVgXRFg/DoKwuDvpjgHvfGYzoZsRUmw= X-Received: from wrqf12.prod.google.com ([2002:adf:f8cc:0:b0:42c:c2d6:29b]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6000:401f:b0:3e8:b4cb:c3dc with SMTP id ffacd0b85a97d-42e0f1d5890mr3161753f8f.3.1764079196864; Tue, 25 Nov 2025 05:59:56 -0800 (PST) Date: Tue, 25 Nov 2025 13:59:38 +0000 In-Reply-To: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1303; i=aliceryhl@google.com; h=from:subject:message-id; bh=7Lm4L7B0JSXJDytRz3uU8jk5LUez42F7IysaCo6TfkY=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpJbZYblPctXPrCXfxhBmnAUqceO4bNbw7uKXEz sAl84kcBaSJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaSW2WAAKCRAEWL7uWMY5 Rr5ID/9YP8uj7WhTFAyf4iLO1Ty8Nis/q8pafkrxeO5iZ3DXkikeMkBxuYxRy7cPRLhf/UA65HA YRMHkFgMI7yBBpWkWwqkGLsaapPsdnjAvv10pbO5qyhM1GqzFv8X9TmO7x2nY/PmzwD961+fQBh kvovD3nQ3kiUXapUI6QUSUFCp9W5rRScIflBgu67vmj1IMhBhCc4J60/C2YgkNeSruEJc30RU2b ld4qa48s18FVCRV4vwdWxz4xsm5zOXh0Dmtdq+wMBG+zqfNAW9tTFbLul0HI3QpmIdtLZuVZUSZ PIfktEqhFqxqGWChS+cqKL7GvxF8wlZJ3NuoLL1hiEtIRQunrqJI+HKFkiFeeIRrPv9cOX+aHeK iesIG32InAD3wqncM6R/Jms4QL93dbb0Ee2pemBH7U016VCPYnBJXumvHlFiPgZCqY5SjeEl72W sCqWJBMpizJtYsHbmc8BUMQNzPv5U0EWtrzy7LMu3juN9HcHdPSOjjxQkhsxzbwnp2eStXobm3l 6Odm+oWdsCvhcTMgWoBDLloFSReIpjW4N994UiOR0mFwPOcLhLxJNk7fR1i7jCZHC2CukWQgNCe CuD+VJTd1dlYMZrXb7w5AVCJsRmSRmO7qx+OMudWSpukp3HLzTJFuSE5ZK1L+hjG+cugXMTHAuu g/edqGMXUwtkoHQ== X-Mailer: b4 0.14.2 Message-ID: <20251125-binder-bitmap-v6-2-dedaf1d05a98@google.com> Subject: [PATCH v6 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..83d7dea99137ded7cba47ec5a3b= f10bb7e13f2d2 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 MAX_INLINE_LEN`, so an inline bitmap is = the right repr. + BitmapVec { + repr: BitmapRepr { bitmap: 0 }, + nbits: BitmapVec::MAX_INLINE_LEN, + } + } + /// Constructs a new [`BitmapVec`]. /// /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allo= cated. This --=20 2.52.0.460.gd25c4c69ec-goog From nobody Tue Dec 2 00:02:15 2025 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 D66403254B0 for ; Tue, 25 Nov 2025 13:59:59 +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=1764079201; cv=none; b=Y4yz2NepcdWqg/TIchFBDEcqtXHXofnLoQcVY5GIP9PXITT8fLveGK9ysnSWGFby6APoW7whxSSbW6DNFNfZsi98HBOA19onr9CZpf2st7miQHTZ6vttw6jLJENyByd/WAs9SKJDDYt1iiG0kXu3xHu8a3SenMPBnD4Ksljv5XA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079201; c=relaxed/simple; bh=L3V/hjYTh4TcX40q392ZKDq3r/3+jf1d4NHStYeCYDw=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=UVAq6LIqnuxrDYCToHneDZYbLoBaoPIOnMXEPEeyp0P73D5V4rZ+p1an5f0rpQgXxh7ls44fzQ7SQNqx0iKyAO4vNWT5iVgIvLsi1E05YOKHB3prc9XV04EYJf6+26I/hXE7+aC52V59Sd921rp5bfNMcPgzm089CwepIG5ROzg= 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=qY9Mm7hM; 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="qY9Mm7hM" Received: by mail-ej1-f73.google.com with SMTP id a640c23a62f3a-b763bab126aso688653966b.3 for ; Tue, 25 Nov 2025 05:59:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1764079198; x=1764683998; 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=mYICst1qwypuMGrR3BVNHhiHZNySi6HJ91X6sJpgEH0=; b=qY9Mm7hMftYLNvrW9rzgOiN5ReU1HbJPISx9kXF7RIlpa5aOTqBF4vyYfxHyBJ1hpD 2L/DLlK6jblDc14zj+6l+iRtVf+i0VZXjfZj1sy8EKvlCRd5rzB0aWKtvYFmHHykmrDI ucEFdu14hPUeetH4EpHM0FIZgv6dlH9celi/MzXMsQG97ODV6UWQd/2uIVzCK9TajaUV 6gn33XKDjwOVhJ8iCo+m0uIeBNA0KQ0qXkNk8fU0ob+iruF+kMiZ/E51EKP1eWbZoQMh +dKMR9Wo06ZjoHUPu4o58SRKoq87FJ96najL1PfNdsEuXF1ZXUdC3UzChGoBAZxxN0Vc 088A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764079198; x=1764683998; 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=mYICst1qwypuMGrR3BVNHhiHZNySi6HJ91X6sJpgEH0=; b=Xek9Tmpf3ZpTv4AskMSE7P1RmCoW3Zi6GNcUqNoLaGfXok4AVzsYZZRPT2y0//8s4e NWyKrSFUPrd8GWhbPAIvvebzxalPP5nFa/FkRCYJv5Lp1KQnWDOb+wJ00F5IyeagMDRD rozt82cSBZx55F/25UijsZfL7Gmj9ah9dkr4/Sfim4b75l9Rn8j2/j25+TQC4OMQA95B f3YunwWF4mAXcAjaQGW8d4MzhicDb7YaHyJdT2X0olGrFNx64GoDBEYG6l6BqclBhqkP iAeq/bHNR1lpwuosnYW7x1792V8wB3cKc5S7Tv5JyTmlc3IPvXFNznyDCTsoTX/En1AH Ggcw== X-Forwarded-Encrypted: i=1; AJvYcCX2m3NClRiZ3daWYv9ZHhcrqPkfyE9KbRxJOoAJeEeldaPAYcyoMA9bRv6MobuyzZZWDAK5VKF3Xqgz6Nc=@vger.kernel.org X-Gm-Message-State: AOJu0YybH4kSwxjjX+jYYqza5M1P29LqJq+kkgarJgwE1FC4v2gRP2fJ gAO9ljAIqTQG4qA1ma6vFqE3AS4zJOPJT196jeFK216E4bMu8UQXawqp0l1zYnBVKuwMUq6LwQY ir1nkx8zt7WcIw6VkQQ== X-Google-Smtp-Source: AGHT+IEdtZeVuESzqfQa48LfHPw+m+ViYXyfo2jQlTY7KINvNtoXCJIYAmkzm+U6yaLcIfB5QkfViMaZA5seMWw= X-Received: from ejctz9.prod.google.com ([2002:a17:907:c789:b0:b73:5d0d:776f]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a17:906:fa0c:b0:b76:8077:4eaa with SMTP id a640c23a62f3a-b7680774fecmr1022841766b.6.1764079198071; Tue, 25 Nov 2025 05:59:58 -0800 (PST) Date: Tue, 25 Nov 2025 13:59:39 +0000 In-Reply-To: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=2248; i=aliceryhl@google.com; h=from:subject:message-id; bh=L3V/hjYTh4TcX40q392ZKDq3r/3+jf1d4NHStYeCYDw=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpJbZY5UyJaMWpH7olMyhiF1A4pqajsthJcWOUT BLc5cw0c16JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaSW2WAAKCRAEWL7uWMY5 RuauD/9f5YvyxMXU8Sd5fDOAmwtzP2TPTv+96udUc8i3bB1pa9RY8h2Q7pbttSahKdx+9Mq+FGG LMxc8dW7hK1KpvwzbI1tNHkb5wkD9GT8aF2GR115Bk0QHyeUDj+a0LB3ncVIal1b2sqKAn00nOr EV75V+G9VSQP8toXlkJ1wKzurOZmKgV95pSvO97oC8W7Kn+CP6kGX36TIY4RkuMorRUn6xWDvk9 AeCX1+gqBtl1HcZMppkFNp6g3yLTM85U3BmCTtyzohBqLdBNRCsz/9wEtC6rGCorTQXRR475mDz zTgqeY4lw/AM1QiXPrzkFRZqDnDqnu41gOrMXZMc18h/todlO1kGocLSQLzUgIMTX8RmyFnZiC9 zszL93bpojGkp17eD31+sBjtGyG/bFp3p2lWbuu0Xv99iZ+2Ayi2QPQlXBl1y04tm0QYRUjNMqZ HrQEwnQIujZ6KE7tT8SmXBJRSOH0BCTZEr5D9np3XYiilbivtagS83tUlAdDM4ok5peiNpFiQ1o IvXqY3nQYAK2q0AJ2dDh6SJLQADomfhYqa6sxf+GDTdS6xlevfb8lKrju3+y2RA3lPJWp2ejGLA eblyOJvqiYzI7UgPT7FKBMUnb40bIG7dXmNoskZC5RWSm+UROxqy0HEGTmgWWCwv69asJ3ibZ1D 6GmGffPbaIAU+vA== X-Mailer: b4 0.14.2 Message-ID: <20251125-binder-bitmap-v6-3-dedaf1d05a98@google.com> Subject: [PATCH v6 3/6] rust: id_pool: 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 | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index 0b1f720a1f7df8766a8481f3c0b332d4cff3b4ad..7968b6c5566bf7022b865b5f59d= eaf46c96f747d 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,13 +93,13 @@ 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 { + pub fn with_capacity(num_ids: usize, flags: Flags) -> Result { let num_ids =3D usize::max(num_ids, BitmapVec::MAX_INLINE_LEN); let map =3D BitmapVec::new(num_ids, flags)?; Ok(Self { map }) @@ -129,7 +129,7 @@ pub fn capacity(&self) -> usize { /// }, /// }; /// - /// 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.52.0.460.gd25c4c69ec-goog From nobody Tue Dec 2 00:02:15 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.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 7F452224AF3 for ; Tue, 25 Nov 2025 14:00:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079203; cv=none; b=Jd8dfUvZAqvCCy9TaMa7QHfUd6oLda0ES10hqpXGk7BQo3KspKqfmiQOE2sbLh/LUI3wWBqo2YMaIPEe7GqUpNnIGnoTkuRTPdE6M/fURLvCObQ4yxEfhX3ccrELBQCxV0v6Hc/qhLDnJqBnWLrN3z94PAim4Oy+HJ0CiWhSTHk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079203; c=relaxed/simple; bh=zjU+xITGYBikz3POlNtXOEPXelplJfBbb1n+/juZ6VA=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Qc2GblBGy2FKrLyDGnIVVAQGiwzW1cCBk8BKgxhkBQ9snwaGlJTcB0pQyy8S+qgkLF7ec09q7LMu7PMWlgA05rbRlhIc88cRGSAirZrYbaFMjALK2+aIkTRe1auPt6fgUz0MvvceL9vnTUcrUX0COW3mxzXBBuTLefdEORzfZbk= 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=gLBUU8Vw; arc=none smtp.client-ip=209.85.128.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="gLBUU8Vw" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-47106720618so70194845e9.1 for ; Tue, 25 Nov 2025 06:00:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1764079200; x=1764684000; 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=0ridHkn+8MIeXliQ1C+V4Os2CRUMRRUj3W1b/Hqz1Mc=; b=gLBUU8VwMg+92q+pdq5GsBgrQWVSkhU28zECfvoKNfTmqfqReb3+pxbwa5WmFkZ7rJ aBcsR6n2vpq9pNXPB18dxhNLNobCvprlxzkV/IPjGikxz7nX64RgGI+8TAMcAA6eE+rM ER/ktyivoo7FHfTcDEJ/HjKTTEJJfmcmQYufOk/avHxgVXxaWR/SYmI8kRVE025pV8Sw kdyK7Quhv8Koi7GqhUxQr9zRjCOpdnuQfbCRTHeWqAwKR5H+OvZp0oQdl7+bC6H2BDUY zErnQe1MqKRURe0sa+kdNiG7Y16r7lUeQVyyKJunCVv13f1P6NVKjlt6QrY0RwbRRYpv 2yGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764079200; x=1764684000; 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=0ridHkn+8MIeXliQ1C+V4Os2CRUMRRUj3W1b/Hqz1Mc=; b=UEGHfqtVM+N9NYIEphOxj/VY/7ZzBwLfmDUlLrDxF/HSfpm3CTdVlRWJGy6rU3oxST Rb8clioE99QpN02bt76kXmTPAxV0lKWyw+MlkzXpP+eA+fDtFNHJ391errd00KXu5dGo rXEL8aFk9nVLU5WD54Qb0ipgYZfdg13d5fvQIYXDpR6pO993T3m5OEtbdMWA36ypYRw7 OBe+Lzd3rKA8N9Tk8adWiOcVsuImHOddt0kBYXwBo07q61W3Dk1Y/hVcLEfuKzUyAq9R 1oe1jouOSLFv9/JLIsze+0zLyNuAV1JW5UD/1sjZpk2HWf71KRTFFtD9WzAuIcjvqW2V +fWw== X-Forwarded-Encrypted: i=1; AJvYcCWTfdceMlM/IviJI/oHUOeyAlNvhC7Ghe+1vhRTjI3N0hB4Fc+f62yXL/Ebyhv7InTATqCKMDXxDxYwCg8=@vger.kernel.org X-Gm-Message-State: AOJu0Yx0KUVAEEsVCB3VmQkFHSB2gk1gsyo6d4I8mOqcmZYxKhMh/qwl ebf1dH38qZPobc2Awn+TclwPSMPb1vroKJ4cC3epLJ/yfwO1EttJxwxe+QPpYl2VrofpegjabkD QKHoUGlaurMNMgyHxYw== X-Google-Smtp-Source: AGHT+IEKtSfIuitGQ3id5RQJVYt5y2EoUT2oM33EIONJTDt15OpOx968jb4WJdc4CS0+xkC1sZ3vgfrUWNrlcM4= X-Received: from wmpg42.prod.google.com ([2002:a05:600c:4caa:b0:477:7ed9:17ad]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:4e8e:b0:477:5aaa:57a3 with SMTP id 5b1f17b1804b1-477c017512dmr147750455e9.2.1764079199625; Tue, 25 Nov 2025 05:59:59 -0800 (PST) Date: Tue, 25 Nov 2025 13:59:40 +0000 In-Reply-To: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1712; i=aliceryhl@google.com; h=from:subject:message-id; bh=zjU+xITGYBikz3POlNtXOEPXelplJfBbb1n+/juZ6VA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpJbZYqTKcsz22atZEfxzG4xjJGo0eUshxVev6E aMGl5K4C4SJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaSW2WAAKCRAEWL7uWMY5 Rr+eEACWgQcRUdJQA14WuJL7sAPA3w1SOZ3sa2T6ZvPAjW8cf27sI3x7mRvrSTsi7tVQBGIAeVR MTidhCHXjDUGac4d3Z6PZz/N4fxCE0dLTCQrACefD9EyHxW2J0XKz0FFsWzlwO3oMAphGYYnZn6 MCvk0mu/hCmARm41ZavvnnCOmKTawgNdRzJS78x1HaP0Kob5RW368RUwxjry6oUGvXKpCgSqwYj GmtPrpWSBZTjK0ofvq1h7crr2CE269QWurJ/p53beEo19olT4DFVlphwqlU2ASUV3C3Cn6SHRfy Y/qiV9XIF/9CPNLy2LK6cYi/WO8S4vnJxrOtKnWmSNr2YfW0bDhKuj8+R2biXCVvtsK5apVS1GC X8RvbfCP3EXZmeX/0WXjs3hHAcBzObYLFYGQZ1zNuNkhZaKn/YoXHBl7y2eo7gKdwSBfdmHPQSX t9Ru1eWn0MeafRuyhRLtlfP2TRV4B0yGfjo6B5onM5422ubUEejah8iy3UYyxyV7RIwtpNdYpOk +LjQUoKhHsTg/XFPQ5OMB3nsZzwexaA44AQJzt9VZC1aC2w4WYOdoHsB3bWd3FIaDc1mOCpQa97 u78LbwS0nAzsHsX2cmc2ZDt+zP779nFS5iBJiLTw4GGNarO/SxvxYpazwSM/hNmifdoBzmH1Znl Kiwce3DT9U0RXng== X-Mailer: b4 0.14.2 Message-ID: <20251125-binder-bitmap-v6-4-dedaf1d05a98@google.com> Subject: [PATCH v6 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 7968b6c5566bf7022b865b5f59deaf46c96f747d..1adec2c6fdb0b80515f9b64c672= 18efa864ce580 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`]. @@ -229,3 +241,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.52.0.460.gd25c4c69ec-goog From nobody Tue Dec 2 00:02:15 2025 Received: from mail-ej1-f74.google.com (mail-ej1-f74.google.com [209.85.218.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 D1AE623372C for ; Tue, 25 Nov 2025 14:00:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.218.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079204; cv=none; b=oPNMHDPkPElfXwFlE3lyNKHVRCwrKTzitw5A8jocDOgzkZZnukPVexwHXXMsSpAHwAt4MpA3c0KiVcCNy4u5r5kPRThyD0t3Y4qFWVGIj4C6+N8tAT/Cb40ti4YWRdeyuaRBcmnRn7NTA7KGzjnBWFa2NRwxG4/W/RNbdEGcKuc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079204; c=relaxed/simple; bh=H5sQlozQgdTviWcXpdsUawBLLbxV7JUv936dYiLlNyk=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=RAW17S/GDOx6p8GjBoJopi4ZCSdmFEgoGqtipvllNw51UpTPPIGGSdPig/ecXTazsJxtYdeja4lqT9Rfg4kbstsJpB4rJ+xkMMCqHSpgF0PUM9hkBSFANimhloXM+0JQQ77EIIVki81PYiAfp7284LpxNRTpYvgV/JZDACu5cr8= 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=dn/3CME0; arc=none smtp.client-ip=209.85.218.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="dn/3CME0" Received: by mail-ej1-f74.google.com with SMTP id a640c23a62f3a-b726a3c3214so522028066b.2 for ; Tue, 25 Nov 2025 06:00:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1764079201; x=1764684001; 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=FGyrSjyLmW1aQxrJ0voWMyUBxAPU9xZJRGnfMgNjx+E=; b=dn/3CME0LnyXCiG5ssdDq7Qnb35Tog0pIgYO3306sioF+sF6SVym8/GDcfTIUrpgfZ 5qMHAHJ3FBNheFiYvSWzrrIwIhcUm/1V7rn3ZolZeBQM3BfZa0bq28i3R1H/29hhDYWK xL5Oa3HKYFwuROpJYBAPO3GqBl3iTg7JriMly9sRio3Aq8Huj5wlvksftK2x8vPO/7Cs sSjO9GgnKdOV/gI97BvGowMR3ntGfXMM6Cms/lVTYMZ+Tdiw666S7+30HlSP9lcnUjmq muXVvfph9Y3ndCHimTzqrvWP+F1Ize7kzhm/xvCvE70aaZo0O6YLpEP+Mgu3ebFo5C56 45Hg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764079201; x=1764684001; 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=FGyrSjyLmW1aQxrJ0voWMyUBxAPU9xZJRGnfMgNjx+E=; b=oCb/4DKYTQkmCLicoM6CCIoGTKBaM1chXV6ApTk/FiBZscM/EoBU8eVqeHhbSadu+o LlvtIelV/on86zRTF0hW9nhjLZwJ7h4rO8NzJ4ZqzPhMrqDzMEFu7OBEDG0tcFORp4pX zf2yvxSvV4tMjDFq8s5kEuArqCzepNGXHvVpQf1GcaVUylPIeAZslUAEXP8q8uwYpYF4 wxQXVBWvBPzehlmb3RCYSeRbztzS+3PH7HA6InRIuMYX6Zu6741EsqTdTt7nOaTPv/7P V0ipM/J393ZQsy/NL/DVDb+4HLwdcnuxsg1KFWrZkZkEIjqyIRuzzmnRj9xJro6WNG5a 0p4Q== X-Forwarded-Encrypted: i=1; AJvYcCVLU/LnOX8TIkVpJg6nryDljz3epaGWSddZOD/kMGCKBQDohnPv/5/ziKAqMC4NbsGsPk1usr3jObTW960=@vger.kernel.org X-Gm-Message-State: AOJu0YzQKHx/CPpW+9utRjsxpnqC1Bg75ev0lfggz1gs/HadllvAw8P+ bomv8XKdIwtl9QWR4n7mJtk3CjgPFdaI7KzlAgP/diALgQXBOadcLga+peelYdIbCEzV5Z3NgzM KIQZjPTxDYFwJauPYJg== X-Google-Smtp-Source: AGHT+IEEAp8zbzW+oweQ62B2PauNM+6chBML5rrFj3kEC2Ce+RRKkoXiSkljEfXTQ11HO5U11MJwjzYkdTLISkc= X-Received: from ejcrm13.prod.google.com ([2002:a17:907:6b0d:b0:b73:7130:3880]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a17:907:72c6:b0:b73:8759:62f6 with SMTP id a640c23a62f3a-b7671a52051mr1832541666b.60.1764079201065; Tue, 25 Nov 2025 06:00:01 -0800 (PST) Date: Tue, 25 Nov 2025 13:59:41 +0000 In-Reply-To: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4864; i=aliceryhl@google.com; h=from:subject:message-id; bh=H5sQlozQgdTviWcXpdsUawBLLbxV7JUv936dYiLlNyk=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpJbZYbcchNTH2JmYGWm49+hAseDKMgJBR+0DJh V8ZgkJLLCuJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaSW2WAAKCRAEWL7uWMY5 RlwdD/4skWmtrLw53OsM6+KwIO1lo04b0MiJ2bN7l79IRUMlg8smzHpbVMxs5+/A9+8xqeTIDCW FcwOCWyit/4grQp+Ro8m0SQUYDdnRkZPbseaMobFgk3wikwy27fEpggFYhFCpbnAbyRu+yRMzuA PDlI/oKkm0i9kpJay78qpMRI6Mx1KZKSKqsDZx2LvJsms4sGijVDyN/k/HOqGuPXDi7K1sqgTdp FnhMDody9uEFiqJAnZDyEYfHJFHtUgFEH1RBwmj/WrpZx+JMRr7FJEZivDGzoKJvKBXPDNITRmk 6pimRRxCNtx6Z7nkI8VuiqEU9Hd3lU0Lkm2SO2L09/KMvPE9fvziovCxpb9IUqQJLU6a+o+R9uL 0udXYqc9sd5TwuScDiUReeBLwt14cjC4we5rqWdX7QstHZfWK9hvjT8yILNCW+qjO2w1CgYj4dE HHsstY0zFxu1J6KPsLwdkWfTZI1J3VLiNq4o/AZQ73fNQDd+re/FUdete13sv40tGYZep2zNA9T rfCD16asrIr11qumv6rcu3J8XkRFwGpv3FQ51x4sJvB7JHciJlIgFCCIbEGoIAA40N2oQLDzhII KSBqROZqnZVf+JH5I6Le9r9B+M3UUupMue4UuOxgYIkFH+rCQcTpxyYKN9f90IkMAdfeGDej8Eq usIOVn4mBARy7Ww== X-Mailer: b4 0.14.2 Message-ID: <20251125-binder-bitmap-v6-5-dedaf1d05a98@google.com> Subject: [PATCH v6 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 1adec2c6fdb0b80515f9b64c67218efa864ce580..a4c37d6a0971699d1ea42facc68= aa3dd2b44a0ca 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); @@ -221,18 +221,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. @@ -242,6 +242,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.52.0.460.gd25c4c69ec-goog From nobody Tue Dec 2 00:02:15 2025 Received: from mail-wr1-f73.google.com (mail-wr1-f73.google.com [209.85.221.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 081F6326951 for ; Tue, 25 Nov 2025 14:00:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079207; cv=none; b=fbyphP0Duqo1v3RGGbgO0HLttDaVCoLQcE/9vpl6cS/KO1E5QDo/dZSBmKbxUMnJeJBafcJKf2XNVEfTo55wzkXC+r44F7wQMdzlWjxsSnDs75cH4hh57poWyGhbFS2s2rT8Frv1YIjITlGvoKZg5PSGn89kWOfM03SOgPx4Q3o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764079207; c=relaxed/simple; bh=o2N3QTu1+TpHMRp7/UKL4YXJK7hQjrcHGLKV8tDPliE=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=bbZkUiijrRQOKj2nMjMoQkrk11KouQWu39byqyqVHdWbcwUx+lCVy3gYxA2XNNMdUAdpEYqcYpnFL9MkpZ08ywSVpdZ3fLp+Jh+fayCDpdMqh/dpAJNcfA1syc9TuOqZRJ5EsmiEtJ5kx18QAY1tNU3TPe+z0lphLlHJ/fVKA40= 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=MlOQMypY; arc=none smtp.client-ip=209.85.221.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="MlOQMypY" Received: by mail-wr1-f73.google.com with SMTP id ffacd0b85a97d-42b366a76ffso2639068f8f.1 for ; Tue, 25 Nov 2025 06:00:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1764079202; x=1764684002; darn=vger.kernel.org; h=content-transfer-encoding:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:from:to:cc:subject:date:message-id :reply-to; bh=oGRza4M1pvLiwn7tj6C+02QbTQCMU0dR2sE428029ts=; b=MlOQMypYBcFLiTgd/RuU0vn053tPNrFTqt0DMvdenkMmT2yV9B131MwWVMr9AbFCsx SFqwTteV3IdrIcdGv/zEcdYI2UIDGX50OmmVe1/nxSZL3wTrBQFjIs9V1DJdTLp0A3E4 klat2HLCev3PEXOfVgi1XHnBosixvnBldPBC4xT8Fn+WVD9p7dRy0AUi12/VM+gnEZwG p15DN0PojYz23l5NhyVr6W4/d9kHYvfLMgmWTWSxdRo2DAZDfmNHtBPdm7j1PeyXnkos Vz6rorIHw1CU4KH2iuAr2j31kbyPwRLAzCxtMuRr9gPcCcPC9Ic0BFfRmvqHr3ufJDH8 KZDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1764079202; x=1764684002; h=content-transfer-encoding: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=oGRza4M1pvLiwn7tj6C+02QbTQCMU0dR2sE428029ts=; b=FSoUngRLld1GBMmsOb5tsE3SJXvmaJB26DThsfcYqHb9Bug8eiKtdm2FDVvO1Ps73c z4CeF+2ppp7cQ5smTPChYFKp9cRknDsy84V+MPTcUCTn1sTqRNL78ehY82h7kjRm6zRC OBf0r5/kkwN+wK5iLPQBkIBtrSeEhQFzr+AoeqDql+Jk8JTVHpijI5b3FyXN/oo9Z0u4 b8chIq7BzQxHoUqifJu7uzfs+pf50ZeyJSGlRbRBg6ILoQ0Dz5PBNwaRnY3aJYlFEMHU NP/07GFDiZI+PnwwgbCqyNgI6neLXq02QSn60XwhS2jLmBs0x1ed3hQE/BQ8kzW9viuS KLuw== X-Forwarded-Encrypted: i=1; AJvYcCXP4i6YwiQXo0Y7R6fcGg9qJTwY8/sN2n/DFJyiAjtWgMn9BP+bLbscxQacKdzredDcW4FN7IpmctB4dDQ=@vger.kernel.org X-Gm-Message-State: AOJu0Yw3o+ZYN0IN+cSCAA3+5FohY3Fd0ZvePFNJ9GxAYU5WZppu+gXE cf39NXZnPvS9YMi3/5xE6IMBJ/hBzbBZSk+XrrdT3loXh6BMIjbqJtlaPkq9QtB1SMFlb5lCe5J ST4oVU9FOiP/8nyclpg== X-Google-Smtp-Source: AGHT+IFqMq1h9VtUtjJ5kcjKhLjZ5lZrXHgiJw5nTw1vx/wOcwekxQ4A5Ui2hRyg2ND1oa2t6HYRjpic9BVbecQ= X-Received: from wrwl12.prod.google.com ([2002:a5d:674c:0:b0:42c:c2d6:29c]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6000:615:b0:429:8b01:c093 with SMTP id ffacd0b85a97d-42e0f213973mr2990207f8f.15.1764079202514; Tue, 25 Nov 2025 06:00:02 -0800 (PST) Date: Tue, 25 Nov 2025 13:59:42 +0000 In-Reply-To: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251125-binder-bitmap-v6-0-dedaf1d05a98@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=8245; i=aliceryhl@google.com; h=from:subject:message-id; bh=Ic10crWh9Vr+03Eo7YRbZ+ys+i8McD15VGekocwJfcs=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpJbZYXXyMpUsJ9dQHttG2KSTBIdKZ/TQC57u+o o81t0za4A+JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaSW2WAAKCRAEWL7uWMY5 RoOLD/9IVkKK/a1jvavrP5MKXLO1AOJOfnXR+oYb2JaJw8G2KD1zEJ7hUsoAoR7qe/oeXW8r2T5 N2gqvyYrxyIKyD3U6hQ2EICjO9hhzoRZDZfvqSSEPlrslGpA+5zxAjY2wnKhiO1LodANN7yZ6g2 WbawLbV/Y92v8rGoPLIEioy4V1xo+5qxctHhLbBUvFbmoxHS2hCt+3dzXaQw8rmlD0PUnIeejDw G1m6nDtndA9B8RVxuKcHuD1Zo4+yXqY+Wp/Z1dc2ELFCZGPyPYdmpfZpQu9ZShzMiCg8x6mYnZe neHQQP5hszYD/bkKGTX2tipFy9UtFrMIJgzi8v2iveXCrG13TOh6is49Jj9/GFRu8blclRxfjLl 5zBk4Kq9VC4cBAmyf2tHbHVD14m4xKiiWvDvpUELSmJvcemxX3KBVjmir2VElLBkWjkkCfPDOu3 h2r0xNb0xWUaqdd3ovDHzq2xqH3y13IctjiRKHGSDq1PbPYV9BUXJw/iaTKATbHLFp4/KxPYxba Z0dMNpHAcMJnGGKukNKfUC78CbgU11fYfTh5Hd+6PqUoxJ3AxY5dKIvanKfW4HUQtJKyNDAKUu/ SqJVVPQhf4ijCidcfyrn4cnzM8hFUMMYjO5DlDt1Y+MWftoPsMuZsZZCVbv+m+LbJ4UQG4P+KyD TByLYIlFF21o4Jg== X-Mailer: b4 0.14.2 Message-ID: <20251125-binder-bitmap-v6-6-dedaf1d05a98@google.com> Subject: [PATCH v6 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. For a benchmark, please see the below numbers that were obtained from modifying binderThroughputTest to send a node with each transaction and stashing it in the server. This results in the number of nodes increasing by one for every transaction sent. I got the following table of roundtrip latencies (in =C2=B5s): Transaction Range =E2=94=82 Baseline (Rust) =E2=94=82 Bitmap (Rust) =E2=94= =82 Comparison (C) 0 - 10,000 =E2=94=82 176.88 =E2=94=82 92.93 =E2=94= =82 99.41 10,000 - 20,000 =E2=94=82 437.37 =E2=94=82 87.74 =E2=94= =82 98.55 20,000 - 30,000 =E2=94=82 677.49 =E2=94=82 76.24 =E2=94= =82 96.37 30,000 - 40,000 =E2=94=82 901.76 =E2=94=82 83.39 =E2=94= =82 96.73 40,000 - 50,000 =E2=94=82 1126.62 =E2=94=82 100.44 =E2=94= =82 94.57 50,000 - 60,000 =E2=94=82 1288.98 =E2=94=82 94.38 =E2=94= =82 96.64 60,000 - 70,000 =E2=94=82 1588.74 =E2=94=82 88.27 =E2=94= =82 96.36 70,000 - 80,000 =E2=94=82 1812.97 =E2=94=82 93.97 =E2=94= =82 91.24 80,000 - 90,000 =E2=94=82 2062.95 =E2=94=82 92.22 =E2=94= =82 102.01 90,000 - 100,000 =E2=94=82 2330.03 =E2=94=82 97.18 =E2=94= =82 100.31 It should be clear that the current Rust code becomes linearly slower per insertion as the number of calls to rb_next() per transaction increases. After this change, the time to find an ID number appears constant. (Technically it is not constant-time as both insertion and removal scan the entire bitmap. However, quick napkin math shows that scanning the entire bitmap with N=3D100k takes ~1.5=C2=B5s, which is neglib= le in a benchmark where the rountrip latency is 100=C2=B5s.) I've included a comparison to the C driver, which uses the same bitmap algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup"). This currently checks if the bitmap should be shrunk after every removal. One potential future change is introducing a shrinker to make this operation O(1), but based on the benchmark above this does not seem required at this time. Reviewed-by: Burak Emir Acked-by: Carlos Llamas Signed-off-by: Alice Ryhl --- drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-------= ---- 1 file changed, 47 insertions(+), 17 deletions(-) diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/pro= cess.rs index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740= cc0b1ec978afd 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,33 @@ 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(); + kernel::warn_on!(true); + return Err(EINVAL); + } + } + } + + 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 +834,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 +857,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 +925,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.52.0.460.gd25c4c69ec-goog