FreeLists / openbeosstorage / [openbeosstorage] Registrar-Based Notification Mechanism

[Ingo Weinhold <bonefish@xxxxxxxxxxxxxxx>]

Howdy,

since I expect to reach the point where kernel notifications will be
needed, soon, I think, it's time to present my ideas for a general
registrar-based notification mechanism for your evaluation.

The general idea is to move as much functionality as possible from the
kernel to a userland server -- the registrar. The expected positive
effects are:

* No (flattened) BMessages in the kernel.

* Similar performance of the kernel entity causing the notification
independent of the number of listeners. Maybe even slightly better
performance for no/one listener.

* No more dropping of notification messages, in case the target port is
full at the moment of the event.

Possible negative effects:

* Higher `event occurence -> arriving of notification' latency.

* More resource usage: thread(s), semaphores and memory


The general strategy to achieve that is the following:

When an event occurs the kernel notifies the registrar, which manages the
lists of listeners and sends the actual notification messages. The
kernel->registrar communication is done via shared memory; for the other
direction syscalls can be used.

Let me refine the different aspects:

1) Subscription/unsubscription for notifications: This is a bit ugly,
since the functions for that live in libroot and the primary target for
the request is the registrar. Either the request is passed through a port
directly to the registrar, or it travels into the kernel and goes the same
way the to the registrar the notifications take (i.e. through the shared
memory). Once there, the listener is added to the appropriate
list/hashtable/...

For it should be avoided that the kernel notifies the registrar on an
event noone is interested in, there still needs to be a structure in the
kernel, holding the information, which events are listened. The registrar
needs to tell the kernel whenever this info has changed. This structure
could be in shared memory too, but, since subscription/unsubscription is
not time-critical, syscalls may be the better choice. Rare events
(mounting, appearing/disappearing of device and the like) can, of course,
always be sent to the registrar.

2) The kernel-side interface: Once the registrar is running it allocates
the shared memory and tells the kernel via a syscall. The layout of this
memory is relatively simple. It has a little header containing general
information, and the rest is a ring buffer containing notification
entries. The access is protected by a mutex and there is a semaphore
counting the entries in the buffer (being released, when a new one is
added and acquired when one is going to be taken out).

A notification entry is a structure like

  struct notification_entry {
    uint32 event;
    size_t size;
  };

The structure is extended for the specific events. `event' identifies the
event and `size' is the size of the whole structure.

The kernel can add an entry using the following two functions:

  status_t reserve_notification_entry(uint32 event, size_t size,
                                      notification_entry **entry);
  void commit_notification_entry();

The first function locks the mutex, reserves enough space in the ring
buffer and returns a pointer to it. Then the caller can write their
additional data into the entry and invoke commit_notification_entry(),
which unlocks the mutex and releases the counter semaphore.

In case the ring buffer is full, reserve_notification_entry() allocates
memory for the entry on the heap and pushes it into a queue. The next call
to it will first try to empty the queue -- copying its contents into the
ring buffer -- and proceed as usual, i.e. reserve ring buffer space or
alloc memory and use the queue respectively.

That the ring buffer runs full should be a very+ rare event, of course. To
catch a special case: If there are still entries in the queue although the
registrar completely emptied the ring buffer meanwhile -- this can happen,
when reserve_notification_entry() has not been called since -- it can
invoke a syscall, which flushes the queue.

3) The registrar side interface: Of course corresponding functions are
needed to pop entries from the ring buffer. A dedicated registrar thread
does nothing else than waiting for entries (on the counter semaphore),
copying them into the heap and pushing them into a queue another thread is
working with. The thread does not do any conversion, e.g. into BMessages,
or anything like this. The main reason is to keep the ring buffer as empty
as possible and to keep locking times very low. The latter point is
important to delay the kernel side threads only as little as necessary.

4) Inside the registrar: As mentioned before there is a second thread in
the registrar, that processes the entries pushed into the queue by the
first one. It pops an entry, converts it into a BMessage and looks up,
which listeners are interested. There is a structure which provides a
mapping of target ports to a queue of pending notification messages
(only, if the queue is non-empty). For each target the notification
message shall be sent to, it is checked whether there is an entry in this
structure, i.e. whether there are already pending messages.

If not, the message is tried to be delivered with timeout 0. If that
fails, a new entry is created for that port and a copy of the message is
pushed into the pending messages queue.

If there are already pending messages for the target port, they are tried
to be delivered, followed by the new message. The messages that could not
be delivered remain in the queue. If the queue is empty, the entry for
that target port is removed completely.

Of course additionally it must periodically be tried to deliver pending
messages. And sanity checks need to prevent that for bad targets thousands
of pending messages are piled.

BTW, there is quite some potential for optimization, e.g. by flattening a
notification message very early (i.e. directly after setting it up) and
writing the flattened message to the target ports instead of using the
high-level API for sending BMessages, which would cause the message to be
flattened each time it is tried to be sent.


Mmh, that's it, I think. At least my mind feels a bit emptier now. ;-)

CU, Ingo