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] [day] [month] [year] [list]

Message-ID: <20150609111502.22465.qmail@ns.horizon.com>
Date:	9 Jun 2015 07:15:02 -0400
From:	"George Spelvin" <linux@...izon.com>
To:	linux@...izon.com, peterz@...radead.org
Cc:	linux-kernel@...r.kernel.org, tglx@...utronix.de,
	viresh.kumar@...aro.org
Subject: Re: [patch 2/7] timer: Remove FIFO guarantee

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.

It definitely gets my mind going.

The issue that's occupying my thoughts right now is this...

Given a "sublist" for a range of future times, the minimum time
can be either a real timeout or a fake one.

If it's a real one, there's a chance you might delete the minimum timeout
on the list.  you have to handle re-sorting after deletion to maintain
a valid minimum time.

You can have a fake list head, which avoids ever re-sorting, but you're
bascially forcing a "tick": taking a timer interrupt at that time even
though nothing needs it.

One possibility that occurs to me would be to have fake heads on the
sublists, but recognize them when they get selected as the "next timeout".
If that happens, deletemin() them now from the remaining heap and find
next *real* timeout.

Basically, just like the current wheel, you'd have to do some scanning
past possibly-empty sublists, but perhaps by using a much more efficient
heap structure, the sublists could be made larger, so not as many heads
would be needed.

Radix sort isn't really O(n); it's O(n log N) with a small constant,
where N is the range of *possible* values (e.g. N = 2^32, so
log N = 32).  But if you want high-resolution timers, N goes
up a lot.
--
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/