Element timeout update ---------------------- - Annotate current time at the beginning of the transaction, use it in _expired() check (=> timeout is not a moving target anymore). - Annotate element timeout refresh in transaction, update timeout from _commit() path not to refresh it. Scenarios --------- #1 Element E1, times out in 1 hour Element E2, times out in 1 second Element E3, timed out (1 second ago, 3 minutes ago, doesn't matter). Userspace batch to kernel: Update Element E1 to time out in 2 hours. Update Element E2 to time out in 1 hour. Update Element E3 to time out in 1 hour. solution => E1 is refreshed E2 is refreshed new E3 is created with 1 hour time out. old E3 is reap by GC. # 2 rbtree possible issue transaction wants to add: 10.1.2.2 - 10.1.2.29 AFAICS, this is now mismerged into: 10.1.2.2 - 10.1.2.30, because walking back to next end element from expired 10.1.2.3 will find 10.1.2.29 as first preceeding end element. solution => (two possible) - From _commit(), skip active elements from GC to find first preceeding end element. - Keep on-demand GC in place for rbtree, but mark expired elements as dead. # 3 resurrecting elements Florian says: "Problem is what to do after reset-inerval support is added, because the newly-marked-dead elements could have a timeout refresh already pending, and I don't see how this can be handled." solution => - Never refresh an element that has expired. - Current time snapshot at the beginning of the transaction is used in _expired(), so things like: element E1 times out in 1 second transaction element E1: refresh to 1 minute ... lots of things in the transaction ... E1 expires. element E1: refresh to 1 hour (NOTE: not expired, because time current snapshot says still is alive) end result in element E1 gets refreshed to 1 hour. # 4 Element E exists and has not timed out yet Userspace generates: Refresh timeout of E to Add E again. As existing E has timed out already, this passes... How to prevent an outcome where E now exists twice? solution => timeout snapshot at the beginning of the transaction ensures E does not expires while handling this transaction. Element E is refreshed once. # 5 Variant: Refresh timeout of E to Delete E Care has to be taken to not add UAF here. ATM deletion (unlink) would take effect before the sets' commit hooks are called, so we refresh timeout of an unlinked element. solution => E (unlinked) gets refreshed then it goes away, but this is not different of deleting an element that is still alive. No UAF can happen.