From nobody Sat Feb 7 18:33:34 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 2CE6D2FDC20 for ; Mon, 20 Oct 2025 13:33:56 +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=1760967238; cv=none; b=QHaMiketm093Iq3AnN+lGNkt3bFqMUfyT+0drPdNhymY7ZmMsnkH69+RBm4BxJaoWoxkfrUIIt8ycxHhLxIvmlfIxjyVCFxV7A9GYWFa+s5HHHMqLESDE3+73HrF5rBbxZ+e1NXZJkD+y1dRl/dIsS7GI9grXMIoHuKYBuvSdAQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760967238; c=relaxed/simple; bh=thSFFHc18AWUj5aqWdgPfPpfkLxR0GCl0hag2FFKB38=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=rjBJPMssr4Y1kZvzLuv+dq62cNlOU1G9YxuIJpuq4wT2SWDC4S6oxVlT7Sefuw3XcDlcV5MjJmDnhK4w5F9ww4FkENUL97x1BE7jKrYhYETpekeQsgFgdGPP2aOt13DyLyzjzE7o5g9Z1Bg71hY3ovOoHBmyFBr2gcItIey9kec= 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=HyXqJntx; 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="HyXqJntx" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-46e4cb3e4deso15873545e9.1 for ; Mon, 20 Oct 2025 06:33:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1760967235; x=1761572035; 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=hP+6efxF2qsVAZJqN5GtRW+FGzYHXSfL66ojkDSC4QY=; b=HyXqJntxTBZrmupaWyHiKmWsHteFX01f6iC/70eNIa9nDb6j+9nQtVcT3XnSJW9Tr0 8g7MV7JMqDfx1AsW5xCw5f61ZGpJ1eQx8vZhbKukKvreziTSiXqMv7NNypAXObuI88J1 pgBZ3v9eVtyLEJF4FtWlV7aPOPCMNNkFgR/+oH+f7TCA7/a9TTjiyJ/HHyIwDzOR5C/s VeBNkJugs0HBYj+mkfX7oWHWT2EptfkcEWI5JDUnIykLLdLZqeI2zEHvtKkLY+0Q1QKO +7o82UIXFpk3F/NZjKhcn855RqKmt1dNVU0VCLqqrvH31DYqcpDnS0LWk67N/gdayr2g gvgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760967235; x=1761572035; 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=hP+6efxF2qsVAZJqN5GtRW+FGzYHXSfL66ojkDSC4QY=; b=XHzA3+JOCxVO///onMQH6QOKivpPwZCE6Be/llZ3tOkZblIW4Og2K3oENhk7Hq1VOF bNg1S9Kv+WCimJ6osZWxbsCITllorqVCI7gYO0YgpRvWJPsTZlTHPDWluaBf3ZpnIPC5 nCBheXdxS025Z2JV11l62Dt3HX5ipfosX42/hQBw4NxrujCAMfDpG9Ye5PtIdAxOglbS MTuk3dikivjrxlofKMW3ihzKhuzGRfhJ6s4K6okLvR40cCHWGblj4vm0NKaGdSW2tQtb uaTL9RigCGLdS37YDtjWMnBN0VHta0HflyAKSJ6BfU0BfHiFtVjvYbTBk3X5kaJTjw3O ZoXw== X-Forwarded-Encrypted: i=1; AJvYcCVlV+J1tHNau/5IMUy8QJjGEQW4lNiAbH/IPUTLRRCTEYgfcRHSYHTmlM0gcoNZA5PU2WW6fbVz0Frkc88=@vger.kernel.org X-Gm-Message-State: AOJu0YzYbPWZVHFhBM5/dPtapGkBWSXtSjkNPcRnp4UvbLZvj1MNugEP DrmfGFCk1nVmGhfv1n+B6EJpPS676mnH1Vc/Q2/B5UxXX9hJUxb4YLJq+Ct99RWEOksGBNN66Qn q9DkCPrS/IE65BJWh4A== X-Google-Smtp-Source: AGHT+IGsJYu7ivmzqWkEMta1m78AwxdpOsRB8GnsOYJkNeIzCPPDV8Af/U2XzI+UoFLtGfkAHK/DNZqKYu4z+S4= X-Received: from wmqg20.prod.google.com ([2002:a05:600c:4ed4:b0:45d:dc32:3d4a]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:8b0c:b0:46e:2815:8568 with SMTP id 5b1f17b1804b1-471172d7e15mr102633925e9.10.1760967235581; Mon, 20 Oct 2025 06:33:55 -0700 (PDT) Date: Mon, 20 Oct 2025 13:33:41 +0000 In-Reply-To: <20251020-binder-bitmap-v1-0-879bec9cddc1@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251020-binder-bitmap-v1-0-879bec9cddc1@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=2529; i=aliceryhl@google.com; h=from:subject:message-id; bh=thSFFHc18AWUj5aqWdgPfPpfkLxR0GCl0hag2FFKB38=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo9jpBcxwwb8kMGMy/7zHQfhjjqF1x9qVmgLLPY TMj/oGIL3qJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPY6QQAKCRAEWL7uWMY5 RrDUD/4llmvaB9bgfQsY+fQaRuNtXWlK4O9049eKPnNRPZaQdzfVJz2+jOFGLpEQwNBPa/NDWnh /1oB5DtKs6n6lvRSfHA4szqtfxBtXaC9kPqRCeRC5ANyINOlYb0RV7xl5K/3RfGk6d9/n7xRmOq iqJzVB2XBumsU2QsGM1IxE+66DkgFrTyNz1mjBkmmsO3EbSNOHEJI55GIe0hLDm+gbMypPzzeLY uzjRjryoB+hX2UWhrdLI+cvxzHZx0NMDTWiKV3ojcj09wHExwZCputoKRROyCTXqOdkjNUZkNK+ VJYqTe0CT6+pKm5Gun6NG4hlWePYV7QV+Hkd21rOXjwlPz6r3u1/4ckfWkISmw2Pv6OVEHg6EdQ ATrrHWdJ9BnMUSfKQNNqjPgLq0MUmxviZjXCC8aK/LAqX3m5revkl/mbigHy29p6Fv9DiFQcngG ToUFw6LUznMznOdf77zH3vfpwYLEeihQ+fWMCMURj8yZMsIeGaid08FR/70OCH5Aa7MT/AdeTVt sltd1T3M1ORWsqFl196kYBoY8IUsW/cvC4ZOEQ7kNNYwa6RpPISJOo0sgM8YQDGvB/3doZJmX6H grcDQcWQBjUVgR5ytVWkGiTSGqsQMJ67wPOe6EP/cV27nuFAzAVyFThtiWhe3bbm7ZFzU9q+bdo /lvTLmZ2kX83S4w== X-Mailer: b4 0.14.2 Message-ID: <20251020-binder-bitmap-v1-1-879bec9cddc1@google.com> Subject: [PATCH 1/2] 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. Signed-off-by: Alice Ryhl Acked-by: Danilo Krummrich Reviewed-by: Burak Emir --- 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.915.g61a8936c21-goog From nobody Sat Feb 7 18:33:34 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 1656B3191D2 for ; Mon, 20 Oct 2025 13:33:58 +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=1760967241; cv=none; b=leF0GEq0OWa2Ukm5A5NA+jZRzu90YNkiCTwG7YUP2UaGQdJghx7I25F5DUdcz6SikSRljG3j2LY1lLvpd23lriZLIwF8nbkWMbZ3qHfk68KE+xT4zQkdosyyhmkfc4hU6MNmG7XCKE9nf/Li/x3PKdw22f5xmg7siPU9P4Pi65I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1760967241; c=relaxed/simple; bh=R4pXEmMNsuBfi+wBM9oIG78safYpExcG2zg7DqP0UyI=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=ZoyG+Zsfzrg09OgSJv7AVvy0oqmd3k2hZtRX4LVm6yM4P6rKwKRxJMl9wkZ2Mhl7J1SVvk1acoWyOutDFd26OHz1Fic3o/V5VpPaukuPoA7iAsAaf/O4GxqxUw1g3J3hupf0h0xbiuC/anSJcEP3tm44jt+WIX96RepYr3yjvuA= 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=m2lzKac2; 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="m2lzKac2" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-471125c8bc1so51778045e9.3 for ; Mon, 20 Oct 2025 06:33:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1760967237; x=1761572037; 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=XujdrAVflWUs/mjjly58vQki5jrDGo9CKvfr8/mpjRU=; b=m2lzKac2YXlReoAZsD/h7ZAyLwVRqe3lw2JwAx0O0j2a+G8OoA95VyXc31ZM1n5cGn 82mcZ9HcZrhlXq8vHnfeyiFa4KLLE8gHfi8BoYs+He6PwNK5vASEjMUnJ8tBSeQfVlWu 1Q/VEDjKaWi5AewFKou03OIVla4EOGROdfc3+51QqZOxJQdyCWaF6DtTwENyrrgykdS4 tYij16iZyVKCQlvInilH5aBsSVVMQPCnQyy2JE30XBKQigOHjFzOl/NDYGXqCBz08eEc sIueUmnQpnphCuLguKoYCw9dRfDQnie+OqIQoQkuLE2h7I55YBB/+N7BOmNQTY116Kwz wkgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1760967237; x=1761572037; 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=XujdrAVflWUs/mjjly58vQki5jrDGo9CKvfr8/mpjRU=; b=PZAOgnmqdcoPQF1ZhkLwuj3L8+7p1HnHV9K7ausp58XnNYs5dlgPTC4xAyWe6iedgB Uf9+hhhZP9CfDyVByPz7KH4vtiSBo31TIBdKTI7rLGnhIythoo5+Pxb0YYy6Xw/VGWVQ cEpX8pWKb2mxd64yZrY8QQifC8rgfGCWwyZZ/rsuvtKN+iG9BO4DC/0188QxViZ3T26n IC+AmkUgFWh9i2MouV2xG/J4omN9WSlUosUdnGq4Y5CUAXv8qO06YTRrRJAQ6OZqkGQT 8TGBOCrSGrLAzINkN0yMHdyuN0HlsYuhq79l2ic4Wt5LQBjHUGNGzjXC6vimMOCoqKD0 zGmA== X-Forwarded-Encrypted: i=1; AJvYcCVm+2Dj9BNI0l3baFm6hnWPWX8j/40T+ll0XNSw8OgjO2hD0O2PJ+7sEzY4nhbA6vVnAvJKywT04Wxnjrs=@vger.kernel.org X-Gm-Message-State: AOJu0YzlzrWsGaJkTxJM1gTRypAonqMIeTlpGmrpLvloD5Lnnrsmqqvz 7TODmprx9b+Eqj+0FvqkDpeQaLH600C4dFv931sio03qLNh1UbeY6knuIBGTB94ZZU4W0qqEU9d ja9nwvrvGCBjTTmRTmQ== X-Google-Smtp-Source: AGHT+IGyFsfWuYmaNbQe9k6gzEwF9MvBVO5TrVWkBk5cWGn3hqRMTnHHpA5EzHmHzJv4ZT2BnK9gOCnVwnD8tng= X-Received: from wmbgz13.prod.google.com ([2002:a05:600c:888d:b0:46f:aa50:d703]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:820b:b0:471:1717:40a with SMTP id 5b1f17b1804b1-471178a8245mr89377715e9.18.1760967237543; Mon, 20 Oct 2025 06:33:57 -0700 (PDT) Date: Mon, 20 Oct 2025 13:33:42 +0000 In-Reply-To: <20251020-binder-bitmap-v1-0-879bec9cddc1@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251020-binder-bitmap-v1-0-879bec9cddc1@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=8183; i=aliceryhl@google.com; h=from:subject:message-id; bh=R4pXEmMNsuBfi+wBM9oIG78safYpExcG2zg7DqP0UyI=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBo9jpBTeFPzhytp2JfiEHURGOLAXJTd8EcDJTJY 3I+swFFn82JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaPY6QQAKCRAEWL7uWMY5 Ri7/D/wO3vwSeuqFI3SlvaFEd+bgQP6HLNB2W4OQmJPhT98ZjJk/QJ6/0BnRAWJk5U8vWy9DZyk lDe7GqVjg33v2q3EUbxlm7N2psb0B+Ev88goRywyoeEO1mm5UBwyahmoqWmJkK67wfKqvwbW9WD UkiOuzFhiEkDTbh7/ze0W9KOCkkgsRwkm/CDWmYdQBjBFvfU/WFqxAowoDAw2oHY0GvWFD/IGFO elFPld6E5YQ4fVp2aCIleMAJe4e3TprTG/sALpSigwcTDJlWXkoXrur+p2YF/sLJKX8+RHf51mm bax+Pt9iZBSxgLdLPxyOsY09OEnhV8VoEkI7MX9bf5qGfthO6K1KiE/2SVyHo75SpTwXjeIZJyn zMlXRPxe4oGy3SdFzVLZmb19N4do/L/F3TH/xQ7Rk078J2z09mZw1/O7pYWHyynLwSCFykY/DEv EDyHYUwNqPjsukTh2lxX77D1Sq3Y2l9IxqzJdCBSB6B//vc3/4NEbiy39UsQ92F0st3qVa98/+w /Ir+AyH/zZFyH1o4D39qbecRFERN6+WBkzFJqgVUTq97En75jO2SV1z6OXjcU+Soxz2HElvg8lh lEmlNTjrtY24tzp3cQi1wlBN41oMvYjYstikc6wNvlhXLtAnB6ixpjANsWhJVUZBL1jpWxIgimp jJ2nQsBec18eeEg== X-Mailer: b4 0.14.2 Message-ID: <20251020-binder-bitmap-v1-2-879bec9cddc1@google.com> Subject: [PATCH 2/2] 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 --- drivers/android/binder/process.rs | 110 +++++++++++++++++++++++++++++++---= ---- 1 file changed, 90 insertions(+), 20 deletions(-) diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/pro= cess.rs index f13a747e784c84a0fb09cbf47442712106eba07c..357ba1b577c73ad3f2b525a8573= 424420577e92d 100644 --- a/drivers/android/binder/process.rs +++ b/drivers/android/binder/process.rs @@ -16,6 +16,7 @@ =20 use kernel::{ bindings, + bitmap::BitmapVec, cred::Credential, error::Error, fs::file::{self, File}, @@ -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_present: BitmapVec, /// 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, @@ -378,13 +381,56 @@ struct ProcessNodeRefs { } =20 impl ProcessNodeRefs { - fn new() -> Self { - Self { + fn new() -> Result { + Ok(Self { by_handle: RBTree::new(), + handle_present: BitmapVec::new(BitmapVec::NO_ALLOC_MAX_LEN, GF= P_KERNEL)?, by_node: RBTree::new(), freeze_listeners: RBTree::new(), + }) + } + + fn bitmap_shrink_len(&self) -> Option { + let nbits =3D self.handle_present.len(); + + if nbits <=3D BitmapVec::NO_ALLOC_MAX_LEN { + return None; + } + + match self.handle_present.last_bit() { + Some(bit) if bit < nbits >> 2 =3D> Some(nbits >> 1), + None =3D> Some(BitmapVec::NO_ALLOC_MAX_LEN), + _ =3D> None, + } + } + + fn bitmap_grow_len(&self) -> Option { + let new_len =3D self + .handle_present + .len() + .checked_mul(2) + .unwrap_or(BitmapVec::MAX_LEN) + .min(BitmapVec::MAX_LEN); + + if new_len > self.handle_present.len() { + Some(new_len) + } else { + None + } + } + + fn try_shrink_bitmap(&mut self, new_map: BitmapVec) { + if let Some(target_len) =3D self.bitmap_shrink_len() { + if new_map.len() =3D=3D target_len { + self.replace_bitmap(new_map); + } } } + + fn replace_bitmap(&mut self, mut new_map: BitmapVec) { + new_map.copy_and_extend(&self.handle_present); + self.handle_present =3D new_map; + } } =20 /// A process using binder. @@ -471,7 +517,7 @@ fn new(ctx: Arc, cred: ARef) -> Re= sult> { cred, inner <- kernel::new_spinlock!(ProcessInner::new(), "Proce= ss::inner"), pages <- ShrinkablePageRange::new(&super::BINDER_SHRINKER), - node_refs <- kernel::new_mutex!(ProcessNodeRefs::new(), "P= rocess::node_refs"), + node_refs <- kernel::new_mutex!(ProcessNodeRefs::new()?, "= Process::node_refs"), freeze_wait <- kernel::new_condvar!("Process::freeze_wait"= ), task: current.group_leader().into(), defer_work <- kernel::new_work!("Process::defer_work"), @@ -775,7 +821,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 +840,34 @@ 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 (handle, 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(handle) =3D refs.handle_present.next_zero_bit(star= t) { + let handle_u32 =3D u32::try_from(handle).map_err(|_| ENOME= M)?; + match refs.by_handle.entry(handle_u32) { + rbtree::Entry::Vacant(entry) =3D> break (handle_u32, e= ntry), + rbtree::Entry::Occupied(_) =3D> { + pr_err!("Detected mismatch between handle_present = and by_handle"); + refs.handle_present.set_bit(handle); + continue; + } + } + } + + let new_len =3D refs.bitmap_grow_len().ok_or(ENOMEM)?; + drop(refs_lock); + let new_bitmap =3D BitmapVec::new(new_len, GFP_KERNEL)?; + refs_lock =3D self.node_refs.lock(); + refs =3D &mut *refs_lock; + if refs.handle_present.len() < new_len { + refs.replace_bitmap(new_bitmap); + } + }; =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 +877,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 +900,9 @@ 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); + Ok(handle) } =20 pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult= { @@ -905,6 +967,14 @@ 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_present.clear_bit(handle as usize); + + if let Some(shrink_len) =3D refs.bitmap_shrink_len() { + drop(refs); + let new_bitmap =3D BitmapVec::new(shrink_len, GFP_KERN= EL)?; + refs =3D self.node_refs.lock(); + refs.try_shrink_bitmap(new_bitmap); + } } } else { // All refs are cleared in process exit, so this warning is ex= pected in that case. --=20 2.51.0.915.g61a8936c21-goog