On Thu, Oct 07, 2021 at 09:32:43PM +0900, Nobuhiro Iwamatsu wrote: > From: Davidlohr Bueso <dave@xxxxxxxxxxxx> > > 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@xxxxxxx> > Signed-off-by: Thomas Gleixner <tglx@xxxxxxxxxxxxx> > Link: https://lkml.kernel.org/r/20190724152323.bojciei3muvfxalm@linux-r8p5 > Reference: CVE-2021-20317 > Signed-off-by: Nobuhiro Iwamatsu (CIP) <nobuhiro1.iwamatsu@xxxxxxxxxxxxx> > --- Now queued up, thanks. greg k-h
