rsc

One small correction: we were doing bisect over compiler optimizations a decade ago, but bisect over call trees only happened in the past year or so.

For the hash table case, deciding the function per-table as you suggest is probably good enough. In a large program there are going to be tons of hash tables, and if bisect gets you to "it's this specific hash table allocated by this call stack that matters", that's a huge win.

The timer change is much like the hash table one, in that we toggle the "timer kind" at creation time, but it's only later operations that actually change behavior. Still, identifying the specific timer and call stack that created it turned out to be good enough in all cases.

If we add it to the standard library it will be for runtime uses (identify the call stack for which swapping in the new implementation or behavior breaks the test). It is pretty simple. You call 'godebug.New' in a global init to get a lookup keyed to a particular setting, and then you look at that setting at runtime. For example take a look at https://go.dev/src/crypto/x509/x509.go#L881 and look at the uses of x509sha1 a few lines later.

You just call x509sha1.Value() and make a decision about old or new behavior based on that. Bisect can then toggle that result based on the hash of the call stack to narrow down the exact path that leads to the critical decision.

You can ignore the IncNonDefault call a few lines later. That's about providing monitoring for whether any non-default (old) behaviors are being executed in a program, so that people can hook it up to something like prometheus and see whether they would be affected by changing to "always default behavior".

Anyone working on libraries that are used by large programs can use them, like in the sort and timer cases described toward the end of the paper. When you work on libraries used by other larger programs you inevitably break them accidentally. This technique pinpoints the exact context of the breakage.

Yes, I believe LLVM has a flag for "run only the first N optimization passes" that gets used with binary search this way.

A global optimization fuel that worked at finer granularity would be even more precise but you'd have to have the compiler run single-threaded to make sure the numbering always matches. At least in the Go compiler, we compile different functions in different threads, so that fouls up any global numbering.

Indeed. Something like this is what I intend to do when I get some time.

What you are describing sounds like comparing traces of two supposed-to-be-identical programs to see where they first diverge. That's not what this is describing. There is no trace at all, nor any decision about what to trace or what not to trace.

There is only a decision about whether to use the old or new implementation based on the hash of the call stack at that moment. Then you binary search on hash values to identify the exact call stack hash for which the new implementation causes a problem. Then you run the program once more with the instructions "print the stack with this hash".

Thanks for that link. I've changed the link beneath the Cinder mention to that page instead of the GitHub page.

Idempotent is a somewhat confusing word choice here. "Verifiable builds" seems more a accurate description of what they want. (See also https://go.dev/blog/rebuild.)

I can't speak to what has happened with Buildifier, but in general you are right. It has to be a hard rule that if you change the format rules, you have to reformat everything to match.

If that means it's too hard to change the format rules, then don't change the format rules. And if you don't reformat, then it has to be a clear rule known to everyone (or written down somewhere you can point to) that incidental formatting changes are acceptable and not something you are allowed to push back on.

I can speak to Go and gofmt, and there we are VERY reluctant to change formatting rules. It does happen for the odd corner case once in a while, but nothing that would cause "changes far beyond my 2-line fix".

Not git, but yes, it did mess up the blame lines. Luckily most people don't care about the attribution on BUILD files. But I did get the occasional email for years afterward about "hey looks like you added this build target, can you explain it?" or just an automated tool deciding I was the last person who edited the file so I was a good reviewer for a future change. Those pings were a fun tour of directories I'd never heard of (but did edit). Been a few years since I got one of those.

This One Trick Will Add 80 Minutes To Your Day

No, because Go compiles to binaries, like C/C++ but unlike Java or Python. Only the buildifier binary needed to be installed on everyone's machine.

(I think Go was already installed on every Google developer machine at that point anyway.)

(Rosie is a code janitor program at Google that takes a change that affects files all across the tree and automatically cuts it into individual changes that can be mailed out to the individual teams as CLs/PRs for their approval.)

Rosie existed but very much wanted to break up the CL into independent per-directory CLs, and since I was editing one file in every directory in the entire tree, that would have been 200,000 independent CLs. I broke the list up by top-level directory or sub-directory and hit 100+ directories at a time.

Rosie also really wants to run each affected directory's tests, and I did not, because at scale flaky tests and such would be a significant source of false positives. The bit-for-bit check on the internal parsed representation of the meaning of the BUILD file proved that the changes were no-ops. That was better than any tests of the code in the directory.

I was already automating everything else, including deciding which files to change, reverting edits in files that were concurrently modified (they got swept into the next attempt), and the testing. Running a shell command to actually make the CLs was not difficult. And it generating the approval script trivial too.

Rosie is great but it wasn't the right tool for this job.

If you're using Go with Bazel, gazelle is available outside Google: https://github.com/bazelbuild/bazel-gazelle

Enabling tools like these was exactly the point of the enforced formatting. It worked extremely well.

At that point you could even use different languages. Maybe you like programs that look like Lisp and I don't. There was a project at Microsoft Research in the late 1990s/early 2000s that did exactly this - storing ASTs in source control instead of code - but the name escapes me at the moment.

My notes say it was 193k at the start. The final dashboard when we stopped said "216,626 / 216,890 = 99.8%; 264 to go".

The other correction I would make is that this post does not mention Nilton Volpato, who had written an earlier Buildifier and graciously accepted replacing his implementation with a new one and then taking over ownership for that new implementation as well. (Eventually ownership moved to Laurent's team.)

It looks like it was just under 2,000 commits. We did pretty extensive testing, by having Blaze load a BUILD file and its transitive closure and then dump that parsed form back out to a binary format. Any automated commit had to preserve that parsed-and-dumped binary format bit for bit. The slowest part of the testing was waiting for Blaze to do all the loads.

Every day I would prepare and test as many files as I could, break them into CLs (think PRs), mail Rob a shell script he could run to approve them all, and go to bed. Then I'd get up early in the morning (5am ET) to submit the changes, because there were various cached indexes that got updated when BUILD files got submitted, and it seemed better to send them when not many people would be working.

That scheme worked until a system did fall over and someone got paged, and then after that I agreed to only submit the large changes during business hours. :-)

If you do it that way, then what should be a 1-line BUILD file change turns into something that changes every line. It distracts from the actual purpose of the future change. Many directories aren't touched for long periods of time. A few months from now someone tries to make a 1-line change and is unpleasantly surprised they have to deal with tons of seemingly spurious formatting changes. Not good.

Putting the time of submitting the changes on a small team (mostly me, with approvals from Rob and help from Laurent) was absolutely the right tradeoff. It avoided the "unfunded mandate" and tech debt of making everyone else deal with it.

Update: I found the FAQ we wrote back then. It was very short. These were the last two questions:

Q: Who will update all the existing BUILD files?

A: We will. There are nearly 200,000 of them, and we’ll take care of that. We’re sending CLs out now. If you want to do it yourself, that’s fine: see go/buildifiernow for a tool that can help.

Q: You’re creating a lot more work for me.

A: We are creating significant amounts of work for ourselves, including reformatting all 193,000 BUILD files in google3. For the rest of the engineers in the company, we intend to make the transition as smooth as possible, with integration in Eclipse, Emacs, and Vim, as well as tools like Rosie and GenJsDeps. It is an explicit goal not to create significant work for other engineers. If, as we roll this out, you find that we’ve created noticeable work in your workflow, please let us know so that we can address that.

Thanks for posting the update here. I was going to point out that 0.5ns for anything is almost always a sign of benchmarks being optimized away.

But even if those numbers had been accurate, it is important to think about how they compare to the operations being performed. Taking 4 nanoseconds to check for an error sentinel is not a huge deal when you've spent microseconds or even milliseconds waiting for a network service.

From the article:

The messages show the Chinese citizen and the collective members reacting in real-time to the vulnerability being detected.

“I don’t understand. Which idiot discovered this?” the Chinese citizen claiming responsibility asked.

“Looks like it’s being dug out,” a fellow said.

“Bullshit”, he replied. “F---. How did he find out?”

The Nightly can also reveal that the cyber infiltration operation may not yet be neutralised.

“And not just this one”, he said after claiming the XZ attack.

“It’s okay. I have another open-source thing. It’s also been poisoned. Still can play with it. F---ing hell,” he told another hacker collective in further messages also discovered by The Nightly.

Sure, like the one in https://9fans.github.io/plan9port/. :-)

Not if you use a modern language that enables TCP_NODELAY by default, like Go. :-)

> I'm kind of surprised that it's slower on AMD Ryzen - it looks like only the Pro series have a an actual co-processor. Weird decision on AMD's part to implement AES-NI without HW acceleration on some CPUs instead of just not implementing the AES-NI instruction set.

I meant that AES-GCM is 20% slower than ChaCha8 on that system, not that HW-accelerated AES-GCM is 20% slower than a software implementation. On the contrary, the HW-accelerated AES-GCM is 20X faster than software on that system.

For benchmarking ChaCha8, I ran:

    go test -bench=Block internal/chacha8rand

For benchmarking AES-GCM, I edited src/crypto/cipher/benchmark_test.go:51 to add 256 to the length list, and then I ran:

    go test -bench=GCM/-128-256 crypto/cipher
    GODEBUG=cpu.aes=off go test -bench=GCM/-128-256 crypto/cipher

You're right that we could use AES where available in the places where reproducibility doesn't matter, although that's a second implementation to debug and maintain. ChaCha8 seems fine.

OpenBSD had a similar problem with people calling arc4random and getting RC4 randomness, but they just changed it to use ChaCha20 anyway and backronymed it to "a replacement call for random".

https://man.openbsd.org/arc4random.3

Filippo and I dug into this a bit more, and it is possible that VSCode auto-complete (which also adds imports for the auto-completed things) is the culprit here. Apologies if that's what happened to you. We will look into fixing that.

Now that math/rand.Read is marked deprecated, at least if it does get selected, you get a nice strikethrough rendering as well.

It's a good question. We probably could have designed something based on AES-GCM instead, but it would have had more limited impact.

ChaCha8 is still very fast even without direct hardware acceleration. The 32-bit benchmarks at the end of the post are running with no assembly at all and still running within 2X of the 64-bit SSE2-based assembly. AES-GCM with hardware is pretty fast, but AES-GCM without hardware is quite slow.

Just now I tried benchmarking ChaCha8 in 256-byte chunks compared to AES-GCM in 256-byte chunks. With HW acceleration, AES-GCM is maybe 10% faster on my Apple M3 but 20% slower on my AMD Ryzen. Same ballpark as ChaCha8 though.

On the other hand, if I disable AES hardware acceleration, that same benchmark drops by about 20X. So using AES would not have been a good idea for systems without AES hardware.

Overall, not much win to AES in the best case, and quite a loss in the worst case.

That publication doesn't seem to mention the "lagged" part, or maybe I missed it. I am aware of https://www.leviathansecurity.com/blog/attacking-gos-lagged-... which also refers to it as a lagged Fibonacci generator.

Rob Pike and I exchanged mail with Don Mitchell (who wrote the original C version of the Go 1 generator) a few months back to see how he would describe the algorithm, and he said "As I recall Jim and I implemented Marsaglia's LFSR-like generator."

I think both descriptions (lagged Fibonacci and LFSR-like) are accurate in different ways, so either would be fine, but for the post I decided to use the original author's description.

Ouch, apologies for that. We changed goimports to prefer crypto/rand back in 2016, so I'm not entirely sure what happened during your refactoring. Perhaps code that used other math/rand-only APIs ended up in the same file. https://go-review.googlesource.com/24847

Anyway, I'm glad we're cleaning all this up!

In general there is very little overlap. crypto/rand vs math/rand don't even overlap except for rand.Read, and that was a mistake. We also corrected the import fixer in 2016 to prefer crypto/rand, so no one should have run into this problem in a very long time. https://go-review.googlesource.com/24847

It doesn't pick an arbitrary one. It prefers crypto/rand, and has since 2016 (https://go-review.googlesource.com/24847).