Entropy generator to provide significant lag reduction in Android

&#62; This is all fascinating, and I'm not totally dismissing that something is happening here.<p>Qualcomm devices have a hardware random device, which when coupled with the qrngd daemon feeds the kernel entropy pool. In normal operation of Android, I <i>never</i> see this pool actually get low unless running the qrngtest tool, in which case qrngd just fills it right back up.<p>Looking in drivers/char/random.c though, the functions which are called in the interrupt, input, and block device paths have an inner function add_timer_randomness which calls preempt_disable().<p>As a totally non scientific test, I turned all of these functions into no-ops and recompiled. This way, we're ONLY relying on the hardware RNG.<p>There's no change in entropy available because random numbers really just aren't being used all that often.<p>But now, I'm seeing a modest increase in interactivity on the device. Certain things feel smoother, and there is less UI jank. There's no change in frequency scaling or power usage as proposed earlier. qrngtest passes just fine as well.<p>What's going on here? I'm not entirely sure. We're either all crazy, or this is tickling a subtle scheduling bug in the kernel. More investigation is needed. [1]<p>[1] Steve Kondik (CyanogenMod maintainer) <a href="https://code.google.com/p/android/issues/detail?id=42265#c114" rel="nofollow">https://code.google.com/p/android/issues/detail?id=42265#c11...</a>

The Android bug seems to explain that this was a bug in Android &#60;= Gingerbread:<p><a href="https://code.google.com/p/android/issues/detail?id=42265" rel="nofollow">https://code.google.com/p/android/issues/detail?id=42265</a><p>A comment by Elliott Hughes on the bug:<p>"i don't know why you think this is anything to do with dalvik (or libcore). neither touches /dev/random. java.util.Random is just a PRNG seeded from the clock. java.util.SecureRandom uses /dev/urandom.<p>"what version of Android are you reporting this against? i think there was a bug once upon a time. &#60;checks&#62; oh, yeah, &#60;= gingerbread was broken. &#62; gingerbread should be fine."

I am extremely- <i>extremely</i>- dubious of these claims. The app linked runs every second- it is far more likely that this constantly running app is keeping the CPU speed artificially high, probably at a detriment to battery life.<p>There doesn't appear to be any actual benchmark evidence to back up what's going on- just that things appear faster. Sometimes I really feel sorry for people that administrate these bug boards. "I have no evidence to back up what I'm saying other than gut feeling but <i>why won't you listen to us, Google?!?</i>"

Looking at the patch, they just modified rngd to populate /dev/random from /dev/urandom instead of /dev/hwrng.<p>/dev/urandom in turn just uses the kernel's internal entropy pool, which is the same one /dev/random uses, and a PRNG to stretch the entropy when the raw entropy available is depleted.<p>My fear here is that the kernel's internal entropy pool is just constantly being replaced by the PRNG output from /dev/urandom, which is then being used by /dev/urandom to reseed it's PRNG output, causing essentially just a cascade of a PRNG reseeding itself. In turn, /dev/urandom's PRNG was seeded by some initial entropy condition that may have been less than optimal, especially if it was just whatever default was there soon after boot time.<p>If /dev/hwrng was designed to be a primary, or worse <i>the</i>, source of good entropy, then this patch may have eliminated good entropy.<p>Anyone with kernel-level knowledge of the Linux entropy pool care to weigh in? I don't know as much as I wish I did.

It seems like a device that has a radio antenna inside it has no excuse for ever running out of entropy.

Uh What? Did they just replace a cryptographically secure random generator with a more deterministic pseudorandom generator???<p>Granted, blocking on /dev/random is dumb, but this is ridiculous as well... seems like there should be a way to implement a cache in the kernel.

Wow! I've installed this on my old Motorola Defy running CM7 and it is <i>very</i> noticeably faster than before. Going back to home screen is a joy!

If the effect is real, it may just be that since it's precalculating numbers for /dev/urandom (which is possibly slow for the quantity of data needed, particularly on a slow ARM), that means that the PRNG is run ahead-of-time instead of on-demand. A better solution might be to keep a pool of lower-quality bits for /dev/urandom to fall back on when the entropy pool is low.

<a href="http://www.xda-developers.com/android/entropy-seed-generator-not-all-its-hacked-up-to-be/" rel="nofollow">http://www.xda-developers.com/android/entropy-seed-generator...</a> and here is what xda news has to say...

My guess is that the AHA moment happened when he ran this: "watch -n x.xx cat /proc/sys/kernel/random/entropy_avail"<p>Which itself appears to deplete entropy: <a href="http://strugglers.net/~andy/blog/2010/06/06/adventures-in-entropy-part-1/" rel="nofollow">http://strugglers.net/~andy/blog/2010/06/06/adventures-in-en...</a><p>As others have said, there's good evidence that nothing in android touches /dev/random these days.

I have been running this on my toro (Verizon Galaxy Nexus) AOKP rom'd phone. Unscientifically this seems to make a difference to render speed of most everything.

It would he hilarious if this patch broke some spyware that is on some phones and not others and thus increase performance seemingly at random.

This thread and patch are silly, but running out of entropy can be a real performance problem sometimes. I've seen it on embedded Linux systems that I've set up to be headless servers. After turning off lots of device drivers, I noticed that SSH was incredibly slow sometimes. The problem was a lack of entropy, causing reads to /dev/random to block. Like in the article, the quick hack is to redirect /dev/urandom to /dev/random, but that isn't a real fix because of the security implications. The right fix was digging through the available devices and figuring out where entropy could be legitimately captured.

One explanation is that this application wakes up every second which keeps the CPU and GPU from sleeping or lowering frequency, which would reduce the delay introduced by whatever CPU/GPU governors are being used.

This is highly amusing. As the developer on the official AOSP ticket for this said, Java apps get their random bits from RandomBitsSupplier, which, quite clearly, does <i>not</i> read from /dev/urandom, as evidenced by line 72 in <a href="https://android.googlesource.com/platform/libcore/+/master/luni/src/main/java/org/apache/harmony/security/provider/crypto/RandomBitsSupplier.java" rel="nofollow">https://android.googlesource.com/platform/libcore/+/master/l...</a>:<p><pre><code> private static final String DEVICE_NAMES[] = { "/dev/urandom" /*, "/dev/random" */ };</code></pre>

Correct me if I'm wrong, but couldn't it just be that people are seeing improvements because running this every second makes more memory heavy apps in the background leave ram? It seems, just looking at the comments here, that symlinkers have had no good effects, while those installing the app have.

Isn't this proof of a "win" for open source where an independent dev has discovered a significant bug/performance improvement because they can examine the source and recompile their own fix?<p>Would not happen on ios or mobile windows?

Besides the obvious thing of showing a process blocking on a read() from a source of entropy, you could also change the minor number on /dev/random to temporarily make it the same as /dev/urandom. No code needs to be re-compiled or added to the system. Just make everything restart (so it grabs the right /dev entry with the new minor number) and see if it changes.<p>That should tell you if it's actually a lack of entropy, or another process undoing the CPU governor, or something else entirely.

I went ahead, opened a root shell on my Gingerbread phone, and symlinked random to urandom.<p>No noticeable difference whatsoever.<p>I agree that the "speedups" reported by some users are either (1) because they had to reboot their phones, or (2) because rngd prevents the system from going into deeper sleep states which are costlier to recover from. There must be a very small number of users who truly run specific apps that drain the entropy pool, on Gingerbread, and who are helped by this hack.

I've been trying this on UnSense 2.1 and 3.0 for the Thunderbolt. The APK doesn't seem to do much even after enabled and applied on boot. The zip seems to work once flashed in 4ext but then again it could also be the placibo effect. I don't know if it's a all around improvement or if it's just the Windows XP effect. "Show the desktop before windows is finished loading to give the illusion of a faster boot time".

I have no low level experience with android but we have fought this issue on our analytical servers. One culprit was java code (hadoop) that read small amounts of entropy with buffered io essentially filling and discarding a large unneeded buffer every time it needed a small unique id. It caused all sorts of weird lags especially with ssh and was a pain to debug.

Too bad the version in the Play app store also requires a rooted phone:<p><a href="https://play.google.com/store/apps/details?id=com.lcis.seeder" rel="nofollow">https://play.google.com/store/apps/details?id=com.lcis.seede...</a><p>I've done so many Linux installs back in the '90s, that nowadays I appreciate anything that is plugin-and-go. Haven't rooted my phone yet.

One of the option for Android would be to run havege[1] (and haveged[2]) on the device.<p>[1] <a href="http://www.irisa.fr/caps/projects/hipsor/" rel="nofollow">http://www.irisa.fr/caps/projects/hipsor/</a> [2] <a href="http://www.issihosts.com/haveged/" rel="nofollow">http://www.issihosts.com/haveged/</a>

It seems to result in quite a bit of an improvement on my CM7 phone (Motorola Triumph) which would fit with what Elliot Hughes said.

The lack of actual Android developers commenting on the issue (and testing/debugging) is astounding.

:s

Have you heard that entropy isn't what it used to be?

It just occurred to me, if an entire mobile OS and its apps were written in a language like Go, this sort of bug could conceivably never happen, because with a few coding conventions, nothing would ever block.