From nobody Wed Dec 17 08:58:18 2025 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 8D61220CCF0 for ; Tue, 18 Mar 2025 17:49:20 +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=1742320162; cv=none; b=G5D1DYeA13bxnJSlsvol+WAGjsIDlmemHmvOHfX6IIKS3pP13tvobREPQ6yDf6xrQoGnxVZSUA+fr7g0PHNqMF+o5TrtW6QL6s1KZy6hv/PAtKdbkT+tlwSOcTKVDy6H7rGT6lyjGTd4kNWOvSKk8QDBJOvrdjVIYv6aAMXWOPk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742320162; c=relaxed/simple; bh=uJIutiU4F9uJdD39iNb8Ou5XvYDbRa8EcLckqr3kp10=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Y60gyHW+zDLShpmLZCYo2OKfqJq6RRYQtdV05Gl5xAbcK90TTd3V1uA9RDADg9YIppopgHQ0zhCyefOYRXhdVcL/U5yLmyolPDkIYZLNSmEnEFzFtAU9x5BEbKc4O5sAHbjGArDGpdOgBpABzVv7szA4W4LAtbuyPR+t57sxmn4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--bqe.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=mazzuzZB; 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--bqe.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="mazzuzZB" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-43941ad86d4so18550905e9.2 for ; Tue, 18 Mar 2025 10:49:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1742320159; x=1742924959; 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=PSbH1lMYu7B70rx8iHcL63GgWlDTcxDGerlsbQLm9MQ=; b=mazzuzZBB6JASR0+GwTWFRNlh1tpYoyxTRhT/MrvYEZ2kjDrVxopj6T0IQOOA1/YRw hZ/Qw89zgFdW625xnq8yCsUjZDwkDih6RbP6zg6Wmq4DYsXQuEdaonbhPQcqeXSPRu70 rUwim6HriVQhzU4ieswYm3YUU5sxXvo2V03l7rFvwUXzpKLE2YOmHJnOyXXkNNIncmTM bvlkbUiSizEpFLwx6HO+giyVmDe6LvVa4Pbm+KMY7jDhmzMBxWlyI+c1j+Gq8MVVURnq 8HGV7H4VELQi9A3H47AFNWC9qwGfqc+tDGQWs9NQ9m+QBCAnD1Kf+ZDXj5FaHfDSouKi Zj3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742320159; x=1742924959; 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=PSbH1lMYu7B70rx8iHcL63GgWlDTcxDGerlsbQLm9MQ=; b=GkYe6KQwbk4lBxnawWlKGGBe0TCIvQFdtC88RDP7n8LdVRDhLQyfWNwph2y+FaeMLf Mu9+huKmHCLep3/1tjRmEpN3abCA6VZO8SrdH2artWYMQEl8jJCFw4XVkIO2gBzMPCBY eDZ+aDCASOffsTvPm3HLdTuNPGdgvsNHRQythkjQGXVjx3FkByG5QqrJraaGWj2SOZDV ogd99/rBgxlFMGHdRquZAacV1cSnuIH+wOn+Epikq/s91eEjdBjUloToTNbdEhaFEqsz 7BzxTd8r6N7VD7YS6JANzZvEEAgmvs7sJBFpEjjlFspHOptHpD4/yLnGK3ExdiZZPP0M YKrg== X-Forwarded-Encrypted: i=1; AJvYcCU+fY3ulsjL4vb/KZ58sJ96MQp2Zx3U3+l1F7wh28Mjf/bYgiZkoJTou/WX4okvHeFUqa3C/PavJkNm7Dw=@vger.kernel.org X-Gm-Message-State: AOJu0YwcFHxoXA9DVEBKWPV1heWIGGK4dpR8MApySBpAW0G5hUTY2+Pj LHHOUh8atgbRiqT/6SnsO0zkLTKPmdncAxdADYylJAinIyrcAh4PV6kGuUDHb/OlyA== X-Google-Smtp-Source: AGHT+IGwrDuMxtuMxwl92MGb7Xvh2jSFb+fFzxcdzRaMOUfOAdTNuPSleq3PgEtUak+wFqpPII4/qFo= X-Received: from wmqd2.prod.google.com ([2002:a05:600c:34c2:b0:43b:c9fc:b269]) (user=bqe job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:1d2a:b0:43c:e2dd:98ea with SMTP id 5b1f17b1804b1-43d3b9cd71bmr30430905e9.22.1742320159036; Tue, 18 Mar 2025 10:49:19 -0700 (PDT) Date: Tue, 18 Mar 2025 17:45:45 +0000 In-Reply-To: <20250318164221.1533590-1-bqe@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250318164221.1533590-1-bqe@google.com> X-Mailer: git-send-email 2.49.0.395.g12beb8f557-goog Message-ID: <20250318174756.1625571-3-bqe@google.com> Subject: [PATCH v4 1/3] Adds bitmap.c and bitops.c Rust bindings. From: Burak Emir To: Yury Norov Cc: Burak Emir , Rasmus Villemoes , Viresh Kumar , Miguel Ojeda , Alex Gaynor , Boqun Feng , Gary Guo , Bjorn Roy Baron , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Adds helpers for bitmap.c and bitops.c to get Rust bindings for inline methods __set_bit and __clear_bit (these are non-atomic variants) as well as bitmap_copy_and_extend. These are needed for providing a basic Rust Bitmap API. Update MAINTAINERS. Suggested-by: Alice Ryhl Signed-off-by: Burak Emir --- MAINTAINERS | 11 +++++++++++ rust/bindings/bindings_helper.h | 1 + rust/helpers/bitmap.c | 9 +++++++++ rust/helpers/bitops.c | 13 +++++++++++++ rust/helpers/helpers.c | 2 ++ 5 files changed, 36 insertions(+) create mode 100644 rust/helpers/bitmap.c create mode 100644 rust/helpers/bitops.c diff --git a/MAINTAINERS b/MAINTAINERS index c43d66bd85f3..50f44d7e5c6e 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -4029,6 +4029,12 @@ F: tools/include/vdso/bits.h F: tools/lib/bitmap.c F: tools/lib/find_bit.c =20 +BITMAP API BINDINGS [RUST] +M: Yury Norov +S: Maintained +F: rust/helpers/bitmap.c +F: rust/helpers/cpumask.c + BITMAP API [RUST] M: Viresh Kumar (cpumask) R: Yury Norov @@ -4049,6 +4055,11 @@ F: include/linux/bitops.h F: lib/test_bitops.c F: tools/*/bitops* =20 +BITOPS API BINDINGS [RUST] +M: Yury Norov +S: Maintained +F: rust/helpers/bitops.c + BLINKM RGB LED DRIVER M: Jan-Simon Moeller S: Maintained diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helpe= r.h index 55354e4dec14..6bd4396b9cd3 100644 --- a/rust/bindings/bindings_helper.h +++ b/rust/bindings/bindings_helper.h @@ -7,6 +7,7 @@ */ =20 #include +#include #include #include #include diff --git a/rust/helpers/bitmap.c b/rust/helpers/bitmap.c new file mode 100644 index 000000000000..a50e2f082e47 --- /dev/null +++ b/rust/helpers/bitmap.c @@ -0,0 +1,9 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include + +void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned = long *from, + unsigned int count, unsigned int size) +{ + bitmap_copy_and_extend(to, from, count, size); +} diff --git a/rust/helpers/bitops.c b/rust/helpers/bitops.c new file mode 100644 index 000000000000..0ea1611b95dc --- /dev/null +++ b/rust/helpers/bitops.c @@ -0,0 +1,13 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include + +void rust_helper___set_bit(unsigned int nr, unsigned long *addr) +{ + __set_bit(nr, addr); +} + +void rust_helper___clear_bit(unsigned int nr, unsigned long *addr) +{ + __clear_bit(nr, addr); +} diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 0640b7e115be..74e5e10694a4 100644 --- a/rust/helpers/helpers.c +++ b/rust/helpers/helpers.c @@ -7,6 +7,8 @@ * Sorted alphabetically. */ =20 +#include "bitmap.c" +#include "bitops.c" #include "blk.c" #include "bug.c" #include "build_assert.c" --=20 2.49.0.rc1.451.g8f38331e32-goog From nobody Wed Dec 17 08:58:18 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 563A421019E for ; Tue, 18 Mar 2025 17:54:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742320443; cv=none; b=R0C1YBaIn91iRook+Ryf0POc6ZY7IN+G2obdVmmf1K1p2juuYTE599yMUEgjys+nin/4gNYRCr+IOxmWTxfO2ymM1K3pW7lcdvrdUmvaK6OC9RIU6jyPTA0TWoT9S5Y2K4NSr+PeLVPf7JdR6nJWpyP7eU4Vp68J4fs6uMjtllk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742320443; c=relaxed/simple; bh=RwSUxJCEIuMsb7Jqi8oaa0p9OZd3rsArgVJSEyzwtm8=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=IpxBNXTh+qCWIRtdObEbL+W0IUyh3uwg58wnVhk+YqqbVtfcJnhmft0EU3dMDuVvDcS8XDGyJ7x5TVy6HAE3PwKCpTXPdMXRJAse4tpJU426B4NXinOawj4r+iZkiVLtDBtpeuL7sJk0SMbuvZUmk/BOxuOzWhkB83rkxIRpWwg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--bqe.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=xfwW1Xpt; 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--bqe.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="xfwW1Xpt" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-43cf172ff63so22971265e9.3 for ; Tue, 18 Mar 2025 10:54:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1742320439; x=1742925239; 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=JtRRUpBmdbrhDkJPpcQ9zxxSGQP77/v+ZvbBB0uFPno=; b=xfwW1XptNybX8bgU8/kD6ETH851p9fQv/1zH7qG2swuOkiMZwBLUND69l6Y8GgDLbM HpcTPTUwxbpnDBxdvSMtHSva3G10d+/KSdyDi+zYkU/d59XxyD2U+o6gf8sdaSpSCh44 4HvDbb9mE4HR7+jtp2euMWMgvaJNsuJcdH9cdL3HLNdZXI8BGdjUcHXC6/XRf4xErVms VYgVHqAV9X+d/ks4gOE6swyLAU6kISymYDaj3V9RKHybVze6rdZZe9MvEQpFfC+X3eye 7VSy85doFVBlgmTR5TaJqRCPExb0xqRRjHNIa0P0u8jFM3hPecK1CFWsH6FU1haiDWcD D09Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742320439; x=1742925239; 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=JtRRUpBmdbrhDkJPpcQ9zxxSGQP77/v+ZvbBB0uFPno=; b=CHtosu4CI73XszFjlz8aV63peb8TRmbrmMKq6S8RvC4Rw1jlpMzssca5KYEhBVbBfy EGzpPw8hLLCPYJKqI3r8QUQ2CjYV45+eGFjdPpTD795uzZI4BdN38MzkB1UDbSST5f5y qVtQomqTl4zyQ+hqDlmAllaE+PKrEV5A+NpZEA18CnaEtoAR7kRt7W672Dcv4uttsxbq WpBNgngfM8fYRP2VziTWeNspKCe4iK7gOK3xG+/rv6j8A302TOfbyud8aqcA+9xxx2sA F234vzDoFsL9R59++J449n30f4S6BR8Zto1HcJlHSZw+c3Siqtxt0TK2HiqMF0UW+zer 6guw== X-Forwarded-Encrypted: i=1; AJvYcCVIGVGw2i3/Q/xUwISfsJUzg8UOR0th9MereWxvzO18QB/rDeKTCZ8mrxeo/7ppee6qTOR/NVHXs3ojr50=@vger.kernel.org X-Gm-Message-State: AOJu0YyHaMM8His1d42qYez5IrWLnZW4U6gPaQsPiNo+3GNYEqExJVOa rRtBWt4i6FftgwkBUeTfVVheUfb0lYNFGi3UsT/I5veSKMcJbCTDoKmCQ7VnUzkj6A== X-Google-Smtp-Source: AGHT+IEow0KUsXork9VOcbrrv1ftSkiGbKuFjzVfSZqoviK0i8inh8tCQQYcQe8VZNOsFlLNOQg7Hys= X-Received: from wmcn9.prod.google.com ([2002:a05:600c:c0c9:b0:43c:e69c:d4e6]) (user=bqe job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:5106:b0:43c:fe90:1279 with SMTP id 5b1f17b1804b1-43d3b9bceaemr30467085e9.21.1742320439795; Tue, 18 Mar 2025 10:53:59 -0700 (PDT) Date: Tue, 18 Mar 2025 17:51:53 +0000 In-Reply-To: <20250318164221.1533590-1-bqe@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250318164221.1533590-1-bqe@google.com> X-Mailer: git-send-email 2.49.0.395.g12beb8f557-goog Message-ID: <20250318175322.1627073-2-bqe@google.com> Subject: [PATCH v4 2/3] Adds Rust Bitmap API. From: Burak Emir To: Yury Norov Cc: Burak Emir , Rasmus Villemoes , Viresh Kumar , Miguel Ojeda , Alex Gaynor , Boqun Feng , Gary Guo , Bjorn Roy Baron , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Provides an abstraction for C bitmap API and bitops operations. This includes enough functionality to reimplementing a Binder data structure (drivers/android/dbitmap.h). More methods can be added later. We offer a safe API through bounds checks which panic if violated. We use the `usize` type for sizes and indices into the bitmap, because Rust generally always uses that type for indices and lengths and it will be more convenient if the API accepts that type. This means that we need to perform some casts to/from u32 and usize, since the C headers use unsigned int instead of size_t/unsigned long for these numbers in some places. Suggested-by: Alice Ryhl Signed-off-by: Burak Emir --- MAINTAINERS | 2 + rust/kernel/bitmap.rs | 234 ++++++++++++++++++++++++++++++++++++++++++ rust/kernel/lib.rs | 1 + 3 files changed, 237 insertions(+) create mode 100644 rust/kernel/bitmap.rs diff --git a/MAINTAINERS b/MAINTAINERS index 50f44d7e5c6e..b3bbce9274f0 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -4036,9 +4036,11 @@ F: rust/helpers/bitmap.c F: rust/helpers/cpumask.c =20 BITMAP API [RUST] +M: Alice Ryhl (bitmap) M: Viresh Kumar (cpumask) R: Yury Norov S: Maintained +F: rust/kernel/bitmap.rs F: rust/kernel/cpumask.rs =20 BITOPS API diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs new file mode 100644 index 000000000000..e8117e0dbe05 --- /dev/null +++ b/rust/kernel/bitmap.rs @@ -0,0 +1,234 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2025 Google LLC. + +//! Rust API for bitmap. +//! +//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h). + +use crate::alloc::{AllocError, Flags}; +use crate::bindings; +use core::ptr::NonNull; + +/// Represents a bitmap. +/// +/// Wraps underlying C bitmap API. +/// +/// # Examples +/// +/// Basic usage +/// ``` +/// use kernel::alloc::flags::GFP_KERNEL; +/// use kernel::bitmap::Bitmap; +/// +/// let mut b =3D Bitmap::new(16, GFP_KERNEL)?; +/// assert_eq!(16, b.len()); +/// for i in 0..16 { +/// if i % 4 =3D=3D 0 { +/// b.set_bit(i); +/// } +/// } +/// assert_eq!(Some(1), b.find_next_zero_bit(0)); +/// assert_eq!(Some(5), b.find_next_zero_bit(5)); +/// assert_eq!(Some(12), b.find_last_bit()); +/// # Ok::<(), Error>(()) +/// ``` +/// +/// # Invariants +/// +/// `ptr` is obtained from a successful call to `bitmap_zalloc` and +/// holds the address of an initialized array of `unsigned long` +/// that is large enough to hold `nbits` bits. +/// `nbits` is `<=3D u32::MAX` and never changes. +pub struct Bitmap { + /// Pointer to an array of `unsigned long`. + ptr: NonNull, + /// How many bits this bitmap stores. Must be `<=3D u32::MAX`. + nbits: usize, +} + +impl Drop for Bitmap { + fn drop(&mut self) { + // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`. + // + // INVARIANT: there is no other use of the `self.ptr` after this + // call and the value is being dropped so the broken invariant is + // not observable on function exit. + unsafe { bindings::bitmap_free(self.as_mut_ptr()) }; + } +} + +impl Bitmap { + /// Constructs a new [`Bitmap`]. + /// + /// Fails with [`AllocError`] when the [`Bitmap`] could not be + /// allocated. This includes the case when `nbits` is greater + /// than `u32::MAX`. + #[inline] + pub fn new(nbits: usize, flags: Flags) -> Result { + if let Ok(nbits_u32) =3D u32::try_from(nbits) { + // SAFETY: `nbits =3D=3D 0` is permitted and `nbits <=3D u32::= MAX`. + let ptr =3D unsafe { bindings::bitmap_zalloc(nbits_u32, flags.= as_raw()) }; + // Zero-size allocation is ok and yields a dangling pointer. + let ptr =3D NonNull::new(ptr).ok_or(AllocError)?; + // INVARIANT: ptr returned by C `bitmap_zalloc` and nbits chec= ked. + Ok(Bitmap { ptr, nbits }) + } else { + Err(AllocError) + } + } + + /// Returns how many bits this [`Bitmap`] holds. + #[inline] + pub fn len(&self) -> usize { + self.nbits + } + + /// Returns true if this [`Bitmap`] has length `0`. + #[inline] + pub fn is_empty(&self) -> bool { + self.nbits =3D=3D 0 + } + + /// Returns a mutable raw pointer to the backing [`Bitmap`]. + #[inline] + fn as_mut_ptr(&mut self) -> *mut usize { + self.ptr.as_ptr() + } + + /// Returns a raw pointer to the backing [`Bitmap`]. + #[inline] + fn as_ptr(&self) -> *const usize { + self.ptr.as_ptr() + } + + /// Sets bit with index `index`. + /// + /// # Panics + /// + /// Panics if `index` is greater than or equal to `self.nbits`. + #[inline] + pub fn set_bit(&mut self, index: usize) { + assert!( + index < self.nbits, + "Bit `index` must be < {}, was {}", + self.nbits, + index + ); + // SAFETY: Bit `index` is within bounds. + unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) }; + } + + /// Clears bit with index `index`. + /// + /// # Panics + /// + /// Panics if `index` is greater than or equal to `self.nbits`. + #[inline] + pub fn clear_bit(&mut self, index: usize) { + assert!( + index < self.nbits, + "Bit `index` must be < {}, was {}", + self.nbits, + index + ); + // SAFETY: Bit `index` is within bounds. + unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) }; + } + + /// Replaces this [`Bitmap`] with `src` and sets any remaining bits to= zero. + /// + /// # Panics + /// + /// Panics if `src` is longer than this [`Bitmap`]. + /// + /// # Examples + /// + /// ``` + /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; + /// use kernel::bitmap::Bitmap; + /// + /// let mut long_bitmap =3D Bitmap::new(256, GFP_KERNEL)?; + /// let short_bitmap =3D Bitmap::new(16, GFP_KERNEL)?; + /// long_bitmap.copy_from_bitmap_and_extend(&short_bitmap); + /// # Ok::<(), AllocError>(()) + /// ``` + #[inline] + pub fn copy_from_bitmap_and_extend(&mut self, src: &Bitmap) { + assert!( + src.nbits <=3D self.nbits, + "Length of `src` must be <=3D {}, was {}", + self.nbits, + src.nbits + ); + // SAFETY: `nbits =3D=3D 0` is supported and access to `self` and = `src` is within bounds. + unsafe { + bindings::bitmap_copy_and_extend( + self.as_mut_ptr(), + src.as_ptr(), + src.nbits as u32, + self.nbits as u32, + ) + }; + } + + /// Replaces this bitmap with a prefix of `src` that fits into this [`= Bitmap`]. + /// + /// # Panics + /// + /// Panics if `src` is shorter than this [`Bitmap`]. + /// + /// # Examples + /// + /// ``` + /// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; + /// use kernel::bitmap::Bitmap; + /// + /// let mut short_bitmap =3D Bitmap::new(16, GFP_KERNEL)?; + /// let long_bitmap =3D Bitmap::new(256, GFP_KERNEL)?; + /// short_bitmap.copy_prefix_from_bitmap(&long_bitmap); + /// # Ok::<(), AllocError>(()) + /// ``` + #[inline] + pub fn copy_prefix_from_bitmap(&mut self, src: &Bitmap) { + assert!( + self.nbits <=3D src.nbits, + "Length of `src` must be >=3D {}, was {}", + self.nbits, + src.nbits + ); + // SAFETY: `nbits =3D=3D 0` is supported and access to `self` and = `src` is within bounds. + unsafe { + bindings::bitmap_copy_and_extend( + self.as_mut_ptr(), + src.as_ptr(), + self.nbits as u32, + self.nbits as u32, + ) + }; + } + + /// Finds the last bit that is set. + #[inline] + pub fn find_last_bit(&self) -> Option { + // SAFETY: `nbits =3D=3D 0` is supported and access is within boun= ds. + let index =3D unsafe { bindings::_find_last_bit(self.as_ptr(), sel= f.nbits) }; + if index =3D=3D self.nbits { + None + } else { + Some(index) + } + } + + /// Finds the next zero bit, starting from `offset`. + #[inline] + pub fn find_next_zero_bit(&self, offset: usize) -> Option { + // SAFETY: `nbits =3D=3D 0` and out-of-bounds offset is supported. + let index =3D unsafe { bindings::_find_next_zero_bit(self.as_ptr()= , self.nbits, offset) }; + if index =3D=3D self.nbits { + None + } else { + Some(index) + } + } +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index efbd7be98dab..be06ffc47473 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -36,6 +36,7 @@ pub use ffi; =20 pub mod alloc; +pub mod bitmap; #[cfg(CONFIG_BLOCK)] pub mod block; #[doc(hidden)] --=20 2.49.0.rc1.451.g8f38331e32-goog From nobody Wed Dec 17 08:58:18 2025 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 6449613D52F for ; Tue, 18 Mar 2025 17:54:52 +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=1742320495; cv=none; b=DCsS86WWwYiXjLu0irXxiICOyqvWwZ7bOC4M6jZ/WqqTBhtSUJzEH+et1RN4sFSyIeU1lZDfb8vRQNbI40AyMskYDt8+DmqpawWKP77WUe+v8q8w9ZURAduWZat7FsA3V7QU0Uf74Sdy3FJe+hbpCDOXO6GWW/jYBate3CBrS7A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742320495; c=relaxed/simple; bh=FK69DBDbx15AGsjLQn4hzKCgIPn8W+7OJ5VoUogYe68=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=fNxd0Ktz2BFBO0UcHh14qiLM+Emg766ybKojNd9vuw/8xqYi037rNxSmW6pUYCJQ+uBe+fkYZzn5ktYkcfM/DJa/DXVj6yN2iyI4GTwoS1OhcliCWBAsc1qNzXa8wVZ7yTCmz8yFkhX2omEF2xT9pMTVulW5k2Zi5W8mwxMy/3w= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--bqe.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=rPbhFtPA; 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--bqe.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="rPbhFtPA" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-43941ad86d4so18569895e9.2 for ; Tue, 18 Mar 2025 10:54:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1742320491; x=1742925291; 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=ucaWlpvQ0hnSoOA7AlIgnz0cgmqZKnUxsdJt8CvjyU8=; b=rPbhFtPA4b0vTDeYJQn4MIrBMR2JXxD2NOBS2g/5Blj10LoIJaTD7vPFtxGaBy+tbv vC5HC+1+s1RZUal3pbYjPwMcQc5xC+lXJYDOEZPi2WoS67P0zpaDK8g9lOqelacDWLrJ 7yhO6On1zA8VTQ0U9bCa6HaWRmMx0XildTqhr6e0EAfKROY8IdIMVt44WZZ8nnKIqme+ 0CI3P4aDF8dP1xYEW+b3iFGhOU6TuL5VGOOycIVRWtOeZPREnEgyt8fO2eaY+qdClPKV cvbK5fV0InEJwhiZTVyR/lTbm5cOcow7BPEl/nYYm4oWWZN1Lzw8wwW0rPbtleYtRYzA AAmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742320491; x=1742925291; 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=ucaWlpvQ0hnSoOA7AlIgnz0cgmqZKnUxsdJt8CvjyU8=; b=tbccCk/FfeKjSf9nLd2kyb0m5G1bqRX7Md2Tg+onDZmnpesd+AECJMUQxgqy0XujfM dtzdOImUt4NoP+KNfe9q3Jwpp1SkB6+PEW4GH85vIVIRPFKjEH5nEDx9Awadl7BDwaDM Z1a6L3ERl7K8IFjgIM5dzNJUIov59zhdt1hu5fBrgiL88D//fkYuJH9lnYu8FJCBbxWO TX0cl8zKQJM5fzI/K7n+ns+vgd1s68lQgtDlffqc7fZujrMgMQZDUcwT6YDR/7w2aOBE yOREE1SEhzD0NlZM+6evsPjfWsSEX4uwHgnt5NK+7NOOfsaqFArcpUj7aJXEn1sU8Yzq dRSg== X-Forwarded-Encrypted: i=1; AJvYcCWDhDLp7j7xJ9Qjx8MpITpMMnttBSp1peoPKfe90A+qhWGy2XTqO7oQAVhiYAZ74GV9TFEXp9BxtJftYcM=@vger.kernel.org X-Gm-Message-State: AOJu0Yy8DlKc7CkcW0zvl6tCw6B7Lqek2sfntBWNF3gzBsmMD9Erw8LJ E9bgRLtEb3qdrNhpYG8wTdg4I+XdN+i82xl1YVj5MRvjYsKpBwDU/YjuhLxQQSkY7w== X-Google-Smtp-Source: AGHT+IE9HCWFwX0V1dhe93zc5NW/AaGRcwmRfIgKOL0NRLkOirF6/Xjn0gSPZ7HpqYNpucDNRmXSVn0= X-Received: from wmbdl18.prod.google.com ([2002:a05:600c:6692:b0:43c:f256:f4b3]) (user=bqe job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:3b97:b0:43c:e467:d6ce with SMTP id 5b1f17b1804b1-43d3b9504a6mr34302145e9.4.1742320490880; Tue, 18 Mar 2025 10:54:50 -0700 (PDT) Date: Tue, 18 Mar 2025 17:54:09 +0000 In-Reply-To: <20250318164221.1533590-1-bqe@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250318164221.1533590-1-bqe@google.com> X-Mailer: git-send-email 2.49.0.395.g12beb8f557-goog Message-ID: <20250318175423.1627715-2-bqe@google.com> Subject: [PATCH v4 3/3] Add DynamicIdPool Rust API. From: Burak Emir To: Yury Norov Cc: Burak Emir , Rasmus Villemoes , Viresh Kumar , Miguel Ojeda , Alex Gaynor , Boqun Feng , Gary Guo , Bjorn Roy Baron , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" This is a port of the Binder data structure introded in commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to Rust. The file drivers/android/dbitmap.h uses bitmaps for allocating and releasing IDs. We provide an equivalent Rust API that gives clients fine-grained control over when to allocate a new bitmap. Suggested-by: Alice Ryhl Signed-off-by: Burak Emir --- MAINTAINERS | 3 +- rust/kernel/dynamic_id_pool.rs | 191 +++++++++++++++++++++++++++++++++ rust/kernel/lib.rs | 1 + 3 files changed, 194 insertions(+), 1 deletion(-) create mode 100644 rust/kernel/dynamic_id_pool.rs diff --git a/MAINTAINERS b/MAINTAINERS index b3bbce9274f0..d429ede24d3c 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -4036,12 +4036,13 @@ F: rust/helpers/bitmap.c F: rust/helpers/cpumask.c =20 BITMAP API [RUST] -M: Alice Ryhl (bitmap) +M: Alice Ryhl (bitmap,dynamic_id_pool) M: Viresh Kumar (cpumask) R: Yury Norov S: Maintained F: rust/kernel/bitmap.rs F: rust/kernel/cpumask.rs +F: rust/kernel/dynamic_id_pool.rs =20 BITOPS API M: Yury Norov diff --git a/rust/kernel/dynamic_id_pool.rs b/rust/kernel/dynamic_id_pool.rs new file mode 100644 index 000000000000..3e243358cd6b --- /dev/null +++ b/rust/kernel/dynamic_id_pool.rs @@ -0,0 +1,191 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2025 Google LLC. + +//! Rust API for an ID pool backed by a `Bitmap`. + +use crate::alloc::{AllocError, Flags}; +use crate::bitmap::Bitmap; + +/// Represents a dynamic ID pool backed by a `Bitmap`. +/// +/// Clients acquire and release IDs from zero bits in a bitmap. +/// +/// The ID pool can grow or shrink as needed. It has been designed +/// to support the scenario where users need to control the time +/// of allocation of a new backing bitmap, which may require release +/// of locks. +/// These operations then, are verified to determine if the grow or +/// shrink is sill valid. +/// +/// # Examples +/// +/// Basic usage +/// +/// ``` +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; +/// use kernel::dynamic_id_pool::DynamicIdPool; +/// +/// let mut pool =3D DynamicIdPool::new(64, GFP_KERNEL)?; +/// for i in 0..64 { +/// pool.acquire_next_id(i).ok_or(ENOSPC)?; +/// } +/// assert_eq!(pool.acquire_next_id(63), None); +/// let resizer =3D pool.grow_alloc().alloc(GFP_KERNEL)?; +/// pool.grow(resizer); +/// assert_eq!(pool.acquire_next_id(63), Some(64)); +/// # Ok::<(), Error>(()) +/// ``` +/// +/// Releasing spinlock to grow the pool +/// +/// ``` +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; +/// use kernel::sync::{new_spinlock, SpinLock}; +/// use kernel::dynamic_id_pool::DynamicIdPool; +/// +/// struct Example { +/// pool: DynamicIdPool +/// } +/// +/// fn get_id_maybe_alloc(s: &SpinLock) -> Result { +/// let mut guard =3D s.lock(); +/// let mut resizer =3D None; +/// loop { +/// match guard.pool.acquire_next_id(0) { +/// index @ Some(_) =3D> return Ok(index), +/// None =3D> { +/// let alloc_request =3D guard.pool.grow_alloc(); +/// drop(guard); +/// let resizer =3D alloc_request.alloc(GFP_KERNEL)?; +/// guard =3D s.lock(); +/// guard.pool.grow(resizer) +/// } +/// } +/// } +/// } +/// ``` +pub struct DynamicIdPool { + map: Bitmap, +} + +/// Returned when the `DynamicIdPool` should change size. +pub struct AllocRequest { + nbits: usize, +} + +/// Contains an allocated `Bitmap` for resizing `DynamicIdPool`. +pub struct PoolResizer { + new: Bitmap, +} + +impl AllocRequest { + /// Allocates a new `Bitmap` for `DynamicIdPool`. + pub fn alloc(&self, flags: Flags) -> Result { + let new =3D Bitmap::new(self.nbits, flags)?; + Ok(PoolResizer { new }) + } +} + +/// Minimum size we want to use for our backing `Bitmap`. +const NBITS_MIN: usize =3D bindings::BITS_PER_LONG as usize; + +impl DynamicIdPool { + /// + #[inline] + pub fn new(mut nbits: usize, flags: Flags) -> Result= { + if nbits < NBITS_MIN { + nbits =3D NBITS_MIN + } + let map =3D Bitmap::new(nbits, flags)?; + Ok(Self { map }) + } + + /// Returns how many IDs this pool can currently have. + #[inline] + pub fn len(&self) -> usize { + self.map.len() + } + + /// Returns an `AllocRequest` if the can be shrunk, or None if not pos= sible. + #[inline] + pub fn shrink_alloc(&self) -> Option { + let len =3D self.map.len(); + if len =3D=3D NBITS_MIN { + return None + } + /* + * Determine if the bitmap can shrink based on the position of + * its last set bit. If the bit is within the first quarter of + * the bitmap then shrinking is possible. In this case, the + * bitmap should shrink to half its current size. + */ + match self.map.find_last_bit() { + Some(bit) =3D> { + if bit < (len >> 2) { + Some(AllocRequest { nbits: len >> 1 }) + } else { + None + } + } + None =3D> Some(AllocRequest { nbits: NBITS_MIN }), + } + } + + /// Shrinks pool by using a new `Bitmap`, if still possible. + #[inline] + pub fn shrink(&mut self, mut resizer: PoolResizer) { + // Verify that shrinking is still possible. The `resizer` + // bitmap might have been allocated without locks, so this call + // could now be outdated. In this case, drop `resizer` and move on. + if let Some(AllocRequest { nbits }) =3D self.shrink_alloc() { + if nbits <=3D resizer.new.len() { + resizer.new.copy_prefix_from_bitmap(&self.map); + self.map =3D resizer.new; + return; + } + } + } + + /// Returns an `AllocRequest` for growing this `DynamicIdPool`. + #[inline] + pub fn grow_alloc(&self) -> AllocRequest { + AllocRequest { + nbits: self.map.len() << 1, + } + } + + /// Grows pool by using a new `Bitmap`, if still necessary. + #[inline] + pub fn grow(&mut self, mut resizer: PoolResizer) { + // `resizer` bitmap might have been allocated without locks, + // so this call could now be outdated. In this case, drop + // `resizer` and move on. + if resizer.new.len() <=3D self.map.len() { + return; + } + + resizer.new.copy_from_bitmap_and_extend(&self.map); + self.map =3D resizer.new; + } + + /// Acquires a new ID by finding and setting the next zero bit in the + /// bitmap. Upon success, returns its index. Otherwise, returns `None` + /// to indicate that a `grow_alloc` is needed. + #[inline] + pub fn acquire_next_id(&mut self, offset: usize) -> Option { + match self.map.find_next_zero_bit(offset) { + res @ Some(nr) =3D> { + self.map.set_bit(nr); + res + } + None =3D> None, + } + } + + /// Releases an ID. + #[inline] + pub fn release_id(&mut self, id: usize) { + self.map.clear_bit(id); + } +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index be06ffc47473..4789e707dacc 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -47,6 +47,7 @@ pub mod device_id; pub mod devres; pub mod driver; +pub mod dynamic_id_pool; pub mod error; #[cfg(CONFIG_RUST_FW_LOADER_ABSTRACTIONS)] pub mod firmware; --=20 2.49.0.rc1.451.g8f38331e32-goog