linux-kernel - Tempering cascade rate when using higher frequency jiffy clocks

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

Message-ID: <4AEB1981.7040907@agilent.com>
Date:	Fri, 30 Oct 2009 09:51:13 -0700
From:	Earl Chew <earl_chew@...lent.com>
To:	linux-kernel@...r.kernel.org
Subject: Tempering cascade rate when using higher frequency jiffy clocks

I've been experimenting a higher frequency jiffy clock (10kHz)
in the spirit of:

http://courses.cs.vt.edu/~cs5204/fall05-gback/papers/p172-etsion.pdf

This is mostly motivated by a wish increase thread delay resolution
by increasing the frequency at which the scheduler gets a chance
to switch threads.

Ingo wrote a much cited description of the timer wheel:

http://lkml.org/lkml/2005/10/19/46

which provides a clear description of the operation of the wheel.

One thing that struck me was the number of wheel buckets (root
plus four more) is independent of the clock frequency.
The kernel allows several clock frequencies to be selected
ranging from 60Hz to 1kHz, but in all cases the same
five buckets are available.

Unless CONFIG_BASE_SMALL is selected, the bucket sizes are
1 x 256 entries, and 4 x 64 entries with 512 entries in total.

This means that at 60Hz, the timer wheel cascade operation must
be performed every 256 / 60 = 4266 ms, while at 1kHz the operation
must be performed every 256 / 1000 = 256 ms. A 10kHz clock
means the operation is performed 256 / 10000 = 25.6 ms.

Does it make sense to trade memory (ie bigger buckets) for
resolution?

In our case, its not that we have more timers, or that the timers
are any longer or shorter necessarily.

Given that, it seems to me that it doesn't make a lot of sense
to cascade buckets any more frequently than before.

So with a 10kHz jiffy clock, I'm think a 1 x 2048 + 4 x 32 = 2176
configuration might be quite attractive. In this configuration
the cascade operation is performed every 2048 / 10000 = 204.8 ms
which is quiet similar to the default configuration with a 1kHz clock.

Are there other considerations?

Earl

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