[RFC PATCH v4 0/2] binder: split alloc->mutex to improve performance

[RFC PATCH v4 0/2] binder: split alloc->mutex to improve performance

[Bo Zhang]

Hi,

This is v4 of the binder alloc lock optimization. Thanks to the Sashiko
automated review for the feedback on v3, and to Alice Ryhl for the
earlier reviews.

The series splits the binder allocator lock into two, with distinct
roles:

  - alloc->lock (spinlock): owns the non-sleeping metadata - pages[],
    the LRU list, the rb-trees and free_async_space. This is the hot
    path hit on every binder transaction.

  - install_mutex: only serializes the sleeping PTE operations
    (vm_insert_page vs the shrinker's zap_vma_range) for a given alloc.

pages[] and the LRU are always updated together under alloc->lock, so
the buffer allocation path always observes a consistent state. The
shrinker takes install_mutex with mutex_trylock() (skipping on failure),
which avoids a self-deadlock when install-side reclaim re-enters the
shrinker, and keeps the shrinker out of any blocking cycle with
mmap_lock.

Performance (binderThroughputTest, Qualcomm SM8850, 2 workers, 10 runs)
under concurrent drop_caches:

                    mutex (baseline)    spinlock + install_mutex
  throughput:    27k-59k iter/s       84k-89k iter/s
  average:       0.031-0.068ms        0.021-0.022ms
  P99:           0.088-0.148ms        0.046-0.056ms

Changes since v3:
- Fix an AA self-deadlock: the shrinker now uses mutex_trylock() on
  install_mutex, so install-side vm_insert_page() recursing into direct
  reclaim and re-entering the shrinker on the same thread no longer
  deadlocks (Sashiko).
- Fix a use-after-free: pages[index]=NULL is done under alloc->lock
  (together with the LRU isolate) instead of under install_mutex, so
  binder_lru_freelist_del() can no longer read a pointer the shrinker is
  about to free (Sashiko).
- Fix an RT-task livelock: since pages[] and the LRU are now consistent
  under alloc->lock, list_lru_del() never fails and the -EAGAIN retry
  path is removed entirely (Sashiko).
- The mutex_trylock() also removes the ABBA concern with mmap_lock, so
  the install side's mmap_lock fallback returns to a plain blocking
  acquire (no more -EAGAIN/retry).

Changes since v2:
- Fixed the ABBA/-EBUSY/next-buffer issues raised on v2 (superseded by
  the simpler v4 locking above).

Changes since v1:
- Dropped the spinlock-only approach that raced install against shrinker
  zap; added install_mutex to serialize them (Alice).

v3: https://lore.kernel.org/all/20260904110448.23086-1-zhangbo0325@gmail.com/
v2: https://lore.kernel.org/all/20260831123545.3655557-1-zhangbo56@xiaomi.com/
v1: https://lore.kernel.org/all/20260805152752.1924434-1-zhangbo56@xiaomi.com/

Bo Zhang (2):
  binder: switch alloc->mutex to spinlock for buffer metadata
  binder: add install_mutex to serialize page install and shrinker zap

 drivers/android/binder_alloc.c | 95 +++++++++++++++++++---------------
 drivers/android/binder_alloc.h | 11 ++--
 2 files changed, 61 insertions(+), 45 deletions(-)

-- 
2.34.1

[RFC PATCH v4 1/2] binder: switch alloc->mutex to spinlock for buffer metadata

[Bo Zhang]

The alloc->mutex is a highly contended lock on Android devices. When a
low-priority task holds this mutex and sleeps, high-priority binder
transactions are blocked, causing priority inversion and latency spikes.

Split the lock by converting alloc->mutex to a spinlock that only
protects buffer metadata. This eliminates the sleeping and priority
inversion on the hot path.

Page installation and shrinker zap serialization is handled separately
by a dedicated install_mutex introduced in the next patch.

Performance (binderThroughputTest, SM8850, 2 workers, 10 runs):

                    mutex               spinlock
  throughput:    27k-59k iter/s       79k-84k iter/s
  average:       0.031-0.068ms        0.022-0.023ms
  P99:           0.088-0.148ms        0.050-0.062ms

Signed-off-by: Bo Zhang <zhangbo56@xiaomi.com>
---
 drivers/android/binder_alloc.c | 36 +++++++++++++++++-----------------
 drivers/android/binder_alloc.h |  8 ++++----
 2 files changed, 22 insertions(+), 22 deletions(-)

diff --git a/drivers/android/binder_alloc.c b/drivers/android/binder_alloc.c
index e4488ad86a65..9775df3616aa 100644
--- a/drivers/android/binder_alloc.c
+++ b/drivers/android/binder_alloc.c
@@ -169,7 +169,7 @@ static struct binder_buffer *binder_alloc_prepare_to_free_locked(
 struct binder_buffer *binder_alloc_prepare_to_free(struct binder_alloc *alloc,
 						   unsigned long user_ptr)
 {
-	guard(mutex)(&alloc->mutex);
+	guard(spinlock)(&alloc->lock);
 	return binder_alloc_prepare_to_free_locked(alloc, user_ptr);
 }
 
@@ -676,10 +676,10 @@ struct binder_buffer *binder_alloc_new_buf(struct binder_alloc *alloc,
 	if (!next)
 		return ERR_PTR(-ENOMEM);
 
-	mutex_lock(&alloc->mutex);
+	spin_lock(&alloc->lock);
 	buffer = binder_alloc_new_buf_locked(alloc, next, size, is_async);
 	if (IS_ERR(buffer)) {
-		mutex_unlock(&alloc->mutex);
+		spin_unlock(&alloc->lock);
 		goto out;
 	}
 
@@ -687,7 +687,7 @@ struct binder_buffer *binder_alloc_new_buf(struct binder_alloc *alloc,
 	buffer->offsets_size = offsets_size;
 	buffer->extra_buffers_size = extra_buffers_size;
 	buffer->pid = current->tgid;
-	mutex_unlock(&alloc->mutex);
+	spin_unlock(&alloc->lock);
 
 	ret = binder_install_buffer_pages(alloc, buffer, size);
 	if (ret) {
@@ -872,9 +872,9 @@ void binder_alloc_free_buf(struct binder_alloc *alloc,
 		binder_alloc_clear_buf(alloc, buffer);
 		buffer->clear_on_free = false;
 	}
-	mutex_lock(&alloc->mutex);
+	spin_lock(&alloc->lock);
 	binder_free_buf_locked(alloc, buffer);
-	mutex_unlock(&alloc->mutex);
+	spin_unlock(&alloc->lock);
 }
 EXPORT_SYMBOL_IF_KUNIT(binder_alloc_free_buf);
 
@@ -967,7 +967,7 @@ void binder_alloc_deferred_release(struct binder_alloc *alloc)
 	struct binder_buffer *buffer;
 
 	buffers = 0;
-	mutex_lock(&alloc->mutex);
+	spin_lock(&alloc->lock);
 	BUG_ON(alloc->mapped);
 
 	while ((n = rb_first(&alloc->allocated_buffers))) {
@@ -1018,7 +1018,7 @@ void binder_alloc_deferred_release(struct binder_alloc *alloc)
 			page_count++;
 		}
 	}
-	mutex_unlock(&alloc->mutex);
+	spin_unlock(&alloc->lock);
 	kvfree(alloc->pages);
 	if (alloc->mm)
 		mmdrop(alloc->mm);
@@ -1043,7 +1043,7 @@ void binder_alloc_print_allocated(struct seq_file *m,
 	struct binder_buffer *buffer;
 	struct rb_node *n;
 
-	guard(mutex)(&alloc->mutex);
+	guard(spinlock)(&alloc->lock);
 	for (n = rb_first(&alloc->allocated_buffers); n; n = rb_next(n)) {
 		buffer = rb_entry(n, struct binder_buffer, rb_node);
 		seq_printf(m, "  buffer %d: %lx size %zd:%zd:%zd %s\n",
@@ -1069,7 +1069,7 @@ void binder_alloc_print_pages(struct seq_file *m,
 	int lru = 0;
 	int free = 0;
 
-	mutex_lock(&alloc->mutex);
+	spin_lock(&alloc->lock);
 	/*
 	 * Make sure the binder_alloc is fully initialized, otherwise we might
 	 * read inconsistent state.
@@ -1085,7 +1085,7 @@ void binder_alloc_print_pages(struct seq_file *m,
 				lru++;
 		}
 	}
-	mutex_unlock(&alloc->mutex);
+	spin_unlock(&alloc->lock);
 	seq_printf(m, "  pages: %d:%d:%d\n", active, lru, free);
 	seq_printf(m, "  pages high watermark: %zu\n", alloc->pages_high);
 }
@@ -1101,7 +1101,7 @@ int binder_alloc_get_allocated_count(struct binder_alloc *alloc)
 	struct rb_node *n;
 	int count = 0;
 
-	guard(mutex)(&alloc->mutex);
+	guard(spinlock)(&alloc->lock);
 	for (n = rb_first(&alloc->allocated_buffers); n != NULL; n = rb_next(n))
 		count++;
 	return count;
@@ -1161,8 +1161,8 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 		vma = vma_lookup(mm, page_addr);
 	}
 
-	if (!mutex_trylock(&alloc->mutex))
-		goto err_get_alloc_mutex_failed;
+	if (!spin_trylock(&alloc->lock))
+		goto err_get_alloc_lock_failed;
 
 	/*
 	 * Since a binder_alloc can only be mapped once, we ensure
@@ -1180,6 +1180,7 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 	trace_binder_unmap_kernel_end(alloc, index);
 
 	list_lru_isolate(lru, item);
+	spin_unlock(&alloc->lock);
 	spin_unlock(&lru->lock);
 
 	if (vma) {
@@ -1190,7 +1191,6 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 		trace_binder_unmap_user_end(alloc, index);
 	}
 
-	mutex_unlock(&alloc->mutex);
 	if (mm_locked)
 		mmap_read_unlock(mm);
 	else
@@ -1201,8 +1201,8 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 	return LRU_REMOVED_RETRY;
 
 err_invalid_vma:
-	mutex_unlock(&alloc->mutex);
-err_get_alloc_mutex_failed:
+	spin_unlock(&alloc->lock);
+err_get_alloc_lock_failed:
 	if (mm_locked)
 		mmap_read_unlock(mm);
 	else
@@ -1235,7 +1235,7 @@ VISIBLE_IF_KUNIT void __binder_alloc_init(struct binder_alloc *alloc,
 	alloc->pid = current->tgid;
 	alloc->mm = current->mm;
 	mmgrab(alloc->mm);
-	mutex_init(&alloc->mutex);
+	spin_lock_init(&alloc->lock);
 	INIT_LIST_HEAD(&alloc->buffers);
 	alloc->freelist = freelist;
 }
diff --git a/drivers/android/binder_alloc.h b/drivers/android/binder_alloc.h
index d6f1f6f2d00e..bea5a77bb6da 100644
--- a/drivers/android/binder_alloc.h
+++ b/drivers/android/binder_alloc.h
@@ -9,7 +9,7 @@
 #include <linux/rbtree.h>
 #include <linux/list.h>
 #include <linux/mm.h>
-#include <linux/rtmutex.h>
+#include <linux/spinlock.h>
 #include <linux/vmalloc.h>
 #include <linux/slab.h>
 #include <linux/list_lru.h>
@@ -80,7 +80,7 @@ static inline struct list_head *page_to_lru(struct page *p)
 
 /**
  * struct binder_alloc - per-binder proc state for binder allocator
- * @mutex:              protects binder_alloc fields
+ * @lock:               protects binder_alloc fields
  * @mm:                 copy of task->mm (invariant after open)
  * @vm_start:           base of per-proc address space mapped via mmap
  * @buffers:            list of all buffers for this proc
@@ -105,7 +105,7 @@ static inline struct list_head *page_to_lru(struct page *p)
  * struct binder_buffer objects used to track the user buffers
  */
 struct binder_alloc {
-	struct mutex mutex;
+	spinlock_t lock;
 	struct mm_struct *mm;
 	unsigned long vm_start;
 	struct list_head buffers;
@@ -156,7 +156,7 @@ void binder_alloc_print_pages(struct seq_file *m,
 static inline size_t
 binder_alloc_get_free_async_space(struct binder_alloc *alloc)
 {
-	guard(mutex)(&alloc->mutex);
+	guard(spinlock)(&alloc->lock);
 	return alloc->free_async_space;
 }
 
-- 
2.34.1

Re: [RFC PATCH v4 1/2] binder: switch alloc->mutex to spinlock for buffer metadata

[Bo Zhang]

Thanks for the review. Both are real regressions introduced by this
patch: the current tree uses a mutex here, and neither problem exists
under the mutex. Converting to a spinlock is what introduces them, so
they must be fixed rather than left as-is.

The root cause is that this patch (spinlock only) cannot fix either
problem on its own, because the fixes rely on the install_mutex added in
patch 2. I will therefore fold the two patches into one in v5, so the
spinlock and install_mutex land together and the intermediate state is
never reached.

1) Soft lockup holding the spinlock across cleanup

Sashiko says
"this loop iterates over all allocated buffers and pages, it can execute
up to 4MB of memset operations and 1024 calls to binder_free_page() while
preemption is disabled by alloc->lock."

Correct. Under the mutex this loop is preemptible; under the spinlock it
is not, so unprivileged userspace can keep a CPU with preemption disabled.
In v5, binder_alloc_deferred_release() drops alloc->lock around the
sleeping/long-running work: the clear-on-free memset and binder_free_page()
run outside the spinlock, while alloc->lock only covers the rb-tree and
LRU bookkeeping.

2) Use-after-free from the early spin_unlock() in the shrinker

Sashiko says
"By dropping alloc->lock here, the shrinker allows a concurrent
binder_alloc_deferred_release() ... to acquire the lock ... The release
function can then complete its cleanup ... and eventually free the
binder_alloc structure. When the shrinker resumes execution, it accesses
the freed alloc structure when calling trace_binder_unmap_user_end()."

Correct. Under the mutex the shrinker's zap and trace ran inside
alloc->mutex, which deferred_release() also took, so release waited for
the shrinker. Dropping the spinlock early breaks that. In v5 the shrinker
already holds install_mutex across the zap/trace (from the folded patch 2),
so binder_alloc_deferred_release() takes install_mutex too and waits for
the shrinker to finish before freeing the alloc.

Note that deferred_release() runs from binder_free_proc(), after all
threads are released and there are no in-flight transactions, so no page
install can run concurrently; the only concurrent writer to pages[] is the
shrinker, which install_mutex now serializes against.

v5 will fold the two patches and carry both fixes.

Bo

[RFC PATCH v4 2/2] binder: add install_mutex to serialize page install and shrinker zap

[Bo Zhang]

The previous patch converted alloc->mutex to a spinlock for the hot
path (buffer alloc/free). However, page installation may sleep in
vm_insert_page(), and the shrinker may sleep in zap_vma_range(), so
these cannot be serialized by the spinlock. Without serialization, the
install side could observe and reuse a page that the shrinker is about
to zap and free.

Add a separate install_mutex to serialize page installation against the
shrinker's zap. The two locks have distinct roles:

- alloc->lock (spinlock) exclusively owns the non-sleeping metadata:
  pages[], the LRU list, the rb-trees and free_async_space.

- install_mutex only serializes the sleeping PTE operations
  (vm_insert_page vs zap_vma_range) for a given alloc.

pages[] and the LRU are always updated together under alloc->lock, so
binder_lru_freelist_del() always observes a consistent state.

The shrinker acquires install_mutex with mutex_trylock() and skips the
page (LRU_SKIP) on failure. This is required because the install side
may hold install_mutex while its vm_insert_page() recurses into direct
reclaim and re-enters this shrinker on the same thread; a blocking
acquire would self-deadlock. Using trylock also keeps the shrinker out
of any blocking lock cycle with mmap_lock, so the install side may take
mmap_lock while holding install_mutex without risking an ABBA deadlock.

Performance (binderThroughputTest, Qualcomm SM8850, 2 workers, 10 runs)
under concurrent drop_caches shows no regression from the install_mutex:

                    mutex (baseline)    spinlock + install_mutex
  throughput:    27k-59k iter/s       84k-89k iter/s
  average:       0.031-0.068ms        0.021-0.022ms
  P99:           0.088-0.148ms        0.046-0.056ms

Signed-off-by: Bo Zhang <zhangbo56@xiaomi.com>
---
 drivers/android/binder_alloc.c | 59 +++++++++++++++++++++-------------
 drivers/android/binder_alloc.h |  3 ++
 2 files changed, 39 insertions(+), 23 deletions(-)

diff --git a/drivers/android/binder_alloc.c b/drivers/android/binder_alloc.c
index 9775df3616aa..61544e3cdae1 100644
--- a/drivers/android/binder_alloc.c
+++ b/drivers/android/binder_alloc.c
@@ -325,34 +325,34 @@ static int binder_install_single_page(struct binder_alloc *alloc,
 		goto out;
 	}
 
-	ret = binder_page_insert(alloc, addr, page);
-	switch (ret) {
-	case -EBUSY:
-		/*
-		 * EBUSY is ok. Someone installed the pte first but the
-		 * alloc->pages[index] has not been updated yet. Discard
-		 * our page and look up the one already installed.
-		 */
-		ret = 0;
+	mutex_lock(&alloc->install_mutex);
+
+	/* Someone may have installed it already; check under alloc->lock */
+	spin_lock(&alloc->lock);
+	if (binder_get_installed_page(alloc, index)) {
+		spin_unlock(&alloc->lock);
+		mutex_unlock(&alloc->install_mutex);
 		binder_free_page(page);
-		page = binder_page_lookup(alloc, addr);
-		if (!page) {
-			pr_err("%d: failed to find page at offset %lx\n",
-			       alloc->pid, addr - alloc->vm_start);
-			ret = -ESRCH;
-			break;
-		}
-		fallthrough;
-	case 0:
-		/* Mark page installation complete and safe to use */
-		binder_set_installed_page(alloc, index, page);
-		break;
-	default:
+		ret = 0;
+		goto out;
+	}
+	spin_unlock(&alloc->lock);
+
+	ret = binder_page_insert(alloc, addr, page);
+	if (ret) {
 		binder_free_page(page);
 		pr_err("%d: %s failed to insert page at offset %lx with %d\n",
 		       alloc->pid, __func__, addr - alloc->vm_start, ret);
-		break;
+		mutex_unlock(&alloc->install_mutex);
+		goto out;
 	}
+
+	/* Mark page installation complete under alloc->lock */
+	spin_lock(&alloc->lock);
+	binder_set_installed_page(alloc, index, page);
+	spin_unlock(&alloc->lock);
+
+	mutex_unlock(&alloc->install_mutex);
 out:
 	mmput_async(alloc->mm);
 	return ret;
@@ -1161,6 +1161,14 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 		vma = vma_lookup(mm, page_addr);
 	}
 
+	/*
+	 * Use trylock: the install side may hold install_mutex while its
+	 * vm_insert_page() recurses into reclaim and re-enters this shrinker
+	 * on the same thread, so blocking here would self-deadlock.
+	 */
+	if (!mutex_trylock(&alloc->install_mutex))
+		goto err_get_install_mutex_failed;
+
 	if (!spin_trylock(&alloc->lock))
 		goto err_get_alloc_lock_failed;
 
@@ -1191,6 +1199,8 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 		trace_binder_unmap_user_end(alloc, index);
 	}
 
+	mutex_unlock(&alloc->install_mutex);
+
 	if (mm_locked)
 		mmap_read_unlock(mm);
 	else
@@ -1203,6 +1213,8 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 err_invalid_vma:
 	spin_unlock(&alloc->lock);
 err_get_alloc_lock_failed:
+	mutex_unlock(&alloc->install_mutex);
+err_get_install_mutex_failed:
 	if (mm_locked)
 		mmap_read_unlock(mm);
 	else
@@ -1236,6 +1248,7 @@ VISIBLE_IF_KUNIT void __binder_alloc_init(struct binder_alloc *alloc,
 	alloc->mm = current->mm;
 	mmgrab(alloc->mm);
 	spin_lock_init(&alloc->lock);
+	mutex_init(&alloc->install_mutex);
 	INIT_LIST_HEAD(&alloc->buffers);
 	alloc->freelist = freelist;
 }
diff --git a/drivers/android/binder_alloc.h b/drivers/android/binder_alloc.h
index bea5a77bb6da..85817efdbef6 100644
--- a/drivers/android/binder_alloc.h
+++ b/drivers/android/binder_alloc.h
@@ -9,6 +9,7 @@
 #include <linux/rbtree.h>
 #include <linux/list.h>
 #include <linux/mm.h>
+#include <linux/mutex.h>
 #include <linux/spinlock.h>
 #include <linux/vmalloc.h>
 #include <linux/slab.h>
@@ -81,6 +82,7 @@ static inline struct list_head *page_to_lru(struct page *p)
 /**
  * struct binder_alloc - per-binder proc state for binder allocator
  * @lock:               protects binder_alloc fields
+ * @install_mutex:      serializes page installation and shrinker zap
  * @mm:                 copy of task->mm (invariant after open)
  * @vm_start:           base of per-proc address space mapped via mmap
  * @buffers:            list of all buffers for this proc
@@ -106,6 +108,7 @@ static inline struct list_head *page_to_lru(struct page *p)
  */
 struct binder_alloc {
 	spinlock_t lock;
+	struct mutex install_mutex;
 	struct mm_struct *mm;
 	unsigned long vm_start;
 	struct list_head buffers;
-- 
2.34.1