From nobody Sat Feb 7 18:16:03 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 C312E3385A2 for ; Tue, 21 Oct 2025 13:33:16 +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=1761053601; cv=none; b=jKKlpj869YTLp70H/fJLZmW9u8K57Fo9Pzb8HlcmBJ3gCEQr68nYQxdkSuqLcayGoQnO21Kae60JGTlC/MoWhSMOJDtB0lwJupKbmY0oh9gALVlft/w0IoYc6drptCweZADtcX2iV9Kq8PGHs4y6UspP+jifZtoCP6ezoLg3/84= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761053601; c=relaxed/simple; bh=y0H0co/pGG3mnaoefgv7jJBWHvIIQnYFtiVxMl2tyu0=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=kBmwJoQ1m92x3gnauH74uKWpPwtybDGtG4QkFSHf/qysKm9F1S0lr5C232nObAIXG0LvCwEp9L97iX4rwVSRhp5IXEowBR1KclLw09UrwxEMmPbDRoq/g64g4BHGO5MbKVUeeVJ0EnB8NOCzKoZNo1VhJMDY1pWv/WFhJzwOQL0= 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=u5JxU01q; 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="u5JxU01q" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-47114d373d5so53876285e9.1 for ; Tue, 21 Oct 2025 06:33:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761053594; x=1761658394; 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=YusvqkwYLWumMyM3OygPRZKhF9bgc4APSkdbz1xg4sY=; b=u5JxU01qQxZ96FXpXlTJhlS75taT+NXHliWBZxEjklSJN1fQ0oz7csPPOO6zGpXVb+ 153+5dHkGdOnPL5ccH+dOwzQlVTBl/2HY3eL9D2sztCre3d/ytjJYKCGzNZk40sCG6L9 A1vkQFysHIgD+cuwg4ebDMsc8wUnsM6G4eIc0186Gxzb6sIalfmuyyCX3i6JrGz6PPhk 8iJwl2iSWRE6rxf8mKhlDyznNdPkc+izrhK/m+LO9RHXNHVQKuUApNRYHBap3BX2nBQu i16Uxh5CZ9Xu32OjuLhvsqNI2aZAhw4ntT10QLrI2srN7BQIuHGGCxgzqc3KjaEeGccG nRqg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761053594; x=1761658394; 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=YusvqkwYLWumMyM3OygPRZKhF9bgc4APSkdbz1xg4sY=; b=oklLt3N0dZ+LVPnwH+87pNWH4Q90pKhxOpYh7iU16ygMKegcMxehzpx11GngvSUVxb ZN5RNpD8KqkehtvomhiVW9rZOuJ95nEUU2pxuv9YHK83sFF0SnXiYTo4CvvZy21fWo7y hvpE1ipjAx/+p2jncLawlg65vAfAP3NVLwSwrBI7enN4qcs3GSO7iMFWA/FBzh1mu0T6 d/c04OUFD70r1mR0NFpLq170he8ucdNUG2C4NVW3JBMU4HVQQtq82qvB3MmPa+z2PELg H8sb8DL5ujqmArO212cpiLMqVV9WnEtu1lrI4yDSHdw9/TQ9/dGg+tB4c5L8tmeeN0kk AV6A== X-Forwarded-Encrypted: i=1; AJvYcCUofQZseeROuepJi8rk56z5ssPibF7Oz28F7LZv3m9dRqKjOswvXHVEC67bhHmx6AiDbvZBHjplgIL6kt0=@vger.kernel.org X-Gm-Message-State: AOJu0Yz5CZIr29nvKk9UXUwHh7Tm/lVBPxPFqLeRwZ6KijFL2OYp/g6m LiuoAzrbIug7f2hYjolL02PQtlQL0N6tRGUPuzFxGwiTrcjoy0VVITtUwbpLMdMYn70fR4TEc0Y cchOefODZ/TxKNAN5bg== X-Google-Smtp-Source: AGHT+IGHAgnRN/r9kkpyIgetmO5A2D9wd+5oaqIK8kJ6Puo5wRwP5Luw9i0GPB6EuIZssrvr5wxVUNGHB3+wWF4= X-Received: from wmbz7.prod.google.com ([2002:a05:600c:c087:b0:45f:2306:167]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:468d:b0:45f:28d2:bd38 with SMTP id 5b1f17b1804b1-471178b14acmr121528965e9.18.1761053594119; Tue, 21 Oct 2025 06:33:14 -0700 (PDT) Date: Tue, 21 Oct 2025 13:32:43 +0000 In-Reply-To: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=2617; i=aliceryhl@google.com; h=from:subject:message-id; bh=y0H0co/pGG3mnaoefgv7jJBWHvIIQnYFtiVxMl2tyu0=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo94uX1NMWifM6CkoHtyygykkIM1ifibZQp3rD/ xyR7Hgs+wCJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPeLlwAKCRAEWL7uWMY5 RozgD/9XaOkDjMN8jCzn0IHApKOCYXGttdJuj7aYLxaz/Khss34iJS7KOd2qxRyPVUIM5wlmOcj mg2vmqlTwRxfBq/FfVWt3DCghKKjzdiBXyhDjpT4OteR0Qai99wAl//XjLolq+aTApMALai9vEN eLVb+YoikoehilUP0p6h/V0E2SdFyB6RMnYCNJX5RFRcAG0+GmlT+WzjRD+zIh7rWx/fRdns1yz ru2urA5bBSV1xnqxDsr1S8p3C2riKpnVy5nXtuUYibtYzREZcJn5/N+VMf1+Jx1wB9vN10vlBq3 +oHDOubkLPqu641tBIR0FAbX9mAE9HVdi/zq3Qc6jRhcbqohmgsIqkM/7hm6gdhQSpHu2KpVb6G MQlpW7nOEbVEKTEu/rl/YhHZImzrEzccGZtZbGy9hNRuljc6cKBPqd5HIrpfCysRw8b/NISJdKR Xi+B3rhADaEnyotWXyaB0WlzRVfse4SpSxDS3GMyZ5zPAcPQPGqjBeVZOR3HZDONv1LhL/aKy9J nI5IfG2G3T3KkcdkPIfXI99Y3PbecAqe1FFIz+QiiUJeQ2bb4KhaliyVNOu4cEeJVxqkBm7ue+z 7pnoHkrakBfWQrDqFYwHjkRK8l0QW6YUD5S0EVWon/HwAAw1N5ujZ37AuEhWRpQnV5t/qGyQ8Mn n40886pW/I9QwGw== X-Mailer: b4 0.14.2 Message-ID: <20251021-binder-bitmap-v2-1-e652d172c62b@google.com> Subject: [PATCH v2 1/5] rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_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. Acked-by: Danilo Krummrich Reviewed-by: Burak Emir Signed-off-by: Alice Ryhl --- rust/kernel/bitmap.rs | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index aa8fc7bf06fc99865ae755d8694e4bec3dc8e7f0..15fa23b45054b9272415fcc000e= 3e3b52c74d7c1 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -149,14 +149,14 @@ macro_rules! bitmap_assert_return { /// /// # Invariants /// -/// * `nbits` is `<=3D i32::MAX` and never changes. +/// * `nbits` is `<=3D MAX_LEN`. /// * if `nbits <=3D bindings::BITS_PER_LONG`, 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 @@ -226,10 +226,16 @@ 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 avoids allocating. + pub const NO_ALLOC_MAX_LEN: usize =3D BITS_PER_LONG; + /// 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 { @@ -238,11 +244,11 @@ pub fn new(nbits: usize, flags: Flags) -> Result { 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: `BITS_PER_LONG < 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. --=20 2.51.0.869.ge66316f041-goog From nobody Sat Feb 7 18:16:03 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 5B2E0334C00 for ; Tue, 21 Oct 2025 13:33:17 +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=1761053602; cv=none; b=HVJLmvdhK8RLuIcQFt/wq6Vc3Bdnc0X7N/eFre5vhcU6/8ll/PV0ydowFE4yaRTlH+UxM2bpXtpjAxnVNT/WDk0J8Jr6cFJLOCaLJR+++AeoreHiChUUGWkxTsneLdQkDEkIG8NQYj2+IONBeR5/DcWKB9a14W1KIboMztU80do= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761053602; c=relaxed/simple; bh=0XwGJ7KDobiszudqfhO29Z8TfiNZOYymA4jTezIL42U=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=SXRKSqmtNPIBGOpGv9HMRRkqMfXhkmAVgH6RJ8294018Pjn7lBxBAV7Nw4fsdGwNRUKjYp5n1FTwpTS9a3S8CP7DEYfv9SZCaFOp+mx9i8NLx5s8e7wWn/mhiupNr+v0P6xDCTXFErQhf1S/jkp9Nqe77GOuOSqCh8cQzGwwqSE= 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=RWVksaxu; 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="RWVksaxu" Received: by mail-ej1-f73.google.com with SMTP id a640c23a62f3a-b41c67edce5so245536266b.3 for ; Tue, 21 Oct 2025 06:33:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761053595; x=1761658395; 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=Q6129u1iYIYEuovLQaBoD4UN49cUgQbvN63SjRIKPAc=; b=RWVksaxuMDqj72Zr0ENwr/mCn92KnmNJcMuaSYtcE/AFcaTf58anW+Aq5pQfrm8TtY QJ3sNntwX5qo9j2dvZ3/4sGoYCt1fFzSOl6WtrpnXWq4m+5ecjea0xCHaUyZtFcZbxca 1PmoakPLyCId3iPZJ7ljJaAk8HXViOAOL8k6rXmCRg6RD5ZRRo7ic4sc8V1PwFjJ+e6k L7FYX5IehFgp0XsrUClsfiu6SRhqastBT/lLBGchm+GJ341NsDeafWd/00KBcar+PwHT YdQvVHO5EAbJ33RFR+h3hYgPqyDst/s/51ojjv5X5LV9y675VMkeTucPUxS+iVpDW4// ZcvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761053595; x=1761658395; 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=Q6129u1iYIYEuovLQaBoD4UN49cUgQbvN63SjRIKPAc=; b=iR0qiIKAnOdp+0cEXigvY0JCpn8VBrv2cqWSc7QWGqCUwfZdm3iz7CYrSSKvKVAqlN 68uykE1VImCVPEhrCOSVG34JN0deGNQ0w5o54I1vtgiaMiFQ0rfHeZIs248HtpOr34D8 EprJNpk3CzlxnNNIp6TVS3aVsXt24KqPwRvVfd57jKbGUnkQwoNC4RmPeNe+uYiZ3deB sgslRnyf457yBzhAh9X/7SXyuJZP/vPm1zk4erAalcETvy2CGmK4CvsOOOy/5e9c9nd+ f6b7DJ1TwypugTLvrTK6vBsQRMvOYm5/cJH2DarR3tHzNwU7BHNvqOfTlKsrgIGPWPlV DOAg== X-Forwarded-Encrypted: i=1; AJvYcCUsFd0rUKeJHztkFSUVefZAPtjGWkOHRcVdXEGejcwPaDbiIkpDO+l/LDqTJ3BPRK0LcFl6wuB1kvA2vRs=@vger.kernel.org X-Gm-Message-State: AOJu0YzE9bMprduvDrDW7ARYKzKEizpCHAWeJ02YYzKooR6sk78pGlmf ElO8R3vOeQaJ1OfGU+IdsV+obvQpxYxxB1mLl4/jPIk6BrlPB6M1ZngVYlrp22ZB2DuJZnjsVGB b5RHBK0jiXMsDNMbSpg== X-Google-Smtp-Source: AGHT+IHthMiXGy80jMaZ8NO+FgSnNWOqiBcpthOR/vfMJffUIA/kav+FOdeCi5No06nwwHWSqxBb+3FBKrB/lAU= X-Received: from ejbgv24.prod.google.com ([2002:a17:906:f118:b0:b48:5a27:695a]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a17:906:6a1e:b0:afe:b92b:28e9 with SMTP id a640c23a62f3a-b647423f370mr2051191966b.49.1761053595245; Tue, 21 Oct 2025 06:33:15 -0700 (PDT) Date: Tue, 21 Oct 2025 13:32:44 +0000 In-Reply-To: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1143; i=aliceryhl@google.com; h=from:subject:message-id; bh=0XwGJ7KDobiszudqfhO29Z8TfiNZOYymA4jTezIL42U=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo94uX6Ot6RnX1kq5rBoe1JUBm01b6sLrSgsNH1 eKsmbT+mcCJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPeLlwAKCRAEWL7uWMY5 RjfND/9CZXLAKgrrXYLqvMdfR8KG2+6kgkJSVz/EOx4eNESv/IO6/C27XHCmPinb9KlxDcdav18 aYSFcqBOpC46LSJbsy90DqSqte+m5GXPToraWHYXv82fGe4erjE3HsmuczbkSqj0NHbG4UZpaHh 69juPv50aIuU2SP2hJsIWsbVvv3NZOEb9/RCVRWs94HrTrX0CeqGBEKPQPpzC7fAE+EC8cCvn06 R6WaDVrVLumwC4szYX73+tymfucNpeYh6UkYKlYB6uPlnVFBExPuCnqGL+nZJ6pZ8/9AjUGwrRi 2LyQK9ykynZk943Gi3dIKDt2PgFk7HlXmu7Qd3ylp69IzCWe0jLeZRa+2yj+B2m2LR0lchGfBp6 JYVBwsoYEPsUZIGuiffHpPM9aPRghyptFWjLTV5OKlQdkEwqeELRm8WttpZTBavnbQajHZxdG7r ZGB1qWVLxoFGQ1HS6QlaffQcKJ+vABQUse+JfPnYrHHpkdhRw5qn3k55gn/atSodOjsUw+z1M/C 16DGa6f0WEbf5p3T0goHvB1JeDJUIuVx/QMA9ph2GgZxEbkHWHreI+q0/5mZq642VU0b+VKlcu1 lVyKhDshbxDEmhvsCdUcUcM1T30endAzOjHOcz+c+4GRbZmxo+pVlat/t6bzT50UlPa/PxqfuxD +OM1cn2CppoUvww== X-Mailer: b4 0.14.2 Message-ID: <20251021-binder-bitmap-v2-2-e652d172c62b@google.com> Subject: [PATCH v2 2/5] rust: bitmap: add BitmapVec::new_small() 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. Signed-off-by: Alice Ryhl Acked-by: Yury Norov (NVIDIA) Reviewed-by: Burak Emir --- rust/kernel/bitmap.rs | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index 15fa23b45054b9272415fcc000e3e3b52c74d7c1..4ffe9eb0f208a3d62016e00297f= 5a0800aa33336 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -232,6 +232,16 @@ impl BitmapVec { /// The maximum length that avoids allocating. pub const NO_ALLOC_MAX_LEN: usize =3D BITS_PER_LONG; =20 + /// Constructs a new [`BitmapVec`] without allocating. + #[inline] + pub fn new_small() -> 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.0.869.ge66316f041-goog From nobody Sat Feb 7 18:16:03 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 879843385B6 for ; Tue, 21 Oct 2025 13:33:20 +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=1761053604; cv=none; b=iz0bHjBxw66yffRHqnJeoEMCNMIRdEAsjHhkpXYoZnYhu17XPZum3Y8oGOIY1QED29Q06fLWVP1NUoSz47Hs5YFNz5Sz/2CipS46KRUeOame9L/727x+sjg2sbkEkc3yY2v4oQyHnmWpIfQHmXPGAYXEEBSrTGUCa75paUT3G14= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761053604; c=relaxed/simple; bh=Jb0vnnnhfxGrNucsxP5BNXkOEu1a4p48ToRxxUSpaQE=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Kl1vz0txuh5w843C5WN3ztzh4827zZMSWNNqxvHqUET4m22LAuroRFfUg1iVHvGundWN1AT4XKTuTk3ctnwT2Z/lWvjSk2QsYZncy+30c/qhjcRCr8w85Mlu3Wze8dNtmbz5xMhFovdPmfAUuYtqUtIjua1Iq+pvL/JGfmlGsPA= 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=FVDD/WG3; 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="FVDD/WG3" Received: by mail-ed1-f73.google.com with SMTP id 4fb4d7f45d1cf-63c4b757a76so5137133a12.2 for ; Tue, 21 Oct 2025 06:33:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761053596; x=1761658396; 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=fWdXzd7QdxlhFuF65XkScJdJM4lE4siYSCj2mHt57X8=; b=FVDD/WG3UVOYCxRlX6VYpRZLwtGSb8GfnQTC77vw7gAiOr0ZE928l4ukPvn2WiTTJQ cpgnqLpojx1CL5MIyhEryI0NUz7j3da4BrjF28f04bCXV7DWpjxMiEOOyp94i/Xsf6a7 Kb8yK+mWu4eLtLP8UQbH5DHEXrClSC/XwcJkme/I0RvRiCbIjDyxfIGbGj9Q1IcOmwru 5EcWYDysuFp/h6lHD/cek0QoPQ47QavNBWcqtngmDi8lwWP7iZva/MG3+U5u6ZNpoWt3 4EndkKiV652XUy0XJY27LHsXxyMNML4ldCTTlLNSqew7T+Kvm2GuGTh6rUQjqPidhydn 2ABQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761053596; x=1761658396; 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=fWdXzd7QdxlhFuF65XkScJdJM4lE4siYSCj2mHt57X8=; b=RFzj8pjdmWAtAX5CiDEIZZAch2Rp/2pdoE/Hz4JHucMlqKXq4FUFb8EYliY9QJfj+X D39UDKGYRTDE6EzerIPrY9+xhQ4e30A2Qq1LW6YQCf/ETKFhslRZCwdPFNvrFwIL+SZb HoPF/vAxhaIQ4gpsWG/j/BDGYq+E3VWA0woSBGcHaoGlhqpj13rXWlWWiSS1N+lQjbF9 brmAF0IPM4c9Bm1OFBmlFeSa39CnYr1m5RxhSIMe1n04iUE03HPwf6Q0z9SVAognnjG5 QKZOEa1Kyq6axGVYDI9rprDKdn2CdRAp+7tBDQRGHthZDuyexwsBtt1gaZSQhrCcjAS1 fFIg== X-Forwarded-Encrypted: i=1; AJvYcCXPHUW4UHd681asVAsODSzom8ZyrKY87z+AlH+jH6FwSOd1Xg/7fKtp5nK6lTyRgUrVVo1ufq4nl2DB2ek=@vger.kernel.org X-Gm-Message-State: AOJu0YwCZ4N16KLk1UPyDKzFErVMzKLjIsd5EqJpmMVU26hnGRq+GGs5 BwG4PEjNqcLH/3PBF7fcH1KYeIL19U9IhS5ULz9Js3wVUUFef0TWht9Bibe5dcbi+oRMQ2nDFuR PJhx5bRuXdTcthoHARA== X-Google-Smtp-Source: AGHT+IHnChQ6BjR2arpBtBJOLhvxyTqTIy9o0xi+8HCMJp18jJNKb80TyCIs9FpjfcNIp//pfUno9FHoyjIxuRY= X-Received: from edp13.prod.google.com ([2002:a05:6402:438d:b0:63b:fc78:ee0b]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6402:4304:b0:63b:efe5:f2b7 with SMTP id 4fb4d7f45d1cf-63c1f64fe10mr15861453a12.12.1761053596442; Tue, 21 Oct 2025 06:33:16 -0700 (PDT) Date: Tue, 21 Oct 2025 13:32:45 +0000 In-Reply-To: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1628; i=aliceryhl@google.com; h=from:subject:message-id; bh=Jb0vnnnhfxGrNucsxP5BNXkOEu1a4p48ToRxxUSpaQE=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo94uXf7oRZ5UX3A/HLX+AvAd8Ta5lw6EyeZra0 9Es5As7BCGJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPeLlwAKCRAEWL7uWMY5 RsKREACpPZ/o7balEXqMDR0XFVp4wneltDDlP1/DDR0s7ishyKE2qzshZyKITzWKIEHRd83NNq+ PwX0oPUmFBec6h/0bzBk+/2u0+pVQehFqJfRv8TRimsgNYx3OLTZFUzWOu+pCcpFx/sDOJhG2ob K1EjJJ1K1VPbfL+d3Bnhnr0wzXF+SzH817HhvWsbwCpK61Dks+/WEuEvh8xoVoJJiyJf2Cs1AB8 EEV3Oxo0GP9YtwiR6OrlolcvrXGgmO1QToJSEaM+mIkZIiQloF6KS8p4D45jSIGW5ixp18db1Pa zc5UsNgW9tFjorDHL2FUFJ/KSBx83EmRzxHGCGNa3XUqvzwtnPep5E2tTVWpCGyS/sMKOOsvSf5 opKtOJ1f/WBROoDzb4UZJkTK6XKztUCj7UyUMKPkwmTu27AbOTBjq2dllkdSG03tazlGqZZSCoj +we0byKKCcoIuYnbE+GV8B6FkfAl6m60sy9LuCqg5ckRCeSFdqft23hZgcdiPu/eFXIvmAOu6vE LjUFcHrzLO4r3zr8ru9VdNzNtvXxlvnYWE1QWwoWmYLWhduPNLRqvI4D7al3bDMhf6bkmP5j0oQ Mi5a+RKsPQvYajLMuL4LWuBzvsYYNfcmbYIy90Rc7eQkYgMa8WBcUIT09p+9qbTWJFIF/xllzvH exiRJ375cRmEEXg== X-Mailer: b4 0.14.2 Message-ID: <20251021-binder-bitmap-v2-3-e652d172c62b@google.com> Subject: [PATCH v2 3/5] 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 When creating the initial IdPool, Rust Binder simply wants the largest value that does not allocate. Having to handle allocating error failures that cannot happen is inconvenient, so make the constructor infallible by removing the size argument. Signed-off-by: Alice Ryhl Acked-by: Yury Norov (NVIDIA) Reviewed-by: Burak Emir --- rust/kernel/id_pool.rs | 20 +++++++++++--------- 1 file changed, 11 insertions(+), 9 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index a41a3404213ca92d53b14c80101afff6ac8c416e..126e57f34c3407cb1dab3169417= f01917e172dee 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -96,16 +96,11 @@ pub fn realloc(&self, flags: Flags) -> Result { =20 impl IdPool { /// Constructs a new [`IdPool`]. - /// - /// A capacity below [`BITS_PER_LONG`] is adjusted to - /// [`BITS_PER_LONG`]. - /// - /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h #[inline] - pub fn new(num_ids: usize, flags: Flags) -> Result { - let num_ids =3D core::cmp::max(num_ids, BITS_PER_LONG); - let map =3D BitmapVec::new(num_ids, flags)?; - Ok(Self { map }) + pub fn new() -> Self { + Self { + map: BitmapVec::new_small(), + } } =20 /// Returns how many IDs this pool can currently have. @@ -224,3 +219,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.0.869.ge66316f041-goog From nobody Sat Feb 7 18:16:03 2026 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 07D5822B8CB for ; Tue, 21 Oct 2025 13:33:21 +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=1761053606; cv=none; b=d6PwqP20CfY4csn8J56Fw/BFdys2C3+8wYafbuZCWYy0FTHMBKdAQ/sCtEgUN6hH3F1cigm0McznhoZHqmy65NYHwDDs1AmfTfIm4wNcCWaHcQOqhbB/udpFo2OjZBBf4Y4dps54PTd/RSR01dvpAM/0yfEzN5MhFc4iW8ffGnU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761053606; c=relaxed/simple; bh=qytksjZdLTISpFuZRyMOiiFkZgrPPHjKD+Mj5pS8yUg=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=UQYSzos6XA0zrGyzm65uDOEVqkN3xPd14VXBzn0R87hGNzUvQV1Ut6ujW3LMe0r6BhZ/mu01/j/xVZ9vsUqZg/vTpRP1jCW9n+RlyJHKTiCMfora0XmX7Ot6S15jdwl72tffBzmQNQFQaPJo0qRNLQMeO5sYcJdkVSLr4OTrQVM= 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=Bgyzk8Qp; 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="Bgyzk8Qp" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-4710d174c31so56784875e9.0 for ; Tue, 21 Oct 2025 06:33:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761053598; x=1761658398; 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=W7fDpabke6WhS46tT+T5FNys2Yr05OPqGRGg3toBdss=; b=Bgyzk8Qp4xj47h46EXJA25pSISKghqSGZO6GhqEKpYVQEcsqBdK/Ubix3wx9iu0lE5 GgTilxXMZ1p0Pa38nL6FmNFVf/XCwyTATY9f4kMwHzTO2U2G+pV+HkXrqcA4gu0xZ0S9 Q0ycWtwynqGQxATB9OtrYMtBRuqoWc46HC7IUTNY5bb0tuY8qIB+xSD0rgpC7i2jIUc4 86Y+afobBhnD2wozWllDXWo+I+IfVoln/sCDOxoO/0sP6uGomdmjvlhgrB+PlvdGHqhn 9tUqZIos9Opz5IiCwB973Fa+UgubKPaO4/+zSgU7x040jqGL4paMTOreyo4+TwLO2HTu WOSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761053598; x=1761658398; 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=W7fDpabke6WhS46tT+T5FNys2Yr05OPqGRGg3toBdss=; b=KrGm4UfP/GKXpG4Rxvqj2mjeqm/PRBkqmeA1Aq7FhbeD04tbNpToKB3vNXBu0GR5cy z/m29+vkQ8H7VcQok2yrqjbFMZ1GRO2JtqOQi5oelKSpjx0DiG/wLz2pbuWpnwNB2Vqu 0OT1mg5NL21eNDq6SrcB6nd4oIA2POBGVDW1NYsvUjR9YB9EKcHyUYKzYP0cZUVwyUq7 XB4IwhACzQOnNxRGJNtvoUu85rM3TwLSFjoc0ulAV+r7mHWNUPOTWMY1cM36MgCVGX06 zTdheG+uo+U8S0p6ofcpgIlqs2Mp91kDAVVu6nn6dghai5oNlzG/oYnsZY+U6KLQHe0J 97jw== X-Forwarded-Encrypted: i=1; AJvYcCUaZrR6c0ZnH7XrymChpwwb+BOVkTlWjT+Mddw00Suhtsl6JKF5TI8ROj9QVgzVlq62CGt+nwMx0P1nQBU=@vger.kernel.org X-Gm-Message-State: AOJu0YyXukWVfgx7hXQwpyNuc16U2H72IU2q4U+ZtBMT7DW8JQ7BZCfX w9xnp+lSS/w02B7u49GliT4gPycLJUe3MyfWHxonU5GgdEKm/PBTj3bvIfl7nxU5Rzu4hEXqUPC Enk6Dju5c98n6hFir4A== X-Google-Smtp-Source: AGHT+IHcH4JhLZmZhIV8KyVieSRjmkESC/bOub8ErG0T1qjHYU7NkdwZHbw5zRM/BUJluwKrwaIhdK6rgh5vdFU= X-Received: from wma6.prod.google.com ([2002:a05:600c:8906:b0:45c:d828:e351]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:4e0b:b0:46d:27b7:e7ff with SMTP id 5b1f17b1804b1-4711791f4e1mr119704175e9.36.1761053597714; Tue, 21 Oct 2025 06:33:17 -0700 (PDT) Date: Tue, 21 Oct 2025 13:32:46 +0000 In-Reply-To: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=2867; i=aliceryhl@google.com; h=from:subject:message-id; bh=qytksjZdLTISpFuZRyMOiiFkZgrPPHjKD+Mj5pS8yUg=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo94uXiyeb+mK6EdxYRp+Hcgh6FeizN0nxE/D5L mEzRRFiCEyJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPeLlwAKCRAEWL7uWMY5 RnDFD/91iGIfnnaWvFEPSgghqmXHMRCCEYUUtXrbWuW+fb6NiAuTxkp7WW0mYI2qzaFIxOA7pHw DoHwg5ejs0NfdiljayEuy98e5XozbobC88QBzU0cCEp7jPBN+bzQtR2Zp5fbL16JF7+jRvANoDb fqs+SsBT0KuMgBbgEamRsvc9V0DsbRws9TNxQGSYFHHyuZw7wO4lFeqw6zxpZU/gmkMIlT2ZbSe JOHEfSvl5kWfFm9+4EoULvC995qzbpkP505x5hvXdfzLpDoQdMKqhY4UOcZelGiV9YeYSkchsaK AoDLfwbfSKudmTAeCJL5gJMutgxbb2FcI6lPhhYFiMEWiX93E1IcKBWBKoXdOqab0Al1f7iKOCf PLOTkNGXj4G4EGWl679ve40KJz7KTWOubKOGZt7/sd9qPn4s5rDRxS/dcyZ22TfGaPYo0hH5Z3M Kphh8rJzhn5dX/OBYyuRjEZZbu0KnOOt4LrFteCxsN2TQtKjYdp5/yaBci42Wh8wtqzXsFkXkwn SDemlcFVTPBysMm58t72SaKywIr2E8urVfIM2mnsXg+2lvwjO1niu8LnjZ4x6zx88QKVcBkxVPI P4OAfTqbJFItDSsmrVJ2XL7UOlHX8B9NkTKKoLhd09yp2SI6jFykcBqm9F7nsz6uHiLqutODFfl HGKYPhMQhZ1n6LQ== X-Mailer: b4 0.14.2 Message-ID: <20251021-binder-bitmap-v2-4-e652d172c62b@google.com> Subject: [PATCH v2 4/5] 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. Signed-off-by: Alice Ryhl Reviewed-by: Burak Emir --- rust/kernel/id_pool.rs | 44 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 36 insertions(+), 8 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index 126e57f34c3407cb1dab3169417f01917e172dee..053ca417e8513fc33afc84c194d= 7899eafac8fec 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -199,18 +199,16 @@ 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 + pub fn find_unused_id(&mut self, offset: usize) -> Option= > { + Some(UnusedId { + id: self.map.next_zero_bit(offset)?, + pool: self, + }) } =20 /// Releases an ID. @@ -220,6 +218,36 @@ pub fn release_id(&mut self, id: usize) { } } =20 +/// Represents an unused id in an [`IdPool`]. +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. + 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. + pub fn as_u32(&self) -> u32 { + // CAST: The maximum possible value in an IdPool is i32::MAX. + self.id as u32 + } + + /// Acquire the unused id. + pub fn acquire(self) { + self.pool.map.set_bit(self.id); + } +} + impl Default for IdPool { #[inline] fn default() -> Self { --=20 2.51.0.869.ge66316f041-goog From nobody Sat Feb 7 18:16:03 2026 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 7E1DE2F39D0 for ; Tue, 21 Oct 2025 13:33:22 +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=1761053607; cv=none; b=Jj3NWvXznu6OIH0NQoKJN4hwP5NJJIzvJkVNM9dxOldit6zfNxDNti0cdd6Q9VL+LBdLZAqNyupYhYUqB3Sj+XG1RQyhWKf8z/rrcFJxM8kQvMFVHpCsWn7tWbVl61jenb/by4/mX8O10iK4uOvScihYiipJ6TnXpY+QaTBgQXY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761053607; c=relaxed/simple; bh=PW4fXPFs25L80fF70NuTLXm2bMNHsJLF6jbykyCi4q4=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=TmmvBMk3HMhDDzjNDDVdi5nebJwLCBjlWT+90p3L1w+toD12p9MjTF4voQL2uduvBlC/bbHBSTSa5M4FAN/1J8qjdfBNSghBf83XNHGxZMnA6w9aXF8gkKWRbR+YschIUZORsLkl+iY+772dZ7vpZ8sA91KjPja1Nb4lC81M6Y4= 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=kPzY1oWX; 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="kPzY1oWX" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-47496b3c1dcso7975965e9.3 for ; Tue, 21 Oct 2025 06:33:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761053599; x=1761658399; 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=rTDltL3AAi/RgZ5a/oTDLo3q33+wUkHf+1m9k8QIy7s=; b=kPzY1oWXI82SDyGSq54iSrA7W6TKFfjnH+GU5h5WZBfP5R1S8jN8AUs1vjU8LjyE7E WpKF93vGMAX/uFr6ykdIjKkLOxXsnus1j3qF5hAuBXC4VwFecpAo+11elnCg0sMOaP3l 77jGDRyoDqGLATdB3Wsbtyey4VGNtFuwagnJesrEI/1ZGLWWtXXS2/mfUGKp2Me3+ouz 25OjTJbcCPBui+Xxsbag8BAJ9JpSMIJK+iqKNuLwPsCjWOWe60redVRzFKFMOOxaYMQw Y7L4NeFi8MAPWO1sak/eon1IcujZqi4LJY/0s08e+079u+Vo/FMWM/+sWl9HOlF36AeZ C7mA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761053599; x=1761658399; 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=rTDltL3AAi/RgZ5a/oTDLo3q33+wUkHf+1m9k8QIy7s=; b=uv1QDVsdfbPs6TLE2FjxbF6+SvM4XmWOtlC8a8Ba1BIjo+PafBDaIYNhH5WM+HgSa8 RSlUzv4V8lf1L9jMM2HQGvi9qQ5cx71ZcvoBmlXckzJ3bPh3GTdNjQRkFyxCRYZlRojz nqwIltzV5gjsjaxMgrT2fTP3JRaZnC72/HoY0c2rxSma4c55uXoyqOPfb54X3sbqtz9w uMJ0Zr6qGFDWAR851X471pQLJCIXXYh0vcR9OTlJWM8Xjpwrdmpw14YQ1QqmflxHSeW3 Fw7V7s3jeuHJXKWdRUke7aCyD06qdr7pm/dcPRqRQv3k3aQBk1YRjmy2NZOBaHYwn0P6 eJNA== X-Forwarded-Encrypted: i=1; AJvYcCVA6WxmHExLQpn8NUbOElq3TbmhVxqFUQdR3QIdHJoZncm2hyzoQwt4M66hoGwQbWmdxbIm4EXqt9nANaA=@vger.kernel.org X-Gm-Message-State: AOJu0Yy1FYc8QpUpz8TpcEJpK3cJzKuOJNCmtGuv60XznBoTIvrvbHd/ dfNQbAgeWr1gIfbUp9Hh9HSnwma6Aw4efSGUaE8pLDCDeG2pFfbtd/At8aHHPZaL0okoEVCvkVD QzSanI6YfpVd6m4wQkA== X-Google-Smtp-Source: AGHT+IHbGsycRyExDTiNuYM7y3DxXLafgUs66DExEEUzWwCgEkrutWY1m8SaJ5WXpD9pbMyB1vK4A7vDVsl5Fdo= X-Received: from wmbhc8.prod.google.com ([2002:a05:600c:8708:b0:46e:49da:cb09]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:310e:b0:471:14f5:1268 with SMTP id 5b1f17b1804b1-47117907a77mr130498745e9.25.1761053598959; Tue, 21 Oct 2025 06:33:18 -0700 (PDT) Date: Tue, 21 Oct 2025 13:32:47 +0000 In-Reply-To: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251021-binder-bitmap-v2-0-e652d172c62b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=6173; i=aliceryhl@google.com; h=from:subject:message-id; bh=PW4fXPFs25L80fF70NuTLXm2bMNHsJLF6jbykyCi4q4=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo94uXSvZrdNt269KCZtQ1EMRnOYj4jE10+cR1a rnYxaaJb2GJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPeLlwAKCRAEWL7uWMY5 RkUHD/90F8j+1nVwohT77GrcF5m7/v0ucDFj5WnQJp+i4y8p8qPO3sjbQuzHH+B8SHCXGdj5QeP QikErE2XXj3V/56RzL9Iohq0dY8bvdeNC3QejLmJXafAi2rninG5VqWCls+1EjRLDlmg7FyFYld 8pq/m0VzWnKC4+dbQzCarEN0mQ3//GL16rrH7d7Cx3+5mtZxAfbiM1S6thAahHgz1c42ZeuL1j1 JLDoH+lXrqXtfjqw7JbDhUO5T/veK7tF265P0osBHmQug/0mYLEhecptO5Jfkp4+Nfu3UWomKi9 0+85suAvZAiPofmvD9MXSnNAlRT0eV8INncE+BFZJzc36uobNdUuUWXt13gtacLA6MVhUIKmBRH CnBSPNrspYOLiKJg+y0sbKtG+WTZ7e+dMjBdEQKLDfdnVzM1baR9xvxScab5+QtTDPYswRCTHCY rz+Aw5SDfiLIRttPybmaaGXCyZvcSNK0aHTjNXoQEeQdgQWkzVj0l+9vfy0diPRg5dTSGfKaZj4 f8soJN1hgvxAkgOLjFHCrYvOJR8vEnM4flZ5tSqgQY5SbjjDtAxhlnw6vxb8CnUiAh4BK56yxvk GWU/+VNchCf2rYVZqB37ZVxGjUWSBZo2LObWxUaNvRR35tFMOcuUuF6bJqwdOATW6lPFMJkBwZm m33GhNU8VhenUjg== X-Mailer: b4 0.14.2 Message-ID: <20251021-binder-bitmap-v2-5-e652d172c62b@google.com> Subject: [PATCH v2 5/5] 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. Signed-off-by: Alice Ryhl Reviewed-by: Burak Emir --- 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.0.869.ge66316f041-goog