Entropy generator to provide significant lag reduction in Android
forum.xda-developers.com
forum.xda-developers.com
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#c11...
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.
No, dismissing unblinded observations of phenomena the perceptions of which are notoriously suggestible (like UI responsiveness) is not "equally un-scientific" as making unblinded observations of phenomena the perceptions of which are notoriously suggestible.
Pointing out that such observations is unreliable is, in fact, a simple application of science. Grandstanding tu quoque arguments are not.
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."
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.
Only a few people inside Google are allowed to see it. Their colleagues aren't allowed to sit in the same cafeteria as the Android developers, much less see the source code, until it's already done.
If it was actually Open Source, XDA developers would actually have real, original development, and features like lock screen widgets, officially added in JB 4.2 in 2012, would have been completed by the community in 2009.
Only old, already released versions of Android are Open Source. This makes it useless for real developers - who would want to fix something that might already be a non-issue as of six months ago?
As a result, the only 'community development' in Android is people who know how to tweak settings files and make ROMs with particular apps and settings built in.
In order for patches to be relevant, they should be on the HEAD of the project where most developers are working, not the old, released, finished, version.
The existence of Cyanogenmod and Amazon Kindle Fire prove that you are over-stating the case.
The kindle fire is a fork of Android 2.x.
Why would new phones be 'spoiled' if their source code was released?
Do you have any figures to back this claim? Somewhere above or below a guy said he did send a patch.
> less developers and less features than it would if it were truly open
Very unlikely. Were it fully open (say, the Linux-way), it would not be pushed forward so steadily by Google, it would not have so many high-end apps (many written by Google), it would not have such a big piece of the market, it would not be the solution of choice for manufacturers, etc.
I also wish Android to be more open, and I hope we will see soon emerge a "Landroid" that will be to Android what Linux is to Unix, and probably Cyanogenmod is paving its path, but this is no reason to spit in the soup: Android is a giant step forward and without it we would be all sandwiched in a MS-Apple cross-fight.
> Why would new phones be 'spoiled' if their source code was released?
Suppose the most recent feature developed by Google on Android reveals that their next phone will have two-faced screens, wouldn't you think Google might prefer to decide when and how this new phone will be announced? As a result, we have a slightly lagging opening of the source code. It is sad, but better than nothing.
On my own side, I can say this: I actually have code right now in Android; however, there is probably no chance that I will ever bother submitting another patch again.
What, in my experience, happens is that you submit a patch, and one person looks at it, thinks it is great, and gives it a +1. However, he can't merge it until someone agrees. Only, there isn't enough involvement on Google's end to get two people to agree. It isn't like someone else disagrees: you just don't get two peoples' opinions on the patch.
https://android-review.googlesource.com/#/c/7288/
That is a patch that I submitted in January of 2009. Apparently, in May of 2010, a second person agreed, and the patch was merged. Yes: 16 months later. (There were three other patches I submitted in November of 2008 that were merged in August of 2009, but that was a "much more reasonable" 9 month gap, so... yeah ;P.)
https://android-review.googlesource.com/#/c/7290/
With this patch, that same second guy had "disagreed"; well, he wanted justification for why I wanted the feature. Two months later, the patch died, as I had long moved on. Now, had that question come, I dunno, a year earlier? (So, a mere 4 months after I submitted it), maybe I'd have remembered whether or not it was required for my use case. ;P
https://android-review.googlesource.com/#/c/14339/
This patch wasn't even mine, but somehow I ended up in the system as "maybe he'll be second reviewer this time!" (and no, I have no clue how or why or what the rules are).
Only, this was the most depressing of all: when I reviewed the patch, I determined that the original code actually had a buffer overflow in it... this was an important patch.
The patch, of course, had already been in the system for a while: it was submitted in April, but it wasn't until nearly two months later that I got poked to review it. But, I don't think I actually could be "second reviewer", so there just ended up being a bunch of +1s from random people until yet another month went by; it finally got merged.
Another half of the problem is the same thing people here are complaining about: that AOSP is really just "an occasionally merged external branch" to "the real code".
The result is that when you are working on a patch, you actually can't know whether you are working on code that even exists anymore in the upstream branch. Maybe the code exists, but doesn't have the bug anymore; or maybe it does, but the implementation is sufficiently different that your code no longer merges against it.
What this means is that even if someone reviewed your patch instantly, it already might not apply anymore, and if it doesn't it isn't like they can even ask you to fix it.
It used to be that Google was promising that they'd merge the internal and AOSP branches, so they'd be working in public on nearly the same codebase (closer to Chromium). However, that promise at some point dissolved so greatly that they simply closed the source for something like eight months, not even attempting to merge it.
Why? As far as I can tell (and I've stared at this a lot), it was to hobble Amazon slightly, who had just announced that they were working on a tablet based on Android. Not just "an Android tablet", but "we are going to use all of that valuable work you did, but not pay you anything for it because we don't need your first-party Google apps".
The code didn't become open again until Amazon started shipping their tablets to users. At which point, the story with the open source codebase changed a lot. Now, the promise is more "we will make certain our preferred partners get access to the codebase quickly", but otherwise the code doesn't get dropped until the product ships.
Due to this, when we received our Android 4.0 test devices at Google I/O, and I soon there-after found a bug in libdl (broken shared object initializers), I was largely screwed. I seriously wasted a week (successfully!) figuring out what caused the bug and reverse-engineering what they changed using a disassembler, so I could file a bug.
When I managed to get the bug filed to the mailing list was about when the code finally dropped, so maybe that week was just wasted, but maybe I needed that time to find it anyway. Of course, Android 4.0 shipped with that bug. The issue was fixed in Android 4.0.1, and "luckily" almost no one upgraded to Android 4.0 until Android 4.0.2, but... frowny. :(
It isn't as if there isn't a model for community contributed patches for Google products: The Chromium projects take community patches and have a code review workflow for them. I don't know how effective this is, or how many end up in Chrome and ChromeOS. But it's not as if opening up more is not do-able.
I agree in general that if AOSP was an actual open source project things would be better but I don't think XDA would be any different. It's been full of end users for years now and most of them are easily fooled by stuff like this. CyanogenMod is developed in the open and they do have quite a few contributors, but it's not terribly ground breaking (although some of their features do get reimplemented in AOSP eventually). The fact is that the Android project is really a gigantic codebase and it takes a lot of time to get started (and even on a really fast machine, 20-40 minutes to build), and a lot of the work CyanogenMod developers do is porting to hardware that's unsupported by AOSP, not feature development.
Well, the Android cafe isn't advertised to Googlers, but any Googler can dine there.
Not really- the Ubuntu forums are an identical cesspool. There are just too many users for developers to interact with, so they hide in forums like IRC and mailing lists that drive off most of their non-technical users.
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.
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.)
Maybe. Or maybe it would have been like all those "Turn off your Windows paging file" for XP and Vista websites.
Or all those "RAM Booster" softwares.
Users get sucked into a bunch of hokum, and having a clueful person tell them it's nonsense often does nothing to stop the nonsense.
But most people hearing this "Windows performance enhancing tweak" are not that knowledgable about their OS.
Compare the MS article here (http://support.microsoft.com/kb/2160852) with, for example, this article with minimal details (http://www.howtogeek.com/howto/windows-vista/understanding-w...).
My eventual duct tape was running cacheset once a minute to cut cache down to .5GB. Thankfully once I upgraded to windows 7 it stopped being a problem.
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.
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-...
From what I can tell, this is the technological-age incarnation of superstition.
I can say, though, that I've not felt any difference on the devices would benefit from it in the performance department, however.
Good points, though.
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.
As someone later shows, putting inotify waits on /dev/random shows nothing is opening it.
Past that, android workloads are certainly different, but i'd still think you'd see something outside of android.
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.
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?!?"
/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.
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.
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.
Source: http://eprint.iacr.org/2012/251.pdf also, the kernel source.
On the contrary, there have been real security problems seen when apps unpredictably get nothing back from the RNG. Exhaustion can also be provoked by a remote attacker.
Good quality PRNGs are not that new. But for good reasons, cryptographically sensitive applications do not want to be in a position of relying purely on PRNG stretched output. Reading from urandom, you have no idea how much entropy was used to seed your output. Was it 5 bytes from last week, or 4K from 5 seconds ago? You don't know.
The PRNG may be good enough to keep successive reads from being statistically correlated and such, but that is only one concern. Crypto, random number generation, and the practical implementations thereof is much more complicated than just the quality of the primitives. Sometimes you want to know for sure how much entropy is devoted to your read. In such a case, you use random.
What I'm saying is: if you are worried about the quality of your PRNG or the size of its pool or the secrecy of its content then you ought to choose a PRNG you can be confident in. Saying "I don't trust my PRNGs output for more than a short time" is equivalent to saying you believe your PRNG is defective (or you don't believe in one way functions in general).
Was it 5 bytes from last week, or 4K from 5 seconds ago? You don't know.
If your kernel takes a week to scavange 5 bytes unknown to an attacker, it's defective. You only need 100-200 bits, and the first seeding is the important one. This amount shouldn't take more than a few seconds to accumulate on all but the most quiet deterministic embedded systems.
Sometimes you want to know for sure how much entropy is devoted to your read.
Entropy is what the attacker doesn't know. The kernel can only try to estimate it based on wild-ass guesses about the properties of the attacker. Decrementing this estimate as RNG numbers are handed out is unjustifiable.
you seem to be saying that apps generally should need /dev/random only rarely. which seems sensible, but is also what the post one up suggested.
in short you seem to be in confused and annoyed agreement.
[vaguely related interesting post on urandom quality - http://security.stackexchange.com/questions/3936/is-a-rand-f...]
+1 on the linked post.
Which itself appears to deplete entropy: 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.
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.
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.
> 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.
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.
private static final String DEVICE_NAMES[] = { "/dev/urandom" /*, "/dev/random" */ };Would not happen on ios or mobile windows?
That should tell you if it's actually a lack of entropy, or another process undoing the CPU governor, or something else entirely.
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.
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.
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.
[1] http://www.irisa.fr/caps/projects/hipsor/ [2] http://www.issihosts.com/haveged/
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.
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.
That is already the case today for well written apps on Android (Java) and Objective C (iOS). Rewriting in Go wouldn't be a solution. It is how the execution is structured in any language.
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. :-)