[RFC,v2,0/2] Add high-performance timer facility

This patchset is an attempt to introduce a high-performance, highly
scalable timer facility into DPDK.

More specifically, the goals for the htimer library are:

* Efficient handling of a handful up to hundreds of thousands of
  concurrent timers.
* Make adding and canceling timers low-overhead, constant-time
  operations.
* Provide a service functionally equivalent to that of
  <rte_timer.h>. API/ABI backward compatibility is secondary.

In the author's opinion, there are two main shortcomings with the
current DPDK timer library (i.e., rte_timer.[ch]).

One is the synchronization overhead, where heavy-weight full-barrier
type synchronization is used. rte_timer.c uses per-EAL/lcore skip
lists, but any thread may add or cancel (or otherwise access) timers
managed by another lcore (and thus resides in its timer skip list).

The other is an algorithmic shortcoming, with rte_timer.c's reliance
on a skip list, which is less efficient than certain alternatives.

This patchset implements a hierarchical timer wheel (HWT, in
rte_htw.c), as per the Varghese and Lauck paper "Hashed and
Hierarchical Timing Wheels: Data Structures for the Efficient
Implementation of a Timer Facility". A HWT is a data structure
purposely design for this task, and used by many operating system
kernel timer facilities.

To further improve the solution described by Varghese and Lauck, a
bitset is placed in front of each of the timer wheel in the HWT,
reducing overhead of rte_htimer_mgr_manage() (i.e., progressing time
and expiry processing).

Cycle-efficient scanning and manipulation of these bitsets are crucial
for the HWT's performance.

The htimer module keeps a per-lcore (or per-registered EAL thread) HWT
instance, much like rte_timer.c keeps a per-lcore skip list.

To avoid expensive synchronization overhead for thread-local timer
management, the HWTs are accessed only from the "owning" thread.  Any
interaction any other thread does with a particular lcore's timer
wheel goes over a set of DPDK rings. A side-effect of this design is
that all operations working toward a "remote" HWT must be
asynchronous.

The <rte_htimer.h> API is available only to EAL threads and registered
non-EAL threads.

The htimer API allows the application to supply the current time,
useful in case it already has retrieved this for other purposes,
saving the cost of a rdtsc instruction (or its equivalent).

Relative htimer does not retrieve a new time, but reuse the current
time (as known via/at-the-time of the manage-call), again to shave off
some cycles of overhead.

A semantic improvement compared to the <rte_timer.h> API is that the
htimer library can give a definite answer on the question if the timer
expiry callback was called, after a timer has been canceled.

The patchset includes a performance test case
'timer_htimer_htw_perf_autotest', which compares rte_timer, rte_htimer
and rte_htw timers in the same scenario.

'timer_htimer_htw_perf_autotest' suggests that rte_htimer is ~3-5x
faster than rte_timer for timer/timeout-heavy applications, in a
scenario where the timer always fires. For a scenario with a mix of
canceled and expired timers, the performance difference is greater.

In scenarios with few timeouts, rte_timer has lower overhead than
htimer, but both variants consume very little CPU time.

In certain scenarios, rte_timer does not suffer from
non-constant-time-add and cancel operations. On such is in case the
timer added is always last in the list, where htimer is only ~2-3x
faster.

The bitset implementation which the HWT implementation depends upon
seemed generic-enough and potentially useful outside the world of
HWTs, to justify being located in the EAL.

This patchset is very much an RFC, and the author is yet to form an
opinion on many important issues.

* If deemed a suitable replacement, should the htimer replace the
  current DPDK timer library in some particular (ABI-breaking)
  release, or should it live side-by-side with the then-legacy
  <rte_timer.h> API? A lot of things in and outside DPDK depend on
  <rte_timer.h>, so coexistence may be required to facilitate a smooth
  transition.

* Should the htimer and htw-related files be colocated with rte_timer.c
  in the timer library?

* Would it be useful for applications using asynchronous cancel to
  have the option of having the timer callback run not only in case of
  timer expiration, but also cancellation (on the target lcore)? The
  timer cb signature would need to include an additional parameter in
  that case.

* Should the rte_htimer be a nested struct, so the htw parts be separated
  from the htimer parts?

* <rte_htimer.h> is kept separate from <rte_htimer_mgr.h>, so that
  <rte_htw.h> may avoid a depedency to <rte_htimer_mgr.h>. Should it
  be so?

* rte_htimer struct is only supposed to be used by the application to
  give an indication of how much memory it needs to allocate, and is
  its member are not supposed to be directly accessed (w/ the possible
  exception of the owner_lcore_id field). Should there be a dummy
  struct, or a #define RTE_HTIMER_MEMSIZE or a rte_htimer_get_memsize()
  function instead, serving the same purpose? Better encapsulation,
  but more inconvenient for applications. Run-time dynamic sizing
  would force application-level dynamic allocations.

* Asynchronous cancellation is a little tricky to use for the
  application (primarily due to timer memory reclamation/race
  issues). Should this functionality be removed?
  
* Should rte_htimer_mgr_init() also retrieve the current time? If so,
  there should to be a variant which allows the user to specify the
  time (to match rte_htimer_mgr_manage_time()). One pitfall with the
  current proposed API is an application calling rte_htimer_mgr_init()
  and then immediately adding a timer with a relative timeout, in
  which case the current absolute time used is 0, which might be a
  surprise.

* Would the event timer adapter be best off using <rte_htw.h>
  directly, or <rte_htimer.h>? In the latter case, there needs to be a
  way to instantiate more HWTs (similar to the "alt" functions of
  <rte_timer.h>)?

* Should the PERIODICAL flag (and the complexity it brings) be
  removed? And leave the application with only single-shot timers, and
  the option to re-add them in the timer callback.

* Should the async result codes and the sync cancel error codes be merged
  into one set of result codes?

* Should the rte_htimer_mgr_async_add() have a flag which allow
  buffering add request messages until rte_htimer_mgr_process() is
  called? Or any manage function. Would reduce ring signaling overhead
  (i.e., burst enqueue operations instead of single-element
  enqueue). Could also be a rte_htimer_mgr_async_add_burst() function,
  solving the same "problem" a different way. (The signature of such
  a function would not be pretty.)

* Does the functionality provided by the rte_htimer_mgr_process()
  function match its the use cases? Should there me a more clear
  separation between expiry processing and asynchronous operation
  processing?

* Should the patchset be split into more commits? If so, how?

Thanks to Erik Carrillo for his assistance.

Mattias Rönnblom (2):
  eal: add bitset type
  eal: add high-performance timer facility

 app/test/meson.build                  |  12 +-
 app/test/test_bitset.c                | 645 +++++++++++++++++++
 app/test/test_htimer_mgr.c            | 674 ++++++++++++++++++++
 app/test/test_htimer_mgr_perf.c       | 322 ++++++++++
 app/test/test_htw.c                   | 478 ++++++++++++++
 app/test/test_htw_perf.c              | 181 ++++++
 app/test/test_timer_htimer_htw_perf.c | 693 ++++++++++++++++++++
 doc/api/doxy-api-index.md             |   5 +-
 doc/api/doxy-api.conf.in              |   1 +
 lib/eal/common/meson.build            |   1 +
 lib/eal/common/rte_bitset.c           |  29 +
 lib/eal/include/meson.build           |   1 +
 lib/eal/include/rte_bitset.h          | 879 ++++++++++++++++++++++++++
 lib/eal/version.map                   |   3 +
 lib/htimer/meson.build                |   7 +
 lib/htimer/rte_htimer.h               |  68 ++
 lib/htimer/rte_htimer_mgr.c           | 547 ++++++++++++++++
 lib/htimer/rte_htimer_mgr.h           | 516 +++++++++++++++
 lib/htimer/rte_htimer_msg.h           |  44 ++
 lib/htimer/rte_htimer_msg_ring.c      |  18 +
 lib/htimer/rte_htimer_msg_ring.h      |  55 ++
 lib/htimer/rte_htw.c                  | 445 +++++++++++++
 lib/htimer/rte_htw.h                  |  49 ++
 lib/htimer/version.map                |  17 +
 lib/meson.build                       |   1 +
 25 files changed, 5689 insertions(+), 2 deletions(-)
 create mode 100644 app/test/test_bitset.c
 create mode 100644 app/test/test_htimer_mgr.c
 create mode 100644 app/test/test_htimer_mgr_perf.c
 create mode 100644 app/test/test_htw.c
 create mode 100644 app/test/test_htw_perf.c
 create mode 100644 app/test/test_timer_htimer_htw_perf.c
 create mode 100644 lib/eal/common/rte_bitset.c
 create mode 100644 lib/eal/include/rte_bitset.h
 create mode 100644 lib/htimer/meson.build
 create mode 100644 lib/htimer/rte_htimer.h
 create mode 100644 lib/htimer/rte_htimer_mgr.c
 create mode 100644 lib/htimer/rte_htimer_mgr.h
 create mode 100644 lib/htimer/rte_htimer_msg.h
 create mode 100644 lib/htimer/rte_htimer_msg_ring.c
 create mode 100644 lib/htimer/rte_htimer_msg_ring.h
 create mode 100644 lib/htimer/rte_htw.c
 create mode 100644 lib/htimer/rte_htw.h
 create mode 100644 lib/htimer/version.map
  

On Wed, 15 Mar 2023 18:03:40 +0100
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> This patchset is an attempt to introduce a high-performance, highly
> scalable timer facility into DPDK.
> 
> More specifically, the goals for the htimer library are:
> 
> * Efficient handling of a handful up to hundreds of thousands of
>   concurrent timers.
> * Make adding and canceling timers low-overhead, constant-time
>   operations.
> * Provide a service functionally equivalent to that of
>   <rte_timer.h>. API/ABI backward compatibility is secondary.

Worthwhile goals, and the problem needs to be addressed.
But this patch never got accepted.

Please fix/improve/extend existing rte_timer instead.
  

> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Thursday, 3 October 2024 20.37
> 
> On Wed, 15 Mar 2023 18:03:40 +0100
> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
> > This patchset is an attempt to introduce a high-performance, highly
> > scalable timer facility into DPDK.
> >
> > More specifically, the goals for the htimer library are:
> >
> > * Efficient handling of a handful up to hundreds of thousands of
> >   concurrent timers.
> > * Make adding and canceling timers low-overhead, constant-time
> >   operations.
> > * Provide a service functionally equivalent to that of
> >   <rte_timer.h>. API/ABI backward compatibility is secondary.
> 
> Worthwhile goals, and the problem needs to be addressed.
> But this patch never got accepted.

I think work on it was put on hold due to the requested changes requiring a significant development effort.
I too look forward to work on this being resumed. ;-)

> 
> Please fix/improve/extend existing rte_timer instead.

The rte_timer API is too "fat" for use in the fast path with millions of timers, e.g. TCP flow timers.

Shoehorning a fast path feature into a slow path API is not going to cut it. I support having a separate htimer library with its own API for high volume, high-performance fast path timers.

When striving for low latency across the internet, timing is everything. Packet pacing is the "new" hot thing in congestion control algorithms, and a simple software implementation would require a timer firing once per packet.
  

On 2024-10-03 23:32, Morten Brørup wrote:
>> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
>> Sent: Thursday, 3 October 2024 20.37
>>
>> On Wed, 15 Mar 2023 18:03:40 +0100
>> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
>>
>>> This patchset is an attempt to introduce a high-performance, highly
>>> scalable timer facility into DPDK.
>>>
>>> More specifically, the goals for the htimer library are:
>>>
>>> * Efficient handling of a handful up to hundreds of thousands of
>>>    concurrent timers.
>>> * Make adding and canceling timers low-overhead, constant-time
>>>    operations.
>>> * Provide a service functionally equivalent to that of
>>>    <rte_timer.h>. API/ABI backward compatibility is secondary.
>>
>> Worthwhile goals, and the problem needs to be addressed.
>> But this patch never got accepted.
> 
> I think work on it was put on hold due to the requested changes requiring a significant development effort.
> I too look forward to work on this being resumed. ;-)
> 
>>
>> Please fix/improve/extend existing rte_timer instead.
> 
> The rte_timer API is too "fat" for use in the fast path with millions of timers, e.g. TCP flow timers.
> 
> Shoehorning a fast path feature into a slow path API is not going to cut it. I support having a separate htimer library with its own API for high volume, high-performance fast path timers.
> 
> When striving for low latency across the internet, timing is everything. Packet pacing is the "new" hot thing in congestion control algorithms, and a simple software implementation would require a timer firing once per packet.
> 

I think DPDK should have two public APIs in the timer area. One is a 
just a bare-bones hierarchical timer wheel API, without callbacks, 
auto-created per-lcore instances, MT safety or any other of the 
<rte_timer.h> bells and whistles. It also doesn't make any assumptions 
about the time source (other it being monotonic) or resolution.

The other is a new variant of <rte_timer.h>, using the core HTW library 
for its implementation (and being public, it may also expose this 
library in its header files, which may be required for efficient 
operation). The new <rte_timer.h> would provide the same kind of 
functionality as the old API, but with some quirks and bugs fixed, plus 
potentially some new functionality added. For example, it would be 
useful to allow non-preemption safe threads to add and remove timers 
(something rte_timer and its spinlocks doesn't allow).

I would consider both "fast path APIs".

In addition, there should probably also be a time source API.

Considering the lead time of relatively small contributions like the 
bitops extensions and the new bitset API (which still aren't in), I 
can't imagine how long time it would take to get in a semi-backward 
compatible rte_timer with a new implementation, plus a new timer wheel 
library, into DPDK.
  

> From: Mattias Rönnblom [mailto:hofors@lysator.liu.se]
> Sent: Sunday, 6 October 2024 15.03
> 
> On 2024-10-03 23:32, Morten Brørup wrote:
> >> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> >> Sent: Thursday, 3 October 2024 20.37
> >>
> >> On Wed, 15 Mar 2023 18:03:40 +0100
> >> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> >>
> >>> This patchset is an attempt to introduce a high-performance, highly
> >>> scalable timer facility into DPDK.
> >>>
> >>> More specifically, the goals for the htimer library are:
> >>>
> >>> * Efficient handling of a handful up to hundreds of thousands of
> >>>    concurrent timers.
> >>> * Make adding and canceling timers low-overhead, constant-time
> >>>    operations.
> >>> * Provide a service functionally equivalent to that of
> >>>    <rte_timer.h>. API/ABI backward compatibility is secondary.
> >>
> >> Worthwhile goals, and the problem needs to be addressed.
> >> But this patch never got accepted.
> >
> > I think work on it was put on hold due to the requested changes
> requiring a significant development effort.
> > I too look forward to work on this being resumed. ;-)
> >
> >>
> >> Please fix/improve/extend existing rte_timer instead.
> >
> > The rte_timer API is too "fat" for use in the fast path with millions
> of timers, e.g. TCP flow timers.
> >
> > Shoehorning a fast path feature into a slow path API is not going to
> cut it. I support having a separate htimer library with its own API for
> high volume, high-performance fast path timers.
> >
> > When striving for low latency across the internet, timing is
> everything. Packet pacing is the "new" hot thing in congestion control
> algorithms, and a simple software implementation would require a timer
> firing once per packet.
> >
> 
> I think DPDK should have two public APIs in the timer area.

Agree.

> One is a
> just a bare-bones hierarchical timer wheel API, without callbacks,
> auto-created per-lcore instances, MT safety or any other of the
> <rte_timer.h> bells and whistles. It also doesn't make any assumptions
> about the time source (other it being monotonic) or resolution.

The <rte_timer.h> library does not - and is never going to - provide sufficient performance for timer intensive applications, such as packet pacing and fast path TCP/QUIC/whatever congestion control. It is too "fat" for this.

We need a new library with a new API for that.
I agree with Mattias' description of the requirements for such a library.

> 
> The other is a new variant of <rte_timer.h>, using the core HTW library
> for its implementation (and being public, it may also expose this
> library in its header files, which may be required for efficient
> operation). The new <rte_timer.h> would provide the same kind of
> functionality as the old API, but with some quirks and bugs fixed, plus
> potentially some new functionality added. For example, it would be
> useful to allow non-preemption safe threads to add and remove timers
> (something rte_timer and its spinlocks doesn't allow).

Agree.

Until that becomes part of DPDK, we will have to stick with what <rte_timer.h> currently offers.

> 
> I would consider both "fast path APIs".
> 
> In addition, there should probably also be a time source API.

A third library, orthogonal to the two other timer libraries.
But I see why you mention it: It could be somewhat related to the design and implementation of the <rte_timer.h> library.
But, let's please forget about a time source API for now.

> 
> Considering the lead time of relatively small contributions like the
> bitops extensions and the new bitset API (which still aren't in), I
> can't imagine how long time it would take to get in a semi-backward
> compatible rte_timer with a new implementation, plus a new timer wheel
> library, into DPDK.

Well said!

Instead of aiming for an unreachable target, let's instead take this approach:
- Provide the new high-performance HTW library as a stand-alone library.
- Postpone improving the <rte_timer.h> library; it can be done any time in the future, if someone cares to do it. And it can use the HTW library or not, whichever is appropriate.

Doing both simultaneously would require a substantial effort, and would cause much backpressure from the community (due to the modified <rte_timer.h> API and implementation).

Although it might be beneficial for the design of the HTW library to consider how an improved <rte_timer.h> would use it, it is not the primary use case of the HTW library, so co-design is not a requirement here.
  

On 2024-10-06 15:43, Morten Brørup wrote:
>> From: Mattias Rönnblom [mailto:hofors@lysator.liu.se]
>> Sent: Sunday, 6 October 2024 15.03
>>
>> On 2024-10-03 23:32, Morten Brørup wrote:
>>>> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
>>>> Sent: Thursday, 3 October 2024 20.37
>>>>
>>>> On Wed, 15 Mar 2023 18:03:40 +0100
>>>> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
>>>>
>>>>> This patchset is an attempt to introduce a high-performance, highly
>>>>> scalable timer facility into DPDK.
>>>>>
>>>>> More specifically, the goals for the htimer library are:
>>>>>
>>>>> * Efficient handling of a handful up to hundreds of thousands of
>>>>>     concurrent timers.
>>>>> * Make adding and canceling timers low-overhead, constant-time
>>>>>     operations.
>>>>> * Provide a service functionally equivalent to that of
>>>>>     <rte_timer.h>. API/ABI backward compatibility is secondary.
>>>>
>>>> Worthwhile goals, and the problem needs to be addressed.
>>>> But this patch never got accepted.
>>>
>>> I think work on it was put on hold due to the requested changes
>> requiring a significant development effort.
>>> I too look forward to work on this being resumed. ;-)
>>>
>>>>
>>>> Please fix/improve/extend existing rte_timer instead.
>>>
>>> The rte_timer API is too "fat" for use in the fast path with millions
>> of timers, e.g. TCP flow timers.
>>>
>>> Shoehorning a fast path feature into a slow path API is not going to
>> cut it. I support having a separate htimer library with its own API for
>> high volume, high-performance fast path timers.
>>>
>>> When striving for low latency across the internet, timing is
>> everything. Packet pacing is the "new" hot thing in congestion control
>> algorithms, and a simple software implementation would require a timer
>> firing once per packet.
>>>
>>
>> I think DPDK should have two public APIs in the timer area.
> 
> Agree.
> 
>> One is a
>> just a bare-bones hierarchical timer wheel API, without callbacks,
>> auto-created per-lcore instances, MT safety or any other of the
>> <rte_timer.h> bells and whistles. It also doesn't make any assumptions
>> about the time source (other it being monotonic) or resolution.
> 
> The <rte_timer.h> library does not - and is never going to - provide sufficient performance for timer intensive applications, such as packet pacing and fast path TCP/QUIC/whatever congestion control. It is too "fat" for this.
> 
> We need a new library with a new API for that.
> I agree with Mattias' description of the requirements for such a library.
> 
>>
>> The other is a new variant of <rte_timer.h>, using the core HTW library
>> for its implementation (and being public, it may also expose this
>> library in its header files, which may be required for efficient
>> operation). The new <rte_timer.h> would provide the same kind of
>> functionality as the old API, but with some quirks and bugs fixed, plus
>> potentially some new functionality added. For example, it would be
>> useful to allow non-preemption safe threads to add and remove timers
>> (something rte_timer and its spinlocks doesn't allow).
> 
> Agree.
> 
> Until that becomes part of DPDK, we will have to stick with what <rte_timer.h> currently offers.
> 
>>
>> I would consider both "fast path APIs".
>>
>> In addition, there should probably also be a time source API.
> 
> A third library, orthogonal to the two other timer libraries.
> But I see why you mention it: It could be somewhat related to the design and implementation of the <rte_timer.h> library.
> But, let's please forget about a time source API for now.
> 
>>
>> Considering the lead time of relatively small contributions like the
>> bitops extensions and the new bitset API (which still aren't in), I
>> can't imagine how long time it would take to get in a semi-backward
>> compatible rte_timer with a new implementation, plus a new timer wheel
>> library, into DPDK.
> 
> Well said!
> 
> Instead of aiming for an unreachable target, let's instead take this approach:
> - Provide the new high-performance HTW library as a stand-alone library.
> - Postpone improving the <rte_timer.h> library; it can be done any time in the future, if someone cares to do it. And it can use the HTW library or not, whichever is appropriate.
> 
> Doing both simultaneously would require a substantial effort, and would cause much backpressure from the community (due to the modified <rte_timer.h> API and implementation).
> 
> Although it might be beneficial for the design of the HTW library to consider how an improved <rte_timer.h> would use it, it is not the primary use case of the HTW library, so co-design is not a requirement here.
> 

Postponing rte_timer improvements would also mean postponing most of the 
benefits of the new timer wheel, in my opinion.

In most scenarios, I think you want to have all application modules 
sharing timer wheel instances, preferably without having to agree on a 
proprietary timer API. Here rte_timer shines.

Also, you want to get the HTW library *exactly* right for the rte_timer 
use case. Making it a public API would make changes to its API painful, 
to address any shortcomings you accidentally designed in. To be on the 
safe side, you would need to have a new rte_timer implementation ready 
upon submitting a HTW library.

That in turn would require a techboard ACK on the necessity of rte_timer 
API tweaks, otherwise all your work may be wasted.