lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
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