Discovering a CPU Invent Bug within the Xbox 360

The sizzling display of Meltdown and Spectre truly reminded me of the time I found a related make bug within the Xbox 360 CPU – a newly added instruction whose mere existence became unhealthy.

Abet in 2005 I became the Xbox 360 CPU guy. I lived and breathed that chip. I composed safe a 30-cm CPU wafer on my wall, and a four-foot poster of the CPU’s structure. I spent so famous time understanding how that CPU’s pipelines labored that when I became requested to analyze some most unlikely crashes I became in a position to intuit how a make bug must always be their trigger. But first, some background…

The Xbox 360 CPU is a 3-core PowerPC chip made by IBM. The three cores sit down in three separate quadrants with the fourth quadrant containing a 1-MB L2 cache – it’s likely you’ll possibly possibly also gape the assorted substances, within the image at lawful and on my CPU wafer. Every core has a 32-KB instruction cache and a 32-KB data cache.

Trivia: Core Zero became closer to the L2 cache and had measurably decrease L2 latencies.

The Xbox 360 CPU had high latencies for every thing, with memory latencies being in particular injurious. And, the 1-MB L2 cache (all that could possibly well fit) became beautiful microscopic for a 3-core CPU. So, conserving direct within the L2 cache in declare to prick again cache misses became necessary.

CPU caches enhance performance attributable to spatial and temporal locality. Spatial locality capacity that while you’ve old one byte of facts then you definately’ll doubtlessly use other nearby bytes of facts rapidly. Temporal locality capacity that while you’ve old some memory then you definately will likely use it one more time within the finish to future.

But frequently temporal locality doesn’t in level of fact occur. Whereas it’s likely you’ll possibly possibly well be processing an incredible array of facts once-per-frame then it could well possibly possibly be trivially provable that this will all be gone from the L2 cache by the time you wish it one more time. You continue to favor that data within the L1 cache so that it’s likely you’ll possibly possibly also safe the benefit of spatial locality, nonetheless having it bright treasured direct within the L2 cache lawful capacity this will evict other data, possibly slowing down the other two cores.

Usually here’s unavoidable. The memory coherency mechanism of our PowerPC CPU required that each one data within the L1 caches also be within the L2 cache. The MESI protocol old for memory coherency requires that when one core writes to a cache line that every other cores with a replica of the identical cache line deserve to discard it – and the L2 cache became accountable for keeping notice of which L1 caches had been caching which addresses.

But, the CPU became for a video recreation console and performance trumped all so a fresh instruction became added – xdcbt. The in model PowerPC dcbt instruction became a in model prefetch instruction. The xdcbt instruction became an extended prefetch instruction that fetched straight from memory to the L1 d-cache, skipping L2. This supposed that memory coherency became no longer assured, nonetheless hello, we’re video recreation programmers, all of us know what we’re doing, this will be lovely.

Oops.

I wrote a broadly-old Xbox 360 memory replica routine that optionally old xdcbt. Prefetching the provision data became needed for performance and on the complete it would use dcbt nonetheless pass within the PREFETCH_EX flag and it would prefetch with xdcbt. This became now now not properly-concept-out.

A recreation developer who became using this feature reported irregular crashes – heap corruption crashes, nonetheless the heap constructions within the memory dumps looked in model. After searching on the fracture dumps for awhile I spotted what a mistake I had made.

Memory that is prefetched with xdcbt is poisonous. If it’s written by one more core before being flushed from L1 then two cores safe assorted views of memory and there is now not any exclaim their views will ever converge. The Xbox 360 cache lines had been 128 bytes and my replica routine’s prefetching went lawful to the quit of the provision memory, meaning that xdcbt became applied to about a cache lines whose latter parts had been portion of adjacent data constructions. Usually this became heap metadata – on the least that’s where we noticed the crashes. The incoherent core noticed old data (despite cautious use of locks), and crashed, nonetheless the fracture dump wrote out the precise contents of RAM so that we couldn’t gape what came about.

So, the handiest stable approach to utilize xdcbt became to be very cautious now to now not prefetch even a single byte beyond the quit of the buffer. I mounted my memory replica routine to keep some distance flung from prefetching too some distance, nonetheless while waiting for the fix the game developer stopped passing the PREFETCH_EX flag and the crashes went away.

The precise bug

To this level so in model, lawful? Cocky recreation builders play with fire, fly too finish to the sun, marry their moms, and a recreation console nearly misses Christmas.

But, we caught it in time, we obtained away with it, and we had been all dwelling to ship the games and the console and toddle dwelling pleased.

After which the identical recreation started crashing one more time.

The symptoms had been identical. Except for that the game became no longer using the xdcbt instruction. I could possibly step via the code and gape that. We had a important challenge.

I old the feeble debugging approach of searching at my display with a blank thoughts, let the CPU pipelines contain my unconscious, and I realized the challenge. A rapid electronic mail to IBM confirmed my suspicion about a delicate internal CPU ingredient that I had under no circumstances concept about before. And it’s the identical culprit within the abet of Meltdown and Spectre.

The Xbox 360 CPU is an in-declare CPU. It’s beautiful straightforward in level of fact, counting on its high frequency (now now not as high as hoped despite 10 FO4) for performance. But it definitely does safe a department predictor – its very long pipelines arrangement that mandatory. Right here’s a publicly shared CPU pipeline plot I made (my cycle-aesthetic version is NDA handiest, nonetheless looky here) that presentations all of the pipelines:

You’re going to be in a position to gape the department predictor, and likewise it’s likely you’ll possibly possibly also gape that the pipelines are very long (extensive on the plot) – loads long ample for mispredicted instructions to face up to the mark, even with in-declare processing.

So, the department predictor makes a prediction and the predicted instructions are fetched, decoded, and executed – nonetheless now now not retired except the prediction is acknowledged to be aesthetic. Sound acquainted? The realization I had – it became fresh to me on the time – became what it supposed to speculatively invent a prefetch. The latencies had been long, so it became essential to come by the prefetch transaction on the bus as rapidly as conceivable, and once a prefetch had been initiated there became no approach to smash it. So a speculatively-executed xdcbt became identical to an actual xdcbt! (a speculatively-executed load instruction became lawful a prefetch, FWIW).

And that became the challenge – the department predictor would frequently trigger xdcbt instructions to be speculatively executed and that became lawful as injurious as in level of fact executing them. One of my coworkers (thanks Tracy!) truly helpful a artful take a look at to study this – replace every xdcbt within the game with a breakpoint. This executed two issues:

1. The breakpoints had been now now not hit, thus proving that the game became now now not executing xdcbt instructions.
2. The crashes went away.

I knew that could possibly be the consequence and yet it became composed trustworthy. All these years later, and even after reading about Meltdown, it’s composed nerdy cold to perceive solid proof that instructions that had been now now not executed had been causing crashes.

The department predictor realization made it clear that this instruction became too unhealthy to safe any place within the code segment of any recreation – controlling when an instruction could possibly be speculatively executed is too sophisticated. The department predictor for indirect branches could possibly, theoretically, predict any address, so there became no “stable direct” to place an xdcbt instruction. And, if speculatively executed it would fortunately attain an extended prefetch of whatever memory the desired registers came about to randomly cling. It became conceivable to prick again the probability, nonetheless now now not keep away with it, and it lawful wasn’t price it. Whereas Xbox 360 architecture discussions continue to demonstrate the instruction I doubt that any games ever shipped with it.

I discussed this once for the interval of a job interview – “describe the toughest bug you’ve needed to analyze” – and the interviewer’s response became “yeah, we hit one thing identical on the Alpha processor”. The extra issues switch…

On account of Michael for some editing.