RFC: a new binder driver implementation

[rong]

Hi Folks,

I've just finished a fresh implementation of the android binder
driver, would love to see some suggestions or comments on the code as
well as the whole binder IPC idea. The driver can be found on Github
at

https://github.com/rong1129/android-binder-ipc

in the module/new directory. The rest in that project are a minimum
set of framework library, the service manager, and some test
applications.

Reason I did this project was because when I was exploring around the
Android kernel and framework stuff, I found the existing binder driver
wasn't implemented efficiently esp. in the context of SMP. There's a
big mutex (binder_lock) that locks everyone else out when one ioctl is
in progress. I spent hours thinking a way to remove it, but turned out
impossible - there are basically pointers shared and passed around
between processes all over the place, which is why most of the driver
is protected by that mutex. It's easy to manage but the downside is no
two or more IPCs can be executed at the same time, regardless how many
CPUs you have. Also the mutex around ioctls or any long operation can
significantly reduce a system's responsiveness.

So in the new implementation, I took a new approach - an sysV like
process message queue is implemented as the foundation of the driver.
Unlike the sysV queue, it's used only in the kernel - mainly for
drivers. I specially separated it out in the hope that it would also
be beneficial to other drivers. The queue is designed so queue
identifiers (addresses) can be passed across processes and queues can
be accessed by different processes as long as the proper get/set
methods are called.

The binder driver is built on top of the queue mechanism and have
other data structure designed carefully so maximum concurrency can be
reached while requiring minimum locking. For example, the binder node
and refs in the existing driver are replaced with a single structure
binder_obj. Objects (nodes and refs in the existing terms) are created
only in the current process context (shared by threads) and not
accessed by other processes.

In terms of performance, the current version is slightly better than
the existing driver, in particular with concurrent IPC call scenarios.
As I just finished the coding and some simple tests, not so much has
been done in terms of tuning or optimizations. But I will surely do
them in the following days together with completing whatever is left.

To summarize the status, I managed to implement most part of the
protocol, as for now, the standard test app binderAddInts application
can work properly. Most of the existing implementation details are
covered, except a few things below,

* mmap and user buffer allocating stuff - it's the only
incompatibility so far
The existing mmap mechanism does reduce data copying from twice to
once, but going into other process's space to allocate and manage
buffers would need a big lock to avoid a lot of nasty things and you
can't be guaranteed other processes are not killed while you writing
to their space. Also the extra buffer management overhead can easily
kill all the benefits it actually brings.

I implemented in a traditional way, where there are two data copying
in a transaction: process A to kernel and kernel to process B, which
is simple and most drivers would do (if DMA is not involved). This is
the only incompatible place in terms kernel/user API so far. There's
no difference for the kernel to read data from user space, but for
writes, the driver writes the transaction data to the supplied buffer
in binder_write_read structure, instead of a pre-allocated mmap-ed
buffer, as a result the application is expected to follow the same
logic to read the data back and of course provide a larger read buffer
when doing ioctl.

* File descriptor sharing across processes
It's not used by the test application so it's not considered yet. Also
I'm not convinced it's so useful, as one can easily implement the
similar thing in user space by re-opening the file, although having it
won't affect much of concurrency as it's already taken care of by
VFS.

* Priority inheritance
Not sure if it exists is to avoid priority inversion, but seems
there's also priority adjusting in the framework - confusing. I'm not
entirely sure how they work together. Will probably look into it a
litter later.

* Reference counting and etc.
The whole strong / weak refs in the kernel just complicates the whole
driver, IMHO. It should well be enforced just at the user level.
There's not so much point of a strong referencing at the driver level,
as a process can quit regardless it wishes or not, or whether it has
strong references to something or not. What it matters is the driver
has to provide a transparent channel and a proper closing-down
notification to the applications, so they can maintain those
references properly just between themselves.

At the moment, there's a hack in the implementation to send an acquire
command to the user when a binder object is written through the driver
- just to stop the application from crashing as if no one holds a
reference to the object, it will be destroyed right after addService()
call. Took me hours to figure it out.

That's it - a good summary for the last ten days or so working on the
driver and a lot more time trying to understand how it works :(.
Anyway, it's GPLed so feel free to try and contribute.

Cheers,
Rong

[Tim Bird]

On 01/25/2012 05:41 AM, rong wrote:
> Hi Folks,
>
> I've just finished a fresh implementation of the android binder
> driver, would love to see some suggestions or comments on the code as
> well as the whole binder IPC idea.

This is really interesting. I hope this doesn't seem rude, but
why are you doing it? Is it just an interesting exercise, or are
you trying to develop something to replace the current driver?
Or, are you trying to develop something in the hopes that it
will have a better chance of being accepted into the mainline kernel?

The main issue you seem to be addressing is performance scalability
on SMP. Is that right?

I'm involved with a project to try to get Android technologies
integrated into the mainline Linux kernel source tree.
See http://elinux.org/Android_Mainlining_Project

If your project gains traction, it would be useful, IMHO,
to discuss this as part of that effort. Also, you may wish
to follow the link on that page to see what issues mainline
kernel developers have with the current binder driver, to
see if they might also apply to your driver.

Regards,
-- Tim

=============================
Tim Bird
Architecture Group Chair, CE Workgroup of the Linux Foundation
Senior Staff Engineer, Sony Network Entertainment
=============================

[rong]

On Jan 26, 5:05 am, Tim Bird <tim.b...@am.sony.com> wrote:
> On 01/25/2012 05:41 AM, rong wrote:
>
> > Hi Folks,
>
> > I've just finished a fresh implementation of the android binder
> > driver, would love to see some suggestions or comments on the code as
> > well as the whole binder IPC idea.
>
> This is really interesting.  I hope this doesn't seem rude, but
> why are you doing it?  Is it just an interesting exercise, or are
> you trying to develop something to replace the current driver?
> Or, are you trying to develop something in the hopes that it
> will have a better chance of being accepted into the mainline kernel?

It was just for fun, I guess that's the beauty of open source - people
can always come up with different solutions when they see how others
have done it. I've seen a lot of discussions on whether or how the
android related driver should be accepted into the mainline kernel, so
I have no intention in doing that. In my opinion, the binder driver
contains too much domain specific details to become part of the
generic kernel, on the other hand, if more people understand it well
and use it in their day to day projects, it'll eventually become part
of a generic system. Until then, I'm just doing it for the fun of
coding, all I wish soon I can replace the binder driver on my phone
and hopefully get a better interaction with it.

> The main issue you seem to be addressing is performance scalability
> on SMP.  Is that right?

Yes and no. The existing driver has poor SMP scalability for sure. But
even on UP systems, that kind of global locking hasn't been a common
practice since long ago, remember UP systems can also have preemption
and so on. But don't get me wrong, the whole binder driver and
supporting framework is quite sophisticated. Android people have done
a great job to put everything together and get it used on a phone that
has become so popular. Considering SMP is now the defacto standard on
desktop PCs and more and more phones, removing the global locking to
get a better system response is the way to go. Also I've seen some
interfacing issues with running the existing driver and framework on
64-bit systems, so there's also something there to be sorted out.

>
> I'm involved with a project to try to get Android technologies
> integrated into the mainline Linux kernel source tree.

> Seehttp://elinux.org/Android_Mainlining_Project

>
> If your project gains traction, it would be useful, IMHO,
> to discuss this as part of that effort.  Also, you may wish
> to follow the link on that page to see what issues mainline
> kernel developers have with the current binder driver, to
> see if they might also apply to your driver.

Great. It'd be useful to have more and more Android specific code to
be accepted into the kernel. Again when you think Android being a
fully commercialized system, and Linux a purely open sourced generic
OS, there will always be things can't be settled well especially in
short period of time. I guess it's a more open ended question for
people who are really evolved to think which way it should go. Having
said that, I'm more than happy to provide whatever support I have to
contribute to your project if ever needed.

> Regards,
>  -- Tim
>
> =============================
> Tim Bird
> Architecture Group Chair, CE Workgroup of the Linux Foundation
> Senior Staff Engineer, Sony Network Entertainment
> =============================

Cheers,
Rong

[Suryandaru Triandana]

Very interesting, I have deadlock problem with current binder implementation on mainline kernel (3.3-rc1), I look into the codes and it quite messy. Trying to find alternative implementation and found yours, its so exciting that someone finally working on it. Hopefull it can become full binder replacement in the near future. Oh, I look into you code and it is quite clean and elegant, keep up the good work. I hope myself can help a one or two, but right now I am still strugling to understand how this thing really work.

Regards,
Surya

[dh]

Hi,

sounds like a great piece of work. I'm not into the details of that low-level kernel stuff, but there's one question that sticks around in my mind:

From a security pov, is it possible to guess binder reference numbers of binder nodes, thus by-passing the service manager to initiate IPC 'directly' from one application to another? Is that possible in the traditional Binder implementation? If yes, did you regard this in your project?

Cheers,

David

[rong]

> From a security pov, is it possible to guess binder reference numbers of
> binder nodes, thus by-passing the service manager to initiate IPC
> 'directly' from one application to another? Is that possible in the
> traditional Binder implementation? If yes, did you regard this in your
> project?

I had thought about before too. From the implementation point of view,
you need someone to send you either a binder or handler (like
invitation) to be able to create a kernel level reference (numbered
locally), which you can then use to start transaction with. As the
reference number is created locally, there's no point of guessing or
forging, because if you don't have a local reference, the kernel will
simply reject it. From that perspective, it's probably secure. But
there's nothing (from memory) would stop you from creating a reference
via a reference from someone else other than the owner. On the other
hand, the service provider (owner) can always enforce verification the
originator of the request if they want to. What might be a security
risk I found is actually the way the framework handles the cookie.
When a request is received, the cookie is cast-ed into an object
without much checking, which can potentially be misused by some
malicious apps.

The first priority of my project was to implement a version that can
be used as a drop replacement, well as much as possible. So logic
mentioned above mostly applies to my implementation too, but I'd
certainly consider those security aspects along the way.

Cheers,
Rong

[rong]

Thanks for the encouraging. It's indeed quite hard to get a big
picture on how it works as there are layers of encapsulation on it,
and no really up-to-date documents can you refer to. If you have any
questions on the existing binder driver, you could try me, not
guaranteed to answer but certainly would be happy to help. Also can
you elaborate a little more about your deadlock issue?

Cheers,
Rong

[dh]

Hi,

I had thought about before too. From the implementation point of view,
you need someone to send you either a binder or handler (like
invitation) to be able to create a kernel level reference (numbered
locally), which you can then use to start transaction with. As the
reference number is created locally, there's no point of guessing or
forging, because if you don't have a local reference, the kernel will
simply reject it. From that perspective, it's probably secure.

That's my point; if I'm wrong, point it out.

/dev/binder is world-writeable on the filesystem. Is it possible to forge an IPC transaction (the id/ref number of the remote node, transaction code which is simply an integer, the parcel data, binder flags, ...) and send it directly from application A to application B, thus circumventing the service manager.

Does the binder implementation perform security checks for such things? If I get you right, the binder module in the kernel DOES do these security checks?!

The first priority of my project was to implement a version that can
be used as a drop replacement, well as much as possible. So logic
mentioned above mostly applies to my implementation too, but I'd
certainly consider those security aspects along the way.

I see that you focused on concurrency and performance. I was just wondering about the security things of binder in earlier work. If the default implementation is secure, then fine. If there are some vulnerabilities, maybe that's interesting for your project.

Cheers, David

[Earlence]

Yes, I'd like to know something about the security of the binder
implementation.
Can I just forge an IPC by talking to /dev/binder?

-Earlence

[rong]

On Feb 10, 12:01 am, dh <david.her...@uni-ulm.de> wrote:
> Hi,
>
> > I had thought about before too. From the implementation point of view,
> > you need someone to send you either a binder or handler (like
> > invitation) to be able to create a kernel level reference (numbered
> > locally), which you can then use to start transaction with. As the
> > reference number is created locally, there's no point of guessing or
> > forging, because if you don't have a local reference, the kernel will
> > simply reject it. From that perspective, it's probably secure.
>
> That's my point; if I'm wrong, point it out.
>
> /dev/binder is world-writeable on the filesystem. Is it possible to forge
> an IPC transaction (the id/ref number of the remote node, transaction code
> which is simply an integer, the parcel data, binder flags, ...) and send it
> directly from application A to application B, thus circumventing the
> service manager.

Okay, need to clarify a bit. First of all, I recall some where in the
android documentation, it describes the binder communication is based
on some kinda shared secret. I think it's not quite right, and often
time words like that can trigger alarms for a lot of security
analysts... :)

First, the service manager does very little things and minimum checks.
All it does it is storing any incoming object handle and name pairs so
others can query handles based on name. It only checks if a
registering (add service) request is coming from a list of known uids,
if not it simply rejects it. Anyone can query a handle using a a name.
The service manager doesn't put any restrictions on it, and I believe
it's up to the actual service provider to check the permissions and so
on when they actually receive a request. Think the service manager as
a DNS server.

In IP connections, for two hosts to take to each other, you need a TCP/
IP connection and a socket (port number, like 80). In terms of binder
IPC, you need a connection between two processes and you need an
object handle to identify which service you are talking to. The kernel
sets up the connection between two processes and creates object
handles (like sockets) for both parties to talk to each other. Again,
like TCP connects, you can't simply inject packets to any existing
connections to forge traffic, you need to be in the loop to be able to
generate legitimate data.

In theory you shouldn't need the service manager to set up an IPC
connection between two processes. But the service provider doesn't
know what process is going to use the service only until the client
process starts making requests, which leaves the service provider no
choice but to publish its service (i.e. object handle) to a known
existing party - the service manager in this case, so later on clients
can get it from there.

So you see, you can't send anything from process A to B without a
proper connection. On the other hand, once the connection is set up
between A and B, communications happen directly between A and B - the
service manager is not involved at all.

These are just my understanding of how the existing binder system
works. Hope it could clear some of your concerns.

[Suryandaru Triandana]

Thanks, will definitely do it. About deadlock, I do little digging Its seem caused when binder holding mmap_sem sometimes never release it, don't know how, I don't dig much futher.

[Brooke]

Hi,

This may seem naive, but what exactly does /dev/binder do? I have some Android code that I'm compiling off target that used to complain about /dev/binder and now it fails since there is no /dev/binder on teh Linux PC. Question I have is whats it doing, why is it needed, and why just Android and not for normal Linux installs?

Appreciate the info - there doesn't seem to be much out there apart from Googles java doc which doesn't mean much when your writing C code.

-Brooke

[Chris Stratton]

On Wednesday, April 11, 2012 9:54:01 PM UTC-4, Brooke wrote:

This may seem naive, but what exactly does /dev/binder do?

It's the device file for accessing a kernel driver which provides a special inter-process communications scheme optimized for use by object-oriented languages and where efficiency is needed.  Android uses it heavily for communication between applications and services and the platform.  It helps with android's ability to give the impression of seamlessly passing objects and paths of execution between processes.  It inherits from a more expansive scheme which some of the engineers who built Android created for some of their earlier projects.

 

 Question I have is whats it doing, why is it needed, and why just Android and not for normal Linux installs?

The later questions were debated on the linux kernel mailing list - some good arguments were made from the perspective of both sides, so it's worth looking up and reading.  Android uses it because android was designed by people who were closely aware of it and felt it offered unique advantages.  More traditional linuxes have instead chosen to rely on older and more widely known ipc mechanism and develop new ones that are more generic (but perhaps heavier) - android uses those too, but not as heavily as it uses binder.