On Thu, Oct 07, 2021 at 09:32:43PM +0900, Nobuhiro Iwamatsu wrote:
From: Davidlohr Bueso dave@stgolabs.net
commit 511885d7061eda3eb1faf3f57dcc936ff75863f1 upstream.
Simplify the timerqueue code by using cached rbtrees and rely on the tree leftmost node semantics to get the timer with earliest expiration time. This is a drop in conversion, and therefore semantics remain untouched.
The runtime overhead of cached rbtrees is be pretty much the same as the current head->next method, noting that when removing the leftmost node, a common operation for the timerqueue, the rb_next(leftmost) is O(1) as well, so the next timer will either be the right node or its parent. Therefore no extra pointer chasing. Finally, the size of the struct timerqueue_head remains the same.
Passes several hours of rcutorture.
Signed-off-by: Davidlohr Bueso dbueso@suse.de Signed-off-by: Thomas Gleixner tglx@linutronix.de Link: https://lkml.kernel.org/r/20190724152323.bojciei3muvfxalm@linux-r8p5 Reference: CVE-2021-20317 Signed-off-by: Nobuhiro Iwamatsu (CIP) nobuhiro1.iwamatsu@toshiba.co.jp
Now queued up, thanks.
greg k-h