[PATCH 1/2] drivers: android: binder: implement CTABS heuristic
From: trieu2.huynh
Date: Tue Jul 14 2026 - 14:37:06 EST
Introduce Cluster/Topology-Aware Binder Selection (CTABS) to optimize
IPC transaction dispatching.
On asymmetric multi-cluster ARM64 architectures (e.g., big.LITTLE), the
default binder thread selection algorithm is topology-blind. This leads
to frequent cross-cluster thread wakeups, resulting in severe CPU cache
misses, interconnect bottlenecks, and unnecessary cache ping-pongs.
To mitigate this latency penalty, CTABS evaluates idle waiting threads
based on their last-executed CPU ID and prioritizing them as follows:
(*) Immediate Selection: Favors threads whose last-executed CPU matches
the caller's CPU exactly, exiting the selection loop early to ensure
optimal L1/L2 cache locality.
(*) Cluster Match: Selects threads that ran on the same CPU cluster as
the caller, maximizing local cache reuse.
(*) Cross-Cluster: Falls back to any available thread across different
clusters if no local affinity is found.
This topology prioritization maximizes CPU cache reuse, minimizes inter-
cluster snooping overhead, and significantly reduces overall transaction
turnaround latency on modern multi-cluster SoCs.
Signed-off-by: trieu2.huynh <trieu2.huynh@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
---
drivers/android/binder.c | 76 +++++++++++++++++++++++++++++--
drivers/android/binder_internal.h | 2 +
2 files changed, 74 insertions(+), 4 deletions(-)
diff --git a/drivers/android/binder.c b/drivers/android/binder.c
index 8f2ef1bd539f..2a7be45368c1 100644
--- a/drivers/android/binder.c
+++ b/drivers/android/binder.c
@@ -42,6 +42,7 @@
#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+#include <linux/cpumask.h>
#include <linux/fdtable.h>
#include <linux/file.h>
#include <linux/freezer.h>
@@ -52,6 +53,7 @@
#include <linux/mutex.h>
#include <linux/nsproxy.h>
#include <linux/poll.h>
+#include <linux/preempt.h>
#include <linux/debugfs.h>
#include <linux/rbtree.h>
#include <linux/sched/signal.h>
@@ -65,6 +67,7 @@
#include <linux/ratelimit.h>
#include <linux/syscalls.h>
#include <linux/task_work.h>
+#include <linux/topology.h>
#include <linux/sizes.h>
#include <linux/ktime.h>
@@ -624,6 +627,56 @@ binder_select_thread_ilocked(struct binder_proc *proc)
return thread;
}
+/* CTABS: topology-aware selection with low-risk load-avoidance heuristic.
+ * Prefer threads with score: 3 (last_cpu == caller_cpu),
+ * 2 (same cluster and task_cpu == last_cpu), 1 (same cluster), else 0.
+ * This uses only thread->last_cpu and task_cpu() and falls back to FIFO.
+ */
+static struct binder_thread *
+binder_select_thread_topology_ilocked(struct binder_proc *proc, int caller_cpu)
+{
+ struct binder_thread *thread, *best = NULL;
+ int caller_cluster = -1;
+ int best_score = -1;
+
+ assert_spin_locked(&proc->inner_lock);
+
+ if ((unsigned int)caller_cpu < (unsigned int)nr_cpu_ids)
+ caller_cluster = topology_cluster_id(caller_cpu);
+
+ list_for_each_entry(thread, &proc->waiting_threads, waiting_thread_node) {
+ int tcpu = READ_ONCE(thread->last_cpu);
+ int score;
+
+ /* Highest priority: exactly the same CPU */
+ if (tcpu == caller_cpu && caller_cpu >= 0) {
+ best = thread;
+ goto found_best;
+ }
+
+ if (caller_cluster >= 0 && (unsigned int)tcpu < (unsigned int)nr_cpu_ids) {
+ /* Prefer threads that last ran on the same cluster */
+ if (topology_cluster_id(tcpu) == caller_cluster) {
+ score = 1;
+ goto check_score;
+ }
+ }
+ score = 0;
+
+check_score:
+ if (score > best_score) {
+ best_score = score;
+ best = thread;
+ }
+ }
+
+found_best:
+ if (best)
+ list_del_init(&best->waiting_thread_node);
+
+ return best;
+}
+
/**
* binder_wakeup_thread_ilocked() - wakes up a thread for doing proc work.
* @proc: process to wake up a thread in
@@ -672,9 +725,12 @@ static void binder_wakeup_thread_ilocked(struct binder_proc *proc,
static void binder_wakeup_proc_ilocked(struct binder_proc *proc)
{
- struct binder_thread *thread = binder_select_thread_ilocked(proc);
+ struct binder_thread *thread =
+ binder_select_thread_topology_ilocked(proc, raw_smp_processor_id());
+ if (!thread)
+ thread = binder_select_thread_ilocked(proc);
- binder_wakeup_thread_ilocked(proc, thread, /* sync = */false);
+ binder_wakeup_thread_ilocked(proc, thread, /* sync = */false);
}
static void binder_set_nice(long nice)
@@ -2877,6 +2933,12 @@ static int binder_proc_transaction(struct binder_transaction *t,
node->has_async_transaction = true;
}
+ /*
+ * Compute caller CPU before acquiring inner_lock to avoid
+ * doing CPU queries while holding spinlocks
+ */
+ int caller_cpu = raw_smp_processor_id();
+
binder_inner_proc_lock(proc);
if (proc->is_frozen) {
frozen = true;
@@ -2891,8 +2953,11 @@ static int binder_proc_transaction(struct binder_transaction *t,
return frozen ? BR_FROZEN_REPLY : BR_DEAD_REPLY;
}
- if (!thread && !pending_async)
- thread = binder_select_thread_ilocked(proc);
+ if (!thread && !pending_async) {
+ thread = binder_select_thread_topology_ilocked(proc, caller_cpu);
+ if (!thread)
+ thread = binder_select_thread_ilocked(proc);
+ }
if (thread) {
binder_enqueue_thread_work_ilocked(thread, &t->work);
@@ -4788,6 +4853,7 @@ static int binder_thread_read(struct binder_proc *proc,
}
thread->looper &= ~BINDER_LOOPER_STATE_WAITING;
+ WRITE_ONCE(thread->last_cpu, raw_smp_processor_id());
if (ret)
return ret;
@@ -5295,6 +5361,8 @@ static struct binder_thread *binder_get_thread_ilocked(
thread->reply_error.work.type = BINDER_WORK_RETURN_ERROR;
thread->reply_error.cmd = BR_OK;
thread->ee.command = BR_OK;
+ /* CTABS: initialize last_cpu to -1 (unknown) */
+ WRITE_ONCE(thread->last_cpu, -1);
INIT_LIST_HEAD(&new_thread->waiting_thread_node);
return thread;
}
diff --git a/drivers/android/binder_internal.h b/drivers/android/binder_internal.h
index 342574bfd28a..d01688cf0961 100644
--- a/drivers/android/binder_internal.h
+++ b/drivers/android/binder_internal.h
@@ -506,6 +506,8 @@ struct binder_thread {
struct binder_stats stats;
atomic_t tmp_ref;
bool is_dead;
+ /* CTABS: last CPU this thread ran on (smp_processor_id()), -1 if unknown */
+ int last_cpu;
};
/**
--
2.43.0