rust_binder: add Rust Binder driver

We're generally not proponents of rewrites (nasty uncomfortable things
that make you late for dinner!). So why rewrite Binder?

Binder has been evolving over the past 15+ years to meet the evolving
needs of Android. Its responsibilities, expectations, and complexity
have grown considerably during that time. While we expect Binder to
continue to evolve along with Android, there are a number of factors
that currently constrain our ability to develop/maintain it. Briefly
those are:

1. Complexity: Binder is at the intersection of everything in Android and
   fulfills many responsibilities beyond IPC. It has become many things
   to many people, and due to its many features and their interactions
   with each other, its complexity is quite high. In just 6kLOC it must
   deliver transactions to the right threads. It must correctly parse
   and translate the contents of transactions, which can contain several
   objects of different types (e.g., pointers, fds) that can interact
   with each other. It controls the size of thread pools in userspace,
   and ensures that transactions are assigned to threads in ways that
   avoid deadlocks where the threadpool has run out of threads. It must
   track refcounts of objects that are shared by several processes by
   forwarding refcount changes between the processes correctly.  It must
   handle numerous error scenarios and it combines/nests 13 different
   locks, 7 reference counters, and atomic variables. Finally, It must
   do all of this as fast and efficiently as possible. Minor performance
   regressions can cause a noticeably degraded user experience.

2. Things to improve: Thousand-line functions [1], error-prone error
   handling [2], and confusing structure can occur as a code base grows
   organically. After more than a decade of development, this codebase
   could use an overhaul.

[1]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/android/binder.c?h=v6.5#n2896
[2]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/android/binder.c?h=v6.5#n3658

3. Security critical: Binder is a critical part of Android's sandboxing
   strategy. Even Android's most de-privileged sandboxes (e.g. the
   Chrome renderer, or SW Codec) have direct access to Binder. More than
   just about any other component, it's important that Binder provide
   robust security, and itself be robust against security
   vulnerabilities.

It's #1 (high complexity) that has made continuing to evolve Binder and
resolving #2 (tech debt) exceptionally difficult without causing #3
(security issues). For Binder to continue to meet Android's needs, we
need better ways to manage (and reduce!) complexity without increasing
the risk.

The biggest change is obviously the choice of programming language. We
decided to use Rust because it directly addresses a number of the
challenges within Binder that we have faced during the last years. It
prevents mistakes with ref counting, locking, bounds checking, and also
does a lot to reduce the complexity of error handling. Additionally,
we've been able to use the more expressive type system to encode the
ownership semantics of the various structs and pointers, which takes the
complexity of managing object lifetimes out of the hands of the
programmer, reducing the risk of use-after-frees and similar problems.

Rust has many different pointer types that it uses to encode ownership
semantics into the type system, and this is probably one of the most
important aspects of how it helps in Binder. The Binder driver has a lot
of different objects that have complex ownership semantics; some
pointers own a refcount, some pointers have exclusive ownership, and
some pointers just reference the object and it is kept alive in some
other manner. With Rust, we can use a different pointer type for each
kind of pointer, which enables the compiler to enforce that the
ownership semantics are implemented correctly.

Another useful feature is Rust's error handling. Rust allows for more
simplified error handling with features such as destructors, and you get
compilation failures if errors are not properly handled. This means that
even though Rust requires you to spend more lines of code than C on
things such as writing down invariants that are left implicit in C, the
Rust driver is still slightly smaller than C binder: Rust is 5.5kLOC and
C is 5.8kLOC. (These numbers are excluding blank lines, comments,
binderfs, and any debugging facilities in C that are not yet implemented
in the Rust driver. The numbers include abstractions in rust/kernel/
that are unlikely to be used by other drivers than Binder.)

Although this rewrite completely rethinks how the code is structured and
how assumptions are enforced, we do not fundamentally change *how* the
driver does the things it does. A lot of careful thought has gone into
the existing design. The rewrite is aimed rather at improving code
health, structure, readability, robustness, security, maintainability
and extensibility. We also include more inline documentation, and
improve how assumptions in the code are enforced. Furthermore, all
unsafe code is annotated with a SAFETY comment that explains why it is
correct.

We have left the binderfs filesystem component in C. Rewriting it in
Rust would be a large amount of work and requires a lot of bindings to
the file system interfaces. Binderfs has not historically had the same
challenges with security and complexity, so rewriting binderfs seems to
have lower value than the rest of Binder.

Correctness and feature parity
------------------------------

Rust binder passes all tests that validate the correctness of Binder in
the Android Open Source Project. We can boot a device, and run a variety
of apps and functionality without issues. We have performed this both on
the Cuttlefish Android emulator device, and on a Pixel 6 Pro.

As for feature parity, Rust binder currently implements all features
that C binder supports, with the exception of some debugging facilities.
The missing debugging facilities will be added before we submit the Rust
implementation upstream.

Tracepoints
-----------

I did not include all of the tracepoints as I felt that the mechansim
for making C access fields of Rust structs should be discussed on list
separately. I also did not include the support for building Rust Binder
as a module since that requires exporting a bunch of additional symbols
on the C side.

Original RFC Link with old benchmark numbers:
	https://lore.kernel.org/r/20231101-rust-binder-v1-0-08ba9197f637@google.com

Co-developed-by: Wedson Almeida Filho <wedsonaf@gmail.com>
Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
Co-developed-by: Matt Gilbride <mattgilbride@google.com>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Acked-by: Carlos Llamas <cmllamas@google.com>
Acked-by: Paul Moore <paul@paul-moore.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Link: https://lore.kernel.org/r/20250919-rust-binder-v2-1-a384b09f28dd@google.com
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

1 files changed, 251 insertions, 0 deletions

diff --git a/drivers/android/binder/range_alloc/array.rs b/drivers/android/binder/range_alloc/array.rs
new file mode 100644
index 000000000000..07e1dec2ce63
--- /dev/null
+++ b/drivers/android/binder/range_alloc/array.rs
@@ -0,0 +1,251 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2025 Google LLC.
+
+use kernel::{
+    page::{PAGE_MASK, PAGE_SIZE},
+    prelude::*,
+    seq_file::SeqFile,
+    seq_print,
+    task::Pid,
+};
+
+use crate::range_alloc::{DescriptorState, FreedRange, Range};
+
+/// Keeps track of allocations in a process' mmap.
+///
+/// Each process has an mmap where the data for incoming transactions will be placed. This struct
+/// keeps track of allocations made in the mmap. For each allocation, we store a descriptor that
+/// has metadata related to the allocation. We also keep track of available free space.
+pub(super) struct ArrayRangeAllocator<T> {
+    /// This stores all ranges that are allocated. Unlike the tree based allocator, we do *not*
+    /// store the free ranges.
+    ///
+    /// Sorted by offset.
+    pub(super) ranges: KVec<Range<T>>,
+    size: usize,
+    free_oneway_space: usize,
+}
+
+struct FindEmptyRes {
+    /// Which index in `ranges` should we insert the new range at?
+    ///
+    /// Inserting the new range at this index keeps `ranges` sorted.
+    insert_at_idx: usize,
+    /// Which offset should we insert the new range at?
+    insert_at_offset: usize,
+}
+
+impl<T> ArrayRangeAllocator<T> {
+    pub(crate) fn new(size: usize, alloc: EmptyArrayAlloc<T>) -> Self {
+        Self {
+            ranges: alloc.ranges,
+            size,
+            free_oneway_space: size / 2,
+        }
+    }
+
+    pub(crate) fn free_oneway_space(&self) -> usize {
+        self.free_oneway_space
+    }
+
+    pub(crate) fn count_buffers(&self) -> usize {
+        self.ranges.len()
+    }
+
+    pub(crate) fn total_size(&self) -> usize {
+        self.size
+    }
+
+    pub(crate) fn is_full(&self) -> bool {
+        self.ranges.len() == self.ranges.capacity()
+    }
+
+    pub(crate) fn debug_print(&self, m: &SeqFile) -> Result<()> {
+        for range in &self.ranges {
+            seq_print!(
+                m,
+                "  buffer {}: {} size {} pid {} oneway {}",
+                0,
+                range.offset,
+                range.size,
+                range.state.pid(),
+                range.state.is_oneway(),
+            );
+            if let DescriptorState::Reserved(_) = range.state {
+                seq_print!(m, " reserved\n");
+            } else {
+                seq_print!(m, " allocated\n");
+            }
+        }
+        Ok(())
+    }
+
+    /// Find somewhere to put a new range.
+    ///
+    /// Unlike the tree implementation, we do not bother to find the smallest gap. The idea is that
+    /// fragmentation isn't a big issue when we don't have many ranges.
+    ///
+    /// Returns the index that the new range should have in `self.ranges` after insertion.
+    fn find_empty_range(&self, size: usize) -> Option<FindEmptyRes> {
+        let after_last_range = self.ranges.last().map(Range::endpoint).unwrap_or(0);
+
+        if size <= self.total_size() - after_last_range {
+            // We can put the range at the end, so just do that.
+            Some(FindEmptyRes {
+                insert_at_idx: self.ranges.len(),
+                insert_at_offset: after_last_range,
+            })
+        } else {
+            let mut end_of_prev = 0;
+            for (i, range) in self.ranges.iter().enumerate() {
+                // Does it fit before the i'th range?
+                if size <= range.offset - end_of_prev {
+                    return Some(FindEmptyRes {
+                        insert_at_idx: i,
+                        insert_at_offset: end_of_prev,
+                    });
+                }
+                end_of_prev = range.endpoint();
+            }
+            None
+        }
+    }
+
+    pub(crate) fn reserve_new(
+        &mut self,
+        debug_id: usize,
+        size: usize,
+        is_oneway: bool,
+        pid: Pid,
+    ) -> Result<usize> {
+        // Compute new value of free_oneway_space, which is set only on success.
+        let new_oneway_space = if is_oneway {
+            match self.free_oneway_space.checked_sub(size) {
+                Some(new_oneway_space) => new_oneway_space,
+                None => return Err(ENOSPC),
+            }
+        } else {
+            self.free_oneway_space
+        };
+
+        let FindEmptyRes {
+            insert_at_idx,
+            insert_at_offset,
+        } = self.find_empty_range(size).ok_or(ENOSPC)?;
+        self.free_oneway_space = new_oneway_space;
+
+        let new_range = Range {
+            offset: insert_at_offset,
+            size,
+            state: DescriptorState::new(is_oneway, debug_id, pid),
+        };
+        // Insert the value at the given index to keep the array sorted.
+        self.ranges
+            .insert_within_capacity(insert_at_idx, new_range)
+            .ok()
+            .unwrap();
+
+        Ok(insert_at_offset)
+    }
+
+    pub(crate) fn reservation_abort(&mut self, offset: usize) -> Result<FreedRange> {
+        // This could use a binary search, but linear scans are usually faster for small arrays.
+        let i = self
+            .ranges
+            .iter()
+            .position(|range| range.offset == offset)
+            .ok_or(EINVAL)?;
+        let range = &self.ranges[i];
+
+        if let DescriptorState::Allocated(_) = range.state {
+            return Err(EPERM);
+        }
+
+        let size = range.size;
+        let offset = range.offset;
+
+        if range.state.is_oneway() {
+            self.free_oneway_space += size;
+        }
+
+        // This computes the range of pages that are no longer used by *any* allocated range. The
+        // caller will mark them as unused, which means that they can be freed if the system comes
+        // under memory pressure.
+        let mut freed_range = FreedRange::interior_pages(offset, size);
+        #[expect(clippy::collapsible_if)] // reads better like this
+        if offset % PAGE_SIZE != 0 {
+            if i == 0 || self.ranges[i - 1].endpoint() <= (offset & PAGE_MASK) {
+                freed_range.start_page_idx -= 1;
+            }
+        }
+        if range.endpoint() % PAGE_SIZE != 0 {
+            let page_after = (range.endpoint() & PAGE_MASK) + PAGE_SIZE;
+            if i + 1 == self.ranges.len() || page_after <= self.ranges[i + 1].offset {
+                freed_range.end_page_idx += 1;
+            }
+        }
+
+        self.ranges.remove(i)?;
+        Ok(freed_range)
+    }
+
+    pub(crate) fn reservation_commit(&mut self, offset: usize, data: &mut Option<T>) -> Result {
+        // This could use a binary search, but linear scans are usually faster for small arrays.
+        let range = self
+            .ranges
+            .iter_mut()
+            .find(|range| range.offset == offset)
+            .ok_or(ENOENT)?;
+
+        let DescriptorState::Reserved(reservation) = &range.state else {
+            return Err(ENOENT);
+        };
+
+        range.state = DescriptorState::Allocated(reservation.clone().allocate(data.take()));
+        Ok(())
+    }
+
+    pub(crate) fn reserve_existing(&mut self, offset: usize) -> Result<(usize, usize, Option<T>)> {
+        // This could use a binary search, but linear scans are usually faster for small arrays.
+        let range = self
+            .ranges
+            .iter_mut()
+            .find(|range| range.offset == offset)
+            .ok_or(ENOENT)?;
+
+        let DescriptorState::Allocated(allocation) = &mut range.state else {
+            return Err(ENOENT);
+        };
+
+        let data = allocation.take();
+        let debug_id = allocation.reservation.debug_id;
+        range.state = DescriptorState::Reserved(allocation.reservation.clone());
+        Ok((range.size, debug_id, data))
+    }
+
+    pub(crate) fn take_for_each<F: Fn(usize, usize, usize, Option<T>)>(&mut self, callback: F) {
+        for range in self.ranges.iter_mut() {
+            if let DescriptorState::Allocated(allocation) = &mut range.state {
+                callback(
+                    range.offset,
+                    range.size,
+                    allocation.reservation.debug_id,
+                    allocation.data.take(),
+                );
+            }
+        }
+    }
+}
+
+pub(crate) struct EmptyArrayAlloc<T> {
+    ranges: KVec<Range<T>>,
+}
+
+impl<T> EmptyArrayAlloc<T> {
+    pub(crate) fn try_new(capacity: usize) -> Result<Self> {
+        Ok(Self {
+            ranges: KVec::with_capacity(capacity, GFP_KERNEL)?,
+        })
+    }
+}