Memory Access Ordering in Complex Embedded Systems
Shore, Chris
There are many cases where it is necessary to enforce a particular order of memory accesses - not all of them are obvious. Most people are aware of the need to use “volatile” when accessing memory-mapped I/O. But that is only the beginning of the story. What about superscalar and out-of-order pipelines? Or multi-threaded and multi-processing systems which use shared memory? What about the effect of write buffers and caches? How does alignment affect this? As embedded systems become more complex, software developers need to know a lot more about how these systems access memory in order to identify potential ordering problems. This presentation will examine simple and complex cases using ARM examples covering VMSAv7 and PMSAv7.
 Okay, let's make a start. Bang on time. My name is Chris Shaw. I work for a company called Arm. How many of you have heard of Arm? Oh, that's so much of a better answer. I would have got 15 years ago when I first started working for Arm, when nobody had ever heard of it. How many of you are actually using Arm-based platforms at the moment? Actually writing code for them. Good. That's even more encouraging. I'm really pleased about that. The one thing you need to know about me, apart from the fact that I run Arm's customer training department and have done for just over 14 years now, is that my hearing is terrible. We're hearing aids, but they don't fix everything. So if you want to ask questions, it's probably best to catch me outside afterwards, rather than try and ask them in the kind of open class. So just save the questions for afterwards. I'll be more than happy to hang around for as long as necessary to deal with any issues that you have. It's kind of fascinating to be here, right at the beginning, I think, of embedded content coming into this particular conference, which by the way is fantastically organized. It's one of the best I've ever spoken at. Congratulations to the organizers. Because although the other presentations that I've been at so far this week have been right up in the cloud, they've been way up at high level, abstract, high level languages and so on, this is something completely different. This is way down at ground level, if not about 10 feet below ground level, right down in the weeds of programming for very sort of complex, but deeply embedded systems. A little bit about the genesis of this presentation. I don't know how many of you are members of LinkedIn, probably most of you I am, but do you sort of frequent the forums that go with LinkedIn? Most of the time they're full of students trying to get people to do their homework and asking stupid questions, but every now and then you get a really good question and a really, really fascinating discussion. This presentation came out of a discussion that happened about 18 months to two years ago on the embedded forum on LinkedIn. It started very innocently with a cross post from an RTOS group of a really simple and innocent question. It was this, is there any guarantee that two sequential writes to two separate volatile variables will be executed in the same order they appear in the code? Simple question, very simple. Now the discussion raged for weeks and it reached hundreds of posts and we had RTOS people, chip designers, C standards experts, language experts, programmers, compiler writers, system architects, everybody. Everybody pitched in on this one because everybody had a view on it. But down towards the end you could see the realisation starting to dawn on people that actually the answer to that question, which you really want to be yes, don't you? The answer to that question actually is no. And that is real shock to some people, especially if you're programming on an embedded system, to find that that question is not true, is a real shock. So it prompted me to look a bit further into the issues that are kind of buried in that question and a lot of other issues it touches on. And a lot of them I think are really completely unknown to a lot of people who are developing in the embedded arena and people who have been developing there for a long time. And we really have to get to grips with this because the embedded world has kind of moved on a long way. Consider for instance, just first of all, that question, it executed in the same order as they appear in the code. Now just think about that word order. What does it mean? Does it mean the instructions are fetched in the same order, issued to the pipeline in the same order, generate their addresses in the same order, get issued to the load store unit in the same order, does the rights get issued from the core to the bus interface in the same order, what about the order in which those rights reach the memory system, what about the order they enter and leave a write buffer, what about the observability by an external agent. All of those are aspects of the order in which two memory accesses occur and all of them are different. And all of them can potentially be changed and kind of come into play when you try to answer that question. It's a huge issue when we don't really have time to do more than just really touch on it today in a very, very brief way. But first of all, I'm going to take you on a little trip down my particular memory lane. They say nostalgia is not what it used to be, neither is our industry. It changes faster than almost any other industry on earth and embedded has gone through huge transformations in the last five years, in the last ten years, even the last five. Okay, it's changed a lot for the better. I started out writing embedded software just about 30 years ago. I guess some of you have probably been at the game longer than I have. You're going to have memories of what it was like too. But the first project I worked on after graduating from university, we were developing code for a radio network switch, operator console, it was a touchscreen thing, and it ran on a custom board which we built with a 6809 processor from Motorola, and we cross-compiled the code on an IBM PCXT. Remember those? Yep. It had twin floppy drives, so you put your source code on one disk and the editor on the other, and you put them both in and you made your edits. And when you finished that, you took the editor disk out and put the compiler disk in, because you couldn't put them both on the same disk because the disk wasn't big enough, and then you compiled your code, and then you took that out and you put the ROM programmer disk in and you transferred the code into an eProm, physically into an eProm, which you had to cook under a UV light to erase the previous contents before you put the new one in, and then you physically plugged that into the board. And the company couldn't afford an emulator, so we had to debug everything using printf and a serial port. And you basically just hit reset and see what happens. And if it doesn't work, you have to go through the whole disk swappy thing and start all over again. A real, sort of, horrendous way to have to develop code. I bet you've got stories of your own. So things like that have got so much better. We now have on-chip debug over JTAC, so you don't even need to shell out for an emulator anymore. So, yeah, in lots of ways, embedded development, development in general, has got an awful lot easier. But think about the systems that we used to use. They used to be so simple. Some low-end systems still are, but even the high-end systems we used are very simple, because everything conformed to what you call the sequential execution model. But systems were simple. The buses were simple. They were single-layer. They were dumb. They were in order. Right buffers were a twinkle in a designer's eye. And unless you were into really, sort of, wacky stuff like DMA, there was only one thing that could control the bus, and that was the processor. So the processor really was in charge of everything that went on to memory. And if you knew what the processor was doing, you knew what memory was doing. There was nothing else you needed to know. Inside the processor, yeah, that was all nice and neat and tidy, too. With just very simple pipelines or even no pipelines at all, all instructions were issued in sequence, executed in sequence, and retired in sequence. Nice and easy. And all instructions executed to completion, including memory effects, before the next one even got to the execute stage. So if an instruction wrote something to memory, that was all completed before you even started on the next instruction. Beautifully, nice, and sequential. Every instruction was essentially an independent unit. Now, that sequential execution model applied at pretty much every level in the system. Instruction fetches, memory accesses, internal control, peripheral action. It was very nice and predictable, and life was very simple. And you really only needed to know two things to write correctly functioning code for such a system. Two things about memory, anyway. One was that sometimes if you did an action on a peripheral, sometimes that took a bit of time to complete. So you might have to pull for its completion or give yourself an interrupt later on to check that it completed. And the second was you had to tell the compiler that some memory locations in your system were not well behaved. In general, that was memory mapped onto peripherals, and you had to tell the compiler that sometimes they change when you're not looking. And that was the prime mover behind that volatile keyword that I'm sure you will know and love. And volatile was really kind of all that you needed. They just told the compiler that certain memory locations change when you weren't looking. And that kind of covered memory map peripherals. It covered global variables that might get changed by an interrupt handler. And the very simple example on the slide, you can see what it does is it prevents the compiler from caching the results from these two loads. It actually has to do two loads from the same memory location, one after the other, because what you're telling the compiler is that register, that location may change in between these two loads. So I really, really want you to do this twice. Now you can see actually, this is the ARM compiler. You can see what the ARM compiler has done here is actually realized that reading the same memory location twice is completely stupid because it's always going to be the same. So it's actually optimized the loads and the compare away completely and just returned you to anyway. So to stop the compiler doing that, which is clever but misguided, you use the volatile keyword. And the key thing about this is it only affects the behavior of the compiler. If you declare a variable as volatile, that's not really visible to the processor at all at runtime. It's not visible to any other part of the system either. It only has an effect on code generation. And if the system doesn't behave the way the compiler expects it to, or the way you have told the compiler it's going to behave, then you're going to have potential problems. Now unfortunately, that is exactly what complex modern systems do. Because they try to be so clever, because they try to increase performance using all kinds of execution tricks in hardware, they do sometimes end up not doing quite what the compiler expects them to do. And memory access ordering is one very obvious area where that becomes very, very visible. So that's simple in order predictable deterministic machine that I had two slides ago. Well, modern systems don't look like that anymore. They tend to look like this. This is a typical, very typical modern embedded system. If anywhere in the previous presentation which Espen just gave on FPGAs, this is the kind of system you'll find in the latest Zinc FPGA from Xilinx. It has a quad core A53 and it has a separate co-processor, a separate processor for handling real-time acceleration, and it has a GPU. And all of this is available in an embedded FPGA today. Multiple processors, maybe in a coherent cluster, sharing a cache, multi-layer bus, multi-master bus, intelligent peripherals, bus bridges, and all kinds of things. And semi-autonomous processing units that you've got to worry about. And all of this is basically what you would find inside the guts of a mobile phone today. It's simple though it seems. And in a system like this, say you've got to deal with things like multi-core processors, they might be running asymmetric or symmetric multi-threaded code. You've got to deal with very complex processor execution pipelines. And those pipelines, in order to maximize throughput of instructions and throughput of data, they do all kinds of things. They speculatively prefetch, they speculatively execute, they try and predict branches ahead of time and speculatively fetch branch destinations. They multi-issue, they issue out of order, and they complete out of order. And they do all kinds of nasty things. You might have multiple levels of cache in your old traditional system. You may not have had cache at all. In a typical sort of phone standard system of today, you probably got three levels of cache. And that level one is probably going to be a coherent cache shared between multiple processors. Level two is going to be shared possibly between multiple clusters of processors. And level three will be out on the bus. Where is your data? Which cache is it in? Keeping track of that is quite difficult. Even when an item, say, is in a particular cache, you might have cache coherency management hardware. We have that on ARM systems, which automatically ensures that at least some subset of the system components have access to the latest value. But you've got to track which subset of components that is. Memory interfaces, they also, they're very clever too. They try and optimize bus traffic to by reducing the number of bus transactions that actually go on. So two writes to the same location. The bus interface might look at that and say, I was no point in doing the first one. I'll just do the second one because there's no point in writing something that immediately overwriting it. Is there? Well, there might be. But for the bus interface, we'll just decide no. Or a location that's just been read, it might cache that in a fill buffer, in an explicit cache, in a transfer buffer somewhere. Write buffers, try and amalgamate accesses. So to write to two adjacent half words, for instance, the right buffer might decide, oh, well, I'll just amalgamate those and do a single one. Write because that's a simpler transaction. It's quicker, uses less energy, and it minimizes the time that I'm occupying the bus. All of this stuff goes on. And most of it is there to help you. Most of it does help you. It helps massively. But sometimes it gets in the way. So the key is knowing when it might happen, knowing what might happen, and knowing what you have to do as a software engineer to kind of just control it to the level that you want to control it. And compilers have got a lot cleverer too. I've just so far been talking about the hardware, but I've just been talking about the compilers are an interesting subject as well. So first of all, let's look at volatility, this volatile keyword. And that simple piece of code declares two hardware registers, control and status, because they're memory mapped, are good little programmers, declared them both as volatile. And what he wants to ensure here is that the device is reset by writing one to the control register here before we start reading stuff out of it. Okay. He wants to be sure that those two things happen in order. Now, does declaring those two items as volatile guarantee that that is the case? Does it guarantee that the peripheral sitting out in the memory system sees this right before it sees that read? Answer? You might not be too surprised. No, it doesn't. And there's at least two reasons for that. There may be others, but there's at least two. And the first reason comes down to the compiler. And the compiler can reorder memory accesses as long as program behavior is not affected. Okay. Now that's program behavior in the view of the compiler. Now, if the compiler was to exchange the accesses to control and status, as far as it's concerned, logical program behavior hasn't changed. There's no data dependencies, no address dependencies between these two accesses. So why shouldn't it switch them over? Either at parsing time or at code generation time. Answer? It can. And sometimes it will. Actually, it's worse than that. Some compilers will and some compilers won't. Because the C standard is actually deliberately silent on this. And it leaves it up to compiler implementers to choose how they behave in that particular situation with that, with the accesses to volatile variables. So the guy who writes the compiler can actually make it up on this one. And you can't rely on what decision he or she has taken. Now, the second reason is down to the hardware. The right to the control register. Maybe that goes through a write buffer. It's perfectly reasonable for it to do that. And that write buffer might delay it by any length of time. And the read from status might be satisfied by a cache. Okay. We can reasonably stop that happening since this is a peripheral. And meaning that it's much quicker to read status than it is to write the control by. Now, as far as the processors concerned, say, they're independent variables. There's no visible data dependencies between the two. So they can be passed through the pipeline in pretty much any order the processor likes. So that code provides no guarantee that the peripheral will be accessed correctly, which is really quite depressing. Even more depressing when you realize that, say, the problem is partly in the compiler, partly in the hardware, and partly somewhere in between the two. I'll just remind you before we go on, say, the other use of the volatile keyword. And this is here we're declaring status. We would declare status as a volatile variable because it's used in the foreground and also in the background. It's used in an interrupt handler as well as the main program. So it may get changed in this interrupt handler while the main program is sort of executing in the foreground. So we have to declare it as volatile so the compiler doesn't cache it in that foreground main loop. If it does, then our program quite simply wouldn't work. So I'm hoping you're familiar with both of these cases, but they illustrate an important point. And this is kind of where I'm going. Neither the compiler nor the hardware have enough knowledge of what your program is intended to do to be able to guarantee that your program will do the right thing. Okay? So certain memory accesses have side effects and certain memory accesses may be linked to each other, like control and status. They're two registers in the same peripheral. Now, they are linked to each other, but in a way that the processor can't see. And also in a way that the compiler can't see either. And in this case, they're desperate desire to run your code as quickly as possible. Both the compiler and the hardware make all kinds of optimizations that affect the function in this situation. Because they're both missing key information and you as the programmer have that information and you have to pass it on. Let's just, again, look at the superscaler. Look at interesting pipelines. This is a rough representation of the pipeline that we used in the Army 11 about 10 years ago. There's one stage missing. There's a fetch stage on the left-hand side. It's what, it's a six-stage pipeline if you add the fetch stage on. The compiler, the pipeline that we use in Cortex-A57 has 15 stages. All right? So pipelines have moved on a little bit since the days that you and I were at college. They're a lot longer. They are superscaler, multi-issue, multiple execution units, out-of-order execution, speculative execution, out-of-order completion. And these very quickly baffle you, to be honest. And it's very difficult and almost impossible to start trying to analyze them by hand or in your head. I'm going to stop. Just make one, one very important point before I carry on. I keep saying that the compiler of the hardware might not do the right thing. Okay? Let's be careful of exactly what we mean by that. I don't mean to say that they don't execute instructions properly or that compilers carry unsafe optimizations. They don't. They always do what you tell them to do. Okay? Precisely. And that sequential execution model still holds, but it only holds at the local level. This processor executing this instruction stream connected to that bus interface. Okay? It has to. All the standards require that that sequential execution model has to hold, but only at that level, only at that very, very localized level. And where that kind of breaks down, and it breaks down spectacularly, is where vital information about things outside that context needs to be given to the processor or given to the compiler, like memory locations behaving in a non-standard way, or a memory region being accessed by an independent processing element, or two elements accessing the same cache, for instance. That information, say the compiler and the hardware just don't have that. They really, really, really do try to do the right thing. But sometimes they need that extra information to do it. Okay? Let's go down just kind of another level and look at maybe what might be happening at pipeline level, just to illustrate this. This is a simple example of how a modern pipeline might affect directly the order that instructions get executed, specifically the order that memory accesses occur. Okay? Remember, what the pipeline is trying to do is maximize instruction throughput. It's trying to help. Okay? So supposing your source code results in that sequence of instructions on the left. Now, if you put that through a simple in-order processor, and there are still some of those around, you might get the sequence in the middle. The instructions are issued into the pipeline in the order that they occur in the program. You can see, no change there. And subject to things like write buffers and caches, which are kind of outside the pipeline, you can reasonably safely make the assumption that the order, the memory accesses happen specifically the store will occur before the load. Okay? An out-of-order, super-scaler pipeline might actually, when it's executing these instructions, execute them in the sequence on the right. And it's done this to hide the latency of the load which is caused to stall here, and the latency of the multiply which is caused to stall a bit further up. And to hide those and basically bleed the stalls out of the instruction sequence, it's promoted the load above the store, which is given the multiply latency time to happen, and it's given the load use latency time to happen behind other instructions. Now, it is entirely free to do this. Okay? Entirely free. And this is a concrete example, if you like, of that first slide we started with, the control register and the status register. This is a concrete example of how the pipeline might reverse those two accesses at runtime. Now, there's three kind of key things to note about this. The first, as I say, is the pipeline is completely free to do this, and you actually want it to do it. Because doing this increases the performance of your program significantly. And if you turned all this stuff off, which you can't, your program would perform significantly worse. Number two, you can't predict it reliably. Okay? Because a lot of this depends on instruction context at runtime. It depends on the context and usage of particular registers at runtime. It may even depend on things like the alignment in memory of individual instructions. Okay? And you can't reliably predict that by hand. You can't predict it with a static analysis. You only find out whether this is going to happen when you actually put the instructions through the processor and see what comes out at the other end. Because all of this is happening in real time. So, and the third thing, you need this behavior. You really do need it because you need the performance that it gives you. And certainly on ARM processors, we don't give you the ability to turn stuff like this off. We don't want you turning it off because it's what gives you the performance that you need. So, moving on, we've established, say, that there's key information about the system, about how it behaves and how the code and the processor need to deal with that, which we possess and we have to pass on to the system. We have to pass it on in such a way that the compiler and the hardware can actually start to behave the right way. Now, from here on in, I'm going to use explicit ARM examples. I mean, these examples, okay, they're ARM assembly instructions, but they could be illustrated using pretty much any architecture. I make no apology from now on that I'm going to use explicit ARM systems, for example, because A, that's what I know about, and B, I work for ARM, so damn it, I'm going to talk about it. Okay, the first concept I need to introduce you to is memory types. So, we know not all memory behaves the same way. We know that, we've established it. Now, most of it does. The vast majority of memory in your system does, and that's the kind of memory that you put your code in, that you put your stack in, your heap and so on. That behaves normally, but some of it doesn't. Some of it is mapped to peripheral registers, shared memory, DMA memory, frame buffers, and all kinds of interesting, tricky things. And we kind of need a way to get that information about these two different kinds of memory to the system in some way so that it can take account of that. Since ARMv6, ARM11 about 10 years ago, the ARM architecture has sort of recognized this concept of memory types. Every addressable part of your address map must be given a type. That's mandatory, okay, and you have to do that. And the system needs to know what that type is. I'll tell you how you do that a little bit later on. So, the vast majority of memory in a system is normal memory, what we call normal, because it behaves normally. Now, it's well-behaved. And the compiler, sorry, the compiler of the machine is free to make all kinds of assumptions about that and make all kinds of optimizations. So, for instance, because normal memory does not have side effects on any access, we permit speculative access, for instance. So, on data side and instruction side, we allow it to merge, reorder, resize, repeat, cache, and buffer, all memory accesses, okay? Now, that's a serious amount of operations. Provided that there are no observable dependencies within a sequence of accesses to normal memory, the processor can do any of that, okay? So, it will observe data dependencies, it will observe address dependencies, and it will reserve resource dependencies. But apart from that, it's free to do all of this stuff, and it's a huge positive effect on performance. ARM architecture actually requires these days that you have to put your instructions in normal memory, which is a bit sad to those of us who remember the fun of executing code out of FIFOs. You can't do that anymore, sorry about that. But the main other kind of memory is device memory, and that's memory map peripherals and other interesting things. Now, the key thing about these accesses is they have side effects, and those side effects may or may not be observable to the processor. So, all that neat stuff that we allowed for normal memory is not and cannot be allowed in device memory. You can't, for instance, ever allow the processor to carry out speculative accesses to device memory. You do not want it reading your peripheral registers without explicit program instruction to do so, because those reads have side effects. You will say, because some devices are size sensitive, you can't allow it to merge and resize accesses. That's safe in normal memory. It's not with peripherals. And you can't allow it to repeat accesses or delete accesses either. And with ARM systems, we do allow peripheral accesses to go through a right buffer when you're writing to them, but we do not allow peripheral accesses to be cached. Okay, that's kind of obvious. There is a third kind right at the bottom here called strongly-ordered memory, which is nasty stuff. That's very strict and really, really, very nasty, and it has incredibly strict ordering rules. And to be honest, nobody actually, even in the architecture team at ARM, really seems certain whether anybody ever uses that and needs it. So, we actually deprecated it in the last revision of the architecture, and it's been deleted in the current revision of the architecture. So, if you see stuff about strongly-ordered memory, in most cases, you can safely ignore that. It doesn't exist anymore. So, how does the system get that information? It's important to realize that we provide this information to the hardware, right? And it's the hardware that uses it. This information is not provided to the compiler. There's no semantics within C, for instance, to allow you to do that. And the compiler has no knowledge of any of this stuff. But in ARM systems, you program normal and device, all kinds of other memory attributes. You program that into either a memory management unit on a virtual memory system or a memory protection unit on a real-time system. And at runtime, the memory interface uses that information. It reads it out of the memory management unit, out of the memory protection unit, and it uses that to control and govern how it accesses particular regions of memory. Some very small microcontrollers, the Cortex-M systems, some of those don't have an MPU, a memory protection unit. And in that case, they actually have an architecturally fixed memory map. So, you know, there will be a region which is designated for code and is required to be normal and is fixed that way in the architecture. There is a region for peripherals, and that's device memory and so on. And that's documented in the architecture. The second thing I've got to introduce you to is the concept of memory barriers. Now, you might have come across these in other architectures. If heaven forbid, you've programmed on anything else in your life other than ARM. Sometimes they're called fences, synchronization instructions. PowerPC, for instance, has the fantastically named EIEIO instruction, which stands for Enforce in Order Execution of IO. I really hope that the architect's had a fantastic session in the bar the day they wrote that one, because opportunities like that don't come up very often in our industry. But, say, like other architectures, ARM has a set of barrier instructions, and you use these at specific points in your code sequence where the sequence of memory operations really matters, and you want it to matter. So, at the top of the slide there, that's the example that we used just a few slides ago to illustrate reordering in that superscalar processor. And in that example, we saw it was possible for the load in the store actually to be switched round at runtime. And there's kind of no easy, efficient way you can fix that within the syntax of C, as understood by the compiler. So what you have to do is insert a memory barrier. There it is, dmb. That's a memory barrier instruction. And what that does, it ensures that the memory access instructions complete in the order in which they appear in the instruction stream. Now, it doesn't stop the processor from doing other stuff around those instructions, provided the memory access ordering is observed. So if there were other instructions which didn't access memory in this gap here between the dmb and the load, then the core would quite happily carry on and do those ads, multipliers, all kinds of other stuff. But the one thing it can't do is initiate this load before that store is completed. Okay? And the core is required to do that to be architecturally compliant. Now, that involves making sure that write buffers are flushed, for instance. It doesn't involve flushing data out of caches. You have to manage that yourself. But the point of the barrier, say, is that it enforces those two memory accesses, the load and the store, there to happen in the intended order in program order. And in a high-level language like C, for instance, you would insert that either using a bit of inline assembler or much better still using an intrinsic function. There is an underscore underscore dmb intrinsic function. And the nice thing about doing it with an intrinsic function is that the C compiler treats that as a sequence point and it handily restricts some of the optimization that the compiler can carry out across the intrinsic function. Very nice. There are two other barrier instructions we have. A DSB, which is a little bit stricter. And what the DSB does, it's called a data synchronization barrier, and it actually stops the processor. It would halt the processor dead at this point until all the memory accesses before this point have completed. And at that point, it would then carry on. So it's a little bit stricter. And I'll show you an example in a minute just of a situation where a DSB is actually needed because a dmb is not quite strict enough. And the final one down here, ISB, is an instruction synchronization barrier. And basically that causes the instruction pipeline and any prefetch buffers to be flushed out and refilled from scratch. And it's the kind of instruction that you would use after any operation that alters the instruction context. The most obvious example that occurs to everybody is self-modifying code. That would be an example of the case where you need an ISB. If you modify the code stream at runtime, then you need to issue an ISB to force it all to be refetched. I sometimes think that all engineers harbor a secret ambition to write some self-modifying code and issue it to the public. Relatively few of us ever succeed, thank goodness. But it's actually very important in, for instance, operating system context switches where one of the things that you're doing there is possibly changing the virtual physical address map. And part of that, you know, you've changed the address map for the instruction side. And you need to throw out all the prefetched instructions and get them back in again. So here's the promised example of a situation where you actually do need a DSB. This is a sequence that you might find at the end of an interrupt handler where one of the last things you do here is write to a peripheral register that clears the interrupt condition down. And then this instruction here, RFE, that's returned from exception. And that would return you back to your foreground process. Obviously, very important that the interrupt is actually physically cleared in the system before you execute the return from exception. Otherwise, you might just get reinterrupted again. Now, that might be spurious. Your system might handle that gracefully, but it might not. Even if it does handle it gracefully, what you've done is just wasted time handling a spurious interrupt. So what you have to do here is put some kind of barrier in between the right to the peripheral register and the return from exception. And a DMB is not enough here because the RFE, in fact, the RFE here is not a memory access instruction which is accessing the same memory domain and the same memory type as this one. This is presumably accessing device memory. This is accessing normal memory. And even within the architecture, ordering between normal and device memory is actually not enforced. Device accesses, they're enforced. Normal accesses are enforced if you want them to be. But between the two, we don't actually enforce them unless you stick a barrier in to do that. So you do actually need a DSB here to physically stop the process of doing anything else at this point. And physically make it sure that this instruction has completed, been issued, been observed in the memory system or whatever before you actually carry on with returning from your exception. So you need, in this case, say the DMB's stricter cousin, the DSB. Now the requirement for barriers is actually very common. And if you're writing any code that deals with memory map peripherals and very often deals with instruction context, so interrupt contexts, then you should very seriously consider where and when you might need barriers. Sometimes you need more than one. Here's a couple of fairly complex examples. The special situations where you carry out, say what the architecture calls context altering operations. This is anything that changes the address map, either physically or virtually, anything that enables or disables a coprocessor. Again, that changes the instruction context. And sometimes you have to combine these with other maintenance operations, which I'll show you in a second. So there's a couple of examples here. The first one is quite a common thing to do on older-arm systems, and you still see it on simple systems today. And it involves using a custom peripheral out in the system called a remap peripheral. What that does is it physically changes the address decode scheme at runtime. You write to this peripheral and it will switch around the placement of some blocks of memory. And the prime reason for wanting to do that, certainly on older-arm systems, is that the vector table is fixed at zero. So it resets at zero. So you have to have some non-volatile memory. You're going to have some ROM down there at zero. When your system is actually running, it's much nicer to have the vector table in RAM, where you can change it and it's faster and it's volatile and you can install new handlers and all that stuff. So actually, rather some systems don't let you relocate the vector table. Even if they do, they only let you relocate it to one particular place and you might not have any RAM there. So what you need to do is actually physically swap the ROM out and put it somewhere else and move some RAM down. And you do that by altering the address decode map. And you do that using this peripheral. And you can see that after we've done that, you need to put two barriers in there. One is a DSB, which says make sure that that remap operation has completed before I carry on. Just stop right here. Once that's completed, you carry on and you hit an instruction synchronization barrier. And that says, I've just changed the system address map. If you fetch any instructions ahead, if you've got any clever stuff like pre-predicting branches, forget it. Throw it out and reload the pipeline in the new address context. Now, you might think that a branch would be good enough for that because isn't that what branches do? Don't they flush the pipeline out? Well, yes, they do sometimes. There's modern pipelines, they're very clever. And in fact, without these barriers here, what it would do is it would get to this branch instruction and say, oh, that's an unconditional branch. I can predict that statically now and it will throw the branch instruction away. It actually won't bother executing it and it will fetch immediately after here this new code destination. And it will carry straight on executing and the branch instruction will actually disappear. So unless you force it to reload that branch instruction and re-execute it, by the time you get there, it may have gone. So you do need the instruction synchronization barrier. It does more than just what a branch does. The second example down here is something that you might find in an operating system context switch where virtual memory is involved. And the first instruction here, maybe that's updating some of the contents of the page tables that define our virtual address map. So the first DSP, that ensures that this write has actually gone to memory. And it ensures that the table is actually now updated, the next external memory, and we can carry on. And then you've got this one here, TLB-IMVA. I won't bother about all the syntax of it, but basically that invalidates the matching TLB entries. The TLBs, if you're not familiar with those, are basically caches for page translations. So we have to chuck all those out if we've changed one overlap to something that's cached. Then we have to flush the branch predictor because the branch predictor also stores address information about branch destinations and branch locations. So we have to flush all that out. And then the DSP, one other effect of a DSP is it also stalls until maintenance operations have completed. So these operations may take quite a long time to go through the TLB and chuck stuff out and to go and clear out the branch predictor cache. So we have to stop there, wait for those to complete. Then we need an ISB to re-synchronize the instruction context, and then finally we can carry on. So you can see that, actually, in a space of five instructions, you've got three barriers. All of them are actually necessary, and all of them actually have to be there. And if you're the kind of guy that gets involved porting operating systems, then that's the kind of thing that you will have to be aware of and you'll have to think very carefully about. Now, let's turn to a slightly different situation here. This introduces a whole new ton of complications. So far, we have only dealt with one processor. But what if your system has two processors? I've got another session tomorrow, interestingly enough, on writing multi-core software for ARM platforms, which we're going to a lot of this stuff in a lot more detail. So if this wets your appetite, I do encourage you to come to that. But anyway, here we are, two processors, P1 and P2, and a nice ordered neat and tidy view of the world. If processor one updates variable X and then variable Y, and then processor two reads the two, then there are three possible outcomes that are logically expected, if you like. If processor two reads Y and X, and reads them in that order, no, reads Y and X after this point here, then it will see the new value for X and the new value for Y. If it reads them before this point, it'll see the old X and the old Y. And if it reads them right in the middle here, it'll see the old Y and the new X. It will never see the new Y and the old X. And if your program ever sees that combination, then you can reasonably assume that something has actually gone wrong. Now, unfortunately, in a modern multi-processing system, this assumption is no longer true. And you do have to deal with the fact that you might see combinations of data values which are unexpected and which are logically impossible, because somebody's changing your data. So that simple little sequence there, and the simple question is two load instructions, sorry, loading two variables from memory, right, and the load instruction to load A comes before the instruction to load B. Very simple. You and I can see that. Simple question, in which order are A and B physically fetched from memory? Now, that should be easy to answer, shouldn't it? Just look at the order in which the instructions are there. But if you ignore pipeline effects for now, and we've seen what pipeline effects can do, what if B is cached and A is not, right? In that case, the memory system could return the value for B much quicker than the value for A. And a typical ARM pipeline these days has a load store unit that can handle five or six outstanding memory transactions and return them in any order, just whenever the memory system gives them back. It'll pass them back onto the pipeline. So what if they're both cacheable, but the load of A causes a cache miss? Then the process is free because we do hit under miss completion. The process is just free to carry on, try and load B while the line fill is happening to get hold of A. So the value for B may well be returned long before the value for A. So, and to remove the stalls, as we've seen, the pipeline may well reorder them at runtime anyway. So already you can see exactly what behavior results in breaking that assumption on the previous slide. Now, it's likely, say, that if you're running this on a single processor, none of that would matter. By the time you get to the add instruction, which is when you need both of those values, the processor will have both of them. And surely it doesn't matter in which order they were loaded. But as we saw in the previous slide, what if another processor somewhere in the system is updating both of those variables at the same time as we're trying to read them? Right? Those assumptions that we made on the previous slide, as we can see, are now broken. And this second processor, if it was doing something slightly more complex than just adding the two values together, would see a logically inconsistent or broken combination of those two values. So we have to be able to cope with that. Or, we have to be able to stop it happening. And coping with something like this in the general case is not really possible and not really desirable in most cases. So we kind of have to make sure it doesn't happen. So how do we do that? Several ways. One could be to make sure that we understand the effects of the cache and we get it out of the way. Or ensure that we have some hardware for managing cache coherency or providing cache coherency. Right? And those are both subjects that I'm going to deal with tomorrow in the multi-core session. But the other approach, which we'll look at now, is to make sure that we have a viable method for locking or protecting critical sections like this where ordering of access by two different processing agents actually matters. So you could write a very simple lock like that. Now, from what you've seen in the last few slides, if you just take a moment to read that code, you'll probably work out very quickly that that lock sequence won't actually work. Well, to be precise, it's not guaranteed to work as intended. And if there's one thing you have to have in a lock function, it has to work reliably every time. Now, what you do is you need a mechanism that's going to enforce the ordering between two memory accesses, specifically between a load and a store. Now, if any of you have been around ARM technology or ARM processes for long enough, you might remember the swap instructions. Anyone remember that? Yay! Three of you. Good stuff. Right. Now, the swap instruction, that basically carried out an atomic load and store, and it swapped a register with memory location. Now, that was exactly what you need here because it forced the load and store to happen in a guaranteed order and in a guaranteed atomic sequence. Now, the way we used to do that was the bus, the memory interface, had a lock signal on it. And between the load and the store, the processor would basically flip the lock signal up, and that would lock anybody else out of the bus and refuse to allow anyone to do anything with memory while the processor was doing these two accesses. Now, that worked very well. And on a simple, you know, sort of single layer, single master bus system, yeah, it was kind of okay. But in the bus systems that we use today, that's just not possible. You can't, A, can't allow a single processor or single element to lock the bus for that length of time. And B, it's very, very difficult to propagate that kind of lock information across complex bus matrices and then through bridges and all kinds of other stuff. It's very, very difficult to do. So in architecture version 6, we defined a new method for doing this. And in architecture version 7, we actually deleted the swap instruction. So if you were very fond of it, I'm sorry. The new instructions, there's a pair of instructions, load and store, exclusive. And most modern architectures have a similar facility to this. Load, acquire and store, release, very, very similar in other architectures. And they all work basically the same way. The way they work in ARM, that must be, the way they work in ARM is that the load exclusive instruction loads from an address and then reserves it for exclusive access. So basically it sets a little tag in the memory system that says, I'm accessing this. Okay? And it sets a flag. The store exclusive instruction stores to an address and returns you a successful status if the flag was still set. Okay? It also then clears the reservation. So you can kind of see where we're going here, that any number of agents in the system can use a load exclusive instruction to load the current value of a lock. But only one of them will be able to do a subsequent successful store because as soon as that's happened, all the others will try and the reservation's gone. So they will all fail and they'll have to go back and, you know, back off and retry. Now in ARM systems, this is something you need to consult the documentation of your platform quite carefully because we don't actually mandate or design or ship the IP necessary in the memory system to implement this lock system. It's very fundamentally integrated within the bus matrix. And the bus matrix is something which is designed by the chip designer, not by the ARM architecture people. So you find that these locks are sometimes placed in slightly different places and they behave in slightly different ways. Their architectural behavior is constrained. But for instance, they're free to recognize any number of outstanding locks from one upwards. So you find some simple lock systems that only recognize one outstanding lock. So if you have multiple lock variables in memory and you try and access all of them, that counts as one lock. And as soon as you store to one of them, it unlocks all the rest. Now that guarantees you correct behavior, but it's not best performance. Other systems divide memory up into what we call a granule, the exclusives reservation granule, brilliant name. And locks which are in separate granules have separate reservation flags. So if you have many locks in your system, check the documentation. And it may be worth you actually spreading the locks out so that they're in separate granules. If your system supports separate reservations, then you may get better performance out of it. For instance. But I said two instructions. There are actually three on the slide here. There's a third one which I should point out before we go on. Clear exclusive. And that basically clears any outstanding reservations in the system. And that's the kind of thing that you might use in an operating system. Context switch so that an outgoing process which has an appending lock or appending reservation doesn't generate a false positive when the new process comes in. And that one might have appending lock as well. And there's potential for confusion there. So in context switch, you very often find this clear exclusive instruction just to clear everything up. So a very simple example. That's how you might build a simple lock structure using these instructions. The lock sequence on the left. The unlock sequence is on the right. And if you look at the code on the left, you can see there's a load exclusive. A little bit lower down. There's a store exclusive. And the load exclusive loads the current value of the lock and it checks and it keeps reloading it until it's unlocked. And then it goes down here and it tries to store to it to actually claim the lock by writing the locked value to it. Now multiple agents, multiple processes, multiple threads might be trying to do this all at the same time. And they'll eventually get through here. One of them will execute this store exclusive instruction. And if you look at it, if you're familiar with our assembler, you'll see that it's a bit unusual. Most stores only have one source register for the value you're going to store. This one actually has two. R1 is the value that we're going to store out. And R2 comes back with the status. And R2 comes back as zero if the lock, sorry, if the reservation has been cleared by the time you get here. It comes back with one if the reservation is still there. So if the reservation persists from here to here, then R2 will tell you you've succeeded. You've got your lock off you go. If somebody else has done a store to this lock location in between here and here, this store exclusive will fail. And you'll go around and try again or back off or do whatever your OS tells you to do. The unlock sequence is trivial because a standard store instruction clears any outstanding reservations on the location as soon as it does it. So you just have to write the unlock value and that automatically clears the reservation and other people can get in. Now then, we're going to have a summary time. I have eight minutes left. I'm kind of conscious that we've only had time to touch on a few of the dragons that exist in this area of embedded development. There's a huge amount of other stuff and other knowledge and other experience that we could go through. But just to build my way of summary, I just want to summarize the different properties of memory accesses that come into play here. And the things that you need to worry about when you're working on a complex embedded system. First of all, memory ordering. If you care that memory accesses must occur in the order that you've written them, then you need to start putting barriers in to make sure that happens. And you need to make sure that you might use locks if necessary to protect critical sections. And you need to make sure that peripheral memory is marked as device. Cardinality. This is if I have written three load instructions, I want three read accesses, right? The cardinality must match. And there, you need to get rid of things like speculative access on both the data side and the instruction side. Arm cores do both these days. And the way you do that is by declaring sensitive memory as device memory and that bans speculative access in those regions of memory. Volatility. Yeah, that's the most common one that we're all aware of. A memory location may change when you or the compiler or the machine are not looking. And in this case, yes, you need to use the volatile keyword and we all know that. Completion. Another one. I need to know when this access has completed before you move on. Again, use barriers for that to make sure that subsequent instructions are not executed. Remember, you've got two flavors of that. dmb, dsb. dsb is stricter than dmb. And in order to stop before moving on, you would use a barrier for that. Observability is by far the most complex one. It's similar to completion, but it's subtly different. Now, an access completes when it kind of leaves our sphere of influence. So when it leaves the kind of local story around my pipeline, my processor, my bus interface, my write buffer, as soon as an access goes beyond that, it's completed as far as we're concerned. But that doesn't necessarily mean that other parts of the system can see the result of that access. And you do need to bring other context into play there. You do need to consider perhaps cache management. You do need to consider, you know, where memory is being shared and how far out of the bus system that memory is, whether it's beyond caches or beyond write buffers and so on. So observability is by far the most complex. And again, I'll deal with some of those issues tomorrow. And finally, atomicity. Atomicity is a really, really fascinating subject. And atomicity is the concept of a sequence of memory accesses must be carried out without anything else getting in the way. So, you know, without any other accesses interleaving in between, for instance, without the bus being granted to anyone else during that particular sequence. And this is really important when you're dealing with shared memory, memory map peripherals and all kinds of things. So critical lock structures are one way that you can guarantee this. But it gets even more complicated when you look right down at the bus level on a complex pipeline processor or placed with a complex memory interface because you need to look very carefully, if it matters to you, at what the architecture says about atomicity. The wonderful thing about the ARM architecture is all processors that have ARM on the lid have to conform with it. But you say, you find, for instance, all single word-sized memory accesses are guaranteed to be atomic. So if you write to a 32-bit word, the architecture guarantees you that that operation, that bus transaction, is atomic. It has to be. Otherwise, that processor is not ARM compliant. And we will get out our big stick and our contract and go and sue them, beat them around the head and make them re-spin the chip and do it again. What about things like load and store multiple instructions, if you remember those? Are they atomic? Well, sometimes they are and sometimes they're not. You need to go and check the architecture very, very carefully and find out. What about accesses to double words, half words? Again, sometimes they are and sometimes they're not. Depends on what kind of memory you're accessing and also depends on the alignment of the address that you're accessing. Unaligned accesses are generally not guaranteed to be atomic, generally. But again, there's a huge amount in here and it has its very own completely incomprehensible chapter in the architecture efforts manual, which I would encourage you to go and have a look at if you want to go to sleep one evening. Anyway, so many questions, so little time, we just don't have time to go to any of that stuff. But hopefully what I've managed to get over to you is that there are lots of cases where the hardware and to some extent the compiler, but especially the hardware, do things that you need to understand. And you need to understand when and why and how these things happen to work out whether you care. And if you do care, then you need to know what to do about that. Memory types and barriers and locks are the three main techniques we used to do that. Just by way of closing on that theme, on November the 26th, 1922, Howard Carter opened just a little chink in the top corner of the door into Toot & Commune's burial chamber. And he kind of looked through the door and Lord Canavan, his backer, was kind of standing behind him, desperate to try and see. But it was only his tiny hole in the door and what he was doing was holding the candle up to it and just trying to see what he could see. And he wrote this in his diary afterwards. He says, As my eyes grew accustomed to the light, details of the room within emerged slowly from the mist. Strange animals, statues and gold, everywhere the glint of gold. And for the moment, it must have seemed an eternity to the other one standing by. I was struck dumb with amazement. And when Lord Canavan, unable to stand the suspense any longer, said anxiously, can you see anything? It was all I could do to get out the words, yes, wonderful things. And I kind of feel a little bit like that today. We kind of just peeled back a little chink and held a candle through the crack. And you can see some great stuff in here. But we do not have a chance to see it all. So I'm going to leave you with two literary quotations because I like to inject a bit of culture into our uncultured industry sometimes. This is from Marcel Praust's, Al-Récherche du Temp-el-Du, Remembrance of Things Past is not necessarily the remembrance of things as they were. And just as human memory is infallible, foolable and imperfect, so sometimes the memory systems that we work within our development work don't quite behave the way you want them to. But that's the literary quote, the pretentious one. I much prefer this one. This is the Red Queen said to Alice in the Looking Boss. It's a poor kind of memory that only works backwards. And sometimes it seems like our memory systems work backwards too. Anyway, I hope that was useful and a kind of introduction to all the stuff that's in here. And I encourage you to come to session tomorrow. We'll unpack some of this a little bit more in the context of multi-core processing and MP core platforms. I am told to encourage you to vote using the buttons at the back. If you've enjoyed this and learnt something new, then please bash the green button. If I've left you with the impression that you need to know quite a lot more, yes, again, please bash the green button. And then come and talk to me afterwards. And I'll tell you how we can fix that. But thanks very much. Thank you.
 Okay, let's make a start. Bang on time.  My name is Chris Shaw. I work for a company called Arm. How many of you have heard of Arm?  Oh, that's so much of a better answer. I would have got 15 years ago when I first started working for Arm,  when nobody had ever heard of it. How many of you are actually using Arm-based platforms at the moment?  Actually writing code for them. Good. That's even more encouraging. I'm really pleased about that.  The one thing you need to know about me, apart from the fact that I run Arm's customer training department  and have done for just over 14 years now, is that my hearing is terrible.  We're hearing aids, but they don't fix everything. So if you want to ask questions, it's probably best to catch me outside afterwards,  rather than try and ask them in the kind of open class. So just save the questions for afterwards.  I'll be more than happy to hang around for as long as necessary to deal with any issues that you have.  It's kind of fascinating to be here, right at the beginning, I think, of embedded content coming into this particular conference,  which by the way is fantastically organized. It's one of the best I've ever spoken at. Congratulations to the organizers.  Because although the other presentations that I've been at so far this week have been right up in the cloud,  they've been way up at high level, abstract, high level languages and so on, this is something completely different.  This is way down at ground level, if not about 10 feet below ground level, right down in the weeds of programming for very sort of complex,  but deeply embedded systems. A little bit about the genesis of this presentation.  I don't know how many of you are members of LinkedIn, probably most of you I am, but do you sort of frequent the forums that go with LinkedIn?  Most of the time they're full of students trying to get people to do their homework and asking stupid questions,  but every now and then you get a really good question and a really, really fascinating discussion.  This presentation came out of a discussion that happened about 18 months to two years ago on the embedded forum on LinkedIn.  It started very innocently with a cross post from an RTOS group of a really simple and innocent question.  It was this, is there any guarantee that two sequential writes to two separate volatile variables will be executed in the same order they appear in the code?  Simple question, very simple. Now the discussion raged for weeks and it reached hundreds of posts and we had RTOS people,  chip designers, C standards experts, language experts, programmers, compiler writers, system architects, everybody.  Everybody pitched in on this one because everybody had a view on it.  But down towards the end you could see the realisation starting to dawn on people that actually the answer to that question,  which you really want to be yes, don't you? The answer to that question actually is no.  And that is real shock to some people, especially if you're programming on an embedded system,  to find that that question is not true, is a real shock.  So it prompted me to look a bit further into the issues that are kind of buried in that question and a lot of other issues it touches on.  And a lot of them I think are really completely unknown to a lot of people who are developing in the embedded arena  and people who have been developing there for a long time.  And we really have to get to grips with this because the embedded world has kind of moved on a long way.  Consider for instance, just first of all, that question, it executed in the same order as they appear in the code.  Now just think about that word order. What does it mean? Does it mean the instructions are fetched in the same order,  issued to the pipeline in the same order, generate their addresses in the same order,  get issued to the load store unit in the same order,  does the rights get issued from the core to the bus interface in the same order,  what about the order in which those rights reach the memory system,  what about the order they enter and leave a write buffer,  what about the observability by an external agent.  All of those are aspects of the order in which two memory accesses occur and all of them are different.  And all of them can potentially be changed and kind of come into play when you try to answer that question.  It's a huge issue when we don't really have time to do more than just really touch on it today in a very, very brief way.  But first of all, I'm going to take you on a little trip down my particular memory lane.  They say nostalgia is not what it used to be, neither is our industry.  It changes faster than almost any other industry on earth and embedded has gone through huge transformations in the last five years,  in the last ten years, even the last five. Okay, it's changed a lot for the better.  I started out writing embedded software just about 30 years ago.  I guess some of you have probably been at the game longer than I have.  You're going to have memories of what it was like too.  But the first project I worked on after graduating from university,  we were developing code for a radio network switch,  operator console, it was a touchscreen thing,  and it ran on a custom board which we built with a 6809 processor from Motorola,  and we cross-compiled the code on an IBM PCXT.  Remember those? Yep.  It had twin floppy drives, so you put your source code on one disk and the editor on the other,  and you put them both in and you made your edits.  And when you finished that, you took the editor disk out and put the compiler disk in,  because you couldn't put them both on the same disk because the disk wasn't big enough,  and then you compiled your code, and then you took that out and you put the ROM programmer disk in  and you transferred the code into an eProm, physically into an eProm,  which you had to cook under a UV light to erase the previous contents before you put the new one in,  and then you physically plugged that into the board.  And the company couldn't afford an emulator, so we had to debug everything using printf and a serial port.  And you basically just hit reset and see what happens.  And if it doesn't work, you have to go through the whole disk swappy thing and start all over again.  A real, sort of, horrendous way to have to develop code. I bet you've got stories of your own.  So things like that have got so much better.  We now have on-chip debug over JTAC, so you don't even need to shell out for an emulator anymore.  So, yeah, in lots of ways, embedded development, development in general, has got an awful lot easier.  But think about the systems that we used to use. They used to be so simple.  Some low-end systems still are, but even the high-end systems we used are very simple,  because everything conformed to what you call the sequential execution model.  But systems were simple. The buses were simple. They were single-layer. They were dumb.  They were in order. Right buffers were a twinkle in a designer's eye.  And unless you were into really, sort of, wacky stuff like DMA, there was only one thing that could control the bus,  and that was the processor. So the processor really was in charge of everything that went on to memory.  And if you knew what the processor was doing, you knew what memory was doing.  There was nothing else you needed to know. Inside the processor, yeah, that was all nice and neat and tidy, too.  With just very simple pipelines or even no pipelines at all, all instructions were issued in sequence,  executed in sequence, and retired in sequence. Nice and easy.  And all instructions executed to completion, including memory effects,  before the next one even got to the execute stage.  So if an instruction wrote something to memory, that was all completed before you even started on the next instruction.  Beautifully, nice, and sequential. Every instruction was essentially an independent unit.  Now, that sequential execution model applied at pretty much every level in the system.  Instruction fetches, memory accesses, internal control, peripheral action.  It was very nice and predictable, and life was very simple.  And you really only needed to know two things to write correctly functioning code for such a system.  Two things about memory, anyway.  One was that sometimes if you did an action on a peripheral, sometimes that took a bit of time to complete.  So you might have to pull for its completion or give yourself an interrupt later on to check that it completed.  And the second was you had to tell the compiler that some memory locations in your system were not well behaved.  In general, that was memory mapped onto peripherals, and you had to tell the compiler that sometimes they change when you're not looking.  And that was the prime mover behind that volatile keyword that I'm sure you will know and love.  And volatile was really kind of all that you needed.  They just told the compiler that certain memory locations change when you weren't looking.  And that kind of covered memory map peripherals.  It covered global variables that might get changed by an interrupt handler.  And the very simple example on the slide, you can see what it does is it prevents the compiler from caching the results from these two loads.  It actually has to do two loads from the same memory location, one after the other, because what you're telling the compiler is that register,  that location may change in between these two loads.  So I really, really want you to do this twice.  Now you can see actually, this is the ARM compiler.  You can see what the ARM compiler has done here is actually realized that reading the same memory location twice is completely stupid because it's always going to be the same.  So it's actually optimized the loads and the compare away completely and just returned you to anyway.  So to stop the compiler doing that, which is clever but misguided, you use the volatile keyword.  And the key thing about this is it only affects the behavior of the compiler.  If you declare a variable as volatile, that's not really visible to the processor at all at runtime.  It's not visible to any other part of the system either.  It only has an effect on code generation.  And if the system doesn't behave the way the compiler expects it to, or the way you have told the compiler it's going to behave, then you're going to have potential problems.  Now unfortunately, that is exactly what complex modern systems do.  Because they try to be so clever, because they try to increase performance using all kinds of execution tricks in hardware,  they do sometimes end up not doing quite what the compiler expects them to do.  And memory access ordering is one very obvious area where that becomes very, very visible.  So that's simple in order predictable deterministic machine that I had two slides ago.  Well, modern systems don't look like that anymore. They tend to look like this.  This is a typical, very typical modern embedded system.  If anywhere in the previous presentation which Espen just gave on FPGAs,  this is the kind of system you'll find in the latest Zinc FPGA from Xilinx.  It has a quad core A53 and it has a separate co-processor,  a separate processor for handling real-time acceleration, and it has a GPU.  And all of this is available in an embedded FPGA today.  Multiple processors, maybe in a coherent cluster, sharing a cache, multi-layer bus, multi-master bus, intelligent peripherals, bus bridges, and all kinds of things.  And semi-autonomous processing units that you've got to worry about.  And all of this is basically what you would find inside the guts of a mobile phone today.  It's simple though it seems.  And in a system like this, say you've got to deal with things like multi-core processors,  they might be running asymmetric or symmetric multi-threaded code.  You've got to deal with very complex processor execution pipelines.  And those pipelines, in order to maximize throughput of instructions and throughput of data,  they do all kinds of things.  They speculatively prefetch, they speculatively execute, they try and predict branches ahead of time and speculatively fetch branch destinations.  They multi-issue, they issue out of order, and they complete out of order.  And they do all kinds of nasty things.  You might have multiple levels of cache in your old traditional system.  You may not have had cache at all.  In a typical sort of phone standard system of today, you probably got three levels of cache.  And that level one is probably going to be a coherent cache shared between multiple processors.  Level two is going to be shared possibly between multiple clusters of processors.  And level three will be out on the bus.  Where is your data?  Which cache is it in?  Keeping track of that is quite difficult.  Even when an item, say, is in a particular cache, you might have cache coherency management hardware.  We have that on ARM systems, which automatically ensures that at least some subset of the system components have access to the latest value.  But you've got to track which subset of components that is.  Memory interfaces, they also, they're very clever too.  They try and optimize bus traffic to by reducing the number of bus transactions that actually go on.  So two writes to the same location.  The bus interface might look at that and say, I was no point in doing the first one.  I'll just do the second one because there's no point in writing something that immediately overwriting it.  Is there?  Well, there might be.  But for the bus interface, we'll just decide no.  Or a location that's just been read, it might cache that in a fill buffer, in an explicit cache, in a transfer buffer somewhere.  Write buffers, try and amalgamate accesses.  So to write to two adjacent half words, for instance, the right buffer might decide, oh, well, I'll just amalgamate those and do a single one.  Write because that's a simpler transaction.  It's quicker, uses less energy, and it minimizes the time that I'm occupying the bus.  All of this stuff goes on.  And most of it is there to help you.  Most of it does help you.  It helps massively.  But sometimes it gets in the way.  So the key is knowing when it might happen, knowing what might happen, and knowing what you have to do as a software engineer to kind of just control it to the level that you want to control it.  And compilers have got a lot cleverer too.  I've just so far been talking about the hardware, but I've just been talking about the compilers are an interesting subject as well.  So first of all, let's look at volatility, this volatile keyword.  And that simple piece of code declares two hardware registers, control and status, because they're memory mapped, are good little programmers, declared them both as volatile.  And what he wants to ensure here is that the device is reset by writing one to the control register here before we start reading stuff out of it.  Okay. He wants to be sure that those two things happen in order.  Now, does declaring those two items as volatile guarantee that that is the case?  Does it guarantee that the peripheral sitting out in the memory system sees this right before it sees that read?  Answer?  You might not be too surprised.  No, it doesn't.  And there's at least two reasons for that.  There may be others, but there's at least two.  And the first reason comes down to the compiler.  And the compiler can reorder memory accesses as long as program behavior is not affected.  Okay.  Now that's program behavior in the view of the compiler.  Now, if the compiler was to exchange the accesses to control and status, as far as it's concerned, logical program behavior hasn't changed.  There's no data dependencies, no address dependencies between these two accesses.  So why shouldn't it switch them over?  Either at parsing time or at code generation time.  Answer?  It can.  And sometimes it will.  Actually, it's worse than that.  Some compilers will and some compilers won't.  Because the C standard is actually deliberately silent on this.  And it leaves it up to compiler implementers to choose how they behave in that particular situation with that, with the accesses to volatile variables.  So the guy who writes the compiler can actually make it up on this one.  And you can't rely on what decision he or she has taken.  Now, the second reason is down to the hardware.  The right to the control register.  Maybe that goes through a write buffer.  It's perfectly reasonable for it to do that.  And that write buffer might delay it by any length of time.  And the read from status might be satisfied by a cache.  Okay.  We can reasonably stop that happening since this is a peripheral.  And meaning that it's much quicker to read status than it is to write the control by.  Now, as far as the processors concerned, say, they're independent variables.  There's no visible data dependencies between the two.  So they can be passed through the pipeline in pretty much any order the processor likes.  So that code provides no guarantee that the peripheral will be accessed correctly, which is really quite depressing.  Even more depressing when you realize that, say, the problem is partly in the compiler, partly in the hardware, and partly somewhere in between the two.  I'll just remind you before we go on, say, the other use of the volatile keyword.  And this is here we're declaring status.  We would declare status as a volatile variable because it's used in the foreground and also in the background.  It's used in an interrupt handler as well as the main program.  So it may get changed in this interrupt handler while the main program is sort of executing in the foreground.  So we have to declare it as volatile so the compiler doesn't cache it in that foreground main loop.  If it does, then our program quite simply wouldn't work.  So I'm hoping you're familiar with both of these cases, but they illustrate an important point.  And this is kind of where I'm going.  Neither the compiler nor the hardware have enough knowledge of what your program is intended to do to be able to guarantee that your program will do the right thing.  Okay?  So certain memory accesses have side effects and certain memory accesses may be linked to each other, like control and status.  They're two registers in the same peripheral.  Now, they are linked to each other, but in a way that the processor can't see.  And also in a way that the compiler can't see either.  And in this case, they're desperate desire to run your code as quickly as possible.  Both the compiler and the hardware make all kinds of optimizations that affect the function in this situation.  Because they're both missing key information and you as the programmer have that information and you have to pass it on.  Let's just, again, look at the superscaler.  Look at interesting pipelines.  This is a rough representation of the pipeline that we used in the Army 11 about 10 years ago.  There's one stage missing.  There's a fetch stage on the left-hand side.  It's what, it's a six-stage pipeline if you add the fetch stage on.  The compiler, the pipeline that we use in Cortex-A57 has 15 stages.  All right?  So pipelines have moved on a little bit since the days that you and I were at college.  They're a lot longer.  They are superscaler, multi-issue, multiple execution units, out-of-order execution,  speculative execution, out-of-order completion.  And these very quickly baffle you, to be honest.  And it's very difficult and almost impossible to start trying to analyze them by hand or in your head.  I'm going to stop.  Just make one, one very important point before I carry on.  I keep saying that the compiler of the hardware might not do the right thing.  Okay?  Let's be careful of exactly what we mean by that.  I don't mean to say that they don't execute instructions properly  or that compilers carry unsafe optimizations.  They don't.  They always do what you tell them to do.  Okay?  Precisely.  And that sequential execution model still holds, but it only holds at the local level.  This processor executing this instruction stream connected to that bus interface.  Okay?  It has to.  All the standards require that that sequential execution model has to hold,  but only at that level, only at that very, very localized level.  And where that kind of breaks down, and it breaks down spectacularly,  is where vital information about things outside that context needs to be given to the processor  or given to the compiler, like memory locations behaving in a non-standard way,  or a memory region being accessed by an independent processing element,  or two elements accessing the same cache, for instance.  That information, say the compiler and the hardware just don't have that.  They really, really, really do try to do the right thing.  But sometimes they need that extra information to do it.  Okay?  Let's go down just kind of another level and look at maybe what might be happening at pipeline level,  just to illustrate this.  This is a simple example of how a modern pipeline might affect directly the order that instructions  get executed, specifically the order that memory accesses occur.  Okay?  Remember, what the pipeline is trying to do is maximize instruction throughput.  It's trying to help. Okay?  So supposing your source code results in that sequence of instructions on the left.  Now, if you put that through a simple in-order processor,  and there are still some of those around,  you might get the sequence in the middle.  The instructions are issued into the pipeline in the order that they occur in the program.  You can see, no change there.  And subject to things like write buffers and caches, which are kind of outside the pipeline,  you can reasonably safely make the assumption that the order, the memory accesses happen  specifically the store will occur before the load.  Okay?  An out-of-order, super-scaler pipeline might actually, when it's executing these instructions,  execute them in the sequence on the right.  And it's done this to hide the latency of the load which is caused to stall here,  and the latency of the multiply which is caused to stall a bit further up.  And to hide those and basically bleed the stalls out of the instruction sequence,  it's promoted the load above the store,  which is given the multiply latency time to happen,  and it's given the load use latency time to happen behind other instructions.  Now, it is entirely free to do this.  Okay?  Entirely free.  And this is a concrete example, if you like,  of that first slide we started with, the control register and the status register.  This is a concrete example of how the pipeline might reverse those two accesses at runtime.  Now, there's three kind of key things to note about this.  The first, as I say, is the pipeline is completely free to do this,  and you actually want it to do it.  Because doing this increases the performance of your program significantly.  And if you turned all this stuff off, which you can't,  your program would perform significantly worse.  Number two, you can't predict it reliably.  Okay?  Because a lot of this depends on instruction context at runtime.  It depends on the context and usage of particular registers at runtime.  It may even depend on things like the alignment in memory of individual instructions.  Okay?  And you can't reliably predict that by hand.  You can't predict it with a static analysis.  You only find out whether this is going to happen  when you actually put the instructions through the processor  and see what comes out at the other end.  Because all of this is happening in real time.  So, and the third thing, you need this behavior.  You really do need it because you need the performance that it gives you.  And certainly on ARM processors, we don't give you the ability to turn stuff like this off.  We don't want you turning it off because it's what gives you the performance that you need.  So, moving on, we've established, say,  that there's key information about the system, about how it behaves  and how the code and the processor need to deal with that,  which we possess and we have to pass on to the system.  We have to pass it on in such a way that the compiler and the hardware  can actually start to behave the right way.  Now, from here on in, I'm going to use explicit ARM examples.  I mean, these examples, okay, they're ARM assembly instructions,  but they could be illustrated using pretty much any architecture.  I make no apology from now on that I'm going to use explicit ARM systems, for example,  because A, that's what I know about, and B, I work for ARM,  so damn it, I'm going to talk about it.  Okay, the first concept I need to introduce you to is memory types.  So, we know not all memory behaves the same way.  We know that, we've established it.  Now, most of it does.  The vast majority of memory in your system does,  and that's the kind of memory that you put your code in,  that you put your stack in, your heap and so on.  That behaves normally, but some of it doesn't.  Some of it is mapped to peripheral registers, shared memory,  DMA memory, frame buffers, and all kinds of interesting, tricky things.  And we kind of need a way to get that information about these two different kinds of memory  to the system in some way so that it can take account of that.  Since ARMv6, ARM11 about 10 years ago,  the ARM architecture has sort of recognized this concept of memory types.  Every addressable part of your address map must be given a type.  That's mandatory, okay, and you have to do that.  And the system needs to know what that type is.  I'll tell you how you do that a little bit later on.  So, the vast majority of memory in a system is normal memory,  what we call normal, because it behaves normally.  Now, it's well-behaved.  And the compiler, sorry, the compiler of the machine  is free to make all kinds of assumptions about that  and make all kinds of optimizations.  So, for instance, because normal memory does not have side effects on any access,  we permit speculative access, for instance.  So, on data side and instruction side,  we allow it to merge, reorder, resize, repeat, cache, and buffer,  all memory accesses, okay?  Now, that's a serious amount of operations.  Provided that there are no observable dependencies  within a sequence of accesses to normal memory,  the processor can do any of that, okay?  So, it will observe data dependencies,  it will observe address dependencies,  and it will reserve resource dependencies.  But apart from that, it's free to do all of this stuff,  and it's a huge positive effect on performance.  ARM architecture actually requires these days  that you have to put your instructions in normal memory,  which is a bit sad to those of us who remember the fun  of executing code out of FIFOs.  You can't do that anymore, sorry about that.  But the main other kind of memory is device memory,  and that's memory map peripherals and other interesting things.  Now, the key thing about these accesses is they have side effects,  and those side effects may or may not be observable to the processor.  So, all that neat stuff that we allowed for normal memory  is not and cannot be allowed in device memory.  You can't, for instance, ever allow the processor  to carry out speculative accesses to device memory.  You do not want it reading your peripheral registers  without explicit program instruction to do so,  because those reads have side effects.  You will say, because some devices are size sensitive,  you can't allow it to merge and resize accesses.  That's safe in normal memory. It's not with peripherals.  And you can't allow it to repeat accesses or delete accesses either.  And with ARM systems, we do allow peripheral accesses  to go through a right buffer when you're writing to them,  but we do not allow peripheral accesses to be cached.  Okay, that's kind of obvious.  There is a third kind right at the bottom here  called strongly-ordered memory, which is nasty stuff.  That's very strict and really, really, very nasty,  and it has incredibly strict ordering rules.  And to be honest, nobody actually, even in the architecture team at ARM,  really seems certain whether anybody ever uses that and needs it.  So, we actually deprecated it in the last revision of the architecture,  and it's been deleted in the current revision of the architecture.  So, if you see stuff about strongly-ordered memory,  in most cases, you can safely ignore that.  It doesn't exist anymore.  So, how does the system get that information?  It's important to realize that we provide this information to the hardware, right?  And it's the hardware that uses it.  This information is not provided to the compiler.  There's no semantics within C, for instance, to allow you to do that.  And the compiler has no knowledge of any of this stuff.  But in ARM systems, you program normal and device,  all kinds of other memory attributes.  You program that into either a memory management unit on a virtual memory system  or a memory protection unit on a real-time system.  And at runtime, the memory interface uses that information.  It reads it out of the memory management unit, out of the memory protection unit,  and it uses that to control and govern how it accesses particular regions of memory.  Some very small microcontrollers, the Cortex-M systems,  some of those don't have an MPU, a memory protection unit.  And in that case, they actually have an architecturally fixed memory map.  So, you know, there will be a region which is designated for code  and is required to be normal and is fixed that way in the architecture.  There is a region for peripherals, and that's device memory and so on.  And that's documented in the architecture.  The second thing I've got to introduce you to is the concept of memory barriers.  Now, you might have come across these in other architectures.  If heaven forbid, you've programmed on anything else in your life other than ARM.  Sometimes they're called fences, synchronization instructions.  PowerPC, for instance, has the fantastically named EIEIO instruction,  which stands for Enforce in Order Execution of IO.  I really hope that the architect's had a fantastic session in the bar the day they wrote that one,  because opportunities like that don't come up very often in our industry.  But, say, like other architectures, ARM has a set of barrier instructions,  and you use these at specific points in your code sequence  where the sequence of memory operations really matters, and you want it to matter.  So, at the top of the slide there, that's the example that we used just a few slides ago  to illustrate reordering in that superscalar processor.  And in that example, we saw it was possible for the load in the store  actually to be switched round at runtime.  And there's kind of no easy, efficient way you can fix that within the syntax of C,  as understood by the compiler.  So what you have to do is insert a memory barrier.  There it is, dmb. That's a memory barrier instruction.  And what that does, it ensures that the memory access instructions  complete in the order in which they appear in the instruction stream.  Now, it doesn't stop the processor from doing other stuff around those instructions,  provided the memory access ordering is observed.  So if there were other instructions which didn't access memory in this gap here  between the dmb and the load, then the core would quite happily carry on  and do those ads, multipliers, all kinds of other stuff.  But the one thing it can't do is initiate this load before that store is completed.  Okay? And the core is required to do that to be architecturally compliant.  Now, that involves making sure that write buffers are flushed, for instance.  It doesn't involve flushing data out of caches.  You have to manage that yourself.  But the point of the barrier, say, is that it enforces those two memory accesses,  the load and the store, there to happen in the intended order in program order.  And in a high-level language like C, for instance,  you would insert that either using a bit of inline assembler  or much better still using an intrinsic function.  There is an underscore underscore dmb intrinsic function.  And the nice thing about doing it with an intrinsic function  is that the C compiler treats that as a sequence point  and it handily restricts some of the optimization  that the compiler can carry out across the intrinsic function.  Very nice.  There are two other barrier instructions we have.  A DSB, which is a little bit stricter.  And what the DSB does, it's called a data synchronization barrier,  and it actually stops the processor. It would halt the processor dead at this point  until all the memory accesses before this point have completed.  And at that point, it would then carry on.  So it's a little bit stricter.  And I'll show you an example in a minute just of a situation where a DSB is actually needed  because a dmb is not quite strict enough.  And the final one down here, ISB, is an instruction synchronization barrier.  And basically that causes the instruction pipeline  and any prefetch buffers to be flushed out and refilled from scratch.  And it's the kind of instruction that you would use after any operation  that alters the instruction context.  The most obvious example that occurs to everybody is self-modifying code.  That would be an example of the case where you need an ISB.  If you modify the code stream at runtime,  then you need to issue an ISB to force it all to be refetched.  I sometimes think that all engineers harbor a secret ambition  to write some self-modifying code and issue it to the public.  Relatively few of us ever succeed, thank goodness.  But it's actually very important in, for instance, operating system context switches  where one of the things that you're doing there is possibly changing the virtual physical address map.  And part of that, you know, you've changed the address map for the instruction side.  And you need to throw out all the prefetched instructions and get them back in again.  So here's the promised example of a situation where you actually do need a DSB.  This is a sequence that you might find at the end of an interrupt handler  where one of the last things you do here is write to a peripheral register  that clears the interrupt condition down.  And then this instruction here, RFE, that's returned from exception.  And that would return you back to your foreground process.  Obviously, very important that the interrupt is actually physically cleared in the system  before you execute the return from exception.  Otherwise, you might just get reinterrupted again.  Now, that might be spurious.  Your system might handle that gracefully, but it might not.  Even if it does handle it gracefully, what you've done is just wasted time handling a spurious interrupt.  So what you have to do here is put some kind of barrier in between the right to the peripheral register  and the return from exception.  And a DMB is not enough here because the RFE, in fact, the RFE here is not a memory access instruction  which is accessing the same memory domain and the same memory type as this one.  This is presumably accessing device memory.  This is accessing normal memory.  And even within the architecture, ordering between normal and device memory is actually not enforced.  Device accesses, they're enforced.  Normal accesses are enforced if you want them to be.  But between the two, we don't actually enforce them unless you stick a barrier in to do that.  So you do actually need a DSB here to physically stop the process of doing anything else at this point.  And physically make it sure that this instruction has completed, been issued,  been observed in the memory system or whatever before you actually carry on with returning from your exception.  So you need, in this case, say the DMB's stricter cousin, the DSB.  Now the requirement for barriers is actually very common.  And if you're writing any code that deals with memory map peripherals and very often deals with instruction context,  so interrupt contexts, then you should very seriously consider where and when you might need barriers.  Sometimes you need more than one.  Here's a couple of fairly complex examples.  The special situations where you carry out, say what the architecture calls context altering operations.  This is anything that changes the address map, either physically or virtually,  anything that enables or disables a coprocessor.  Again, that changes the instruction context.  And sometimes you have to combine these with other maintenance operations, which I'll show you in a second.  So there's a couple of examples here.  The first one is quite a common thing to do on older-arm systems, and you still see it on simple systems today.  And it involves using a custom peripheral out in the system called a remap peripheral.  What that does is it physically changes the address decode scheme at runtime.  You write to this peripheral and it will switch around the placement of some blocks of memory.  And the prime reason for wanting to do that, certainly on older-arm systems, is that the vector table is fixed at zero.  So it resets at zero.  So you have to have some non-volatile memory.  You're going to have some ROM down there at zero.  When your system is actually running, it's much nicer to have the vector table in RAM,  where you can change it and it's faster and it's volatile and you can install new handlers and all that stuff.  So actually, rather some systems don't let you relocate the vector table.  Even if they do, they only let you relocate it to one particular place and you might not have any RAM there.  So what you need to do is actually physically swap the ROM out and put it somewhere else and move some RAM down.  And you do that by altering the address decode map.  And you do that using this peripheral.  And you can see that after we've done that, you need to put two barriers in there.  One is a DSB, which says make sure that that remap operation has completed before I carry on.  Just stop right here.  Once that's completed, you carry on and you hit an instruction synchronization barrier.  And that says, I've just changed the system address map.  If you fetch any instructions ahead, if you've got any clever stuff like pre-predicting branches, forget it.  Throw it out and reload the pipeline in the new address context.  Now, you might think that a branch would be good enough for that because isn't that what branches do?  Don't they flush the pipeline out?  Well, yes, they do sometimes.  There's modern pipelines, they're very clever.  And in fact, without these barriers here, what it would do is it would get to this branch instruction and say, oh, that's an unconditional branch.  I can predict that statically now and it will throw the branch instruction away.  It actually won't bother executing it and it will fetch immediately after here this new code destination.  And it will carry straight on executing and the branch instruction will actually disappear.  So unless you force it to reload that branch instruction and re-execute it, by the time you get there, it may have gone.  So you do need the instruction synchronization barrier.  It does more than just what a branch does.  The second example down here is something that you might find in an operating system context switch where virtual memory is involved.  And the first instruction here, maybe that's updating some of the contents of the page tables that define our virtual address map.  So the first DSP, that ensures that this write has actually gone to memory.  And it ensures that the table is actually now updated, the next external memory, and we can carry on.  And then you've got this one here, TLB-IMVA.  I won't bother about all the syntax of it, but basically that invalidates the matching TLB entries.  The TLBs, if you're not familiar with those, are basically caches for page translations.  So we have to chuck all those out if we've changed one overlap to something that's cached.  Then we have to flush the branch predictor because the branch predictor also stores address information about branch destinations and branch locations.  So we have to flush all that out.  And then the DSP, one other effect of a DSP is it also stalls until maintenance operations have completed.  So these operations may take quite a long time to go through the TLB and chuck stuff out and to go and clear out the branch predictor cache.  So we have to stop there, wait for those to complete.  Then we need an ISB to re-synchronize the instruction context, and then finally we can carry on.  So you can see that, actually, in a space of five instructions, you've got three barriers.  All of them are actually necessary, and all of them actually have to be there.  And if you're the kind of guy that gets involved porting operating systems, then that's the kind of thing that you will have to be aware of and you'll have to think very carefully about.  Now, let's turn to a slightly different situation here.  This introduces a whole new ton of complications.  So far, we have only dealt with one processor.  But what if your system has two processors?  I've got another session tomorrow, interestingly enough, on writing multi-core software for ARM platforms, which we're going to a lot of this stuff in a lot more detail.  So if this wets your appetite, I do encourage you to come to that.  But anyway, here we are, two processors, P1 and P2, and a nice ordered neat and tidy view of the world.  If processor one updates variable X and then variable Y, and then processor two reads the two,  then there are three possible outcomes that are logically expected, if you like.  If processor two reads Y and X, and reads them in that order,  no, reads Y and X after this point here, then it will see the new value for X and the new value for Y.  If it reads them before this point, it'll see the old X and the old Y.  And if it reads them right in the middle here, it'll see the old Y and the new X.  It will never see the new Y and the old X.  And if your program ever sees that combination, then you can reasonably assume that something has actually gone wrong.  Now, unfortunately, in a modern multi-processing system, this assumption is no longer true.  And you do have to deal with the fact that you might see combinations of data values which are unexpected and which are logically impossible,  because somebody's changing your data.  So that simple little sequence there, and the simple question is two load instructions,  sorry, loading two variables from memory, right, and the load instruction to load A comes before the instruction to load B.  Very simple. You and I can see that.  Simple question, in which order are A and B physically fetched from memory?  Now, that should be easy to answer, shouldn't it?  Just look at the order in which the instructions are there.  But if you ignore pipeline effects for now, and we've seen what pipeline effects can do,  what if B is cached and A is not, right?  In that case, the memory system could return the value for B much quicker than the value for A.  And a typical ARM pipeline these days has a load store unit that can handle five or six outstanding memory transactions  and return them in any order, just whenever the memory system gives them back.  It'll pass them back onto the pipeline.  So what if they're both cacheable, but the load of A causes a cache miss?  Then the process is free because we do hit under miss completion.  The process is just free to carry on, try and load B while the line fill is happening to get hold of A.  So the value for B may well be returned long before the value for A.  So, and to remove the stalls, as we've seen, the pipeline may well reorder them at runtime anyway.  So already you can see exactly what behavior results in breaking that assumption on the previous slide.  Now, it's likely, say, that if you're running this on a single processor, none of that would matter.  By the time you get to the add instruction, which is when you need both of those values, the processor will have both of them.  And surely it doesn't matter in which order they were loaded.  But as we saw in the previous slide, what if another processor somewhere in the system is updating both of those variables  at the same time as we're trying to read them?  Right?  Those assumptions that we made on the previous slide, as we can see, are now broken.  And this second processor, if it was doing something slightly more complex than just adding the two values together,  would see a logically inconsistent or broken combination of those two values.  So we have to be able to cope with that.  Or, we have to be able to stop it happening.  And coping with something like this in the general case is not really possible and not really desirable in most cases.  So we kind of have to make sure it doesn't happen.  So how do we do that?  Several ways. One could be to make sure that we understand the effects of the cache and we get it out of the way.  Or ensure that we have some hardware for managing cache coherency or providing cache coherency.  Right?  And those are both subjects that I'm going to deal with tomorrow in the multi-core session.  But the other approach, which we'll look at now, is to make sure that we have a viable method for locking  or protecting critical sections like this where ordering of access by two different processing agents actually matters.  So you could write a very simple lock like that.  Now, from what you've seen in the last few slides, if you just take a moment to read that code,  you'll probably work out very quickly that that lock sequence won't actually work.  Well, to be precise, it's not guaranteed to work as intended.  And if there's one thing you have to have in a lock function, it has to work reliably every time.  Now, what you do is you need a mechanism that's going to enforce the ordering between two memory accesses,  specifically between a load and a store.  Now, if any of you have been around ARM technology or ARM processes for long enough,  you might remember the swap instructions. Anyone remember that?  Yay! Three of you. Good stuff.  Right. Now, the swap instruction, that basically carried out an atomic load and store,  and it swapped a register with memory location.  Now, that was exactly what you need here because it forced the load and store to happen in a guaranteed order  and in a guaranteed atomic sequence.  Now, the way we used to do that was the bus, the memory interface, had a lock signal on it.  And between the load and the store, the processor would basically flip the lock signal up,  and that would lock anybody else out of the bus and refuse to allow anyone to do anything with memory  while the processor was doing these two accesses.  Now, that worked very well.  And on a simple, you know, sort of single layer, single master bus system, yeah, it was kind of okay.  But in the bus systems that we use today, that's just not possible.  You can't, A, can't allow a single processor or single element to lock the bus for that length of time.  And B, it's very, very difficult to propagate that kind of lock information across complex bus matrices  and then through bridges and all kinds of other stuff.  It's very, very difficult to do.  So in architecture version 6, we defined a new method for doing this.  And in architecture version 7, we actually deleted the swap instruction.  So if you were very fond of it, I'm sorry.  The new instructions, there's a pair of instructions, load and store, exclusive.  And most modern architectures have a similar facility to this.  Load, acquire and store, release, very, very similar in other architectures.  And they all work basically the same way.  The way they work in ARM, that must be, the way they work in ARM is that the load exclusive instruction  loads from an address and then reserves it for exclusive access.  So basically it sets a little tag in the memory system that says, I'm accessing this.  Okay? And it sets a flag.  The store exclusive instruction stores to an address and returns you a successful status if the flag was still set.  Okay? It also then clears the reservation.  So you can kind of see where we're going here, that any number of agents in the system can use a load exclusive instruction  to load the current value of a lock. But only one of them will be able to do a subsequent successful store  because as soon as that's happened, all the others will try and the reservation's gone.  So they will all fail and they'll have to go back and, you know, back off and retry.  Now in ARM systems, this is something you need to consult the documentation of your platform quite carefully  because we don't actually mandate or design or ship the IP necessary in the memory system to implement this lock system.  It's very fundamentally integrated within the bus matrix.  And the bus matrix is something which is designed by the chip designer, not by the ARM architecture people.  So you find that these locks are sometimes placed in slightly different places and they behave in slightly different ways.  Their architectural behavior is constrained.  But for instance, they're free to recognize any number of outstanding locks from one upwards.  So you find some simple lock systems that only recognize one outstanding lock.  So if you have multiple lock variables in memory and you try and access all of them, that counts as one lock.  And as soon as you store to one of them, it unlocks all the rest.  Now that guarantees you correct behavior, but it's not best performance.  Other systems divide memory up into what we call a granule, the exclusives reservation granule, brilliant name.  And locks which are in separate granules have separate reservation flags.  So if you have many locks in your system, check the documentation.  And it may be worth you actually spreading the locks out so that they're in separate granules.  If your system supports separate reservations, then you may get better performance out of it.  For instance.  But I said two instructions. There are actually three on the slide here.  There's a third one which I should point out before we go on.  Clear exclusive.  And that basically clears any outstanding reservations in the system.  And that's the kind of thing that you might use in an operating system.  Context switch so that an outgoing process which has an appending lock or appending reservation doesn't generate a false positive when the new process comes in.  And that one might have appending lock as well.  And there's potential for confusion there.  So in context switch, you very often find this clear exclusive instruction just to clear everything up.  So a very simple example.  That's how you might build a simple lock structure using these instructions.  The lock sequence on the left. The unlock sequence is on the right.  And if you look at the code on the left, you can see there's a load exclusive.  A little bit lower down.  There's a store exclusive.  And the load exclusive loads the current value of the lock and it checks and it keeps reloading it until it's unlocked.  And then it goes down here and it tries to store to it to actually claim the lock by writing the locked value to it.  Now multiple agents, multiple processes, multiple threads might be trying to do this all at the same time.  And they'll eventually get through here. One of them will execute this store exclusive instruction.  And if you look at it, if you're familiar with our assembler, you'll see that it's a bit unusual.  Most stores only have one source register for the value you're going to store.  This one actually has two.  R1 is the value that we're going to store out.  And R2 comes back with the status.  And R2 comes back as zero if the lock, sorry, if the reservation has been cleared by the time you get here.  It comes back with one if the reservation is still there.  So if the reservation persists from here to here, then R2 will tell you you've succeeded.  You've got your lock off you go.  If somebody else has done a store to this lock location in between here and here, this store exclusive will fail.  And you'll go around and try again or back off or do whatever your OS tells you to do.  The unlock sequence is trivial because a standard store instruction clears any outstanding reservations on the location as soon as it does it.  So you just have to write the unlock value and that automatically clears the reservation and other people can get in.  Now then, we're going to have a summary time. I have eight minutes left.  I'm kind of conscious that we've only had time to touch on a few of the dragons that exist in this area of embedded development.  There's a huge amount of other stuff and other knowledge and other experience that we could go through.  But just to build my way of summary, I just want to summarize the different properties of memory accesses that come into play here.  And the things that you need to worry about when you're working on a complex embedded system.  First of all, memory ordering. If you care that memory accesses must occur in the order that you've written them,  then you need to start putting barriers in to make sure that happens.  And you need to make sure that you might use locks if necessary to protect critical sections.  And you need to make sure that peripheral memory is marked as device.  Cardinality. This is if I have written three load instructions, I want three read accesses, right?  The cardinality must match. And there, you need to get rid of things like speculative access on both the data side and the instruction side.  Arm cores do both these days. And the way you do that is by declaring sensitive memory as device memory and that bans speculative access in those regions of memory.  Volatility. Yeah, that's the most common one that we're all aware of.  A memory location may change when you or the compiler or the machine are not looking.  And in this case, yes, you need to use the volatile keyword and we all know that.  Completion. Another one. I need to know when this access has completed before you move on.  Again, use barriers for that to make sure that subsequent instructions are not executed.  Remember, you've got two flavors of that. dmb, dsb. dsb is stricter than dmb.  And in order to stop before moving on, you would use a barrier for that.  Observability is by far the most complex one. It's similar to completion, but it's subtly different.  Now, an access completes when it kind of leaves our sphere of influence.  So when it leaves the kind of local story around my pipeline, my processor, my bus interface, my write buffer,  as soon as an access goes beyond that, it's completed as far as we're concerned.  But that doesn't necessarily mean that other parts of the system can see the result of that access.  And you do need to bring other context into play there.  You do need to consider perhaps cache management. You do need to consider, you know, where memory is being shared  and how far out of the bus system that memory is, whether it's beyond caches or beyond write buffers and so on.  So observability is by far the most complex. And again, I'll deal with some of those issues tomorrow.  And finally, atomicity. Atomicity is a really, really fascinating subject.  And atomicity is the concept of a sequence of memory accesses must be carried out without anything else getting in the way.  So, you know, without any other accesses interleaving in between, for instance, without the bus being granted to anyone else  during that particular sequence. And this is really important when you're dealing with shared memory,  memory map peripherals and all kinds of things. So critical lock structures are one way that you can guarantee this.  But it gets even more complicated when you look right down at the bus level on a complex pipeline processor  or placed with a complex memory interface because you need to look very carefully, if it matters to you,  at what the architecture says about atomicity.  The wonderful thing about the ARM architecture is all processors that have ARM on the lid have to conform with it.  But you say, you find, for instance, all single word-sized memory accesses are guaranteed to be atomic.  So if you write to a 32-bit word, the architecture guarantees you that that operation, that bus transaction, is atomic.  It has to be. Otherwise, that processor is not ARM compliant.  And we will get out our big stick and our contract and go and sue them, beat them around the head and make them re-spin the chip and do it again.  What about things like load and store multiple instructions, if you remember those?  Are they atomic? Well, sometimes they are and sometimes they're not.  You need to go and check the architecture very, very carefully and find out.  What about accesses to double words, half words?  Again, sometimes they are and sometimes they're not.  Depends on what kind of memory you're accessing and also depends on the alignment of the address that you're accessing.  Unaligned accesses are generally not guaranteed to be atomic, generally.  But again, there's a huge amount in here and it has its very own completely incomprehensible chapter in the architecture efforts manual,  which I would encourage you to go and have a look at if you want to go to sleep one evening.  Anyway, so many questions, so little time, we just don't have time to go to any of that stuff.  But hopefully what I've managed to get over to you is that there are lots of cases where the hardware and to some extent the compiler,  but especially the hardware, do things that you need to understand.  And you need to understand when and why and how these things happen to work out whether you care.  And if you do care, then you need to know what to do about that. Memory types and barriers and locks are the three main techniques we used to do that.  Just by way of closing on that theme, on November the 26th, 1922, Howard Carter opened just a little chink in the top corner of the door into Toot & Commune's burial chamber.  And he kind of looked through the door and Lord Canavan, his backer, was kind of standing behind him, desperate to try and see.  But it was only his tiny hole in the door and what he was doing was holding the candle up to it and just trying to see what he could see.  And he wrote this in his diary afterwards. He says,  As my eyes grew accustomed to the light, details of the room within emerged slowly from the mist. Strange animals, statues and gold, everywhere the glint of gold. And for the moment, it must have seemed an eternity to the other one standing by.  I was struck dumb with amazement. And when Lord Canavan, unable to stand the suspense any longer, said anxiously, can you see anything?  It was all I could do to get out the words, yes, wonderful things.  And I kind of feel a little bit like that today. We kind of just peeled back a little chink and held a candle through the crack. And you can see some great stuff in here.  But we do not have a chance to see it all. So I'm going to leave you with two literary quotations because I like to inject a bit of culture into our uncultured industry sometimes.  This is from Marcel Praust's, Al-Récherche du Temp-el-Du, Remembrance of Things Past is not necessarily the remembrance of things as they were.  And just as human memory is infallible, foolable and imperfect, so sometimes the memory systems that we work within our development work don't quite behave the way you want them to.  But that's the literary quote, the pretentious one. I much prefer this one. This is the Red Queen said to Alice in the Looking Boss.  It's a poor kind of memory that only works backwards. And sometimes it seems like our memory systems work backwards too.  Anyway, I hope that was useful and a kind of introduction to all the stuff that's in here.  And I encourage you to come to session tomorrow. We'll unpack some of this a little bit more in the context of multi-core processing and MP core platforms.  I am told to encourage you to vote using the buttons at the back. If you've enjoyed this and learnt something new, then please bash the green button.  If I've left you with the impression that you need to know quite a lot more, yes, again, please bash the green button.  And then come and talk to me afterwards. And I'll tell you how we can fix that. But thanks very much.  Thank you.
Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_0_6887.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_6888_9731.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_9732_12791.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_12792_15743.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_15744_16679.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_16680_16739.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_16740_17051.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_17052_21179.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_21180_22331.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_22332_25007.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_25008_27071.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_27072_30527.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_30528_35819.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_35820_43307.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_43308_49559.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_49560_52559.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_52560_52835.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_52836_54023.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_54024_59123.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_59124_61499.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_61500_65939.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_65940_68843.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_68844_73547.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_73548_76139.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76140_76187.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76188_76235.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76236_76283.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76284_76331.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76332_76379.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76380_76427.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76428_76475.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76476_76523.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76524_76571.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76572_76619.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76620_76667.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76668_76715.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76716_76763.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76764_76811.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76812_76859.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76860_76907.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76908_76955.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_76956_77003.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77004_77051.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77052_77099.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77100_77147.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77148_77195.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77196_77243.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77244_77291.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77292_77339.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77340_77387.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77388_77435.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_77436_78119.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_78120_78407.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_78408_78923.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_78924_80279.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_80280_83363.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_83364_83855.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_83856_86003.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86004_86051.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86052_86099.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86100_86147.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86148_86207.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86208_86255.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86256_86327.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86328_86387.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86388_86435.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86436_86507.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86508_86567.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86568_86675.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86676_86735.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_86736_87935.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_87936_88019.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_88020_88151.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_88152_88199.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_88200_88367.png Memory_Access_Ordering_in_Complex_Embedded_Systems_-_Chris_Shore_ORIGINAL_DOWNLOAD_88368_89882.png
Okay, let's make a start. Bang on time. My name is Chris Shaw. I work for a company called Arm. How many of you have heard of Arm? Oh, that's so much of a better answer. I would have got 15 years ago when I first started working for Arm, when nobody had ever heard of it. How many of you are actually using Arm-based platforms at the moment? Actually writing code for them. Good. That's even more encouraging. I'm really pleased about that. The one thing you need to know about me, apart from the fact that I run Arm's customer training department and have done for just over 14 years now, is that my hearing is terrible. We're hearing aids, but they don't fix everything. So if you want to ask questions, it's probably best to catch me outside afterwards, rather than try and ask them in the kind of open class. So just save the questions for afterwards. I'll be more than happy to hang around for as long as necessary to deal with any issues that you have. It's kind of fascinating to be here, right at the beginning, I think, of embedded content coming into this particular conference, which by the way is fantastically organized. It's one of the best I've ever spoken at. Congratulations to the organizers. Because although the other presentations that I've been at so far this week have been right up in the cloud, they've been way up at high level, abstract, high level languages and so on, this is something completely different. This is way down at ground level, if not about 10 feet below ground level, right down in the weeds of programming for very sort of complex, but deeply embedded systems. A little bit about the genesis of this presentation. I don't know how many of you are members of LinkedIn, probably most of you I am, but do you sort of frequent the forums that go with LinkedIn? Most of the time they're full of students trying to get people to do their homework and asking stupid questions, but every now and then you get a really good question and a really, really fascinating discussion. This presentation came out of a discussion that happened about 18 months to two years ago on the embedded forum on LinkedIn. It started very innocently with a cross post from an RTOS group of a really simple and innocent question. It was this, is there any guarantee that two sequential writes to two separate volatile variables will be executed in the same order they appear in the code? Simple question, very simple. Now the discussion raged for weeks and it reached hundreds of posts and we had RTOS people, chip designers, C standards experts, language experts, programmers, compiler writers, system architects, everybody. Everybody pitched in on this one because everybody had a view on it. But down towards the end you could see the realisation starting to dawn on people that actually the answer to that question, which you really want to be yes, don't you? The answer to that question actually is no. And that is real shock to some people, especially if you're programming on an embedded system, to find that that question is not true, is a real shock. So it prompted me to look a bit further into the issues that are kind of buried in that question and a lot of other issues it touches on. And a lot of them I think are really completely unknown to a lot of people who are developing in the embedded arena and people who have been developing there for a long time. And we really have to get to grips with this because the embedded world has kind of moved on a long way. Consider for instance, just first of all, that question, it executed in the same order as they appear in the code. Now just think about that word order. What does it mean? Does it mean the instructions are fetched in the same order, issued to the pipeline in the same order, generate their addresses in the same order, get issued to the load store unit in the same order, does the rights get issued from the core to the bus interface in the same order, what about the order in which those rights reach the memory system, what about the order they enter and leave a write buffer, what about the observability by an external agent. All of those are aspects of the order in which two memory accesses occur and all of them are different. And all of them can potentially be changed and kind of come into play when you try to answer that question. It's a huge issue when we don't really have time to do more than just really touch on it today in a very, very brief way. But first of all, I'm going to take you on a little trip down my particular memory lane. They say nostalgia is not what it used to be, neither is our industry. It changes faster than almost any other industry on earth and embedded has gone through huge transformations in the last five years, in the last ten years, even the last five. Okay, it's changed a lot for the better. I started out writing embedded software just about 30 years ago. I guess some of you have probably been at the game longer than I have. You're going to have memories of what it was like too. But the first project I worked on after graduating from university, we were developing code for a radio network switch, operator console, it was a touchscreen thing, and it ran on a custom board which we built with a 6809 processor from Motorola, and we cross-compiled the code on an IBM PCXT. Remember those? Yep. It had twin floppy drives, so you put your source code on one disk and the editor on the other, and you put them both in and you made your edits. And when you finished that, you took the editor disk out and put the compiler disk in, because you couldn't put them both on the same disk because the disk wasn't big enough, and then you compiled your code, and then you took that out and you put the ROM programmer disk in and you transferred the code into an eProm, physically into an eProm, which you had to cook under a UV light to erase the previous contents before you put the new one in, and then you physically plugged that into the board. And the company couldn't afford an emulator, so we had to debug everything using printf and a serial port. And you basically just hit reset and see what happens. And if it doesn't work, you have to go through the whole disk swappy thing and start all over again. A real, sort of, horrendous way to have to develop code. I bet you've got stories of your own. So things like that have got so much better. We now have on-chip debug over JTAC, so you don't even need to shell out for an emulator anymore. So, yeah, in lots of ways, embedded development, development in general, has got an awful lot easier. But think about the systems that we used to use. They used to be so simple. Some low-end systems still are, but even the high-end systems we used are very simple, because everything conformed to what you call the sequential execution model. But systems were simple. The buses were simple. They were single-layer. They were dumb. They were in order. Right buffers were a twinkle in a designer's eye. And unless you were into really, sort of, wacky stuff like DMA, there was only one thing that could control the bus, and that was the processor. So the processor really was in charge of everything that went on to memory. And if you knew what the processor was doing, you knew what memory was doing. There was nothing else you needed to know. Inside the processor, yeah, that was all nice and neat and tidy, too. With just very simple pipelines or even no pipelines at all, all instructions were issued in sequence, executed in sequence, and retired in sequence. Nice and easy. And all instructions executed to completion, including memory effects, before the next one even got to the execute stage. So if an instruction wrote something to memory, that was all completed before you even started on the next instruction. Beautifully, nice, and sequential. Every instruction was essentially an independent unit. Now, that sequential execution model applied at pretty much every level in the system. Instruction fetches, memory accesses, internal control, peripheral action. It was very nice and predictable, and life was very simple. And you really only needed to know two things to write correctly functioning code for such a system. Two things about memory, anyway. One was that sometimes if you did an action on a peripheral, sometimes that took a bit of time to complete. So you might have to pull for its completion or give yourself an interrupt later on to check that it completed. And the second was you had to tell the compiler that some memory locations in your system were not well behaved. In general, that was memory mapped onto peripherals, and you had to tell the compiler that sometimes they change when you're not looking. And that was the prime mover behind that volatile keyword that I'm sure you will know and love. And volatile was really kind of all that you needed. They just told the compiler that certain memory locations change when you weren't looking. And that kind of covered memory map peripherals. It covered global variables that might get changed by an interrupt handler. And the very simple example on the slide, you can see what it does is it prevents the compiler from caching the results from these two loads. It actually has to do two loads from the same memory location, one after the other, because what you're telling the compiler is that register, that location may change in between these two loads. So I really, really want you to do this twice. Now you can see actually, this is the ARM compiler. You can see what the ARM compiler has done here is actually realized that reading the same memory location twice is completely stupid because it's always going to be the same. So it's actually optimized the loads and the compare away completely and just returned you to anyway. So to stop the compiler doing that, which is clever but misguided, you use the volatile keyword. And the key thing about this is it only affects the behavior of the compiler. If you declare a variable as volatile, that's not really visible to the processor at all at runtime. It's not visible to any other part of the system either. It only has an effect on code generation. And if the system doesn't behave the way the compiler expects it to, or the way you have told the compiler it's going to behave, then you're going to have potential problems. Now unfortunately, that is exactly what complex modern systems do. Because they try to be so clever, because they try to increase performance using all kinds of execution tricks in hardware, they do sometimes end up not doing quite what the compiler expects them to do. And memory access ordering is one very obvious area where that becomes very, very visible. So that's simple in order predictable deterministic machine that I had two slides ago. Well, modern systems don't look like that anymore. They tend to look like this. This is a typical, very typical modern embedded system. If anywhere in the previous presentation which Espen just gave on FPGAs, this is the kind of system you'll find in the latest Zinc FPGA from Xilinx. It has a quad core A53 and it has a separate co-processor, a separate processor for handling real-time acceleration, and it has a GPU. And all of this is available in an embedded FPGA today. Multiple processors, maybe in a coherent cluster, sharing a cache, multi-layer bus, multi-master bus, intelligent peripherals, bus bridges, and all kinds of things. And semi-autonomous processing units that you've got to worry about. And all of this is basically what you would find inside the guts of a mobile phone today. It's simple though it seems. And in a system like this, say you've got to deal with things like multi-core processors, they might be running asymmetric or symmetric multi-threaded code. You've got to deal with very complex processor execution pipelines. And those pipelines, in order to maximize throughput of instructions and throughput of data, they do all kinds of things. They speculatively prefetch, they speculatively execute, they try and predict branches ahead of time and speculatively fetch branch destinations. They multi-issue, they issue out of order, and they complete out of order. And they do all kinds of nasty things. You might have multiple levels of cache in your old traditional system. You may not have had cache at all. In a typical sort of phone standard system of today, you probably got three levels of cache. And that level one is probably going to be a coherent cache shared between multiple processors. Level two is going to be shared possibly between multiple clusters of processors. And level three will be out on the bus. Where is your data? Which cache is it in? Keeping track of that is quite difficult. Even when an item, say, is in a particular cache, you might have cache coherency management hardware. We have that on ARM systems, which automatically ensures that at least some subset of the system components have access to the latest value. But you've got to track which subset of components that is. Memory interfaces, they also, they're very clever too. They try and optimize bus traffic to by reducing the number of bus transactions that actually go on. So two writes to the same location. The bus interface might look at that and say, I was no point in doing the first one. I'll just do the second one because there's no point in writing something that immediately overwriting it. Is there? Well, there might be. But for the bus interface, we'll just decide no. Or a location that's just been read, it might cache that in a fill buffer, in an explicit cache, in a transfer buffer somewhere. Write buffers, try and amalgamate accesses. So to write to two adjacent half words, for instance, the right buffer might decide, oh, well, I'll just amalgamate those and do a single one. Write because that's a simpler transaction. It's quicker, uses less energy, and it minimizes the time that I'm occupying the bus. All of this stuff goes on. And most of it is there to help you. Most of it does help you. It helps massively. But sometimes it gets in the way. So the key is knowing when it might happen, knowing what might happen, and knowing what you have to do as a software engineer to kind of just control it to the level that you want to control it. And compilers have got a lot cleverer too. I've just so far been talking about the hardware, but I've just been talking about the compilers are an interesting subject as well. So first of all, let's look at volatility, this volatile keyword. And that simple piece of code declares two hardware registers, control and status, because they're memory mapped, are good little programmers, declared them both as volatile. And what he wants to ensure here is that the device is reset by writing one to the control register here before we start reading stuff out of it. Okay. He wants to be sure that those two things happen in order. Now, does declaring those two items as volatile guarantee that that is the case? Does it guarantee that the peripheral sitting out in the memory system sees this right before it sees that read? Answer? You might not be too surprised. No, it doesn't. And there's at least two reasons for that. There may be others, but there's at least two. And the first reason comes down to the compiler. And the compiler can reorder memory accesses as long as program behavior is not affected. Okay. Now that's program behavior in the view of the compiler. Now, if the compiler was to exchange the accesses to control and status, as far as it's concerned, logical program behavior hasn't changed. There's no data dependencies, no address dependencies between these two accesses. So why shouldn't it switch them over? Either at parsing time or at code generation time. Answer? It can. And sometimes it will. Actually, it's worse than that. Some compilers will and some compilers won't. Because the C standard is actually deliberately silent on this. And it leaves it up to compiler implementers to choose how they behave in that particular situation with that, with the accesses to volatile variables. So the guy who writes the compiler can actually make it up on this one. And you can't rely on what decision he or she has taken. Now, the second reason is down to the hardware. The right to the control register. Maybe that goes through a write buffer. It's perfectly reasonable for it to do that. And that write buffer might delay it by any length of time. And the read from status might be satisfied by a cache. Okay. We can reasonably stop that happening since this is a peripheral. And meaning that it's much quicker to read status than it is to write the control by. Now, as far as the processors concerned, say, they're independent variables. There's no visible data dependencies between the two. So they can be passed through the pipeline in pretty much any order the processor likes. So that code provides no guarantee that the peripheral will be accessed correctly, which is really quite depressing. Even more depressing when you realize that, say, the problem is partly in the compiler, partly in the hardware, and partly somewhere in between the two. I'll just remind you before we go on, say, the other use of the volatile keyword. And this is here we're declaring status. We would declare status as a volatile variable because it's used in the foreground and also in the background. It's used in an interrupt handler as well as the main program. So it may get changed in this interrupt handler while the main program is sort of executing in the foreground. So we have to declare it as volatile so the compiler doesn't cache it in that foreground main loop. If it does, then our program quite simply wouldn't work. So I'm hoping you're familiar with both of these cases, but they illustrate an important point. And this is kind of where I'm going. Neither the compiler nor the hardware have enough knowledge of what your program is intended to do to be able to guarantee that your program will do the right thing. Okay? So certain memory accesses have side effects and certain memory accesses may be linked to each other, like control and status. They're two registers in the same peripheral. Now, they are linked to each other, but in a way that the processor can't see. And also in a way that the compiler can't see either. And in this case, they're desperate desire to run your code as quickly as possible. Both the compiler and the hardware make all kinds of optimizations that affect the function in this situation. Because they're both missing key information and you as the programmer have that information and you have to pass it on. Let's just, again, look at the superscaler. Look at interesting pipelines. This is a rough representation of the pipeline that we used in the Army 11 about 10 years ago. There's one stage missing. There's a fetch stage on the left-hand side. It's what, it's a six-stage pipeline if you add the fetch stage on. The compiler, the pipeline that we use in Cortex-A57 has 15 stages. All right? So pipelines have moved on a little bit since the days that you and I were at college. They're a lot longer. They are superscaler, multi-issue, multiple execution units, out-of-order execution, speculative execution, out-of-order completion. And these very quickly baffle you, to be honest. And it's very difficult and almost impossible to start trying to analyze them by hand or in your head. I'm going to stop. Just make one, one very important point before I carry on. I keep saying that the compiler of the hardware might not do the right thing. Okay? Let's be careful of exactly what we mean by that. I don't mean to say that they don't execute instructions properly or that compilers carry unsafe optimizations. They don't. They always do what you tell them to do. Okay? Precisely. And that sequential execution model still holds, but it only holds at the local level. This processor executing this instruction stream connected to that bus interface. Okay? It has to. All the standards require that that sequential execution model has to hold, but only at that level, only at that very, very localized level. And where that kind of breaks down, and it breaks down spectacularly, is where vital information about things outside that context needs to be given to the processor or given to the compiler, like memory locations behaving in a non-standard way, or a memory region being accessed by an independent processing element, or two elements accessing the same cache, for instance. That information, say the compiler and the hardware just don't have that. They really, really, really do try to do the right thing. But sometimes they need that extra information to do it. Okay? Let's go down just kind of another level and look at maybe what might be happening at pipeline level, just to illustrate this. This is a simple example of how a modern pipeline might affect directly the order that instructions get executed, specifically the order that memory accesses occur. Okay? Remember, what the pipeline is trying to do is maximize instruction throughput. It's trying to help. Okay? So supposing your source code results in that sequence of instructions on the left. Now, if you put that through a simple in-order processor, and there are still some of those around, you might get the sequence in the middle. The instructions are issued into the pipeline in the order that they occur in the program. You can see, no change there. And subject to things like write buffers and caches, which are kind of outside the pipeline, you can reasonably safely make the assumption that the order, the memory accesses happen specifically the store will occur before the load. Okay? An out-of-order, super-scaler pipeline might actually, when it's executing these instructions, execute them in the sequence on the right. And it's done this to hide the latency of the load which is caused to stall here, and the latency of the multiply which is caused to stall a bit further up. And to hide those and basically bleed the stalls out of the instruction sequence, it's promoted the load above the store, which is given the multiply latency time to happen, and it's given the load use latency time to happen behind other instructions. Now, it is entirely free to do this. Okay? Entirely free. And this is a concrete example, if you like, of that first slide we started with, the control register and the status register. This is a concrete example of how the pipeline might reverse those two accesses at runtime. Now, there's three kind of key things to note about this. The first, as I say, is the pipeline is completely free to do this, and you actually want it to do it. Because doing this increases the performance of your program significantly. And if you turned all this stuff off, which you can't, your program would perform significantly worse. Number two, you can't predict it reliably. Okay? Because a lot of this depends on instruction context at runtime. It depends on the context and usage of particular registers at runtime. It may even depend on things like the alignment in memory of individual instructions. Okay? And you can't reliably predict that by hand. You can't predict it with a static analysis. You only find out whether this is going to happen when you actually put the instructions through the processor and see what comes out at the other end. Because all of this is happening in real time. So, and the third thing, you need this behavior. You really do need it because you need the performance that it gives you. And certainly on ARM processors, we don't give you the ability to turn stuff like this off. We don't want you turning it off because it's what gives you the performance that you need. So, moving on, we've established, say, that there's key information about the system, about how it behaves and how the code and the processor need to deal with that, which we possess and we have to pass on to the system. We have to pass it on in such a way that the compiler and the hardware can actually start to behave the right way. Now, from here on in, I'm going to use explicit ARM examples. I mean, these examples, okay, they're ARM assembly instructions, but they could be illustrated using pretty much any architecture. I make no apology from now on that I'm going to use explicit ARM systems, for example, because A, that's what I know about, and B, I work for ARM, so damn it, I'm going to talk about it. Okay, the first concept I need to introduce you to is memory types. So, we know not all memory behaves the same way. We know that, we've established it. Now, most of it does. The vast majority of memory in your system does, and that's the kind of memory that you put your code in, that you put your stack in, your heap and so on. That behaves normally, but some of it doesn't. Some of it is mapped to peripheral registers, shared memory, DMA memory, frame buffers, and all kinds of interesting, tricky things. And we kind of need a way to get that information about these two different kinds of memory to the system in some way so that it can take account of that. Since ARMv6, ARM11 about 10 years ago, the ARM architecture has sort of recognized this concept of memory types. Every addressable part of your address map must be given a type. That's mandatory, okay, and you have to do that. And the system needs to know what that type is. I'll tell you how you do that a little bit later on. So, the vast majority of memory in a system is normal memory, what we call normal, because it behaves normally. Now, it's well-behaved. And the compiler, sorry, the compiler of the machine is free to make all kinds of assumptions about that and make all kinds of optimizations. So, for instance, because normal memory does not have side effects on any access, we permit speculative access, for instance. So, on data side and instruction side, we allow it to merge, reorder, resize, repeat, cache, and buffer, all memory accesses, okay? Now, that's a serious amount of operations. Provided that there are no observable dependencies within a sequence of accesses to normal memory, the processor can do any of that, okay? So, it will observe data dependencies, it will observe address dependencies, and it will reserve resource dependencies. But apart from that, it's free to do all of this stuff, and it's a huge positive effect on performance. ARM architecture actually requires these days that you have to put your instructions in normal memory, which is a bit sad to those of us who remember the fun of executing code out of FIFOs. You can't do that anymore, sorry about that. But the main other kind of memory is device memory, and that's memory map peripherals and other interesting things. Now, the key thing about these accesses is they have side effects, and those side effects may or may not be observable to the processor. So, all that neat stuff that we allowed for normal memory is not and cannot be allowed in device memory. You can't, for instance, ever allow the processor to carry out speculative accesses to device memory. You do not want it reading your peripheral registers without explicit program instruction to do so, because those reads have side effects. You will say, because some devices are size sensitive, you can't allow it to merge and resize accesses. That's safe in normal memory. It's not with peripherals. And you can't allow it to repeat accesses or delete accesses either. And with ARM systems, we do allow peripheral accesses to go through a right buffer when you're writing to them, but we do not allow peripheral accesses to be cached. Okay, that's kind of obvious. There is a third kind right at the bottom here called strongly-ordered memory, which is nasty stuff. That's very strict and really, really, very nasty, and it has incredibly strict ordering rules. And to be honest, nobody actually, even in the architecture team at ARM, really seems certain whether anybody ever uses that and needs it. So, we actually deprecated it in the last revision of the architecture, and it's been deleted in the current revision of the architecture. So, if you see stuff about strongly-ordered memory, in most cases, you can safely ignore that. It doesn't exist anymore. So, how does the system get that information? It's important to realize that we provide this information to the hardware, right? And it's the hardware that uses it. This information is not provided to the compiler. There's no semantics within C, for instance, to allow you to do that. And the compiler has no knowledge of any of this stuff. But in ARM systems, you program normal and device, all kinds of other memory attributes. You program that into either a memory management unit on a virtual memory system or a memory protection unit on a real-time system. And at runtime, the memory interface uses that information. It reads it out of the memory management unit, out of the memory protection unit, and it uses that to control and govern how it accesses particular regions of memory. Some very small microcontrollers, the Cortex-M systems, some of those don't have an MPU, a memory protection unit. And in that case, they actually have an architecturally fixed memory map. So, you know, there will be a region which is designated for code and is required to be normal and is fixed that way in the architecture. There is a region for peripherals, and that's device memory and so on. And that's documented in the architecture. The second thing I've got to introduce you to is the concept of memory barriers. Now, you might have come across these in other architectures. If heaven forbid, you've programmed on anything else in your life other than ARM. Sometimes they're called fences, synchronization instructions. PowerPC, for instance, has the fantastically named EIEIO instruction, which stands for Enforce in Order Execution of IO. I really hope that the architect's had a fantastic session in the bar the day they wrote that one, because opportunities like that don't come up very often in our industry. But, say, like other architectures, ARM has a set of barrier instructions, and you use these at specific points in your code sequence where the sequence of memory operations really matters, and you want it to matter. So, at the top of the slide there, that's the example that we used just a few slides ago to illustrate reordering in that superscalar processor. And in that example, we saw it was possible for the load in the store actually to be switched round at runtime. And there's kind of no easy, efficient way you can fix that within the syntax of C, as understood by the compiler. So what you have to do is insert a memory barrier. There it is, dmb. That's a memory barrier instruction. And what that does, it ensures that the memory access instructions complete in the order in which they appear in the instruction stream. Now, it doesn't stop the processor from doing other stuff around those instructions, provided the memory access ordering is observed. So if there were other instructions which didn't access memory in this gap here between the dmb and the load, then the core would quite happily carry on and do those ads, multipliers, all kinds of other stuff. But the one thing it can't do is initiate this load before that store is completed. Okay? And the core is required to do that to be architecturally compliant. Now, that involves making sure that write buffers are flushed, for instance. It doesn't involve flushing data out of caches. You have to manage that yourself. But the point of the barrier, say, is that it enforces those two memory accesses, the load and the store, there to happen in the intended order in program order. And in a high-level language like C, for instance, you would insert that either using a bit of inline assembler or much better still using an intrinsic function. There is an underscore underscore dmb intrinsic function. And the nice thing about doing it with an intrinsic function is that the C compiler treats that as a sequence point and it handily restricts some of the optimization that the compiler can carry out across the intrinsic function. Very nice. There are two other barrier instructions we have. A DSB, which is a little bit stricter. And what the DSB does, it's called a data synchronization barrier, and it actually stops the processor. It would halt the processor dead at this point until all the memory accesses before this point have completed. And at that point, it would then carry on. So it's a little bit stricter. And I'll show you an example in a minute just of a situation where a DSB is actually needed because a dmb is not quite strict enough. And the final one down here, ISB, is an instruction synchronization barrier. And basically that causes the instruction pipeline and any prefetch buffers to be flushed out and refilled from scratch. And it's the kind of instruction that you would use after any operation that alters the instruction context. The most obvious example that occurs to everybody is self-modifying code. That would be an example of the case where you need an ISB. If you modify the code stream at runtime, then you need to issue an ISB to force it all to be refetched. I sometimes think that all engineers harbor a secret ambition to write some self-modifying code and issue it to the public. Relatively few of us ever succeed, thank goodness. But it's actually very important in, for instance, operating system context switches where one of the things that you're doing there is possibly changing the virtual physical address map. And part of that, you know, you've changed the address map for the instruction side. And you need to throw out all the prefetched instructions and get them back in again. So here's the promised example of a situation where you actually do need a DSB. This is a sequence that you might find at the end of an interrupt handler where one of the last things you do here is write to a peripheral register that clears the interrupt condition down. And then this instruction here, RFE, that's returned from exception. And that would return you back to your foreground process. Obviously, very important that the interrupt is actually physically cleared in the system before you execute the return from exception. Otherwise, you might just get reinterrupted again. Now, that might be spurious. Your system might handle that gracefully, but it might not. Even if it does handle it gracefully, what you've done is just wasted time handling a spurious interrupt. So what you have to do here is put some kind of barrier in between the right to the peripheral register and the return from exception. And a DMB is not enough here because the RFE, in fact, the RFE here is not a memory access instruction which is accessing the same memory domain and the same memory type as this one. This is presumably accessing device memory. This is accessing normal memory. And even within the architecture, ordering between normal and device memory is actually not enforced. Device accesses, they're enforced. Normal accesses are enforced if you want them to be. But between the two, we don't actually enforce them unless you stick a barrier in to do that. So you do actually need a DSB here to physically stop the process of doing anything else at this point. And physically make it sure that this instruction has completed, been issued, been observed in the memory system or whatever before you actually carry on with returning from your exception. So you need, in this case, say the DMB's stricter cousin, the DSB. Now the requirement for barriers is actually very common. And if you're writing any code that deals with memory map peripherals and very often deals with instruction context, so interrupt contexts, then you should very seriously consider where and when you might need barriers. Sometimes you need more than one. Here's a couple of fairly complex examples. The special situations where you carry out, say what the architecture calls context altering operations. This is anything that changes the address map, either physically or virtually, anything that enables or disables a coprocessor. Again, that changes the instruction context. And sometimes you have to combine these with other maintenance operations, which I'll show you in a second. So there's a couple of examples here. The first one is quite a common thing to do on older-arm systems, and you still see it on simple systems today. And it involves using a custom peripheral out in the system called a remap peripheral. What that does is it physically changes the address decode scheme at runtime. You write to this peripheral and it will switch around the placement of some blocks of memory. And the prime reason for wanting to do that, certainly on older-arm systems, is that the vector table is fixed at zero. So it resets at zero. So you have to have some non-volatile memory. You're going to have some ROM down there at zero. When your system is actually running, it's much nicer to have the vector table in RAM, where you can change it and it's faster and it's volatile and you can install new handlers and all that stuff. So actually, rather some systems don't let you relocate the vector table. Even if they do, they only let you relocate it to one particular place and you might not have any RAM there. So what you need to do is actually physically swap the ROM out and put it somewhere else and move some RAM down. And you do that by altering the address decode map. And you do that using this peripheral. And you can see that after we've done that, you need to put two barriers in there. One is a DSB, which says make sure that that remap operation has completed before I carry on. Just stop right here. Once that's completed, you carry on and you hit an instruction synchronization barrier. And that says, I've just changed the system address map. If you fetch any instructions ahead, if you've got any clever stuff like pre-predicting branches, forget it. Throw it out and reload the pipeline in the new address context. Now, you might think that a branch would be good enough for that because isn't that what branches do? Don't they flush the pipeline out? Well, yes, they do sometimes. There's modern pipelines, they're very clever. And in fact, without these barriers here, what it would do is it would get to this branch instruction and say, oh, that's an unconditional branch. I can predict that statically now and it will throw the branch instruction away. It actually won't bother executing it and it will fetch immediately after here this new code destination. And it will carry straight on executing and the branch instruction will actually disappear. So unless you force it to reload that branch instruction and re-execute it, by the time you get there, it may have gone. So you do need the instruction synchronization barrier. It does more than just what a branch does. The second example down here is something that you might find in an operating system context switch where virtual memory is involved. And the first instruction here, maybe that's updating some of the contents of the page tables that define our virtual address map. So the first DSP, that ensures that this write has actually gone to memory. And it ensures that the table is actually now updated, the next external memory, and we can carry on. And then you've got this one here, TLB-IMVA. I won't bother about all the syntax of it, but basically that invalidates the matching TLB entries. The TLBs, if you're not familiar with those, are basically caches for page translations. So we have to chuck all those out if we've changed one overlap to something that's cached. Then we have to flush the branch predictor because the branch predictor also stores address information about branch destinations and branch locations. So we have to flush all that out. And then the DSP, one other effect of a DSP is it also stalls until maintenance operations have completed. So these operations may take quite a long time to go through the TLB and chuck stuff out and to go and clear out the branch predictor cache. So we have to stop there, wait for those to complete. Then we need an ISB to re-synchronize the instruction context, and then finally we can carry on. So you can see that, actually, in a space of five instructions, you've got three barriers. All of them are actually necessary, and all of them actually have to be there. And if you're the kind of guy that gets involved porting operating systems, then that's the kind of thing that you will have to be aware of and you'll have to think very carefully about. Now, let's turn to a slightly different situation here. This introduces a whole new ton of complications. So far, we have only dealt with one processor. But what if your system has two processors? I've got another session tomorrow, interestingly enough, on writing multi-core software for ARM platforms, which we're going to a lot of this stuff in a lot more detail. So if this wets your appetite, I do encourage you to come to that. But anyway, here we are, two processors, P1 and P2, and a nice ordered neat and tidy view of the world. If processor one updates variable X and then variable Y, and then processor two reads the two, then there are three possible outcomes that are logically expected, if you like. If processor two reads Y and X, and reads them in that order, no, reads Y and X after this point here, then it will see the new value for X and the new value for Y. If it reads them before this point, it'll see the old X and the old Y. And if it reads them right in the middle here, it'll see the old Y and the new X. It will never see the new Y and the old X. And if your program ever sees that combination, then you can reasonably assume that something has actually gone wrong. Now, unfortunately, in a modern multi-processing system, this assumption is no longer true. And you do have to deal with the fact that you might see combinations of data values which are unexpected and which are logically impossible, because somebody's changing your data. So that simple little sequence there, and the simple question is two load instructions, sorry, loading two variables from memory, right, and the load instruction to load A comes before the instruction to load B. Very simple. You and I can see that. Simple question, in which order are A and B physically fetched from memory? Now, that should be easy to answer, shouldn't it? Just look at the order in which the instructions are there. But if you ignore pipeline effects for now, and we've seen what pipeline effects can do, what if B is cached and A is not, right? In that case, the memory system could return the value for B much quicker than the value for A. And a typical ARM pipeline these days has a load store unit that can handle five or six outstanding memory transactions and return them in any order, just whenever the memory system gives them back. It'll pass them back onto the pipeline. So what if they're both cacheable, but the load of A causes a cache miss? Then the process is free because we do hit under miss completion. The process is just free to carry on, try and load B while the line fill is happening to get hold of A. So the value for B may well be returned long before the value for A. So, and to remove the stalls, as we've seen, the pipeline may well reorder them at runtime anyway. So already you can see exactly what behavior results in breaking that assumption on the previous slide. Now, it's likely, say, that if you're running this on a single processor, none of that would matter. By the time you get to the add instruction, which is when you need both of those values, the processor will have both of them. And surely it doesn't matter in which order they were loaded. But as we saw in the previous slide, what if another processor somewhere in the system is updating both of those variables at the same time as we're trying to read them? Right? Those assumptions that we made on the previous slide, as we can see, are now broken. And this second processor, if it was doing something slightly more complex than just adding the two values together, would see a logically inconsistent or broken combination of those two values. So we have to be able to cope with that. Or, we have to be able to stop it happening. And coping with something like this in the general case is not really possible and not really desirable in most cases. So we kind of have to make sure it doesn't happen. So how do we do that? Several ways. One could be to make sure that we understand the effects of the cache and we get it out of the way. Or ensure that we have some hardware for managing cache coherency or providing cache coherency. Right? And those are both subjects that I'm going to deal with tomorrow in the multi-core session. But the other approach, which we'll look at now, is to make sure that we have a viable method for locking or protecting critical sections like this where ordering of access by two different processing agents actually matters. So you could write a very simple lock like that. Now, from what you've seen in the last few slides, if you just take a moment to read that code, you'll probably work out very quickly that that lock sequence won't actually work. Well, to be precise, it's not guaranteed to work as intended. And if there's one thing you have to have in a lock function, it has to work reliably every time. Now, what you do is you need a mechanism that's going to enforce the ordering between two memory accesses, specifically between a load and a store. Now, if any of you have been around ARM technology or ARM processes for long enough, you might remember the swap instructions. Anyone remember that? Yay! Three of you. Good stuff. Right. Now, the swap instruction, that basically carried out an atomic load and store, and it swapped a register with memory location. Now, that was exactly what you need here because it forced the load and store to happen in a guaranteed order and in a guaranteed atomic sequence. Now, the way we used to do that was the bus, the memory interface, had a lock signal on it. And between the load and the store, the processor would basically flip the lock signal up, and that would lock anybody else out of the bus and refuse to allow anyone to do anything with memory while the processor was doing these two accesses. Now, that worked very well. And on a simple, you know, sort of single layer, single master bus system, yeah, it was kind of okay. But in the bus systems that we use today, that's just not possible. You can't, A, can't allow a single processor or single element to lock the bus for that length of time. And B, it's very, very difficult to propagate that kind of lock information across complex bus matrices and then through bridges and all kinds of other stuff. It's very, very difficult to do. So in architecture version 6, we defined a new method for doing this. And in architecture version 7, we actually deleted the swap instruction. So if you were very fond of it, I'm sorry. The new instructions, there's a pair of instructions, load and store, exclusive. And most modern architectures have a similar facility to this. Load, acquire and store, release, very, very similar in other architectures. And they all work basically the same way. The way they work in ARM, that must be, the way they work in ARM is that the load exclusive instruction loads from an address and then reserves it for exclusive access. So basically it sets a little tag in the memory system that says, I'm accessing this. Okay? And it sets a flag. The store exclusive instruction stores to an address and returns you a successful status if the flag was still set. Okay? It also then clears the reservation. So you can kind of see where we're going here, that any number of agents in the system can use a load exclusive instruction to load the current value of a lock. But only one of them will be able to do a subsequent successful store because as soon as that's happened, all the others will try and the reservation's gone. So they will all fail and they'll have to go back and, you know, back off and retry. Now in ARM systems, this is something you need to consult the documentation of your platform quite carefully because we don't actually mandate or design or ship the IP necessary in the memory system to implement this lock system. It's very fundamentally integrated within the bus matrix. And the bus matrix is something which is designed by the chip designer, not by the ARM architecture people. So you find that these locks are sometimes placed in slightly different places and they behave in slightly different ways. Their architectural behavior is constrained. But for instance, they're free to recognize any number of outstanding locks from one upwards. So you find some simple lock systems that only recognize one outstanding lock. So if you have multiple lock variables in memory and you try and access all of them, that counts as one lock. And as soon as you store to one of them, it unlocks all the rest. Now that guarantees you correct behavior, but it's not best performance. Other systems divide memory up into what we call a granule, the exclusives reservation granule, brilliant name. And locks which are in separate granules have separate reservation flags. So if you have many locks in your system, check the documentation. And it may be worth you actually spreading the locks out so that they're in separate granules. If your system supports separate reservations, then you may get better performance out of it. For instance. But I said two instructions. There are actually three on the slide here. There's a third one which I should point out before we go on. Clear exclusive. And that basically clears any outstanding reservations in the system. And that's the kind of thing that you might use in an operating system. Context switch so that an outgoing process which has an appending lock or appending reservation doesn't generate a false positive when the new process comes in. And that one might have appending lock as well. And there's potential for confusion there. So in context switch, you very often find this clear exclusive instruction just to clear everything up. So a very simple example. That's how you might build a simple lock structure using these instructions. The lock sequence on the left. The unlock sequence is on the right. And if you look at the code on the left, you can see there's a load exclusive. A little bit lower down. There's a store exclusive. And the load exclusive loads the current value of the lock and it checks and it keeps reloading it until it's unlocked. And then it goes down here and it tries to store to it to actually claim the lock by writing the locked value to it. Now multiple agents, multiple processes, multiple threads might be trying to do this all at the same time. And they'll eventually get through here. One of them will execute this store exclusive instruction. And if you look at it, if you're familiar with our assembler, you'll see that it's a bit unusual. Most stores only have one source register for the value you're going to store. This one actually has two. R1 is the value that we're going to store out. And R2 comes back with the status. And R2 comes back as zero if the lock, sorry, if the reservation has been cleared by the time you get here. It comes back with one if the reservation is still there. So if the reservation persists from here to here, then R2 will tell you you've succeeded. You've got your lock off you go. If somebody else has done a store to this lock location in between here and here, this store exclusive will fail. And you'll go around and try again or back off or do whatever your OS tells you to do. The unlock sequence is trivial because a standard store instruction clears any outstanding reservations on the location as soon as it does it. So you just have to write the unlock value and that automatically clears the reservation and other people can get in. Now then, we're going to have a summary time. I have eight minutes left. I'm kind of conscious that we've only had time to touch on a few of the dragons that exist in this area of embedded development. There's a huge amount of other stuff and other knowledge and other experience that we could go through. But just to build my way of summary, I just want to summarize the different properties of memory accesses that come into play here. And the things that you need to worry about when you're working on a complex embedded system. First of all, memory ordering. If you care that memory accesses must occur in the order that you've written them, then you need to start putting barriers in to make sure that happens. And you need to make sure that you might use locks if necessary to protect critical sections. And you need to make sure that peripheral memory is marked as device. Cardinality. This is if I have written three load instructions, I want three read accesses, right? The cardinality must match. And there, you need to get rid of things like speculative access on both the data side and the instruction side. Arm cores do both these days. And the way you do that is by declaring sensitive memory as device memory and that bans speculative access in those regions of memory. Volatility. Yeah, that's the most common one that we're all aware of. A memory location may change when you or the compiler or the machine are not looking. And in this case, yes, you need to use the volatile keyword and we all know that. Completion. Another one. I need to know when this access has completed before you move on. Again, use barriers for that to make sure that subsequent instructions are not executed. Remember, you've got two flavors of that. dmb, dsb. dsb is stricter than dmb. And in order to stop before moving on, you would use a barrier for that. Observability is by far the most complex one. It's similar to completion, but it's subtly different. Now, an access completes when it kind of leaves our sphere of influence. So when it leaves the kind of local story around my pipeline, my processor, my bus interface, my write buffer, as soon as an access goes beyond that, it's completed as far as we're concerned. But that doesn't necessarily mean that other parts of the system can see the result of that access. And you do need to bring other context into play there. You do need to consider perhaps cache management. You do need to consider, you know, where memory is being shared and how far out of the bus system that memory is, whether it's beyond caches or beyond write buffers and so on. So observability is by far the most complex. And again, I'll deal with some of those issues tomorrow. And finally, atomicity. Atomicity is a really, really fascinating subject. And atomicity is the concept of a sequence of memory accesses must be carried out without anything else getting in the way. So, you know, without any other accesses interleaving in between, for instance, without the bus being granted to anyone else during that particular sequence. And this is really important when you're dealing with shared memory, memory map peripherals and all kinds of things. So critical lock structures are one way that you can guarantee this. But it gets even more complicated when you look right down at the bus level on a complex pipeline processor or placed with a complex memory interface because you need to look very carefully, if it matters to you, at what the architecture says about atomicity. The wonderful thing about the ARM architecture is all processors that have ARM on the lid have to conform with it. But you say, you find, for instance, all single word-sized memory accesses are guaranteed to be atomic. So if you write to a 32-bit word, the architecture guarantees you that that operation, that bus transaction, is atomic. It has to be. Otherwise, that processor is not ARM compliant. And we will get out our big stick and our contract and go and sue them, beat them around the head and make them re-spin the chip and do it again. What about things like load and store multiple instructions, if you remember those? Are they atomic? Well, sometimes they are and sometimes they're not. You need to go and check the architecture very, very carefully and find out. What about accesses to double words, half words? Again, sometimes they are and sometimes they're not. Depends on what kind of memory you're accessing and also depends on the alignment of the address that you're accessing. Unaligned accesses are generally not guaranteed to be atomic, generally. But again, there's a huge amount in here and it has its very own completely incomprehensible chapter in the architecture efforts manual, which I would encourage you to go and have a look at if you want to go to sleep one evening. Anyway, so many questions, so little time, we just don't have time to go to any of that stuff. But hopefully what I've managed to get over to you is that there are lots of cases where the hardware and to some extent the compiler, but especially the hardware, do things that you need to understand. And you need to understand when and why and how these things happen to work out whether you care. And if you do care, then you need to know what to do about that. Memory types and barriers and locks are the three main techniques we used to do that. Just by way of closing on that theme, on November the 26th, 1922, Howard Carter opened just a little chink in the top corner of the door into Toot & Commune's burial chamber. And he kind of looked through the door and Lord Canavan, his backer, was kind of standing behind him, desperate to try and see. But it was only his tiny hole in the door and what he was doing was holding the candle up to it and just trying to see what he could see. And he wrote this in his diary afterwards. He says, As my eyes grew accustomed to the light, details of the room within emerged slowly from the mist. Strange animals, statues and gold, everywhere the glint of gold. And for the moment, it must have seemed an eternity to the other one standing by. I was struck dumb with amazement. And when Lord Canavan, unable to stand the suspense any longer, said anxiously, can you see anything? It was all I could do to get out the words, yes, wonderful things. And I kind of feel a little bit like that today. We kind of just peeled back a little chink and held a candle through the crack. And you can see some great stuff in here. But we do not have a chance to see it all. So I'm going to leave you with two literary quotations because I like to inject a bit of culture into our uncultured industry sometimes. This is from Marcel Praust's, Al-Récherche du Temp-el-Du, Remembrance of Things Past is not necessarily the remembrance of things as they were. And just as human memory is infallible, foolable and imperfect, so sometimes the memory systems that we work within our development work don't quite behave the way you want them to. But that's the literary quote, the pretentious one. I much prefer this one. This is the Red Queen said to Alice in the Looking Boss. It's a poor kind of memory that only works backwards. And sometimes it seems like our memory systems work backwards too. Anyway, I hope that was useful and a kind of introduction to all the stuff that's in here. And I encourage you to come to session tomorrow. We'll unpack some of this a little bit more in the context of multi-core processing and MP core platforms. I am told to encourage you to vote using the buttons at the back. If you've enjoyed this and learnt something new, then please bash the green button. If I've left you with the impression that you need to know quite a lot more, yes, again, please bash the green button. And then come and talk to me afterwards. And I'll tell you how we can fix that. But thanks very much. Thank you.
embedded systems. A little bit about the genesis of this presentation. I don't know how many of the order in which two memory accesses occur and ordering is one very obvious area where that pipelines, in order to maximize throughput of mapped to peripheral registers, shared memory, There it is, dmb. That's a memory barrier access memory in this gap here between the dmb called a remap peripheral. What that does is it them are actually necessary, and all of them of a lock. But only one of them will be able to might build a simple lock structure using these yes, you need to use the volatile keyword and we it's beyond caches or beyond write buffers and so accessing. Unaligned accesses are generally not know quite a lot more, yes, again, please bash