ARM Assembly: Pointers and Global Memory Access

I deliberately decided to write this tutorial after the one about the stack.  This is because the stack is a harder subject, but if you don't learn it first, you may fall into the bad practice of trying to put everything into global memory.  This is especially bad if you start off by storing lr in global memory.  The stack should be your primary goto place for memory, unless you need create something in a function that will still be needed after the function returns or if you need to allocate quantities of memory too large to put on the stack.  Even then, using global variables is not always the right solution.

When we learned about the stack, we learned that the stack pointer (sp) points to some location in memory, representing the top of the stack.  The stack pointer is just a pointer in the sense of C pointers.  It has a dedicated register, because it is essential to structured programming.  In reality, we can try to access any address in memory space.  Trying to access 0 will throw a null pointer exception, and trying to access anything past 0xc0000000 (3GB) will give you a permission error.  The memory is reserved for the kernel to keep track of information about the program.  Most of the rest of the space is initially unallocated space that will cause a segfault if you try to access it.

There are a few ways to allocate memory.  The stack is allocated by default, and the operating system will typically make sure there is enough, up to a certain limit (8MB, for example).  There is also a data area, a bss area, and a read only area (possibly more, depending on the OS and architecture) that you can also define, which will be allocated for the program when it starts.

These sections require special directives to create in your program.  Each section has a different purpose.  The data section is typically used for preinitialized (they start with data in them) variables.  The bss section is used for uninitialized variables.  The reason you might choose the bss section over the data section with 0s in places that are not initialized is that the data section is written into your executable, taking up more space.  If you need the variables to be preloaded with values, this is usually a secondary concern.  The bss section is allocated when the program starts, which means that it does not need space in the executable, aside from the amount of memory desired.  The last section, the read only or rodata section is typically used for constant strings or other run time constants.  When using the read system call, this appears to silently fail, not writing anything and not throwing an exception.  It appears that trying to write to the rodata area directly causes a segfault.   Put stuff in this section only if you are certain you don't want to overwrite it.  GCC typically puts string constant there.

Perhaps the most valuable area is the data area.  If you find you need to initialize a lot of mutable (changeable) variables at start up, this is probably a good place to put them.  Just make sure the stack would not be a more appropriate location.  For example, perhaps you need some memory to store an IP address.  You want the default to 127.0.0.1.  You program is going to load the IP address from a config file, but perhaps this file is empty the first time a user runs the problem.  You could allocate 4 bytes for the IP address in the bss section, but now you have to check if the IP address was in the config file, and if it was, store it to the memory, but if it was not, you will have to put the default value in.  Further, if you want to change this default, that could require finding there the default is put into memory in your config reading code.  If you put this in the data section and there is no address in the config file, you don't have to do anything, because it is already there.  If you want to change it, you can generally find one entry in the data section more easily than a bunch of moves and an LDM in the middle of a configuration section.

So, let's try it.

.data
.balign 4
ip_address:
    .word 127
    .word   0
    .word   0
    .word   1


.text
.global _start
_start:
    ldr r0, =ip_address
    ldr r0, [r0]

    mov r7, #1
    svc #0

This program is not going to read a config file, but it will set the default IP address.   Technically this is backwards, as the OS stores and accepts IP addresses starting with the lowest section and going up to the highest.

Give this a file name and compile this with as filename.s -o filename.o && ld filename.o -o filename.  From there, you can run it and output the error code, which will be 127.

The first thing that happens when you run this program is that the OS loads it into memory and reads some header information to see if it is valid.  By this time, your data area is already in memory.  Then the text section gets the memory address for the global variable and it reads the first value.  The first LDR instruction is getting a pointer to the data desired.  This is exactly like C pointers.  It is merely a memory address.  The second LDR line dereferences the pointer, getting the data that it points to.  (You could change the second LDR line to ldr r0, [r0, #4] to get the second value in the IP address.  Technically, we just created a simple struct that holds an IP address.  We can increase that 4 in multiples of 4 to get the next two elements of our struct.  Alternatively, we could use LDM to load the entire IP address into registers r0 through r3.  (And we could even flip the direction in the read or the write back, by using the right memory access code.)

The bss section is initially empty.  You use directives to tell the operating system how much preallocated memory you want, and it will allocate it and initialize it all to 0s for you (I am not certain you can rely on this last behavior on all platforms; some may leave garbage from something else there).

.bss
.balign 4 
some_memory:
    .space 16

.text
.global _start
_start:
    ldr r0, =some_memory
    ldr r0, [r0]

    mov r7, #1
    svc #0

This will allocate 16 bytes of memory (the same as the last program) when the program starts.  If you change the amount of space in the bss section to 1,600 bytes, you will find it increases the size of the executable by only 2 bytes.

The program starts by asking for 16 bytes of space in the bss section, and then it reads the first byte and returns it as an error code.  Again, the first LDR instruction is getting a pointer and the second is dereferencing it, getting the data.  You can add immediate multiples of 4 to the second LDR instruction to see the 0s in the other word sized sections of the 16 byte memory space.

The read only data section requires slightly different syntax on this particular device.  The assembler won't recognize the directive .rodata, unless it is preceeded by a .section directive.  Essentially this means that the assembler or linker does not support this section by default, so you have to define one.  The linker script used by the linker does recognize it though, and it makes sure to put it in the right place in the program binary, as well as designating it read only.

.section .rodata
.balign 4
write_this:
    .word 27

.text
.balign 4
.global _start
_start:
    mov r0, #13
    ldr r1, =write_this
    str r0,  [r1]

    mov r0, #0
    ldr r0, [r1]

    mov r7, #1
    svc #0

This will put the value 27 into the read only data section.  From there we put the number 13 in r0, and then we try to write r0 to the variable we created in the read only section.  The last part before returning first overwrites r0 with 0, to make sure we don't have an old value in there, and then we read the value from the rodata area.  If the write succeeded, we should get a 13 as the error code, but if it did not, we will probably get a segfault.  Using the debugger, I identified the location of the segfault this program throws as the STR instruction that attempts to overwrite the read only data.

As before, the LDR at the beginning is getting a pointer.  The STR instruction is dereferencing the  pointer and attempting to write to it this time (changing the stored value to a new one).  The last LDR does not run (the program crashes before this happens), but it is dereferencing the pointer stored in r1 and reading it into a register.

These different sections can give you a lot of control over your program.  If you want to make sure that a value is never changed, the read only section is very useful.  If you need your values initialized, the data section is probably the best.  If you cannot preinitialize your data, then maybe the bss section is what you need.

The things to keep in mind are that putting stuff in the data section will save the program time it would otherwise use to initialize, but putting it in the bss section will reduce the size of the executable.  The read only section is more of an error detection and security mechanism, that can prevent unskilled programmers and hackers from breaking things or sneaking malicious code or data in where it should not be.

ARM Assembly: The Stack

If you have been following the tutorials in order, you have likely hit a point where you are wondering what to do if you don't have enough registers to hold everything to need.  Of course, with so many registers, maybe you are not there yet.  Either way, now is a good time to learn about local memory.

The stack is where a process stores local variables. The stack is also used to hold onto anything it needs to store right before or after making a function call.  The stack is generally fairly small, often having a limit of only 8MB.  This means it is not good for storing large data structures.  What it is good for is storing information that is being used in a function, but which will no longer matter when the function is returned.  In other words, the stack is good for storing local variables that go out of scope when the function returns.

Before we start trying to use it, we need to know how it works.  There are several different ways the stack can work, depending on system.  The stack can grow up or down, and the stack pointer can either point at the last value stored on the stack, or it can point to the first unused address on the stack.  This presents four options, and ARM assembly is equipped to handle all of them.  Thankfully, we only need to know one.

Linux on ARM grows the stack down, and the stack pointer (sp) points to the last value on the stack.  This means, if you want to allocate more space on the stack, first you decrease the sp by the amount of memory you want, then you write to that memory.  When you are done using that memory, you increase the sp to its previous location.  This paragraph contains some of the most important information for using the stack, so reread it if you need to.

The second most important thing you need to know about the stack is that when you return from a function you must set the sp to exactly where it was when the function was called.  If you don't, then the calling function won't know where to find its local variables, which will almost certainly lead to unexpected behavior and eventually a segfault.  We will talk more about this when we learn how to make functions.

Now that we know the basics of how the stack works, let's try it out.  First we need to learn how to store data in memory and how to load it back into registers.  There is a set of instructions for this.  The easiest ones are LDR and STR, for load [to] register, and store [from] register.  The ARM quick reference card shows these instructions:

<op>{size}{T} Rd, [Rn {, #<offset>}]{!}
<op>{size}{T} Rd, [Rn],  #<offset>
<op>{size} Rd, [Rn, +/-Rm {, <opsh>}]{!}
<op>{size}{T} Rd, [Rn], +/-Rm {, <opsh>}
<op>{size} Rd, <label>

If you think this is confusing, you are not alone.  I had a hard time with this initially too.  The first thing you need to know is that <op> is either LDR or STR.  For LDR, Rd is the destination, where the value is being loaded to.  For STR, Rd is the register that contains the value to store.  The {size} portion is a code, telling the processor how much data we are loading or storing.  The options are B, SB, H, or SH, where B is byte or 8 bits, SB is signed byte, H is halfword or 16 bits, and SH is signed halfword.  Note that only LDR cares about whether a value is signed or not, so SB and SH won't work with STR.  If the size is omitted, then the instructions will load and store 32 bits, which is the full size of a register.  Here signed and unsigned make no difference for LDR or STR.  The {T} is an optional character that can be used to specify privilege level, which only matters to the kernel, so we won't worry about it.

Now let's talk about addressing modes.  ARM provides several ways to specify memory addresses, so that we don't have to waste precious instructions calculating memory addresses manually.  The first four options above start with a register that contains an address.  The Rn register will contain a base address.  In the first two, an offset is added to that base address.  The top one will add the offset, then it will load or store using the calculated address.  If the optional ! is used, the calculated address will be stored in Rn.  This can be used for easily traversing arrays.  The second option will access (load from or store to) the memory location in Rn, then it will add the offset to Rn and store the result in Rn.  The difference here is whether the offset is added before or after accessing memory.  The third and fourth allow an offset that is stored in a register, which may be added or subtracted from the base address and which can optionally be shifted.  <opsh> is defined as Rm, ??? #<shift>, where ??? is a shift code (LSL for logical left shift, etc...).  This allows Rm to be an offset that will be shifted before applying it, which is useful for traversing some types of data structures.  As with the first two, the third will update the base address in Rn if the ! is included, while the fourth will access the memory at Rn first, and then it will update Rn with the offset.  The last one uses a label.  When the program is compiled, this label is converted into an offset relative to the current position of the pc, essentially hard coding the memory location.

For accessing the stack, we only care about the first two of these.  The first one is for accessing memory without updating the address and for accessing memory where the offset is applied before accessing the memory, then the memory address is updated.  The second one is for accessing memory before applying the offset, then applying the offset and updating the memory address.  We don't need optionally shifted offsets, nor do we need offsets that are stored in registers, so we are not going to worry about the third and fourth options.  We are also not using labels, so the fifth option is not useful right now either.

Now we come to the point where how the stack works is important.  There are two ways we can deal with the stack.  The first is using SUB and ADD to decrement and increment the stack pointer directly.  For example, if we need to allocate 8 bytes on the stack, we might do this:

sub sp, sp, #8

This will reduce the sp by 8, giving us access to 8 bytes of memory on the stack.  When we are done, before we return, we would do this, to put it back where it was:

add sp, sp, #8

And now we have deallocated 8 bytes.  There is a cheaper way to do this though.  While it is sometimes better to just allocate as much as you will need at once, if you only need to put one or two things on the stack, it may be better to just do this:

str r0, [sp, #-4]!

This will decrement the stack by 4 bytes (the size of a register), storing the calculated address in sp, then it will store r0 to that location in memory.  This takes care of decrementing the stack and storing the data all in a single instruction.  Once we are done, there are two ways we can finish.  If we don't need the value, we can just add 4 to the sp and walk away.  If we do need the value though, we can do this:

ldr r0, [sp], #4

Notice that we used the first option above for storing and the second for loading.  This is important.  When storing something on the stack, we need to decrement before we store the value.  When loading, we need to load and then increment.  So, this time, we are loading the value from the stack (sp is pointing at the last value stored, which is what we want to load), then once our value is loaded, it will increment the stack pointer by 4, deallocating the stack memory we were using.

You should familiarize yourself with the different memory addressing modes.  For this particular system, pre-indexing (the first option) stores and post-indexing loads is the right way to deal with the stack, but if you ever program in ARM assembly for another OS, you may find this is not the case.  Further, when traversing arrays and other data structures, you may also find that this is not the best strategy.  Understanding how each addressing mode works is valuable for a lot of applications.

Now, you should also be aware that there is an easier way to do this.  ARM defines two pseudo instructions to help you work with the stack more easily.  These instructions are PUSH and POP.  The compiler turns PUSH and POP into the above STR and LDR instructions for the Raspberry Pi, but they are defined more loosely than that.  Whatever system you are compiling for, they will work with the stack as is appropriate for that system.  So, if you take a program written and tested on the Pi using PUSH and POP, assuming everything else is the same, it will compile correctly for other ARM systems that use the stack differently.  This is not all these instructions can do though.  Before we go any further, let's write some example programs.

We are going to write a program that uses the stack with STR and LDR, then alter it to use PUSH and POP.  There is one thing that is frequently stored on the stack at the beginning of a function.  This is the link register, lr.  We will get into function calls more later, but the two instructions for making function calls overwrite the lr register with a pointer to the instruction directly after the function call.  This is the return point, and it is how the processor helps our programs to keep track of where function calls need to return to.  There is a problem here though.  What happens if we call a function within another function?  The answer is the lr is overwritten with the new return point.  If we don't store the return pointer somewhere else, then it will be lost, and our program won't know where to return to.  In practice, we will probably end up with an infinite loop between the return point of the nested function and the end of the current function.  The universal solution to this is to store lr on the stack in any function that will be calling another function.  When we need to return, we will load it from the stack and use it.

There is another important use of the stack when using functions.  We only have about 12 registers we can use.  It is not uncommon to have function calls nesting quite deep, and it is not reasonable for us to allocate registers to specific functions.  Instead, we have a set of standards that functions ought to follow, which, when followed, will guarantee that they don't step on each other's toes.  We won't get deep into this at this point, but there is one thing that is relevant here.  r0 through r3 are used for passing arguments (and r0 is used for the return value).  Further, even if you don't pass arguments in them, the caller may not assume that the values in them will be the same when a function returns.  Essentially, functions are allowed to do whatever they want with r0 through r3, and calling functions must accept that.  In practice, this means that if you have values in these registers that you want to keep, you must store them somewhere else before calling a function.  The second thing is that values in r4 through r11 are expected to be maintained through a function call.  This means that any function that wishes to use any of these registers must store the existing values and then restore them before returning.  Both of these things can be handled using the stack.  We will focus on the second, as the first is more often handled either by doing work primarily in r4 through r11 to avoid the need to store before calling a function or by copying values in r0 through r3 into the r4 to r11 range.

We will continue using GCC as our compiler here, since main() is a function, and thus we should follow these function call procedures in it.  We are going to do some work in r4, r5, and r6, and leave the results in r0, but since main() is a function, we must restore whatever is in these registers and restore it before returning.

.text
.global main
main:
    str lr, [sp, #-4]!
    str r4, [sp, #-4]!
    str r5, [sp, #-4]!
    str r6, [sp, #-4]!

    mov r4, #13
    mov r5, #27
    add r6, r4, r5
    sub r0, r6, #7

    ldr r6, [sp], #4
    ldr r5, [sp], #4
    ldr r4, [sp], #4
    ldr lr, [sp], #4
    bx lr

Our program starts by putting any registers from r4 to r11 that we will be using onto the stack.  Then we use those registers to do some stuff.  In this case, we could have used r1, r2, and r3 just as easily, but if we had wanted to print out the value using printf(), then we would have had to move what we wanted to keep out of those registers to the higher ones.

Once we are done, we restore the values from the stack to the registers.  Note that we do this in reverse order.  The stack works exactly like a stack data structure when used this way.  The last thing we put in will be the first thing that comes out.  This means we must pull things out in reverse order so they will all be restored to the same places.

Something else important to note is that we are pre-decrementing when putting things on the stack and post-incrementing when we pull things off.  This is because the stack grows downward, and the stack pointer always points at the last item on the stack.  And recall that when we return, the stack pointer must point at the same place it was at when the function was called.  If we add up the decrements and increments, we get -16 at the beginning of the function, and +16 at the end, which breaks even.

Lastly, once we compile and run the program, we can use echo $? to print the return value, which should be 13 + 27 - 7 or 33.

This function is rather inefficient.  We are doing a ton of memory access.  We have a total of 8, and because they are in succession, each will have to wait for the previous one to complete.  Because ARM is very limited in instructions that access memory, it provides some instructions optimize memory accesses.  These are LDM and STM.  The M on the end of each means "multiple".  We can use these instructions to transfer the data in many registers to and from memory in a single instruction.  I can't say I understand how the wiring works for this, but I assume that the wiring between registers and memory is fairly robust to allow this.

We are not going to use these instructions directly right now, because they have to care about the order things are being transferred in.  We would not want to store r0 through r3, and then reload the data and have it end up with the first value in r3 and the last in r0.  So these have a sort of addressing mode system giving each another four versions.  The PUSH and POP instructions don't just apply to writing single registers to the stack.  If you give them a list of registers, instead of using LDR and STR, the assembler will use LDM and STM, to optimize performance.

Let's rewrite the above program using PUSH and POP to transfer multiple values at one!

.text
.global main
main:
    push {r4, r5, r6, lr}

    mov r4, #13
    mov r5, #27
    add r6, r4, r5
    sub r0, r6, #7

    pop {r4, r5, r6, lr}
    bx lr

This program will work identically to the first one, except cleaner and faster.  In fact, it should run a lot faster, because we cut memory accesses by 75%, and none of the other code takes significant time in comparison.

Note that PUSH and POP always produce code using the stack pointer.  If you want to load or store data anywhere else, you will have to use STR, LDR, STM, or LDM directly.

As usual, running this program should return the value 33 as the error code.

ARM Assembly: Ditching GCC

We started this using gcc to compile our assembly programs.  There are significant benefits to doing this, but it also comes with some costs.  In addition, the greatest value in programming in assembly is optimization, and if you are using a lot of C functions in your code, it defeats this point.  The choice to use gcc or not depends on a number of factors.

GCC makes compiling assembly slightly easier, because it can be done in one command.  Compiling without gcc requires two commands.  That said, if this is a problem, it is probably better to use a makefile anyway, which eliminates this trivial inconvenience.  GCC also gives you access to C functions, like printf(), malloc(), and others.  Avoiding the need to rewrite existing C functions can be very valuable, saving a great deal of time.

GCC adds some startup code to your binary.  In reality, all programs start at the _start label.  This label tells the linker that this is where your program should begin execution.  GCC adds its own _start section to our programs.  After some startup code, _start calls the main() function, which is why our assembly programs need it.  GCC's startup code increases the size of our binaries, and it increases the time required to start our programs.  This time is short, but it can still make a difference.  Both the time and size can be a big deal for embedded devices.  Also, while being able to use C functions can save substantial amounts of time, optimization is often an important reason for using assembly, and C's built in functions are not optimal for most applications.  C functions are designed for the most generic case possible.  This means that they are big and full of features.  When size or speed optimization is important, it is often better to write application specific versions of these functions yourself.  In that case, it may become entirely unnecessary to have access to C functions in your program at all.  Additionally, libraries for embedded devices may not have some C functions that are available for other platforms.

There is always a trade off.  If we abandon C, we have to talk to the operating system ourselves to get things done.  Things like I/O and memory allocation are protected by the operating system, for security and stability reasons.  If we want to talk to a peripheral device, we have to do it through the operating system.  If we want to allocate more memory, we have to ask the operating system for more memory.  C provides convenient wrappers for this, but without C, we won't have access to those.

We talk to the operating system through system calls.  We will discuss those more in later tutorials, but there is one system call that is essential when ditching gcc.  That is the exit system call.  Our program does not even have the ability to terminate itself.  We have to ask the operating system to do that for us.  This is done with the exit system call.

Here is a simple pure assembly program for you:

.text
.global _start
_start:
    mov r0, #10
    add r0, r0, #3

    mov r7, #1
    svc #0

Assuming this is saved as pure.s, you can compile it with the following pair of commands.

as pure.s -o pure.o
ld pure.o -o pure

 As with gcc compiled programs, the value in r0 is the return value or error code for the program, when it terminates.  This means you can run this and then echo the error code to make sure it works as expected.

The first part of the program should be pretty familiar by now.  The only difference here is that we are using _start instead of main().  Note that _start is not a function, so you cannot return from it with bx lr.  Attempting to do this will cause a segfault, because the address in lr is 0 when the program starts, making it a null pointer.  If you don't exit from the program, it will continue trying to execute code beyond the end of what you wrote, which will either be data in the data area or a bunch of null instructions (empty space full of zeros).  Eventually it will get to the end of allocated memory and segfault, or it will interpret some data as an invalid instruction and crash.

The last two lines of the program are a system call.  r7 is used by Linux to pass the constant for the system call you want.  In this case, we want the exit system call, which is number 1.  The last line, svc #0, is the system call instruction.  It turns over control to the operating system, which checks the value in r7, and performs the requested operation, if the user has permissions to do so.  In this case, it terminates the program.


(Side note: r0 is not some magic register for returning the error code of your program.  Technically, it is just the argument for the exit system call.  System call arguments work just like those for normal functions, starting at r0.  Unlike normal functions, Linux system calls can have up to 6 arguments in registers, starting at r0 and ending at r5.  The exit system call takes one argument, which is the exit code for the program.  C happens to use the return value from main() as the argument for its own call to exit.)

ARM Assembly: Integer Division

Division in discussed briefly in a previous post, but no example is given.  Originally, I left figuring out division to the reader, but I forgot something critical.  So, we are going to look at integer division separately.

ARM is an architecture that has advanced and evolved over time.  Some of the things you have already learned did not exist in early versions of ARM.  Because division is expensive, in the literal cost of transistors on the chip, it has commonly been left out of many architectures.  Division is often implemented in software, as successive subtractions, long division, or using so called "magic numbers".  The ARMv6 architecture used on the original Raspberry Pi is one architecture that does not have an integer division instruction.  In fact, even ARMv7-A (the architecture used for the original Pi 2) does not have an integer division instruction.  The Cortex-A7 version, however, has something called Virtual Extensions, which adds two integer division instructions.  The original Pi 2 happens to have a Cortex-A7 version of the ARMv7-A architecture, which means that it does have these instructions.

There is still a problem.  If you attempt to compile a program using the udiv or sdiv instructions, you will likely get an error message saying that this processor does not support the instruction.  This is because gcc and as compile for ARMv6 by default, to ensure compatibility with older Pi versions.  (Note that this means that if you do want your program to run on the older Pis, you will have to use some other method for doing division.)  To compile a program using these instructions, you must tell the compiler that you want to compile for the ARMv7-A Cortex-A7 processor architecture.  This is done with directives.

Before I demonstrate the directives, let's briefly talk about the division instructions.  If you have done the basic math tutorial, you may recall that these instructions only take registers, instead of an optional immediate value for the third argument.  This means that the numerator (dividend) and the denominator (divisor) must both be placed in registers.

.arch armv7-a
.cpu cortex-a7

.text
.global main
main:
    mov r1, #12
    mov r2, #2
    udiv r0, r1, r2

    bx lr

The first thing you will notice is the two new directives at the top.  The first tells the assembler what architecture you are compiling for.  The second tells it the specific ARM core you are compiling for.  The rest of the program is trivial.  It puts two values into registers, then it does unsigned division on them.  If you compile this, run it, and echo the error code, it will be 6 (12 divided by 2).  Try changing the values to see what behavior you get when the dividend is not evenly divisible by the divisor.

The directives used to tell the compiler what architecture to compile for can be very valuable, but they should also be treated with care.  When you use instructions that are limited to a particular architecture, you limit what your program can run on.  For the Raspberry Pi, the consequences are very clear cut, and it is easy to make a decision.  If you want your program to run on older Pis, you can keep the default.  If you don't need it to run on older Pis, you can compile for ARMv7, using instructions that are not available in older versions of ARM.  Note that some instructions also have multiple encodings, and they may not all be available on all architectures.  This means, even if you don't use ARMv7 specific instructions, using these directives may produce code that won't run on ARMv6.  ARM processors are typically backward compatible (at least for a few versions back), so if you are using a more recent Pi 2 or a Pi 3, with ARMv8 processors, compiling for ARMv7 will be fine.  If you were writing assembly for wider range of devices though, it would be less clear what those devices can support.  If we were writing Intel assembly to run on Intel processors, we might expect some customers to run our code on Pentium 4 computers or perhaps even Pentium 3s.  Maybe someone would eventually want to try it on a Pentium 1 even.  We would need to decide what we are willing to support.  If the odds of someone needing to run it on a Pentium 4 or lower are very low, we could compile for the Core 2 architecture, using more advanced instructions than we would have access to for a Pentium 1 processor.  We are lucky we are doing this on the Pi, where things are clear cut, but in real life applications, we cannot always just compile for the architecture we are developing on, or we might severely limit our market.  Sometimes it may be better to forego convenient instructions to allow clients with older machines access to our software.

There are a few more directives we will look at later, but you might find it valuable to know the correct directives for the ARMv8 processors currently shipping on new Pi 2s as well as on Pi 3s.

.arch armv8-a
.arch_extension crc
.cpu cortex-a53

There is one additional directive here, which you will probably never need.  The Pi 3 (and new Pi 2) processor has a CRC extension that adds a few instructions (that will not be covered in this series).  You can look up these instructions in the ARMv8 manual, if you are interested.  If you do use them, you will need the .arch_extension directive above.

Later on, we will add another directive for the floating point unit, but for now, these ARMv7 and ARMv8 ones should be sufficient.

Rasperry Pi SSH Over Bluetooth

I have been trying to do this for years, always failing.  In theory, it is possible to setup a network, called a Personal Area Network, using Bluetooth.  Once a PAN is setup, it should be easy to SSH into a machine on the network that is running an SSH server, for example a Raspberry Pi.  This is a very desirable situation where the only wireless network does not allow computers on it to see each other, for example a public network at a college.  In the past, my solution was using an ethernet cable to setup an ad hoc network, which works but can be very inconvenient.  I recently got a Raspberry Pi 3, and after several hours of research, I finally got it working!

The main problem I have run into with this is that most instructions for using Bluetooth on the Pi are geared toward connecting to Bluetooth devices offering a service, for example Bluetooth speakers or a Bluetooth keyboard.  It should not be terribly difficult to setup a Bluetooth PAN this way, using a Windows or Mac computer as the service provider and the Pi as a client.  There are a few problems with this though.  The first is that getting the Pi to log onto the computer typically requires access to the Pi.  In other words, you need either a monitor and keyboard or an SSH connection over some other network.  This defeats the purpose.  The second is that the Pi is offering the SSH service.  It does not make sense for the device offering the desired service to have to initiate the connection to the client.  This may seem trivial, but in practice it means that to automate the process you would have to run something on the Pi to constantly try to connect until it is successful, and that is wasteful and inefficient, not to mention error prone.

So, my goal was to setup a Raspberry Pi as a PAN server that my Windows laptop can connect to and then access the SSH service running on the Pi.

What you will need for this:

A Pi 3, or a Pi or Pi 2 with a USB Bluetooth dongle, and a laptop or desktop computer with Bluetooth (USB dongle or built in).  Don't get a cheap USB Bluetooth dongle from China.  It turns out that is probably why I have failed so often in the  last several years.  The $1 Bluetooth dongles I got from China don't seem to support the mode required to host a PAN network.  The Pi 3's built in Bluetooth works fine, and I have a more expensive USB Bluetooth dongle I got from Walmart 5 or 6 years ago that also works fine (on an old Pi B+, no less).

Boot up your Pi and log in.  You will need direct access for the setup, so either connect it to a keyboard and monitor, or SSH into it through other means.

Now,  we need to do a lot of things as root, so we are going to log into the root account.

    sudo su

From here on out, be very careful.  As root, you can do pretty much anything to your Pi, and Linux does not typically ask you to confirm when instructed to have destructive behavior.

Now update your Pi and install some packages you will need to continue (you will need internet access for this).
  
    apt-get update
    apt-get upgrade
    apt-get install bluetooth bluez-tools python-dev libsystemd-dev bridge-utils python-pip libdbus-1-dev libdbus-glib-1-dev
    pip install systemd-python
    pip install dbus-python

Each of those will take 30 seconds to a few minutes.

Next we need to create some files.  Each entry below will start with the file name surrounded by some dashes.  Below that is what the contents of the file should look like.  When you are done, you should have created four new files.

-----/etc/systemd/network/pan.netdev-----
[NetDev]
Name=pan
Kind=bridge
ForwardDelaySec=0


-----/etc/systemd/network/pan.network-----
[Match]
Name=pan

[Network]
Address=0.0.0.0/24
DHCPServer=yes
IPMasquerade=yes

-----/etc/systemd/system/pan.service-----
[Unit]
Description=Bluetooth Personal Area Network
After=bluetooth.service systemd-networkd.service
Requires=systemd-networkd.service
PartOf=bluetooth.service

[Service]
Type=notify
ExecStart=/usr/local/sbin/pan

[Install]
WantedBy=bluetooth.target

-----/usr/local/sbin/pan-----
#!/bin/sh
iptables -F
iptables -t nat -F
iptables -t mangle -F
iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

exec /usr/local/sbin/bt-pan --systemd --debug server pan

Once you have created these four files, you need the make the final one executable.

    chmod +x /usr/local/sbin/pan

Now you will need to install a script that handles some communication with the Bluetooth system.

    wget https://raw.githubusercontent.com/mk-fg/fgtk/master/bt-pan -O /usr/local/sbin/bt-pan
    chmod +x /usr/local/sbin/bt-pan

Now we are on the home stretch.  The last thing is making it all start up when the Pi boots.  First we will start the Bluetooth PAN service.

    systemctl enable pan.service

Next we need to tell it to listen for incoming connections.  Before we do this, we need to find out the MAC address of the Bluetooth adapter of the client machine (in my case, my Windows laptop).  In Windows 10, you can find this by opening the Properties of the Bluetooth adapter in the Device Manager.  One of the tabs will list the address of the device.  For other operating systems, you should be able to consult Google to find instructions for finding the MAC address of your Bluetooth adapter.

Once you know the device address, you can continue.

    crontab -e

The first time you run this, it will ask what editor you want to use.  Pick the one you are most comfortable with.  At the end of the file, add the following line:

    @reboot echo -e 'power on\ndiscoverable on\nagent on\ntrust 00:00:00:00:00:00\nquit' | bluetoothctl

Replace the colon separated zeros with the address of your client Bluetooth adapter.  This will tell the Pi that it should allow connections from that device.  Without the correct address here, the Pi will reject connections over Bluetooth.  If you need more than one device to be able to connect, you should be able to add additional trust lines to this string, with the Bluetooth adapter MAC addresses for those devices.  (Each should start with \n, followed by trust, a space, and then a MAC address.)  Save the file to the default location and exit the editor.

Lastly, if you have not already enabled SSH on the Pi, you will need to do that.  Run raspi-config.  Choose option 5, Interfacing Options, and then pick SSH, which is P2 in that menu.  Enable it, then close the configuration program. 

Now, reboot the Pi!  (I run init 6, but there is also a reboot program you can run from the command line.)


From here, you will need to look up how to log into a PAN for the operating system on your client computer.  In Windows 10, you right click the Bluetooth icon in the system menu, add a Bluetooth device, and connect to your Raspberry Pi.  Once connected, you can right click the icon again, click Join a Personal Area Network, right click on the icon for the Pi in the window that opens, then click Access Point in the Connect Using menu.  The default IP address for the Pi seems to be 10.0.0.1, though I am looking into changing this, as it is commonly used in business networks and may make it difficult to connect to the Pi while on some wireless networks.

I have found that this is sometimes a bit unreliable.  I do not claim to be an expert on Bluetooth, and I am still learning, but I believe the Pi may reject the trust command if it cannot detect the device when it boots.  If you have issues, make sure the client computer is running before turning on the Pi, and make sure the Pi is reasonably close when it boots (Bluetooth has a very short range).  This will ensure that the Pi can detect the client computer when it runs the trust line, hopefully consistently allowing you to log into the PAN and SSH into the Pi.


I'll update this as I learn more.  There are still some challenges that I want to see if I can overcome to make things work more consistently and smoothly.  Some of this seems kind of hacky, but there is not enough information available on using Bluez5 to do this, so it is all I have right now.

ARM Assembly: Memory Architecture

One of the biggest strengths of the ARM architecture is that it has a lot of registers.  This allows it to avoid wasting a lot of time waiting for memory transactions.  Any serious program is going to have to use memory though.  Before we learn how to use memory, we need to learn about the memory architecture of the Raspberry Pi (which is very similar to most modern systems).

The first thing we need to learn about is virtual memory.  Nearly all modern systems use memory virtualization for a number of reasons.  The first is security.  Early computers allowed programs to access memory directly, but this lead to major security problems when multiple programs could run at the same time.  A program could easily look at and change the memory used by another program.  A background program could watch memory being used by another program to capture a username and password, and then it might report that information somewhere that another user had access to, allowing a nefarious user to easily hack other users' accounts (in modern applications, could have allowed a program to see credit card information entered into a web page).  The second problem is a matter of memory addressing.  When multiple programs have direct access to the same memory space, it can be difficult for each to know what memory is being used by the other.  This is a bad situation when 20 or more programs could be running at the same time (as is common in modern computers).

Protected memory was created to deal with these two problems.  Protected memory is a processor level technology that allows the operating system to run at a different access level than other processes.  When the processor starts up, it is in unrestricted mode.  The operating system starts up with direct memory access, as well as direct access to all other hardware.  Once the OS has started, it starts up other programs in a restricted mode.  When the OS starts a program, it sets up the program memory address space in a memory manager unit within the processor.  When the program attempts to access a memory address, the CPU consults the memory manager unit to determine where that address points to in physical memory.  This is often called virtual memory.  On a 32 bit system, the program sees 4GB of memory space that it can access.  Part of this is where the program data is stored.  This also includes stack space, global memory, heap space, linked libraries, and some space reserved for the kernel to keep track of metadata about the program.  While the program sees all of this memory space, it cannot actually use all of it.  On the Raspberry Pi, this should be obvious, as it has only 1GB of memory.  When a program starts running, it can access (read and write) allocated stack space, global memory, and it can read (and write in some systems but not others) the text area, where the executable code is.  If it tries to read or write any other area of memory or in the reserved kernel space, it will fail with a segfault.  If the program wants more memory, it must ask the operating system for it.

 This represents how memory is mapped to programs in Linux.  The kernel space is the space reserved by the kernel for metadata.  In Linux, it is 1GB, in Windows it is 2GB by default.

The stack is used for storing local variables.  It grows downwards.  The stack has a maximum size limit, often 8MB.  This means that it is not suitable for storing large amounts of data.  It is mostly pre-allocated though, which means that it is readily available.

The memory mapping area is used for two things.  One is memory mapped files.  This includes dynamically linked libraries as well as files that are mapped to memory explicitly by the program, so it can access the file as if it were just memory addresses.  The benefit of mapping dynamically linked libraries this way is that multiple programs can have their virtual memory mapped to the same physical memory, allowing the operating system to load a single copy of each library for multiple programs to use.  The second thing this area is used for is anonymous mappings, which is essentially like mapping a file to memory without actually having a file.  We will discuss this more later, but this is one method of getting access to more memory from the OS.  This section grows downward.

The heap is the other method of getting access to more memory.  When the program starts, no heap memory is allocated.  The program must ask the OS to increase the size of the heap, which grows upward.

The BSS and data areas are global memory allocated when the program starts up.  The difference is, the data area contains variables that have been initialized.  In other words, they have values in then when the program starts.  The BSS area has uninitialized global variables, which are generally filled with zeroes when the program starts.

The text segment is one of the most important parts of the program.  It contains the executable code.


Now let's look at the spaces.  Most of these spaces represent random offsets.  Bugs in programs sometimes allow malicious code to be injected.  When this happens, it is very convenient to the malicious code when memory addresses of the various sections all start at the same place.  Modern operating systems make it more difficult for malicious code to affect buggy programs by randomly picking starting addresses for the stack, the memory mapping segment, and the heap.  There are two other spaces, one between the heap and the memory mapping segment, and one at the beginning of the program.  The one between the heap and memory mapping segment is generally the largest, and it leaves room for those sections to grow.  On the Raspberry Pi, it is impossible for them to meet, because the Pi will run out of memory before that ever happens.  On a system with more memory though, if those two sections meet, the OS will refuse the request to allocate more memory.  A robust program will deal with this gracefully.  The gap at the beginning of the program exists for another reason.  Most of the reason is due to certain performance gains in an ancient system the starting address was borrowed from (this gap is exactly 128MB).  There is, however, a very important reason the text segment cannot start at 0.  This reason is that 0 is used to indicate a null pointer, and if the text area started at address 0, then the null pointer would point to a valid memory location.

Aside from this, there are a few other segment types that can be used, though none of them are very important for this system.


Like most modern systems, the Raspberry Pi uses memory mapped hardware.  Like most 32 bit processors since the early-90s, the processor on the Pi is capable of addressing 1TB of memory (yes, the 4GB memory limit of 32 bit systems was Windows, not limitations of the processors; case in point, I have a 32 bit Xeon server that was running Windows Server 2003 Enterprise (essentially XP with a few extra features, like access to all of your memory) with 6GB of memory and full access to all of it; it is now running Linux, with full access to all 6GB).  With 1,000 times the memory space needed for the amount of memory is has, it just makes sense to use the memory system for accessing peripherals.  So, access to the GPIO pins, USB, Ethernet, audio, video, and everything else happens by accessing physical memory addresses.  Unfortunately (or, perhaps, fortunately) programs are limited to their virtual memory space, which is not mapped to this hardware.  The kernel, however, has direct access to this memory space, so programs must interact with hardware through the kernel.


Some of this information is academic, unless you end up programming embedded systems, operating systems, or drivers.  The important things to remember are that the stack grows down and the heap grows up, and the stack, the heap, and the memory mapping segment start at random addresses.  Also keep in mind that when a program accesses a memory address, it is not accessing that address on the actual memory of the Raspberry Pi.  It is essentially using a lookup table to find the data in physical memory.  And, of course, while the Pi's hardware is memory mapped, you won't be able to access it directly.  Instead, you will have to do that through the operating system.

ARM Assembly: Advanced Integer Math

The ARM architecture provides some additional capabilities in its math instructions that allow multiple operations to be done in a single instruction.  This also allows for using faster instructions for certain math operations when one of the operands is static.  Knowing how to use these instructions to their fullest will allow you to produce optimal programs.

In a previous article, we saw that some of the math instructions have an operand listed in the documentation as <Operand2>.  This is something of a multi-purpose operand.  As we saw, it can be a register that holds a value, and it can be an immediate value that fits some constraints.  It can also be a register, where the value in the register is shifted left or right by a certain number of bits.

You probably already know that arithmetic shifts can be equated with multiplication and division.  Since a logical left shift is the same as an arithmetic left shift, ARM just uses the term "logical shift left" and the syntax LSL to refer to it.  Keep in mind that logical right shifts should be used for unsigned math, while arithmetic right shifts should be used for signed math.  Shifting right is equivalent to division by a power of 2 (where the number of bits shifted is the exponent), and left shifting is equivalent to multiplication by a power of 2.  We can use add and subtract instructions with shifts in the last operand to multiply by some values that are close to powers of 2.  Why would we not just use a MUL instruction?  While timing of instructions is processor specific, and this particular processor does not seem to have good published data on that timing, it is generally safe to assume that multiplication and division instructions are significantly slower than addition, subtraction, and bit shifts.  The MUL instruction is best used when the second operand is not constant or when the equation cannot be reduced to a shifted ADD or SUB instruction.

The first example is multiplication by 4.  We won't even need to use ADD or SUB for this one.  The MOV instruction has a flexible operand as well.  (Note that ARM does not have any dedicated shift instructions.  It does have pseudo instructions for shifts, but the machine code generated just uses MOV instructions with shifts.)  To multiply a value in r0 by 4, storing the result in r1, use the following:

mov r1, r0, LSL #2

This will multiply the value in r0 by 4, and then store it in r1.  With this, we can multiply by any power of 2 that the processor is capable of.  If we wanted to multiply by 5, we would use an ADD instruction:

add r1, r0, r0, LSL #2

This adds the value in r0 to the value in r0 multiplied by 4.  In math, it might look like this: r1 = r0 + (r0 * 2^2), which is the same as r1 = r0 + (r0 * 4) or r1 = r0 * 5.  Using the ADD instruction, we can multiply by one greater than any power of 2.  So, what can we do with SUB?  We cannot use SUB directly for this, because the operand that can be shifted is the one that is being subtracted.  This could allow us to negate a value and then multiply it by one less than a power of 2.  We rarely need to negate a value, and then multiply that by one less than a power of 2 though.  More likely, we will need to multiply the value by one less than a power of 2 without first negating it.  There is a special subtraction instruction that allows us to do just that.

With addition, order does not matter, but it does matter with subtraction, which is why ARM has provided the RSB instruction.  This does reverse subtraction.  If the math for the SUB instruction looks like r0 = r1 - r2, the math for RSB looks like r0 = -r1 + r2.  If this does not make sense, consider that in normal subtraction, we subtract the second operand from the first.  In assembly, the second operand is the flexible one.  This means we can take a value in a register and subtract an immediate or shifted value from it.  We cannot start with an immediate or shifted value, and subtract a register from it, without some extra instruction.  The RSB instruction allows us to do this without any extra instructions.  So, let's multiply a value by 7, using RSB.

rsb r0, r1, r1, LSL #3

In math, we are doing this: r0 = (r1 * 2^3) - r1 = (r1 * 8) - r1 = r1 * 7.  When we want to multiply by a constant that is 1 less than a power of 2, we will typically use the RSB instruction to do that.

Division is not quite as flexible, as just adding or subtracting another instance of the original value will not increase or decrease the value we are dividing by.  Using right shifts though, we can still divide by powers of 2.  For example, if we want to divide by 16, we would use this:

mov r0, r1, LSR #4

This works only for unsigned values.  Instead of LSR, you can use ASR to divide signed values by powers of 2.

There is a special way of doing division by constants, however, it is rarely used with processors that have integer division instructions.  It essentially uses multiplication with a "magic number" that sort of represents the reciprocal of the number you want to divide by.  We won't go any further into this, as we have access to integer division instructions, but you can learn more by Googling, "magic number division -sports".

Note that the above strategies only work when one of the values is constant.  If neither of the values will be known until runtime, then you will have to use MUL, SDIV, or UDIV, and if you don't have access to integer division instructions, you either have to resort to long division or looped subtraction, for division.

You should spend some time looking over ARM's quick reference card for ARMv7, to see what other math instructions are available.  It includes some more overt combined operation instructions, like multiply and subtract, dual signed multiply and add (multiplies 2 sets of 16 bit values, then adds them), as well as a few other instructions for 16 and 32 bit multiplication combined with other operations.  Most of these exist, because they are useful for certain common applications, so there is certainly some value in knowing what is available to you.

If you have been doing these tutorials in order, you should know enough by now to write a program or two that will demonstrate your understanding of the things we just covered.  I encourage you to do so, as doing helps to reinforce learning.