As foretold in the last episode, it’s time to dig into C++ memory handling. However, this will be explained the way I learned it, which means we’ll start with a story…
Once upon a time, I learned how to program machine code on the C64. To do this I used a cartridge which would let you type machine code straight into memory. This is a terrible way to program, because there is no “insert” functionality. Also, if you move any part of the code, you have to update all jumps to that code yourself. It’s a terrible way to program, but a great way to learn.
On all modern computers, memory is organized into bytes. A byte is an 8-bit number, a lot like the “char” discussed in the previous post. A curious reader might ask at this point, are those bytes signed, or unsigned? The answer is that the computer doesn’t care, and when you program machine code, the bytes can be whatever you want.
Machine code doesn’t have types, so a byte that contains the value 67 could be the letter ‘A’, the value 67, a bitfield, a tiny 8-bit floating point number, or anything else you can possibly imagine. Neither the computer, nor the machine code cares.
When got an Amiga 500, I started using assembler instead of machine code. Assembler and machine code are closely related, but with assembler, you use a compiler to translate a text file into machine code. This means that “insert” is now a thing, and you can use labels for jumps, which simplifies moving code around a lot. The Amiga 500 had a 68000 processor, which had 8 “address registers”. An address register is generally used to point to a location in memory, however, there is very little difference between an address register and an integer.
The Amiga 500 has 512kb of memory. That means ~512 thousand bytes. If we just imagine all of them laid out in a row and start counting from zero, then each memory location has a number, and that number is what the address register contains. There is nothing really magical about address registers though. Since the computer doesn’t care, we can also treat them like integers. For instance, if we add one to an address register, then it will point to the next byte. If you have an address register that points to a 32-bit integer, then you need to add four to it to make it point to the next 32-bit integer, since 32-bit integers are four bytes long.
Then I tried to learn C…
C has pointers, and makes heavy use of them. (C++ does too since it’s built on C) Pointers are a lot like address registers with one very important distinction: They know what kind of thing they point to! A pointer to an integer and a pointer to a char behaves differently in some ways, because the compiler cares in ways that assembler and machine code doesn’t. At first I thought this was immensely stupid, and it wasn’t until a few years later when I picked up C a second time that I got used to it and realized how helpful it is.
Let’s illustrate with an example:
// An array of 512000 char.
char mem[512000];
// a pointer to a char
char* pointer;
// make 'pointer' point to the first char
// in the 'mem' array.
pointer = & mem[0];
// increase 'pointer' by one
pointer++;
// pointer now points to second char in 'mem'
Let’s try that again, but with integers:
// An array of 512000 int.
int mem[512000];
// a pointer to an int
int* pointer;
// make 'pointer' point to the first int
// in the 'mem' array.
pointer = & mem[0];
// increase 'pointer' by one
pointer++;
// pointer now points to second int in 'mem'
A few notes:
- in the second example ‘mem’ is four times larger, because each int takes up four bytes, while a char only takes up one byte.
- When pointer is increased in the second example, the underlying address register is actually increased by four, to make it point at the second integer in the ‘mem’ array. This is done automatically by the compiler since it knows that ‘pointer’ points to an integer, which is four bytes in size.
Ok, I think storytime is over, let’s get down to actual C++ things…
Arrays
As we saw in the sample above TYPE name[SIZE]; creates an array variable. An array variable is simply a bunch of TYPE next to each other in memory. As we discussed earlier, that memory can be global, object instance memory, or function-local. An array created this way can never change in size, except for function-local arrays, the size has to be a compile-time constant, so you have to know what size you want when write the program.
To access the individual entries in the array, you use name[index], care has to be taken, because there is nothing that stops you from trying to access entries outside of the array. The program will generally crash if you do that though.
It should also be noted that for basic types, arrays are not generally initialized to zero, so you generally have to do that yourself, sort of like this:
void test() {
int data[2000];
for (int i = 0; i < 2000; i++) data[i] = 0;
// more code here which uses data
}
Pointers
In the previous example “i” ends up working a lot like a pointer, as we loop over each entry in the array and set it to zero. However, it’s not actually a pointer. We could write the same thing using a pointer like this:
void test() {
int data[2000];
for (int* p = data; p < data + 2000; p++) *p = 0;
}
This might be a little harder to understand, so let’s look at the individual parts:
int* pthis declares a variable called “p” which is a pointer to anint.p = datawhen you use “data” without the[], what you get is actually a pointer to the first element in the array, and here we assign that pointer to “p”, so “p” points to the first element in the array.data + 2000again “data” is a pointer to the first element in the array, but when we add 2000, we get a pointer which points to a spot right after the whole array. Pointing outside of the array like this might seem weird, but it’s perfectly reasonable as long as we don’t try to read or write the memory at that point.p < data + 2000this reads out as “while p is less than the end of the array”.p++this increments p by one (but remember, the address register is incremented by four.)*pThis is how you access the value that the pointer points to.*p = 0this sets the integer that p points to to zero.
A few more things you can do with pointers:
& Xmeans “get the a pointer that points to X”* ptris the inverse of& X.- If you have two pointers that point into the same array, you can subtract them to find out how many elements apart the are. Note that the result will not be counted in bytes, but in elements. (Basically the underlying address registers will be subtracted, and the result will be divided by the size of the elements.)
ptr->nameis used to look up a member in a struct which ptr is pointing to.ptr->nameis the same as(*ptr).name.ptr[N]can be used to access the N th element from the point the pointer is pointing to.ptr[N]is exactly the same as *(ptr + N)& ( ptr[N] )(take the address of the Nth element) can be written out as& * (ptr + N)“&” and “*” ends up negating each other, so& (ptr[N] )is the same asptr + N.
In actual use case, pointers are sometimes used to point to a single value, or sometimes it’s a pointer into an array. In C++ “this” is a pointer to the object instance we’re currently executing code in.
The Heap
Well there you have it. Memory is an array of bytes. Arrays are elements next to each other in memory. Pointers are basically integers and C++ multiplies all your pointer math by the size of the element. Simple, right?
Remember how I said that strings are not a basic type in C/C++? Well we can just make an array of char with a zero at the end. In C that is generally how strings work. In C++ there is also an std::string class that manages the char array for you, however I try to avoid using that because it allocates memory from the heap.
Oh, right, we haven’t talked about the heap yet…
Let’s look at a typical memory layout. This basically applies for both embedded processors and a single process on a machine with a MMU:
Ok, so I borrowed this image from wikipedia this image, so it needs a little bit of “translation”… Starting from the bottom:
- “text” actually means the machine code (On a Proffieboard, the program actually lives in flash memory, which is separate from RAM memory.)
- “initialized” data means global variables which were given a value, like “int X = 5;”
- “uninitialized” data means global variables which were not given a value, like “int X;” these will just be initialized to zero at the beginning of the program.
- “heap” this is the memory that is not used when the program begins. We can allocate memory from this space using “malloc” or “new”.
- The “stack” contains all the temporary local variables inside functions. Every time your call a function, some stack space is used, and when you return from the function that memory is returned. A pointer is used to keep track of how much stack memory is used. This pointer is called the “stack pointer”.
The stack is easy to keep track of because memory is always freed in the reverse order compared to to it’s allocation. Heap memory is not so lucky. Entities allocated with malloc() can be freed with free(), but the order of these calls is controlled by the program and may follow little or no pattern.
We could compare it to a parking lot. Except the cars all have different widths (1 or more parking spots wide), and every time we park a car (allocate memory with malloc) we block those parking spots until the car leaves (calls free). As you can imagine, a parking lot such as this would eventually have a bunch of free slots, but it’s possible that none of those free slots are big enough for a large car, even if the total amount of free slots would be enough. This sort of wasted space is called “fragmentation”, and most kinds of memory allocation schemes have this problem, and unfortunately there is no valet available to fix it.
Even without fragmentation, a program which runs out of memory will generally fail, and in some cases crash, which is just not great, especially for an embedded program like ProffieOS, and since the Proffieboard doesn’t really have a lot of memory, the problem is potentially a big one.
The “solution” to this problem used in ProffieOS is to only use heap memory sparingly, and when we do use heap memory, we allocate all the memory we need at the start, and then run the code without allocating any more memory. Assuming I did this right, it means that the code cannot suddenly run out of memory while you’re using your lightsaber, because no new memory is allocated at that time. The only time the saber can run out of memory is when switching between presets, as we do re-allocate some things when that happens.