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: <8331928c-a525-ff99-d06e-21e769982770@gmail.com> Date: Thu, 18 May 2023 09:59:45 -0700 From: Kui-Feng Lee <sinquersw@...il.com> To: Stephen Hemminger <stephen@...workplumber.org> 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 5/18/23 08:43, Stephen Hemminger wrote: > 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. I will run experiments to get numbers to see how the compact actually is.
Powered by blists - more mailing lists