[PATCH 0/2] drivers: android: binder: Introduce Cluster Aware Thread Selection

[PATCH 0/2] drivers: android: binder: Introduce Cluster Aware Thread Selection

[trieu2.huynh]

  Motivation
  ----------

On asymmetric multi-cluster ARM64 SoCs, the default binder thread
selection is topology-blind. Cross-cluster thread wakeups incur severe
cache-coherency overhead.

Measured performance test [1], especially with schd-dbg tiered threads [2]
on baseline (10K iter, 16B payload):

  Class       Tier              Avg Latency    Count / % of txns
  -----       ----              -----------    -----------------
  SCHED_FIFO  Same-core         0.089 ms       9,963 / 99.6%
  (max prio)  Same-cluster      0.120 ms          13 /  0.1%
              Cross-cluster     0.140 ms          24 /  0.2%
              -----------------------------------------------------
  Normal      Same-core         0.130 ms       4,623 / 46.2%
  (Other)     Same-cluster      0.140 ms       3,290 / 32.9%
              Cross-cluster     0.190 ms       2,087 / 20.9%

Key Observations:
(*) For SCHED_FIFO tasks, the scheduler aggressively locks the affinity,
    keeping 99.6% of txns on the same core, establishing the hardware's
    ideal latency ceiling (~0.089 ms).
(*) For normal tasks, selection is highly fragmented (only 46.2% on
    same-core). Cross-cluster transactions are ~46% slower (0.19 vs
    0.13 ms) due to interconnect overhead and cache invalidation.
(*) CTABS aims to close this gap for normal threads by enforcing affinity.

  Design
  ------

CTABS optimizes thread dispatching through a two-tiered co-design:

(*) Topology Scoring: Scores waiting threads at selection time:
    - Same CPU: Immediate dispatch (optimal L1/L2 locality via early exit)
    - Score 1 (same cluster): Local cache reuse within the same cluster
    - Score 0 (cross-cluster): Fallback to any available thread

(*) Adaptive Wake-up Nudge: For synchronous transactions yielding a cluster
    match, the caller's CPU is stored as 'preferred_cpu'. Right before
    wakeup, this value is injected into 'task->wake_cpu' to guide the
    scheduler. To prevent runqueue contention under heavy load, this nudge
    is adaptively applied only if 'available_idle_cpu(caller_cpu)' returns
    true.

  Implementation
  --------------

[PATCH 1/2] drivers: android: binder: implement CTABS
  Core scoring in binder_select_thread_topology_ilocked(),
  thread->last_cpu tracking, integration at sync and async paths.

[PATCH 2/2] drivers: android: binder: add CTABS wake-up nudge
  Adaptive scheduler hint via task->wake_cpu on top of scoring,
  safeguarded by available_idle_cpu() to avoid core contention.

  Benchmark Methodology
  ---------------------

The evaluation is conducted on a Qualcomm SA8155P Automotive platform
featuring an 8-core asymmetric Kryo 485 hierarchy organized into 3 distinct
clusters under a 1 + 3 + 4 configuration:
- Cluster 1 (Prime): 1x Kryo Gold Prime core (Cortex-A76 based).
- Cluster 2 (Gold):  3x Kryo Gold cores (Cortex-A76 based).
- Cluster 3 (Silver):4x Kryo Silver cores (Cortex-A55 based).

The test environment runs AAOSP 14 with a Linux Kernel 6.1 GKI under the 
default schedutil governor.

To provide a comprehensive performance profile, two distinct test suites
are leveraged:
(*) schd-dbg [2]: Utilized as a micro-benchmark to isolate and collect
    precise latency granularities across different affinity tiers.
(*) binderThroughputTest [3]: Executed under a heavy stress load (8 workers
    x 100K iterations, 3 runs) paired with simpleperf to capture
    hardware-level metrics (cycles, cache behavior, migrations) that reflect
    the macro-level systemic impact of the optimization.

  Results
  -------

(*) schd-dbg — Tiered Thread Latency (Avg in ms)

  Class      Tier            Baseline   Patch 1/2   Patch 2/2   Δ P1/2   Δ P2/2
  -----      -------------   --------   ---------   ---------   ------   ------
  SCHED_FIFO Same-core       0.089 ms   0.084 ms    0.083 ms    -5.6%    -6.7%
             Same-cluster    0.120 ms   0.110 ms    0.110 ms    -8.3%    -8.3%
             Cross-cluster   0.140 ms   0.130 ms    0.130 ms    -7.1%    -7.1%
             ------------------------------------------------------------------
  Normal     Same-core       0.130 ms   0.140 ms    0.140 ms    +7.7%    +7.7%
  (Other)    Same-cluster    0.140 ms   0.140 ms    0.130 ms     0%      -7.1%
             Cross-cluster   0.190 ms   0.210 ms    0.200 ms    +10.5%   +5.3%

(*) binderThroughputTest — 8 workers x 100K iter

  Metric            Baseline     Patch 1/2    Patch 2/2    Δ P1/2   Δ P2/2
  ------            --------     ---------    ---------    ------   ------
  Throughput        41,045/s     46,252/s     46,179/s     +12.7%   +12.5%
  Avg latency       0.168 ms     0.146 ms     0.145 ms     -13.1%   -13.7%
  p50 latency       0.195 ms     0.195 ms     0.117 ms       0%     -40.0%
  p99 latency       0.586 ms     0.586 ms     0.558 ms       0%      -4.8%
  
  CPU cycles        143.15 B     128.66 B     128.94 B     -10.1%    -9.9%
  Cache refs        21.83 B      21.04 B      21.24 B       -3.6%    -2.7%
  Cache misses      1,078 M      968 M        949 M        -10.2%   -11.9%
  CPU migrations    922,848      730,277      739,576      -20.9%   -19.9%
  Ctx switches      1,697 K      1,691 K      1,692 K       -0.4%    -0.3%

[1] https://source.android.com/docs/core/tests/vts/performance
[2] https://android-review.googlesource.com/c/platform/frameworks/native/+/4164726
[3] https://android.googlesource.com/platform/frameworks/native/+/master/libs/binder/tests/binderThroughputTest.cpp

trieu2.huynh (2):
  drivers: android: binder: implement CTABS heuristic
  drivers: android: binder: add preferred CPU wake-up nudge for waiting
    threads

 drivers/android/binder.c          | 111 ++++++++++++++++++++++++++++--
 drivers/android/binder_internal.h |   2 +
 2 files changed, 109 insertions(+), 4 deletions(-)

-- 
2.43.0

[PATCH 1/2] drivers: android: binder: implement CTABS heuristic

[trieu2.huynh]

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@lge.corp-partner.google.com>
---
 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

Re: [PATCH 1/2] drivers: android: binder: implement CTABS heuristic

[Greg KH]

On Wed, Jul 15, 2026 at 03:35:51AM +0900, trieu2.huynh wrote:
> 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@lge.corp-partner.google.com>

We need a real name here, and a real email address, not a
partner.google.com one.

thanks,

greg k-h

[PATCH 2/2] drivers: android: binder: add preferred CPU wake-up nudge for waiting threads

[trieu2.huynh]

Implement a wake-up nudge mechanism that hints the scheduler to wake up
the selected Binder thread on its preferred CPU. This maximizes cache
locality for the incoming transaction.

The preferred CPU is recorded during thread selection and stored in the
thread structure. Right before waking up the thread, this value is
safely injected into the task's 'wake_cpu' field.

Signed-off-by: trieu2.huynh <trieu2.huynh@lge.corp-partner.google.com>
---
 drivers/android/binder.c          | 39 +++++++++++++++++++++++++++++--
 drivers/android/binder_internal.h |  4 ++--
 2 files changed, 39 insertions(+), 4 deletions(-)

diff --git a/drivers/android/binder.c b/drivers/android/binder.c
index 2a7be45368c1..580889b773b7 100644
--- a/drivers/android/binder.c
+++ b/drivers/android/binder.c
@@ -638,6 +638,7 @@ 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;
+	int chosen_cpu = -1;
 
 	assert_spin_locked(&proc->inner_lock);
 
@@ -648,9 +649,14 @@ binder_select_thread_topology_ilocked(struct binder_proc *proc, int caller_cpu)
 		int tcpu = READ_ONCE(thread->last_cpu);
 		int score;
 
-		/* Highest priority: exactly the same CPU */
+		/* Highest priority: exactly the same CPU. No wake_cpu nudge
+		 * needed here: __set_task_cpu() already keeps task->wake_cpu
+		 * in sync with task_cpu(p) (== tcpu), so writing
+		 * chosen_cpu = tcpu back would be a no-op.
+		 */
 		if (tcpu == caller_cpu && caller_cpu >= 0) {
 			best = thread;
+			chosen_cpu = -1;
 			goto found_best;
 		}
 
@@ -667,12 +673,29 @@ binder_select_thread_topology_ilocked(struct binder_proc *proc, int caller_cpu)
 		if (score > best_score) {
 			best_score = score;
 			best = thread;
+			/* Nudge toward caller_cpu (not the thread's own stale
+			 * tcpu) so the wake_cpu hint conveys new information:
+			 * the transaction data was just touched on caller_cpu,
+			 * and it shares an L2/L3 with tcpu within the cluster,
+			 * so migrating there is cheap and cache-friendly.
+			 */
+			if (score == 1 && caller_cpu >= 0) {
+				/* Only nudge if caller_cpu is idle */
+				if (available_idle_cpu(caller_cpu))
+					chosen_cpu = caller_cpu;
+				else
+					chosen_cpu = -1;
+			} else {
+				chosen_cpu = -1;
+			}
 		}
 	}
 
 found_best:
-	if (best)
+	if (best) {
 		list_del_init(&best->waiting_thread_node);
+		best->preferred_cpu = chosen_cpu;
+	}
 
 	return best;
 }
@@ -700,6 +723,16 @@ static void binder_wakeup_thread_ilocked(struct binder_proc *proc,
 	assert_spin_locked(&proc->inner_lock);
 
 	if (thread) {
+#ifdef CONFIG_SMP
+		/* CTABS nudge: hint scheduler to wake thread on preferred CPU.
+		 * This improves cache locality for the transaction. Only do
+		 * this for sync wakeups, for oneway/async work the caller
+		 * keeps running on caller_cpu.
+		 */
+		if (sync && thread->preferred_cpu >= 0 && thread->task)
+			WRITE_ONCE(thread->task->wake_cpu, thread->preferred_cpu);
+#endif
+		thread->preferred_cpu = -1;
 		if (sync)
 			wake_up_interruptible_sync(&thread->wait);
 		else
@@ -5363,6 +5396,8 @@ static struct binder_thread *binder_get_thread_ilocked(
 	thread->ee.command = BR_OK;
 	/* CTABS: initialize last_cpu to -1 (unknown) */
 	WRITE_ONCE(thread->last_cpu, -1);
+	/* CTABS: initialize preferred_cpu to -1 (no nudge) */
+	WRITE_ONCE(thread->preferred_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 d01688cf0961..285846e6068f 100644
--- a/drivers/android/binder_internal.h
+++ b/drivers/android/binder_internal.h
@@ -506,8 +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;
+	int last_cpu;	   /* CTABS: last CPU this thread ran on */
+	int preferred_cpu; /* CTABS: preferred CPU for wake-up nudge */
 };
 
 /**
-- 
2.43.0

Re: [PATCH 0/2] drivers: android: binder: Introduce Cluster Aware Thread Selection

[Alice Ryhl]

On Wed, Jul 15, 2026 at 03:35:50AM +0900, trieu2.huynh wrote:
>   Motivation
>   ----------
> 
> On asymmetric multi-cluster ARM64 SoCs, the default binder thread
> selection is topology-blind. Cross-cluster thread wakeups incur severe
> cache-coherency overhead.
> 
> Measured performance test [1], especially with schd-dbg tiered threads [2]
> on baseline (10K iter, 16B payload):
> 
>   Class       Tier              Avg Latency    Count / % of txns
>   -----       ----              -----------    -----------------
>   SCHED_FIFO  Same-core         0.089 ms       9,963 / 99.6%
>   (max prio)  Same-cluster      0.120 ms          13 /  0.1%
>               Cross-cluster     0.140 ms          24 /  0.2%
>               -----------------------------------------------------
>   Normal      Same-core         0.130 ms       4,623 / 46.2%
>   (Other)     Same-cluster      0.140 ms       3,290 / 32.9%
>               Cross-cluster     0.190 ms       2,087 / 20.9%
> 
> Key Observations:
> (*) For SCHED_FIFO tasks, the scheduler aggressively locks the affinity,
>     keeping 99.6% of txns on the same core, establishing the hardware's
>     ideal latency ceiling (~0.089 ms).
> (*) For normal tasks, selection is highly fragmented (only 46.2% on
>     same-core). Cross-cluster transactions are ~46% slower (0.19 vs
>     0.13 ms) due to interconnect overhead and cache invalidation.
> (*) CTABS aims to close this gap for normal threads by enforcing affinity.

I've been told that GKI has patched wake_up_sync() to make it place the
recipient on the same CPU if nothing else is scheduled to run there.

* http://r.android.com/1362918
* http://r.android.com/1145589

Are these patches included in the tree from which you took this
benchmark?

Alice