Message-ID: <20230518084335.5ed41e3f@hermes.local>
Date: Thu, 18 May 2023 08:43:35 -0700
From: Stephen Hemminger <stephen@...workplumber.org>
To: Kui-Feng Lee <sinquersw@...il.com>
Cc: David Ahern <dsahern@...nel.org>, Kui-Feng Lee <thinker.li@...il.com>,
 netdev@...r.kernel.org, ast@...nel.org, martin.lau@...ux.dev,
 kernel-team@...a.com, davem@...emloft.net, edumazet@...gle.com,
 kuba@...nel.org, pabeni@...hat.com, Kui-Feng Lee <kuifeng@...a.com>, Ido
 Schimmel <idosch@...sch.org>
Subject: Re: [RFC PATCH net-next v2 0/2] Mitigate the Issue of Expired
 Routes in Linux IPv6 Routing Tables

On Wed, 17 May 2023 22:40:08 -0700
Kui-Feng Lee <sinquersw@...il.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.

Powered by blists - more mailing lists