[RTEMS Project] #2554: New watchdog handler implementation

[RTEMS trac]

#2554: New watchdog handler implementation
-----------------------------+-----------------------------
 Reporter:  sebastian.huber  |      Owner:  sebastian.huber
     Type:  enhancement      |     Status:  new
 Priority:  normal           |  Milestone:  4.12
Component:  cpukit           |    Version:  4.12
 Severity:  normal           |   Keywords:
-----------------------------+-----------------------------
 = Background =

 The watchdog handler uses delta chains.  The insert operation has a O(n)
 worst-case time complexity with n being the count of watchdogs in the
 delta chain.  In each step of the insert operation, the SMP lock of the
 corresponding watchdog header is acquired and released.  The profiling
 data obtain by test program `smptests/smpwakeafter01` showed that the
 current implementation leads to unacceptable latencies, thus it should be
 replaced by something else.

 The use cases for the watchdog handler fall roughly into two categories.
 * Timeouts - used to detect if some operations needs more time than
 expected.  Since the unexpected happens hopefully rarely, timeout timers
 are usually removed before they expire.  The critical operations are
 insert and removal.  They are important for the performance of a network
 stack.
 * Timers - used to carry out some work in the future.  They usually expire
 and need a high resolution.  An example user is a time driven scheduler,
 e.g.  rate-monotonic or EDF.

 One approach is to use a red-black tree with the expiration time as the
 key.  This leads to O(log(n)) worst-case insert and removal operations.
 For each operation it is sufficient to acquire and release the lock only
 once.  The drawback is that a 64-bit integer type must be used for the
 intervals to avoid a potential overflow of the key values. With a system
 tick interval of 1ns the system could run more than 500 years before an
 overflow happens.  The EDF scheduler would also profit from a 64-bit
 interval representation, see #2173.

 An alternative is the use of a
 [http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf
 timer wheel] based algorithm which is used in Linux and
 [http://web.mit.edu/afs.new/sipb/user/daveg/ATHENA/Info/wucs-95-23.ps
 FreeBSD] for example.  A timer wheel based algorithm offers O(1) worst-
 case time complexity for insert and removal operations.  The drawback is
 that the run-time of the watchdog tick procedure is somewhat unpredictable
 due to the use of a hash table or cascading.

 Which approach should we choose?  Since the watchdog serves the timeout
 and timer services in RTEMS we have to make some trade-offs.  We recommend
 to use the red-black tree approach which offers a more predictable run-
 time behaviour and sacrifice the constant insert and removal operations
 offered by the timer wheel algorithms, see also
 https://www.kernel.org/doc/ols/2006/ols2006v1-pages-333-346.pdf.  We can
 reuse the red-black tree support already used for the thread priority
 queues.

 The new watchdog handler implementation is a prerequisite to eliminate the
 Giant lock in the Classic Timer manager.

 = Implementation =

 Change the `_Watchdog_Ticks_since_boot` to a 64-bit integer type.  Keep
 the `Watchdog_Interval` at 32-bit for backward compatibility.  Replace the
 delta chains with a red-black tree.  Use the ticks for timers with a
 relative expiration time.  Use `struct timespec` or `struct bintime` for
 timers with an absolute expiration time.  This has the benefit that we do
 not have to adjust the data structures in case the absolute time changes,
 e.g.  due to NTP.  It simplifies the POSIX timer services, since no
 conversion to ticks is necessary.

--
Ticket URL: <http://devel.rtems.org/ticket/2554>
RTEMS Project <http://www.rtems.org/>
RTEMS Project