[RFC PATCH v5] binder: switch alloc->mutex to a spinlock plus install_mutex

[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 into two with distinct roles:

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

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

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

The shrinker takes install_mutex with mutex_trylock() and skips the page
on failure: the install side may hold install_mutex while vm_insert_page()
recurses into reclaim and re-enters this shrinker on the same thread, so a
blocking acquire would self-deadlock. trylock also avoids an ABBA cycle
with mmap_lock.

binder_alloc_deferred_release() drops alloc->lock around the clear-on-free
memset and binder_free_page() so preemption is not disabled across the
whole cleanup, and takes install_mutex to wait for an in-flight shrinker
(which still touches the alloc after dropping alloc->lock) before freeing
it.

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.058ms

Signed-off-by: Bo Zhang <zhangbo56@xxxxxxxxxx>
---
Tested on Qualcomm SM8850 with KASAN (HW_TAGS), PROVE_LOCKING and
DEBUG_ATOMIC_SLEEP enabled, under concurrent drop_caches, with no
warnings.

Changes since v4:
- Fold the two patches into one. v4 patch 1 (spinlock only) has two
  regressions that can only be fixed with the install_mutex from patch 2,
  so it was never correct on its own (Sashiko).
- binder_alloc_deferred_release() no longer holds the spinlock across
  the clear-on-free memset and binder_free_page(); it drops alloc->lock
  around them so preemption is not disabled for the whole cleanup, which
  under a spinlock could otherwise be triggered by unprivileged userspace
  (Sashiko).
- binder_alloc_deferred_release() takes install_mutex so it waits for an
  in-flight shrinker (which accesses the alloc after dropping alloc->lock)
  before freeing the alloc, closing a use-after-free (Sashiko).

Changes since v3:
- Fix an AA self-deadlock: the shrinker 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
  (with the LRU isolate) instead of under install_mutex (Sashiko).
- Fix an RT-task livelock: pages[] and the LRU are consistent under
  alloc->lock, so the -EAGAIN retry path is removed entirely (Sashiko).
- The mutex_trylock() also removes the ABBA concern with mmap_lock, so
  the install-side mmap_lock fallback returns to a plain blocking acquire.

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

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

v4: https://lore.kernel.org/all/20260907130028.807366-1-zhangbo0325@xxxxxxxxx/
v3: https://lore.kernel.org/all/20260904110448.23086-1-zhangbo0325@xxxxxxxxx/
v2: https://lore.kernel.org/all/20260831123545.3655557-1-zhangbo56@xxxxxxxxxx/
v1: https://lore.kernel.org/all/20260805152752.1924434-1-zhangbo56@xxxxxxxxxx/

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

diff --git a/drivers/android/binder_alloc.c b/drivers/android/binder_alloc.c
index e4488ad86a65..644a9d81e1ed 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);
 }
 
@@ -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;
@@ -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,14 @@ void binder_alloc_deferred_release(struct binder_alloc *alloc)
 	struct binder_buffer *buffer;
 
 	buffers = 0;
-	mutex_lock(&alloc->mutex);
+	/*
+	 * Hold install_mutex to serialize against the shrinker, which may
+	 * access this alloc after dropping alloc->lock to zap pages. This
+	 * also keeps pages[] stable so the loops below can drop alloc->lock
+	 * for the sleeping memset and page free.
+	 */
+	mutex_lock(&alloc->install_mutex);
+	spin_lock(&alloc->lock);
 	BUG_ON(alloc->mapped);
 
 	while ((n = rb_first(&alloc->allocated_buffers))) {
@@ -977,7 +984,9 @@ void binder_alloc_deferred_release(struct binder_alloc *alloc)
 		BUG_ON(buffer->transaction);
 
 		if (buffer->clear_on_free) {
+			spin_unlock(&alloc->lock);
 			binder_alloc_clear_buf(alloc, buffer);
+			spin_lock(&alloc->lock);
 			buffer->clear_on_free = false;
 		}
 		binder_free_buf_locked(alloc, buffer);
@@ -1010,15 +1019,18 @@ void binder_alloc_deferred_release(struct binder_alloc *alloc)
 					      page_to_lru(page),
 					      page_to_nid(page),
 					      NULL);
+			spin_unlock(&alloc->lock);
 			binder_alloc_debug(BINDER_DEBUG_BUFFER_ALLOC,
 				     "%s: %d: page %d %s\n",
 				     __func__, alloc->pid, i,
 				     on_lru ? "on lru" : "active");
 			binder_free_page(page);
 			page_count++;
+			spin_lock(&alloc->lock);
 		}
 	}
-	mutex_unlock(&alloc->mutex);
+	spin_unlock(&alloc->lock);
+	mutex_unlock(&alloc->install_mutex);
 	kvfree(alloc->pages);
 	if (alloc->mm)
 		mmdrop(alloc->mm);
@@ -1043,7 +1055,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 +1081,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 +1097,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 +1113,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 +1173,16 @@ 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;
+	/*
+	 * 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;
 
 	/*
 	 * Since a binder_alloc can only be mapped once, we ensure
@@ -1180,6 +1200,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 +1211,8 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 		trace_binder_unmap_user_end(alloc, index);
 	}
 
-	mutex_unlock(&alloc->mutex);
+	mutex_unlock(&alloc->install_mutex);
+
 	if (mm_locked)
 		mmap_read_unlock(mm);
 	else
@@ -1201,8 +1223,10 @@ 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:
+	mutex_unlock(&alloc->install_mutex);
+err_get_install_mutex_failed:
 	if (mm_locked)
 		mmap_read_unlock(mm);
 	else
@@ -1235,7 +1259,8 @@ 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);
+	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 d6f1f6f2d00e..85817efdbef6 100644
--- a/drivers/android/binder_alloc.h
+++ b/drivers/android/binder_alloc.h
@@ -9,7 +9,8 @@
 #include <linux/rbtree.h>
 #include <linux/list.h>
 #include <linux/mm.h>
-#include <linux/rtmutex.h>
+#include <linux/mutex.h>
+#include <linux/spinlock.h>
 #include <linux/vmalloc.h>
 #include <linux/slab.h>
 #include <linux/list_lru.h>
@@ -80,7 +81,8 @@ 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
+ * @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
@@ -105,7 +107,8 @@ 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 mutex install_mutex;
 	struct mm_struct *mm;
 	unsigned long vm_start;
 	struct list_head buffers;
@@ -156,7 +159,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