Igalia / snabb

Snabb Switch: Fast open source packet processing
Apache License 2.0
48 stars 5 forks source link

Fix promotion of lib.fibers.timer events from outer to inner wheel #1231

Closed wingo closed 4 years ago

wingo commented 4 years ago

An timer wheel advances by a fixed time-step and contains a fixed number of slots. If, when adding an event, we find that the event is too far in the future, it gets added to an outer wheel, whose time step is the inner wheel's time step, multiplied by the number of slots in the inner wheel.

When the timer runs and an inner wheel's timer wraps around to 0, one timestep's worth of events are moved from the outer wheel to the inner wheel.

This process had a bug. Given that floating-point arithmetic is inexact, it's possible that an event from the outer wheel may have a timestamp that's either slightly before or slightly after the time range covered by the inner wheel. We already protected against the latter, but we were missing a check against the former.

See e.g. https://gist.github.com/lwaftr-igalia/e9479e1d9ff04f008b86d040ed9c403e for a failure log containing this error:

(3) Lua upvalue 'tick_outer' at file 'lib/fibers/timer.lua:134'
    Local variables:
           inner = table: 0x41b90250  {slots:table: 0x40a2a678, period:0.001, rate:1000, cur:0, now:17883918.881778 (more...)}
           outer = table: 0x40826950  {slots:table: 0x40826ae0, period:0.256, rate:3.90625, cur:52, now:17883918.881778 (more...)}
           head = table: 0x41b8f7f0  {prev:table: 0x41b8f7f0, next:table: 0x41b8f7f0, time:false, obj:false}
           ent = table: 0x41448d68  {prev:table: 0x41b8f7f0, next:table: 0x41b8f7f0, time:17883918.881778, obj:table: 0x41448d08 (more...)}
           idx = number: -1

Note that idx here is -1, indicating a value just before the time range for the inner wheel.

wingo commented 4 years ago

Merging as reviewed by @eugeneia