New watchdog handler implementation
|Reported by:||Sebastian Huber||Owned by:||Sebastian Huber|
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 timer wheel based algorithm which is used in Linux and 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.
_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.
Change History (17)
Changed 13 months ago by Sebastian Huber