linux-kernel - Re: [patch 2/7] timer: Remove FIFO guarantee

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 9 Jun 2015 12:24:53 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	George Spelvin <linux@...izon.com>
Cc:	tglx@...utronix.de, linux-kernel@...r.kernel.org,
	viresh.kumar@...aro.org
Subject: Re: [patch 2/7] timer: Remove FIFO guarantee

On Tue, Jun 09, 2015 at 05:43:18AM -0400, George Spelvin wrote:
> Thomas Gleixner wrote:
> > The only reason is performance. The wheel has O(1) insertion and
> > deletion time while heaps and trees usually have O(log(n)).
> 
> Pairing heaps also have O(1) insertion, and rescheduling can
> be quite lightweight.
> 
> The issue I was worried about is the need for an additional pointer
> per timer (left, right, parent) and the associated cache line touch
> when modifying the heap.
> 
> > Timer wheel timers are usually timeouts and 99% of them are canceled
> > before expiry. Networking is probably the heaviest use case followed
> > by disk I/O.
> 
> And that rewards very lazy structures, that postpone work in the
> hope it will become unnecessary.  But a wheel has real problems with
> non-tick-based timers, which as you note covers both hrtimers and NOHZ.
> 
> Now, two things to note about pairing heaps (and many related heap
> structures like Fibonacci heaps, but pairing heaps have a particularly
> good constant factor in practice) are:
> 
> 1) It is O(1) to "meld" two heaps into one.
> 2) The above is O(1) because it's literally "stick it on a linked list";
>    the left child pointers are NULL until the minimum (which is kept
>    at the head/root) is deleted and a new minimum has to be found.
> 
> Combining these two facts, we could do something wheel-like: divide
> the future into a number of heaps, link future events into the correct
> subheap, and meld the subheaps into the main heap when necessary.
> 
> Hopefully, by the time it's necessary, the subheap would have been
> thinned out by timers being ccanceled.

Right, so while pairing (and fibonacci) heaps have O(log n) deletion, if
you can delay heapification you can equally delay that extra cost.

But as you say, the heapification is a O(n) hit, which is not too
different from our current 'problem'.

But yes, interesting problem space this.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/