kdbus: add documentation

kdbus is a system for low-latency, low-overhead, easy to use
interprocess communication (IPC).

The interface to all functions in this driver is implemented through ioctls
on /dev nodes.  This patch adds detailed documentation about the kernel
level API design.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add header file

This patch adds the header file which describes the low-level
transport protocol used by various ioctls. The header file is located
in uapi as it is shared between kernel and userspace, and it only
contains data structure definitions and #defines for constants.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add driver skeleton, ioctl entry points and utility functions

Add the basic driver structure.

handle.c is the main ioctl command dispatcher that calls into other parts of
the driver.

main.c contains the code that creates the initial domain at startup, and
util.c has utility functions such as item iterators that are shared among
other files.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add connection pool implementation

A pool for data received from the kernel is installed for every
connection of the bus, and it is used to copy data from the kernel to
userspace clients, for messages and other information.

It is accessed when one of the following ioctls is issued:

  * KDBUS_CMD_MSG_RECV, to receive a message
  * KDBUS_CMD_NAME_LIST, to dump the name registry
  * KDBUS_CMD_CONN_INFO, to retrieve information on a connection

Internally, the pool is organized in slices, and implements a buddy system.
The offsets returned by either one of the aforementioned ioctls describe
offsets inside the pool. In order to make the slice available for subsequent
calls, KDBUS_CMD_FREE has to be called on the offset.

To access the memory, the caller is expected to mmap() it to its task.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add connection, queue handling and message validation code

This patch adds code to create and destroy connections, to validate
incoming messages and to maintain the queue of messages that are
associated with a connection.

Note that connection and queue have a 1:1 relation, the code is only
split in two parts for cleaner separation and better readability.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add code to gather metadata

A connection chooses which metadata it wants to have attached to each
message it receives with kdbus_cmd_hello.attach_flags. The metadata
will be attached as items to the messages. All metadata refers to
information about the sending task at sending time, unless otherwise
stated. Also, the metadata is copied, not referenced, so even if the
sending task doesn't exist anymore at the time the message is received,
the information is still preserved.

See kdbus.txt for more details on which metadata can currently be
attached to messages.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add code for notifications and matches

This patch adds code for matches and notifications.

Matches:

A message addressed at the connection ID 0 (KDBUS_DST_ID_BROADCAST) is
a broadcast message, delivered to all connected peers which installed
a rule to match certain properties of the message. Without any rules
installed in the connection, no broadcast message or kernel-side
notifications will be delivered to the connection.

Matches for messages from other connections (not kernel notifications)
are implemented as bloom filters. The sender adds certain properties
of the message as elements to a bloom filter bit field, and sends
that along with the broadcast message.

The connection adds the message properties it is interested as elements
to a bloom mask bit field, and uploads the mask to the match rules
of the connection.

The kernel will match the broadcast message's bloom filter against
the connections bloom mask (simply by &-ing it), and decide whether
the message should be delivered to the connection.

The kernel has no notion of any specific properties of the message,
all it sees are the bit fields of the bloom filter and mask to match
against. The use of bloom filters allows simple and efficient matching,
without exposing any message properties or internals to the kernel
side. Clients need to deal with the fact that they might receive
broadcasts which they did not subscribe to, as the bloom filter might
allow false-positives to pass the filter.

To allow the future extension of the set of elements in the
bloom filter, the filter specifies a "generation" number. A later
generation must always contain all elements of the set of the previous
generation, but can add new elements to the set. The match rules mask
can carry an array with all previous generations of masks individually
stored. When the filter and mask are matched by the kernel, the mask
with the closest matching "generation" is selected as the index into
the mask array.

Notifications:

The kernel will notify its users of the following events.

  * When connection A is terminated while connection B is waiting
    for a reply from it, connection B is notified with a message with
    an item of type KDBUS_ITEM_REPLY_DEAD.

  * When connection A does not receive a reply from connection B
    within the specified timeout window, connection A will receive a
    message with an item of type KDBUS_ITEM_REPLY_TIMEOUT.

  * When a connection is created on or removed from a bus, messages
    with an item of type KDBUS_ITEM_ID_ADD or KDBUS_ITEM_ID_REMOVE,
    respectively, are sent to all bus members that match these
    messages through their match database.

  * When a connection owns or loses a name, or a name is moved from one
    connection to another, messages with an item of type
    KDBUS_ITEM_NAME_ADD, KDBUS_ITEM_NAME_REMOVE or
    KDBUS_ITEM_NAME_CHANGE are sent to all bus members that match these
    messages through their match database.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add code for buses, domains and endpoints

Add the logic to handle the following entities:

Domain:
  A domain is a named object containing a number of buses. A
  system container that contains its own init system and
  users usually also runs in its own kdbus domain. The
  /dev/kdbus/domain/<container-name>/ directory shows up inside
  the domain as /dev/kdbus/. Every domain offers its own "control"
  device node to create new buses or new sub-domains.  Domains have
  no connection to each other and cannot see nor talk to each
  other. See section 5 for more details.

Bus:
  A bus is a named object inside a domain. Clients exchange messages
  over a bus. Multiple buses themselves have no connection to each
  other; messages can only be exchanged on the same bus. The default
  entry point to a bus, where clients establish the connection to, is
  the "bus" device node /dev/kdbus/<bus name>/bus.  Common operating
  system setups create one "system bus" per system, and one "user
  bus" for every logged-in user. Applications or services may create
  their own private named buses. See section 5 for more details.

Endpoint:
  An endpoint provides the device node to talk to a bus. Opening an
  endpoint creates a new connection to the bus to which the endpoint
  belongs. Every bus has a default endpoint called "bus". A bus can
  optionally offer additional endpoints with custom names to provide
  a restricted access to the same bus. Custom endpoints carry
  additional policy which can be used to give sandboxed processes
  only a locked-down, limited, filtered access to the same bus.

See kdbus.txt for more details.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add name registry implementation

This patch adds the name registry implementation.

Each bus instantiates a name registry to resolve well-known names
into unique connection IDs for message delivery. The registry will
be queried when a message is sent with kdbus_msg.dst_id set to
KDBUS_DST_ID_NAME, or when a registry dump is requested.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add policy database implementation

This patch ass the policy database implementation.

A policy databases restrict the possibilities of connections to own,
see and talk to well-known names. It can be associated with a bus
(through a policy holder connection) or a custom endpoint.

By default, buses don't have a policy database but create one on
demand as soon as a policy holder connection is instantiated.

Policies are set through KDBUS_CMD_HELLO (when creating a policy
holder connection), KDBUS_CMD_CONN_UPDATE (when updating a policy
holder connection), KDBUS_CMD_EP_MAKE (creating a custom endpoint)
or KDBUS_CMD_EP_UPDATE (updating a custom endpoint). In all cases,
the name and policy access information is stored in items of type
KDBUS_ITEM_NAME and KDBUS_ITEM_POLICY_ACCESS.

See kdbus.txt for more details.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add Makefile, Kconfig and MAINTAINERS entry

This patch hooks up the build system to actually compile the files
added by previous patches. It also adds an entry to MAINTAINERS to
direct people to Greg KH, David Herrmann and me for questions and
patches.

Signed-off-by: Daniel Mack <daniel@zonque.org>
kdbus: add selftests

This patch adds a quite extensive test suite for kdbus that checks
some of the most important code pathes in the driver. It's of course
impossible to check for every corner case, but the idea is to extend
the test suite over time.

Also, this code can serve as an example implementation to show how to
use the kernel API from userspace.

Signed-off-by: Daniel Mack <daniel@zonque.org>