12 ms·

Entropy generator to provide significant lag reduction in Android

244 points by moeffju 14y ago

deleted 14y ago
[deleted]
mmastrac 14y ago
The Android bug seems to explain that this was a bug in Android <= Gingerbread: https://code.google.com/p/android/issues/detail?id=42265 https://code.google.com/p/android/issues/detail?id=42265 A comment by Elliott Hughes on the bug: "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. "what version of Android are you reporting this against? i think there was a bug once upon a time. <checks> oh, yeah, <= gingerbread was broken. > gingerbread should be fine."
- bjustin 14y ago
  A later comment says it affects versions through JB: Users are reporting this issue up through Jelly Bean / 4.2 - my specific information is against 4.2. I don't believe this issue was solved in gingerbread.
  - AndrewDucker 14y ago
    We're seeing lots of people say "It's faster", but without some actual benchmarks I'm sceptical to say the least.
  - DannyBee 14y ago
    This comment is wrong. As someone later shows, putting inotify waits on /dev/random shows nothing is opening it.
    - mjg59 14y ago
      There are in-kernel consumers of entropy (such as for aslr) that wouldn't show up as /dev/random opens. Reading urandom will deplete the available entropy, but won't block - however, anything relying on actual entropy availability will then block until entropy is repopulated. So if entropy_avail is ever hitting 0, there's some vague plausibility that you could have some slowdowns. But honestly, it doesn't seem likely.
      - DannyBee 14y ago
        I could buy this, but i'd be surprised if it was in the very small percentage of code that is in android but not regular kernel. Past that, android workloads are certainly different, but i'd still think you'd see something outside of android.
    - vidarh 14y ago
      It appears to be wrong that there's anything that reads /dev/random, yes. It is still correct that there are reports of latency reductions across the board. Whether or not they are real or placebo, or if they are real but have other causes (such as reboots) is another matter. But it's too easy to just dismiss this. I tried it on one of my tablets too, and din't reboot, and subjectively it feels substantially snappier - previously the UI would often freeze up long enough for me to get ANR dialogues, and the recommended solution for that tablet model is a full factory reset when it start being persistently slow. That does not mean that I'm sure the effect is real. Nor does it mean that it has to have anything to do with /dev/random.
- m0th87 14y ago
  I was following this last night because it's hilarious. Last I checked, there were three likely causes for the "performance boost" (or some combination thereof): 1) You have to restart the phone to activate the patch. Many users might not have restarted in ages, and this alone would cause a good performance gain. 2) The patch is keeping the CPU from idling by constantly writing to /dev/random. This gives you better performance at the detriment of battery life. 3) Placebo effect.
  - StavrosK 14y ago
    I'm also running this. I haven't noticed much of an improvement. The original poster says he spent hours debugging it, but hasn't posted a single shred of evidence on the process or the result.
    - zackelan 14y ago
      Yeah, users' reports of its effectiveness seem to vary wildly. My suspicion is that it depends heavily on the CPU governor [1] a device uses. Some will see that process running once a second, and keep the CPU at or near max frequency 100% of the time. Others will back down more quickly and you won't see much of a benefit, and still others were probably running at max frequency even before the change, so it wouldn't have much of an effect on them either. [1]: http://androidforums.com/xperia-mini-all-things-root/513426-android-cpu-governors-explained.html http://androidforums.com/xperia-mini-all-things-root/513426-...
      - StavrosK 14y ago
        Maybe. I symlinked /dev/urandom to /dev/random, so I wouldn't have noticed a difference if that were a case, as I didn't.
      - juliano_q 14y ago
        I installed the patch and my CPU frequencies looks like the same, they are not scaling to max all the time. That said it is hard to notice any significant improvement after installing it.
- 89a 14y ago
  Pretty funny it was an issue in any version of the OS at all. Amateur hour
- ajross 14y ago
  I hate to say it, but this kind of bad analysis is just endemic in the Android modding world. There's no technical leadership at the top (the AOSP people are, for the most part, silent except occasionally in bug reports like this), so people just throw whatever hack they want onto forums filled with even-less-clueful folks and things go viral. If you tried this on a "real" Linux project you'd be laughed at. Where's the test showing latency improvement? Hell, there isn't even any identifaction of any code at all that reads from /dev/random (and of course it appears there is none). It seems a little unfair, but frankly I blame Google for this mess. They refuse to run AOSP as a "project", which leaves the AOSP-derived projects a big soup of developers with no clear meritocracy. Some bits (Cyanogenmod) are really quite good. But the stuff on XDA is probably 60% useless junk.
  - angryasian 14y ago
    A google engineer already came out and said this does nothing for ics and up.
    - ajross 14y ago
      Not my point at all. If AOSP worked like, say, the kernel (or KDE, or gcc, or any other big project) this "fix" would have been submitted to and vetted by a functioning group of experts who would have immediately said "Dude, no." and it would have died silently. No such thing exists with AOSP. Google does their development internally. External patch submissions (if acknowledged at all) end up appearing in a usable release only months after the fact. So the poor excited hacker here (who, let's be clear, really didn't do anything wrong other than, well, being wrong) had nowhere to post a fix somewhere where it would be useful to people. So s/he threw it up on XDA with all the other junk, and we're now having this discussion.
      - jrockway 14y ago
        Do "real" open source projects issue releases after every patch? I've recently submitted a small patch to Android and it showed up in the repository immediately. While there is some development done in secret, not everything is. You can git blame and email the developers and they will probably talk to you. (My experience is perhaps different because I have a @google.com email address, but the developers are actually nice people that do value open source, as far as I can tell.)
exabrial 14y ago
Uh What? Did they just replace a cryptographically secure random generator with a more deterministic pseudorandom generator??? 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.
- Freaky 14y ago
  FreeBSD, OS X and iOS have non-blocking /dev/random thanks to http://en.wikipedia.org/wiki/Yarrow_algorithm http://en.wikipedia.org/wiki/Yarrow_algorithm
  - B-Con 14y ago
    Those are more or less the equivalent of /dev/urandom, not /dev/random. On Linux, /dev/random is only raw entropy, /dev/urandom is raw entropy plus PRG stretching when raw entropy runs out.
    - __alexs 14y ago
      /dev/random is not "raw entropy" it goes through the exact same mixing and (SHA-1) compression stages that /dev/urandom does. It just happens to block if there's not much entropy in the pool at the start. Source: http://eprint.iacr.org/2012/251.pdf http://eprint.iacr.org/2012/251.pdf also, the kernel source.
      - B-Con 14y ago
        I understand that, my words were not precise. My point in phrasing it that way was that there is no entropy stretching. (You only get to read (about) as much entropy as has been gathered. You don't have to worry about reading 128 bytes and having them be associated with the previously read 128 bytes, because the pools that generated them are distinct.)
    - Freaky 14y ago
      Well, the main distinction of note would be whether or not they're cryptographically secure, which (despite being much slower) Linux /dev/urandom isn't?
buzzkillr2 14y ago
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.
- Karunamon 14y ago
  I can report identical results on the exact same device running the AOKP 4.2 release that just dropped. There does appear to be significantly less menu lag. I grabbed this yesterday when it was reported over on r/android, and I can see no meaningful impact on battery life. The developer also explicitly stated that no wakelocks are taken.
- DannyBee 14y ago
  That's the problem though. Every report of speed increase is unscientific, and every scientific mechanism shows it can't possibly speed anything up. nothing is opening and using /dev/random continuously, as shown by using inotify to watch it. Things are using /dev/urandom, but /dev/urandom doesn't block anyway. I see a bunch of people showing that this patch makes more entropy available (duh), but without anything using /dev/random, that should not matter. The only thing i can think of is that something in the kernel is asking for random numbers from the blocking interface. Otherwise, it should show up in inotify.
  - BenoitEssiambre 14y ago
    It is also possible that this has nothing to do with blocking but rather with processor resources depletion. The fact that the entropy generating processes are being triggered to run at just the wrong time when the device is most likely busy instead of being triggered when it is idle might cause slowdowns.
  - vidarh 14y ago
    This assertion: > and every scientific mechanism shows it can't possibly speed anything up. Does not follow from this: > nothing is opening and using /dev/random continuously, as shown by using inotify to watch it. The finding that nothing is opening and using /dev/random rules out the explanation the author of the app gave. It does not in any way prove that the app has no effect, even if it might be for totally different reasons. Several people appear to be looking at ways of doing some proper tests to determine if there is a real measurable effect, so we'll presumably find out soon enough.
untog 14y ago
I am extremely- extremely- 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. 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 why won't you listen to us, Google?!?"
- moeffju 14y ago
  I've been running it for a few hours now and didn't notice any significant difference on battery life, but I'll keep watching out for it. I'm now reading through the xda thread to maybe get some insight into how this was "determined"...
- juliano_q 14y ago
  I am running it all day and my CPU frequencies looks the same (I am tracking it on CPU Spy). Battery life is also the same. I didn't noticed any improvement on my Galaxy Nexus with Android 4.2.1.
  - deleted 14y ago
    [deleted]
cocoflunchy 14y ago
Wow! I've installed this on my old Motorola Defy running CM7 and it is very noticeably faster than before. Going back to home screen is a joy!
jedahan 14y ago
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.
B-Con 14y ago
Looking at the patch, they just modified rngd to populate /dev/random from /dev/urandom instead of /dev/hwrng. /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. 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. If /dev/hwrng was designed to be a primary, or worse the, source of good entropy, then this patch may have eliminated good entropy. 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.
- nly2 14y ago
  random and urandom are more or less the same... /dev/random is still a PRNG, using the same algorithms as urandom, it just maintains a record of some desirable degree of estimated entropy and just blocks until it's satisfied. They also use separate entropy buffers, called the blocking and non-blocking pools, respectively. The latter doesn't directly seed itself from the former like you might expect. Both use the SHA1 hash function on their buffers, presumably to prevent any practical leakage of raw data from the pool to the outside world, and both then mix this hash back in to their pool before outputting just half of it to the user.
- mook 14y ago
  According to https://lwn.net/Articles/525459/ https://lwn.net/Articles/525459/ filling the entropy pool with /dev/urandom is a bad idea. Of course, checking my Nexus S, /dev/hwrng just plain doesn't exist; I assume that means the kernel would normally get entropy from other sources at a slower rate.
donretag 14y ago
Too bad the version in the Play app store also requires a rooted phone: https://play.google.com/store/apps/details?id=com.lcis.seeder https://play.google.com/store/apps/details?id=com.lcis.seede... 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.
- brian_cloutier 14y ago
  I greatly appreciate that an app which messes up with chromes ability to generate secure SSL keys requires root to run.
aidenn0 14y ago
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.
neverever 14y ago
http://www.xda-developers.com/android/entropy-seed-generator-not-all-its-hacked-up-to-be/ http://www.xda-developers.com/android/entropy-seed-generator... and here is what xda news has to say...
mistercow 14y ago
It seems like a device that has a radio antenna inside it has no excuse for ever running out of entropy.
- rbanffy 14y ago
  May be a dangerous idea if an attacker gains control of the antenna.
  - mistercow 14y ago
    In order to exercise any control whatsoever over radio noise, the attacker would have to have exceptional control over your surrounding environment. And if you're sampling at a high enough frequency, the attacker isn't going to be able to control the noise unless broadcasting it very near you. And even under those circumstances, there will always be some outside noise that they couldn't eliminate.
- frozenport 14y ago
  Also a motion sensor.
  - mistercow 14y ago
    The capacitive sensor for the touch screen probably also pulls in a lot of noise that could be used.
JohnFromBuffalo 14y ago
Have you heard that entropy isn't what it used to be?
rachelbythebay 14y ago
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. That should tell you if it's actually a lack of entropy, or another process undoing the CPU governor, or something else entirely.
nsp 14y ago
:s
deelowe 14y ago
My guess is that the AHA moment happened when he ran this: "watch -n x.xx cat /proc/sys/kernel/random/entropy_avail" Which itself appears to deplete entropy: http://strugglers.net/~andy/blog/2010/06/06/adventures-in-entropy-part-1/ http://strugglers.net/~andy/blog/2010/06/06/adventures-in-en... As others have said, there's good evidence that nothing in android touches /dev/random these days.
- tytso 14y ago
  The reason why this drains entropy is because when you start a new process (for example "cat" in this case), the kernel passes 16 bytes of randomness at exec time for the benefit of userspace. This allows for fast stack randomization, without the overhead of explicitly opening and reading from /dev/urandom. Due to the internal kernel interface which gets used, this draws from the /dev/random pool, thus decreasing entropy_avail, although it is not a blocking call. There has been some discussions that the userspace randomization should use a CRNG, or perhaps draw from the urandom pool instead.
mrb 14y ago
I went ahead, opened a root shell on my Gingerbread phone, and symlinked random to urandom. No noticeable difference whatsoever. 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.
- BenoitEssiambre 14y ago
  This solution might not help because urandom depletes random entropy anyways when there is some available. It might be that it is not the blocking on urandom calls that is the problem but rather depleting the entropy which triggers processes to generate more of it at just the wrong time when processors are busy rendering things. If the entropy would be pre-generated when the device is idle then there would be more power available for rendering later.
  - mrb 14y ago
    There are no processes that generate entropy on a stock Android. The whole point of the reported hack is to install such a process (rngd).
- sp332 14y ago
  Symlinking random to urandom would have no effect on in-kernel consumers of entropy. Not saying it's any more likely...
lifeguard 14y ago
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.
thefreeman 14y ago
> This is all fascinating, and I'm not totally dismissing that something is happening here. 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 never see this pool actually get low unless running the qrngtest tool, in which case qrngd just fills it right back up. 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(). 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. There's no change in entropy available because random numbers really just aren't being used all that often. 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. 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] [1] Steve Kondik (CyanogenMod maintainer) https://code.google.com/p/android/issues/detail?id=42265#c114 https://code.google.com/p/android/issues/detail?id=42265#c11...
- ibrahima 14y ago
  Ah, this is interesting, since he's probably one of the few people outside of Google with the credentials to actually comment on something like this. It still seems hard to quantify "UI jank" but I'm glad he's looking into it. I had dismissed it as placebo yesterday but if he thinks it's worth looking into then maybe it is.
- judofyr 14y ago
  Nice to see somewhat knowledgable commenting on this issue and actually test things out. It's very easy to say "meh, you haven't done a scientific test so it's probably placebo", but remember that you're being equally un-scientific in such an analyse. When so many users are reporting improvements you (aka. Google) owe them to get to the bottom of it. I also find it surprisingly that nearly no-one posts information about what phone they tested it on. Android ships in so many variants that it wouldn't surprise me if it only works in some of them.
ricardobeat 14y ago
The lack of actual Android developers commenting on the issue (and testing/debugging) is astounding.
- DannyBee 14y ago
  There is at least one actual android engineer who has responded to about 10 comments in the bug report. At this point, the bug report is mostly filled with people saying "i think my phone goes faster, fix this bug", which is non-helpful.
nwhitehead 14y ago
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.
javanix 14y ago
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.
addlepate 14y ago
> You know how sometimes when you hit the home button, it takes 5-10 seconds for the home screen to repopulate? What?! That can't be true, can it?
stcredzero 14y ago
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.
- lukasLansky 14y ago
  Well, no. You still have to wait for computation, you still have to wait for network... and you still have to wait for entropy generators, if you use them. It would possible for a part of application (thread) that do not rely on random numbers to be more responsive. But you do not need OS rewrite for that. And, of course, if you are aware that you are waiting for random numbers to draw a map, you want to do something with that in the first place. :-)
- rogerbinns 14y ago
  That isn't a fix. The problem isn't blocking as such but rather latency. If for example a screen refresh and reading from 10 different network connections were all done in one thread (non-blocking) it could still take some time before the screen refresh code gets to run. 60fps gives you 16ms per frame. Correctly written Android apps (and iOS for that matter) are expected to do work on secondary threads, and keep UI only code in the UI thread. Of course many applications don't quite stick to that. In the Android developer settings you can make it whine about work being done in the UI thread (eg storage/network activity - StrictMode). You can also make it flash a red border whenever the UI thread blocks. In Android 4.0 I used to see a lot of red border from Google's own apps. In 4.2 it happens a lot less often.
  - stcredzero 14y ago
    The problem isn't blocking as such but rather latency. If for example a screen refresh and reading from 10 different network connections were all done in one thread (non-blocking) Yes, but in the sort of environment I just described, if things are done correctly, the thread handling UI updates would not only never block, it would never be waiting on anything high latency. In the Android developer settings you can make it whine about work being done in the UI thread Good to know.
ctbeiser 14y ago
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.
Shadow_Death 14y ago
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".
ck2 14y ago
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? Would not happen on ios or mobile windows?
qxcv 14y ago
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 not read from /dev/urandom, as evidenced by line 72 in https://android.googlesource.com/platform/libcore/+/master/luni/src/main/java/org/apache/harmony/security/provider/crypto/RandomBitsSupplier.java https://android.googlesource.com/platform/libcore/+/master/l...: private static final String DEVICE_NAMES[] = { "/dev/urandom" /*, "/dev/random" */ };
adulau 14y ago
One of the option for Android would be to run havege[1] (and haveged[2]) on the device. [1] http://www.irisa.fr/caps/projects/hipsor/ http://www.irisa.fr/caps/projects/hipsor/ [2] http://www.issihosts.com/haveged/ http://www.issihosts.com/haveged/
micro_cam 14y ago
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.

244 points by moeffju 14y ago

deleted 14y ago

[deleted]

The Android bug seems to explain that this was a bug in Android <= Gingerbread: https://code.google.com/p/android/issues/detail?id=42265 https://code.google.com/p/android/issues/detail?id=42265 A comment by Elliott Hughes on the bug: "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. "what version of Android are you reporting this against? i think there was a bug once upon a time. <checks> oh, yeah, <= gingerbread was broken. > gingerbread should be fine."

bjustin 14y ago
A later comment says it affects versions through JB: Users are reporting this issue up through Jelly Bean / 4.2 - my specific information is against 4.2. I don't believe this issue was solved in gingerbread.
- AndrewDucker 14y ago
  We're seeing lots of people say "It's faster", but without some actual benchmarks I'm sceptical to say the least.
- DannyBee 14y ago
  This comment is wrong. As someone later shows, putting inotify waits on /dev/random shows nothing is opening it.
  - mjg59 14y ago
    There are in-kernel consumers of entropy (such as for aslr) that wouldn't show up as /dev/random opens. Reading urandom will deplete the available entropy, but won't block - however, anything relying on actual entropy availability will then block until entropy is repopulated. So if entropy_avail is ever hitting 0, there's some vague plausibility that you could have some slowdowns. But honestly, it doesn't seem likely.
    - DannyBee 14y ago
      I could buy this, but i'd be surprised if it was in the very small percentage of code that is in android but not regular kernel. Past that, android workloads are certainly different, but i'd still think you'd see something outside of android.
  - vidarh 14y ago
    It appears to be wrong that there's anything that reads /dev/random, yes. It is still correct that there are reports of latency reductions across the board. Whether or not they are real or placebo, or if they are real but have other causes (such as reboots) is another matter. But it's too easy to just dismiss this. I tried it on one of my tablets too, and din't reboot, and subjectively it feels substantially snappier - previously the UI would often freeze up long enough for me to get ANR dialogues, and the recommended solution for that tablet model is a full factory reset when it start being persistently slow. That does not mean that I'm sure the effect is real. Nor does it mean that it has to have anything to do with /dev/random.
m0th87 14y ago
I was following this last night because it's hilarious. Last I checked, there were three likely causes for the "performance boost" (or some combination thereof): 1) You have to restart the phone to activate the patch. Many users might not have restarted in ages, and this alone would cause a good performance gain. 2) The patch is keeping the CPU from idling by constantly writing to /dev/random. This gives you better performance at the detriment of battery life. 3) Placebo effect.
- StavrosK 14y ago
  I'm also running this. I haven't noticed much of an improvement. The original poster says he spent hours debugging it, but hasn't posted a single shred of evidence on the process or the result.
  - zackelan 14y ago
    Yeah, users' reports of its effectiveness seem to vary wildly. My suspicion is that it depends heavily on the CPU governor [1] a device uses. Some will see that process running once a second, and keep the CPU at or near max frequency 100% of the time. Others will back down more quickly and you won't see much of a benefit, and still others were probably running at max frequency even before the change, so it wouldn't have much of an effect on them either. [1]: http://androidforums.com/xperia-mini-all-things-root/513426-android-cpu-governors-explained.html http://androidforums.com/xperia-mini-all-things-root/513426-...
    - StavrosK 14y ago
      Maybe. I symlinked /dev/urandom to /dev/random, so I wouldn't have noticed a difference if that were a case, as I didn't.
    - juliano_q 14y ago
      I installed the patch and my CPU frequencies looks like the same, they are not scaling to max all the time. That said it is hard to notice any significant improvement after installing it.
89a 14y ago
Pretty funny it was an issue in any version of the OS at all. Amateur hour
ajross 14y ago
I hate to say it, but this kind of bad analysis is just endemic in the Android modding world. There's no technical leadership at the top (the AOSP people are, for the most part, silent except occasionally in bug reports like this), so people just throw whatever hack they want onto forums filled with even-less-clueful folks and things go viral. If you tried this on a "real" Linux project you'd be laughed at. Where's the test showing latency improvement? Hell, there isn't even any identifaction of any code at all that reads from /dev/random (and of course it appears there is none). It seems a little unfair, but frankly I blame Google for this mess. They refuse to run AOSP as a "project", which leaves the AOSP-derived projects a big soup of developers with no clear meritocracy. Some bits (Cyanogenmod) are really quite good. But the stuff on XDA is probably 60% useless junk.
- angryasian 14y ago
  A google engineer already came out and said this does nothing for ics and up.
  - ajross 14y ago
    Not my point at all. If AOSP worked like, say, the kernel (or KDE, or gcc, or any other big project) this "fix" would have been submitted to and vetted by a functioning group of experts who would have immediately said "Dude, no." and it would have died silently. No such thing exists with AOSP. Google does their development internally. External patch submissions (if acknowledged at all) end up appearing in a usable release only months after the fact. So the poor excited hacker here (who, let's be clear, really didn't do anything wrong other than, well, being wrong) had nowhere to post a fix somewhere where it would be useful to people. So s/he threw it up on XDA with all the other junk, and we're now having this discussion.
    - jrockway 14y ago
      Do "real" open source projects issue releases after every patch? I've recently submitted a small patch to Android and it showed up in the repository immediately. While there is some development done in secret, not everything is. You can git blame and email the developers and they will probably talk to you. (My experience is perhaps different because I have a @google.com email address, but the developers are actually nice people that do value open source, as far as I can tell.)

exabrial 14y ago

Uh What? Did they just replace a cryptographically secure random generator with a more deterministic pseudorandom generator??? 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.

Freaky 14y ago
FreeBSD, OS X and iOS have non-blocking /dev/random thanks to http://en.wikipedia.org/wiki/Yarrow_algorithm http://en.wikipedia.org/wiki/Yarrow_algorithm
- B-Con 14y ago
  Those are more or less the equivalent of /dev/urandom, not /dev/random. On Linux, /dev/random is only raw entropy, /dev/urandom is raw entropy plus PRG stretching when raw entropy runs out.
  - __alexs 14y ago
    /dev/random is not "raw entropy" it goes through the exact same mixing and (SHA-1) compression stages that /dev/urandom does. It just happens to block if there's not much entropy in the pool at the start. Source: http://eprint.iacr.org/2012/251.pdf http://eprint.iacr.org/2012/251.pdf also, the kernel source.
    - B-Con 14y ago
      I understand that, my words were not precise. My point in phrasing it that way was that there is no entropy stretching. (You only get to read (about) as much entropy as has been gathered. You don't have to worry about reading 128 bytes and having them be associated with the previously read 128 bytes, because the pools that generated them are distinct.)
  - Freaky 14y ago
    Well, the main distinction of note would be whether or not they're cryptographically secure, which (despite being much slower) Linux /dev/urandom isn't?

buzzkillr2 14y ago

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.

Karunamon 14y ago
I can report identical results on the exact same device running the AOKP 4.2 release that just dropped. There does appear to be significantly less menu lag. I grabbed this yesterday when it was reported over on r/android, and I can see no meaningful impact on battery life. The developer also explicitly stated that no wakelocks are taken.
DannyBee 14y ago
That's the problem though. Every report of speed increase is unscientific, and every scientific mechanism shows it can't possibly speed anything up. nothing is opening and using /dev/random continuously, as shown by using inotify to watch it. Things are using /dev/urandom, but /dev/urandom doesn't block anyway. I see a bunch of people showing that this patch makes more entropy available (duh), but without anything using /dev/random, that should not matter. The only thing i can think of is that something in the kernel is asking for random numbers from the blocking interface. Otherwise, it should show up in inotify.
- BenoitEssiambre 14y ago
  It is also possible that this has nothing to do with blocking but rather with processor resources depletion. The fact that the entropy generating processes are being triggered to run at just the wrong time when the device is most likely busy instead of being triggered when it is idle might cause slowdowns.
- vidarh 14y ago
  This assertion: > and every scientific mechanism shows it can't possibly speed anything up. Does not follow from this: > nothing is opening and using /dev/random continuously, as shown by using inotify to watch it. The finding that nothing is opening and using /dev/random rules out the explanation the author of the app gave. It does not in any way prove that the app has no effect, even if it might be for totally different reasons. Several people appear to be looking at ways of doing some proper tests to determine if there is a real measurable effect, so we'll presumably find out soon enough.

untog 14y ago

I am extremely- extremely- 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. 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 why won't you listen to us, Google?!?"

moeffju 14y ago
I've been running it for a few hours now and didn't notice any significant difference on battery life, but I'll keep watching out for it. I'm now reading through the xda thread to maybe get some insight into how this was "determined"...
juliano_q 14y ago
I am running it all day and my CPU frequencies looks the same (I am tracking it on CPU Spy). Battery life is also the same. I didn't noticed any improvement on my Galaxy Nexus with Android 4.2.1.
- deleted 14y ago
  [deleted]

cocoflunchy 14y ago

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

jedahan 14y ago

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.

B-Con 14y ago

Looking at the patch, they just modified rngd to populate /dev/random from /dev/urandom instead of /dev/hwrng. /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. 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. If /dev/hwrng was designed to be a primary, or worse the, source of good entropy, then this patch may have eliminated good entropy. 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.

nly2 14y ago
random and urandom are more or less the same... /dev/random is still a PRNG, using the same algorithms as urandom, it just maintains a record of some desirable degree of estimated entropy and just blocks until it's satisfied. They also use separate entropy buffers, called the blocking and non-blocking pools, respectively. The latter doesn't directly seed itself from the former like you might expect. Both use the SHA1 hash function on their buffers, presumably to prevent any practical leakage of raw data from the pool to the outside world, and both then mix this hash back in to their pool before outputting just half of it to the user.
mook 14y ago
According to https://lwn.net/Articles/525459/ https://lwn.net/Articles/525459/ filling the entropy pool with /dev/urandom is a bad idea. Of course, checking my Nexus S, /dev/hwrng just plain doesn't exist; I assume that means the kernel would normally get entropy from other sources at a slower rate.

donretag 14y ago

Too bad the version in the Play app store also requires a rooted phone: https://play.google.com/store/apps/details?id=com.lcis.seeder https://play.google.com/store/apps/details?id=com.lcis.seede... 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.

brian_cloutier 14y ago
I greatly appreciate that an app which messes up with chromes ability to generate secure SSL keys requires root to run.

aidenn0 14y ago

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.

neverever 14y ago

http://www.xda-developers.com/android/entropy-seed-generator-not-all-its-hacked-up-to-be/ http://www.xda-developers.com/android/entropy-seed-generator... and here is what xda news has to say...

mistercow 14y ago

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

rbanffy 14y ago
May be a dangerous idea if an attacker gains control of the antenna.
- mistercow 14y ago
  In order to exercise any control whatsoever over radio noise, the attacker would have to have exceptional control over your surrounding environment. And if you're sampling at a high enough frequency, the attacker isn't going to be able to control the noise unless broadcasting it very near you. And even under those circumstances, there will always be some outside noise that they couldn't eliminate.
frozenport 14y ago
Also a motion sensor.
- mistercow 14y ago
  The capacitive sensor for the touch screen probably also pulls in a lot of noise that could be used.

JohnFromBuffalo 14y ago

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

rachelbythebay 14y ago

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. That should tell you if it's actually a lack of entropy, or another process undoing the CPU governor, or something else entirely.

nsp 14y ago

deelowe 14y ago

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

tytso 14y ago
The reason why this drains entropy is because when you start a new process (for example "cat" in this case), the kernel passes 16 bytes of randomness at exec time for the benefit of userspace. This allows for fast stack randomization, without the overhead of explicitly opening and reading from /dev/urandom. Due to the internal kernel interface which gets used, this draws from the /dev/random pool, thus decreasing entropy_avail, although it is not a blocking call. There has been some discussions that the userspace randomization should use a CRNG, or perhaps draw from the urandom pool instead.

mrb 14y ago

I went ahead, opened a root shell on my Gingerbread phone, and symlinked random to urandom. No noticeable difference whatsoever. 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.

BenoitEssiambre 14y ago
This solution might not help because urandom depletes random entropy anyways when there is some available. It might be that it is not the blocking on urandom calls that is the problem but rather depleting the entropy which triggers processes to generate more of it at just the wrong time when processors are busy rendering things. If the entropy would be pre-generated when the device is idle then there would be more power available for rendering later.
- mrb 14y ago
  There are no processes that generate entropy on a stock Android. The whole point of the reported hack is to install such a process (rngd).
sp332 14y ago
Symlinking random to urandom would have no effect on in-kernel consumers of entropy. Not saying it's any more likely...

lifeguard 14y ago

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.

thefreeman 14y ago

> This is all fascinating, and I'm not totally dismissing that something is happening here. 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 never see this pool actually get low unless running the qrngtest tool, in which case qrngd just fills it right back up. 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(). 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. There's no change in entropy available because random numbers really just aren't being used all that often. 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. 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] [1] Steve Kondik (CyanogenMod maintainer) https://code.google.com/p/android/issues/detail?id=42265#c114 https://code.google.com/p/android/issues/detail?id=42265#c11...

ibrahima 14y ago
Ah, this is interesting, since he's probably one of the few people outside of Google with the credentials to actually comment on something like this. It still seems hard to quantify "UI jank" but I'm glad he's looking into it. I had dismissed it as placebo yesterday but if he thinks it's worth looking into then maybe it is.
judofyr 14y ago
Nice to see somewhat knowledgable commenting on this issue and actually test things out. It's very easy to say "meh, you haven't done a scientific test so it's probably placebo", but remember that you're being equally un-scientific in such an analyse. When so many users are reporting improvements you (aka. Google) owe them to get to the bottom of it. I also find it surprisingly that nearly no-one posts information about what phone they tested it on. Android ships in so many variants that it wouldn't surprise me if it only works in some of them.

ricardobeat 14y ago

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

DannyBee 14y ago
There is at least one actual android engineer who has responded to about 10 comments in the bug report. At this point, the bug report is mostly filled with people saying "i think my phone goes faster, fix this bug", which is non-helpful.

nwhitehead 14y ago

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.

javanix 14y ago

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.

addlepate 14y ago

> You know how sometimes when you hit the home button, it takes 5-10 seconds for the home screen to repopulate? What?! That can't be true, can it?

stcredzero 14y ago

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.

lukasLansky 14y ago
Well, no. You still have to wait for computation, you still have to wait for network... and you still have to wait for entropy generators, if you use them. It would possible for a part of application (thread) that do not rely on random numbers to be more responsive. But you do not need OS rewrite for that. And, of course, if you are aware that you are waiting for random numbers to draw a map, you want to do something with that in the first place. :-)
rogerbinns 14y ago
That isn't a fix. The problem isn't blocking as such but rather latency. If for example a screen refresh and reading from 10 different network connections were all done in one thread (non-blocking) it could still take some time before the screen refresh code gets to run. 60fps gives you 16ms per frame. Correctly written Android apps (and iOS for that matter) are expected to do work on secondary threads, and keep UI only code in the UI thread. Of course many applications don't quite stick to that. In the Android developer settings you can make it whine about work being done in the UI thread (eg storage/network activity - StrictMode). You can also make it flash a red border whenever the UI thread blocks. In Android 4.0 I used to see a lot of red border from Google's own apps. In 4.2 it happens a lot less often.
- stcredzero 14y ago
  The problem isn't blocking as such but rather latency. If for example a screen refresh and reading from 10 different network connections were all done in one thread (non-blocking) Yes, but in the sort of environment I just described, if things are done correctly, the thread handling UI updates would not only never block, it would never be waiting on anything high latency. In the Android developer settings you can make it whine about work being done in the UI thread Good to know.

ctbeiser 14y ago

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.

Shadow_Death 14y ago

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".

ck2 14y ago

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? Would not happen on ios or mobile windows?

qxcv 14y ago

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 not read from /dev/urandom, as evidenced by line 72 in https://android.googlesource.com/platform/libcore/+/master/luni/src/main/java/org/apache/harmony/security/provider/crypto/RandomBitsSupplier.java https://android.googlesource.com/platform/libcore/+/master/l...: private static final String DEVICE_NAMES[] = { "/dev/urandom" /*, "/dev/random" */ };

adulau 14y ago

One of the option for Android would be to run havege[1] (and haveged[2]) on the device. [1] http://www.irisa.fr/caps/projects/hipsor/ http://www.irisa.fr/caps/projects/hipsor/ [2] http://www.issihosts.com/haveged/ http://www.issihosts.com/haveged/

micro_cam 14y ago

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.