selftests/bpf: Add a test for objects stuck in free_by_rcu_ttracegrafted

Delete all elements of BPF_F_NO_PREALLOC hash map in one batch. The first
free_bulk() starts RCU tasks trace GP and the rest of the elements are
freed while it's in flight. Wait for call_rcu_ttrace_in_progress to clear
in bpf_mem_cache of every cpu and check that free_by_rcu_ttrace and
waiting_for_gp_ttrace lists are empty.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/20260930095920.601738-4-alexei.starovoitov@gmail.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

1 files changed, 590 insertions, 0 deletions

diff --git a/drivers/android/binder/transaction.rs b/drivers/android/binder/transaction.rs
new file mode 100644
index 000000000..245f1556b
--- /dev/null
+++ b/drivers/android/binder/transaction.rs
@@ -0,0 +1,590 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2025 Google LLC.
+
+use kernel::{
+    net::netlink::GENLMSG_DEFAULT_SIZE,
+    prelude::*,
+    seq_file::SeqFile,
+    seq_print,
+    sync::atomic::{ordering::Relaxed, Atomic},
+    sync::{Arc, SpinLock},
+    task::{Kuid, Pid},
+    time::{Instant, Monotonic},
+    types::ScopeGuard,
+    uapi,
+};
+
+use crate::{
+    allocation::{Allocation, TranslatedFds},
+    defs::*,
+    error::{BinderError, BinderResult},
+    netlink::Report,
+    node::{Node, NodeRef},
+    process::{Process, ProcessInner},
+    ptr_align,
+    thread::{PushWorkRes, Thread},
+    BinderReturnWriter, DArc, DLArc, DTRWrap, DeliverToRead,
+};
+
+kernel::impl_flags!(
+    /// Represents multiple transaction flags.
+    #[derive(Debug, Clone, Default, Copy, PartialEq, Eq, Zeroable)]
+    pub struct TransactionFlags(u32);
+
+    /// Represents a single transaction flag.
+    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
+    pub enum TransactionFlag {
+        OneWay = TF_ONE_WAY,
+        AcceptFds = TF_ACCEPT_FDS,
+        ClearBuf = TF_CLEAR_BUF,
+        UpdateTxn = TF_UPDATE_TXN,
+    }
+);
+
+impl TransactionFlags {
+    /// Creates a `TransactionFlags` from a raw `u32` value.
+    pub(crate) fn from_bits(bits: u32) -> Self {
+        Self(bits)
+    }
+
+    /// Checks if the Oneway flag is set.
+    pub(crate) fn is_oneway(self) -> bool {
+        self.contains(TransactionFlag::OneWay)
+    }
+}
+
+#[derive(Zeroable)]
+pub(crate) struct TransactionInfo {
+    pub(crate) from_pid: Pid,
+    pub(crate) from_tid: Pid,
+    pub(crate) to_pid: Pid,
+    pub(crate) to_tid: Pid,
+    pub(crate) code: u32,
+    pub(crate) flags: TransactionFlags,
+    pub(crate) data_ptr: UserPtr,
+    pub(crate) data_size: usize,
+    pub(crate) offsets_ptr: UserPtr,
+    pub(crate) offsets_size: usize,
+    pub(crate) buffers_size: usize,
+    pub(crate) target_handle: u32,
+    pub(crate) errno: i32,
+    pub(crate) reply: u32,
+    pub(crate) oneway_spam_suspect: bool,
+    pub(crate) is_reply: bool,
+    pub(crate) debug_id: usize,
+}
+
+impl TransactionInfo {
+    #[inline]
+    pub(crate) fn is_oneway(&self) -> bool {
+        self.flags.is_oneway()
+    }
+
+    pub(crate) fn report_netlink(&self, reply: u32, ctx: &crate::Context) {
+        if let Err(err) = self.report_netlink_inner(reply, ctx) {
+            pr_warn!(
+                "{}:{} netlink report failed: {err:?}\n",
+                self.from_pid,
+                self.from_tid
+            );
+        }
+    }
+
+    fn report_netlink_inner(&self, reply: u32, ctx: &crate::Context) -> kernel::error::Result {
+        if !Report::has_listeners() {
+            return Ok(());
+        }
+        let mut report = Report::new(GENLMSG_DEFAULT_SIZE, 0, 0, GFP_KERNEL)?;
+
+        report.error(reply)?;
+        report.context(&ctx.name)?;
+        report.from_pid(self.from_pid as u32)?;
+        report.from_tid(self.from_tid as u32)?;
+        if self.to_pid != 0 {
+            report.to_pid(self.to_pid as u32)?;
+        }
+        if self.to_tid != 0 {
+            report.to_tid(self.to_tid as u32)?;
+        }
+
+        if self.is_reply {
+            report.is_reply()?;
+        }
+        report.flags(u32::from(self.flags))?;
+        report.code(self.code)?;
+        report.data_size(self.data_size as u32)?;
+
+        report.multicast(0, GFP_KERNEL)?;
+        Ok(())
+    }
+}
+
+use core::mem::offset_of;
+use kernel::bindings::rb_transaction_layout;
+pub(crate) const TRANSACTION_LAYOUT: rb_transaction_layout = rb_transaction_layout {
+    debug_id: offset_of!(Transaction, debug_id),
+    code: offset_of!(Transaction, code),
+    flags: offset_of!(Transaction, flags),
+    from_thread: offset_of!(Transaction, from),
+    to_proc: offset_of!(Transaction, to),
+    target_node: offset_of!(Transaction, target_node),
+};
+
+#[pin_data(PinnedDrop)]
+pub(crate) struct Transaction {
+    pub(crate) debug_id: usize,
+    target_node: Option<DArc<Node>>,
+    pub(crate) from_parent: Option<DArc<Transaction>>,
+    pub(crate) from: Arc<Thread>,
+    pub(crate) to: Arc<Process>,
+    #[pin]
+    allocation: SpinLock<Option<Allocation>>,
+    is_outstanding: Atomic<bool>,
+    code: u32,
+    pub(crate) flags: TransactionFlags,
+    data_size: usize,
+    offsets_size: usize,
+    data_address: usize,
+    sender_euid: Kuid,
+    txn_security_ctx_off: Option<usize>,
+    start_time: Instant<Monotonic>,
+}
+
+kernel::list::impl_list_arc_safe! {
+    impl ListArcSafe<0> for Transaction { untracked; }
+}
+
+impl Transaction {
+    pub(crate) fn new(
+        node_ref: NodeRef,
+        from_parent: Option<DArc<Transaction>>,
+        from: &Arc<Thread>,
+        info: &mut TransactionInfo,
+    ) -> BinderResult<DLArc<Self>> {
+        let allow_fds = node_ref.node.flags & FLAT_BINDER_FLAG_ACCEPTS_FDS != 0;
+        let txn_security_ctx = node_ref.node.flags & FLAT_BINDER_FLAG_TXN_SECURITY_CTX != 0;
+        let mut txn_security_ctx_off = if txn_security_ctx { Some(0) } else { None };
+        let to = node_ref.node.owner.clone();
+        let mut alloc = match from.copy_transaction_data(
+            to.clone(),
+            info,
+            info.debug_id,
+            allow_fds,
+            txn_security_ctx_off.as_mut(),
+        ) {
+            Ok(alloc) => alloc,
+            Err(err) => {
+                if !err.is_dead() {
+                    pr_warn!("Failure in copy_transaction_data: {:?}", err);
+                }
+                return Err(err);
+            }
+        };
+        if info.is_oneway() {
+            if from_parent.is_some() {
+                pr_warn!("Oneway transaction should not be in a transaction stack.");
+                return Err(EINVAL.into());
+            }
+            alloc.set_info_oneway_node(node_ref.node.clone());
+        }
+        if info.flags.contains(TransactionFlag::ClearBuf) {
+            alloc.set_info_clear_on_drop();
+        }
+        let target_node = node_ref.node.clone();
+        alloc.set_info_target_node(node_ref);
+        let data_address = alloc.ptr;
+
+        Ok(DTRWrap::arc_pin_init(pin_init!(Transaction {
+            debug_id: info.debug_id,
+            target_node: Some(target_node),
+            from_parent,
+            sender_euid: Kuid::current_euid(),
+            from: from.clone(),
+            to,
+            code: info.code,
+            flags: info.flags,
+            data_size: info.data_size,
+            offsets_size: info.offsets_size,
+            data_address,
+            allocation <- kernel::new_spinlock!(Some(alloc.success()), "Transaction::new"),
+            is_outstanding: Atomic::new(false),
+            txn_security_ctx_off,
+            start_time: Instant::now(),
+        }))?)
+    }
+
+    pub(crate) fn new_reply(
+        from: &Arc<Thread>,
+        to: Arc<Process>,
+        info: &mut TransactionInfo,
+        allow_fds: bool,
+    ) -> BinderResult<DLArc<Self>> {
+        let mut alloc =
+            match from.copy_transaction_data(to.clone(), info, info.debug_id, allow_fds, None) {
+                Ok(alloc) => alloc,
+                Err(err) => {
+                    pr_warn!("Failure in copy_transaction_data: {:?}", err);
+                    return Err(err);
+                }
+            };
+        if info.flags.contains(TransactionFlag::ClearBuf) {
+            alloc.set_info_clear_on_drop();
+        }
+        Ok(DTRWrap::arc_pin_init(pin_init!(Transaction {
+            debug_id: info.debug_id,
+            target_node: None,
+            from_parent: None,
+            sender_euid: Kuid::current_euid(),
+            from: from.clone(),
+            to,
+            code: info.code,
+            flags: info.flags,
+            data_size: info.data_size,
+            offsets_size: info.offsets_size,
+            data_address: alloc.ptr,
+            allocation <- kernel::new_spinlock!(Some(alloc.success()), "Transaction::new"),
+            is_outstanding: Atomic::new(false),
+            txn_security_ctx_off: None,
+            start_time: Instant::now(),
+        }))?)
+    }
+
+    #[inline(never)]
+    pub(crate) fn debug_print_inner(&self, m: &SeqFile, prefix: &str) {
+        seq_print!(
+            m,
+            "{}{}: from {}:{} to {} code {:x} flags {:x} elapsed {}ms",
+            prefix,
+            self.debug_id,
+            self.from.process.task.pid(),
+            self.from.id,
+            self.to.task.pid(),
+            self.code,
+            u32::from(self.flags),
+            self.start_time.elapsed().as_millis(),
+        );
+        if let Some(target_node) = &self.target_node {
+            seq_print!(m, " node {}", target_node.debug_id);
+        }
+        seq_print!(m, " size {}:{}\n", self.data_size, self.offsets_size);
+    }
+
+    /// Determines if the transaction is stacked on top of the given transaction.
+    pub(crate) fn is_stacked_on(&self, onext: &Option<DArc<Self>>) -> bool {
+        match (&self.from_parent, onext) {
+            (None, None) => true,
+            (Some(from_parent), Some(next)) => Arc::ptr_eq(from_parent, next),
+            _ => false,
+        }
+    }
+
+    /// Returns a pointer to the next transaction on the transaction stack, if there is one.
+    pub(crate) fn clone_next(&self) -> Option<DArc<Self>> {
+        Some(self.from_parent.as_ref()?.clone())
+    }
+
+    /// Searches in the transaction stack for a thread that belongs to the target process. This is
+    /// useful when finding a target for a new transaction: if the node belongs to a process that
+    /// is already part of the transaction stack, we reuse the thread.
+    fn find_target_thread(&self) -> Option<Arc<Thread>> {
+        let mut it = &self.from_parent;
+        while let Some(transaction) = it {
+            if Arc::ptr_eq(&transaction.from.process, &self.to) {
+                return Some(transaction.from.clone());
+            }
+            it = &transaction.from_parent;
+        }
+        None
+    }
+
+    /// Searches in the transaction stack for a transaction originating at the given thread.
+    pub(crate) fn find_from(&self, thread: &Thread) -> Option<&DArc<Transaction>> {
+        let mut it = &self.from_parent;
+        while let Some(transaction) = it {
+            if core::ptr::eq(thread, transaction.from.as_ref()) {
+                return Some(transaction);
+            }
+
+            it = &transaction.from_parent;
+        }
+        None
+    }
+
+    pub(crate) fn set_outstanding(&self, to_process: &mut ProcessInner) {
+        // No race because this method is only called once.
+        if !self.is_outstanding.load(Relaxed) {
+            self.is_outstanding.store(true, Relaxed);
+            to_process.add_outstanding_txn();
+        }
+    }
+
+    /// Decrement `outstanding_txns` in `to` if it hasn't already been decremented.
+    fn drop_outstanding_txn(&self) {
+        // No race because this is called at most twice, and one of the calls are in the
+        // destructor, which is guaranteed to not race with any other operations on the
+        // transaction. It also cannot race with `set_outstanding`, since submission happens
+        // before delivery.
+        if self.is_outstanding.load(Relaxed) {
+            self.is_outstanding.store(false, Relaxed);
+            self.to.drop_outstanding_txn();
+        }
+    }
+
+    /// Submits the transaction to a work queue. Uses a thread if there is one in the transaction
+    /// stack, otherwise uses the destination process.
+    ///
+    /// Not used for replies.
+    pub(crate) fn submit(self: DLArc<Self>, info: &mut TransactionInfo) -> BinderResult {
+        // Defined before `process_inner` so that the destructor runs after releasing the lock.
+        let _t_outdated;
+        let _oneway_node;
+
+        let oneway = self.flags.is_oneway();
+        let process = self.to.clone();
+        let mut process_inner = process.inner.lock();
+
+        self.set_outstanding(&mut process_inner);
+
+        if oneway {
+            if let Some(target_node) = self.target_node.clone() {
+                crate::trace::trace_transaction(false, &self, None);
+                if process_inner.is_frozen.is_frozen() {
+                    process_inner.async_recv = true;
+                    if self.flags.contains(TransactionFlag::UpdateTxn) {
+                        if let Some(t_outdated) =
+                            target_node.take_outdated_transaction(&self, &mut process_inner)
+                        {
+                            let mut alloc_guard = t_outdated.allocation.lock();
+                            if let Some(alloc) = (*alloc_guard).as_mut() {
+                                // Take the oneway node to prevent `Allocation::drop` from calling
+                                // `pending_oneway_finished()`, which would be incorrect as this
+                                // transaction is not being submitted.
+                                _oneway_node = alloc.take_oneway_node();
+                            }
+                            drop(alloc_guard);
+                            // Save the transaction to be dropped after locks are released.
+                            _t_outdated = t_outdated;
+                        }
+                    }
+                }
+                match target_node.submit_oneway(self, &mut process_inner) {
+                    Ok(()) => {}
+                    Err((err, work)) => {
+                        drop(process_inner);
+                        // Drop work after releasing process lock.
+                        drop(work);
+                        return Err(err);
+                    }
+                }
+
+                if process_inner.is_frozen.is_frozen() {
+                    return Err(BinderError::new_frozen_oneway());
+                } else {
+                    return Ok(());
+                }
+            } else {
+                pr_err!("Failed to submit oneway transaction to node.");
+            }
+        }
+
+        if process_inner.is_frozen.is_frozen() {
+            process_inner.sync_recv = true;
+            return Err(BinderError::new_frozen());
+        }
+
+        let res = if let Some(thread) = self.find_target_thread() {
+            info.to_tid = thread.id;
+            crate::trace::trace_transaction(false, &self, Some(&thread.task));
+            match thread.push_work(self) {
+                PushWorkRes::Ok => Ok(()),
+                PushWorkRes::OkNotifyPoll => {
+                    process.notify_poll(true);
+                    Ok(())
+                }
+                PushWorkRes::FailedDead(me) => Err((BinderError::new_dead(), me)),
+            }
+        } else {
+            crate::trace::trace_transaction(false, &self, None);
+            process_inner.push_work(&process, self)
+        };
+        drop(process_inner);
+
+        match res {
+            Ok(()) => Ok(()),
+            Err((err, work)) => {
+                // Drop work after releasing process lock.
+                drop(work);
+                Err(err)
+            }
+        }
+    }
+
+    /// Check whether one oneway transaction can supersede another.
+    pub(crate) fn can_replace(&self, old: &Transaction) -> bool {
+        if self.from.process.task.pid() != old.from.process.task.pid() {
+            return false;
+        }
+
+        let required = TransactionFlag::OneWay | TransactionFlag::UpdateTxn;
+        if !(self.flags.contains_all(required) && old.flags.contains_all(required)) {
+            return false;
+        }
+
+        let target_node_match = match (self.target_node.as_ref(), old.target_node.as_ref()) {
+            (None, None) => true,
+            (Some(tn1), Some(tn2)) => Arc::ptr_eq(tn1, tn2),
+            _ => false,
+        };
+
+        self.code == old.code && self.flags == old.flags && target_node_match
+    }
+
+    fn prepare_file_list(&self) -> Result<TranslatedFds> {
+        let mut alloc = self.allocation.lock().take().ok_or(ESRCH)?;
+
+        match alloc.translate_fds() {
+            Ok(translated) => {
+                *self.allocation.lock() = Some(alloc);
+                Ok(translated)
+            }
+            Err(err) => {
+                // Free the allocation eagerly.
+                drop(alloc);
+                Err(err)
+            }
+        }
+    }
+}
+
+impl DeliverToRead for Transaction {
+    fn do_work(
+        self: DArc<Self>,
+        thread: &Thread,
+        writer: &mut BinderReturnWriter<'_>,
+    ) -> Result<bool> {
+        let send_failed_reply = ScopeGuard::new(|| {
+            if self.target_node.is_some() && !self.flags.is_oneway() {
+                let reply = Err(BR_FAILED_REPLY);
+                self.from.deliver_reply(reply, &self, None);
+            }
+            self.drop_outstanding_txn();
+        });
+
+        let files = if let Ok(list) = self.prepare_file_list() {
+            list
+        } else {
+            // On failure to process the list, we send a reply back to the sender and ignore the
+            // transaction on the recipient.
+            binder_debug!(
+                FailedTransaction,
+                "transaction {} to {} failed, fd fixups failed, size {}-{}",
+                self.debug_id,
+                self.to.task.pid(),
+                self.data_size,
+                self.offsets_size
+            );
+            return Ok(true);
+        };
+
+        let mut tr_sec = BinderTransactionDataSecctx::default();
+        let tr = tr_sec.tr_data();
+        if let Some(target_node) = &self.target_node {
+            let (ptr, cookie) = target_node.get_id();
+            tr.target.ptr = ptr as uapi::binder_uintptr_t;
+            tr.cookie = cookie as uapi::binder_uintptr_t;
+        };
+        tr.code = self.code;
+        tr.flags = u32::from(self.flags);
+        tr.data_size = self.data_size as uapi::binder_size_t;
+        tr.data.ptr.buffer = self.data_address as uapi::binder_uintptr_t;
+        tr.offsets_size = self.offsets_size as uapi::binder_size_t;
+        if tr.offsets_size > 0 {
+            tr.data.ptr.offsets =
+                (self.data_address + ptr_align(self.data_size).unwrap()) as uapi::binder_uintptr_t;
+        }
+        tr.sender_euid = self.sender_euid.into_uid_in_current_ns();
+        tr.sender_pid = 0;
+        if self.target_node.is_some() && !self.flags.is_oneway() {
+            // Not a reply and not one-way.
+            tr.sender_pid = self.from.process.pid_in_current_ns();
+        }
+        let code = if self.target_node.is_none() {
+            BR_REPLY
+        } else if self.txn_security_ctx_off.is_some() {
+            BR_TRANSACTION_SEC_CTX
+        } else {
+            BR_TRANSACTION
+        };
+
+        // Write the transaction code and data to the user buffer.
+        writer.write_code(code)?;
+        if let Some(off) = self.txn_security_ctx_off {
+            tr_sec.secctx = (self.data_address + off) as u64;
+            writer.write_payload(&tr_sec)?;
+        } else {
+            writer.write_payload(&*tr)?;
+        }
+
+        let mut alloc = self.allocation.lock().take().ok_or(ESRCH)?;
+
+        // Dismiss the completion of transaction with a failure. No failure paths are allowed from
+        // here on out.
+        send_failed_reply.dismiss();
+
+        // Commit files, and set FDs in FDA to be closed on buffer free.
+        let close_on_free = files.commit();
+        alloc.set_info_close_on_free(close_on_free);
+
+        // It is now the user's responsibility to clear the allocation.
+        alloc.keep_alive();
+
+        self.drop_outstanding_txn();
+
+        crate::trace::trace_transaction_received(&self);
+
+        // When this is not a reply and not a oneway transaction, update `current_transaction`. If
+        // it's a reply, `current_transaction` has already been updated appropriately.
+        if self.target_node.is_some() && tr_sec.transaction_data.flags & TF_ONE_WAY == 0 {
+            thread.set_current_transaction(self);
+        }
+
+        Ok(false)
+    }
+
+    fn cancel(self: DArc<Self>) {
+        let allocation = self.allocation.lock().take();
+        drop(allocation);
+
+        // If this is not a reply or oneway transaction, then send a dead reply.
+        if self.target_node.is_some() && !self.flags.is_oneway() {
+            let reply = Err(BR_DEAD_REPLY);
+            self.from.deliver_reply(reply, &self, None);
+        } else {
+            binder_debug!(
+                pid = self.to.task.pid(),
+                DeadTransaction,
+                "undelivered transaction {}, process died",
+                self.debug_id
+            );
+        }
+
+        self.drop_outstanding_txn();
+    }
+
+    fn should_sync_wakeup(&self) -> bool {
+        !self.flags.is_oneway()
+    }
+
+    fn debug_print(&self, m: &SeqFile, _prefix: &str, tprefix: &str) -> Result<()> {
+        self.debug_print_inner(m, tprefix);
+        Ok(())
+    }
+}
+
+#[pinned_drop]
+impl PinnedDrop for Transaction {
+    fn drop(self: Pin<&mut Self>) {
+        self.drop_outstanding_txn();
+    }
+}