[Ce-android-mainline] binder re-implementation

[NeilBrown]

On Fri, 27 Jan 2012 13:51:19 +0000 Arnd Bergmann <arnd at arndb.de> wrote:

> I don't understand the binder requirements well enough to judge if there
> are any fundamental differences that we can't work around in message queues.

Partly triggered by this comment I decided to write out what I understand the
requirements to be, and then the weaknesses.

I was going to add a more concrete description of a possible solution but
kept hitting the same recurring difficulties (I'm probably trying too hard -
I usually do).

So here it is with just the problem statement, not the solution.

NeilBrown

----------------------------
The features of Android Binder are:

- reliable datagram messaging.
  A message can be sent from one process to another and can convey
  a byte string, some file descriptors, and some object descriptors (see below).
  A message also converys the process id and uid of the sending process.

- object descriptors
  Each 'object' belongs to a single process.  A descriptor for the object
  can be passed to another process in a message.
  Object descriptors are the primary addressing mechanism for messaging.
  A message is addressed to an object, and it is passed to the process
  (thread-group) which owns that object.
  As object descriptors cannot be faked, they can also be used as credentials.
  If a particular object is only given out in restricted circumstances, then 
  any process which can pass a descriptor for an object must have been able
  to receive it and so is in the appropriate restricted set.
  So it must be possible to compare object descriptors for equality.

- well known object.
  There is a well-known object that every process automatically owns a descriptor
  for.  This is identified by descriptor '0'.  Only a single privileged process
  can request to receive messages destined for object '0'.

- death notifications
  A process can request notification when an object dies.  When the process
  which owns the object exits (or closes its Binder handle) the notification
  is sent.

- Transaction tracking.
  Some messages are one-shot and do not expect a reply and are not involved in
  transactions.
  Otherwise each thread can only be involved in one transaction at a time.
  When a thread sends a message and waits for a reply, it will only be passed
  a genuine reply to that message, or a new message in a subordinate request
  in the same transaction.
  i.e. If 'A' sends a request to 'B' and 'B' find that to complete the request
  it needs to call some object which happens to be owned by 'A', then that call
  will be flagged as being in the same transaction so 'A' will be chosen to
  process it.  If at this time 'C' sends a message to an object owned by 'A',
  the message will either be queued until the current transaction completes, or
  if 'A' is part of the thread group, the message can be handled by some other
  thread in the group.

- process priority follows transaction
  With a transaction there is only one thread active at a time.  Other threads
  which are part of the transaction will be waiting for a reply.
  Binder allows the priority of the initiating thread to be handed on to other
  threads taking part in the transaction so the whole transaction runs
  with the priority of the initiating thread.

- single-copy messaging.
  When a message is sent from A to B it is copied exactly once by the kernel,
  from the address space of A into a buffer which is managed by the kernel
  and mapped into the address space of B.  B can use the information directly
  from there.
  Note that as there is no 'writev' style interface, 'A' may need to copy parts
  of the message into a buffer to linearise it, so this may not always provide
  true single-copy messaging.

- thread management.
  binder can alter the user-space part of the threads when all threads in the
  thread pool are busy so that it can start new threads if it wishes.
  This happens in a controlled way so that it is easy to ensure that only
  one thread attempts to create new threads.


Weaknesses in the Android Binder implementation.

(A 'binder handle' is a file descriptor obtained by opening /dev/binder.)

- The identity of a binder handle is closely linked with the process
  that is using it.  If it is passed to another process - e.g. by 'fork'
  or some form of IPC - it will behave very differently.

- The binder handle is intended to be shared between threads of a
  thread group.  However it behaves slightly differently in each thread
  to implement the transaction semantics.  This is 'odd'.

- The ioctl to send a message does not take an iovec list, so true
  single-copy may not always be possible.

- The mapped receive buffer imposes an arbitrary limit on the total
  size of active transaction for a process.

- There is only one 'well known object'.  So binder cannot be used
  concurrently for several independent purposes unless there is a
  single broker which works with all the different uses.  Having
  multiple 'well known objects' would make it a lot easier to have
  multiple independant users.

- 'death notifications' are a useful broadcast mechanism, but are
  very narrow in application.  The same basic mechanism could provide
  a more general 'broadcast' or 'publish/subscribe' mechanism.

- binder ensures that if a process receives a descriptor for a given object
  twice, they will both by the same byte-string for that process.
  This seems natural, but
  a/ is different from the way passing file descriptors works (you always
     receive a new file descriptor)
  b/ requires extra linkage and lookups in the kernel, and 
     requires a complex ref-counting protocol between user-space and
     kernel which would not otherwise be necessary.

- binder shares a lot of concepts with unix-domain sockets but uses
  none of the infrastructure.  Thus we find little things are missing
  like that fact that while a pid and uid can be sent in a message,
  the gid is not.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 828 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/ce-android-mainline/attachments/20120131/317daae1/attachment.sig>