linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 00/37] fine-grained locking in binder driver
@ 2017-06-29 19:01 Todd Kjos
  2017-06-29 19:01 ` [PATCH 01/37] Revert "android: binder: Sanity check at binder ioctl" Todd Kjos
                   ` (37 more replies)
  0 siblings, 38 replies; 58+ messages in thread
From: Todd Kjos @ 2017-06-29 19:01 UTC (permalink / raw)
  To: gregkh, arve, devel, linux-kernel, maco, tkjos

The binder driver uses a global mutex to serialize access to state in a
multi-threaded environment. This global lock has been increasingly
problematic as Android devices have scaled to more cores. The problem is
not so much contention for the global lock which still remains relatively
low, but the priority inversion which occurs regularly when a lower
priority thread is preempted while holding the lock and a higher priority
thread becomes blocked on it. These cases can be especially painful if the
lower priority thread runs in the background on a slow core at a low
frequency. This often manifests as missed frames or other glitches.

For several years, a hacky solution has been used in many Android devices
which disables preemption for most of the time the global mutex is held.
This dramatically decreased the cases of glitches induced by priority
inversion and increased the average throughput for binder transactions.

Moving to fine-grained locking in this patchset results is a cleaner
and more scalable solution than the preempt disable hack. Priority
inversion is decreased significantly.

Here is a comparison of the binder throughputs for the 3 cases
with no payload (using binderThroughputTest on a 4-core Pixel device):

1 Client/Server Pair (iterations/s):
Global Mutex:	 4267
+ No-Preempt:	69688
Fine-Grained:	52313

2 Client/Server Pairs (iterations/s):
Global Mutex:	  5608
+ No-Preempt:	111346
Fine-Grained:	117039

4 Client/Server Pairs (iterations/s):
Global Mutex:	 12839
+ No-Preempt:	118049
Fine-Grained:	189805

8 Client/Server Pairs (iterations/s):
Global Mutex:	 12991
+ No-Preempt:	111780
Fine-Grained:	203607

16 Client/Server Pairs (iterations/s):
Global Mutex:	 14467
+ No-Preempt:	106763
Fine-Grained:	202942

Note that global lock performance without preempt disable seems to perform
significantly worse on Pixel than on some other devices. This run used the
4.4 version of the binder driver that is currently upstream (and there
have been few lines changed since then which wouldn't explain the poor
performance).

The no-preempt version has better throughput in the single threaded case
where the new locking overhead adds to the transacton latency. However
with multiple concurent transactions, the lack of contention results in
better throughput for the fine-grained case.

In the patchset, the binder allocator is moved to a separate file and
protected with its own per-process mutex.

Most of the binder driver is now protected by 3 spinlocks which must be
acquired in the order shown:
1) proc->outer_lock : protects binder_ref binder_proc_lock() and
   binder_proc_unlock() are used to acq/rel.
2) node->lock : protects most fields of binder_node.  binder_node_lock()
   and binder_node_unlock() are used to acq/rel
3) proc->inner_lock : protects the thread and node lists (proc->threads,
   proc->waiting_threads, proc->nodes) and all todo lists associated with
   the binder_proc (proc->todo, thread->todo, proc->delivered_death and
   node->async_todo), as well as thread->transaction_stack
   binder_inner_proc_lock() and binder_inner_proc_unlock() are used
   to acq/rel

Any lock under procA must never be nested under any lock at the same
level or below on procB.

There was significant refactoring needed to implement the locking so there
are 37 patches in the set.

Here are the patches grouped into 4 categories:

1) bugfixes: 3 patches to fix behavior and are
   needed for fine-grained locking implementation
	Revert "binder: Sanity check at binder ioctl"
	  - note: introduces kernel race to fix userspace bug. An
	          attempt to fix this was submitted in
		  "[PATCH v2] android: binder: fix dangling pointer comparison"
		  however that discussion concluded that this
		  patch should be reverted and the problem fixed
		  in userspace. Doing the revert now since this patch
		  conflicts with some of the fine-grained locking
		  patches.
	binder: use group leader instead of open thread
	binder: Use wake up hint for synchronous transactions.

2) Separate binder allocator into a separate file from binder driver
	binder: separate binder allocator structure from binder proc
	binder: remove unneeded cleanup code
	binder: separate out binder_alloc functions
	binder: move binder_alloc to separate file

3) Refactor binder driver to support locking
	binder: remove binder_debug_no_lock mechanism
	binder: add protection for non-perf cases
	binder: change binder_stats to atomics
	binder: make binder_last_id an atomic
	binder: add log information for binder transaction failures
	binder: refactor queue management in binder_thread_read
	binder: avoid race conditions when enqueuing txn 
	binder: don't modify thread->looper from other threads
	binder: remove dead code in binder_get_ref_for_node
	binder: protect against two threads freeing buffer
	binder: add more debug info when allocation fails.
	binder: use atomic for transaction_log index
	binder: refactor binder_pop_transaction
	binder: guarantee txn complete / errors delivered in-order
	binder: make sure target_node has strong ref 
	binder: make sure accesses to proc/thread are safe
	binder: refactor binder ref inc/dec for thread safety
	binder: use node->tmp_refs to ensure node safety

4) Add the locks and remove the global lock
	binder: introduce locking helper functions
	binder: use inner lock to sync work dq and node counts
	binder: add spinlocks to protect todo lists
	binder: add spinlock to protect binder_node
	binder: protect proc->nodes with inner lock
	binder: protect proc->threads with inner_lock
	binder: protect transaction_stack with inner lock.
	binder: use inner lock to protect thread accounting
	binder: protect binder_ref with outer lock
	binder: protect against stale pointers in print_binder_transaction
	binder: fix death race conditions
	binder: remove global binder lock

drivers/android/Makefile       |    2 +-
drivers/android/binder.c       | 3467 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------------------------------
drivers/android/binder_alloc.c |  802 ++++++++++++++++++++++++++++++++
drivers/android/binder_alloc.h |  163 +++++++
drivers/android/binder_trace.h |   41 +-
5 files changed, 3235 insertions(+), 1240 deletions(-)

^ permalink raw reply	[flat|nested] 58+ messages in thread

end of thread, other threads:[~2017-07-28 11:58 UTC | newest]

Thread overview: 58+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-06-29 19:01 [PATCH 00/37] fine-grained locking in binder driver Todd Kjos
2017-06-29 19:01 ` [PATCH 01/37] Revert "android: binder: Sanity check at binder ioctl" Todd Kjos
2017-07-03  9:17   ` Greg KH
     [not found]     ` <CAHRSSExh9JX5xiSRig55DSei31C_BPSasOKB+BTC6jjjuZ+ZpA@mail.gmail.com>
2017-07-05 18:47       ` Greg KH
2017-06-29 19:01 ` [PATCH 02/37] binder: use group leader instead of open thread Todd Kjos
2017-07-03  9:17   ` Greg KH
     [not found]     ` <CAHRSSEyH3t0igLJqcC4e-HR68RH0bg4T310jnRHZzrMChoOeOg@mail.gmail.com>
2017-07-05 18:47       ` Greg KH
2017-07-07 18:23         ` Todd Kjos
2017-07-07 18:29           ` Greg KH
2017-07-24 21:00   ` John Stultz
2017-07-24 21:07     ` John Stultz
2017-07-25  9:13       ` Martijn Coenen
2017-07-27  9:08         ` Amit Pundir
2017-07-27 13:23           ` Greg Kroah-Hartman
2017-07-27 13:40             ` Martijn Coenen
2017-07-27 13:42             ` Amit Pundir
2017-07-28 11:58               ` Martijn Coenen
2017-07-24 21:23     ` Greg Kroah-Hartman
2017-07-24 21:53       ` John Stultz
2017-06-29 19:01 ` [PATCH 03/37] binder: Use wake up hint for synchronous transactions Todd Kjos
2017-07-03  9:18   ` Greg KH
2017-06-29 19:01 ` [PATCH 04/37] binder: separate binder allocator structure from binder proc Todd Kjos
2017-06-29 19:01 ` [PATCH 05/37] binder: remove unneeded cleanup code Todd Kjos
2017-06-29 19:01 ` [PATCH 06/37] binder: separate out binder_alloc functions Todd Kjos
2017-06-29 19:01 ` [PATCH 07/37] binder: move binder_alloc to separate file Todd Kjos
2017-06-29 19:01 ` [PATCH 08/37] binder: remove binder_debug_no_lock mechanism Todd Kjos
2017-06-29 19:01 ` [PATCH 09/37] binder: add protection for non-perf cases Todd Kjos
2017-06-29 19:01 ` [PATCH 10/37] binder: change binder_stats to atomics Todd Kjos
2017-06-29 19:01 ` [PATCH 11/37] binder: make binder_last_id an atomic Todd Kjos
2017-06-29 19:01 ` [PATCH 12/37] binder: add log information for binder transaction failures Todd Kjos
2017-06-29 19:01 ` [PATCH 13/37] binder: refactor queue management in binder_thread_read Todd Kjos
2017-06-29 19:01 ` [PATCH 14/37] binder: avoid race conditions when enqueuing txn Todd Kjos
2017-06-29 19:01 ` [PATCH 15/37] binder: don't modify thread->looper from other threads Todd Kjos
2017-06-29 19:01 ` [PATCH 16/37] binder: remove dead code in binder_get_ref_for_node Todd Kjos
2017-06-29 19:01 ` [PATCH 17/37] binder: protect against two threads freeing buffer Todd Kjos
2017-06-29 19:01 ` [PATCH 18/37] binder: add more debug info when allocation fails Todd Kjos
2017-06-29 19:01 ` [PATCH 19/37] binder: use atomic for transaction_log index Todd Kjos
2017-06-29 19:01 ` [PATCH 20/37] binder: refactor binder_pop_transaction Todd Kjos
2017-06-29 19:01 ` [PATCH 21/37] binder: guarantee txn complete / errors delivered in-order Todd Kjos
2017-06-29 19:01 ` [PATCH 22/37] binder: make sure target_node has strong ref Todd Kjos
2017-06-29 19:01 ` [PATCH 23/37] binder: make sure accesses to proc/thread are safe Todd Kjos
2017-06-29 19:01 ` [PATCH 24/37] binder: refactor binder ref inc/dec for thread safety Todd Kjos
2017-06-29 19:01 ` [PATCH 25/37] binder: use node->tmp_refs to ensure node safety Todd Kjos
2017-06-29 19:02 ` [PATCH 26/37] binder: introduce locking helper functions Todd Kjos
2017-06-29 19:02 ` [PATCH 27/37] binder: use inner lock to sync work dq and node counts Todd Kjos
2017-06-29 19:02 ` [PATCH 28/37] binder: add spinlocks to protect todo lists Todd Kjos
2017-06-29 19:02 ` [PATCH 29/37] binder: add spinlock to protect binder_node Todd Kjos
2017-06-29 19:02 ` [PATCH 30/37] binder: protect proc->nodes with inner lock Todd Kjos
2017-06-29 19:02 ` [PATCH 31/37] binder: protect proc->threads with inner_lock Todd Kjos
2017-06-29 19:02 ` [PATCH 32/37] binder: protect transaction_stack with inner lock Todd Kjos
2017-06-29 19:02 ` [PATCH 33/37] binder: use inner lock to protect thread accounting Todd Kjos
2017-06-29 19:02 ` [PATCH 34/37] binder: protect binder_ref with outer lock Todd Kjos
2017-06-29 19:02 ` [PATCH 35/37] binder: protect against stale pointers in print_binder_transaction Todd Kjos
2017-06-29 19:02 ` [PATCH 36/37] binder: fix death race conditions Todd Kjos
2017-06-30  6:05   ` Greg KH
2017-06-29 19:02 ` [PATCH 37/37] binder: remove global binder lock Todd Kjos
2017-06-30  6:04 ` [PATCH 00/37] fine-grained locking in binder driver Greg KH
2017-07-17 12:49   ` Greg KH

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).