1 Why is Chrome spawning a new browser engine?
The WebKit maintainers wouldn’t let us attack Apple directly, by changing WebKit in ways that would make it perform badly on OS X and iOS.
Because they share a rendering engine, developer effort to ensure Chrome compatibility currently benefits Apple platforms for free. To prevent this, we must make Chrome and WebKit behave differently.
1.1 What sorts of things should I expect from Chrome?
Nothing yet. This is a political move, not a technical one.
However, while the Chrome user interface will not change in any significant way, we will be silently overwriting all existing installations of Chrome with our new rendering engine without your knowledge or consent.
…continues gloriously at Chrome Blink FAQ.
What worked, ultimately, was finding operations that have instruction costs O(n**2) in the number of commits and squashing them. At this point a shout-out goes to Julien “FrnchFrgg” Rivaud, a very capable hacker trying to use reposurgeon for some work on the Blender repository. He got interested in the speed problem (the Blender repo is also quite large) and was substantially helpful with both patches and advice. Working together, we memoized some expensive operations and eliminated others, often by incrementally computing reverse-lookup pointers when linking objects together in order to avoid having to traverse the entire repository later on.
Even just finding all the O(n**2) operations isn’t necessarily easy in a language as terse and high-level as Python; they can hide in very innocuous-looking code and method calls. The biggest bad boy in this case turned out to be child-node computation. Fast import streams express “is a child of” directly; for obvious reasons, a repository analysis often has to look at all the children of a given parent. This operation blows up quite badly on very large repositories even if you memoize it; the only way to make it fast is to precompute all the reverse lookups and update them when you update the forward ones.
Another time sink (the last one to get solved) was identifing all tags and resets attached to a particular commit. The brute-force method (look through all tags for any with a from member matching the commit’s mark) is expensive mainly because to look through all tags you have to look through all the events in the stream – and that’s expensive when there are 56K of them. Again, the solution was to give each commit a list of back-pointers to the tags that reference it and make sure all the mutation operations update it properly.
It all came good in the end. In the last benchmarking run before I shipped 2.29 it processed 56424 commits in 303 seconds. That’s 186 commits per second, 11160 per minute. That’s good enough that I plan to lay off serious speed-tuning efforts; the gain probably wouldn’t be worth the increased code complexity.
Due to a misplaced parenthesis, if insufficient GOOD bits were available to satisfy a request, the keying/rekeying code requested either 32 or 64 ANY bits, rather than the balance of bits required to key the stream generator.
The result of this bug is that even after the minimum entropy threshold was reached, the generators for in-kernel and userspace consumers could in the worst case be keyed, or re-keyed, with as few as 32 bits (on 32 bit platforms) or 64 bits (on 64 bit platforms) of data, plus a 32-bit cycle counter value, plus the name of the generator (an LWP ID for userspace, a fixed string for kernel consumers), plus stack noise for the remainder.
Systems which never experience an “insufficient entropy” condition (for example, systems with hardware random number generators supported by NetBSD) are not impacted by this bug.
All cryptographic keys generated on NetBSD 6 or NetBSD-current (prior to 2013-01-27) systems should be regenerated, unless it is certain that the system in question cannot have suffered a low-entropy condition when the keys were generated.
Back in June 2011 I joined Surevine – a company of great people whom I cannot commend highly enough* as a excellent working environment, as promoters of open source, and of people who care about software and security and about doing both right. I am pleased to have helped cause some beneficial change at Surevine – including, but not limited to, security awareness, operations architecture and obtaining ISO27001 certification.
All this said: I’ve been offered a really exciting prospect which I’ve decided to pursue.
Thus: I shall shortly be joining Facebook as a software engineer and will be working out of the London/Covent Garden office.
What happens after that will be interesting in a whole variety of ways. 🙂
* If you’re a UK-based security geek or Java developer then go look Surevine up. Send them a resume. Say that “Alec’s blog sent you”; I get no money for this, it’s just a really great company that deserves good people.