Re: [RFC PATCH net-next v2 0/2] Mitigate the Issue of Expired Routes in Linux IPv6 Routing Tables

[Kui-Feng Lee <sinquersw@gmail.com>]

On 5/18/23 08:43, Stephen Hemminger wrote:
> On Wed, 17 May 2023 22:40:08 -0700
> Kui-Feng Lee <sinquersw@gmail.com> wrote:
> 
>>>> Solution
>>>> ========
>>>>
>>>> The cause of the issue is keeping the routing table locked during the
>>>> traversal of large tries. To address this, the patchset eliminates
>>>> garbage collection that does the tries traversal and introduces
>>>> individual timers for each route that eventually expires.  Walking
>>>> trials are no longer necessary with the timers. Additionally, the time
>>>> required to handle a timer is consistent.
>>>
>>> And then for the number of routes mentioned above what does that mean
>>> for having a timer per route? If this is 10's or 100's of 1000s of
>>> expired routes what does that mean for the timer subsystem dealing with
>>> that number of entries on top of other timers and the impact on the
>>> timer softirq? ie., are you just moving the problem around.
>>
>> Yes, each expired route has a timer.  But, not all routes have expire
>> times.  The timer subsystem will handle every single one. Let me
>> address the timer subsystem later.
>>
>>>
>>> did you consider other solutions? e.g., if it is the notifier, then
>>> perhaps the entries can be deleted from the fib and then put into a list
>>> for cleanup in a worker thread.
>>
>> Yes, I considered to keep a separated list of routes that is expiring,
>> just like what neighbor tables do.  However, we need to sort them in the
>> order of expire times.  Other solutions can be a RB-tree or priority
>> queues. However, later, I went to the timers solution suggested by
>> Martin Lau.
>>
>> If I read it correctly, the timer subsystem handles each
>> timer with a constant time.  It puts timers into buckets and levels.
>> Every level means different granularity.  For example, it has
>> granularity of 1ms, 8ms (level 0), 64ms, 512ms, ... up to 4 hours
>> (level 8) for 1000Hz.  Each level (granularity) has 64 buckets.
>> Every bucket represent a time slot. That means level 0 holds
>> timers that is expiring in 0ms~63ms in its 64 buckets, level 1 holds
>> timers that is expiring in 64ms~511ms, ... so on.  What the timer
>> subsystem does is to emit every timers in the corresponding current
>> buckets of every level.  In other word, it checks the current bucket
>> from level 0 ~ level 8, and emit timers if there is any timer
>> in the buckets.
>>
>> In contrast, the current GC has to walk every tree even only one route
>> expired.  Timers is far better. It emits every timer in the
>> buckets associated with current time, no search needed.  The current GC
>> is triggered by a timer as well.  So, it should reduce the computation
>> of the timer softirq.
>>
>> However, just like what I mentioned earlier, the drawback of timers are
>> its granularity can vary.  The longer expiration time means more coarse-
>> grained.  But, it probably is not a big issue.
> 
> If Linux is used on backbone router it can easily have 3 million routes
> to deal with. That won't make timer subsystem happy.

I will run experiments to get numbers to see how the compact
actually is.