libtscb - Thread-safe callback services

0.1

This library provides classes for notifications via callbacks in multi-threaded programs. In particular, it provides the following services:

• Signals and slots: signal_proxy provides an interface through which interested receivers can connect/disconnect callback functions at runtime. signal provides an implementation of this interface and provides senders a mechanism to notify interested receivers, passing specified arguments to each callback function.
• I/O readiness: ioready_service provides an interface through which interested receivers can register/deregister for notification on I/O readiness events (i.e. file descriptor ready for reading/writing; cf. poll/select). ioready_dispatcher provides an implementation of this interface that allows waiting (with timeout) for and fetching the required information from the operating system and notifying registered receivers.
• Timers: timer_service provides an interface through which interested receivers can register/deregister for notification at specific points in time. timerqueue_dispatcher provides an implementation of this interface, keeping track of all pending timers, deadline when next timer is due, and "premature interruption" if the deadline must be invalidated (e.g. due to a newly-added timer).
• Compound event dispatching (or "reactor-style" operation): posix_reactor_service combines the ioready_service, timer_service and workqueue_service interfaces. posix_reactor provides an implementation of this interface and performs all required operations of delivering all requested notifications.

The implementations in this library provide strong thread-safety guarantees, are reentrant, deadlock-free and provide strong consistency guarantees. See section Concurrency and reentrancy below for an exact definition of the guarantees.

Design goals and principles

Interfaces

The library strictly separates the interfaces for registering callbacks from the implementations that provide notifications. The rationale for this design decision is to two-fold: First, it allows implementors to export an interface allowing only registration. Consider the following classes:

        class Observable1 {
        public:
                tscb::signal<void(int, int)> on_value_change;
                
                void change_value(int new_value)
                {
                        int old_value=value;
                        value=new_value;
                        on_value_change(old_value, new_value);
                }
        protected:
                int value;
                
        };
        
        class Observable2 {
        public:
                tscb::signal_proxy<void(int, int)> &on_value_change(void) throw()
                {
                        return value_change;
                }
                
                void change_value(int new_value)
                {
                        int old_value=value;
                        value=new_value;
                        value_change(old_value, new_value);
                }
        protected:
                int value;
                tscb::signal<void(int, int)> value_change;
        };

Both classes allow an observer to register callbacks (via Observable1::on_value_change::connect(...) or Observable2::on_value_change()connect(...), respectively), but Observable1 also exports the capability to notify registered callbacks to external classes (which is probably unintended).

The second reason is to decouple "consumers" of notifications from the exact mechanism used for providing them. Classes only interested in receiving notification should depend on posix_reactor_service instead of posix_reactor: The former allows the implementation to be supplanted by a "bridge class" that delegates to services provided by other frameworks such as Qt or Gtk. (FIXME: Qt/Glib support split out into dependent libraries, not sure if worth maintaining in separate repository).

Concurrency and reentrancy

Let A,B,C,... denote receivers (i.e. functions that can be registered as callbacks) and X,Y,Z event sources (e.g. signals, posix_reactors with registration and notification capability. The library generally supports the following operations:

• Registration of a new callback A,B,... at a notification service X,Y
• Modification of callbacks A,B... pending at X,Y (e.g. changing the set of events the receiver is interested in)
• Deregistration of callback A,B,... previously registered to X,Y
• Notification through X,Y to all registered callbacks
• Deconstruction of the event provider X,Y (which therefore ceases to deliver notifications)

All implementations provide the following concurrency guarantees:

• Any concurrent Registration A₁, A₂,... to X₁, X₂ Deregistration B₁, B₂ from X₁, X₂, Modification B₁, B₂ at X₁, X₂, Notification through X₁, X₂, Deconstruction of Y₁, Y₂ is safe.
• Any concurrent Deregistration B₁, B₂ from X₁, X₂, Modification B₁, B₂ at X₁, X₂, Notification through X₁, X₂, Deconstruction of X₁, X₂ is safe.

All implementations provide the following reentrancy guarantee: From within a callback A registered to service X, the following operations may be performed:

• Registration B to X,Y
• Deregistration A,C from X,Y
• Modification A,C at X,Y
• Notification through X,Y
• Deconstruction of Z

Finally, the implementation provides the folliwing consistency guarantee: If a callback is deregistered it will not be invoked "subsequently" from the same or other threads. For the same thread, "subsequently" refers to the normal flow of execution after the disconnect operation returns. For other threads this means that if

• disconnect returns in thread A
• thread A accesses a memory location with "release" semantics
• thread B accesses the same memory location with "acquire" semantics
  the corresponding callback will not be invoked from thread B. (Note that this guarantee provides essentially "causal consistency" and is thus what implementors will generally expect).

Implementation notes

Synchronization

The aim of this library is to maximize concurrency while minimizing the overhead introduced through the required synchronization mechanisms, ideally to the point where the overhead becomes pretty much negligible so that even single-threaded applications (where the synchronization is unnecessary) can afford to pay the price.

These goals are achieved by employing synchronization mechanisms that generally allow readers to access shared data structures without any locking, with carefully designed access protocols using appropriate atomic operations to ensure consistency. "Critical" operations that might affect concurrent readers are split up into "safe" modifications that may be performed at any time (e.g. modifying a forward-traversable linked list) and "unsafe" modifications that must be deferred to quiescent periods where no reader is active (e.g. freeing memory of objects accessed without locking). In almost all fast-path cases the overhead over a highly optimized single-threaded implementation is just two atomic operations and is thus very close to the theoretical optimum.

The basic access idiom to shared data structures for readers is:

1. Increment the "active" marker (an atomic counter)
2. Access required parts of the data structure (almost) freely (*)
3. Decrement the "active" marker
4. If "active" marker dropped to, check for and execute pending deferred "unsafe" operations

Writers must adhere to the following protocol:

1. Lock out other writers, increment "active" marker
2. Perform "safe" modifications, queue up "unsafe" operations
3. Allow other writers, decrement "active" marker
4. If "active" marker dropped to zero, check for and execute pending deferred "unsafe" operations

Note during the step marked (*) above, it is permissible to initiate nested read or write acesses using the same synchronization idiom without access or conflicts or potential for deadlock.

The library relies on the C++0x atomic datatypes, an implementation of the required functional subset is provided for gcc on various target machines in order to make the library useful with older compilers and systems.

Performance

Comparison with other libraries; given values are normalized to number of CPU clock cycles per operation (smaller is better)

Signal/slot mechanism

Debian Linux 5.0, gcc-4.3.2, Intel Celeron @2GHz

Implementation	call single callback	call 10 callbacks	connect+disconnect	comments
open-coded (std::list of function pointers)	16	150	92	not thread-safe
open-coded (std::list of boost::function objects)	33	320	254	not thread-safe
tscb::signal	120	436	1286	thread-safe
sigc::signal	280	400	1216	not thread-safe
boost::signal	432	1310	3362	not thread-safe
boost::signals2	593	2803	2146	thread-safe

Debian Linux 5.0, gcc-4.3.2, DEC Alpha EV6 @500MHz

Implementation	call single callback	call 10 callbacks	connect+disconnect	comments
open-coded (std::list of function pointers)	16	141	458	not thread-safe
open-coded (std::list of boost::function objects)	32	333	576	not thread-safe
tscb::signal	157	472	2164	thread-safe
sigc::signal	576	812	2885	not thread-safe
boost::signal	796	1810	11241	not thread-safe

I/O dispatching

n pipe pairs, n handler functions that read a token out of one pipe and write it into the next one. Numbers indicate clock cycles per single dispatch operation (one forwarding of the token to the next pipe).

Debian Linux 5.0, gcc-4.3.2, Intel Celeron @2GHz

Implementation	32 pipe pairs	64 pipe pairs	128 pipe pairs
open-coded (epoll_wait+read+write)	2425	2439	2477
ACE	3469	3460	3494
tscb::posix_reactor	3292	3308	3344
boost::asio	11406	11426	11536