cmcfarlen commented on code in PR #13821: URL: https://github.com/apache/trafficserver/pull/13821#discussion_r4340796645
########## include/tscore/TimerWheel.h: ########## @@ -0,0 +1,246 @@ +/** @file + + A timer wheel: O(1) amortized scheduling and expiry of per-element + deadlines, used to replace O(N)-per-tick scans of open connections. + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#pragma once + +#include <algorithm> +#include <cstdint> +#include <limits> +#include <type_traits> + +#include "tscore/List.h" +#include "tscore/ink_assert.h" +#include "tscore/ink_hrtime.h" + +// Per-element linkage for TimerWheel: the deadline the element was last +// scheduled with, which bucket (slot) it currently lives in (-1 if not in +// the wheel), and which wheel instance owns it. +// +// An element must never be scheduled on more than one wheel at a time. +// Moving an element between wheels (e.g. a NetVConnection migrating between +// per-thread wheels) requires calling cancel() on the old wheel before +// calling schedule() on the new one; owner is asserted in cancel() and +// schedule() to catch a missed hand-off, which would otherwise splice two +// unrelated rings together. +// +// Destroying an element while it is still scheduled is a use-after-free: +// the element's destructor has no way to reach the wheel and unlink it. +// Callers must cancel() before destruction. +struct TimerWheelHook { + ink_hrtime deadline = 0; + int32_t slot = -1; + void const *owner = nullptr; +}; + +// The delegate expire() drives: it reports each visited element's current true +// deadline and fires the ones that are due. +// +// deadline_of() returning 0 means "no timeout", so the element is dropped from +// the wheel. operator() is called once per element whose true deadline has +// passed, after the element has already been removed from the wheel; it may +// call schedule()/cancel() on the wheel, including re-scheduling the very +// element being fired, and the wheel guards against that landing back in the +// bucket currently being drained. +// +// Both are invoked through a non-const F &, so a delegate may carry mutable +// state shared across one pass - a visit count, for instance. +// +// Spelled with std::is_convertible_v rather than std::convertible_to so that +// toolchains whose standard library predates <concepts> can still build it. +template <class F, class C> +concept TimerWheelDelegate = requires(F &f, C *e) { + requires std::is_convertible_v<decltype(f.deadline_of(e)), ink_hrtime>; + f(e); +}; + +// An intrusive ring of DLL buckets, one per second (TICK), used to find +// elements whose deadline has passed without scanning every element. +// +// Not thread safe: each instance is owned and driven by a single thread. +// +// The scheduled deadline may be earlier than an element's eventual true +// deadline (it will simply be rearmed in place, lazily, at expire time) +// but must never be later, or the timeout fires late. +// +// expire() stops early once it has fired @c budget elements or examined +// @c max_visits of them, whichever comes first; either means the caller is +// behind and should call again promptly. The visit cap matters because a +// lazy rearm fires nothing, so a bucket of elements whose deadlines were all +// extended would otherwise be drained in one unbounded pass. The return value +// is the fired count, so a caller that sets a visit cap must count visits +// itself (via deadline_of(), which runs once per element examined) to tell +// whether that cap was the one hit. If the driving thread lags by more than +// N_BUCKETS ticks (e.g. init() was never called, or a long stall), the +// cursor is fast-forwarded rather than replaying every intervening empty +// tick; elements that would have been visited during that lag lose strict +// firing-order fidelity relative to each other, but none fire early or are +// lost. +// N_BUCKETS default: sized from src/tscore/unit_tests/test_TimerWheel.cc's +// "TimerWheel bucket-count sizing sweep" benchmark. At the 30s/120s keepalive +// timeouts (the dominant real case) 256 through 4096 are all already +// steady-state (~1.0 visits per element per timeout period); the difference +// only shows up for timeouts beyond the ring's range (e.g. a multi-hour +// tunnel active timeout), which get revisited every Buckets-1 ticks until +// due. Measured steady state for a 4h timeout: 1024 buckets costs ~14.9 +// revisits per element per period, 4096 costs ~4. The memory difference +// (8 KiB vs 32 KiB per wheel, one wheel per ET_NET thread) is negligible +// either way, so 4096 is strictly better and is the default. +template <class C, int32_t Buckets = 4096, class L = typename C::Link_timer_link> class TimerWheel +{ +public: + static constexpr int32_t N_BUCKETS = Buckets; + static constexpr ink_hrtime TICK = HRTIME_SECOND; + static constexpr int32_t MAX_TICKS_AHEAD = N_BUCKETS - 1; + + static_assert((N_BUCKETS & (N_BUCKETS - 1)) == 0, "N_BUCKETS must be a power of two"); + + void + init(ink_hrtime now) + { + _cursor = now / TICK; + } + + void + schedule(C *e, ink_hrtime deadline) + { + cancel(e); + e->timer_hook.owner = this; + e->timer_hook.deadline = deadline; + // Floor past both the last fully-drained tick and, if we are being + // called reentrantly from inside expire()'s fire callback, past the + // bucket currently being drained - otherwise a reschedule from within + // the callback could land back in that bucket and be popped again in + // the same pass. + _insert(e, std::max(_cursor + 1, _draining_tick + 1)); + } + + void + cancel(C *e) + { + int32_t const slot = e->timer_hook.slot; + + if (slot >= 0) { + ink_assert(e->timer_hook.owner == this); + _buckets[slot].remove(e); + e->timer_hook.slot = -1; + } + } + + bool + is_scheduled(C const *e) const + { + return e->timer_hook.slot >= 0; + } + + template <TimerWheelDelegate<C> F> + int + expire(ink_hrtime now, int budget, F &f, int max_visits = std::numeric_limits<int>::max()) + { + if (budget <= 0 || max_visits <= 0) { + return 0; // nothing to do; wheel state is left untouched + } + + int64_t const now_tick = now / TICK; + + // A cursor lagging by more than a full ring has already had every + // bucket aliased over at least once; fast-forward instead of replaying + // N_BUCKETS empty ticks (this also covers expire() being called before + // init(), where _cursor starts at 0). + if (now_tick - _cursor > N_BUCKETS) { + _cursor = now_tick - N_BUCKETS; + } + + int fired = 0; + int visits = 0; + + while (_cursor < now_tick) { Review Comment: Fixed in 0cc3bf3a73. When `expire()` sees `now` behind the cursor it re-buckets every entry against the new time. That also covers entries scheduled after the step, which had been floored to the old cursor. Your repro is now a unit test, along with pre-step entries and a step larger than the ring. One caveat, from reading the event system rather than testing it: the cop is driven by `schedule_every` on the same `CLOCK_REALTIME` clock, and a periodic event reschedules at `event_time + period`. After a backward step the cop's next run stays at the old time, so it doesn't run at all until the clock catches up. The old sweep was scheduled the same way, so that stall predates this PR and affects every timed event, not just the cop. The wheel fix makes the container correct on its own terms, but the real fix is to move the event system and the net deadlines to a monotonic clock. `ink_get_hrtime()` also serves as the wall clock (log timestamps, cache pin times), so that needs a separate monotonic now-function. I'd like to do that as a follow-up PR rather than grow this one. ########## src/iocore/net/UnixNetVConnection.cc: ########## @@ -1052,7 +1093,8 @@ UnixNetVConnection::mainEvent(int event, Event * /* e ATS_UNUSED */) } *signal_timeout_at = 0; - writer_cont = write.vio.cont; + rearm_timer(); Review Comment: Fixed in 88980c33c5: `mainEvent` now re-arms before the lock-failure return. A real-`UnixNetVConnection` test for this is in 731fbf5dee. -- 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]
