* [PATCH 1/2] rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants
2025-10-20 13:33 [PATCH 0/2] Use Rust Bitmap from Rust Binder driver Alice Ryhl
@ 2025-10-20 13:33 ` Alice Ryhl
2025-10-20 14:13 ` Burak Emir
2025-10-20 14:18 ` Danilo Krummrich
2025-10-20 13:33 ` [PATCH 2/2] rust_binder: use bitmap for allocation of handles Alice Ryhl
1 sibling, 2 replies; 7+ messages in thread
From: Alice Ryhl @ 2025-10-20 13:33 UTC (permalink / raw)
To: Greg Kroah-Hartman, Yury Norov
Cc: Arve Hjønnevåg, Todd Kjos, Martijn Coenen,
Joel Fernandes, Christian Brauner, Carlos Llamas,
Suren Baghdasaryan, Burak Emir, Miguel Ojeda, Boqun Feng,
Gary Guo, Björn Roy Baron, Benno Lossin, Andreas Hindborg,
Trevor Gross, Danilo Krummrich, rust-for-linux, linux-kernel,
Alice Ryhl
To avoid hard-coding these values in drivers, define constants for them
that drivers can reference.
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
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..15fa23b45054b9272415fcc000e3e3b52c74d7c1 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -149,14 +149,14 @@ macro_rules! bitmap_assert_return {
///
/// # Invariants
///
-/// * `nbits` is `<= i32::MAX` and never changes.
+/// * `nbits` is `<= MAX_LEN`.
/// * if `nbits <= 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 `<= i32::MAX`.
+ /// Length of this bitmap. Must be `<= MAX_LEN`.
nbits: usize,
}
@@ -226,10 +226,16 @@ fn drop(&mut self) {
}
impl BitmapVec {
+ /// The maximum possible length of a `BitmapVec`.
+ pub const MAX_LEN: usize = i32::MAX as usize;
+
+ /// The maximum length that avoids allocating.
+ pub const NO_ALLOC_MAX_LEN: usize = BITS_PER_LONG;
+
/// Constructs a new [`BitmapVec`].
///
/// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. 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<Self, AllocError> {
if nbits <= BITS_PER_LONG {
@@ -238,11 +244,11 @@ pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
nbits,
});
}
- if nbits > i32::MAX.try_into().unwrap() {
+ if nbits > Self::MAX_LEN {
return Err(AllocError);
}
let nbits_u32 = u32::try_from(nbits).unwrap();
- // SAFETY: `BITS_PER_LONG < nbits` and `nbits <= i32::MAX`.
+ // SAFETY: `BITS_PER_LONG < nbits` and `nbits <= MAX_LEN`.
let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
let ptr = NonNull::new(ptr).ok_or(AllocError)?;
// INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.
--
2.51.0.915.g61a8936c21-goog
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH 2/2] rust_binder: use bitmap for allocation of handles
2025-10-20 13:33 [PATCH 0/2] Use Rust Bitmap from Rust Binder driver Alice Ryhl
2025-10-20 13:33 ` [PATCH 1/2] rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants Alice Ryhl
@ 2025-10-20 13:33 ` Alice Ryhl
2025-10-20 15:06 ` Burak Emir
1 sibling, 1 reply; 7+ messages in thread
From: Alice Ryhl @ 2025-10-20 13:33 UTC (permalink / raw)
To: Greg Kroah-Hartman, Yury Norov
Cc: Arve Hjønnevåg, Todd Kjos, Martijn Coenen,
Joel Fernandes, Christian Brauner, Carlos Llamas,
Suren Baghdasaryan, Burak Emir, Miguel Ojeda, Boqun Feng,
Gary Guo, Björn Roy Baron, Benno Lossin, Andreas Hindborg,
Trevor Gross, Danilo Krummrich, rust-for-linux, linux-kernel,
Alice Ryhl
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 <aliceryhl@google.com>
---
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/process.rs
index f13a747e784c84a0fb09cbf47442712106eba07c..357ba1b577c73ad3f2b525a8573424420577e92d 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -16,6 +16,7 @@
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<u32, ListArc<NodeRefInfo, { NodeRefInfo::LIST_PROC }>>,
+ /// 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 usize is the address of
/// the underlying `Node` struct as returned by `Node::global_id`.
by_node: RBTree<usize, u32>,
@@ -378,13 +381,56 @@ struct ProcessNodeRefs {
}
impl ProcessNodeRefs {
- fn new() -> Self {
- Self {
+ fn new() -> Result<Self> {
+ Ok(Self {
by_handle: RBTree::new(),
+ handle_present: BitmapVec::new(BitmapVec::NO_ALLOC_MAX_LEN, GFP_KERNEL)?,
by_node: RBTree::new(),
freeze_listeners: RBTree::new(),
+ })
+ }
+
+ fn bitmap_shrink_len(&self) -> Option<usize> {
+ let nbits = self.handle_present.len();
+
+ if nbits <= BitmapVec::NO_ALLOC_MAX_LEN {
+ return None;
+ }
+
+ match self.handle_present.last_bit() {
+ Some(bit) if bit < nbits >> 2 => Some(nbits >> 1),
+ None => Some(BitmapVec::NO_ALLOC_MAX_LEN),
+ _ => None,
+ }
+ }
+
+ fn bitmap_grow_len(&self) -> Option<usize> {
+ let new_len = 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) = self.bitmap_shrink_len() {
+ if new_map.len() == 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 = new_map;
+ }
}
/// A process using binder.
@@ -471,7 +517,7 @@ fn new(ctx: Arc<Context>, cred: ARef<Credential>) -> Result<Arc<Self>> {
cred,
inner <- kernel::new_spinlock!(ProcessInner::new(), "Process::inner"),
pages <- ShrinkablePageRange::new(&super::BINDER_SHRINKER),
- node_refs <- kernel::new_mutex!(ProcessNodeRefs::new(), "Process::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<u32> {
{
let mut refs = self.node_refs.lock();
@@ -794,7 +840,34 @@ pub(crate) fn insert_or_update_handle(
let reserve2 = RBTreeNodeReservation::new(GFP_KERNEL)?;
let info = UniqueArc::new_uninit(GFP_KERNEL)?;
- let mut refs = self.node_refs.lock();
+ let mut refs_lock = self.node_refs.lock();
+ let mut refs = &mut *refs_lock;
+
+ let (handle, by_handle_slot) = loop {
+ // ID 0 may only be used by the manager.
+ let start = if is_manager { 0 } else { 1 };
+
+ if let Some(handle) = refs.handle_present.next_zero_bit(start) {
+ let handle_u32 = u32::try_from(handle).map_err(|_| ENOMEM)?;
+ match refs.by_handle.entry(handle_u32) {
+ rbtree::Entry::Vacant(entry) => break (handle_u32, entry),
+ rbtree::Entry::Occupied(_) => {
+ pr_err!("Detected mismatch between handle_present and by_handle");
+ refs.handle_present.set_bit(handle);
+ continue;
+ }
+ }
+ }
+
+ let new_len = refs.bitmap_grow_len().ok_or(ENOMEM)?;
+ drop(refs_lock);
+ let new_bitmap = BitmapVec::new(new_len, GFP_KERNEL)?;
+ refs_lock = self.node_refs.lock();
+ refs = &mut *refs_lock;
+ if refs.handle_present.len() < new_len {
+ refs.replace_bitmap(new_bitmap);
+ }
+ };
// Do a lookup again as node may have been inserted before the lock was reacquired.
if let Some(handle_ref) = refs.by_node.get(&node_ref.node.global_id()) {
@@ -804,20 +877,9 @@ pub(crate) fn insert_or_update_handle(
return Ok(handle);
}
- // Find id.
- let mut target: u32 = if is_mananger { 0 } else { 1 };
- for handle in refs.by_handle.keys() {
- if *handle > target {
- break;
- }
- if *handle == target {
- target = target.checked_add(1).ok_or(ENOMEM)?;
- }
- }
-
let gid = node_ref.node.global_id();
let (info_proc, info_node) = {
- let info_init = NodeRefInfo::new(node_ref, target, self.into());
+ let info_init = NodeRefInfo::new(node_ref, handle, self.into());
match info.pin_init_with(info_init) {
Ok(info) => 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) };
- 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)
}
pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult<NodeRef> {
@@ -905,6 +967,14 @@ pub(crate) fn update_ref(
let id = 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) = refs.bitmap_shrink_len() {
+ drop(refs);
+ let new_bitmap = BitmapVec::new(shrink_len, GFP_KERNEL)?;
+ refs = self.node_refs.lock();
+ refs.try_shrink_bitmap(new_bitmap);
+ }
}
} else {
// All refs are cleared in process exit, so this warning is expected in that case.
--
2.51.0.915.g61a8936c21-goog
^ permalink raw reply related [flat|nested] 7+ messages in thread