Fix-Point opened a new pull request, #17556:
URL: https://github.com/apache/nuttx/pull/17556
## Summary
High-resolution Timer (HRTimer) is a timer abstraction capable of achieving
nanosecond-level timing precision, primarily used in scenarios requiring
high-precision clock events. With the advancement of integrated circuit
technology, modern high-precision timer hardware (such as the typical x86 HPET)
can already meet sub-nanosecond timing requirements and offer femtosecond-level
jitter control.
Although the current timer abstraction in the NuttX kernel already supports
nanosecond-level timing, its software timer abstraction, wdog, and the timer
timeout interrupt handling process remain at microsecond-level (tick)
precision, which falls short of high-precision timing demands. Therefore, it is
necessary to implement a new timer abstraction—HRTimer, to address the
precision limitations of wdog. HRTimer primarily provides the following
functional interfaces:
- **Set a timer in nanoseconds**: Configure a software timer to trigger at a
specified nanosecond time.
- **Cancel a timer**: Cancel the software timer.
- **Handle timer timeout**: Execute timeout processing after the timer event
is triggered.
# Design
The new NuttX HRTimer is designed to address the issues of insufficient
precision and excessively long interrupt-disabled times in the current NuttX
wdog timer abstraction. It draws on the strengths of the Linux HRTimer design
while improving upon its weaknesses. The HRTimer design is divided into two
parts: the HRTimer Queue and the HRTimer. The HRTimer Queue is a reusable
component that allows users to freely customize their own HRTimer interface by
pairing it with a private timer driver, without needing to modify the kernel
code.
## API Design
The HRTimer Queue is a zero-performance-overhead, composable, and
customizable abstraction that provides only asynchronous-style interfaces:
- **hrtimer_queue_start(queue, timer)**: Asynchronously starts an HRTimer.
- **hrtimer_queue_async_cancel(queue, timer)**: Asynchronously cancels an
HRTimer and returns the current reference count of the timer.
- **hrtimer_queue_wait(queue, timer)**: Waits for the release of all
references to the HRTimer to obtain ownership of the HRTimer data structure.
All other user interfaces can be composed based on these three interfaces.
On top of the HRTimer Queue, users only need to implement the following
interfaces to customize their own HRTimer implementation:
- **hrtimer_expiry(current)**: Handles timer expiration, typically called
within the execution path of the corresponding timer hardware interrupt handler.
- **hrtimer_reprogram(queue, next_expired)**: Sets the next timer event.
- **hrtimer_current()**: Gets the current time to set relative timers.
After implementing the above three interfaces, users can use the
`HRTIMER_QUEUE_GENERATE` template macro to combine and generate their own
hrtimer implementation, which mainly includes the following interfaces:
- **hrtimer_restart(timer, func, arg, time, mode)**: Restarts a timer that
has been asynchronously canceled (its callback function might still be
executing). This interface is designed to explicitly remind users to be aware
of concurrency issues, as concurrency problems are prone to occur in actual
programming and are very difficult to locate. Providing such an interface
facilitates quick identification of concurrency issues.
- **hrtimer_start(timer, func, arg, time, mode)**: Starts a stopped timer.
The mode parameter indicates whether it is a relative or absolute timer.
- **hrtimer_async_cancel(timer)**: Asynchronously cancels a timer. Note that
the semantics of this interface are completely different from Linux's
try_to_cancel. It ensures that the timer can definitely be canceled
successfully, but may need to wait for its callback function to finish
execution.
- **hrtimer_cancel(timer)**: Synchronously cancels a timer. If the timer's
callback function is still executing, this function will spin-wait until the
callback completes. It ensures that the user can always obtain ownership of the
timer.
The design characteristics of HRTimer are as follows:
- **Strict and Simplified HRTimer State Machine:** In the old wdog design,
wdog could be reset in any state, which introduced unnecessary complexity to
certain function implementations. For example, `wd_start` had to account for
the possibility of restarting. In the new HRTimer design, an HRTimer that has
already been started and not canceled cannot be started again.
- **Abstracted Sorting Queue:** Since no single design can be optimal for
all application scenarios, HRTimer abstracts interfaces for inserting and
deleting nodes in the sorting queue. This allows for different data structure
implementations to be configured for different application scenarios, as shown
in Table 1.
**Table 1: Comparison of Several Sorting Queue Implementations**
| Sorting Queue Implementation | Insert | Delete | Delete Head |
Determinism | Suitable Scenarios |
| :--- | :--- | :--- | :--- | :--- | :--- |
| Doubly Linked List | O(n) | O(1) | O(1) | Moderate | Embedded / Soft
Real-time Systems |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | Slightly Poor |
General Purpose |
- **Callback Execution Without Lock Held:** HRTimer implements callback
execution without lock held, ensuring that the system's blocking time is not
limited by the user's callback function. However, this introduces additional
states and waits, where waiting for reference release is primarily implemented
using hazard pointers. This will be explained in detail in the subsequent state
transition diagram.
- **Clear HRTimer Object Ownership Transfer Path:** In the wdog
implementation, the wdog callback function could restart the current timer
directly without regard to ownership, potentially causing concurrency issues.
In the new implementation, the HRTimer callback function cannot restart itself.
Instead, inspired by Linux's design, the callback function returns whether a
restart is needed. If a restart is required, the thread executing the callback
function re-enqueues it; otherwise, the thread releases ownership. This change
ensures a clear ownership transfer path for the HRTimer object.
- **Non-blocking Timer Restart:** To address the issue in Linux where
restarting a timer must wait for an already-started callback function to
finish, which reduces the real-time performance, the new HRTimer implements a
non-blocking timer restart mechanism. This mechanism reuses the last bit of the
hazard pointer to mark whether the thread executing the callback has lost write
ownership of the HRTimer object. After `hrtimer_cancel` is called, other
threads executing callbacks will lose write ownership of the HRTimer (though
their callback functions may still be executing). This means the HRTimer can be
restarted and repurposed for other callbacks without waiting for the callback
function to complete. However, note that the callback function might still be
executing, requiring users to consider this concurrency and implement proper
synchronization mechanisms within their callback functions. To explicitly
remind users of this concurrency, an HRTimer whose callback function has not
yet completed execution must be restarted using `hrtimer_restart`. This
function relaxes the state checks on the HRTimer, allowing a timer with pending
waits to be started.
- **Deterministic Timer Cancellation:** To address the starvation issue
present in Linux's timer cancellation, the new HRTimer implementation sets a
cancellation state via `hrtimer_cancel`. This cancellation state has a unique
and deterministic state transition, eliminating starvation. Memory reclamation
is performed through hazard pointer checking loops. Hazard pointer checking
ensures that all threads finish executing the callback function and release
read ownership (reference release) of the specified HRTimer object.
The valid state transitions of an HRTimer object are shown in Figure 2.
States are represented using a simplified notation of `State|Ownership`, such
as `HRTIMER_PENDING|shared`. The meanings of the simplified ownership markers
are as follows:
**Ownership Markers**
- `|private` indicates that the resource is exclusively owned by a specific
thread `t`. Only the owning thread `t` can read from or write to this resource.
- `|shared` indicates that the resource is globally shared and can be read
by any thread. However, only the thread `t` that holds the global lock `l` (`t
= Owned(l)`) can obtain write ownership of this resource.
- `|half_shared` indicates that the resource may be accessed by multiple
threads, but only the thread that called `set_cancel` holds write ownership of
this resource. Modifications to it by threads executing callback functions are
prevented.
The resource ownership here uses a simplified notation. In actual static
analysis or formal verification processes, more complex abstractions such as
resource algebra might be employed.
All state transitions not described in the diagram must return failure. For
example, a timer in the `HRTIMER_PENDING` state cannot be started (`start`)
again. Note that there is one exception: a thread that is already in the
`HRTIMER_CANCELED` state can legally call `hrtimer_async_cancel` again, and the
state remains unchanged.
To avoid the overhead caused by threads waiting for callback functions to
finish executing, HRTimer adds a `restart` interface. Under normal
circumstances, the `start` interface cannot start a timer that is already in
the `canceled` state. Only when the user uses this `restart` interface can a
timer whose callback function has not yet completed be started normally. Using
this interface serves to explicitly remind users to pay attention to
concurrency within their callback functions. Furthermore, when concurrency
issues arise with HRTimer, it helps in pinpointing the source of the
problem—issues can only originate from callback functions where `restart` was
used to restart the timer.
**Figure 2 HRTimer State Transition Diagram**
```mermaid
%%{
init: {
'theme': 'base',
'themeVariables': {
'primaryColor': '#FFFFFF',
'primaryTextColor' : '#000000',
'mermiad-container': "#FFFFFF",
'primaryBorderColor': '#000000',
'lineColor': '#000000',
'secondaryColor': '#FFFFFF',
'tertiaryColor': '#000000'
},
'sequence': { 'mirrorActors': false }
}
}%%
stateDiagram-v2
HRTIMER_COMPLETED|private --> HRTIMER_PENDING|shared : hrtimer_start
HRTIMER_PENDING|shared --> HRTIMER_COMPLETED|private : hrtimer callback
return 0 in hrtimer_expiry
HRTIMER_PENDING|shared --> HRTIMER_PENDING|shared : hrtimer callback
return non-zero in hrtimer_expiry
HRTIMER_PENDING|shared --> HRTIMER_CANCELED|half_shared :
hrtimer_async_cancel
HRTIMER_CANCELED|half_shared --> HRTIMER_CANCELED|private :
hrtimer_cancel wait all cores release the references to the timer.
HRTIMER_CANCELED|half_shared --> HRTIMER_PENDING|shared : hrtimer_restart
HRTIMER_CANCELED|private --> HRTIMER_COMPLETED|private : Complete the
cancel
```
# Performance Evaluation
We conducted 1 million interface calls on the `intel64:nsh` (Intel 12700)
platform and measured their average execution CPU cycles, as shown in the
Figure 3 below. It can be observed that the overhead for inserting and deleting
timers is significantly reduced compared to wdog. Additionally, after enabling
hrtimer, wdog processing is treated as an hrtimer timer, which lowers the
overhead of the wdog interface.
<img width="800" height="600" alt="hrtimer tsv"
src="https://github.com/user-attachments/assets/232947b1-a599-46f4-a19d-0ea390ae5046";
/>
Figure 3 HRtimer API Latency Test.
# Plan
The merge plan for this PR is as follows:
1. Introduce definitions of rmb/wmb memory barriers (done by hujun)
2. Introduce seqlock (done by hujun/Fix-Point)
3. Simplify the scheduler processing flow in preparation for introducing
HRtimer
4. Modify the semantics of scheduling functions to allow immediate timer
event triggering.
5. Fix buggy wdog to avoid attributing faults to the introduction of hrtimer
6. Introduce hrtimer_queue
7. Introduce hrtimer
8. [WIP] Introdude hrtimer_test
9. [WIP] Add HRtimer documents.
## Impact
*Update this section, where applicable, on how change affects users,
build process, hardware, documentation, security, compatibility, etc.*
## Testing
Tested on `intel64:nsh`, `rv-virt:smp`, `qemu-armv8a:smp`, `ostest` passed.
The hrtimer parallel stress test ran for over 72 hours without errors.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
