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 for Android: free password hash cracker in your pocket

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

Date:	Tue, 9 Jun 2015 10:05:56 +0200 (CEST)
From:	Thomas Gleixner <tglx@...utronix.de>
To:	George Spelvin <linux@...izon.com>
cc:	linux-kernel@...r.kernel.org, peterz@...radead.org,
	viresh.kumar@...aro.org
Subject: Re: [patch 2/7] timer: Remove FIFO guarantee

On Tue, 9 Jun 2015, George Spelvin wrote:
> Thomas Gleixner wrote:
> 
> > After thinking more about it, I'm even more sure that any code which
> > relies on the FIFO "guarantee" is broken today.
> 
> Indeed, I am completely convinced.  All I might request is a reassignment
> of blame in the commit message.

Will do. Thanks for spotting it!
 
> Thank you for your comments on my other blue-sky ideas, too.
> 
> I need to look into why we're using wheels, and what the point is.
> How much of an advantage do they have over an efficient priority queue
> like a pairing heap?

The only reason is performance. The wheel has O(1) insertion and
deletion time while heaps and trees usually have O(log(n)).

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.

Thanks,

	tglx




--
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/