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

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

[Bo Zhang]

From: Bo Zhang <zhangbo56@xiaomi.com>

Hi,

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

The series splits the binder allocator lock into two:

  - spinlock: protects buffer metadata (rb-trees, free_async_space,
    LRU operations) on the hot path (every binder transaction).

  - install_mutex: serializes page installation and shrinker zap on
    the cold path (only when pages are installed or reclaimed).

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

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

Changes since v2:
- Fix an ABBA deadlock between install_mutex and mmap_lock: the install
  side now uses mmap_read_trylock() and retries on contention without
  holding install_mutex, so it never blocks on mmap_lock under
  install_mutex (Sashiko).
- Fix a potential infinite retry loop on -EBUSY: an unexpected
  already-populated PTE under install_mutex is now treated as an error
  instead of being retried (Sashiko).
- Fix a use-after-free of the preallocated buffer on the -EAGAIN retry
  path: the split is now rolled back and the preallocated buffer is
  reallocated on each attempt (Sashiko).

Changes since v1:
- Dropped the simple spinlock-only approach that had a race between
  page installation and shrinker zap (Alice).
- Added install_mutex to serialize page install and shrinker zap.
- Removed binder_page_lookup() (GUP) since install_mutex serializes
  concurrent installers.

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 | 144 ++++++++++++++++++++++++---------
 drivers/android/binder_alloc.h |  11 ++-
 2 files changed, 112 insertions(+), 43 deletions(-)

-- 
2.34.1

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

[Bo Zhang]

From: Bo Zhang <zhangbo56@xiaomi.com>

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

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

[Bo Zhang]

From: Bo Zhang <zhangbo56@xiaomi.com>

The previous patch converted alloc->mutex to a spinlock for the hot
path (buffer alloc/free). However, this leaves page installation and
shrinker's zap_vma_range() unserialized, which can cause use-after-free
as identified by Alice Ryhl.

Add a separate install_mutex to serialize page installation against
the shrinker's page reclaim (pages[index]=NULL + zap_vma_range). This
mutex is only contended on the cold path when pages need to be installed
or reclaimed, not on the hot path.

Key changes:

- binder_install_single_page() holds install_mutex across the entire
  install sequence, eliminating the need for binder_page_lookup() (GUP)
  since concurrent installers are now serialized.

- The shrinker holds install_mutex across pages[index]=NULL and
  zap_vma_range(), making them atomic to the install side.

- binder_lru_freelist_del() returns -EAGAIN when list_lru_del() fails
  (shrinker already isolated the page). Any pages already removed from
  the LRU are rolled back, and if the free buffer was split, the split
  is undone (rb_erase + list_del). The caller in binder_alloc_new_buf()
  reallocates the preallocated buffer on each attempt, so a freed
  pointer is never reused.

- To avoid an ABBA deadlock (the shrinker takes mmap_lock before
  install_mutex, while the install side takes install_mutex first),
  binder_page_insert() uses mmap_read_trylock() in its fallback path
  and returns -EAGAIN on contention. The caller drops install_mutex and
  waits for mmap_lock without holding any binder lock before retrying,
  so the install side never blocks on mmap_lock under install_mutex.

- Under install_mutex the PTE cannot already be populated, so an
  unexpected -EBUSY from vm_insert_page() is treated as an error rather
  than retried, avoiding any risk of looping.

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       85k-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 | 108 ++++++++++++++++++++++++++-------
 drivers/android/binder_alloc.h |   3 +
 2 files changed, 90 insertions(+), 21 deletions(-)

diff --git a/drivers/android/binder_alloc.c b/drivers/android/binder_alloc.c
index 9775df3616aa..bbef44cc30d4 100644
--- a/drivers/android/binder_alloc.c
+++ b/drivers/android/binder_alloc.c
@@ -268,8 +268,13 @@ static int binder_page_insert(struct binder_alloc *alloc,
 		return ret;
 	}
 
-	/* fall back to mmap_lock */
-	mmap_read_lock(mm);
+	/*
+	 * Fall back to mmap_lock. Use trylock to avoid blocking under
+	 * install_mutex, which could deadlock against the shrinker (it
+	 * takes mmap_lock before install_mutex). Retry on contention.
+	 */
+	if (!mmap_read_trylock(mm))
+		return -EAGAIN;
 	vma = vma_lookup(mm, addr);
 	if (vma && binder_alloc_is_mapped(alloc))
 		ret = vm_insert_page(vma, addr, page);
@@ -325,24 +330,36 @@ static int binder_install_single_page(struct binder_alloc *alloc,
 		goto out;
 	}
 
+	mutex_lock(&alloc->install_mutex);
+
+	/* Check again under install_mutex */
+	if (binder_get_installed_page(alloc, index)) {
+		mutex_unlock(&alloc->install_mutex);
+		binder_free_page(page);
+		ret = 0;
+		goto out;
+	}
+
 	ret = binder_page_insert(alloc, addr, page);
 	switch (ret) {
+	case -EAGAIN:
+		/* mmap_lock contended; drop install_mutex and retry */
+		binder_free_page(page);
+		mutex_unlock(&alloc->install_mutex);
+		goto out;
 	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.
+		 * install_mutex serializes page installation against the
+		 * shrinker's zap, so the PTE should never be already
+		 * populated here. If it somehow is (e.g. populated
+		 * externally), fail rather than retry to avoid looping.
 		 */
-		ret = 0;
 		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;
+		mutex_unlock(&alloc->install_mutex);
+		pr_err("%d: %s unexpected EBUSY at offset %lx\n",
+		       alloc->pid, __func__, addr - alloc->vm_start);
+		ret = -ENOMEM;
+		goto out;
 	case 0:
 		/* Mark page installation complete and safe to use */
 		binder_set_installed_page(alloc, index, page);
@@ -353,6 +370,8 @@ static int binder_install_single_page(struct binder_alloc *alloc,
 		       alloc->pid, __func__, addr - alloc->vm_start, ret);
 		break;
 	}
+
+	mutex_unlock(&alloc->install_mutex);
 out:
 	mmput_async(alloc->mm);
 	return ret;
@@ -377,8 +396,21 @@ static int binder_install_buffer_pages(struct binder_alloc *alloc,
 			continue;
 
 		trace_binder_alloc_page_start(alloc, index);
-
+retry:
 		ret = binder_install_single_page(alloc, index, page_addr);
+		if (ret == -EAGAIN) {
+			/*
+			 * Wait for mmap_lock to become free before retrying,
+			 * to avoid busy-looping. Safe here as no binder lock
+			 * is held.
+			 */
+			if (mmget_not_zero(alloc->mm)) {
+				mmap_read_lock(alloc->mm);
+				mmap_read_unlock(alloc->mm);
+				mmput_async(alloc->mm);
+			}
+			goto retry;
+		}
 		if (ret)
 			return ret;
 
@@ -389,7 +421,7 @@ static int binder_install_buffer_pages(struct binder_alloc *alloc,
 }
 
 /* The range of pages should exclude those shared with other buffers */
-static void binder_lru_freelist_del(struct binder_alloc *alloc,
+static int binder_lru_freelist_del(struct binder_alloc *alloc,
 				    unsigned long start, unsigned long end)
 {
 	unsigned long page_addr;
@@ -411,7 +443,16 @@ static void binder_lru_freelist_del(struct binder_alloc *alloc,
 					      page_to_lru(page),
 					      page_to_nid(page),
 					      NULL);
-			WARN_ON(!on_lru);
+			/*
+			 * If !on_lru, the shrinker has already isolated this
+			 * page and will reclaim it. Abort so the caller can
+			 * retry after the shrinker finishes.
+			 */
+			if (!on_lru) {
+				/* Rollback pages already removed from LRU */
+				binder_lru_freelist_add(alloc, start, page_addr);
+				return -EAGAIN;
+			}
 
 			trace_binder_alloc_lru_end(alloc, index);
 			continue;
@@ -420,6 +461,8 @@ static void binder_lru_freelist_del(struct binder_alloc *alloc,
 		if (index + 1 > alloc->pages_high)
 			alloc->pages_high = index + 1;
 	}
+
+	return 0;
 }
 
 static void debug_no_space_locked(struct binder_alloc *alloc)
@@ -521,6 +564,7 @@ static struct binder_buffer *binder_alloc_new_buf_locked(
 	struct rb_node *n = alloc->free_buffers.rb_node;
 	struct rb_node *best_fit = NULL;
 	struct binder_buffer *buffer;
+	struct binder_buffer *split_buffer = NULL;
 	unsigned long next_used_page;
 	unsigned long curr_last_page;
 	size_t buffer_size;
@@ -568,6 +612,7 @@ static struct binder_buffer *binder_alloc_new_buf_locked(
 		list_add(&new_buffer->entry, &buffer->entry);
 		new_buffer->free = 1;
 		binder_insert_free_buffer(alloc, new_buffer);
+		split_buffer = new_buffer;
 		new_buffer = NULL;
 	}
 
@@ -583,8 +628,17 @@ static struct binder_buffer *binder_alloc_new_buf_locked(
 	 */
 	next_used_page = (buffer->user_data + buffer_size) & PAGE_MASK;
 	curr_last_page = PAGE_ALIGN(buffer->user_data + size);
-	binder_lru_freelist_del(alloc, PAGE_ALIGN(buffer->user_data),
-				min(next_used_page, curr_last_page));
+	if (binder_lru_freelist_del(alloc, PAGE_ALIGN(buffer->user_data),
+				min(next_used_page, curr_last_page))) {
+		/* Shrinker is reclaiming a page; undo the split and retry */
+		if (split_buffer) {
+			rb_erase(&split_buffer->rb_node, &alloc->free_buffers);
+			list_del(&split_buffer->entry);
+			new_buffer = split_buffer;
+		}
+		buffer = ERR_PTR(-EAGAIN);
+		goto out;
+	}
 
 	rb_erase(&buffer->rb_node, &alloc->free_buffers);
 	buffer->free = 0;
@@ -671,7 +725,8 @@ struct binder_buffer *binder_alloc_new_buf(struct binder_alloc *alloc,
 		return ERR_PTR(-EINVAL);
 	}
 
-	/* Preallocate the next buffer */
+	/* Preallocate the next buffer; (re)allocate on each attempt */
+retry:
 	next = kzalloc_obj(*next);
 	if (!next)
 		return ERR_PTR(-ENOMEM);
@@ -680,6 +735,12 @@ struct binder_buffer *binder_alloc_new_buf(struct binder_alloc *alloc,
 	buffer = binder_alloc_new_buf_locked(alloc, next, size, is_async);
 	if (IS_ERR(buffer)) {
 		spin_unlock(&alloc->lock);
+		if (PTR_ERR(buffer) == -EAGAIN) {
+			/* wait for the shrinker to finish, then retry */
+			mutex_lock(&alloc->install_mutex);
+			mutex_unlock(&alloc->install_mutex);
+			goto retry;
+		}
 		goto out;
 	}
 
@@ -1175,7 +1236,6 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 	trace_binder_unmap_kernel_start(alloc, index);
 
 	page_to_free = alloc->pages[index];
-	binder_set_installed_page(alloc, index, NULL);
 
 	trace_binder_unmap_kernel_end(alloc, index);
 
@@ -1183,6 +1243,9 @@ enum lru_status binder_alloc_free_page(struct list_head *item,
 	spin_unlock(&alloc->lock);
 	spin_unlock(&lru->lock);
 
+	mutex_lock(&alloc->install_mutex);
+	binder_set_installed_page(alloc, index, NULL);
+
 	if (vma) {
 		trace_binder_unmap_user_start(alloc, index);
 
@@ -1191,6 +1254,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
@@ -1236,6 +1301,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

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

[Bo Zhang]

Thanks for the review. All three are valid; I'll address them together
in v4 by tightening the roles of the two locks: install_mutex only
serializes page install vs shrinker zap, while alloc->lock (spinlock)
exclusively owns pages[] and the LRU. Details per point below.

1) AA self-deadlock via direct reclaim

Sashiko says
"binder_install_single_page() acquires alloc->install_mutex here, then
calls binder_page_insert() which invokes vm_insert_page(). vm_insert_page()
can trigger page table allocations using GFP_KERNEL semantics, which may
enter direct reclaim. If direct reclaim iterates over list_lru shrinkers
and invokes binder_alloc_free_page() for this same allocator on the same
thread, the shrinker callback will unconditionally try to lock the
already-held install_mutex."

Correct. In v4 the shrinker uses mutex_trylock(&install_mutex) and skips
the page (LRU_SKIP) on failure, so a reclaim recursion from the install
side's vm_insert_page() cannot deadlock on the same thread. The original
shrinker already used trylock on alloc->mutex; restoring trylock here also
removes the ABBA concern with mmap_lock, since a trylock does not
participate in a blocking lock cycle.

2) RT task livelock on the -EAGAIN retry

Sashiko says
"a race window exists where the shrinker has isolated a page from the
buffer's range (causing list_lru_del to fail and return -EAGAIN) but is
preempted before acquiring install_mutex. Because the mutex is uncontended,
the allocating thread acquires and drops it instantly, thinks the shrinker
is done, and retries. It will again find the page installed, fail
list_lru_del, and spin in a tight loop."

Correct. The root cause is that the current approach splits the
shrinker's pages[index]=NULL and list_lru_isolate() such that
binder_lru_freelist_del() can observe an inconsistent state. In v4 the
shrinker performs pages[index]=NULL and list_lru_isolate() together under
alloc->lock, so binder_lru_freelist_del() always sees a consistent
pages[]/LRU state and list_lru_del() never fails. This removes the
-EAGAIN retry path entirely, so the livelock cannot occur.

3) Use-after-free from clearing pages[index] outside alloc->lock

Sashiko says
"By moving binder_set_installed_page(alloc, index, NULL) outside the
alloc->lock critical section, a concurrent allocating thread holding
alloc->lock in binder_lru_freelist_del() can read the stale pointer:
page = alloc->pages[index] (which is not yet NULL). ... When the allocating
thread resumes, it will pass the dangling pointer to page_to_lru(page) and
page_to_nid(page), dereferencing the freed page_private."

Correct. In v4 pages[index]=NULL is moved back inside alloc->lock (together
with list_lru_isolate), so binder_lru_freelist_del() reading pages[index]
under alloc->lock can no longer observe a pointer that the shrinker is
about to free.

v4 will carry all three fixes.

Bo