From nobody Sat Feb 7 18:21:28 2026 Received: from mail-wr1-f74.google.com (mail-wr1-f74.google.com [209.85.221.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CB1242DECC2 for ; Tue, 28 Oct 2025 10:55:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648929; cv=none; b=YmX79TfgGMxDf3YWROZT9vjWebwblOH/VWS8GX4WKbibhokrzIJ7VEGB3uvee4PCMvAD1GU6/zl+pwBGW52BG8Fd+vk2V55DUOvV/ttSmb5lwAb9tFz7vKJwua6s7BcsGoMdJ0WaQXdpCITrUzqQQtJefA9tMHMv/JkAmZIuXxw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648929; c=relaxed/simple; bh=l1yiCuIrEHrN9qTyEeGJb8gDUsEUM5CWLl0VkXTvO/Q=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=bzA9MBWwQoLzDJGVOYcnsSfnLGF5ysuQxkNWMjBjhEfKuG4ym7+cn+604z30gvHJNzB2pUf0Ii3uX5nSjGaGIr9aFNBlhOse5gfq44xtOelaCDOlPAbdfeyltnvP5Jz67EE0Y9lz+G0Fr3vYMikR6nAukSxe0leSg/KXowuXnZs= 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=nZU7Jcux; arc=none smtp.client-ip=209.85.221.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="nZU7Jcux" Received: by mail-wr1-f74.google.com with SMTP id ffacd0b85a97d-4298da9effcso3639138f8f.2 for ; Tue, 28 Oct 2025 03:55:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761648926; x=1762253726; 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=XkfuEZJAJLwiOPcOM5KW0XWm5zAGxFJfsgxlppUu9Ew=; b=nZU7Jcux1HaH4h7UU3db1qHoHt/j3c6qg/Q9Wnbf91H+MlabiZnlCP9h9bzC1Vsf4f ISUUss6vm30X0CdVvzx1wPDkXF4BSCJhMWb9j2g5q9ZCQv5UFORdeyc8DabsM27Pc2MH PYI/j97VIWDe5pmchNBHG8qPciTeS3d1AYyJpn9r+/3FVtevwiMMt6XdD1sKL3cB3/lr YMiawcYemJAntA/oSZvuCgKDryhyeqXQPG7+BEih5CNtv9rznUD9nXF3z0dwVe1EXGfg qgUOGosqhPRIdDmB0fi1MBbp+aDSwyRr783oIBNmKsG5X0oL7KFnWS9hVVcUjpxfdO1l ODzA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761648926; x=1762253726; 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=XkfuEZJAJLwiOPcOM5KW0XWm5zAGxFJfsgxlppUu9Ew=; b=eAvlJxGWrrv3EvtbbOWH0VOpudN1lvl1iPN9n3dry9As73Z3EBNQYgdOMfKgcIW4RT Zlp/2u2yrCXWP+6USMllJCnii1vjA00fdWaOGh/qql2Zkb/63pCx9VOSzXXojUMkJ6VO e5bCg0TwN8ljpQ3YnoU/2NVut/Iu2gbzGLdJ/vldUUHC0vh7fwgbj5TTG31UXM3RX8X1 K3ggQfT8sAcbD+3PbMXVqx8mM42ldAQixA7CSJ8V9R1Ts0ulq7hJ4jQ+75bpTNGwFSsW qD7kClKBGG6bzk/TyE+5uAOSRR5W2f591C1nyVx0cJhOxFj4A93WN1/X5n6zZe6AR6yy 5ryA== X-Forwarded-Encrypted: i=1; AJvYcCVbBFydEXWaqRX/HJF6fvC6S6ME/pDusFeXRIpjlteob2eHmHc/CE2uXSEKTXIsFFUBOUMLqd+aQ1tQOxU=@vger.kernel.org X-Gm-Message-State: AOJu0YwbsyILqo07t24BhgMHAWfR+Tg3jJOoPdJqdwK/kP3m0PRA8eg6 jbxDVNd5haldin+e2cFUzUS8RxdwN7fXmJm7rMHMgLPPC3o6cX1PjckVVoZVs/K9XJBD7BfyuCm 346Qa8s85MseTTyt1WA== X-Google-Smtp-Source: AGHT+IG6lAR1Exg+ZJ2zeUf3ihqt8puTw2kX4ttNtep8dx0xRWXe8BU2dAVTBuGkGoyamUr15I7XwqhwKq38BhA= X-Received: from wmbjo7.prod.google.com ([2002:a05:600c:6b47:b0:46e:2f78:5910]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6000:611:b0:426:ff8f:a0a3 with SMTP id ffacd0b85a97d-429a7e7320dmr2182375f8f.34.1761648926292; Tue, 28 Oct 2025 03:55:26 -0700 (PDT) Date: Tue, 28 Oct 2025 10:55:14 +0000 In-Reply-To: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251028-binder-bitmap-v3-0-32822d4b3207@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=l1yiCuIrEHrN9qTyEeGJb8gDUsEUM5CWLl0VkXTvO/Q=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpAKEbulObCzB8CJqtGdcXGSog2T3jFiGI7DMrh LYWsDttYl2JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaQChGwAKCRAEWL7uWMY5 Rq9MEACayJs55q3EtpvYIg6w0qS+F2kplLuZ0uQ7Qeyl1olMJ/GnBjf4QMiXXQFmg3lWn7JsbJZ tO6UuQC4wMLPRoZvv7TNjWYuANM1nVBX8MZKaSFRVOzPt3OmOdpkC6nnnyVg+Lj8xrN1alK46J/ jr2l3rJzEND+9LDWrtS74micAoggZVG4hiNA99Ln1dhHsfHvicJ7KYV/CDLkKuEsS+AOa0O+5P7 yrMSJjtrNWt7CleJVInCJOPMqzVLHs0IIAz/tvQNDvG/0n2pP+sVOaahCGoIGw2bfC+48NZHi3Q wcuxMFlBO4AZTr9L8GANjs/EN171RGxhXbR1KPSXkAoCF2afTCDwrI6Dkv/1cij+JbbwVgoq/cM VA/ByzSxbm3Fs4yfKB+SDhRoiOlgp6QhBC5Fz9frhh1I2UAIQrG95xmUemRM9kZwSJxkEcQn37P pEF8EJxaCYDumGGH9bxWyL5+f2FFyiTc4WRdgvaasqgO8hgU8jkmxZ3k+XaqY8TKssbizlE3Pjt Nys9/u9floX1lB/rAK+R9JVg4VCir5biNws7dxRhS+Q1SXnjTLshiNyciSZzjrYglcKv+ySyAnH lh+iycc6RhfeMJkLnxeWlfzXXVeAXu57/eKt9pR5T9mHXKRQo8TCvpsC0y0mlHh5BM4xGXpxqtZ ejAvjyBCI5e48mA== X-Mailer: b4 0.14.2 Message-ID: <20251028-binder-bitmap-v3-1-32822d4b3207@google.com> Subject: [PATCH v3 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.1.838.g19442a804e-goog From nobody Sat Feb 7 18:21:28 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 18F003090CD for ; Tue, 28 Oct 2025 10:55:28 +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=1761648930; cv=none; b=OB9M810oKkgMIol1WlY8DEi8xzqEvSjlmj2s1jq7jxy6KbmK4YfKF7U26SG36STHMfQYDBUmo0vVFxubhQlP52Lmjb5XnVCTeiozJHxfSzeWfdY0wEVv5FdpXz2E3lBxQ9uEe5vqkxDx9klaGmkT7XVgwe/p0SuTLMQsgmm6lT8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648930; c=relaxed/simple; bh=u5cQmrhUMazV/NbgrGa0POvpnkdiyA3r9buDRqet4wA=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=fZCnyQy7BTkqIV/TPGabE6mn7yeTNOTyPdm+TJapgL9T4O+e2LRFAULYf84LAZAxmK5zqweEu6dnRKsgWyevaMSOCfV8QN5AS671+dux/I9zAUmIpqrP5YyHkE1iGKl/FxV7nyYSryYdE7r9MUMDIohLiK6LFLI2mnY8X9Ug+UM= 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=n+5owXJB; 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="n+5owXJB" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-47111dc7c5dso34103325e9.0 for ; Tue, 28 Oct 2025 03:55:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761648927; x=1762253727; 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=kA4eaFrdLr1JSkUKeDkNkT7+AEWbhQjt26vQGgnU0WU=; b=n+5owXJBrA6OBuR58/vANOK5DUWs5eqhheUaAUbxhoHlI06A0r6kazitHzh8HKVIv4 Gaq9wc4apDpeE49kUj4OL5flb43Beqr6iGVvnwBQAb/fbvtLqsL1g6FbxAeGqHliRRz5 2vQ6LTKJI6W8RfkShShThdSlCuHmIzngoyIdXv8f9TQBbqtyO6aKLqRC8+phOVxnZpU6 g3GdPgigi5t74J0eHK4d7d03gF0Y2SqgHSq5187JAnuG0sIlsftSTZ5Y/WNssUjiJ06c U6pZu88JCI7thl6idwTBr6aEaPwy2oNKwhQSqsI6J45ikYz6xoBOTRP70gS+M650rjSC 0zzw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761648927; x=1762253727; 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=kA4eaFrdLr1JSkUKeDkNkT7+AEWbhQjt26vQGgnU0WU=; b=eh0PX5LBvKrYJTqlwj/5fxUBWX46XEPi9qHJuT+jk8jiFsHvlr7VAmNIwqZSxjXcgd dGe9VBLhHdPPOdwC3xiabeRyyhJFsPUzVCrfgMRGHCW6/lm6O/4angKAJVVbR6Ro71WZ p78VFAagty8wN8iipMf8LKpm7XnDbu75502AKSGsmBuiv9ENvUAFkHKR4b9drW1pubMw TdJKH4kBanoLhfIOvoPLwHgKZhkCkaBxT3erPAfuCY88dzS6sF+gVw5rafuGljDxafwQ tUE15vEta1bu0HKFy6iWsc3mD83OLVcZjLPeU6QTXVJqiKO4Ckl3/FT72A+8jzyF3ELf 7AQg== X-Forwarded-Encrypted: i=1; AJvYcCXKna/PzCVvGTnEVqX9r4gRuS6m8LgH5oqDwPrj751zJx3w80ngI7IcpvK8bVrytZ4nWN0WVwQkUTYfwVY=@vger.kernel.org X-Gm-Message-State: AOJu0Yx65SAKsldBof5Y6QgNyAEFmJlGbJ38d1CXYt44lguuAjDtDkmW S4ysyPyr6Rw9dQOvin9+17hpQbcJ1olRiw/TwMV1YPVz0dNtWQ88NhsPLz8Phjvds+xhNFx6E8d sJ0PjQMFStDihS6s3EA== X-Google-Smtp-Source: AGHT+IFRbJ1tH44lIpEv23gIpvmhBMuxiE+JbhC8TVzF6WmLYlq4uRK7OPBTmIpSxquYR3bw2fwC37MlLZWhza8= X-Received: from wmmu18.prod.google.com ([2002:a05:600c:d2:b0:475:d8ac:bbb0]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:5246:b0:46e:6339:79c5 with SMTP id 5b1f17b1804b1-4771812e415mr29064065e9.5.1761648927520; Tue, 28 Oct 2025 03:55:27 -0700 (PDT) Date: Tue, 28 Oct 2025 10:55:15 +0000 In-Reply-To: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=1240; i=aliceryhl@google.com; h=from:subject:message-id; bh=u5cQmrhUMazV/NbgrGa0POvpnkdiyA3r9buDRqet4wA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpAKEb/ewdk1lpt9r1xeOREyfL4xflpbXO9tvCh oxRUEcrfsGJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaQChGwAKCRAEWL7uWMY5 RmPfEACfpfOQOfGSTuquxnxa9aaTAoYP42qpAtVpDHCibufjxtFsccqhbnZ0HotxsAXILZqYHLN mvdg7QyxmXMFPed8pdiEZp3PnpCKNWMWHlWGl2mG02bwq3xxj3Z7lQru1D1Ik273TgBsKw/6Z7+ R3Wv7Z67yLe8AtLMo+/GBz2oCm4JHasM/Gfj9Nec/N0/8Ay3eTed5Xv9EIdiS/WaPFrvDJQ26Rm pV2fcA4dWtI+J8Kr/wkAGB5baWqQ1D/hxKbp+0mC3DnNht7YLxhMf1pyN2hpjklzSOeXcuZGVhk btYbncIoeLeknvtsMG2aPml8ZsYt7WPC8qk8dC551ma7cIQ4/Pk7PVQ2Ikv6OgRaPz4Tdg9AhFv T3jloqyCq2qlhpw6pIMlvAeCuoCHjPrSdBo5AKfyhXQ+bWk6ITDspAO5zBFr39cpf04NKHV9Y8X nKWlkbAaIQmvoUrXsqcttKRbAJirN6KCVtPYdT/ARSWBAIQyXM5X/g3lp1eTMY4baZhns8kWos9 zs6fXKSMS6RMSCgifnXqgm7m8I/XoX1kdAVh8srSxTAl4MiykIbpLVZZsUUylxjBprpQNug0z5D AWlrZ3wqaSk4kQJqjqtYLoxViFKm9fda2ydPVhDOjdd5v+eHGm0a73O5HXQ4aLYDemYGtwsCNz3 l25Y+iqrYTgIGwA== X-Mailer: b4 0.14.2 Message-ID: <20251028-binder-bitmap-v3-2-32822d4b3207@google.com> Subject: [PATCH v3 2/5] 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 Signed-off-by: Alice Ryhl Reviewed-by: Danilo Krummrich --- rust/kernel/bitmap.rs | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index 15fa23b45054b9272415fcc000e3e3b52c74d7c1..f385a539a90ba87a7b9f6d686e1= 50e95e358bbef 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 + /// Construct a longest possible inline [`BitmapVec`]. + #[inline] + pub fn new_inline() -> Self { + // INVARIANT: `nbits <=3D NO_ALLOC_MAX_LEN`, so an inline bitmap i= s the right repr. + BitmapVec { + repr: BitmapRepr { bitmap: 0 }, + nbits: BitmapVec::NO_ALLOC_MAX_LEN, + } + } + /// Constructs a new [`BitmapVec`]. /// /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allo= cated. This --=20 2.51.1.838.g19442a804e-goog From nobody Sat Feb 7 18:21:28 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 4A160309DDB for ; Tue, 28 Oct 2025 10:55:30 +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=1761648932; cv=none; b=HWRTg++FWK6kqVrTizNFmQRmuRFDZBXQNvJSQ2+krfCUx9UWc7DqOgo85Ded3buP35k4Welc+ObFs3wnBFQEXOzEUTVNVUfg0o2UKoCdYJ85XW+7bPfMAv6hlWJY03+ycBY1W9N+4YbUro54GRda5ghkhlnT8nXzMufslU/Hn30= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648932; c=relaxed/simple; bh=wVEdg6FeeLwB/hit6gnmFv1v8wpEUtieEvxq37cRo8o=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=owBrOl4zMbVnyt9I/19cuNuj5mnX2Z93fwu29Cds+3YBF4rRTyqXg4K6AM2AS80hgu2O9vdGus+G4bLGFgU9JW3gowLKaIllYlmjWkbdkkcQZT1kdgtGGi7sAy7l4+t0DMXD6faL4HFP1puSknn+PUy7I72K7dRSgcNlC9kxtJI= 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=e/2rAbIS; 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="e/2rAbIS" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-47113dfdd20so21383475e9.1 for ; Tue, 28 Oct 2025 03:55:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761648928; x=1762253728; 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=oyfRCk0EaJ1XWxrdb6W14tsx1dzvf/EiCVJtPUF+24A=; b=e/2rAbISoueCNyncAYsjvUGUERadFTXGWeic5xu2MQpSmXShYjDuDb4HeNi7d8OlTm iUw6HFeYoAsv8CT35wrAf+VrVc90yDKrT6/Gnjso7l1/s9D6WPLPFuSHMjHa/8rdND0r 5nFaBq8IyPQYuYZEVDSo3e1jxr3zEoOUvw6zl53FyexrJ9EokEnVFmU7LwRn/0H6Q4gR AM+2EZNvQsKWhr1fmHq271m25m1BP8pK7JN1Ipy+pze9Kgg6OXzyWpFXzW9O+/6hDkft pvuhZ+08R4QaYeLf7eYRot2TIATAU2eoe6p/3ElnosC9Pb9JWROcwLdzc/3WERQoyHp2 Ktbw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761648928; x=1762253728; 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=oyfRCk0EaJ1XWxrdb6W14tsx1dzvf/EiCVJtPUF+24A=; b=XOnsTiUq6/rhbCyzN8wZ5gENwL30/ptmuFiClVJwA7wXQK18WBpZfI2kaqCa3UPiQa DdWWKwBkb0AUNUeIwDypK94+mf8csOl9GJMqrIdtuhyD93bHhMvtgKzi9j3xD786Ymij Rn+Cm+SDMTMJBjLYXXZtpOEL+jn58OWBJcMYz6wapUoUQySh8Do6OYTULglmaKtMYEVd q2E5MvjjpOyQPDn8i/SUmvxVKHZe00ITu6CJyq7NZZr6Nb0TRqVxkTCEWOgo3evBJbs4 6Ox07+5TqWdnh1xTAEiqCqO5nb7XluLK4plB+p1i3QbHNPVBwh6xAcBal3BdQuKVCwze eWsA== X-Forwarded-Encrypted: i=1; AJvYcCVYd4Ri0RCuUl1bf5fS08LiIb1uObv8eBSAKEa9+kEEqwTEBUjgww9ALGG+GLR8H0GuLXEHPZFvJ990dMA=@vger.kernel.org X-Gm-Message-State: AOJu0YwvpXGkM4jx9r6+vgyAYWjIhpQCGrkHYrs34DUYZIXmQQC2Mbl/ uwNZmJtdGVfMj9zPCfQWDE0T9lkQvI8emVlUezLHhdsPkXmvmwDoWGoLaeFtazTuhFTnQV9x6aB P8KdbJkS65oQW0wBXAw== X-Google-Smtp-Source: AGHT+IGSToYHrvAtmCCKH93eCaQBK/1hSpp4oS1FPlqIAdAPq0AxsXI/5FVGw0BVLFvZb8SiQ189jAiQcfnEh0k= X-Received: from wmgg16.prod.google.com ([2002:a05:600d:10:b0:475:de83:8f42]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:8411:b0:471:7a:791a with SMTP id 5b1f17b1804b1-47717df6c67mr23657245e9.7.1761648928631; Tue, 28 Oct 2025 03:55:28 -0700 (PDT) Date: Tue, 28 Oct 2025 10:55:16 +0000 In-Reply-To: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=3606; i=aliceryhl@google.com; h=from:subject:message-id; bh=wVEdg6FeeLwB/hit6gnmFv1v8wpEUtieEvxq37cRo8o=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpAKEbKP4cXyDZC8ed7UCVTDO0DjnqjfM+D/73U EKXjp0ZWzyJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaQChGwAKCRAEWL7uWMY5 Rgg7EAC2hTlkGBo1Y8m7lyzJFdkLs6KX4tn7ZepP4Za9Yg30LJqD224EVERnchMH5puZk5xbi/l ZwVlNBGjsgd1h/PN22sSB8Q7VecMHuCGNKaVSFJRnJlyxnVCaNlxD5CIKdkmvhGa/b3g640tgah 0Dl1GclvcuEzHCgarlqF3Dv058D6PwNQCOGEzyuu+OzwVDcIuH8p9mXqutotMmpKfBG5VdBXVv9 LFrKptsZQ+pVjChYogKn8ZhknaF6azv1gjXz0P0xnOkf/XTP911Frn7K2yiTB3yypZBDSzmgWNk XYoVR+mkdsOs9r3gkfgSzDnbeAysn44h5iIHamsr9CZJkDtD28flpbPm9ie8BSDjtL2Fqd7a5e8 E28YSsFA+m3uDY2UaMcwvtn8hZPLU7kjYw9YgcwmuzlgHq35v/avn443xSiKUnJP64/SOMcj/2A dMubIs1EA4glbJ/tcavyppxBOOUCMJRPy9PNEMVuRiW/2BVzOFq6clIosWacZaT7osA6BEi9e2C +RHZbLb34liEJTLQKPVaGoyP4xnEXswpytNlgOCz9mSxqbFwDJpb0Ogi4hmWwYrMhZ6Te55oUUQ 1y78SIu8qjEivncLWfkefxFVl1v7EdBR5szqCcMNEeuN/Pz793Q66vJ+RlqHKxW4LAbeItmywGK rMOExOitiYOo7Nw== X-Mailer: b4 0.14.2 Message-ID: <20251028-binder-bitmap-v3-3-32822d4b3207@google.com> Subject: [PATCH v3 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 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 Signed-off-by: Alice Ryhl Reviewed-by: Danilo Krummrich --- rust/kernel/id_pool.rs | 46 ++++++++++++++++++---------------------------- 1 file changed, 18 insertions(+), 28 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index a41a3404213ca92d53b14c80101afff6ac8c416e..d53628a357ed84a6e00ef9dfd03= a75e85a87532c 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -28,19 +28,21 @@ /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; /// use kernel::id_pool::IdPool; /// -/// let mut pool =3D IdPool::new(64, GFP_KERNEL)?; -/// for i in 0..64 { +/// let mut pool =3D IdPool::new(); +/// let cap =3D pool.capacity(); +/// +/// for i in 0..cap { /// assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?); /// } /// -/// pool.release_id(23); -/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?); +/// pool.release_id(5); +/// assert_eq!(5, pool.acquire_next_id(0).ok_or(ENOSPC)?); /// /// assert_eq!(None, pool.acquire_next_id(0)); // 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.acquire_next_id(0), Some(cap)); /// # Ok::<(), Error>(()) /// ``` /// @@ -96,16 +98,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_inline(), + } } =20 /// Returns how many IDs this pool can currently have. @@ -119,20 +116,6 @@ pub fn capacity(&self) -> usize { /// The capacity of an [`IdPool`] cannot be shrunk below [`BITS_PER_LO= NG`]. /// /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h - /// - /// # Examples - /// - /// ``` - /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; - /// use kernel::id_pool::{ReallocRequest, IdPool}; - /// - /// 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); - /// # Ok::<(), AllocError>(()) - /// ``` #[inline] pub fn shrink_request(&self) -> Option { let cap =3D self.capacity(); @@ -224,3 +207,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.1.838.g19442a804e-goog From nobody Sat Feb 7 18:21:28 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 6CC6B30B519 for ; Tue, 28 Oct 2025 10:55:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648933; cv=none; b=W/zNrz6HRD+7fID52ITsxJYPjOberpC94mV1G24yIi2Y00MybgZs7x+rcFtKbthDVBd1Iw46SyCuH1o9sKFWUYEY15KIgr7rS3ep+kl/Qq2f3k58ARHmJbSdcSn9Pn7YZyV8Sit7/qCxyvp+iJjBxzzZshqH4g+2qGI9QaLaAx0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648933; c=relaxed/simple; bh=mKyR9/h7rlG7KiZjyzS5QxeqgESuhech2GJoN8dGoVw=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Ajir69zRjUu2XTlmOJIDSu3wnWvV3jwINaQ1kiMFj8TuiSdw32LCKIf++Hi1Ld5MwZjSsGdjIlRSu9sMxVANJvRVVNzFCW14jRK8XA1edqIBc8Q8t7S8AZ9lNjxC+2Z6m2gPltc69PwRuNibOwiJloB97qeRCot4/RuX56rQJws= 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=Ne7pXCTC; 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="Ne7pXCTC" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-475dabb63f2so13634395e9.3 for ; Tue, 28 Oct 2025 03:55:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761648930; x=1762253730; 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=n9exySn0FhaBtD6aPkK902goSNi5LE/rsvaCxJ4AAlk=; b=Ne7pXCTC+OR64XGqUhcTwqvuEsmCkZ7XBoqJSd8vh3XY9Qwu54NMXPRvrdxiXshGE0 UIXHflQPBz47qZ6sDWzHwhguswqP6F43ThjMEtDgA1hl0RDG9YJMKDLFXGHiFUUPmtlx 1JWw+BdPMJkKOK82W8kP6HiEBs1F0o5STCAm17HFJZgeuCcC1rtqxHLrjLhIb7k4O0Ji TR7igLFV84CtrtFY/e3nkMHqqd9OxbifnaePHkIhJabq21CA/rDMewBeTPu1PERjs0/2 WnjjcP9bUS+5RvPJW6h9h545PSR6Ec3cWuFMjkn+6BhYJi2Yp4xstYaOUDlPOpNsfCMt uJag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761648930; x=1762253730; 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=n9exySn0FhaBtD6aPkK902goSNi5LE/rsvaCxJ4AAlk=; b=v2XznbmDnhACjEjGiyLI80iCc4v5fZha1WwAZbFqF+vi5J6ru+gA1ASCV7OjFqE3zU H4FxgheW+XFvNCsT6hLjQ7vWsDPkgqExhXdwvmWdLM67OKIF/WkmwdPYlZbgLqgy75lW FFU0mc+01LWNbp5QID0AkQ3VBLg3d2yotYuTAD7ZKqZfYlF5ced13rm95jAlHXcdMrF/ vi1FgPkiecoKz7ZlyaoScCsTdJ9QkZQTSkQkcQ4/TkGqa3WOhQmsMyuMTAu6QvkmE4D3 LcOttc2fQUsFDYXCug/Pyj9WuugTLQmMM3Z5s2GN+inxzCmr0nSL+mfyJn2StzQBw0IH qgYQ== X-Forwarded-Encrypted: i=1; AJvYcCXmOUu76Vpg9EnogihIUAhhF6wQjUJtMXZ4ydxV9NGe2bXu2CDXuz1as1wHBqCcwQ2zmVe5/nV8ltDA2pM=@vger.kernel.org X-Gm-Message-State: AOJu0Yw7ZrDJp2F5ma4tSezNSUuF2HBMIx3ogLXNRrgNQA1tc22PIVyl yGFc1NFWxycODy48UGnSxZulYi/WuFTbBglyhvtNEb23M10JsVYk5RT58oNVTZK/NZo/RJfEqG7 /DXB7ggglgtT8pPM1EA== X-Google-Smtp-Source: AGHT+IGBGsazRL54FZwV9R3EStOOg/ha2XSfRRiPYubsZPxrgejlBZWmFz3G/PdUeaNC1qLhaOWWWtWRy9V8zww= X-Received: from wmbiv8.prod.google.com ([2002:a05:600c:5488:b0:477:1186:dfaf]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:4e4b:b0:471:13fc:e356 with SMTP id 5b1f17b1804b1-47717def78cmr26198225e9.3.1761648929762; Tue, 28 Oct 2025 03:55:29 -0700 (PDT) Date: Tue, 28 Oct 2025 10:55:17 +0000 In-Reply-To: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4579; i=aliceryhl@google.com; h=from:subject:message-id; bh=mKyR9/h7rlG7KiZjyzS5QxeqgESuhech2GJoN8dGoVw=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpAKEbI64GJwTDLy8qUysgob6rTWmZt9rhINssF 1/Vgg0grAiJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaQChGwAKCRAEWL7uWMY5 RvOlEACtUDd/QdwUS7owdfpd9PpxRihEgoSppAXrCHcE6pkuyXny15p5Jc4QorveoZekgK1vZdO 1pjtSw0HSRKe9oBndWd0TsQrEeoqQuYIh1dom6wN1Vq3sEUe2mNrd5lmBbijq+6V8KssLvgpT99 cAaayRaS78ZGb9vP+dIuZSZrJ7QQyqYKS0EPkFDoCGAk7641y5nRnmFDX7EUMtuUvqIVNjWA55b Q9ReryCdM0nzG63+w4sF1fOxp3RBwSj8/bvvDxbrWGoElLP6N3l236h4Xhb/aET05lBBmjZu+CU L/TJexmt0Qz2mlDaWuG2FRO76YNwopKZUWCbOxC8cOPzK9bTdas/ydqDD7C0fsdcmkGmnAEXFnQ qP4Litp2XOCHpUxI8qzzHNgN53v5ab5kyaHsGP4QncpVTSioQREK13KOEGZMkqoTUzFHOqZs3OE qRyuHRQZ9nHwjItat0a0UvBGSjkV5rof7PH5PMWYykSg2uopHpZnoc6Uj+gyTto4BAYa65biwzh H+2vWV9mehnsaJotev+Pilefa3I19IL91CGUV4TU17Oq/WW4yiXhg2suwP0nflFeuu3tCXXCedX xtUdyettXLm5S/83kbFSbmAU8LZ7QPNQiLSTug7k6LohYaUy0yLHpaDDD4TwjIp8bdk67QHXlSg 8r4jjzXI7n74Yvw== X-Mailer: b4 0.14.2 Message-ID: <20251028-binder-bitmap-v3-4-32822d4b3207@google.com> Subject: [PATCH v3 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: Danilo Krummrich --- rust/kernel/id_pool.rs | 67 ++++++++++++++++++++++++++++++++++++++--------= ---- 1 file changed, 51 insertions(+), 16 deletions(-) diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs index d53628a357ed84a6e00ef9dfd03a75e85a87532c..e5651162db084f5dc7c16a493aa= 69ee253fe4885 100644 --- a/rust/kernel/id_pool.rs +++ b/rust/kernel/id_pool.rs @@ -25,24 +25,24 @@ /// 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::new(); /// let cap =3D pool.capacity(); /// /// for i in 0..cap { -/// assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?); +/// assert_eq!(i, pool.find_unused_id(i).ok_or(ENOSPC)?.acquire()); /// } /// /// pool.release_id(5); -/// assert_eq!(5, pool.acquire_next_id(0).ok_or(ENOSPC)?); +/// assert_eq!(5, 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(cap)); +/// assert_eq!(pool.find_unused_id(0).ok_or(ENOSPC)?.acquire(), cap); /// # Ok::<(), Error>(()) /// ``` /// @@ -56,8 +56,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); @@ -187,18 +187,17 @@ 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= > { + Some(UnusedId { + id: self.map.next_zero_bit(offset)?, + pool: self, + }) } =20 /// Releases an ID. @@ -208,6 +207,42 @@ 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. + #[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. + #[inline] + #[must_use] + 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. + #[inline] + pub fn acquire(self) -> usize { + self.pool.map.set_bit(self.id); + self.id + } +} + impl Default for IdPool { #[inline] fn default() -> Self { --=20 2.51.1.838.g19442a804e-goog From nobody Sat Feb 7 18:21:28 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 8E88830C378 for ; Tue, 28 Oct 2025 10:55:33 +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=1761648935; cv=none; b=uTqGX/1hONrgTpVgTndPwDL1yZuv+1aoDk4hBORNIs9Grv/tg5VZV2m1jiFXJ4SZJ/y/gIXOF1452J8RCKq4TzvEGnU3vkWJDdr3YC3nBFnc0csCaJc0Hkh/z5TMYDIzOtFr1tmON96hOpeuR6KsRbHOVR7MkKi4SGWUoJu85vo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1761648935; c=relaxed/simple; bh=udW1FE6CeJVfsDJwC6o78IFfdh17JFG2cGpHdZXuV68=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=ePHSXNvp5XMhlJ+qJAoXy8BCkSdiVz8ewY0RWUEo3JUueC8g4ytzUXjTVElXE9dcs1LEJQZE9GMemLUGVa+aKqzjpKEr10yaNcbthyR1mD8XFVdnChHT2Zw2oWUd/4VEzKr467ucMWjZNmLYxBcCIuXe+0C6JXxDr6XDJbNRFWE= 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=uozo1NG2; 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="uozo1NG2" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4711899ab0aso41244515e9.2 for ; Tue, 28 Oct 2025 03:55:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1761648932; x=1762253732; 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=usUdwV5qA+un71/eG88Mj+9iiBrsIeUHPYN64+4XrwA=; b=uozo1NG2HB3KA8nOTG5cGvssqqKP88VhN5Hi+JGkZ7hc1R5E3S+2Tbw+Ng98nJyejy o7wvKvim7DHpCxKXiBQrDCzqCcm9sZlNMo3yzy9w1U8TFFyTx4uKT9YxuZc8nZYKlhIC ahEpDQ20/FCIR5zEigjM+TOE12YWHY/SuFMuGi2bak95H3nL8EcYVT1DqLO4rkbz2csj +RNGYeSVI9T9GaylBRV2yTB3W+KnnVLJMKJ0rmuVcpApm/X2rhlxEhCV0g1WC2vBH1Oq 3zgKSa5h7ulln4oG1qWza8keGyZBgQM63X0YWj+P4XLkzn26mz8DgkW3r/ywKSovQ0eg eCZg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1761648932; x=1762253732; 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=usUdwV5qA+un71/eG88Mj+9iiBrsIeUHPYN64+4XrwA=; b=Kkz4OtBDagpcFBupEs4o9DQEFsF/+aCj15R0omYH+64vm9u+D49JtpybQjk4Vf+xkt 6tkBAPeYSVdHY+NJi/K+n8xhtvcD0MbL0wAJJmVZn2/PnQoGtXuTWPnttcfXKXeDPy8a RE8Vdtidw/NMpBrF1jPuXISqNj5GVwf37/C4+tMEgXjwS5ftOL/XafGTTcXogo9gph7y r5oXnz/P7ngWqpLGQvDHmDJ4DlVcA3O/azevN4Yg0zFiy6lth/iSsvDGEeEgixidk9Pk 47FXQhB9ymrx5Nq2m1tpyc+/iPXCDcXF90gh9q/eQf6sDeGn98rh3/CBDjye+F0qYKt0 eJIQ== X-Forwarded-Encrypted: i=1; AJvYcCWhBoKCCmm7K0WlUXiXPqyp8gap6xlMAmbBuqS9sC1Ew8lmim08i7BEKnZmT/BMjy3LwPir9y0hk/KlvfY=@vger.kernel.org X-Gm-Message-State: AOJu0Ywg3R7fHg1Ly7cE61VFYY+1s8WUYyqLQCfjWjvZGOAU4R31Cjmc 45C6IgMhF/vSbq4AK583NYLiQB4X08LLEA/XBeI6FQwLqlmLnSAsmGTTu8PmzRm1I/ZUd7zPO33 3ztVd/TQS4fC0Abg4gg== X-Google-Smtp-Source: AGHT+IFBSW6bF2q+Y3mewsY9Yj4Vi0BdA+pCImOnLmS8xiYMVzsIPBnvLC6oaJxCr7X7JpbuYJv3ec/ih7Towrw= X-Received: from wmht4.prod.google.com ([2002:a05:600c:41c4:b0:475:da28:9004]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:1da3:b0:46e:4e6d:79f4 with SMTP id 5b1f17b1804b1-47717dfaa6dmr22114485e9.15.1761648932262; Tue, 28 Oct 2025 03:55:32 -0700 (PDT) Date: Tue, 28 Oct 2025 10:55:18 +0000 In-Reply-To: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251028-binder-bitmap-v3-0-32822d4b3207@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=6215; i=aliceryhl@google.com; h=from:subject:message-id; bh=udW1FE6CeJVfsDJwC6o78IFfdh17JFG2cGpHdZXuV68=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBpAKEb6/jzR1A++T9KBHbdNW3hm55lNwI/Pvmlm Z6AdePXRS6JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaQChGwAKCRAEWL7uWMY5 RlrSEACw0LfP3ntIv+4pqRfxE26K0afKHBul8eqjdsDdO+y3l8yPFfLaZpNu8FSAmrch6mcB9dJ FqSwTE6YBV9hpyu1c92GJoaK7W9K1zctnhAfvzopCxdj3m7eHlBw5wInK8XnqK45Ozm5h7staQG f5W8ht4W5SSSWLSr2OTcO/NJTbDDctuVZSsYeyI8jjRmEHv9w2JNXNgL22s8gtqhGsuD3KZF01h k/has8YncnY9HUXzyaI2ZcsTJt+QhUZx+d11SaElf0SB8957/DE9ThOmvVeVhFpUQ2LJDzswjsl qMbQ1Q/AB3ML0/1iSA7S4LD6TzE81WZ/4LD5oWfXwtaiTFgSgHu4WKgNvKIPDVrLKZmaP3nquS3 4j2asU1qytUrZ4fH21VY3ds2N7NghuXdnYXCl68sN+bLASwxfQH1bYhdWNKohQ6AG/Vyja8+NPQ RrSDk4gJY0zZCEDzAD7CLyshcZ9BtKPZL1mLWBxISUCDW+x+HOz0Q/9R3MVCioDbWaUuA/O4eHB Jxe9J5MqxENjB/4ak20GcrRmJrO1ZcAc4RONusT3MFLzewBnBVbKfEDp1nXJQ7RSI9RmvD2HLAt xLM9FLEq+rVxs9ybWf6W8IjV+2fBrc2xY9vmI4bVE2Fb2qXgF3ajKmbBP1IbC18YdRwYavPTBrS Q/4inrBC73RRMqg== X-Mailer: b4 0.14.2 Message-ID: <20251028-binder-bitmap-v3-5-32822d4b3207@google.com> Subject: [PATCH v3 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. Reviewed-by: Burak Emir Signed-off-by: Alice Ryhl Acked-by: Carlos Llamas --- 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.1.838.g19442a804e-goog