A tale of an impossible bug: big.LITTLE and caching
mono-project.com
mono-project.com
There is a Linux kernel patchset currently going through review which provides a workaround for this kind of erratum by trapping the CTR_EL0 accesses to the kernel so they can be emulated with the safe correct value: http://www.mail-archive.com/linux-kernel@vger.kernel.org/msg... and it seems to me that that's really the right way to deal with this.
(Edit: rereading the blog post, they say they need to figure out the global minimum, but I can't see how their code actually does that, since there's nothing that guarantees that the icache flush code gets run on every cpu before it's needed in anger.)
EDIT: Actually if the big and little cores are used together, and not exclusively, then this might still be an issue, yeah.
Core migration don't need to reach a global synchronization point, just enough so that the 2 cores in question agree with each other. This can be done without requiring global visibility of all operations of the source core.
If anything, the OS should have an API to tell you this info in advance.
The API for "tell me this info" is "read the CTR_EL0 register"; it's a hardware bug that it doesn't do the right thing on this particular chip.
The problem is like printing. If you put in an A4 or letter (ANSI A) sized sheet and tell your printer it's A3 or tabloid (ANSI B), you're gonna have problems.
I think the really correct answer might be to abandon the idea that the system has a single cache line size...
[1] With the exception of pre-Pentium CPUs, where modifying at various forward offsets from the locus of execution could give insight into how big the prefetch queue is. With the Pentium it was fully detected and the later multithreaded/multicored react similarly to cross-modifying code as described above, which leads me to believe that Intel is very much supportive of these things as otherwise they could've just told programmers to do as ARM does.
Maybe what ARM needs, short of doing it the Intel way, is a "flush region" instruction which takes both the address and size, so it can automatically flush the appropriate cache lines based on the current hardware's cacheline size.
An instruction for flushing an entire region would potentially have a very long execution time, which is awkward because you would want to be able to interrupt and resume it. So it would need "how far have I got" state stored somewhere. The obvious observation from a RISC-architecture point of view is that you can get the equivalent effect without the pain of making a long-running interruptible instruction, by having an "invalidate one cache line" instruction plus an explicit loop in the code, and that's what most architectures do.
https://news.ycombinator.com/item?id=9340231
An instruction for flushing an entire region would potentially have a very long execution time, which is awkward because you would want to be able to interrupt and resume it. So it would need "how far have I got" state stored somewhere.
x86 has the REP prefix for this purpose; used with certain instructions, it decrements a register and if it's nonzero, executes the instruction. The earlier implementations simply didn't update the instruction pointer in this case so the CPU would repeatedly fetch and execute the same instruction, and it's interruptable between each step. The register counts down how many iterations remain. Otherwise, the instruction pointer moves to the next instruction. Modern x86 handles this by generating uops instead in the decoder, but the basic functionality is the same.
The one at fault appears to be Samsung, who designed M1 Mongoose with 128 byte lines and packed it together with A53 cores in their SoC.
Samsung tried to improve performance, I don't think they are at fault at all.
Going to 128-byte cache lines was fine, but they should have made the lower-power part of the chip match (which in this case they likely couldn't because they licensed that design), or they should have made sure 128-byte lines were reported in all circumstances (which requires a hack similar to the workaround done in the kernel because again they can't make the A53 report 64 bytes).
This is similar to blaming OS/BIOS manufaturers for Y2K breaking "correctly written code" at the turn of the millenium.The code was incorrect in this instance because it assumed the cache size would be the same for all cores, Samsung simply manufactured a SOC that breaks that faulty assumption.
In this system, that would be 64 bytes.
> [3:0] IminLine Log 2 of the number of words in the smallest cache line of all the Instruction Caches that the processor controls.
> This values is:
> 0x4
> Smallest Instruction Cache line size is 16 words.
Are you sure? From the article, it sounds to me that the real cause of the error is an incorrect assumption made by the GCC people.
If we forget about the ARM spec explicitly enforcing this anyway, here's some food for thought: how exactly do you suppose the GCC people could write correct code, if they aren't allowed to make that assumption?
The CTR holds minimum line length values for: - the instruction caches
...this value is the most efficient address stride to use to apply to a sequence of address-based maintenance operations to a range of addresses...
The documentation for the CTR_EL0 reg talks about "caches under this processors control" which you could argue don't include other cores, but if you allow migration between cores, then line size changes underneath running software break the above "most efficient address stride" assumption. So you can't do that.
It boils down to this: If you can't assume that cache line size doesn't change underneath you, then you can't invalidate line by line at all, and would have to go word by word. That's terrible for performance (and a huge waste), which is why the spec says to use the above value for those operations.
That document does not explicitly forbids this. In addition, take a look at their sample code which indeed reads some cache configuration registers during each call. The same code is found verbatim in the linux kernel, if you now don't trust the ARM engineers :)
I don't think considering how to actually implement the basic operation without a terrible performance penalty is a "far fetched assumption".
> That document does not explicitly forbids this.
Yet it makes it clear software can be written to assume it doesn't happen, which is the same thing.
> In addition, take a look at their sample code which indeed reads some cache configuration registers during each call.
This doesn't prevent the problem at all, it just reduces the window for things to go wrong.
> The same code is found verbatim in the linux kernel, if you now don't trust the ARM engineers :)
I trust the ARM engineers. As I already said, their code is right, Samsung got it wrong. Note that the libgcc code that breaks was ALSO written by ARM.
Still a bit hazy on why they manually flush the cache for a given block of memory (presumably for protecting disclosure?) but I'm also a bit curious how it works if you get the sequence big fetches a cache line, switches to little which fetches a line (half as long and changing half the bytes in the cache) and then you switch back to big and its thinking it has a full cache line? Presumably there is some mechanism that invalidates cache lines?
The reason for the manual cache operations is because they're generating JITted code -- on ARM to ensure that what you execute is the same thing you just wrote you have to (1) clean the data cache, so your changes get out to main memory[.] and then (2) invalidate the icache, so that execution will fetch the fresh data from memory rather than using stale info. This clean-and-invalidate operation is usually informally called a flush, though it isn't really one in ARM terminology.
[.] not actually main memory, usually: only has to go out to the "point of unification" where the iside and dside come together, which is probably the L2 cache.
I'll admit that I find the question of dissimilar cache line sizes into the same cache intriguing from an architecture point of view. It has me doodling all sorts of questions into my notebook.
* allocate read/write buffer
* JIT instructions into it
* change mapping to read/execute
* run the JITted code
Then the kernel manages flushing the data caches on the mapping change, and Mono gets to wrap a Somebody Else's Problem field around it. It sounds like they are instead:
* allocate read/write/execute buffer
* JIT instructions into it
* manually flush relevant data caches (with an assumption that the cache line size is constant)
* run the JITted code
In which case a manual flush of the icache is needed, hence this problem.
The OS only let you alloc in large granules, like 4k or 16k, and the vast majority of the methods are significantly smaller than that, meaning a JIT must colocate multiple methods in the same allocation block or waste a significant amount of memory.
We could get around that by remapping memory between read/write to read/execute and have the OS solve the problem for us. Except for a couple of small details, modifying a memory mapping is very expensive and we're, well, in the performance business, and that mono is multi-threaded so one thread might be executing code from the exact page we just made non-executable.
This approach, IIRC, was tried by Firefox as it has some security advantages, but discarded due to the measurable performance impact - and they don't have the second problem as JS is single threaded.
Full Disclosure: I'm part of the Mono team.
And the "Firefox (Ion)" and "Firefox (non writable jitcode)" lines on https://arewefastyet.com/ seem to coincide...
But yes, actually making this work in practice is not at all simple.
Things get a lot more complicated when it comes to code patching, but the principle is similar.
Or is the flush guaranteed to flush all cores caches? That would be a fairly unusual design.
> modifying a memory mapping is very expensive
It used to be true that operations on memory mappings were appallingly expensive. However, the advent of virtualization has driven a significant change in performance. IIRC, ARMv8 has a TLB invalidation operation that is per-entry, addressed by the virtual address being invalidated. You don't need to flush the entire TLB cache.
Not just that, the ISA usually requires that a cache invalidation instruction be issued regardless of whether the chip's coherency will automatically detect and invalidate it.
In cases such as this post, it is perfectly valid for the silicon engineers to say that its the software's fault for not adhering to the ISA.
Since GDB is patching the instrution with ptrace to insert a breakpoint for example.
See my blog post about it: https://www.kayaksoft.com/blog/2016/05/11/random-sigill-on-a...
Or the post on the GDB mailling list: https://www.sourceware.org/ml/gdb/2015-11/msg00030.html
Too bad however that the kernel patchset mentionned in a previous post only covers arm64..
So it's still a problem from arm32.
I rather see the problem in the fact that there seems to be no possibility to say to the Linux scheduler: Only schedule this process/thread between cores that have the same cache line size. Or add an attribute when some thread is created on the cache line size of the cores it is allowed to run. Or an attribute when some thread is created for "allow arbitrary cache line size but don't let it run on cores with a different size". This way it would suffice to check for the cache size on program or thread start.
The intention of the big.LITTLE architecture is to let processes be migrated seamlessly between the small and big core and let the unused core be turned off to save power. The kernel and the hardware should work together to make the core switching transparent and expose a safe way to invalidate the cache independent of the current processor.
On the other hand flushing specific cache lines is a rather special feature. If the code uses such obscure low-level features (much more than the "typical" application) such as the invariant that the size of a cache-line stays constant over the execution (which most applications really don't care about) one can at least expect from the developer to pass this information to the scheduler so that the scheduler can take that this invariant will indeed be satisfied.
Rather: Only applications that don't depend on the invariant that the size of a cache line will stay constant over the execution time will take advantage of this. I can imagine ways how one could increase the advantage, but I don't want to go too much into technical details here.
In this case, it probably mattered because when JITing code, you need to explicitly flush instruction cache after changing code. But that's not anything the application cares about; that's something the runtime cares about, and the runtime is going to want to support taking advantage of the speed/power tradeoff without making application developers have to go to the trouble of thinking about it.
Also, from a user perspective, you don't want applications to be able to demand only the big, powerful cores. That will eat through your battery much faster, with likely very little benefit.
This should rather be a setting in the rights system that a user can refuse the right to an application to be able to demand big, powerful cores. I can nevertheless imagine quite well scenarios where enabling a (specific) application to do so can be quite useful.
Add an interface to the kernel/scheduler
void lock_cacheline_size(...)
void unlock_cacheline_size(...)
Calling lock_cacheline_size tells that from now on the thread must stay on a core with the same cache line size. Consider it as locking a mutex on the cache line size.
After this you can run critical code that depends on the fact that the cache line size stays constant for the whole time.
After you are finished with it, you call unlock_cacheline_size (as a kind of unlocking the mutex on the cache line size) - from now on the scheduler is free again to migrate the code again to cores with different cache line sizes.
Doesn't ARM have an "Enter Critical Region" instruction?
One question about the intro, which states that this is the first mass produced AMP architecture, but isn't the PlayStation 3's Cell CPU one?
PPE and SPE don't even share an ISA, SPE have a custom-built SIMD-oriented ISA.
Nope. Remember the Cell? The processor in the Playstation 3? One main CPU with 8 little CPUs and no shared memory, just channels.
The Playstation 4 isn't a AMP machine because programming the Cell was so hard.
The PS4 could be an AMP design if you consider the (closely coupled) GPU a processor.
It doesn't require the same gymnastics as the PS3 though because both the main processor and GPU are more capable. The SPUs were required to perform computation that the anemic PPU could not do as well as fill in where the pre-unified shader model GPU was unable to keep the pace.
Memory was shared on the PS3 but, from the SPUs, required explicit put and fetch operations.
There is no question of hardness of programming for Cell, but I think it's mostly about middleware support (probably because the platform is so different from PC and xbox360).
If they'd had, say, 16MB per processor, it might have worked out. One CPU for collision detection and physics, one for NPC management and AI, etc. But giving each SPE processor only 0.1% of the total memory space was too constraining.
https://gcc.gnu.org/ml/gcc-patches/2012-09/msg00076.html
Prior to that, the call:
asm volatile ("mrs\t%0, ctr_el0":"=r" (cache_info));
The big cores should report the smaller cache line size always.
At the time this patch was submitted, ARM was running a program that awarded engineers who could improve performance of aarch64.
Caches are bugs waiting to happen. Rob Pike @rob_pike 21 Mar 2014
This is one of those quotes where I feel there's more than one right answer. I like the addition of "off-by-one", and to make it a nice round three things, I usually use this version:
There are three hard things in computer science:
1. Naming things
2. 3. Concurrency
Cache Invalidation
4. Off-by-one errors
[2]: https://skeptics.stackexchange.com/questions/19836/has-phil-...
I like the addition of "concurrency" too, but I'm not quite sure how to make it flow....
I would do nasty, painful things to the designer of such a system.
Along similar lines, if you have an optimized routine using specific CPU instructions, you don't want to call CPUID (or equivalent) on every call to find out if you have those instructions; you want to call it once and cache the answer. If it can return different answers on different CPUs in the same system, you need to use a different mechanism instead, such as asking the OS for the least common denominator features of available CPUs, or notifying the OS that you need to run on one of the more capable CPUs that has the feature you need.
You'll choose a lowest common denominator of features sets.
Also, for this specific case, I doubt migration will keep around the contents of the cache lines and their 'dirty' bits (corollary: it will be possible to reliably detect a move, if one is willing to continuously run code that detects cache-line timing differences)
(This is all documented in the v8 ARM ARM section "Synchronization requirements for AArch64 System Registers".)
An astute reader might realize that computing the cache line on every
invocation is not enough for user space code: It can happen that a process
gets scheduled on a different CPU while executing the __clear_cache
function with a certain cache line size, where it might not be valid
anymore. Therefore, we have to try to figure out a global minimum of the cache line sizes across all CPUs.
In theory I think you could just invalidate the addresses byte for byte, ignoring the cache line size, but I assume the performance hit would be noticeable.
The only real fix is to do what they are doing -- always use the smallest line size of the system, regardless of which core you are running on.