From 1e75103b1546f1fc732c37c93b85510b4b4f8c81 Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Sun, 3 May 2026 18:25:33 +0200 Subject: lib: Add generic hierarchical timing wheel Introduce a generic 3-level / 256-slot deadline-ordered callback queue (1 ms / 16 ms / 256 ms per-slot resolution at levels 0/1/2). Will replace the existing timerwheel.c. Signed-off-by: Dimitri Staessens Signed-off-by: Sander Vrijders --- include/ouroboros/time.h | 6 ++++ include/ouroboros/tw.h | 77 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 83 insertions(+) create mode 100644 include/ouroboros/tw.h (limited to 'include') diff --git a/include/ouroboros/time.h b/include/ouroboros/time.h index 3d037a3c..a4136e8e 100644 --- a/include/ouroboros/time.h +++ b/include/ouroboros/time.h @@ -46,6 +46,12 @@ #define TS_TO_UINT64(ts) \ ((uint64_t)(ts).tv_sec * BILLION + (uint64_t)(ts).tv_nsec) +#define UINT64_TO_TS(ns, ts) \ + do { \ + (ts)->tv_sec = (time_t)((ns) / BILLION); \ + (ts)->tv_nsec = (long)((ns) % BILLION); \ + } while (0) + #define TIMEVAL_INIT_S(s) {(s), 0} #define TIMEVAL_INIT_MS(ms) {(ms) / 1000, ((ms) % 1000) * 1000} #define TIMEVAL_INIT_US(us) {(us) / MILLION, ((us) % MILLION)} diff --git a/include/ouroboros/tw.h b/include/ouroboros/tw.h new file mode 100644 index 00000000..156f99db --- /dev/null +++ b/include/ouroboros/tw.h @@ -0,0 +1,77 @@ +/* + * Ouroboros - Copyright (C) 2016 - 2026 + * + * Generic deadline-ordered callback queue (timing wheel) + * + * Dimitri Staessens + * Sander Vrijders + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * version 2.1 as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., http://www.fsf.org/about/contact/. + */ + +#ifndef OUROBOROS_TW_H +#define OUROBOROS_TW_H + +#include +#include + +#include +#include +#include + +typedef void (*tw_fire_fn_t)(void * arg); + +struct tw_entry { + struct list_head next; + uint64_t deadline_ns; + tw_fire_fn_t fire; + void * arg; + size_t lvl; +}; + +__BEGIN_DECLS + +int tw_init(void); + +void tw_fini(void); + +void tw_init_entry(struct tw_entry * e); + +/* + * Schedule e to fire at deadline_ns. If e is already posted, + * the previous schedule is cancelled and replaced. + */ +void tw_post(struct tw_entry * e, + uint64_t deadline_ns, + tw_fire_fn_t fire, + void * arg); + +void tw_cancel(struct tw_entry * e); + +/* + * Advance the wheel and fire due callbacks. Callbacks run with the wheel + * unlocked and may call tw_post / tw_cancel on any entry, including the one + * currently firing. Concurrent tw_move from a second thread is a no-op. + */ +void tw_move(void); + +/* + * Write the absolute deadline of the earliest pending entry to *out. + * Empty wheel is signalled by out->tv_nsec == -1. + */ +void tw_next_expiry(struct timespec * out); + +__END_DECLS + +#endif /* OUROBOROS_TW_H */ -- cgit v1.2.3