# DMA vs ARM9, round 2 : invalidate considered harmful

It would seem these two aren't finished with each other yet.

A while ago, I wrote an article about NDS caching , how it can interfere with DMA transfers and what you can do about them. A little later I got a pingback from ant512, who had tried the “safe” DMA routines I made and found they weren't nearly as safe as I'd hoped. I'm still not sure what the actual problem was, but this incident did make me think about one possible reason, namely the one that will be discussed in this post: problematic cache invalidation.

### 1 Test base

But first things first. Let's start with some simple test code, see below. We have a simple struct definition, two arrays using this struct, and some default data for both arrays that we'll use later.

// A random struct, 32-bits in size.
struct Foo
{
u8  type;
u8  id;
u16 data;
} ALIGN(4);

// Define some globals. We only use 4 of each.
Foo g_src[16] ALIGN(32);
Foo g_dst[16] ALIGN(32);

const Foo c_fooIn[2][4]=
{
{   // Initial source data.
{ 0x55, 0, 0x5111 },
{ 0x55, 1, 0x5111 },
{ 0x55, 2, 0x5111 },
{ 0x55, 3, 0x5111 }
},
{   // Initial destination data.
{ 0xDD, 0, 0xD111 },
{ 0xDD, 1, 0xD111 },
{ 0xDD, 2, 0xD111 },
{ 0xDD, 3, 0xD111 }
},
};

And now we're going to do some simple things with these arrays that we always do: some reads, some writes, and a struct copy. And for the copying, I'm going to use DMA, because DMA-transfers are fast, amirite(1)? The specific actions I will do are the following:

##### Initialization
• Zero out g_src and g_dst.
• Initialize the arrays with some data, in this case from c_fooIn.
• Cache-Flush both arrays to ensure they're uncached.
##### Testing
• Modify element in g_src, namely g_src[0].
• Modify an element in g_dst, namely g_dst[3].
• DMA-copy g_src[0] to g_dst[3].

In other words, this:

void test_init()
{
// Zero out everything
memset(g_src, 0, sizeof(g_src));
memset(g_dst, 0, sizeof(g_dst));

// Fill 4 of each.
for(int i=0; i<4; i++)
{
g_src[i]= c_fooIn[0][i];
g_dst[i]= c_fooIn[1][i];
}

// Flush data to be sure.
DC_FlushRange(g_src, sizeof(g_src));
DC_FlushRange(g_dst, sizeof(g_dst));
}

void test_dmaCopy()
{
test_init();

// Change g_src[0] and g_dst[3]
g_src[0].id += 0x10;
g_src[0].data= 0x5222;

g_dst[3].id += 0x10;
g_dst[3].data= 0xD333;

// DMA src[0] into dst[0];
dmaCopy(&g_src[0], &g_dst[0], sizeof(Foo));
}

Note that there is nothing spectacularly interesting going on here. There's just your average struct definition, run of the mill array definitions, and boring old accesses without even any pointer magic that might hint at something tricky going on. Yes, alignment is forced, but that just makes the test more reliable. Also, the fact that I'm incrementing Foo.id rather than just reading from it is only because ARM9 cache is read-allocate, and I need to have these things end up in cache. The main point is that the actions in test_dmaCopy() are very ordinary.

### 2 Results

It should be obvious what the outcome of the test should be. However, when you run the test (on hardware! not emulator), the result seems to be something different.

// Just dmaCopy.

// Result           // Expected:
// Source (hex)
55, 10, 5222        // 55, 10, 5222
55, 01, 5111        // 55, 01, 5111
55, 02, 5111        // 55, 02, 5111
55, 03, 5111        // 55, 03, 5111

// Destination (hex)
DD, 00, D111        // 55, 10, 5222 (bad!)
DD, 01, D111        // DD, 01, D111
DD, 02, D111        // DD, 02, D111
DD, 13, D333        // DD, 13, D333

Notice that the changed values of g_src[0] never end up in g_dst[0]. Not only that, not even the original values g_src[0] have been copied. It's as if the transfer never happened at all.

The reason for this was covered in detail in the original article. Basically, it's because cache is invisible to DMA. Once a part of memory is cached, the CPU only looks to the contents of the cache and not the actual addresses, meaning that DMA not only reads out-of-date (stale) source data, but also puts it where the CPU won't look. Two actions allow you to remedy this. The first is the cache flush, which write the cache-lines back to RAM and frees the cache-line. Then there's cache invalidate, which just frees the cache-line. Note that in both cases, the cache is dissociated from memory.

With this information, it should be obvious what to do. When DMA-ing from RAM, you need to flush the cache before the transfer to update the source's memory. When DMA-ing to RAM, you need to invalidate after the transfer because now it's actually the cache's data that's stale. When you think about it a little this makes perfect sense, and it's easy enough to implement:

// New DMA-code:
DC_FlushRange(&g_src[0], sizeof(Foo));          // Flush source.
dmaCopy(&g_src[0], &g_dst[0], sizeof(Foo));     // Transfer.
DC_InvalidateRange(&g_dst[0], sizeof(Foo));     // Invalidate destination.

Unfortunately, this doesn't work right either. And if you think about it a lot instead of merely a little, you'll see why. Maybe showing the results will make you see what I mean. The transfer seems to work now, but the earlier changes to g_dst[3] have been erased. How come?

// Result:          // Expected:
// Source (hex)
55, 10, 5222        // 55, 10, 5222
55, 01, 5111        // 55, 01, 5111
55, 02, 5111        // 55, 02, 5111
55, 03, 5111        // 55, 03, 5111

// Destination (hex)
55, 10, D222        // 55, 10, 5222
DD, 01, D111        // DD, 01, D111
DD, 02, D111        // DD, 02, D111
DD, 13, D111        // DD, 13, D333 (wut?)

The problem is that a cache-invalidate invalidates entire cache-lines, not just the range you supply. If the start or end of the data you want invalidate does not align to a cache-line, the adjacent data contained in that line is also thrown away. I hope you can see that this is bad.

This is exactly what's happening here. The ARM9's cache-lines are 32 bytes in size. Because of the alignment I gave the arrays, elements 0 through 3 lie on the same cache-line. The changes to g_dst[3] occur in cache (but only because I read from it through +=). The invalidate of g_dst[0] also invalidates g_dst[3], which throws out the perfectly legit data and you're left in a bummed state. And again, I've done nothing spectacularly interesting here; all I did was modify something and then invalidated data that just happened to be adjacent to it. But that was enough. Very, very bad.

Just to be sure, this is not due to a bad implementation of DC_InvalidateRange(). The function does exactly what it's supposed to do. The problem is inherent in the hardware. If your data does not align correctly to cache-lines, an invalidate will apply to the adjacent data as well. If you do not want that to happen, do not invalidate.

### 3 Solutions

So what to do? Well, there is one thing, but I'm not sure how foolproof this is, but instead of invalidating the destination afterwards, you can also flush it before the transfer. This frees up the cache-lines without loss of data, and then it should be safe to DMA-copy to it.

DC_FlushRange(&g_src[0], sizeof(Foo));          // Flush source.
DC_FlushRange(&g_dst[0], sizeof(Foo));          // Flush destination.
dmaCopy(&g_src[0], &g_dst[0], sizeof(Foo));     // Transfer.
// Result:          // Expected:
// Source (hex)
55, 10, 5222        // 55, 10, 5222
55, 01, 5111        // 55, 01, 5111
55, 02, 5111        // 55, 02, 5111
55, 03, 5111        // 55, 03, 5111

// Destination (hex)
55, 10, D222        // 55, 10, 5222
DD, 01, D111        // DD, 01, D111
DD, 02, D111        // DD, 02, D111
DD, 13, D333        // DD, 13, D333

// Yay \o/

Alternatively, you can also disable the underlying reason behind the problem with invalidation: the write-buffer. The ARM9 cache allows two modes for writing: write-through, which also updates the memory related to the cache-line; and write-back, which doesn't. Obviously, the write-back is faster, so that's how libnds sets things up. I know that putting the cache in write-through mode fixes this problem, because in libnds 1.4.0 the write-buffer had been accidentally disabled and my test cases didn't fail. This is probably not the route you want to take, though.

### 4 Conclusions

So what have we learned?

• Cache - DMA interactions suck and can cause really subtle bugs. Ones that will only show up on hardware too.
• Cache-flushes and invalidates cover the cache-lines of the requested ranges, which exceed the range you actually wanted.
• To safely DMA from cachable memory, flush the source range first.
• Contrary to what I wrote earlier, to DMA to cachable memory, do not cache-invalidate – at least not when the range is not properly aligned to cache-lines. Instead, flush the destination range before the transfer (at which time invalidation should be unnecessary). That said, invalidate should still be safe if the write-buffer is disabled.

##### Notes:
1. No I'm not. For NDS WRAM-WRAM copies, DMA is actually slow as hell and outperformed by every other method. But hopefully more on that later. For now, though, I need the DMA for testing purposes.

# Some new notes on NDS code size

When I discussed the memory footprints of several C/C++ elements, I apparently missed a very important item: operator new and related functions. I assumed new shouldn't increase the binary that much, but boy was I wrong.

The short story is that officially new should throw an exception when it can't allocate new memory. Exceptions come with about 60 kb worth of baggage. Yes, this is more or less the same stuff that goes into vector and string.

The long story, including a detailed look at a minimal binary, a binary that uses new and a solution to the exception overhead (in this particular case anyway) can be read below the fold.

# DMA vs ARM9 - fight!

DMA, or Direct Memory Access, is a hardware method for transferring data. As it's hardware-driven, it's pretty damn fast(1). As such, it's pretty much the standard method for copying on the NDS. Unfortunately, as many people have noticed, it doesn't always work.

There are two principle reasons for this: cache and TCM. These are two memory regions of the ARM9 that DMA is unaware of, which can lead to incorrect transfers. In this post, I'll discuss the cache, TCM and their interactions (or lack thereof) with DMA.

The majority of the post is actually about cache. Cache basically determines the speed of your app, so it's worth looking into in more detail. Why it and DMA don't like each other much will become clear along the way. I'll also present a number of test cases that show the conflicting areas, and some functions to deal with these problems.

##### Notes:
1. Well, quite fast anyway. In some circumstances CPU-based transfers are faster, but that's a story for another day.

# Some interesting numbers on NDS code size

Even though the total size of code is usually small compared to assets, there are still some concerns about a number of systems. Most notably among these are stdio, iostream and several STL components like vectors and strings. I've seen people voice concerns about these items, but I don't think I've ever seen any measurements of them. So here are some.

 Barebones: just VBlank code 14516 base+printf 71148 base+iprintf 54992 base+iostream 266120 base+fopen 56160 base+fstream 260288 base+ 59384 base+ 59624 base++ 59648

The sizes in Table 1 are for a bare source file with just the VBlank initialization and swiWaitForVBlank() plus whatever's necessary to use a particular component. For the IO parts this means a call to consoleDemoInit(); for vectors and strings, it means defining a variable.

Even an empty project is already 15k in size. Almost all of this is FIFO code, which is required for the ARM9 and ARM7 to communicate. Adding consoleDemoInit() and a printf() call adds roughly 71k. Printf has a lot of bagage: you have to have basic IO hooks, character type functions, allocations, decimal and floating point routines and more.

Because printf() uses the usually unnecessary floating point routines for float conversions, it is often suggested to use the integer-only variant iprintf(). In that case, it comes down to 55k. The difference is mostly due to two functions: _vfprintf_r() and _dtoa_r(), for 5.8k and 3.6k, respectively. The rest is made up of dozens of smaller functions. While the difference is relatively large, considering the footprint of the other components, the extra 16k is probably not that big of a deal. For the record, there is no difference in speed between the two. Well, almost: if the format string doesn't contain formatting parts, printf() is actually considerably faster. Another point of note is that the 55k for iprintf() is actually already added just by using consoleDemoInit().

And now the big one. People have said that C++ iostream was heavy, and indeed it is. 266k! That's a quite a lot, especially since the benefits of using iostream over stdio is rather slim if not actually negative(1). Don't use iostream in NDS projects. Don't even #include <iostream>, as that seems enough to link the whole thing in.

Related to iosteam is fstream. This also is about a quarter MB. I haven't checked too carefully, but I think the brunt of these parts are shared, so it won't combine to half a Meg if you use both. Something similar is true for the stdio file routines.

Why are the C++ streams so large? Well, lots of reasons, apparently. One of which is actually its potential for extensibility. Because it doesn't work via formatting flags, none of those can be excluded like in iprintf()'s case. Then there's exceptions, which adds a good deal of code as well. There also seems to be tons of stuff for character traits, numerical traits, money traits (wtf?!?) and iosbase stuff. These items seem small, say 4 to 40 bytes, but when there are over a thousand it adds up. Then there's all the stuff from STL strings and allocators, type info, more exception stuff, error messages for the exceptions, date/time routines, locale settings and more. I tell you, looking at the mapfile for this is enough to give me a headache. And worst of all, you'll probably use next to none of it, but it's all linked in anyway.

Finally, some STL. This is also said to be somewhat big-boned, and yes it isn't light. Doing anything non-trivial with either a vector or string seems to add about 60k. Fortunately, though, this is mostly the same 60k, so there are not bad effects from using both. Unfortunately, I can't really tell where it's all going. About 10k is spent on several d_*() routines like d_print(), which is I assume debug code. Another 10k is exceptions, type info and error messages and 10 more for. But after that it gets a little murky. In any case, even though adding STL strings and vectors includes more that necessary, 60k is a fair price for what these components give you.

#### Conclusions

The smallest size for an NDS binary is about 14k. While printf() is larger than iprintf(), it's probably not enough to worry about, so just use printf() until it becomes a pressing matter (and even then you could probably shrink down another part more easily anyway). There is no speed difference between the two. The C++ iostream and fstream components are not worth it. Their added value over printf and FILE routines are small when it comes to basic IO functionality. STL containers do cost a bit, but are probably worth the effort. If you need more than simple text handling or dynamic arrays and lists, I'd say go for it. But that's just my opinion.

Please note, the tests I did for this were fairly roughly. Your mileage may vary.

Lastly. The nm tool (or arm-eabi-nm for DKA) is my new best friend for executable analysis. Unlike the linker's mapfile, nm can sort addresses and show symbol sizes, and doesn't include tons of crap used for glue.

##### Notes:
1. Yes, I said negative. Even though it has the benefit of being typesafe and extensible, the value of these advantages are somewhat exaggerated, especially since it has several drawback as well (see FQA:ch 15 for details). For one thing, try finding the iostream equivalent of "%08X", or formatted anything for that matter. For early grit code I was actually using iostream until I got to actually writing the export code. I couldn't move back to stdio fast enough.

# NDS register overview

libnds has two sets of names. This probably is a result of serving different masters in its early days. One set uses Mappy's nomenclature. That's the one without the REG_ in front of it, and uses things like _CR, and _SR. This is one you're most likely to see in the current NDS tutorials. The second set uses GBATek's names (mostly) plus a REG_ prefix. If you've done GBA programming, these should feel quite familiar.