The plan

Basically for synchronization of multiple CPUs it should be enough to implement a simple mutual exclusion mechanism sometimes referred to as spinlock. And the simplest implementation of the spinlock if pretty straighforward, as you will see.

Once we have a simple implementation, I’m going to use it as an opportunity to look at somewhat more subtle details of shared memory synchronization like memory model and memory barriers. Hopefully that would show why correct synchronization is difficult and why using simple synchronization primities like mutual exclusion is so convenient.

Simple spinlock

In the simple implementation I will rely on an atomic read-modify-write operation that exists in many programming languages. To be specific I will be using C, but C++ and Rust would have a very similar mechanisms available.

In the standard C there is a header stdatomic.h that defines a type struct atomic_flag. You can think of this type as a bool variable, with a caveat that you can’t (or shouldn’t) work with it as a simple bool variable and instead should rely on special functions.

The basic idea of the implementation is that we have a bool variable that initially is set to false. We want to implement two functions: lock and unlock.

The point of those two function is that a thread of execution that successfully finished execution of function lock and before it executed unlock becomes an “owner” of the lock on which the function was called.

And while the lock has an owner like that, all other threads of execution that call the lock on the same object will get stuck in the lock function and will not complete until the current owner of the lock calles unlock function.

Let’s take a look at an example and for that we will start with defining an interface for our implementation:

struct spinlock {
    ...
};

void spinlock_lock(struct spinlock *l);
void spinlock_unlock(struct spinlock *l);

Now with that interface in mind, let’s consider an example when we have a structure with a complex state that is being accessed from multiple threads. Let’s say for example, we have a binary search tree or something like that:

struct node {
    struct node *parent;
    struct node *left;
    strict node *right;
};

struct search_tree {
    struct node *root;
};

If we start inserting and deleting elements from the tree from multiple threads without any synchronization, because making changes to the search tree requires multiple operations done in the correct order, those threads will start steping on each other feet.

To avoid that we can use the spinlock as follows:

struct spinlock lock;
struct search_tree tree;

...

void search_tree_insert(struct search_tree *tree, struct node *new_node)
{
    spinlock_lock(&lock);
    tree_insert(tree, new_node);
    spinlock_unlock(&lock);
}

Because the lock can have no more than one owner, at most one thread can execute tree_insert at the same time, thus we avoid situation when multiple threads step on each other feet.

NOTE: We only get this guarantee of mutual exclusion if all the threads of execution follow the same protocol and take ownership of the same lock before making any updates to the search tree in the example above.

Now, let’s take a look at how we can implement this using only C functions defined in the standard (and are not really architecture specific):

struct spinlock {
    struct atomic_flag flag;
};

void spinlock_setup(struct spinlock *l)
{
    atomic_flag_clear(&l->flag);
}

void spinlock_lock(struct spinlock *l)
{
    while (atomic_flag_test_and_set(&l->flag));
}

void spinlock_unlock(struct spinlock *l)
{
    atomic_flag_clear(&l->flag);
}

There are basically just a couple of functions:

1. atomic_flag_test_and_set
2. atomic_flag_clear

atomic_flag_clear writes to the atomic_flag structure a value of false atomically - rather simple, if we leave aside the details of what atomic actually means.

atomic_flag_test_and_set is somewhat more interesting it atomically as one indivisable operation performs the following actions:

1. read the current value in the flag
2. write true to the flag

So it reads the old value and writes a new one as one operation. The old value is returned as a result of the function.

Taking that semantic let’s look at the spinlock_lock function in a bit more details. The function will spin in the loop as long as the value in the flag is true.

If the function at some point observes that the value is not true it will write true there again and returns.

Intuitively it’s rather easy to understand - when atomic_flag structure contains true it means that the lock has an owner and when it contains false the lock is free and does not have an owner.

We can aquire the lock by writing true value to the flag, but only as long as it does not have an owner already. And we can release the lock by writing false there, but only the current owner of the lock should do that obviously.

This implementation of mutual exclusion is actually correct, but as we will see below its simplicity might be a bit misleading and there is much more going on here than meets the eye. Moreover, as we will see there are some things that we can actually change in this implementation to gain some additional properties.

Memory ordering constraints

Quoting Leslie Lamport, “accessing a single memory location in a multiprocessor is traditionally assumed to be atomic. Such atomicity is a fiction; a memory access consists of a number of hardware actions, and different accesses may be executed concurrently”.

What it means is basically, just because the instructions in the program go in a certain order, does not mean that the processors executing them has to do them in the same order.

It might sound weird, but it actually makes sense if you consider that processor may try to optimize what it is doing to achieve the same result faster or more efficiently.

The problem is that when you have multiple cores working independently it’s difficult to tell what the expected end result should be. Even without potential re-orderings that processor might do, when you run a program on multiple cores, without proper synchronization, the result might essentially be unpredicatble.

And that’s what it comes to in the end - proper synchronization must tell the processor what operations can and cannot be re-ordered. Now, with that in mind let’s take a look at the spinlock implementation and figure out what are the ordering constraints we have.

Looking again at the hypothetical example of updating a search tree:

// Code before the critical section
spinlock_lock(&lock);

// Critical section that should only be executed by one thread at a time
tree_insert(tree, new_node);

spinlock_unlock(&lock);
// Code after critical section

One thing that we want to enforce here is that tree_insert function is not executed concurrently by multiple threads and that’s why we use the lock. So at the very least we want to prevent re-orering of tree_insert or any of its parts before spinlock_lock or after spinlock_unlock, otherwise it defeats the purpose of having the lock in the first place.

On the other hand, for correctness at least, we don’t need to prevent any code before or after the critical section being moved into the critical section. That’s because that code could be run by multiple threads at the same time, so it could be run by a single thread as well, without violating correctness.

As I mentioned earlier, the implementation of the spinlock was correct, so what exactly in the implementation prevents re-ordering of tree_insert logic outside of the critical section guarded by spinlocks?

What controls memory ordering constraints around atomic operations like atomic_flag_clear or atomic_flag_test_and_set is memory order parameter. The atomic operations I used above don’t take such a paramter, but there are versions of these functions that do: atomic_flag_clear_explicit and atomic_flag_test_and_set_explicit. The versions I used above are equivalent to the explicit versions with the parameter memory_order_seq_cst.

memory_order_seq_cst means sequentially consistent memory operation ordering. To understand what kind of constraints does the memory_order_seq_cst implies let’s look at the C standard. The relevant parts we need to pay attention to are:

1. “sequenced before” relation
2. “synchronizes with” relation
3. “inter-thread happens before” relation
4. “happens before” relation

Quite a few things to unpack here, but once you’re go through the formalisms, it’s not that hard to develop basic intution about those things.

Sequenced-before relation

Let’s start with the “sequenced before” relation. It’s an asymetric and transitive relation between evaluations executed in a single thread.

This relation induces a partial order between evaluations in a single thread. Which in this case means that we can tell for some of the evaluations whether one of them is computed before another.

Let’s take a look at a toy example:

#include <stdio.h>
#include <stdlib.h>
...
char *buf = malloc(large_enough_buffer_size);
char *p = buf;
...
while ((*p++ = getchar()) != EOF);

What can we say about evaluations in this example and how they are ordered? I can say that malloc is definitely “sequenced before” p = buf. That’s because those two statements are separated by ‘;’ which creates a so called sequence point between the two.

Similarly, I can tell that p = buf is “sequenced before” p++ and getchar because they are separated by a sequence point. Because “sequenced before” is transitive relations, I can also say that malloc is “sequenced before” p++ and getchar, because it’s “sequenced before” p = buf, and, in turn, p = buf is “sequenced before” p++ and getchar.

In the same example however, I cannot tell whether increment of p “sequenced before” getchar or not. So sequencing of those two evaluations is not determined, so it demonstraints that the relation is not total, but in fact partial - not all evaluations can be ordered with this relation.

To summarize, “sequence before” relation defines how evaluations happenning in a single thread can or cannot be ordered.

One point that I want to stress is that “sequenced before” relation is strictly single threaded. It does not order, at least directly, evaluations that happen in different threads. For example, just because A is sequenced before B in thread T1, as unnatural as it sounds, it does not actually imply, that another thread T2 will see the effects of A before it will see the effects of B.

Synchronizes-with relation

This relation is really the core and probably the most important thing we need to understand.

Unlike the previous relation, this one is about evaluations or operations happening in different threads. And language standard has to define what operations synchronizes with each other.

The version of the C standard covers several cases, but one particularly important is atomic release and atomic acquire operations on the same object synchronize with each other under some conditions.

What is an atomic release operation? Atomic release operation is an atomic operation that performs a write or stores a value in the atomic variable using one of the following memory ordering parameters:

1. memory_order_release
2. memory_order_ack_rel - this is just short for acquire and release
3. memory_order_seq_cst - this is the one which atomic operations use by default.

An acquire operations is an atomic operation that performse a read or loads a value from an atomic variable using one of the following memory ordering parameters:

1. memory_order_acquire
2. memory_order_ack_rel
3. memory_order_seq_cst.

NOTE: some atomic operations can perform more than just load or store, like, for example, atomic_flag_test_and_set performs both read and write, in this case the operation still can be a release or an acquire operation even though it does more than just store or just a load.

Now, I mentioned that two atomic operations synchronize with each other if they act on the same atomic variable, use right memory ordering paramter and satisfy certain conditions, what are those conditions?

Let’s say we consider two operations A and B, both acting on the same atomic variable M. Let also A be a release operation, it means that among other things it writes a value to M. And let B be an acquire operation, so among other things it reads from M.

A synchronizes with B if B reads from M a value written by A or any atomic operation that wrote a value to M after A. In other words, A synchronizes with B, if B reads a value written by A or a value written after A wrote something to the atomic variable.

So to put it even simpler, two operations on the same atomic variable synchronize with each other if one operation sees the result of another operation plus all the addition conidtions on the memory order parameters.

Inter-thread happens before and happens before relations

So now we have some idea about “sequenced before” and “synchronizes with” relations, what remains is to understand some rules of how those relations can be combined with each other and what properties those combinations have.

In order to do that C standard introduces additional relation called “inter-thread happens before”. We don’t need to know all the rules of this relation for this post, so I will simplify and only cover those that I’m going to use.

Again, let’s say we have two evaluations A and B, unlike in case of “sequenced before relation” these evaluations may potentially be in different threads. We say that A “inter-thread happens before” B if one of those is true:

• A synchronizes with B
• There is some evaluation X and A is sequenced before X and X inter-thread happens before B
• There is some evaluation X and A inter-thread happens before X and X sequenced before B.

So it’s a recursively defined relation, but it’s a rather intutive definition that allows to combine sequences of “sequenced before” and “synchronized with” relations together.

Happens before relation is even simpler, evaluation A happens before B if one of the following is true:

• A is sequenced before B, which implies that A and B are executed in the same thread
• A is inter-thread happens before B, and in this case A and B can be executed in differnt threads.

Hopefully, the name of the relation “happens before” gives you a clue as to what this relation implies in practice, but when it comes to the language standard it additionally formalizes it by introducing a concept of visible side effect.

Basically a side effect of an operation A on some object M is visible to the operation B on the same object M, if A happens before B and there is no other operation X that affects M such that A happens before X and X happens before B.

NOTE: that in this case M does not have to even be an atomic object - as long as we can establish that A happens before B, side effects of A should be visible as long as they were not overriden by some other operation.

Putting things together

Now let’s try to put things together and return to our hypothetical example:

// Code before the critical section
spinlock_lock(&lock);

// Critical section that should only be executed by one thread at a time
tree_insert(tree, new_node);

spinlock_unlock(&lock);
// Code after critical section

Let’s consider an example with just two threads, T1 and T2, to be specific. This example, will extend the same way for a larger number of threads.

Let’s say that thread T1 owns the lock lock at the moment and thread T2 tries to take ownership by calling spinlock_lock.

Assuming that tree_insert call does not get stuck indefinitely, thread T1 will eventually call spinlock_unlock. Remember that spinlock_unlock inside uses a function atomic_flag_clear which writes to an atomic variable and uses memory_order_seq_cst. So it’s a release operation.

Concurrently, thread T2 calls spinlock_lock and in its implementation we used atomic_flag_test_and_set function, which, among other things, reads from an atomic variable using memory_order_seq_cst. So it’s an aquire operation.

If inside spinlock_lock T2 reads from the atomic variable value true it means that either T1 didn’t write false into the atomic variable yet or the write is not visible to T2 yet. Either way, T2 will re-try the operation in the loop.

Once T1 actually writes false in the atomic variable and T2 reads the written value from the same variable, we can tell that atomic_flag_clear inside spinlock_unlock syncrhonizes with atomic_flag_test_and_set inside spinlock_lock.

And at this point, we know that everything that in thread T1 was sequenced before atomic_flag_clear or spinlock_unlock is guaranteed to have happened before atomic_flag_test_and_set and everything that is sequenced after it and spinlock_lock function in the thread T2.

Thus we demonstrated that T2 cannot take ownership of the lock before thread T1 completed all its operations in the critical section and released the lock.

Improved implementation

The name of this section is somewhat misleading - I don’t actually know how much of an improvement this is in practice. That being said, careful reader may have noticed, that earlier I mentioned some other memory ordering options besides memory_order_seq_cst.

Specifically, there were as well the following memory ordering parmaters that would have provided us with the same properties as memory_order_seq_cst:

• memory_order_acquire
• memory_order_release.

memory_order_seq_cst provides the same guarantess as these two memory orderings plus some more. It stands to reason, that if we don’t need those additional guaratees and can use memory_order_acquire and memory_order_release it will give complier and processor more freedom and might yield better relults.

I additionally will introduce here another type of operation in C called a fence. Fences can be used to estabslish a synchronizes with relations in the execution of the program, just like atomic variables, except that they are not tied to any particular location in memory, like atomic variables do.

Finally, I will introduce one last additional type of memory ordering that C standard allows for: memory_order_relaxed. Atomic operations that use memory_order_relaxed do not establish synchronizes with relations in the program execution and, in a way, memory_order_relaxed provides the weekest guarantees across all the memory orderings and allows the most freedom to re-order operations.

NOTE: atomic operations using memory_order_relaxed are still atomic though, meaning that observers will see the operation either complete or not, but will never see intermediate results of an atomic operation using memory_order_relaxed.

With those additional tools and considerations we can rewrite our locks as follows:

void spinlock_lock(struct spinlock *l)
{
    while (atomic_flag_test_and_set_explicit(&l->flag, memory_order_relaxed));
    atomic_thread_fence(memory_order_acquire);
}

void spinlock_unlock(struct spinlock *l)
{
    atomic_thread_fence(memory_order_release);
    atomic_flag_clear_explicit(&l->flag, memory_order_relaxed);
}

Similarly to the analysis above, when atomic_flag_test_and_set_explicit operation in the spinlock_lock sees a value written by atomic_flag_clear_explicit inside spinlock_unlock, the atomic_thread_fence calls in the two functions helps us to establish “synchronizes with” relation.

This implementation might appear to be more intuitive if you think of atomic_thread_fence as a barrier that prevents re-ordering operations. Specifically, atomic_thread_fence(memory_order_acquire) prevents re-ordering of reads and writes that happen after the fence before the fence and atomic_thread_fence(memory_order_release) prevents re-ordering reads and writes before the fence after the fence.

This way we get exactly the property that I started with - operations that happen in the critical section cannot be moved outside of the critical section due to the fences we put around them.

NOTE: the new implementation has two advantages over the previous one - it replaces stronger memory_order_seq_cst with weaker memory_order_acquire and memory_order_release; however, besides that it makes atomic_flag_test_and_set_explicit which is called in the loop inside spinlock_lock use the weakest memory_order_relaxed, so we don’t have to call “a heavy” memory_order_seq_cst atomic operation in a loop.

What about ARM?

So far, all we’ve looked at was provided by the standard of C in an architecture agnostic way. The same spinlock should work just as correctly on ARM machines as it would on Intel machines.

FWIW, C is still called a high-level programming language, so it should as much as practical abstract away the details of the specific hardware and, at least when it comes to memory ordering, it does it well enough for us not to worry about how it would work on ARM, Intel or any other hardware for that matter.

However, it would be interesting to actually see what this implementation actually translates to, so let’s take a look…

llvm-objdump -d spinlock.o 

spinlock.o:	file format elf64-littleaarch64

Disassembly of section .text:

0000000000000000 <spinlock_setup>:
       0: 1f 00 00 39  	strb	wzr, [x0]
       4: c0 03 5f d6  	ret

0000000000000008 <spinlock_lock>:
       8: 28 00 80 52  	mov	w8, #1
       c: 09 7c 5f 08  	ldxrb	w9, [x0]
      10: 08 7c 0a 08  	stxrb	w10, w8, [x0]
      14: 29 01 00 12  	and	w9, w9, #0x1
      18: 49 01 09 2a  	orr	w9, w10, w9
      1c: 89 ff ff 35  	cbnz	w9, 0xc <spinlock_lock+0x4>
      20: bf 39 03 d5  	dmb	ishld
      24: c0 03 5f d6  	ret

0000000000000028 <spinlock_unlock>:
      28: bf 3b 03 d5  	dmb	ish
      2c: 1f 00 00 39  	strb	wzr, [x0]
      30: c0 03 5f d6  	ret

I will start with the spinlock_unlock function given that it’s simpler. strb instruction is just a varian of a regular store instruction. The b suffix just means that this store stores a single byte.

It takes a value from wzr register which is a special register which always reads as 0, so it’s just a fancy way to get 0 value.

And x0, according to the calling convention, contains the first parmater of the function, which in our case would the the struct spinlock pointer.

Putting things together strb wzr, [x0] writes 0 to the first byte of struct spinlock passed as a paramter. Given that struct spinlock consists of just atomic_flag, not hard to see that this writes 0 to the flag.

NOTE: there is nothing specific about the strb instruction that makes the store atomic, that’s because there isn’t any need for that and some stores in ARM are atomic, i.e. indivisable, by default without any additional actions.

The only interesting part of this function is dmb ish instruction. This is a memory barrier instruction and that’s basically what atomic_thread_fence(memory_order_release) translated to in the end - a single instruction.

dmb is a data memory barrier instruction. As per ARM refernce manual, dmb ish prevents re-ordering of read and write operations before the barier with read and write operations after the barrier.

NOTE: one, rather simplistic and inaccurate, way to think about the dmb instruction is that it waits until the relevant operations complete before allowing any other loads or stores, i.e. dmb ish might wait for all loads and stores before the barrier to complete before any new loads and stores would be allowed to start.

Now, let’s take a look at the implementation of the spinlock_lock. We know that it must contain a loop of some form, so let’s figure out where in the code the loop is hidden first.

The key to finding a loop is finding a conditional jump instruction. In this case cbnz is such instruction. As you can see it has two parmaters: register w9 and some address.

This instruction compares the value in the register with 0 and if it’s not the case it will transfer control to the address given as the second paramter. Otherwise the control will go to the next instruction after it.

Looking at the address where cbnz would transfer control in our case we can derive the general structure of the loop:

    mov w8, #1

# before the loop

body:
    # The loop body
    ldxrb w9, [x0]
    stxrb w10, w8, [x0]
    and w9, w9, #0x1
    orr w9, w10, w9
    cbnz w9, body

# after the loop

    dmb ishld
    ret

Let’s tryt to parse the body of the loop next. There are two important instructions to pay attention to here: ldxrb and stxrb.

ldxrb is Load Exclusive Register Byte. This is a special instruction that reads a byte from address in memory, indicated by by address [x0], to register w9.

stxrb is a Store Exclusive Register Byte. This is another special instruction that writes a byte from a register w8 to memory, indicated by address [x0]. However, stxrb is only successfull if the memory indicated by address [x0] has not been modified since the ldxrb instruction.

Whether stxrb was able to successfully write the data or not is recorded in register w10. It would contain 0 if the store operation was successful and 1 otherwise.

ldxrb and stxrb instructions work together with each other and form a pair of operation often refered to as “load linked/store conditional”. These operations basically implement atomic_flag_test_and_set_explicit in our case. And we have to do them in the loop, until the store succeeds, just like it’s written in the C code.

One last finishing touch is dmb ishld instruction. Just like dmb ish instruction we looked at above, it’s a memory barrier instruction. The only difference is that this particular memory barrier prevent loads that happened before the fence to be re-ordered with loads and stores after the fence.

Why the difference? dmb ish that was used earlier would work here as well, but dmb ishld is a weaker barrier that dmb ish. And while dmb ishld is weaker than dmb ish, it’s still enough for correctness, so it was preferred.

Remember that we want loads and stores that happened within the critical section to stay within the critical section and not escape it. In other words, by the time we finish the memory barrier instruction, we want all the effects of the loads and stores to be visible to everyone.

We don’t need to prevent any loads and stores that happen outside of critical section getting inside the critical section, as it’s not needed for correctness.

The only reason why dmb ish was used in the spinlock_unlock is because there is no other weaker barier that would give the right properties in ARM instruction set.

NOTE: let’s think a bit about what properties we actually need here in terms of barriers? In the spinlock_lock function we need to make sure that all loads and stores within the critical section happen strictly after the load from the atomic_flag that atomic_flag_test_and_set does, so we need to prevent re-ordering of all the loads and stores after the barrier with the load before the barrier. Thinking similarly about spinlock_unlock, we want to prevent all loads and stores before the barrier to be re-ordered with the store after the barrier. For the first case we have dmb ishld that provides exactly the properties we need, but ARM architecture does not have the instruction with exactly the properties we need for the latter case, so we have to resort to the next best thing and it’s dmb ish.

Back to sequential consistency

Out of curiousity, does returning back to memory_order_seq_cst produces a different code? Based on what we’ve learned above, it should, but let’s take a look at what this code translates to:

void spinlock_lock(struct spinlock *l)
{
    while (atomic_flag_test_and_set_explicit(&l->flag, memory_order_relaxed));
    atomic_thread_fence(memory_order_seq_cst);
}

void spinlock_unlock(struct spinlock *l)
{
    atomic_thread_fence(memory_order_seq_cst);
    atomic_flag_clear_explicit(&l->flag, memory_order_relaxed);
}

And indeed it does:

llvm-objdump -d spinlock.o 

spinlock.o:	file format elf64-littleaarch64

Disassembly of section .text:

0000000000000000 <spinlock_setup>:
       0: 1f 00 00 39  	strb	wzr, [x0]
       4: c0 03 5f d6  	ret

0000000000000008 <spinlock_lock>:
       8: 28 00 80 52  	mov	w8, #1
       c: 09 7c 5f 08  	ldxrb	w9, [x0]
      10: 08 7c 0a 08  	stxrb	w10, w8, [x0]
      14: 29 01 00 12  	and	w9, w9, #0x1
      18: 49 01 09 2a  	orr	w9, w10, w9
      1c: 89 ff ff 35  	cbnz	w9, 0xc <spinlock_lock+0x4>
      20: bf 3b 03 d5  	dmb	ish
      24: c0 03 5f d6  	ret

0000000000000028 <spinlock_unlock>:
      28: bf 3b 03 d5  	dmb	ish
      2c: 1f 00 00 39  	strb	wzr, [x0]
      30: c0 03 5f d6  	ret

As you can see, with memory_order_seq_cst we now use dmb ish, the strongest barrier of those we’ve seen, both in spinlock_lock and spinlock_unlock. So we do in fact see a difference in the generated code, though it’s a difference in just a single instruction.

How does linux do it?

We looked at how to implement spinlocks in standard C and then looked at what ARM instructions it translates to. I hope I didn’t make any terrible mistakes there that would lead you towards incorrect assumptions about how synchronization works in ARM.

That being said, let’s take a look at how Linux Kernel does it and compare what I created above. Linux Kernel spinlock implementation comes with a complexity of large code base that needs to support multiple different architectures and a lot of tooling (including tooling used to enforce correctness).

Once you get through the complexities, you will find that the actual implementation of ARM spinlocks lives in arch/arm/include/asm/spinlock.h and it’s not that large and complicated.

And even though it’s not that large, it has a few fundamentral differences from the implementation above:

1. It uses a different algorithm
2. It employs an ARM specific relaxation strategy
3. It uses dmb ish barriers in both lock and unlock.

Let’s start with briefly touching at the algorithm it uses. It appears that ARM spinlock implemnetation in Linux Kernel relies on so-called ticket lock algorithm.

Like our algorithm it relies some kind of read-modify-write operation and has a loop in the lock function. However, unlike our algorithm, ticket lock provides additional guarantees of fairness that our algorithm does not have.

The next difference is that Linux Kernel implementation does not just spin in a loop like I did above. Instead it executes in wfe instruction in the loop inside lock implementation while it waits to acquire ownership of the lock.

ARM documnetation describes wfe or Wait For Event instruction as a hint to the CPU that it could enter a low-power state and remain in that state until a wake up event occurs.

It seem to suggest, that ARM CPU can potentially get to a mode of operation that consumes less energy and stay in such a state until something, i.e. another CPU presumably holding the lock, calls sev instruction that will wake it up.

Finally, as you can see, arch_spin_lock function ends with smp_mb and arch_spin_unlock function starts with the same smp_mb call. smp_mb is a memory barrier function, an equivalant of C atomic_thread_fence function if you will.

So Linux Kernel uses the same type of barrier in both lock and unlock functions. And digging through the code code you can indeed find that in ARM, smp_mb function translates into dmb ish instruction, which is a stronger barrier than needed, at least to the best of my understanding.

Instead of conclusion

Hopefully I explored a rather well explored subject of creating a spinlock with details and follwed up with specifics of the memory model for this post not to be way too boring.

I was a bit suprised to find lock in linux kernel forces a full memory barrier. Naturally, I suspected that I was wrong in my understanding of how things work and that’s still certainly a plausible explanation.

That being said, reading doc/Documentation/memory-barriers.txt suggests that lock operation in Linux Kernel indeed should only behave as an acquire operation.

Whether linux kernel implemenetation is too conservative or not in the use of memory barriers, at least from correctness point of view, using stronger and simpler to reason about barriers seems wise given the overall complexity. And I’m not even sure if using a weaker barrier will have a measurable effect.

Hopefully, by the end of this post I will have an example of how to configure paging in AArch64 and will gather some basic understanding of the relevant concepts and related topics along the way.

The End Goal

Setting up simple address translation in AArch64 is not that hard, however it might not be easy to see because of sheer number of different translation modes and various options supported by the architecture.

So, somewhat at odds with how I usually structure my posts, I will start with the end result I want to get and will use this to limit the complicated configuration surface of ARM memory mangement unit that we need to explore to achieve the end result.

By the end of the post I want to configure and test a very simple translation scheme. The translation scheme I chose can be characterized as follows:

1. It will only support a single exception level EL2, so we don’t need to worry about priviledge levels when accessing memory, e.g. there will be no memory that can only be accessed by highly priviledged code or anything of this sort;
2. All memory will be readable, writable and executable in my very simplistic setup;
3. I will use 64 KiB transaltion granule - I will cover brifly what it means later, for now I will only mention that there are 3 supported options (4 KiB, 16 KiB and 64 KiB) and for what this post tries to do it really does not matter much which one we chose, so I picked 64 KiB and will stick with it;
4. I will use translation scheme that have a single input (virtual) address range (the other alternative is to have 2 address ranges);
5. I will only need a single translation stage (the other alternative is to have 2 stages of address translation);
6. Finally, I will setup identity mapping.

If some or all of those things sound like a bunch of giberish to you, don’t worry. Some of those will be clarified later and as for the rest, hopefully by the end of this post you will have good enough bird-eye view of the whole thing to figure out the details on your own.

Device Memory

I first will start from seemingly unrelated topic of caching memory accesses. Putting it very simply and generally, cache memory is a relatively fast memory that can store results of access to a relatively slow memory to speed up the work of a computing system striking a balance between performance and cost.

For example, RAM is faster than HDD, so we can use RAM as a cache for HDD access and store there the results we recently read from HDD or even data that we may want to write to HDD, but didn’t yet. So where a system with enough RAM to replace the whole HDD will be too costly and the system with just HDD will be to slow, as system with RAM as a cache and HDD is somewhere in between.

With that basic idea of the cache, we now will look at the other side of using caches - correctnes. You may have heard a phrase “single source of truth”, this phrase refers to a pattern of organizing systems in such a way when there is an authoritative source of information that contains the latest correct version.

When you introduce caches in the system you create a situation when you don’t have a single source of truth anymore. E.g. when a CPU tries to write something in memory, the write may be cached. In this case the latest correct version of the data will be in the cache. When we en entry from the cache, the memory will contain the latest correct version of the data. So as you can see, we don’t have a single place where we can get the latest correct version of the data - we have to check both cache and memory.

The presence of caches complicates things significantly and we need to explore some of those complications to understand the concept of memory type in ARM, and I will start with the idea of memory mapped device registers.

In modern hardware systems (and actually in the old compute hardware as well), it’s often the case that if you want to interact with a device, the interface you use look like memory access. For example, if you take a look at PL011 to configure the serial interface you need to write a certain magic numbers to certain magic memory addresses. That’s because the registers of the device are mapped to memory, meaning that they have actually memory addresses and attempts to read and write at those addresses result in reading and writing from the device registers.

However, those memory reads and writes have side effects that are not typical for regular memory. Because of that you often may want to have a very tight control over how those reads and writes actually happen.

In ARM it is possible to mark ranges of memory where device registers are mapped as device memory and that gives you a level of control over reads and writes that regular memory accesses don’t have (or don’t allow to do it as easily at least).

ARM specification defines 3 properties of device memory that we may control:

• Gathering (G)
• Reordering (R)
• Early Write Acknowledgement (E).

Gathering is when multiple memory accesses, typically to the same location, are merged together into one memory transaction. In a very simple example, if you program reads from the same memory location twice, without writing anything in between those reads, CPU can gather those reads together and issue just a single read instead of issuing two separate reads.

That makes perfect sense and something that you can expect to see when you access regular memory. After all if both reads read the same memory and there is no reason to believe that this memory would have changed between the reads you can skip an unnecessary read.

On the other hand, if this is not a usual memory, but a memory mapped register it might be undesirable to skip a read. One very simplistic example is when a program wants to wait until the device finishes an action. One way to achieve that is for the device to expose a read-only status register that will set or drop a flag when devices completes an action. In this case, multiple reads from the same address may in fact return different results, even if there are no writes.

Reordering, as the name suggests, is when memory accesses can be re-ordered and issued in a different order from what is encoded in the executed program.

This is somewhat more complicated to explain than gathering, but when you work with regular memory the order of memory accesses does not always affect the end result of your program, but it may affect performance of the program. When it is the case, CPU might potentially re-order those accesses in whatever way it deems more efficient.

With memory mapped device registers such re-ordering may or may not be desirable, however unlike with the regular memory, it’s definitely harder for the CPU to tell when such re-ordering affects visible behavior or the end result of the program, so it may be benefitial to disable re-ordering all together for memory mapped devices.

Early write acknowledgement refers to even more obscure for a regular programmer idea that when you write to some memory mapped device register you may want to wait until the write will fully propagate and device will acknowledge that write.

The early part basically means that the write has to be acknowledged by the device itself and not some intermediary standing between the CPU and the device. Imagine a complicated bus (e.g. PCIe). The bus itself is a complicated device, but we can also connect other devices to the bus including various bridge devices or hubs that just pass messages along.

When we say that we don’t want early write acknowledgement we mean that none of those intermediate devices (e.g. bus itself, bridges, hubs, etc) will acknowledge the write. Instead they just pass the message along to the target device and once the device responds, they pass back the responce as well.

Typically, when we write something we don’t wait for any memory write acknowledgments (at least not explicitly), but in ARM we could wait for it using the DSB barrier instruction in the program and wait until the write fully propagates to the target device explicitly.

Depending on whether early write acknowledgement enabled or disabled the behavior of the DSB instruction may yield different results.

Each of the three properties or behaviors can be allowed or disallowed in ARM memory configuration. AArch64 supports the following combinations of those:

1. nGnRnE - gathering, reordering and early write acknowledgement are not allowed;
2. nGnRE - gathering and reording are prohibitted, but early write acknowledgement is allowed;
3. nGRE - gathering is prohibited, but reordering and early write acknoweldgement are allowed
4. GRE - gathering, reording and early write acknowledgment are allowed.

And it’s actually up to us to configure which memory type system will use when accessing memory. Naturally, given that nGnRnE is the configuration that prohibits all the strange memory behaviors, it’s the simplest device memory type to reason about. On the other hand, device memory accesses with nGnRnE memory type may perform somewhat worse given that they reduce the processing unit flexbility to optimize memory accesses.

NOTE: You an find more details about device memory and additional pointers in the section B2.7.2 “Device Memory” of Arm Architecture Reference Manual for A-profile architecture.

Normal Memory

The normal memory, unlike the device memory that we covered above, does not produce side effects that a CPU cannot expect when we access it, so in a way working with normal memory is much simpler than working with device memory.

However, normal memory can still be used for communications. For example, two CPUs of a multi-processing system may communicate with each other via memory. We can also use normal memory for communicating between CPU and a device, as long as they have access to the same memory.

In cases where we use regular memory for communcation, either explicitly or implicitly, caches can still result in various strange and un-intuitive effects. To avoid those effects different parts of the compute system (e.g. CPUs, devices, etc) have to communicate with each other to learn of the state of various hardware caches and modify those caches in a way that makes sense.

Such communcation protocol that creates a consistent shared view of memory in presence of various caches is commonly refered to as cache coherency protocol. There are probably many different cache coherency protocols that exist and I will not discuss them in this post. However, it’s probably not going to be a surprise for you if I said that depending on what parts of the system have to be kept in sync by cache coherency protocols, the protocol may be more or less complicated, more or less performant, more or less power efficient, etc.

To put it another way, layout and number of components may affect the how well the cache coherency protocol works. Not a far leap from this is to imagine a system that may support multiple different cache coherency protocols depending on what parts of the system we want to keep in sync with each other.

That’s where the concept of memory sherability comes into play. Normal memory shareability is about communications via memory between different parts of the system and required synchronization.

ARM defines three different sharebility types for normal memory:

• Non-sharebable
• Inner shareable
• Outer shareable

Non-shareable memory is, as the name suggest, memory not used for communcations and therefore there is not need to maintain cache coherency for that memory.

Basically, if we for example had a memory range that is used exclusively by a single CPU, meaning that nothing else, besides that CPU, reads or writes from and to that memory, we don’t have to maintain cache coherency for that memory range at all.

Inner and outer sharebavle normal memory is used for communication between different parts of the system. The different between the two is rather hard to explain coherently because ARM specification actually leaves it up to the hardware to decide.

However, the general idea is that different parts of the system will be kept in sync for inner sharable memory and for outer shareable memory. When a CPU or device access a memory range that is marked as inner shareable, hardware will use the cache coherency protocol that will keep all the CPUs and devices in the same inner shareability domain in sync. When a CPU or devices access a memory marked as outer shareable, a cache coherency protocol that keeps all the CPUs and devices in the same outer sharebility domain in sync will be used.

ARM specification says that each device or CPU (each agent) belongs to a single inner shareablity domain and a single outer sharebility domain. It additionally says that all devices in the same inner sharebility domain also must belong to the same outer shareability domain. So agents, inner sharebility domains and outer sharebility domains form a hierarchy.

I speculate that the idea here is that keepin agents inside a single sharebility domain in sync may potentially be faster or more power efficient, then keeping all the agents in the outer sharebility domain in sync. So, if we know that a particual memory is only used by agents withing a single inner shareability domain we may mark it as inner shareable and make accesses to the memory a bit more efficient.

On the other hand, if a memory range is used by devices from different inner shareability domain, but within the same outer shareable domain, we have to mark it as outer shareable.

So far so good, but how do we know what agents belong to what inner/outer shareable domain? ARM specification does not actually say that explicitly, so ultimately it’s up to the specific hardware implementation.

ARM specification, however, provides a guidance that the inner shareable domain is expected to include all the CPUs controlled by the same OS/hypervisor. If I understand it correctly, in practice it means that all the CPUs that an OS has available are withing the same inner shareability domain.

NOTE: You an find more details about sharebaility attributes of normal memory in the section B2.7.1 “Normal Memory” of Arm Architecture Reference Manual for A-profile architecture.

Normal Memory Caching Mode

The other attribute of normal memory is cacheability. ARM supports 3 options for configuring cache behavior:

• No caching
• Write-through caching
• Write-back caching

The first of those options is self explanatory. Write-through and write-back refer to two well known caching strategies. In case of write-through cache when we write a value to memory, it’s written to both cache and memory right away.

In the case of write-back cache, when we write a value to memory, it’s written in cache only. The write to memory happens when, for whatever reason, we need to evict the value from the cache.

At least to me, write-back caching strategy appears a bit more natural, as slow write to memory happens asynchronously, but write-through strategy allows for a nice propety that the write will be visible in memory without delay.

In addition to caching strategy, ARM also supports so called allocation and transient hints. What those hints do if anything is not exactly well defined and is left up to the specific implementation.

That being said, at least the idea of those hints is to indicate to hardware that a particular memory would benefit from caching. Whether cache is going to be effective or not is really a property of a workload, so those hints are intended to convey something about the workload that access the memory.

Caching strategy can be configured on two levels: inner and outer. What is the exact scope of the inner and outer level is implementation defined, but to give you an idea think of multiple levels of caches. For example, in a multiprocessor system each CPU may have their own cache and they may also have a shared cache. In this case shared cache might belong to the outer level and the cache on each CPU is inner.

Configuring Memory Types

So now we have some idea about memory types and what properties we can configure for memory. Let’s try to put it in practice. Before we start though I’d like to warn you that the practice is going to be a bit underwelming at this step.

The type of memory that a system uses are “configured” in MAIR_ELx register. This is a 64 bit register, that could be thought of as an array of 8 entries. Each entry describes a type of memory (device vs normal) and its attributes and is 8 bits long.

NOTE: x in this case corresponds to the ARM exception level.

An entry describing a device memory type would follow the binary pattern 0b0000xx00, where xx is one of the following:

1. 0b00 - nGnRnE
2. 0b01 - nGnRE
3. 0b10 - nGRE
4. 0b11 - GRE.

Putting it all together, if you want to encode nGnRnE device memory you would use 0b00000000 = 0x00 for this and if you wanted to encode nGnRE device memory you would use 0b00000100 = 0x04.

Encoding of a normal memory type is somewhat more complicated and follows the pattern 0bxxxxyyyy. xxxx defines caching strategy on the outer level and yyyy defines the caching strategy on the inner level.

NOTE: To avoid overlap with device memory, xxxx and yyyy cannot be zeros.

The encoding of caching configuration has the following options:

1. 0b00RW - write-through normal memory with transient hint bit set
2. 0b0100 - non-cacheable normal memory
3. 0b01RW - write-back normal memory with transient hint bit set
4. 0b10RW - write-though normal memory without transient hint bit set
5. 0b11RW - write-back normal memory without transient hint bit set

The values of R and W are read and write hint bits. Note that in case of write-through normal memory with transient hint bit, R and W cannot be 0 at the same time because it will conflict with the encoding of the device memory.

For example, normal non-cacheable memory (for both inner and outer levels) would be encoded as 0b01000100 = 0x44. Normal write-back cacheable (for both inner and outer level) memory without transient hint bit set and with read/write hint bits set would be encoded as 0b11111111 = 0xff.

NOTE: The encoding format of each entry can be find in the description of the MAIR_ELx register, e.g. D19.2.101 MAIR_EL2, memory Attribute Indirection Register (EL2).

Now, we can write the memory type configurations in any of the 8 slots in the MAIR_ELx refister, we just need to remember what slot do we use for what memory type as it will become important later.

Given that ultimately MAIR_ELx is just a 64 bit register, writing to the register is just writing a 64-bit value to a system register. In Aarch64 there is a special instruction for writing to a system register - msr (Move to System register). Reading from a system register is done via mrs instruction. Here is how the code in assembly might look like:

mair_el2_store:
  msr mair_el2, x0
  ret

mair_el2_load:
  mrs x0, mair_el2
  ret

NOTE: In the code above I rely on a calling convetion in which an argument is passed to a function in x0 register and the value is returned from a function also in x0 register, so mair_el2_store takes the value we want to write to MAIR_EL2 in x0 register and mair_el2_load returns the current value of MAIR_EL2 in x0 register.

Now, what would we write into the register? For the sake of being specific let’s say that we will use the following memory types:

1. Normal inner/outer write-back cacheable memory with read/write hint bits and without transient hint bit in slot 0
2. Normal non-cacheable memory in slot 2
3. nGnRnE device memory in slot 3
4. ‘nGnRE’ device memory in slot 4

The rest of the slots we will not use at all and they will be filled with zeros (which also happens to mean that they will describe nGnRnE device memory). So together it gives us MAIR value equal to 0x4004400ff = 17184325887.

And a complete code might look something like this:

#define MT_NORMAL             0u
#define MT_NORMAL_NO_CACHING  2u
#define MT_DEVICE_NGNRNE      3u
#define MT_DEVICE_NGNRE       4u

static const unsigned NORMAL_MEMORY = 0xff;
static const unsigned NORMAL_MEMORY_NO_CACHING = 0x44;
static const unsigned DEVICE_NGNRNE = 0x00;
static const unsigned DEVICE_NGNRE = 0x04;

static uint64_t mair_attr(uint64_t attr, unsigned idx)
{
    return attr << (8 * idx);
}

void memory_cpu_setup(void)
{
    void mair_el2_store(uint64_t);

    const uint64_t mair =
        mair_attr(NORMAL_MEMORY, MT_NORMAL) |
        mair_attr(NORMAL_MEMORY_NO_CACHING, MT_NORMAL_NO_CACHING) |
        mair_attr(DEVICE_NGNRNE, MT_DEVICE_NGNRNE) |
        mair_attr(DEVICE_NGNRE, MT_DEVICE_NGNRE);

    mair_el2_store(mair);
}

You can also refer how Linux Kernel configures the MAIR register (though in their case it’s MAIR_EL1 register) by checking the __cpu_setup function.

The value Linux Kernel uses to initialize MAIR_EL1 can be found in proc.S and it’s quite similar to the example I showed above with just a few differences.

Some of you may be confused at this point as to what did we actually configure here. Well, to tell you the truth we didn’t actually configure anything yet. To give you a hint into what purpose the MAIR register actually serve let’s look at the name of the register. MAIR stands for Memory Attribute Indirection Register.

Basically, the actual configuration that will determine how we will access memory (including it’s type) will live in a different place. However, instead of encoding memory type directly there we will just use an index of a slot in the MAIR register instead - thus the name of the register.

Why is that? To encode memory type and related attributes we need 8 bits, but to encode an index in the MAIR register we just need 3 bits.

Translation Table

The next item on the agenda is translation table. Translation table is basically a map-like hierarchical data structure that describes:

1. How virtual or logical addresses should be mapped to the physical addresses
2. What kinds of access are allowed and disallowed for different virtual addresses (e.g. can we read something at a given virtual address, can we write there, can we execute code at that virtual address, etc).

As I mentioned earlier I will setup identity mapping translation table. That basically means that virtual address X will be translated by this translation table to a physical address X. To even further simplify the matters, the translation table will not even need to be hyerarchical at all - it’s going to consist of just a flat array of entries.

A typical translation table usually looks like a tree with several levels (like 3, 4 or 5 levels, depending on the specific configuration). Each node of the tree would contain an array of entries, each entry either contains a pointer to a node at a higher level or directly encodes how to map vritual addresses corresponding to the entry to the physical addressed. The pointer to the root of the tree is stored in TTBRx_ELy register (or VTTBRx_ELy).

The data structure is rather simple to comprehend once you have an idea of how it’s used by hardware, so let’s take a look at an example. Say a program tries to access memory at virtual address X. To find the actual physical address corresponding to X process has to “walk” the page table.

It would first start by going to the TTBRx_ELy register and find the physical address of the root of the translation table. Let’s for the sake of being specific say that code executes in EL2, so the register the process will look at will be TTBR0_EL2.

NOTE: Naturally the address has to be physical, otherwise processor will have to translate it going into an infinite loop.

From TTBR0_EL2 process will take the physical address of the level 1 translation table. This table basically is just a massive array of 64-bit entries. The exact size of the translation table, format of each entry and so on depends on the configuration.

For the sake of being specific and as was mentioned earlier, I will be using 64 KiB translation granule and in this case the root node of the translation table may contain up to 1024 entries and the minimum of 64 entries depending on the configuration.

The next step is to find the entry corresponding to the virtual address X. In order to do that processor will look at a few significant high bits in the value X and use them as an index in the table.

To cover the whole 1024 entries you need 10 bits and in our case processor will look at bits X[51:42] to decide which entry from the table it needs. For the case when the root table only contains 64 entries, we need just 6 bits, so in this case the process will look at X[47:42].

NOTE: Even though the virtual address typically would be described as a 64-bit value, as you can see, bit 52 and higher are not actually being used; that’s not a mistake, but even a 52-bit virtual address space is so large, that it’s not that big of constraint at the moment.

Now processor knows the right entry in the level 1 table and it can decode it. There a few options for what the entry could describe:

1. The entry might be invalid - that would mean that virtual address X is not mapped to any physical address, the translation will stop and processor will report an error;
2. The entry might be a so called block entry - that means that this entry directly describes how virtual address X is mapped to a physical address; the translation will stop and processor will learn the right physical address;
3. The entry might point to the next level page table (e.g. level 2 page table in our example) - that means that processor will continue page table walk to resolve the physical address.

Let’s say we reached the case 3, so the entry processor just looked at contained a physical address of a level 2 page table. level 2 page table is very similar to the level 1 page table in structure - it’s an array of 64-bit entries, up to 8129 entries long.

NOTE: Tables at level 2 and level 3 always contain 8192 entries and require 13 bits for an index unlike the table at the level 1.

To find the right entry in the level 2 page table, processor would look at the bits X[41:29] of the virtual address this time to find the right entry in the table. As for level 1 there are the same 3 options available for the type of the entry in the table, so the “walk” may stop there or continue to the level 3.

With 64 KiB translation granule this tree can have up to 3 levels. So a level 3 page table cannot point to a level 4 page table anymore and must contain either invalid entries that stop the translation process or direct description of how virtual address corresponding to the entry maps to the physical address.

Let’s assume that “walking” the translation table we finally reached an entry at level 3 that describes how to translate virtual address to a physical address. How would this entry look like and how do we use it to get a physical address?

The entry at the level 3 like that should contain an address of a contiguous 64 KiB long range of physical memory - that’s what we call a physical page. If we take unused bits of the X and use them as an offset within the page we will get a physical address.

E.g. bits X[63:52] can be ignored, we used bits X[51:42] as index in the level 1 table, bits X[41:29] as index in the level 2 table and bits X[28:16] as index in level 3 table, which leaves us with X[15:0] unused - those unusued bits are the offset inside a 64 KiB physical page we need and so we can form the final address by adding up the physical address of the page and offset of the page together.

NOTE: So page table is basically a kind of radix-tree or a prefix tree of some sort.

Translation Table Entry Format

Now, when we have a general idea of how translation tables look like and how they are used, we will create one. Just like in the example above we will use 64 KiB translation granule - which basically means that we will use 64 KiB physical pages. However, instead of creating all the 3 levels of page tables we will cut the “walk” short at the level 1 by using that describe mapping of virtual addresses to physical addresses directly instead of point to a higher level tables.

In general each entry format includes type of the entry, physical address and some attributes. There are multiple different attributes that we can set in the translation table entry, but I will cover only a small subset of those and assume the rest to be set to 0.

Here are the attributes we are going to set:

1. bits [47:16] - will contain a 64 KiB aligned physical address of a block; it will not be a physical address of 64 KiB page, but an address of 4 TiB contiguous physical memory block because that’s the size of memory a single entry at level 1 is responsible for;
2. bits [9:8] - sharebility attributes; we will use inner sharebale for everything and that is encoded as value 0b11;
3. bits [7:6] - access permission bits; we will make everything writable and that is encoded as value 0b01;
4. bits [4:2] - index in the MAIR register for the corresponding memory type entry; I will use 0 there which would mean that all memory will be normal memory as was configured in the example above;
5. bits [1:0] encode the type of the entry and in our case, bit 1 has to contain value 0 and bit 0 have to contain value 1.

Addtionally, we will limit ourselves to 48-bit large physical address space for now, so we will only need 64 entries and not maximum possible 1024 entries in the root table for now.

In the code the whole setup might look like this:

#define PF_TYPE_BLOCK      ((uint64_t)1 << 0)
#define PF_MEM_TYPE_NORMAL ((uint64_t)MT_NORMAL << 2)
#define PF_READ_WRITE      ((uint64_t)1 << 6)
#define PF_INNER_SHAREABLE ((uint64_t)3 << 8)
#define PF_ACCESS_FLAG     ((uint64_t)1 << 10)

void ttbr0_el2_store(uint64_t ttbr);

void paging_idmap_setup(void)
{
    static uint64_t idmap[64] __attribute__ ((__aligned__(512)));

    const uint64_t block_size = 0x40000000000ull;
    const uint64_t block_attr =
        PF_TYPE_BLOCK |
        PF_MEM_TYPE_NORMAL |
        PF_READ_WRITE |
        PF_INNER_SHAREABLE |
        PF_ACCESS_FLAG;
    uint64_t phys = 0;

    for (size_t i = 0; i < sizeof(idmap)/sizeof(idmap[0]); ++i) {
        idmap[i] = phys | block_attr;
        phys += block_size;
    }

    ttbr0_el2_store((uint64_t)idmap);
}

NOTE: I had to forecfully align idmap to 512 bytes boundary, becaus it is one of the requirements of the AArch64 architecture that the root table as well as all other tables have to be aligned on the size of the table.

The definition of ttbr0_el2_store function might look something like this:

ttbr0_el2_store:
    msr ttbr0_el2, x0
    ret

Given that TTBR0_EL2 is also a system register, just like MAIR_EL2 that we saw above, the function looks very similar to mair_el2_store.

NOTE: The details of the format of various translation table entries can be found in section D8.3 Translation table descriptor format of Arm Architecture Reference Manual for A-profile architecture.

NOTE: I didn’t explain the meanining of the PF_ACCESS_FLAG, but you soon will see that it is not only present in the code snippet above, but also in the Linux Kernel implementation. Without that flag the page table will not work unless we tell hardware to manage the access bit automatically - without it attempts to translate address will result in a Data Abort.

Enabling MMU

Let’s take a look at what has been done so far… We created a very simplistic translation table and saved a pointer to it to the right register. At this point the translation table is not actually being used, because we didn’t configure and enable MMU yet. So let’s do that.

ARM supports multiple different address translation schemas and for each of those there are multiple different configuration parameters, so let’s try to recall what parameters do we need to configure:

1. Translation granule - we have a choice between 4 KiB, 16 KiB and 64 KiB, remeber that I decided at the beginning that we will use 64 KiB granule;
2. We will use a single contiguous VA range, instead of splitting it in lower and higher halfs;
3. We will only support EL2 exception level for now;
4. Finally, we will only have a single translation stage.

Looking at section D8.1.2 Translation regimes from the Arm Architecture Reference Manual for A-profile architecture, you can see the list of the supported translation regimes. Among those we need so called “Non-secure EL2 translation regime”.

NOTE: I mostly ignored the topic of security states all together so far and I don’t intend to cover it, so going forward just assume that everything we do happens in non-secure state. I also ignore the topic of realm state, so please ignore those as well and assume that we are not using it.

NOTE: When documentation says something like “EL1&0” in the translation scheme description, it means that the translation scheme supports multiple exception levels, e.g. “EL1&0” supports EL1 and EL0.

So how can we tell the CPU to use “Non-secure EL2 translation regime”? Once you know what translation scheme you want to use, documentation provides a pretty clear answer:

1. CPU must be in non-secure state and in EL2 - I just assume that these conditions hold true and we don’t need to do anything to make it true;
2. The value of HCR_EL2.E2H bit is 0.

NOTE: In case the CPU is in secure state or not in EL2, we can change it if the CPU supports changing to EL2 at all, but to simplify an already lengthy post, I omit details of how to do it.

So we need to make sure to reset bit E2H in the HCR_EL2 register to 0 to configure what we want. We already saw multiple times how to manipulate system registers in Aarch64, so the following code should look very familiar:

hcr_el2_store:
    msr hcr_el2, x0
    ret

hcr_el2_load:
    mrs x0, hcr_el2
    ret

Register HCR_EL2 is a 64 bit register, and E2H is bit 34 of that register.

Let’s take a look at the translation granules now. Section D8.1.1 Translation granules of the Arm Architecture Reference Manual for A-profile architecture implies that not all translation granule sizes may be supported on each Arm implementation.

We can check if 64 KiB translation granule is supported by looking at ID_AA64MMFR0_EL1 register. This is a readonly feature register. It exists to report what optional features are supported by the underliyng hardware.

To check that 64 KiB granule is supported we need to look at bits from 24 to 27 (also known as TGran64). When all bits are zeros it means that 64 KiB granule is supported. So we need one additional function to read this register:

id_aa64mmfr0_el1_load:
    mrs x0, id_aa64mmfr0_el1
    ret

Assuming that we confirmed that 64 KiB granule size is actually supported by hardware and we want to enable it, how do we do that? For that we need to program bits TG0 (bits from 14 to 15) of TCR_EL2 register. To configure 64 KiB translation granule we need to write there values 0b01.

There are a couple of additional things that I would like to cover here:

1. Size of the physical address space;
2. Size of the virtual address space.

ARM basically can support different sizes of VA address and physical address. When it comes to the translation table it basically controls how many bits of the virtual address CPU will consider when doing a lookup in the translation table. It specifically affects lookups at the level 1.

The size of the physical address space affects how CPU will interpret physical addresses in the translation table and how many bits it will take into consideration.

For the translation table we created in the example above we assumed both virtual and physical address spaces to be 48 bit, so we want configuration compatible with that.

ARM requires that the size of the address produced by address translation cannot be larger than the size of the supported physical address.

To find the maximum supported size of the physical address space we need to look at bits PARange (bits from 0 to 3) of the ID_AA64MMFR0_EL1 register.

And the size of the output address of the translation scheme is configured via bits PS (bits from 16 to 18) of TCR_EL2 register. The TCR_EL2.PS bits have the same encoding as ID_AA64MMFR0_EL1.PARange bits, so in principle we can just copy those.

NOTE: it’s ok to have physical addresses outside of the physical address space in the translation table, as long as we don’t actually access them, so even if the translation table we created above uses physical addresses that are too large, we should still be fine, since we should never need to access those.

How many bits of the virtual address the translation scheme can use depends on multiple paramters, but for basically for 64 KiB granules it should always be possible to support at least 48 bit virtual addresses.

To actually configure the number of significant bits of the virtual address we should write to bits T0SZ (bits from 0 to 5) of the TCR_EL2 register. And the number of significant bits of the virtual address is determined as 64 - T0SZ.

So if we want to configure 48 bit virtual addresses, then in bits T0SZ we need to write the value 16.

There are some other configuration bits, but let’s ingore them for now and try to put all the things together in one example. The final bit that we need in order to make it happen is to actually enable address translation.

For that we need one more system register SCTLR_EL2. There are couple of relevant bits in the register:

1. M (bit 0) - when set to 1 it enables address translation;
2. EE (bit 25) - endianness of data access, when 0 CPU uses little-endian (and that’s what we are going to use), otherwise the CPU uses big-endian.

So we need a couple more rather familiar functions:

sctlr_el2_store:
    msr sctlr_el2, x0
    ret

sctlr_el2_load:
    mrs x0, sctlr_el2
    ret

And we now are ready to put all things together. I will update memory_cpu_setup function introduced earlier as follows:

static const unsigned HCR_EL2_E2H_OFFSET = 34;

static const uint64_t TCR_EL2_TG0_MASK = 0xc000ull;
static const uint64_t TCR_EL2_TG0_64KIB = 0x4000ull;
static const uint64_t TCR_EL2_PS_MASK = 0x70000ull;
static const unsigned TCR_EL2_PS_OFFSET = 16;
static const uint64_t TCR_EL2_T0SZ = 0x1full;
static const uint64_t TCR_EL2_T0SZ_48BITS = 0x10ull;
static const uint64_t TCR_EL2_HA_MASK = 0x200000ull;
static const uint64_t TCR_EL2_HA_DISABLED = 0x000000ull;

static const uint64_t SCTLR_EL2_M_MASK = 0x1ull;
static const uint64_t SCTLR_EL2_M_ENABLE = 0x1ull;
static const uint64_t SCTLR_EL2_EE_MASK = 0x2000000ull;
static const uint64_t SCTLR_EL2_EE_LITTLE_ENDIAN = 0x0ull;

static const uint64_t ID_AA64MMFR0_EL1_TGRAN64_MASK = 0xf000000ull;
static const uint64_t ID_AA64MMFR0_EL1_TGRAN64_ENABLED = 0x0ull;
static const uint64_t ID_AA64MMFR0_EL1_PARANGE_MASK = 0xfull;

enum error_code memory_cpu_setup(void)
{
    void mair_el2_store(uint64_t mair);
    uint64_t hcr_el2_load(void);
    void hcr_el2_store(uint64_t hcr);
    uint64_t tcr_el2_load(void);
    void tcr_el2_store(uint64_t tcr);
    uint64_t sctlr_el2_load(void);
    void sctlr_el2_store(uint64_t sctlr);
    uint64_t id_aa64mmfr0_el1_load(void);

    const uint64_t mair =
        mair_attr(NORMAL_MEMORY, MT_NORMAL) |
        mair_attr(NORMAL_MEMORY_NO_CACHING, MT_NORMAL_NO_CACHING) |
        mair_attr(DEVICE_NGNRNE, MT_DEVICE_NGNRNE) |
        mair_attr(DEVICE_NGNRE, MT_DEVICE_NGNRE);

    mair_el2_store(mair);
    paging_idmap_setup();

    const uint64_t mmfr0 = id_aa64_mmfr0_el1_load();
    if ((mmfr0 & ID_AA64MMFR0_EL1_TGRAN64_MASK) !=
            ID_AA64MMFR0_EL1_TGRAN_ENABLED) {
        return ERR_NOT_SUPPORTED;
    }

    uint64_t tcr = tcr_el2_load();
    uint64_t hcr = hcr_el2_load();
    uint64_t sctlr = sctlr_el2_load();

    hcr &= ~((uint64_t)1 << HCR_EL2_E2H_OFFSET);
    tcr = (tcr & ~TCR_EL2_TG0_MASK) | TCR_EL2_TG0_64KIB;
    tcr = (tcr & ~TCR_EL2_PS_MASK) |
            ((mmfr0 & ID_AA64MMFR0_EL1_PARANGE_MASK) << TCR_EL2_PS_OFFSET);
    tcr = (tcr & ~TCR_EL2_T0SZ) | TCR_EL2_T0SZ_48BIT;
    tcr = (tcr & ~TCR_EL2_HA_MASK) | TCR_EL2_HA_DISABLED;

    sctlr = (scltr & ~SCTLR_EL2_EE_MASK) | SCTLR_EL2_EE_LITTLE_ENDIAN;
    sctlr = (sctlr & ~SCTLR_EL2_M_MASK) | SCTLR_EL2_M_ENABLE;

    tcr_el2_store(tcr);
    hcr_el2_store(hcr);
    sctlr_el2_store(sctlr);

    return OK;
}

Testing

How can we test that address translation was enabled and indeed works? One way to quickly verify that address translation is happening is to map two different ranges of the virtual address space to the same range of the physical address space. This way you would essentially create two different views of the same physical memory, and to test it you can write something using one virtual address and read the same data back using a different virtual address.

Let’s try to do that in a quick, dirty and not very generic way. This is also going to be a good exercise to explain effects of the TLB cache along the way.

I’m not going to change fundamentally the structure of the translation table - it will still remain a simple array of 64 entries each describing how a contiguous 4TiB long region of virtual address space maps on a contiguous 4TiB long region of the physical memory. Instead, I’m going to pick one entry out of 64 and point it to a different area of the physical memory.

The way my test system is configured is as follows:

1. It has 128 MiB of actual physical memory (not memory mapped registers);
2. The physical memory is located in the physical address space in [0x40000000; 0x48000000).

Looking at the bits [47;42] of 0x48000000, you can see that those bits contain only zeros. That means that the whole memory range in our identity translation table, is currently mapped by the entry with the index 0. That’s the entry I will duplicate.

Now, we need to find where exactly in our virtual address space we want to duplicate. Any range that the code currently does not use will work fine for this, so I will use entry with the index 1.

NOTE: I used the entry that does not contain any physical memory or any memory mapped device registers that I’m using, though strictly speaking for memory mapped device registers the identity mapping I created is not really good as it maps all the memory using the same memory attributes.

What would we expect to see when we copy entry 0 to entry 1 in our simplistic translation table?

Entry 0 is responsible for mapping all the virtual addresses in range [0x0; 0x40000000000). Entry 1 is responsible for mapping all the virtual addresses in range [0x40000000000; 0x80000000000). And both will point to the same physical address range [0x0; 0x40000000000).

So anything we write by address X in range [0x0; 0x40000000000), can be read back by address X + 0x40000000000. And opposite is also true, anything we write by address Y in the range [0x40000000000; 0x80000000000), can be read back by address Y - 0x40000000000.

So let’s create a simple test function:

enum error_code memory_cpu_setup_test(void)
{
    /*
     * Given our setup from program point of view this array will be located
     * in memory in the virtual address range [0x0; 0x40000000000).
     */
    static char message[32];

    /*
     * Let's make changes to our translation table so that both
     * [0x0; 0x40000000000) and [0x40000000000; 0x80000000000) virtual address
     * ranges point to the same physical memory.
     */
    uint64_t *translation_table = (uint64_t *)ttbr0_el2_load();
    uint64_t old_entry = translation_table[1];

    translation_table[1] = translation_table[0];

    /*
     * Let's verify that now both [0x0; 0x40000000000) and
     * [0x40000000000; 0x80000000000) point to the same physical memory by
     * writing data using one of the two address ranges and reading it back
     * using a different address range.
     */

    static const uint64_t shift = 0x40000000000ull;
    char *original = message;
    char *mirrored = (char *)((uintptr_t)message + shift);

    strncpy(original, "Ping!", sizeof(message));
    if (strncmp(mirrored, "Ping!", sizeof(message)) != 0) {
        return ERR_INVALID_ARGUMENT;
    }

    strncpy(mirrored, "Pong!", sizeof(message));
    if (strncmp(original, "Pong!", sizeof(message)) != 0) {
        return ERR_INVALID_ARGUMENT;
    }

    translation_table[1] = old_entry; 

    return OK;
}

Hopefully the code of the function is self explanatory. And probably if you run this function you will indeed observe the desirable results of the translation table manipulations.

However, I will use this opportunity to draw attention to yet another caching side effect that is important. The test function modified the content of the translation table while it was being used.

Leaving aside potential race conditions associated with this, the content of the translation table is cached by the processor using it. If you think about it, enabling address translation without any caching would means that any access to memory will require several additional access to memory just to resolve the physical address.

For example, with the translation table as I set it up earlier, every memory access will translate to two memory acesses:

1. Read the translation table entry corresponding to the virtual address to find the physical address;
2. Read the data at the given physical address.

With more realistic translation tables, you may have 3, 4 or 5 levels in the translation table, so each memory access would require 5 memory accesses just to translate virtual address to a physical address. That’s way too much overhead! So to reduce the impact, processors do use a special cache for the address translation.

So when we update translation table like I did above, we need to make sure that the translation cache, also commonly known as Translation Lookaside Buffer or TLB, has to be updated accordingly as well. And, at least for ARM, that does not happen automatically, and the code has to inform the processor, that TLB has to be updated after updating translation table.

With that in mind, we can refer to the section D8.14.1 “Using break-before-make when updating translation table entries” of the Arm Architecture Reference Manual for A-profile architecture for the recommended way of doing it.

The reference manual suggests to replace the entry with an invalid entry first and then with the entry we actually want to see. And on top of that the procedure is heavily reinforced with memory barrier instructions along the way. This procedure does seem somewhat excessive for our use case, but let’s implement it nontheless.

First, we need a few support functions. A few functions implementing the right memory barriers and another invalidating TLB.

pt_update_barrier:
    dsb ishst
    ret

pt_tlbi_barrier:
    dsb ish
    ret

NOTE: It’s a bit excessive to create a whole function for just a varian of dsb instruction, but it does not require to introduce inline assembly or try to map standard C memory barrier functions to ARM instructions, so it’s simpler this way.

The argument of the dsb instruction specifies what type of a barrier behavior we want. The argument ishst, to put it simplistically, requires the dsb instruction to wait for all the previous memory writes to complete and their effects to become visible to everyone in the same inner shareable domain (specifically, other CPUs that potentially may access the same memory).

We will call pt_update_barrier after we modify the translation table entry to make sure that all the updates are visible.

The argument ish expands the scope of the dsb instruction a little bit by requiring all reads to be completed in addition to writes, so dsb #ish is a “stronger” barrier compared to dsb #ishst. According to the paragraph “Data Synchronization Barrier (DSB)” in section B2.3.12 Memory Barriers of the reference manual, it takes a dsb instruction with both read and write access considered to make sure that TLB invalidation completed. So that’s the barrier we will use after actually invalidating TLB entries to make sure that the effects of it are visible.

Second, we need a way to invalidate potential TLB entries. Section D8.14.5 “TLB maintenance instructions” describes the set of available ARM commands that do this for a wide variety of potential use cases. That’s quite a complicated reading, but here is a clue that might help to find a simple version of the tlbi instruction that works for our use case: it does not make much of a difference to us whether we consider just the last level of the translation table walk or all the levels, since we have just a single level anyway. So we can use the version of the instruction that takes just a single virtual address.

NOTE: Also keep in mind that we are working with a single stage translation table, in EL2 exception level and care only about internal shareability domain.

TL;DR: We need to use tlbi vale2is instruction and wrapping it into a function that takes a VA address gives us the following code:

tlb_invalidate_page:
    lsr x0, x0, 12
    tlbi vale2is, x0
    ret

This function takes just one argument - virtual address within the range that we want to invalidate. It will invalidate cache for the last level of the translation table walk, keeping all the previous levels in cache. As I mentioned earlier it does not make much of a difference to us, but it’s quite important to avoid dropping from the cache what can stay there in the case of real translation tables that may have multiple levels.

With those helper functions, the test function will change as follows:

static void tlb_invalidate_address(uint64_t virtual_address)
{
    void pt_update_barrier(void);
    void pt_tlbi_barrier(void);
    void tlb_invalidate_page(uint64_t);

    pt_update_barrier();
    tlb_invalidate_page(virtual_address);
    pt_tlbi_barrier();
}

enum error_code memory_cpu_setup_test(void)
{
    /*
     * Given our setup from program point of view this array will be located
     * in memory in the virtual address range [0x0; 0x40000000000).
     */
    static char message[32];

    /*
     * Let's make changes to our translation table so that both
     * [0x0; 0x40000000000) and [0x40000000000; 0x80000000000) virtual address
     * ranges point to the same physical memory.
     */
    const uint64_t invalid_entry = 0x0ull;
    static const uint64_t shift = 0x40000000000ull;
    uint64_t *translation_table = (uint64_t *)ttbr0_el2_load();
    uint64_t old_entry = translation_table[1];

    translation_table[1] = invalid_entry;
    tlb_invalidate_address(shift);
    
    translation_table[1] = translation_table[0];
    tlb_invalidate_address(shift);

    /*
     * Let's verify that now both [0x0; 0x40000000000) and
     * [0x40000000000; 0x80000000000) point to the same physical memory by
     * writing data using one of the two address ranges and reading it back
     * using a different address range.
     */

    char *original = message;
    char *mirrored = (char *)((uintptr_t)message + shift);

    strncpy(original, "Ping!", sizeof(message));
    if (strncmp(mirrored, "Ping!", sizeof(message)) != 0) {
        return ERR_INVALID_ARGUMENT;
    }

    strncpy(mirrored, "Pong!", sizeof(message));
    if (strncmp(original, "Pong!", sizeof(message)) != 0) {
        return ERR_INVALID_ARGUMENT;
    }

    translation_table[1] = invalid_entry;
    tlb_invalidate_address(shift);

    translation_table[1] = old_entry; 
    tlb_invalidate_address(shift);

    return OK;
}

NOTE: I’m pretty sure that most of those manipulations are quite excessive in my simple case just because there is no concurrency involved here, but even without concurency in the picture, we do have to tell the CPU when we change the mapping to update the TLB accordingly.

NOTE: If you’re curious about TLB manipulations you can also refer to Linux Kernel as an example. One place to start would be looking at the comments in tlbflush.h.

Instead of conclusion

This post took quite some time for me to prepare and write. As a result, it ended up being rather lengthy and the example in this post is not that practical in the end (and frankly speaking, I probably made a few mistakes here and there).

That being said, I think it was overall a useful exercise to get a level of understanding of address translation tables in ARM. And I hope that provided examples (both my code snippets and references to Linux Kernel implementation) are good enough to get some people started.

Boot script

In the past posts to load my toy binary using U-boot I had to run the following commands in the U-boot shell:

fatload virtio 0:1 0x40000000 kernel.bin
fatload virtio 0:1 0x41000000 virt.dtb
booti 0x40000000 - 0x41000000

That’s not a big deal, but it would be better if U-boot could do all that automatically and, naturally, U-boot should be able to do that.

NOTE: U-boot is used in multiple consumer hardware systems, for example, some Wi-Fi routers use U-boot as a bootloader and you don’t have to type some shell commands when using those - you just power up the device and then U-boot does the rest automatically.

So how can we tell U-boot to execute command above automatically?

First, we need to prepare the script. When I built U-boot with it I also built a bunch of useful tools, one of them is mkimage. This tool takes some image or data as an input, attaches a header to it and produces an image in format that U-boot is familiar with.

Let’s save the commands above in a text file, let’s call it boot.txt, though the name does not matter as much. Now, we can use mkimage to produce a U-boot image from it as follows:

~/ws/u-boot/tools/mkimage -T script -d boot.txt boot.scr
Image Name:   
Created:      Sun Nov 19 20:54:48 2023
Image Type:   PowerPC Linux Script (gzip compressed)
Data Size:    118 Bytes = 0.12 KiB = 0.00 MiB
Load Address: 00000000
Entry Point:  00000000
Contents:
   Image 0: 110 Bytes = 0.11 KiB = 0.00 MiB

NOTE: ~/ws/u-boot/ is where U-boot sources I downloaded live and where the U-boot build results are, so that’s where mkimage is as well.

This command should have prodiced a file boot.scr. The content of this file is mostly the text of our script, but it also contains an additional binary header:

cat boot.scr
'V�$��eZvPv�jպnfatload virtio 0:1 0x40000000 kernel.bin
fatload virtio 0:1 0x41000000 virt.dtb
booti 0x40000000 - 0x41000000

So now, I will place this boot.scr file in the root file system used by QEMU:

mkdir rootfs/boot
cp boot.scr rootfs/boot

NOTE: rootfs is the directory that QEMU will use as a root file system on the emulated device.

So if we start QEMU now, it will load U-boot and U-boot will load our toy binary automatically auto some wait time unless we interrupt it:

qemu-system-aarch64 \
    -machine virt,virtualization=on,secure=off \
    -cpu max \
    -bios u-boot.bin \
    -nographic \
    -drive file=fat:rw:./rootfs,format=raw,media=disk


U-Boot 2023.10-rc1-00323-gb1a8ef746f (Aug 07 2023 - 13:43:27 +0100)

DRAM:  128 MiB
Core:  51 devices, 14 uclasses, devicetree: board
Flash: 64 MiB
Loading Environment from Flash... *** Warning - bad CRC, using default environment

In:    pl011@9000000
Out:   pl011@9000000
Err:   pl011@9000000
Net:   eth0: virtio-net#32
Hit any key to stop autoboot:  0 
Scanning for bootflows in all bootdevs
Seq  Method       State   Uclass    Part  Name                      Filename
---  -----------  ------  --------  ----  ------------------------  ----------------
Scanning global bootmeth 'efi_mgr':
Scanning bootdev 'fw-cfg@9020000.bootdev':
fatal: no kernel available
No working controllers found
scanning bus for devices...
Scanning bootdev 'virtio-blk#33.bootdev':
  0  script       ready   virtio       1  virtio-blk#33.bootdev.par /boot/boot.scr
** Booting bootflow 'virtio-blk#33.bootdev.part_1' with script
4608 bytes read in 1 ms (4.4 MiB/s)
1048576 bytes read in 1 ms (1000 MiB/s)
## Flattened Device Tree blob at 41000000
   Booting using the fdt blob at 0x41000000
Working FDT set to 41000000
   Loading Device Tree to 0000000045c8c000, end 0000000045d8efff ... OK
Working FDT set to 45c8c000

Starting kernel ...

Hello, World

Standard Boot Process

So let’s try to understand a little bit more how U-boot actually finds the kernel to boot and the specifc commands. U-boot has a few relevant concepts that are relevant to the boot process:

1. Boot Device - disk, memory card, network device, etc from which we get the binaries, device tree, scripts and other things we need to boot the system;
2. Boot Method - it’s a method/algorithm/process used to scan the Boot Device extract the configs and binaries we need;
3. Boot Flow - a configuration of how to actually boot an OS, I will ignore it for my simplistic example as I don’t actually need it.

U-boot supports multiple differnt types of boot devices and boot methods. For example, in the U-boot build that I use on QEMU I can see the following boot devices:

bootdev list
Seq  Probed  Status  Uclass    Name
---  ------  ------  --------  ------------------
  0   [   ]      OK  qfw       fw-cfg@9020000.bootdev
  1   [   ]      OK  ethernet  virtio-net#32.bootdev
  2   [   ]      OK  virtio    virtio-blk#33.bootdev
---  ------  ------  --------  ------------------
(3 bootdevs)

And here are the available boot methods:

bootmeth list -a
Order  Seq  Name                Description
-----  ---  ------------------  ------------------
    0    0  efi                 EFI boot from an .efi file
 glob    1  efi_mgr             EFI bootmgr flow
    2    2  extlinux            Extlinux boot from a block device
    3    3  pxe                 PXE boot from a network device
    4    4  qfw                 QEMU boot using firmware interface
    5    5  script              Script boot from a block device
 glob    6  vbe_simple          VBE simple
-----  ---  ------------------  ------------------
(7 bootmeths)

In the example above I used virtio-blk#33.bootdev as a boot device and script as a boot method. Though, U-boot tried multiple different options before it figured out that those boot device and method work.

Boot Order

As you saw above virtio-blk#33.bootdev was not the first device in the list and script was far from the first method, so U-boot tried multiple different options before it found that that combination worked.

We can actually see what things and in what order U-boot would try on startup using the following command in U-boot shell:

bootflow scan -lae
Scanning for bootflows in all bootdevs
Seq  Method       State   Uclass    Part  Name                      Filename
---  -----------  ------  --------  ----  ------------------------  ----------------
Scanning global bootmeth 'efi_mgr':
  0  efi_mgr      base    (none)       0  <NULL>                    <NULL>
     ** No media/partition found, err=-22E
Scanning bootdev 'fw-cfg@9020000.bootdev':
  1  efi          base    qfw          0  <NULL>                    <NULL>
     ** No media/partition found, err=-524E
  2  extlinux     base    qfw          0  <NULL>                    <NULL>
     ** No media/partition found, err=-524E
  3  pxe          base    qfw          0  <NULL>                    <NULL>
     ** No media/partition found, err=-524E
fatal: no kernel available
  4  qfw          base    qfw          0  qfw                       <NULL>
     ** No media/partition found, err=-5E
  5  script       base    qfw          0  <NULL>                    /boot/boot.scr
     ** No media/partition found, err=-1E
No working controllers found
scanning bus for devices...
Scanning bootdev 'virtio-blk#33.bootdev':
  6  efi          media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  7  extlinux     media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  8  pxe          base    virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No media/partition found, err=-524E
  9  qfw          base    virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No media/partition found, err=-524E
  a  script       media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  b  efi          fs      virtio       1  virtio-blk#33.bootdev.par efi/boot/bootaa64.efi
     ** File not found, err=-2E
  c  extlinux     fs      virtio       1  virtio-blk#33.bootdev.par /boot/extlinux/extlinux.conf
     ** File not found, err=-2E
  d  pxe          base    virtio       1  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
  e  qfw          base    virtio       1  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
  f  script       ready   virtio       1  virtio-blk#33.bootdev.par /boot/boot.scr
 10  efi          media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 11  extlinux     media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 12  pxe          base    virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 13  qfw          base    virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 14  script       media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 15  efi          media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 16  extlinux     media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 17  pxe          base    virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 18  qfw          base    virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 19  script       media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1a  efi          media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1b  extlinux     media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1c  pxe          base    virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 1d  qfw          base    virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 1e  script       media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1f  efi          media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 20  extlinux     media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 21  pxe          base    virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 22  qfw          base    virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 23  script       media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 24  efi          media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 25  extlinux     media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 26  pxe          base    virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 27  qfw          base    virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 28  script       media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 29  efi          media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2a  extlinux     media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2b  pxe          base    virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 2c  qfw          base    virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 2d  script       media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2e  efi          media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2f  extlinux     media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 30  pxe          base    virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 31  qfw          base    virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 32  script       media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 33  efi          media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 34  extlinux     media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 35  pxe          base    virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 36  qfw          base    virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 37  script       media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 38  efi          media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 39  extlinux     media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3a  pxe          base    virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 3b  qfw          base    virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 3c  script       media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3d  efi          media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3e  extlinux     media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3f  pxe          base    virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 40  qfw          base    virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 41  script       media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 42  efi          media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 43  extlinux     media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 44  pxe          base    virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 45  qfw          base    virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 46  script       media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 47  efi          media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 48  extlinux     media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 49  pxe          base    virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 4a  qfw          base    virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 4b  script       media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 4c  efi          media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 4d  extlinux     media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 4e  pxe          base    virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 4f  qfw          base    virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 50  script       media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 51  efi          media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 52  extlinux     media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 53  pxe          base    virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 54  qfw          base    virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 55  script       media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 56  efi          media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 57  extlinux     media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 58  pxe          base    virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 59  qfw          base    virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 5a  script       media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 5b  efi          media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 5c  extlinux     media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 5d  pxe          base    virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 5e  qfw          base    virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 5f  script       media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 60  efi          media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 61  extlinux     media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 62  pxe          base    virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 63  qfw          base    virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 64  script       media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 65  efi          media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 66  extlinux     media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 67  pxe          base    virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 68  qfw          base    virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 69  script       media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6a  efi          media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6b  extlinux     media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6c  pxe          base    virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 6d  qfw          base    virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 6e  script       media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6f  efi          media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 70  extlinux     media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 71  pxe          base    virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 72  qfw          base    virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 73  script       media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 74  efi          media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 75  extlinux     media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 76  pxe          base    virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 77  qfw          base    virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 78  script       media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 79  efi          media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7a  extlinux     media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7b  pxe          base    virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 7c  qfw          base    virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 7d  script       media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7e  efi          media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7f  extlinux     media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 80  pxe          base    virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 81  qfw          base    virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 82  script       media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 83  efi          media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 84  extlinux     media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 85  pxe          base    virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 86  qfw          base    virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 87  script       media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 88  efi          media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 89  extlinux     media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8a  pxe          base    virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 8b  qfw          base    virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 8c  script       media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8d  efi          media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8e  extlinux     media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8f  pxe          base    virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 90  qfw          base    virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 91  script       media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 92  efi          media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 93  extlinux     media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 94  pxe          base    virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 95  qfw          base    virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 96  script       media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 97  efi          media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 98  extlinux     media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 99  pxe          base    virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 9a  qfw          base    virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 9b  script       media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
BOOTP broadcast 1
DHCP client bound to address 10.0.2.15 (2 ms)
Scanning bootdev 'virtio-net#32.bootdev':
BOOTP broadcast 1
DHCP client bound to address 10.0.2.15 (0 ms)
*** Warning: no boot file name; using '0A00020F.img'
Using virtio-net#32 device
TFTP from server 10.0.2.2; our IP address is 10.0.2.15
Filename '0A00020F.img'.
Load address: 0x40400000
Loading: *
TFTP error: 'Access violation' (2)
Not retrying...
 9c  efi          base    ethernet     0  virtio-net#32.bootdev.0   <NULL>
     ** No media/partition found, err=-2E
 9d  extlinux     base    ethernet     0  <NULL>                    <NULL>
     ** No media/partition found, err=-524E
 9e  pxe          base    ethernet     0  <NULL>                    <NULL>
     ** No media/partition found, err=-524E
 9f  qfw          base    ethernet     0  <NULL>                    <NULL>
     ** No media/partition found, err=-524E
 a0  script       base    ethernet     0  virtio-net#32.bootdev.0   <NULL>
     ** No media/partition found, err=-22E
No more bootdevs
---  -----------  ------  --------  ----  ------------------------  ----------------
(161 bootflows, 1 valid)

Excluding so called global boot methods, the logic U-boot uses is pretty straighforward - it just itreatates over all the possible boot devices and tries all the possible boot methods on each device in order.

So what is the order of those boot devices? It appears that the order is controlled by an environment variable boot_targets. It seems that the default value of the boot_targets variable is board specific, but it can be changed.

For example, in my case the default value looks like:

env print boot_targets
boot_targets=qfw usb scsi virtio nvme dhcp

And given that I know that my boot script lives on a Virtio block device I can override it this way:

setenv boot_targets "virtio"

And once I do that, the boot process will actually start by looking at the virtio block device first reducing the number of options to consider:

bootflow scan -lae          
Scanning for bootflows in all bootdevs
Seq  Method       State   Uclass    Part  Name                      Filename
---  -----------  ------  --------  ----  ------------------------  ----------------
Scanning global bootmeth 'efi_mgr':
  0  efi_mgr      base    (none)       0  <NULL>                    <NULL>
     ** No media/partition found, err=-22E
Scanning bootdev 'virtio-blk#33.bootdev':
  1  efi          media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  2  extlinux     media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  3  pxe          base    virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No media/partition found, err=-524E
  4  qfw          base    virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No media/partition found, err=-524E
  5  script       media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  6  efi          fs      virtio       1  virtio-blk#33.bootdev.par efi/boot/bootaa64.efi
     ** File not found, err=-2E
  7  extlinux     fs      virtio       1  virtio-blk#33.bootdev.par /boot/extlinux/extlinux.conf
     ** File not found, err=-2E
  8  pxe          base    virtio       1  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
  9  qfw          base    virtio       1  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
  a  script       ready   virtio       1  virtio-blk#33.bootdev.par /boot/boot.scr
  b  efi          media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  c  extlinux     media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  d  pxe          base    virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
  e  qfw          base    virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
  f  script       media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 10  efi          media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 11  extlinux     media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 12  pxe          base    virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 13  qfw          base    virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 14  script       media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 15  efi          media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 16  extlinux     media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 17  pxe          base    virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 18  qfw          base    virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 19  script       media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1a  efi          media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1b  extlinux     media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1c  pxe          base    virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 1d  qfw          base    virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 1e  script       media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1f  efi          media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 20  extlinux     media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 21  pxe          base    virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 22  qfw          base    virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 23  script       media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 24  efi          media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 25  extlinux     media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 26  pxe          base    virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 27  qfw          base    virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 28  script       media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 29  efi          media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2a  extlinux     media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2b  pxe          base    virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 2c  qfw          base    virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 2d  script       media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2e  efi          media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 2f  extlinux     media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 30  pxe          base    virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 31  qfw          base    virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 32  script       media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 33  efi          media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 34  extlinux     media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 35  pxe          base    virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 36  qfw          base    virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 37  script       media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 38  efi          media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 39  extlinux     media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3a  pxe          base    virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 3b  qfw          base    virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 3c  script       media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3d  efi          media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3e  extlinux     media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 3f  pxe          base    virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 40  qfw          base    virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 41  script       media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 42  efi          media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 43  extlinux     media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 44  pxe          base    virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 45  qfw          base    virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 46  script       media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 47  efi          media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 48  extlinux     media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 49  pxe          base    virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 4a  qfw          base    virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 4b  script       media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 4c  efi          media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 4d  extlinux     media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 4e  pxe          base    virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 4f  qfw          base    virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 50  script       media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 51  efi          media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 52  extlinux     media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 53  pxe          base    virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 54  qfw          base    virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 55  script       media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 56  efi          media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 57  extlinux     media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 58  pxe          base    virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 59  qfw          base    virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 5a  script       media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 5b  efi          media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 5c  extlinux     media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 5d  pxe          base    virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 5e  qfw          base    virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 5f  script       media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 60  efi          media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 61  extlinux     media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 62  pxe          base    virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 63  qfw          base    virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 64  script       media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 65  efi          media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 66  extlinux     media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 67  pxe          base    virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 68  qfw          base    virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 69  script       media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6a  efi          media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6b  extlinux     media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6c  pxe          base    virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 6d  qfw          base    virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 6e  script       media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 6f  efi          media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 70  extlinux     media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 71  pxe          base    virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 72  qfw          base    virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 73  script       media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 74  efi          media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 75  extlinux     media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 76  pxe          base    virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 77  qfw          base    virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 78  script       media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 79  efi          media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7a  extlinux     media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7b  pxe          base    virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 7c  qfw          base    virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 7d  script       media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7e  efi          media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 7f  extlinux     media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 80  pxe          base    virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 81  qfw          base    virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 82  script       media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 83  efi          media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 84  extlinux     media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 85  pxe          base    virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 86  qfw          base    virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 87  script       media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 88  efi          media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 89  extlinux     media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8a  pxe          base    virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 8b  qfw          base    virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 8c  script       media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8d  efi          media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8e  extlinux     media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 8f  pxe          base    virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 90  qfw          base    virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 91  script       media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 92  efi          media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 93  extlinux     media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 94  pxe          base    virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 95  qfw          base    virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No media/partition found, err=-524E
 96  script       media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
No more bootdevs
---  -----------  ------  --------  ----  ------------------------  ----------------
(151 bootflows, 1 valid)

Addtionally, I can change the order of boot methods as well even further reducing the number of options U-boot will have to try:

setenv bootmeths "script"
bootflow scan -lae       
Scanning for bootflows in all bootdevs
Seq  Method       State   Uclass    Part  Name                      Filename
---  -----------  ------  --------  ----  ------------------------  ----------------
Scanning bootdev 'virtio-blk#33.bootdev':
  0  script       media   virtio       0  virtio-blk#33.bootdev.who <NULL>
     ** No partition found, err=-2E
  1  script       ready   virtio       1  virtio-blk#33.bootdev.par /boot/boot.scr
  2  script       media   virtio       2  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  3  script       media   virtio       3  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  4  script       media   virtio       4  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  5  script       media   virtio       5  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  6  script       media   virtio       6  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  7  script       media   virtio       7  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  8  script       media   virtio       8  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  9  script       media   virtio       9  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  a  script       media   virtio       a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  b  script       media   virtio       b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  c  script       media   virtio       c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  d  script       media   virtio       d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  e  script       media   virtio       e  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
  f  script       media   virtio       f  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 10  script       media   virtio      10  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 11  script       media   virtio      11  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 12  script       media   virtio      12  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 13  script       media   virtio      13  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 14  script       media   virtio      14  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 15  script       media   virtio      15  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 16  script       media   virtio      16  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 17  script       media   virtio      17  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 18  script       media   virtio      18  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 19  script       media   virtio      19  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1a  script       media   virtio      1a  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1b  script       media   virtio      1b  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1c  script       media   virtio      1c  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
 1d  script       media   virtio      1d  virtio-blk#33.bootdev.par <NULL>
     ** No partition found, err=-2E
No more bootdevs
---  -----------  ------  --------  ----  ------------------------  ----------------
(30 bootflows, 1 valid)

Instead of conclusion

Instead of the conclusion I will provide some code references to where this boot logic implementation lives in U-boot:

1. the implementation of the bootflow shell command lives in u-boot/cmd/bootflow.c
2. the implementation of the boot device iterators is located in u-boot/boot/bootflow.c
3. logic of different boot methods is split bettwen multiple files in u-boot/boot directory, but the common routines for iteration through the available boot methods live in u-boot/boot/bootmeth-uclass.c
4. spefically script boot method implementation details live in u-boot/boot/bootmeth-script.c and by looking around for similarly named files you can find what other boot methods can U-boot support in principle.

Finally, environment variables boot_targets and bootmeths that control what boot devices and methods to try and in which order handled a little bit differently from each other.

boot_targets environment variable is read directly when needed and that’s why it’s relatively easy to find a reference to it in u-boot/boot/bootstd-uclass.c.

bootmeths variable is not accessed directly and instead there is a callback that gets called when this variable get changed. It’s registered via U_BOOT_ENV_CALLBACK macro in u-boot/boot/bootmeth-uclass.c.

Linux kernel

Last time I used a plain binary containing binary code without any structure and that works fine for simple scenarios.

However Linux kernel is a bit more complicated in multiple ways. For example, Linux kernel images can be compressed and can support EFI - that means that they should look like PE executables. As a result, U-boot also has to be able to handle different binary formats.

On top of that, Linux kernel for Aarch64 required a description of perefery attached to the board in form of a flat device tree blob (fdt). So not only U-boot has to support different binary formats, it also need to be able to pass some arguments to the kernel, e.g. address of the fdt in memory.

It’s also quite common for Linux to have an image of init RAM filesystem, so that should be provided somehow as well, though it’s optional.

The format of the Linux kernel image is documented in https://www.kernel.org/doc/Documentation/arm64/booting.txt. The documentation is farily straighforward, but let’s play with it a bit to understand it better.

I will skip compressed kernel images and right away start with decompressed image format. Linux kernel, at the beginning of the decompressed binary puts a header in the following format:

struct Image_header {
	uint32_t	code0;		/* Executable code */
	uint32_t	code1;		/* Executable code */
	uint64_t	text_offset;	/* Image load offset, LE */
	uint64_t	image_size;	/* Effective Image size, LE */
	uint64_t	flags;		/* Kernel flags, LE */
	uint64_t	res2;		/* reserved */
	uint64_t	res3;		/* reserved */
	uint64_t	res4;		/* reserved */
	uint32_t	magic;		/* Magic number */
	uint32_t	res5;
};

NOTE: You can find this structure in the U-boot code base in the arch/arm/lib/image.c. The same structure is documented in the Linux kernel docs.

There are multiple fields here, but when it comes to U-boot the only relevant fields are:

• code0/code1
• text_offset
• image_size
• flags
• magic

code0/code1

TL;DR: the only functionally relevant content of the code0/code1 is the unconditional jump instruction that jumps over the rest of the header fields and transfers control to the actual kernel code.

code0 and code1, as the commend in the U-boot code indicates are expected to contain executable code. That basically means that at the beginning of the Linux kernel binary we are expected to have some actually executable code.

Two fields are just 8 bytes long together, so there is not a lot of code that could be put there, but we can fit there an unconditional jump instruction (e.g. b instruction in ARM).

Linux kernel, depending on the configuration, puts in code0 and code1 either:

ccmp x18, #0, #0xd, pl
b primary_entry

or

nop
b primary_entry

NOTE: The header in Linux kernel code base is populated inside arch/arm64/kernel/head.S.

Instruction nop, as the name suggest, does nothing - it’s just used to fill the space. ccmp x18, #0, #0xd, pl, while looks complicated, doesn’t actually do anything useful and is only there because binary encoding of the instruction, when interpreted as ASCII string, spells “MZ”.

As I mentioned before, Linux kernel may support EFI and when it is configured, the Linux kernel binary is expected to look like PE executable. One of the valid PE executable binaries may start from a so called DOS Header which contains string “MZ” as its first two bytes. So this way Linux kernel maskarades itself as a PE executable.

text_offset

TL;DR: This field does affect how and more imporatntly where U-boot relocates the binary in memory, but in practice it is always set to 0.

As I showed last, U-boot has commands to load binaries from different places to memory (e.g. from a disk with FAT filesystem). With Linux kernel the story is similar - we still need to put the binary in memory. However the story does not end there and U-boot may relocate the binary in memory to a different location to satisfy certian constraints Linux kernel puts forward.

One such constraint is that Linux kernel image has to be relocated to a text_offset bytes from a 2MiB aligned memory address.

I’m not familiar with the history of the constraint, so cannot really say why exactly Linux kernel has it. However, in the recent kernels at least, text_offset is always set to 0. So in practice all U-boot needs to do is to make sure that the kernel image is aligned on 2MiB boundary and if it’s not, it will move it to satisfy the constraints.

NOTE: You can find the U-boot logic responsible for relocating Linux kernel in rch/arm/lib/image.c.

image_size

The name of this field is fairly self descriptive. It just indicates the size of the “useful” part of the kernel image. That’s how many bytes U-boot would need to relocate if the kernel is not aligned in memory on 2MiB boundary.

flags

There are 3 properties that can be recorded in the flags:

1. Kernel endianness (Little Endian or Big Endian) - as far as I can tell U-boot does not really care about the value of this flag;
2. Kernel page size (4KiB, 16KiB, 64KiB or unspecified) - similarly to the flag above it does not seem like U-boot cares about the value of this flag;
3. Kernel placement - it’s a hint flag, when it’s not set, U-boot should relocate the kernel as close as possible to the begining of the usable RAM.

Linux kernel endiannes is configurable, so it seems like in principle you can have both Little Endian and Big Endinan kernel. However, the kernel page size for Aarch64 seem to always be 4KiB and and nowdays Linux kernels for Aarch64 can be placed anywhere without restrictions.

So for example, if we assume that we are building a Linux kernel for Little Endian and given the values of all other flags appear to be fixed, then the value of the flags we are looking for should be 0x000000000000000a.

magic

This field just contains a fixed value: 0x644d5241. U-boot will check the value in this field to confirm that the image it tries to load is actually a Linux kernel binary in the proper format.

If the value will not match the expected magic value, U-boot will refuse to boot the image.

Practice

I read the documentation and got some level of understanding of how a Linux kernel binary should look like. Now it’s time to test that knowledge - the task for today is to create a binary that for U-boot will look like a Linux kernel binary and U-boot should load it.

Output

Last time I used gdb to confirm that my binary was loaded and is running. It’s a good tool, but it’s a bit tiresome to always use gdb to figure out if things worked.

So to simplify my life a little bit I will change the binary to output some text via serial port. Qemu emulate PL011 compatible UART device, so we can create a simple driver that outputs some text to serial port.

I will not cover in details how to interract with PL011 here - I have another article covering this very topic specifically. Just for completeness I will say that I assume that we have the following two functions implemented:

// Initializes pl011 structure given the provided paramters.
//
// addr - physical address where the pl011 registers are mapped to
// clock - frequency of the clock that pl011 is using
void pl011_setup(struct pl011 *serial, uintptr_t addr, uint64_t clock);

// Sends given data to the serial port.
void pl011_send(const struct pl011 *serial, const uint8_t *data, size_t size);

I also happen to know (and it’s also covered in another article on PL011 that I have on the site) that the frequency of the clock that PL011 uses is 24GHz and the PL011 registers are mapped to address 0x9000000.

Putting it all together we have the following code:

#include "pl011.h"

void kernel_start(void *fdt) {
    struct pl011 serial;
    char greeting[] = "Hello, World\n";

    pl011_setup(&serial, 0x9000000, 24000000);
    pl011_send(&serial, (uint8_t *)greeting, 13);
}

I will show how the kernel_start function will be called later in this article.

Header

Now I have a code that sends some data to a serial port that I will be able to see when (and if) U-boot successfuly loads and boots the kernel image. And I have to make sure that the binary will have a proper header now.

Fortunately generating the header in assmebler is mostly straighforward:

.section ".head.text","ax"
.global _start
.extern _end, kernel_start

_start:
    // code0/code1
    nop
    b entry

    // text_offset
    .quad 0

    // image_size
    .quad _end - _start

    // flags
    .quad 0b1010

    // Reserved fields
    .quad 0
    .quad 0
    .quad 0

    // magic - yes 0x644d5241 is the same as ASCII string "ARM\x64"
    .ascii "ARM\x64"

    // Another reserved field at the end of the header
    .byte 0, 0, 0, 0

entry:
    bl kernel_start 

loop:
    b loop

I covered most of the header fields above already, so I will not go over them again. I will just mention, that in code0/code1 I just put nop instruction and a jump to the actual entry point entry.

The only thing that the actual entry code does is calls kernel_start that I showed above already. Once the kernel_start function returns the code enters infinite loop.

Two important things to note in this snippet are these:

1. image_size is calculated as a difference between _start, the lable that marks the beginning of the header, and _end that is not in this code, but I will create this symbol in the linker script.
2. Instead of using .text GNU Assember directive to create a section, I use .section directive - that’s because I want to use a custom name for the section - it will be useful to make sure that the code in this file will be at the beginning of the final binary.

Linker script

I use the linker script from the previous article with some minor modifications. I will not copy the whole linker script and will just show the relevant parts that I changed:

OUTPUT_FORMAT(elf64-aarch64)
// NOTE: The name of the entry point changed from start to _start
ENTRY(_start)

...

SECTIONS
{
    ...

    .text : {
        _TEXT_BEGIN = .;
        // NOTE: Here I use the name of the section from the assmbler code above.
        //       That's why I used .section directive, so that I can give it a
        //       different name and refer to that name here and make sure that
        //       the header will actually be at the beginning of the file and not
        //       in some random location.
        *(.head.text)
        *(.text)
        _TEXT_END = .;
    } :text

    ...

    // NOTE: Here I create the _end symbol with an appropriate value, so that
    //       linker can automatically calculate the size of the image and put
    //       it in the header.
    _end = .;
}

There are two really relevant changes here:

1. I had to make changes to make sure that header will be at the beggining of the binary where the header should be;
2. I had to create _end symbol to be able to calculate the size of the image.

Build and compare

I assume that the result of the build is stored in kernel.bin file, just like in the previous article. Let’s take a look at what is at the beginning of the binary:

hexdump -C -n 64 kernel.bin
00000000  1f 20 03 d5 0f 00 00 14  00 00 00 00 00 00 00 00  |. ..............|
00000010  08 11 00 00 00 00 00 00  0a 00 00 00 00 00 00 00  |................|
00000020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000030  00 00 00 00 00 00 00 00  41 52 4d 64 00 00 00 00  |........ARMd....|
00000040

The fist 8 bytes are just encoding instructions nop and b entry. Then goes the text_offset value which happens to be 0.

The image size that was recorded in the image is 0x1108 (4360 bytes) recorded in the Little Endian format (e.g. starting from the least significant byte). That’s a bit more than I expected, but it matches the size of the file in my case, so nothing outrageously wrong here either:

ls -al kernel.bin 
-rwxrwxr-x 1 kmu kmu 4360 Aug 21 17:38 kernel.bin

Then go flags, and the value, as expected, is 0xa. Finally, after some reserved fields, we have a magic value 0x644d5241, again in Little Endian format.

So the header looks close to what I expected, but I can do another check here. Given that it’s the header used by Linux kernel, I can just build a Linux kernel and compare its header with mine:

sudo apt-get install gcc-aarch64-linux-gnu
git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git linux
cd linux
ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- make allnoconfig
ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- make -j8
ls -al arch/arm64/boot/Image
-rw-rw-r-- 1 kmu kmu 4040712 Aug 21 17:10 arch/arm64/boot/Image
hexdump -C -n 64 arch/arm64/boot/Image
00000000  1f 20 03 d5 0d f0 0a 14  00 00 00 00 00 00 00 00  |. ..............|
00000010  00 00 43 00 00 00 00 00  0a 00 00 00 00 00 00 00  |..C.............|
00000020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
00000030  00 00 00 00 00 00 00 00  41 52 4d 64 00 00 00 00  |........ARMd....|
00000040

The headers don’t match perfectly, but they are pretty close. Let’s take a look at the details starting with code0/code1. The 4 bytes of the nop instruction do match between the two headers, but encoding of the b instructions are different.

The difference here makes perfect sense, because Linux kernel jumps to a slightly different place from my code and the instruction also encodes the offset of the jump, so it stands to reason that instruction encodings may be somewhat different.

The size of the Linux kernel image is much larger (0x430000 or 4390912 bytes). Interestingly enough the size of the image is actually greater then the size of the binary file.

NOTE: I suspect that it might have something to do with BSS sections that are not stored in the binary file itself, but ultimately given that I use Linux kernel in this task as a perfect example, I will not dig deeper and assume that Linux does it right.

The flags and magic values that Linux kernel has in the header match the values in my binary, so nothing to look at here - the headers appear to losely match.

Device Tree

One last thing we need is a flat device tree blob that contains description of the board. I’ve already covered in one of the previous articles how to get device tree from Qemu and how to compile it into a flat device tree.

I will just mention that for the example here I will assume that the flat device tree lives in file virt.dtb in the rootfs directory, so U-boot has access to it.

Loading and running

So I have kernel.bin and virt.dtb in my rootfs and they seem, at least after a brief inspection, to be correct. Let’s test it with U-boot. I described how to launch U-boot in Qemu before, so will not cover it here, so I start from U-boot shell right away.

Unlike the last time, we now have to load 2 binary files in memory and they should not overlap, otherwise one will overwrite parts of the other. In order to do that all we need is to just space them in memory far enough apart:

U-Boot 2023.10-rc1-00323-gb1a8ef746f (Aug 07 2023 - 13:43:27 +0100)

DRAM:  128 MiB
Core:  51 devices, 14 uclasses, devicetree: board
Flash: 64 MiB
Loading Environment from Flash... *** Warning - bad CRC, using default environment

In:    pl011@9000000
Out:   pl011@9000000
Err:   pl011@9000000
Net:   eth0: virtio-net#32
Hit any key to stop autoboot:  0 
=> fatload virtio 0:1 0x40000000 kernel.bin
4360 bytes read in 2 ms (2.1 MiB/s)
=> fatload virtio 0:1 0x41000000 virt.dtb
1048576 bytes read in 2 ms (500 MiB/s)

We now have kernel image loaded in memory starting with address 0x40000000 and flat device tree starting with address 0x41000000. We can check that the device tree is valid and U-boot can parse it by running:

fdt addr 0x41000000
fdt print /

The first command will set the address of the “working” device tree and the second command prints the working device tree starting from the root of the tree.

To actually load the binary the same way as Linux kernel binary U-boot provides booti command. The command needs 3 parameters:

1. The address where the kernel binary was loaded;
2. The address where init RAM filesystem image was loaded;
3. The address where flat device tree was loaded.

NOTE: I don’t use init RAM filesystem, so I will specify - instead of the address.

So let’s try:

booti 0x40000000 - 0x41000000
## Flattened Device Tree blob at 41000000
   Booting using the fdt blob at 0x41000000
Working FDT set to 41000000
   Loading Device Tree to 0000000045c8c000, end 0000000045d8efff ... OK
Working FDT set to 45c8c000

Starting kernel ...

Hello, World

The output suggest that U-boot successfully loaded the image and it sent “Hello, World” to the output. It also suggests that U-boot relocated the device tree from 0x41000000 to 0x45c8c000.

I’m not completely certain why U-boot decided to relocate the device tree to a different place, but I suspect that U-boot may sometimes make some changes to the provided device tree (e.g. mark some memory addresses as reserved) and in such cases it would make sense to construct a new device tree in a different location.

Instead of conclusion

It was a nice and simple exercise to try to create a Linux kernel-like binary image that U-boot can load and boot. I was also able to get a bit more familiar with bits an pieces of U-boot and Linux kernel code bases, which is a bonus as well.

In the past posts I covered already EFI, Qemu, Aarch64. I tried to create a simple EFI bootloader and a simplistic Aarch64 kernel from scratch.

I still didn’t quite abandon the idea of playing with virtualization on Aarch64, but creating everything from scratch, as fun as it is, probably going to delay things even further.

So a new me wants to learn and use some of the existing tools and in this post I will cover the most basic things related to U-boot.

Pre-requisites

We will start with creating a simple binary that we will load with U-boot. For now this binary will not do anything useful or exciting:

.text
.global start

start:
    b start

This is basically an unconditional infinite loop - instruction b is just a jump to a given label.

We now need to compile and link it in such a way that does not pull in various unncessary dependencies (e.g. libc and what not). In order to do that I used a linker script from one of my hobby projects:

OUTPUT_FORMAT(elf64-aarch64)
ENTRY(start)

PHDRS
{
    headers PT_PHDR PHDRS;
    text PT_LOAD FILEHDR PHDRS;
    rodata PT_LOAD;
    data PT_LOAD;
    dynamic PT_DYNAMIC;
}

SECTIONS
{
    . = SIZEOF_HEADERS;
    . = 0x1000;
    _IMAGE_START = .;

    .text : {
        _TEXT_BEGIN = .;
        *(.text)
        _TEXT_END = .;
    } :text

    .init_array : ALIGN(0x1000) {
        _INIT_BEGIN = .;
        KEEP(*(SORT(.init_array.*)))
        KEEP(*(.init_array))
        _INIT_END = .;
    } :rodata

    .rodata : {
        _RODATA_BEGIN = .;
        *(.rodata)
        _RODATA_END = .;
    } :rodata

    .data.rel.ro : {
        _RELRO_BEGIN = .;
        *(.data.rel.ro)
        _RELRO_END = .;
    } :rodata

    .rela.dyn : {
        _RELA_BEGIN = .;
        *(.rela.dyn)
        _RELA_END = .;
    } :rodata

    .dynamic : {
        _DYNAMIC = .;
        *(.dynamic)
    } :rodata :dynamic

    .data : {
        _DATA_BEGIN = .;
        *(.data)
        _DATA_END = .;
    } :data

    .bss : {
        _BSS_BEGIN = .;
        *(.bss)
        _BSS_END = .;
    } :data
}

What this linker script instructs linker to do is not super relevant for this post. It’s sufficient to say, that with this script linker is expected to produce and Aarch64 ELF binary with an entry point in function with name start (it’s the name of the label in the code above).

Now let’s build that. I use LLVM toolchain to build things because I’ve had it installed already:

clang -fPIE -target aarch64-unknown-none -c start.S -o start.o
lld -flavor ld -maarch64elf --pie --static --nostdlib --script=kernel.lds start.o -o kernel.elf

These command produce a rather simple ELF binary with the name kernel.elf. We can take a look at the internals of the file briefly to make sure that it contains what we expect:

llvm-objdump --disassemble kernel.elf 

kernel.elf:	file format elf64-littleaarch64

Disassembly of section .text:

0000000000001000 <start>:
    1000: 00 00 00 14  	b	0x1000 <start>

The output tells us that it’s indeed a Aarch64 ELF binary (specifically, little endian Aarch64 ELF binary) and the binary code there matches what I wrote before.

Now, I don’t actually want an ELF binary, I actually want the raw binary that just contains the code and data without any ELF metadata. The reason I want a raw binary is because later in this post I’m going to load it in memory, using U-boot, and tell U-boot to execute it. All the ELF metadata will just stand in the way.

So to conver this ELF binary into a raw binary we can use objdump:

llvm-objcopy -O binary kernel.elf kernel.bin

We cannot disassemable the new file using llvm-objdump as we did with the ELF file above (or at least I didn’t find a good way to do it), but given that our binary is simple, we can just use hexdump:

hexdump -C -n 4 kernel.bin 
00000000  00 00 00 14                                       |....|
00000004

If you squint a little bit you will notice the four bytes (00 00 00 14) that we saw above - that’s just the binary encoding of the b instruction in our code and it’s located right at the beginning of the file.

So now I have a binary I can load using U-boot in our experiments.

Downloading and building U-boot

The main star of the show is next now - let’s donwload and build U-boot. I again will be using Qemu instead of real hardware for my experiments because it’s easy, so we will be building U-boot for hardware emulated by Qemu:

sudo apt-get install binutils-aarch64-linux-gnu
git clone git@github.com:u-boot/u-boot.git
cd u-boot
make HOST=clang qemu_arm64_defconfig
export TRIPLET=aarch64-linux-gnu
make HOSTCC=clang CROSS_COMPILE=${TRIPLET}- CC="clang -target ${TRIPLET}" -j8

NOTE: Even though I’m mostly using LLVM tools to build U-boot I still had to install GNU binutils.

qemu_arm64_defconfig is a predefined configuration for the Aarch64 hardware emulated by Qemu, so I didn’t need to configure U-boot build in any way for this.

Successful build should produce multiple different artifacts, but for now I care just about u-boot.bin - that’s our U-boot image that we will run.

We can test that it works in Qemu:

qemu-system-aarch64 -machine virt,virtualization=on,secure=off -cpu max -bios u-boot.bin -nographic


U-Boot 2023.10-rc1-00323-gb1a8ef746f (Aug 07 2023 - 13:43:27 +0100)

DRAM:  128 MiB
Core:  51 devices, 14 uclasses, devicetree: board
Flash: 64 MiB
Loading Environment from Flash... *** Warning - bad CRC, using default environment

In:    pl011@9000000
Out:   pl011@9000000
Err:   pl011@9000000
Net:   eth0: virtio-net#32
Hit any key to stop autoboot:  0 
=>

So I have Qemu running the U-boot image I just built.

Qemu setup

Now I want to load and run the simple binary I created earlier using U-boot. For that, I’m going to add a FAT disk to the machine Qemu emulates. I don’t need to create a disk image, Qemu can actually take a content of a directory and present it as a FAT disk to the emulated hardware, which is nice.

Let’s prepare it:

mkdir rootfs
cp kernel.bin rootfs/

And now we can start Qemu again, but this time with a disk:

qemu-system-aarch64 -machine virt,virtualization=on,secure=off -cpu max -bios u-boot.bin -nographic -drive file=fat:rw:./rootfs,format=raw,media=disk


U-Boot 2023.10-rc1-00323-gb1a8ef746f (Aug 07 2023 - 13:43:27 +0100)

DRAM:  128 MiB
Core:  51 devices, 14 uclasses, devicetree: board
Flash: 64 MiB
Loading Environment from Flash... *** Warning - bad CRC, using default environment

In:    pl011@9000000
Out:   pl011@9000000
Err:   pl011@9000000
Net:   eth0: virtio-net#32
Hit any key to stop autoboot:  0
=> 

Still the same output, but now we will explore a little bit. U-boot shell has multiple commands (and what commands available depends on the specific configuration), you can see available commands by running help:

=> help
?         - alias for 'help'
base      - print or set address offset
bdinfo    - print Board Info structure
blkcache  - block cache diagnostics and control
boot      - boot default, i.e., run 'bootcmd'
bootd     - boot default, i.e., run 'bootcmd'
bootdev   - Boot devices
bootefi   - Boots an EFI payload from memory
bootelf   - Boot from an ELF image in memory
bootflow  - Boot flows
booti     - boot Linux kernel 'Image' format from memory
bootm     - boot application image from memory
bootmeth  - Boot methods
bootp     - boot image via network using BOOTP/TFTP protocol
bootvx    - Boot vxWorks from an ELF image
bootz     - boot Linux zImage image from memory
chpart    - change active partition of a MTD device
cmp       - memory compare
coninfo   - print console devices and information
cp        - memory copy
crc32     - checksum calculation
date      - get/set/reset date & time
dfu       - Device Firmware Upgrade
dhcp      - boot image via network using DHCP/TFTP protocol
dm        - Driver model low level access
echo      - echo args to console
editenv   - edit environment variable
eficonfig - provide menu-driven UEFI variable maintenance interface
env       - environment handling commands
erase     - erase FLASH memory
exit      - exit script
ext2load  - load binary file from a Ext2 filesystem
ext2ls    - list files in a directory (default /)
ext4load  - load binary file from a Ext4 filesystem
ext4ls    - list files in a directory (default /)
ext4size  - determine a file's size
false     - do nothing, unsuccessfully
fatinfo   - print information about filesystem
fatload   - load binary file from a dos filesystem
fatls     - list files in a directory (default /)
fatmkdir  - create a directory
fatrm     - delete a file
fatsize   - determine a file's size
fatwrite  - write file into a dos filesystem
fdt       - flattened device tree utility commands
flinfo    - print FLASH memory information
fstype    - Look up a filesystem type
fstypes   - List supported filesystem types
go        - start application at address 'addr'
gzwrite   - unzip and write memory to block device
help      - print command description/usage
iminfo    - print header information for application image
imxtract  - extract a part of a multi-image
itest     - return true/false on integer compare
ln        - Create a symbolic link
load      - load binary file from a filesystem
loadb     - load binary file over serial line (kermit mode)
loads     - load S-Record file over serial line
loadx     - load binary file over serial line (xmodem mode)
loady     - load binary file over serial line (ymodem mode)
loop      - infinite loop on address range
ls        - list files in a directory (default /)
lzmadec   - lzma uncompress a memory region
md        - memory display
mii       - MII utility commands
mm        - memory modify (auto-incrementing address)
mtd       - MTD utils
mtdparts  - define flash/nand partitions
mw        - memory write (fill)
net       - NET sub-system
nm        - memory modify (constant address)
nvme      - NVM Express sub-system
panic     - Panic with optional message
part      - disk partition related commands
pci       - list and access PCI Configuration Space
ping      - send ICMP ECHO_REQUEST to network host
poweroff  - Perform POWEROFF of the device
printenv  - print environment variables
protect   - enable or disable FLASH write protection
pxe       - commands to get and boot from pxe files
To use IPv6 add -ipv6 parameter
qfw       - QEMU firmware interface
random    - fill memory with random pattern
reset     - Perform RESET of the CPU
run       - run commands in an environment variable
save      - save file to a filesystem
saveenv   - save environment variables to persistent storage
scsi      - SCSI sub-system
scsiboot  - boot from SCSI device
setenv    - set environment variables
setexpr   - set environment variable as the result of eval expression
showvar   - print local hushshell variables
size      - determine a file's size
sleep     - delay execution for some time
source    - run script from memory
test      - minimal test like /bin/sh
tftpboot  - load file via network using TFTP protocol
tpm       - Issue a TPMv1.x command
tpm2      - Issue a TPMv2.x command
true      - do nothing, successfully
unlz4     - lz4 uncompress a memory region
unzip     - unzip a memory region
usb       - USB sub-system
usbboot   - boot from USB device
vbe       - Verified Boot for Embedded
version   - print monitor, compiler and linker version
virtio    - virtio block devices sub-system

I want to explore the attached disk a little bit. Qemu relies on virtio specification to emulate disk in this case, so virtio command is what I need:

=> virtio info
Device 0: 1af4 VirtIO Block Device
            Type: Hard Disk
            Capacity: 504.0 MB = 0.4 GB (1032192 x 512)
=> virtio part 0

Partition Map for VirtIO device 0  --   Partition Type: DOS

Part	Start Sector	Num Sectors	UUID		Type
  1	63        	1032129   	be1afdfa-01	06 Boot

virtio info shows that we have one virtio disk with index 0, so using virtio part 0 we can see what partitions this disk has.

Given that disk “formatted” using FAT filesystem I will use fatls to actually look at the files on the disk:

=> fatls virtio 0:1
     4344   kernel.bin

1 file(s), 0 dir(s)

In this command virtio is the “interface” or device subsystem and 0:1 are device and partition on that device.

Now I have my binary available to U-boot.

Loading and running the binary

Since my binary is raw, loading it basically means copying it from disk to memory. I want to know where in memory I can put it, let’s take a look at what is available:

=> bdinfo
boot_params = 0x0000000000000000
DRAM bank   = 0x0000000000000000
-> start    = 0x0000000040000000
-> size     = 0x0000000008000000
flashstart  = 0x0000000000000000
flashsize   = 0x0000000004000000
flashoffset = 0x00000000000fc5e0
baudrate    = 115200 bps
relocaddr   = 0x0000000047ed8000
reloc off   = 0x0000000047ed8000
Build       = 64-bit
current eth = virtio-net#32
ethaddr     = 52:52:52:52:52:52
IP addr     = <NULL>
fdt_blob    = 0x0000000046d97db0
new_fdt     = 0x0000000046d97db0
fdt_size    = 0x0000000000100000
lmb_dump_all:
 memory.cnt = 0x1 / max = 0x10
 memory[0]	[0x40000000-0x47ffffff], 0x08000000 bytes flags: 0
 reserved.cnt = 0x2 / max = 0x10
 reserved[0]	[0x45d8f000-0x47ffffff], 0x02271000 bytes flags: 0
 reserved[1]	[0x46d937b0-0x47ffffff], 0x0126c850 bytes flags: 0
devicetree  = board
arch_number = 0x0000000000000000
TLB addr    = 0x0000000047fe0000
irq_sp      = 0x0000000046d97da0
sp start    = 0x0000000046d97da0
Early malloc usage: 508 / 2000

I don’t know exactly how to interpret all this output, but lmb_dump_all looks like what I need. And if I understand it right, I have enough memory available starting from address 0x40000000 and all the memory that was already reserved for something else is way above that address.

Now I can copy the binary from the disk to memory:

=> fatload virtio 0:1 0x40000000 kernel.bin
4344 bytes read in 1 ms (4.1 MiB/s)

Let’s quickly check what I now have in memory at 0x40000000:

=> md.b 0x40000000 0x04   
40000000: 00 00 00 14

And yes that’s the same 4 magic bytes of the b instruction, so far so good. So now I have my binary in memory I can actually tell U-boot to jump there and start running it:

=> go 0x40000000
## Starting application at 0x40000000 ...

And at this point everything hangs. That’s because the binary I created does not do anything useful it just goes into an infinite loop.

Verifying

The things hanged, but how do I know that they hanged in my code and not because something else failed? Well, I don’t know that for sure, but let’s confirm.

Let’s kill the Qemu and start it somewhat differently to get more visibility into what’s happenning. Now I’m going to run Qemu with monitor enabled:

qemu-system-aarch64 -machine virt,virtualization=on,secure=off -cpu max -bios u-boot.bin -nographic -drive file=fat:rw:./rootfs,format=raw,media=disk -monitor telnet:localhost:1234,server,nowait


U-Boot 2023.10-rc1-00323-gb1a8ef746f (Aug 07 2023 - 13:43:27 +0100)

DRAM:  128 MiB
Core:  51 devices, 14 uclasses, devicetree: board
Flash: 64 MiB
Loading Environment from Flash... *** Warning - bad CRC, using default environment

In:    pl011@9000000
Out:   pl011@9000000
Err:   pl011@9000000
Net:   eth0: virtio-net#32
Hit any key to stop autoboot:  0
=> fatload virtio 0:1 0x40000000 kernel.bin
4344 bytes read in 2 ms (2.1 MiB/s)
=> go 0x40000000
## Starting application at 0x40000000 ...

I have Qemu running and want to confirm that U-boot indeed started my binary. I started Qemu with monitor listening on locahost:1234, so I’m going to connect to it using telnet:

elnet localhost 1234
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
QEMU 6.2.0 monitor - type 'help' for more information
(qemu)

monitor allows quite a bit of introspection into the virtual machine, but for now all I need monitor for is to start gdb, so that I can connect with debugger to the virtual machine and see what exactly it executes:

(qemu) gdbserver tcp::1235
Waiting for gdb connection on device 'tcp::1235'

Now when Qemu is listening we can connect to port 1235 with gdb:

gdb-multiarch 
GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1
Copyright (C) 2022 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word".
(gdb) set architecture aarch64
The target architecture is set to "aarch64".
(gdb) target remote localhost:1235
Remote debugging using localhost:1235
warning: No executable has been specified and target does not support
determining executable automatically.  Try using the "file" command.
0x0000000040000000 in ?? ()

So gdb is now connected and right away I can see that the code in the virtual machine is running at address 0x40000000 - that’s exactly where I loaded my little binary.

Let’s take a look at what command is actually there:

(gdb) display/i $pc
1: x/i $pc
=> 0x40000000:	b	0x40000000

And here I can see my b instruction again.

Instead of conclusion

Not much to say here, it’s probably the most basic use of U-boot out there. I hope to return to this topic and see how U-boot loads proper kernel (e.g. Linux kernel) and some other nice things that U-boot has in other posts.

One obvious limitation is that it allocates memory in multiples of the basic block size. Moreover the multiplier has to be a power of 2. That will lead to some memory wasted if you want to allocate a memory chunk that is not a power of 2 multiple of the basic block size.

Another caveat is the data that we need to maintain for bookkeeping. In the specifc implementation I showed I pre-allocated a page structure for each basic block. This page structure is a bit above 16 bytes in size and the smaller the base block is the more such structures we need. Which increases the overhead of the buddy allocator if we want to allocate small chunks of memory.

So here I’m going to cover another approach to memory allocation that is more efficient when working with smaller object sizes.

I take no creadit for the algorithm itself. This post covers a very simplified version of an algorithm proposed by Jeff Bonwick and described in the The SLAB Allocator paper.

As always the code is available on GitHub.

Introduction

First of all, we will start from simplifing the problem. The most generic interface a memory allocator can have may contain just a couple of methods:

void* allocate(size_t size);
void free(void* ptr);

Basically we tell allocator the amount of memory we need and it gives us a ppointer to a large enough memory chunk. We are going to abandon this idea that we need to be able to allocate memory chunks of different size.

Instead we will create an allocator that is only capable of allocating of memory chunks of single fixed size. So when we will create an allocator we will instruct it what size it will support and that size will stay the same throughout the lifetime of the allocator.

I will go even further and simplify our task even more and assume that we already have an allocator that we can use to allocate large chunks of memory. For example, we could use a Buddy allocator or any other similar algorithm.

With such a simplified problem statement, all we really need is to allocate memory for a large array of objects of the same size and keep track which one have been allocated already and which are still free.

SLAB

I think you got the general idea of what we are going to do, let’s flash out some details of how exactly are we going to do that. First, we will organize our memory in a set of SLABs.

Each SLAB will contain the array of objects of a fixed size plus some bookkeeping structures to keep track of what of the objects are free and what are busy.

Connecting it back to the general idea covered above, SLAB will be our array of objects. Once one SLAB gets full, we can allocate a new SLAB. If we freed all of the objects in the SLAB we can free the whole SLAB back.

There are multiple different layouts that a SLAB can use, here is the high level idea of the layout I use in my simplified example:

NOTE: I decided that a SLAB size has to be a power of 2 and has to be aligned on the power of 2 boundary. It works nicely with the Buddy allocator I described in [the previous post], but that’s not the reason why it was decided this way. I will cover the purpose of that later in the post.

On the picture you can see that I have an array of fixed size memory chunks in the SLAB. Some of them are free and some of them are occupied.

Initially, when we create a new SLAB, all of those objects will be free and as we allocate and free objects from the SLAB we can get various combinations of free and busy objects.

Naturally, we need to keep track what objects are free and what objects are busy. In order to do that I will organize all the free objects in the SLAB into a linked list.

When an object is free, all the memory is available for us to use. So I keep all the pointers required to organize objects in a list right in that very memory that the object occupies. So each object should be large enough to store a pointer, so that we can organize objects in a list.

So here is what I used in my code:

struct Storage : public common::ListNode<Storage> {
    void* pointer;

    Storage(void* ptr) : pointer(ptr) {}
};

NOTE: common::ListNode is a C++ template representing a node of an intrusive linked list, so I can derrive from it and then organize objects in a linked list - I’m not going to cover it in more details, but you’ll see in code examples how the list is used.

NOTE: pointer is just a pointer to the beginning of the object in the free list. Strictly speaking we don’t really need it, because we can just type cast pointer to the Storage object directly to void*. It’s more of my personal taste to avoid type casts if possible.

So for free objects in the SLAB we have something like this in memory:

NOTE: My layout is actually quite different from what Bonwick proposed. My layout is simpler and because of that does not allow for some performance optimizations that Bonwick covered in the orignal paper.

NOTE: Doubly linked list is not actually needed here, a singly linked list is just enough to link the free objects in the list.

When we allocate we take an object from the list, when we free we return an object back to the list - that’s it.

Besides the array of objects, each SLAB will have some metadata. Obviously we need to store the head of the free objects list somewhere, so we will store it in our metadata. This free list is the only thing we need to allocate/free objects from/back to the SLAB.

There are a few things that I will add on top of that to our metadata:

• counter of the number of allocated objects;
• range of memory addresses that the SLAB occupies;
• pointer back to the allocator that the SLAB belongs to.

None of that is strictly needed for the allocator itself, but I think they might be useful for various internal integrity checks, statistics and so on.

In the end the SLAB metadata looks like this:

class Slab : public common::ListNode<Slab> {
public:

    void* Allocate();
    bool Free(void* ptr);

    /* Some other methods here */

private:
    /* The actual data */
    common::IntrusiveList<Storage> freelist_;
    size_t allocated_ = 0;
    /*
     * Cache is the name of the allocator class in my code.
     * For now the details of the Cache class do not matter.
     */
    const Cache* cache_ = nullptr;
    /*
     * Contigous is a structure that describes a contigous chunk of memory.
     * In this case memory_ describes the memory that this very SLAB occupies
     * (inlcuding the array of objects, metadata, all of it).
     */
    Contigous memory_;
};

NOTE: As you can figure out from the fact that Slab inherits common::ListNode<Slab>, we want to organize SLABs in a linked list, you will see later why it’s the case.

Working with SLABs

Now let’s take a look at how we can allocate some memory from a SLAB. Well, it’s quite trivial - we have a list of free object, let’s just take the first object from the list and return it.

void* Slab::Allocate() {
    Storage* storage = freelist_.PopFront();
    if (storage == nullptr) {
        return nullptr;
    }

    void* ptr = storage->pointer;
    storage->~Storage();
    ++allocated_;
    return ptr;
}

I stress here again that, in contrast to other allocation algorithms that I covered, we do not specify the amount of memory we want to allocate.

Each SLAB can only allocate objects of a fixed size. The size of the objects it can allocate is fixed at the time of allocator creation and cannot change after that. Exactly because of that limitation we can have such a simple allocation routine.

Now, let’s take a look at how to free an object back to the SLAB. It’s not much more complicated than the Allocate function above:

bool Slab::Free(void* ptr) {
    const uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
    if (addr < memory_.FromAddress() || addr >= memory_.ToAddress()) {
        return false;
    }

    Storage* storage = reinterpret_cast<Storage*>(ptr);
    ::new (storage) Storage(ptr);
    freelist_.PushFront(storage);
    --allocated_;
    return true;
}

NOTE: checking whether address belongs to the memory range is not really required by the algorithm itself, it’s just an internal integrity check to try to catch incorrect use of the algorithm and the bugs in the implementation. Similar story with returning bool from the function.

SLAB management

Working with the SLABs is easy once you have them, but how do we create and destroy SLABs? I will start with the following helper class that will be responsible for allocating, finding and freeing SLABs.

struct Layout {
    size_t object_size;
    size_t object_offset;
    size_t objects;
    size_t control_offset;
    size_t slab_size;
};

class Allocator {
public:
    Allocator(Layout layout);

    ...

    Slab* Allocate(const Cache* cache);
    void Free(Slab* slab);
    Slab* Find(void* ptr);

private:
    /* some bookkeeping information */
};

Let’s first explain what Layout struct is for. It’s a structure that describes the layout of the SLAB:

• the size of the SLAB
• the size and the number of objects we can allocate from the SLAB
• where the allocated objects are located inside the SLAB
• where the metadata located inside the SLAB
• etc.

When we create a SLAB we use this information to initialize the SLAB, let’s take a look at the SLAB constructor to see how it looks:

Slab::Slab(const Cache* cache, Contigous mem, Layout layout)
        : cache_(cache), memory_(mem) {
    const uintptr_t from = memory_.FromAddress() + layout.object_offset;
    const uintptr_t to = from _ layout.object_size * layout.objects;

    for (uintptr_t addr = from; addr < to; addr += layout.object_size) {
        void* ptr = reinterpret_cast<void*>(addr);
        Storage* storage = reinterpret_cast<Storage*>(ptr);
        ::new (storage) Storage(ptr);
        freelist_.PushBack(storage);
    }
}

So all-in-all, SLAB initialization boils down to a bunch of memory pointer casts to create the list of free object that we use for allocating from the SLAB as was shown above.

Now we know how to initialize a new SLAB, let’s now take a look at the Allocator:

Allocator::Allocator(Layout layout) : layout_(layout) {}

Slab* Allocator::Allocate(const Cache* cache) {
    Contigous memory = AllocatePhysical(layout_.slab_size).release();
    if (!memory.Size()) {
        return nullptr;
    }

    Slab* slab = reinterpret_cast<Slab*>(
            memory.FromAddress() + layout_.control_offset);
    ::new (slab) Slab(cache, memory, layout_);
    return slab;
}

This snippet is a bit complicated, because I skipped through a few background details. Let’s try to explain them now. AllocatePhysical is C++ implementation of Buddy allocator that I use and it returns a structure called Contigous that describes a contigous range of memory allocated by the allocator.

The rest should be more or less understandable. Once we allocated a contigous memory chunk for the SLAB, we find the offset of metadata inside it (based on the Layout structure) and initialize Slab object there. SLAB constructor does most of the work and you saw it above already.

Freeing a SLAB is also rather straightforward:

void Allocator::Free(Slab* slab) {
    Contigous memory = slab->Memory();
    slab->~Slab();
    FreePhysical(memory);
}

NOTE: we get a copy of Contigous structure from the SLAB before calling a destructor, since we should not access any members of the object after it was destroyed.

As you probably guessed, FreePhysical is the function that returns memory back to the Buddy allocator.

Finally, we need the Find function. The purpose of this function is to find a SLAB that contains a certain pointer. Why do we need it? You will see the details later, but in short we could have multiple SLABs at the same time. When we want to free some memory that was allocated from a SLAB we need to find the SLAB from which we allocated that memory. That’s why we need the Find function.

How can we implement Find function? The origianl SLAB allocator paper suggested to maintain a hash map. Using a hash map would work, but somewhat complicated, so I went for a bit simpler and significantly hackier option instead.

Remember that we use Buddy allocator to allocate SLABs. Buddy allocator allocates objects of size that is a power of 2. Additionally, it’s possible to implement Buddy allocator in such a way, that it will allocate objects of size $2^x$ aligned on the boundary of $2^x$. That alignment propery allows us to use a nifty trick:

Slab* Allocator::Find(void* ptr) {
    const uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
    const uintptr_t head = common::AlignDown(
        addr, static_cast<uintptr_t>(layout_.slab_size));
    Slab* slab = reinterpret_cast<Slab*>(head + layout_.control_offset);
    Contigous memory = slab->Memory();
    if (addr < memory.FromAddress() || addr >= memory.ToAddress()) {
        return nullptr;
    }
    return slab;
}

Let’s quickly look at the implementation of the AlignDown function:

template <typename T>
T AlignDown(T x, T alignment) {
    return x & ~(alignment - 1);
}

So essentially, what the Find function does it just finds the closest address that is:

1. less then or equal to the value of ptr
2. is aligned on the SLAB size boundary.

We add a quick check on top of it to make sure that we are not looking at some random memory that never contained SLAB in the first place and that’s it.

Does it look shady? Well, it’s because it is absolutely shady.

Layout

Before we jump to the final part, let’s take a look at the Layout structure. So far we just assumed that it exists and it’s populated with values that make sense. Now we will look at how can we initialize the Layout structure.

We have 2 input parameters that control the layout of our SLABs:

1. the size of the object we want to allocate from the SLAB (remember that we allocate objects of a fixed size)
2. the alignment of the object we want to allocate.

The alignment argument is a bit of a technical detail, but some hardware architectures may require memory to be aligned on a certain boundary.

For example, if your code tries to load 4 bytes long piece of data from memory to a register, CPU may require that that those 4 bytes of data are located in memory starting at the address divisble by 4. For the algorithm it does not really matter why such restrictions may exist - we just have to support them, because otherwise the memory we return from the allocator may not be usable.

How can we account for the alignment constraints? Well, obviously we need to put our objects in the SLAB starting from the address aligned on the right boundary. However that’s not enough.

Consider a situation when you need to allocate objects that are 16 bytes long, but for whatever reason they have to be aligned on the 32 bytes boundary. Even if you put the first object on the 16 bytes boundary, the next object that is located right after the first one will not be aligned to a 16 bytes boundary.

So to account for that, we need to keep some gap between the objects to make sure that all of them are aligned on the right boundary. In other words, we need to artificially increase the size of the object.

Additionally on top of that, all our objects have to be at least large enough to contain Storage structure, so that we could link them into a list. Putting everything together gives us something like this:

size_t ObjectSize(size_t size, size_t alignment) {
    return common::AlignUp(std::max(size, sizeof(Storage)), alignment);
}

The second thing we need to figure out is how big each SLAB should be. There is quite a bit of flexibility there. One thing that I considered is how much memory will be wasted depending on the size of the SLAB.

Imagine we allocate a SLAB that is just 4096 bytes large. It needs to contain the SLAB metadata and all the objects within 4096 bytes chunk of memory. Let’s also assume that the size of the SLAB metadata is 64 bytes and the size of the object is 2048 bytes. With this parameters we will be able to allocate only a single object per SLAB, which is already not great, but on top of that 1984 bytes will not store anything and will be basically wasted. That’s almost 50% of the total memory we allocate for the SLAB.

On the other hand, if the SLAB was 32768 bytes long. We would be able to fit there SLAB metadata and 15 objects of size 2048. In this case we again will waste 1984 bytes, but comparing it to the size of the SLAB it’s just about 6% of the total memory we allocate for the SLAB, which is much better.

So the bigger SLAB we allocate the less memory we waste. On the other hand if we allocate a SLAB that it’s too large and don’t use all the objects there we would also be wasting memory.

With that background out of the way, here is the heuristic I came up with:

size_t SlabSize(size_t size, size_t control) {
    constexpr size_t kMinObjects = 8;
    constexpr size_t kMinSize = 4096;

    const size_t min_bytes = size * kMinObjects + control;

    if (kMinSize >= min_bytes) {
        return kMinSize;
    }

    const size_t order = common::MostSignificantBit(min_bytes - 1) + 1;
    return static_cast<size_t>(1) << order;
}

And the final code that will define the layout of a SLAB looks like this:

Layout MakeLayout(size_t size, size_t alignment) {
    const size_t control_size = sizeof(Slab);
    const size_t object_size = ObjectSize(size, alignment);
    const size_t slab_size = SlabSize(object_size, control_size);

    Layout layout;
    layout.object_size = object_size;
    layout.object_offset = 0;
    layout.objects = (slab_size - control_size) / object_size;
    layout.control_offset = slab_size - control_size;
    layout.slab_size = slab_size;
    return layout;
}

Aside from the topics we covered above, two things that are relevant here. Given that we use Buddy allocator to allocate a SLAB, the SLAB size have to be a power of 2 and will be aligned in memory on the power of 2 boundary. That means that if we put our objects at the beginning of the SLAB, the first of the objects will be aligned on the power of 2 boundary. Similarly, if we put something at the end of the SLAB, it will be aligned well.

In this case I put objects at the beginning of the SLAB memory range and put the SLAB metadata at the end of the SLAB memory range, thus everything should be well aligned inside the SLAB.

Cache

We have most of our building blocks ready to create the final allocator. Let’s see how the interface of our allocator will look like:

class Cache {
public:
    Cache(size_t size, size_t alignment);

    void* Allocate();
    bool Free(void* ptr);
    bool Reclaim();

private:
    /* some fields that will be covered later */
};

Allocate and Free are self explanatory, Reclaim requires a bit of a clarification. As you may have noticed, SLAB is more of a memory cache rather than a true memory allocator (thus the name of the class). It would be useful to have an option to tell to the cache to release the memory it doesn’t need now back to the system. That’s exactly what the Reclaim function is for.

Inside our Cache we are going to maintain 3 lists of SLABs:

• SLABs that are full - we cannot allocate anything from those anymore
• SLABs that are empty - we can return those back to the system if needed
• SLABs that are not full and not empty (partial) - we cannot return those back to the system and we can allocate some objects from them.

class Cache {
public:
    Cache(size_t size, size_t alignment);

    void* Allocate();
    bool Free(void* ptr);
    bool Reclaim();

private:
    Layout layout_;
    Allocator allocator_;
    common::IntrusiveList<Slab> free_;
    common::IntrusiveList<Slab> partial_;
    common::IntrusiveList<Slab> full_;
};

When we need to allocate a new object, we will first check the partially used SLABs. If there are none, we will check the empty SLABs. If there are none we will create a new SLAB.

When we free an object we will always have to free it to the same SLAB from which we allocated it in the first place. However, freeing an object may turn SLAB from full to partially used or from partially used to empty. So we will have to move the SLABs between the list accordingly.

Fortunately, we maintain SLABs in linked lists, so it’s not that hard to do. Let’s take a look:

void* Cache::Allocate() {
    if (!partial_.Empty()) {
        Slab* slab = partial_.Front();
        if (slab->Allocated() + 1 == layout_.objects) {
            partial_.Unlink(slab);
            full_.PushFront(slab);
        }
        return slab->Allocate();
    }

    if (!free_.Empty()) {
        Slab* slab = free_.PopFront();
        partial_.PushFront(slab);
        return slab->Allocate();
    }

    Slab* slab = allocator_.Allocate(this);
    if (slab == nullptr) {
        return nullptr;
    }

    partial_.PushFront(slab);
    return slab->Allocate();
}

bool Cache::Free(void* ptr) {
    if (ptr == nullptr) {
        return false;
    }

    Slab* slab = allocator_.Find(ptr);
    if (slab == nullptr) {
        return false;
    }

    if (slab->Owner() != this) {
        Panic();
    }

    if (slab->Allocated() == 0) {
        return false;
    }

    if (!slab->Free(ptr)) {
        return false;
    }

    if (slab->Allocated() == 0) {
        partial_.Unlink(slab);
        free_.PushFront(slab);
    }

    if (slab->Allocated() + 1 == layout_.objects) {
        full_.Unlink(slab);
        partial_.PushFront(slab);
    }

    return true;
}

NOTE: I brushed over the details of how we check if the SLAB is full or empty, but hopefully it will not be too much trouble to figure out how to implement the Allocated function for the SLAB by just maintaing a counter of the objects that were allocated from the SLAB.

NOTE: Half of the Free function are various internal integrity checks that have little to do with the algorithm itself, that’s why it looks more complicated than it actually is.

Where to go from here

This is the most basic skeleton of a SLAB-like memory allocator. Most of the functions of the SLAB allocator only require a constant amount of time to finish until we need to allocate or free a SLAB. By allocating large enough SLABs we can amortize the cost of allocating and freeing SLABs and bring the amortized cost of allocation and deallocation to constant time with SLABs. So that is pretty nice in its own right, compared to the naive memory allocators that I covered before.

However SLAB can offer much more than that. If you refer to the orignal paper you will find a few interesting optimizations that could be applied to the SLAB allocator and some idea of the impact that those optimizations provide. I’m not going to cover those here because my implementation was simplified to such an extend that it cannot support some of those anymore.

However, I think it might be useful to give you an idea how to build a generic memory allocator, an allocator that can allocate objects of different sizes, using SLAB allocator.

Essentially you can pre-create SLAB allocators for object of different sizes in advance. When we need to allocate memory we first find the smallest SLAB allocator that fits and allocate the object from that SLAB allocator. That’s quite easy.

When we free memory back we need to find the SLAB allocator we allocated it from. This might be a bit complicated, but not impossible to figure out. One simple idea that we could use here is to do some bookkeeping during allocation. For example, we can allocate a bit more memory then requested. In the additional memory we can save the Cache pointer for later. A hash table will work fine as well.

So using a SLAB allocator we can create a generic memory allocator that takes an amortized constant time to allocate and free memory of any size, which is quite neat.

Instead of conclusion

The original SLAB allocator is quite complicated, powerful and efficient algorithm. However, the fundamental ideas behind the algorithm are quite easy to understand and use.

Variations of top of SLAB algorithm are used in all kinds of systems and generic memory allocators, so it’s quite a useful algorithm to understand.

Naturally, this post just scratches over the surface, but hopefully it will be enough to get you started to explore the details on your own.

I’m probably not going to cover anything else related to memory allocation and instead will switch to ARM specific topics like how virtual memory works in ARM in the future posts.

Background

For a bit of background, for my hobby projects that are on a “low-level” side of the software stack I mostly used C. C tooling is predictable and you don’t need to think about runtime much.

C++ and Rust are in the similar category from that point of view, as they both require some non trivial runtime support, and it’s not immediately obvious what runtime do they actually need and what properties it should satisfy.

NOTE: I’ve heard claims that Rust has zero-runtime, but under closer inspection those claims turned out to be not true.

NOTE: for C++ at least there are various ABIs that document the runtime, plus there are compiler docs that shed some light, but I’ve always been struggling to build a complete picture because C++ runtime is actually quite large.

Introduction

With that background out of the way, we have LLVM-based C++ toolchain in our disposal and we can build freestanging programs.

NOTE: compiler support for C++ freestsanding environment is quite attrocious. Don’t mean to offent anyone, just my personal opinion on the current state of the available tools.

I’m working with aarch64 architecture, but I don’t think it matters that much for the thing I’m going to cover in this post.

Finally, to make our life miserable, I’ll be building everything using -Ofast. And that is a bit of a give away. There are stories of C and C++ compilers performing pretty un-intutive “optimizations” making a lot of assumptions about what software engineers should and should not write in their code. This is another such story.

Now to the problem, in a freestanding environment what should we do when the program discovers something it cannot handle? I want to create a function that I’ll call in this situations, and so, I’m going to call this function Panic going forward.

One options is to reset/restart the machine. This option is undesirable for the hobby project, because I’d like to be able to debug what lead to the Panic call and reseting the machine will lose all the valuable debugging information.

NOTE: reset doesn’t have to lose all the valuable info, we can for example collect all that information in the Panic call and save it somewhere, but it’s too hard, so for now I’ll assume that it’s not an option.

Another option is to just hang in the Panic call. While the machine is hanging in the Panic call I cann attach to it with debugger and callect everything I can for debugging. And, compared to the first option, it’s just an infinite loop - it couldn’t be any simpler, right?

Implementation

Enough with the suspence, you all know where it’s going. Let’s start with the naive implementation:

namespace {

void Panic() {
    while (1);
}

}  // namespace

extern "C" void kernel() {
    Panic();
}

NOTE: the kernel function is called from the assembler, so it’s marked as extern "C" to avoid C++ name mangling.

In this example, the kernel function does nothing, it’s just expected to hang right away in the Panic call. To my surprise however, it actually didn’t do what I wanted it to do (I didn’t even ask that much from it…).

When I looked at the generated assembler code of the kernel function with llvm-objdump -D it looked like this:

00000000000020c8 <kernel>:
    20c8: e0 03 1f 2a   mov     w0, wzr
    20cc: c0 03 5f d6   ret

It should be more or less easy to see that there is no function call or infinite loop here, but just for the clarity, mov w0, wzr just writes 0 to the register w0 and ret is just an instruction that returns from a function call.

NOTE: wzr is a “register” that contains 0 and zr in the name is a referece to that.

If I remove the -Ofast flag from the compiler parameters, I see a very different picture:

0000000000002148 <kernel>:
    2148: fd 7b bf a9   stp     x29, x30, [sp, #-16]!
    214c: fd 03 00 91   mov     x29, sp
    2150: 03 00 00 94   bl      0x215c <_ZN12_GLOBAL__N_15PanicEv>
    2154: fd 7b c1 a8   ldp     x29, x30, [sp], #16
    2158: c0 03 5f d6   ret

I will ignore irrelevant parts and will just point out that bl instruction is a branch instruction commonly used in ARM to call functions and _ZN12_GLOBAL__N_15PanicEv is the mangled name of our Panic function.

So without optimizations the kernel function does some stack manipuations ( sp is a stack pointer register) and then calls the Panic function - that’s pretty much what I’d expect to see there.

For completeness let’s look at the Panic function itself:

000000000000215c <_ZN12_GLOBAL__N_15PanicEv>:
    215c: 00 00 00 14   b       0x215c <_ZN12_GLOBAL__N_15PanicEv>

The function contains just one instruction - b. b is an unconditional jump in ARM and in this case it jumps to the instruction itself (pay attention to the instruction address on the left side), so it’s an infinite loop - pretty much what I wanted.

NOTE: without explicitly enabled optimizations I would expect that compiler would put a ret instruction at the end, but it did realize that there is no escape from the inifinite loop and removed all the dead code after the loop.

When I saw that my code behaves differently with and without optimizations I knew I screwed up somewhere, but where?

In the example I’ve shown the code pretty much does nothing, so where could the problem be?

Infinite loops shall not pass

The problem is the inifnite loop itself. Turnes out many-many years ago in a glaxy far-far away, standardization committee decided that loops have to terminate: Optimizing away infinite loops.

NOTE: N1509 is a document from the WG14 - a working group responsible for the C standard, not C++, but it’s still interesting and I found that one before I found other documents.

TL;DR: if the body of the loop and it’s condition/control parts don’t contain any operations that can be considered an observable behavior, compiler is allowed to assume that this loop will terminate.

What does observable behavior mean? It’s technical, but it’s easy to understand:

• input/output operations (like operations with std::fstream) are considered observable behavior
• operations over volatile objects are also considered observable
• synchronization and atomic operations are observable as well.

As you can see our initial implementation had no operations that can be considered observable in the loop itself (operations outside the loop don’t matter). So in our case the compiler was allowed to assume that the loop will terminate.

It’s not a bit leap from that to understand why compiler dropped the loop all together. If the loop doesn’t have any visible effects and we know that it will terminate - it’s useless and can be dropped.

The good

We now know what is happening, but given it’s somewhat unintuitive consequences of this optimization, it’s worth understanding why it was introduced, surely the smart folks in the standardization committee didn’t do it just for the fun of seeing C and C++ developers struggle.

We can find a somewhat shallow explanation of the intent in the N1509 itself:

This is intended to allow compiler transformations such as removal of empty
loops even when termination cannot be proven.

Initially it looks like a cop-out. Basically they are saying that in some limited set of situations when compiler really-really wants to optimize something away, but can’t demonstrate that it’s correct, we just let the complier to assume that everything is fine.

Well, that does not sound great, does it? And if you read it through, the author of the N1509 calls out the fact that it’s a bit of a breaking change despite some claims that it just preserves the status quo of how compilers already work.

So did they actually introduce it to annoy people after all? I’m starting to lean toward this conspiracy theory, but let’s give them a bit of benefit of a doubt and keep digging.

It was the time when C++ standard committee made some pretty significant changes to the C++ standard to support concurrency. In a concurrent environment with shared memory they had to formally specify how this shared memory works. They introduced a memory model in a set of documents culminating in: N2334.

In N2334 they indeed argued that the specification of the C++ at the time already didn’t impose much of restrictions on infinite loops without side effects and that compiler already eliminate such loops.

I haven’t looked at the compiler implementations of that time, so I’m not going to comment on that. However the argument that C++ standard at the time allowed it anyways (or didn’t specify it well enough to disallow such “optimization”) is just bad. Hanging in an infinite loop is a pretty noticeable side affect that does in fact affects observable behavior of the prgram, doesn’t matter how you look at it. Think about operations that come after the loop. Those operations may have observable behavior and, if the loop is infinite, we should not see the effects of those operations.

I’m genuenly having a very hard time beliving that Hans Boehm didn’t realize that this part of the argument was not particularly sound. And, I think, I’m not the only one and that’s how N1509 came to be in the first place. So why?

Hans actually wrote a response to N1509: N1528. The response argues three points:

• consistency between C and C++
• status quo
• optimizations that would not be possible without this assumption

Let’s get the point about consistency between C and C++ out of the way, since it’s mostly irrelevant. As I mentioned above, N1509 is a document from the C standardization working group, not C++. They tried to reconcile C and C++, by adopting some of the things introduced in the new C++ standard to C. So this argument can be rephrased as “C++ has it and there are reasons why C should not diverge from C++”. While it’s an argument, it doesn’t explain why it was introduced to C++ standard in the first place.

Status quo argument is again about compilers already eliminating such loops. As I said before, I cannot comment on what compilers did at the time. That being said, it seems like they are trying to save some work for compiler developers at the cost of the experience of those who will use those compilers.

NOTE: I don’t want to argue that this kind of reasoning is always bad, but I feel that in this particular case it was a bad decision, especially in the light that the last argument somewhat lacking supporting evidence.

Now to the interesting argument, what optimizations this special assumptions allows compilers to do that they would not be able to do otherwise?

There are no general algorithms that could determine if an arbitrary loop terminates or not - that follows from the fact that the Halting problem has no solutions. Just think of a loop that exectues steps of a turing machine based on it’s description.

So it’s clear, that the compiler cannot always prove if a loop terminates. This special dispansation for loops in the standard allows compilers to assume that a loop terminates even if it can’t prove it, sometimes incorrectly.

N1528 even provides a toy example of a situation where it could happen:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

The two loops traverse the same linked list (if you replace 0 with NULL it might be a bit easier to see). If we can assume that all loops without side effects terminate, then the first loop terminates as well (assuming that there are no volatile objects involved).

With that we can rewrite the two loops the following way without losing correctness:

for (p = q; p != 0; p = p -> next) {
    ++count;
    ++count2;
}

This is somewhat better as we only need to traverse the list once. We might even benefit from some vector instructions for ++count and ++count2 (purely hypothetically - I don’t think it will make much of a difference in practice). So we do allow some optimizations by introducing this special assumption about terminating loops.

How ubiqoutous such cases? I don’t know and the N1528 doesn’t provide any data. So I can’t really say anything on whether this kind of optimizations even worth the trouble.

NOTE: I don’t make a claim either way. These optimization may or may not be significant. The only claim I can confidently make that N1528 didn’t provide any evidence that would demonstrate the significance.

All-in-all, assuming that loops without side effects always terminate allows for some optimizations that otherwise would be impossibe and that’s all I can say.

The bad

I started by presenting the problem of creating a Panic function and then immediately showed you a problem that a naive implementation like that creates. However, that’s not at all how I hit this problem.

I hit this problem only when my codebase grew to 1000s of lines of code. When my code started to misbehave the initial set of possibilities that I explored were running out of stack, corrupt memory and so on.

NOTE: some might say that rewriting code in Rust would remove all the memory related bugs out of the picture and would have made my life easier. That’s actually not the case due to the nature of the problem I was solving. You see, when the problem you’re trying to solve is allocation of memory resources, you have no choice but to use unsafe from the Rust point of view manipulations, so all the same set of problems would still be in scope even if the code was written in Rust.

I did a bunch of tests to create a small reproducer, but I couldn’t really come up with anything. It’s only much later, when I started going through individual assembly commands in GDB, I noticed that the compiled code looked weird and not at all what I expected it to be.

Some might say here that there are plenty of questions and posts already written about non-terminating loops in C and C++. And indeed this topic is well covered all over the Internet. However, when my code started to misbehave I didn’t apriori know what caused the problem and it’s quite a debugging jump from a generally misbehaving program to non-terminating loops.

The ugly

With my whining and hurt pride out of the way, what can we do?

Well, now when we know what compiler will look at when it decides whether the loop can be dropped or not, rewriting our Panic function should be straightforward.

I, however, to redeem myself wanted to try and find how we can make the compiler warn me when it eliminates loops. My best attempt was to write something like this:

[[ noreturn ]] void Panic() {
    while (1);
}

As the name suggests, [[ noreturn ]] tells compiler that the function is not expected to return to the caller. The logic behind introducing the [[ noreturn ]] was that at least the compiler I use warns if I write code like this:

[[ noreturn ]] void Panic() {}

The error I get from the compiler looks something like this:

main.cc:9:1: error: function declared 'noreturn' should not return [-Werror,-Winvalid-noreturn]

So, I was thinking that if compiler can assume that while (1); always terminates then, just like in the example above, it can warn me that a function marked as [[ noreturn ]] terminates and it’s not right.

Unfortunately, Clang is “smart” enough to eliminate the loop, but is not smart enough to realize that it would mean reaching the end of function that should never terminiate.

NOTE: some of you may have heard or seen __builtin_unreachable() function and thought about using it here. __builtin_unreachable() function however does not solve the problem. The point of __builtin_unreachable() is to help compiler when it cannot figure out on its own if some code is unreachable.

For example, the following compiles without a warning for me in Clang:

[[ noreturn ]] void Panic() {
    __builtin_unreachable();
}

As I shown above, without the __builtin_unreachable() the compiler sees a problem in the code and rightfully so. With the __builtin_unreachable() it doesn’t see the problem anymore, because we “helped” it.

Needless to say, I couldn’t find in the Clang docs any magical -W command line argument I could use to ask compiler to warn me about dropped loops.

Here I will go into a bit of a speculation and suggest that, at least in Clang, all the compilation warnings are generated long before LLVM applies any of its optimizations.

The mental model I have is as follows: we have a compiler frontend that parses the source code of the program and produces the internal representation of the code. The frotend can analyze the structure of the program and emit some warnings.

The generated internal representation is then processed by the compiler backend. The backend generates the machine code and applies optimization, but, it looks like, the backend assumes that the internal representation it got from the frontend describes a well formed program already and doesn’t generate any warnings.

In the end I settled on the following ugliness in my code to avoid spending even more time dealing with this silly issue:

[[ noreturn ]] void Panic() {
    while (1) {
        asm volatile("":::"memory");
    }
}

Instead of conclusion

• Don’t have hobby projects - they are bad for your mental health;
• Don’t make mistakes in your code - they are bad for your mental health;
• If you made a mistake in your code, write a inconsequentially long post about it, and don’t forget to mention how it’s everybody’s else fault - it’s good for your mental health.

In this post I’d like to cover a rather interesting algorithm, that on the one hand is not as generic as the one I covered in the previous post, but on the other hand it’s quite often used in practice.

As always the code is available on GitHub.

Introduction

The algorithm I will cover is refered to as Buddy Allocator or Buddy System. As I mentioned the algorithm I’ll cover here is not generic, so what does it mean?

This algorithm will allocate memory only by powers of two. So if you want to allocate a memory range you’d have to round the size up to the closest power of two that is large enough.

Additionally, even though it’s not strictly a limitation of the algorithm, due to the amount of metadata we will maintain this algorithm is somewhat wasteful for allocation of small memory blocks. As a result, we will not be working with individual bytes and sizes in bytes, instead we will be working with pages and sizes in pages.

The page size can be anything, but, to give you an example, a potential page size might be 4096 bytes. So algorithm can allocate 1 page, 2 pages, 4 pages and so on.

Moreover, instead of working with the allocated memory directly, I will create a representative (handle, descriptor, etc) for each page. Each representative will contain some amount of metadata that the algorithm will use to maintain its state.

As a result, the interface of the algorithm will look something like this:

struct BuddySystem {
    /* fields */
}

impl BuddySystem {
    pub fn allocate_pages(&mut self, order: u64) -> Option<u64> {
        /* implementation */
    }

    pub fn free_pages(&mut self, index: u64) {
        /* implementation */
    }
}

In this interface index is the number of the page, so you can convert from the index to the address easily by multipling by the page size and vice versa. The order is the power of two. So, for example, allocate_pages(2) will try to allocate a contigous block of four pages. If the allocation is successful it will return the index of the first page in the block.

Hopefully that high level introduction will give you a general idea of what kind of beast we are going to release, so let’s get down to it.

Page

I’ll start with introducing a page representative. There are few pieces of information that we will have to keep per page. One obvious piece is whether the page is free or busy.

In addition to that we will have to store order or level of the page. It’s a little bit hard to explain what this field will actually mean at the moment, but I’ll cover it in details later. For now, all you need to know that level of the page is a small number. When it comes to memory allocation, it doesn’t make sense for this number to be more than 64, so it can easily fit in one byte.

Finally, we will be linking page representatives in lists. In order to do that we need to have fields for the next and previous elements of the list.

All in all we are getting something like this:

use core::cell::Cell;

pub struct Page {
    pub next: Cell<*const Page>,
    pub prev: Cell<*const Page>,
    level: Cell<u8>,
    free: Cell<bool>,
}

I use *const Page instead of something like Option<&Page> here because being able to initialize the structure with zeros is quite a convenient property to have, but in Rust references can never be null. I suspect that Option<&Page> can be zero-initialized, but I could not find any kind of guarantees about that, thus I do not depend on that.

I wrapped all the fields into core::cell::Cell. Cell essentially allows to modify data via immutable reference. And yes, it’s safe as far as Rust type system is concerned.

The reason to do it this way, is because without that the only way to modify the fields would be to either drop to unsafe code or via mutable references.

The problem with mutable references is that you’re only allowed to have one of those at a time. That’s problematic if you have to maintain more than one reference to an object (like for example, in doubly linked lists, or in general when you want to have multiple different indexes refereing to the same objects).

We are not done with the Page structure just yet. You see, we will create a separate Page structure for each page of the memory we will be working with. So naturally, the bigger the structure size, the more overhead we will have. So it might make sense to compress it a little bit. After all free and level can easily fit in one byte - there is no reason to create multiple fields for them and pay for field alignment overhead.

Here is what I ended up having in the end:

use core::cell::Cell;
use core::ptr;

pub struct Page {
    pub next: Cell<*const Page>,
    pub prev: Cell<*const Page>,
    state: Cell<u64>,
}

const LEVEL_MASK: u64 = 0x7f;
const FREE_MASK: u64 = 0x80;

impl Page {
    // This function is only useful for tests, as Page structure will normally
    // be initialized with zeros without calling Page::new().
    pub const fn new() -> Page {
        Page {
            next: Cell::new(ptr::null()),
            prev: Cell::new(ptr::null()),
            state: Cell::new(0),
        }
    }

    pub fn level(&self) -> u64 {
        self.state.get() & LEVEL_MASK
    }

    pub fn set_level(&self, level: u64) {
        assert_eq!(level & ~LEVEL_MASK, 0);
        self.state.set(level | (self.state.get() & !LEVEL_MASK));
    }

    pub fn is_free(&self) -> bool {
        (self.state.get() & FREE_MASK) != 0
    }

    pub fn set_free(&self) {
        self.state.set(self.state.get() | FREE_MASK);
    }

    pub fn set_busy(&self) {
        self.state.set(self.state.get() & !FREE_MASK);
    }
}

Rust doesn’t really provide much guarantees about the internal layout of structures. but if it’s any kind of sensible, then I’d expect that Page structure to be 24 bytes long. With the 4096 byte pages it gives us 0.6% overhead.

To compare, the algorithm from the previous post had about 32 bytes overhead per allocated memory block after applying similar compaction. Though keep in mind that algorithm only incures overhead for blocks of memory we actually allocated, which is not the case for the Buddy System. For the Buddy System we will have to reserve all the memory we need for the metadata upfront, so we always paying this overhead.

List

We need to be able to link Page structures in lists. I will not cover the list implementation, as it’s hardly interesting and nobody would benefit from another bespoke linked list implementation.

Instead I just cover what operations we need and some important properties of the implementation.

Basically, we need just three operations: push, pop and remove. Push and pop are more or less self explanatory: push adds element to the list and pop returns an element from the list. From the algorithm point of view the order of the elements in the list doesn’t matter.

Remove operation given an element of the list and the list itself unlinks the element from the list. The linked list in this case doesn’t own any of the elements it stores, so it cannot delete, copy or move the elements around and restricted to only work with the prev and next fields of the Page structure.

Without covering the implementation here is the interface I ended up with:

use core::option::Option;

pub struct List<'a> {
    head: Option<&'a Page>,
}

impl<'a> List <'a> {
    pub const fn new() -> List<'a> { /* implementation */ }

    pub fn is_empty(&self) -> bool { /* implementation */ }

    pub unsafe fn push(&mut self, page: &'a Page) { /* implementation */ }

    pub unsafe fn pop(&mut self) -> Option<&'a Page> { /* implementation */ }

    pub unsafe fn remove(&mut self, page: &'a Page) { /* implementation */ }
}

Since we use pointers for the linked list links and to implement the operations we need we have to dereference them, the implementation will necessarily use unsafe Rust. I did keep the unsafe in the interface and didn’t try to hide it because with the way the Page structure is defined and how List links Page structures together all the safety guarantees Rust provides are out of the window anyways. Trying to hide it would be rather misleading.

Buddies

We are done with preparations, it’s now time to get to the meat of the algorithm itself. The main idea of the algorithm and the origin of the name is that we will statically pair pages together. To put it another way, we will be creating buddies.

For example, pages with index 0 and 1 are going to be buddies, pages 2 and 3 will be buddies, pages 4 and 5 will be buddies as well and so on - you probably can see the pattern.

More formally, though for the page with index \(x\) the index of its buddy will defined the following way:

where \(\oplus\) is bitwise exclusive or operation. In other words, to find the index of the buddy we need to flip the least significant bit of the index.

You can easily check that it works for the examples given above. Note however, that according to this formula pages with index 1 and 2 are not buddies even though they are neighbours.

NOTE: keep in mind that not all pages may have buddies, for example, if you have only 7 pages, due to the odd number of pages, at least one page will not have a buddy.

Now I’m going to take this idea of buddies and generalize it a little bit. We know that two buddy pages must be neighbours - that’s just how the formula above works.

We can combine two buddy pages in a bigger page. For example, pages with index 0 and 1 are buddies and together they can form a contigous block of a higher order or level. You might catch a drift at this point of what the level in the Page structure is for.

We will call individual pages blocks of order or level 0, as if they are \(2^0 = 1\) pages long. Two buddy pages combined form a block of level 1, as if it’s \(2^1 = 2\) pages long. Similarly we can combine two buddy blocks of level 1 into one block of level 2, and so on and so forth.

For each block, we will use the page with the smallest index as a representative. For example, when we combines pages 0 and 1 we will get a block of level 1. In that block the page with the smallest index is 0 and this page will be representative of the block.

It’s not hard to generalize the formula above to the blocks of arbitrary levels. Let’s say we have a block of level \(level\) that is represented by page \(x\), to find the buddy of that block we can use the following formula:

For example, for the block 0 of order 1 (meaning 2 pages long block) the buddy index will be 2. For the block 4 of order 1 the buddy index will be 6 and so on.

If you draw a picture you may see that buddies form some kind of a tree structure:

So why do we need to pair memory blocks this way?

In the previous post we spent a great deal of time figuring out how can we combine adjusent free memory ranges effectively in bigger memory ranges to avoid fragmentation.

In the Buddy System we will do the same, but we will not combine arbitrary adjusent blocks together. Instead we will only combine buddies together.

Combining two free buddies together gives us a bigger memory block. Buddy of that bigger memory block might also be free. If so we combine them into even bigger memory block and so on.

Similarly when we are allocating memory, we have to find a large enough memory block and split it until we are left with the block of just the right size. When we split one big block in two and we endup with two buddies. One of the buddies is returned to the allocator and stays free, while we continue to work with the other buddy.

Allocating pages

Now when we have an idea of what buddies are we can get to the allocation algorithm using the Buddy System. First let me start with introducing the structure:

pub const LEVELS: usize = 20;

pub struct BuddySystem<'a> {
    free: [List<'a>; LEVELS],
    pages: &'a [Page],
}

NOTE: Here I assume that the memory for the Page structure was allocated somehow and here we just have a reference to the slice containing the Page structures - that simplifies the description of the algorithm. You can reserve memory for the pages from the memory that the Buddy System manages, just don’t forget to make sure that this memory is marked as busy, so that you will not allocate it to somebody.

For each possible level we have a separate list. As the name of the field suggests we will be keeping free blocks in those lists.

I limit the number of levels to 20 here. It means that the largest block that my implementation will consider will have level 19, or, in other words, it will be \(2^{19}\) pages in size.

It’s an arbitrary restriction that I’ve put in place. You can increase the limit higher than that - there is no problem with that. When it comes to the memory allocation, it hardly makes sense to work with blocks larger than \(2^{64}\), so this number cannot be too big anyways.

Initial State

I’ll start explanation of the allocation alogrithm from giving you some intuation of how the state is tracked in the Buddy System.

To be specific and without loss of generality, let’s assume that we have exactly \(2^{19}\) pages of memory and all of those pages are free. How the Buddy System state would look in this case?

In this state all lists in the free array except the last one will be empty, but the last one will contain just one entry - page 0.

That means that all memory we have combined in one big block of level 19 and page 0 is the representative of this big block. The Page structure of the page 0 in this state should be marked as free and have level set to 19.

In a not particularly revealing graphical representation this state might look something like this:

Now, what if add one more page to the system, so that we have \(2^{19} + 1\) pages of memory in total and all of them are free?

In this case, and you can check it for yourself, this additional page will not have buddies at any level - it will be a loner page. That means that it cannot be combined with any other page and as a result can only be a part of a block of level 0 (block that consists of just that one page).

So the state with this additional page will be almost the same as the state we looked at before. However in addition to the free[19] begin not empty, free[0] also will not be empty. free[0] will contain just one element containing that one additional page. The Page structure for that page will be marked as free and will have the level set to 0.

Adding this one page will change our graphical representation to this:

Now, when we have some intuition about how the sate of the algorithm is tracked let’s get to the allocation itself. The allocation will proceed in two stages:

1. finding a large enough free block;
2. splitting the block in smaller blocks.

Finding a large enough free block

Let’s assume that we want to allocate \(2^x\) pages (we call allocate_pages(x)), where \(x\) is anywhere between 0 and 19. We first have to take a look at the free[x] list and check if it’s empty or not. If the list is not empty, then it means that we have a free block of size exactly \(2^x\). In this case we can just remove the element from the list, mark it as busy and return to the caller the index of the first page in that block.

However, it might happen that the free[x] is empty. In this case we assume that we don’t have a free block of size exactly \(2^x\) available. We might have bigger blocks available though. So we should check other free lists starting from \(x + 1\) until we find a non empty list (if there is one of course).

If all the lists are empty, we conclude that there is no large enough free block to satisfy our request.

NOTE: We might in fact have a large enough contigous free block to satisfy the request. Consider the case when we have only pages 1 and 2 free and we want to allocate block of level 1. Since pages 1 and 2 are neighbours we do have a large enough contigous memory block, however pages 1 and 2 are not buddies according to our definition, so they will not be combined to a larger block by the algorithm.

If we did manage to find a non empty list, then we can just pop any element from that list. The block however might be too big for the request. So to avoid wasting memory we can split the block in two buddies and return one back to the Buddy System. We can repeat this process until we endup with a block of the appropriate size at our hands.

Let’s take a look:

pub fn allocate_pages(&mut self, order: u64) -> Option<u64> {
    unsafe {
        let order = order as usize;
        for level in order..LEVELS {
            if let Some(page) = self.free[level].pop() {
                let index = self.page_index(page);
                assert_eq!(level, page.level());
                self.split_and_return(page, index, order);
                page.set_busy();
                page.set_level(order as u64);
                return Some(index);
            }
        }
        None
    }
}

NOTE: we have to use unsafe code here because we are performing address arithmetic here which is unsafe in Rust and because List operations are unsafe. However all of those are internal details of implementation and don’t leave the function, so it’s fine to mark the whole function as safe.

The general flow of the function is straighforward - we start at the free list responsible for the order order and work our way upwards, until we run out of free lists or find a free list with elements.

Helper function page_index converts a reference to the Page structure to its index. It can be done using basic pointer arithmetics, since all the Page structures are stored in the same slice and we know where the slice begins.

The split_and_return function is responsible for the second stage of our algorithm. If we found a free block, but it’s too large, split_and_return will repeatedly split the block in two buddies and return the buddies we don’t need back to the Buddy System.

Once we are done, we have to mark the block as busy. We do it by marking the representative of the block as busy and recording the level of the block in the Page structure.

Splitting the block in smaller blocks

Now let’s take a look at how split_and_return function works. You probably can guess that it works in the opposite direction compared to the allocate_pages - it starts from a higher level and then works it way towards lower levels.

As input the split_and_return function gets the representative of the free block we found and its index as well as the target level that the caller requested.

Here is how it goes:

unsafe fn split_and_return(&mut self, page: &Page, index: u64, order: usize) {
    let from = page.level() as usize;
    let to = order;

    for level in (to..from).rev() {
        let buddy = &self.pages[BuddySystem::buddy_index(index, level)];

        buddy.set_level(level as u64);
        buddy.set_free();
        self.free[level].push(buddy);
    }
}

Here BuddySystem::buddy_index is a helper function that calculates a buddy index at a give level using the formula we saw above.

So again, the function is not really tricky. It’s given a large block. It splits it in two smaller buddies. One of the buddies go back to the appropriate free list, and the function keep working with the other one. The function keep spliting blocks until it ends up with a block of required size.

For the buddies that the function returns back to the Buddy System it’s important to not just mark them as free, but also set the right level there. It is important for the correct freeing logic, which I’ll cover later, but it’s also important for the implementation of the split_and_return function presented here.

The function depends on page.level() returning the correct value. split_and_return uses page.level() to figure out the level it started from.

And that’s it - it’s the complete allocation implementation. That’s not terribly a lot of code.

You can easily see that the number of operations grows with the size of the free array inside the BuddySystem structure. That’s a serious improvment over the algorithm detailed in the previous post where the free list can be arbitrary long.

We achived this improvement by segregating one large free list into a few smaller free list by the powers of two. You can actually take the same idea of segregating a free list and combine it with the algorithm described in the previous post and don’t bother with all the buddy stuff.

That being said, the implementation is likely to be quite a bit more complicatedthan what you have here with the Buddy System.

Freeing pages

To free pages we need to do the opposite operation. For the block we want to free we need to check if the buddy of the block is also free. If the buddy is free, then we can combine them in a bigger block and repeat the operation.

There are a few caveats that you should keep in mind here. First of all, we need to be careful how we check that the buddy is free. Secondly, we need to keep in mind that some blocks may not even have a buddy at all, as we saw in the example above when we had an odd number of pages.

Let’s start with the second caveat. How can we check that the buddy at a certain level even exists? It’s actually quite easy, all we need to do is to find the index of the hypothetical buddy. If this index points to a page that actually exists, then you have your buddy, otherwise you don’t.

As for the checking if the buddy is free, you obviously have to check if the buddy page is marked as free. However it’s not enough. The caveat comes from the fact that a page might be free, but have a wrong level.

Let’s take a look at an example to demonstrate this case. We will look at four pages: 0, 1, 2, 3. Pages 0 and 1 are level 0 buddies, pages 2 and 3 are level 0 buddies, pages 0 and 2 are level 1 buddies - all of that following the buddy definition above.

Now let’s say that page 0 is free, but page 1 is not, like on this picture:

With this state in mind, imagine that we want to free a block of order 1 that starts from page 2 (so block that contains pages 2 and 3). We check the buddy of page 2 at the level 1 and the buddy index is 0, so we have to look at page 0. And surprise! Page 0 is actually free!

However, because page 1 is not free, the block of order 1 starting at the page 0 as a whole is not free. So we cannot combine two blocks of order 1 in one block of order 2.

After freeing operation completes correctly the sate we should have should look like this:

See how pages 3 and 4 ended up in the free list at the level 1 and the page 0 stayed in the list at the level 0. The only way those can be combined is if we free the page 1, that is not free at the moment.

So to avoid this problem in this situation we have to check both the free bit and the level of the page. In the example above, page 0 is free, but its level is 0 and not 1 as we need.

The rest is purely technical stuff:

use core::cmp;

pub fn free_pages(&mut self, index: u64) {
    let mut index = index;
    let mut level = self.pages[index].level() as usize;

    unsafe {
        while level < LEVELS - 1 {
            let buddy = BuddySystem::buddy_index(index, level);

            if buddy >= self.pages.len() {
                break;
            }

            let page = &self.pages[buddy];
            if !page.is_free() { break; }
            if page.level() as usize != level { break; }

            self.free[level].remove(page);
            // representative of the block is always the first page in that
            // block, so we need to pick the smallest index from two buddies
            index = cmp::min(index, buddy);
            level += 1;
        }

        let page = &self.pages[index];
        page.set_free();
        page.set_level(level as u64);
        self.free[level].push(page);
    }
}

Again, the whole implementation just fits in a few lines of code. And again it’s not hard to see that each iteration of the loop takes constant time and the number of iterations is bounded by the number of elements in the free array.

This time we could not say that it’s a win of the approach described in the previous post since there freeing memory was a constant time operation. That being said, given that the size of free array is very much bounded, we are not far behind.

Instead of conclusion

The implementation I presented in this post is slightly different from the implementation you’ll find in the repository. That being said you should still be able to recognize the overall algorithm.

The reason why the implementation in the repository is different is because it enforces an additional alignment restriction: when you allocate \(2^x\) pages it makes sure that the result is aligned on the \(2^x\) boundary as well. Due to the way BuddySystem works, this alignment property comes almost for free with only a slight modification of the implementation.

As I mentioned before, Buddy System is quite practical algorithm, in the sense that it’s in fact used quite a lot. For example, it’s used in the Linux Kernel for memory pages allocation and it served as a building block of generic memory allocator known as jemalloc.

Buddy System also serves as a simple enough introduction into the idea of segregated free lists. This is an important approach for modern efficient memory allocators. For example. another popular generic memory allocator tcmalloc doesn’t use the Buddy System approach for splitting and coalescing memory blocks, but does heavily employ segregated free lists.

So all-in-all, it’s quite useful algorithm to understand.

I don’t think that I found an obviously convincing approach here, but what can you do…

As always, I have some sources related to the post on GitHub, though in this particular post I will be construction a purely hypothetical example, so you will not be able to find the snippets from the post in the repository.

Static Memory Allocation Strawman

I’d like to start by separating globals and statics. Not all statically allocated objects have to be global. You can look at it this way: we have two questions to anwer here:

• where to store data?
• how to access data?

When we talk about statics we are talking about how the data for the object is allocated. The object may or may not be globally accessible. On the other hand when we talk about globals it’s mostly about who can access the object. We don’t have to allocate memory for global objects statically.

Where to store data?

The programming model of typical imperative programming language that offloads memory management responsibilities to the program itself often provides three high-level options here:

1. we can dynamically reserve memory for the data when we need it from a global memory pool - dynamic memory allocation;
2. we can reserve part of the stack of a thread to store some data - this is a less generic, but still quite useful form of dynamic memory allocation;
3. we can reserve memory in the program binary - similarly to how memory is reserved for the code of the program itself.

All three options provide an answer to the question of where to store data, but all three answers have somewhat different properties. And as you may have guessed statics belong to the option 3.

Option 1 is the most generic, but also is the most demanding. That’s why there are problems where dynamic memory allocation is just not available. So we cannot reduce everything to dynamically allocated memory.

We can however store all the things that we cannot use dynamic memory allocation for on stack. However, while theoretically possible, storing everything on stack create a few practical concerns:

• we need to make sure that we have enough space on stack - with globals compilers just magically handle it for you (well, not magically, but you don’t really need to care about it);

• we need to make sure that the thread and therefore the stack of the tread surives long enough - otherwise we may end up with a dangling pointer on our hands.

Those two practical concerns have to be addressed and it’s by no means always easy to do correctly.

How to access data?

Accessing globals is easy. You don’t need to structure your code to make sure that all the right data is available where you need it - global data is available everywhere.

So naturally, with such a power comes responsibility and this ease of access can be employed in a good way and in a bad way. And, again unsurprisingly, if something can be used in a bad way you can be sure that it will absolutely be used in a bad way at some point.

So I have an impression that the “globalness” property that is why people bash global variables. For the same reason people often bash singleton pattern.

Unfortunately though, globals and statics often come together, but what follows will be specifically about static memory allocation and not about creating global objects.

The Problem

Back to buisness. My problem is that I’m setting up a memory management system in my hobby project. As such dynamic memory allocation is not available and that sucks. I don’t want to allocate all the things I need on stack, since it comes with caveats. So static allocation it’s!

Without loss of generality we will be allocating an array of objects. That’s what I needed to do for my project, but it’s also turned out to be a more interesting problem.

The code is in Rust. You know one of those “safe” languages that shouldn’t allow you to shut yourself in the foot.

The safety of Rust comes with a few caveats:

• Mutable static (regardless of whether they are global or not) objects are unsafe;
• Everything have to be initialized.

One of the fundamental properties of safe Rust typesystem and safe Rust libraries is that there cannot be multiple mutable references to the same object at the same time.

It’s easy to see how this property can be easily violated with global mutable objects. And Rust doesn’t provide means to allocate memory statically in a way that makes safe subset of Rust happy.

NOTE: that Rust does actually provide means to circumvent the restriction on only one mutable reference at a time using so called interrior mutability pattern, however interrior mutability implementation ultimately boil down to using UnsafeCell which implies dropping into unsafe code at some point. The unsafe code might be hidden inside the Rust library, but you can be sure that it’s there. The actual safety guarantees in such cases come from carefully designed interface and library implementation correctness, that should not allow leaking mutable references outside of the library abstractions.

The second caveat is really easy to understand - working with uninitialized state is basically asking for trouble. What makes it a bit difficult in Rust specifically is somewhat lacking support for default initialization. You’ll see what I’m talking about in a moment.

Definitions

Let’s start from some basic definitions. Let’s introduce a type of objects I’d want to allocate:

pub struct AnObject {
  /* there might be some fields here */
}

The AnObject type is not copyable. In my case it was because it contained a mutable reference to a slice and copying those is not allowed in the safe subset of Rust - so there are practical reasons for that.

The importance of the Copy trait implementation (or lack of thereof) will become important later.

What I want to implement is a function like this:

pub fn allocate_slice(size: usize) -> Option<&'static mut [AnObject]> {
   /* some magic happening here */
}

I don’t use statics for the ease of access, I only care about allocating enough memory. So the interface the function provides is what you can expect from an allocator:

• it returns a reference or a pointer insted of AnObject directly;
• it might fail, so the returned value is wrapped in Option.

Since we want to allocate memory statically the lifetime of the returned value is 'static as well.

Of course, we have to guarantee that we will not return references to the same memory twice from this function. Otherwise we’d be violating only one mutable reference at a time rule.

Basic Idea

The basic idea is that we create a statically allocated arrays of AnObject objects inside the allocate_slice function. When the function is called we will need to check if the array has enough elements and if it does we mark it as reserved and return the slice.

On the subsequent allocations I will return None for simplicity, but in general we don’t have to mark the whole array as reserved and can satisfy more then one allocation from the same array if we wanted to.

Let’s take a look at the straighforward attempt to translate the basic idea into code:

pub fn allocate_slice(size: usize) -> Option<&'static mut [AnObject]> {
    const MAX_SIZE: usize = 32;
    static mut BUSY: bool = false;
    static mut OBJECTS: [AnObject; MAX_SIZE];

    if BUSY {
        return None;
    }

    if size <= MAX_SIZE {
        BUSY = true;
        return Some(&mut OBJECTS[0..size]);
    }

    None
}

It’s a rough attempt, so unsurprisingly Rust compiler didn’t like it:

error: free static item without body
 --> test.rs:8:5
  |
8 |     static mut OBJECTS: [AnObject; MAX_SIZE];
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^-
  |                                             |
  |                                             help: provide a definition for the static: `= <expr>;`

Initialization

So what’s the problem? As I mentioned before in Rust everything should be initialized, we didn’t initialize OBJECTS array with anything.

In C and C++ it might not be a problem, but it is not because in C and C++ it’s ok to work with uninitialized data. On the contrary in C and C++ statically allocated objects are initialized.

In C there is concept of zero initialization and statically allocated objects are guaranteed to be initialized with zeros. It actually makes a lot of sense too, but of course there are caveats.

What if for your particular type zero initialization doesn’t make sense and doesn’t produce an object with a valid state. Well, tough luck then.

Situation in C++ is better. It does inherit the zero initialization from C, but when zero initialization is not good enough you can provide a constructor that will initialize the object in whatever state you need. So it’s up to you to tell the compiler if zero initialization is what you need or not.

That’s quite reasonable, but it also comes at a cost - at some point somebody has to call the constructors for the objects. So in C++ some initialization will have to happen during runtime as opposed to compile time.

So what the story in Rust? Well, in Rust when it comes to initialization of arrays the story is quite… well, bad. There are roughly four options:

1. You have to explicitly enumerate each element of the array - quite horrible for any array with more than just a handful elements;
2. If the type implements Copy trait you can provide just one element
   • that’s quite convenient, but Copy trait implementation is a non-trivial requirement;
3. If the type implements Default trait, you can just use Default::default() to initialize the array - again, that’s quite convenient, but doesn’t work for statics initialization;
4. Finally, you can write some unsafe code to initialize the array element by element - which is neither convenient nor does it work for statics.

The option 2 doesn’t work for me because my type doesn’t implement Copy trait.

The options 3 and 4 don’t work for statics because they do initialization during runtime and Rust doesn’t allow runtime initialization for statics, like, for example, C++ does with its constructors.

Which lives us with option 1, which is so terrible that I’d rather cut my hands off.

So what should we do? Well, there is little choice here, but to delay the initialization until the runtime. So essentially we want to initialize array on the first access to the allocate_slice function.

There are multiple options to do that. Rust library provides a dedicated type to deal with potentially uninitialized state: MaybeUninit. However to extract a value from MaybeUninit you have to resort to unsafe code. While for this particular problem unsafe code seem to be unavoidable, we can do better at least for the array initialization with Option.

static mut OBJECTS: Option<AnObject; MAX_SIZE> = None;

We don’t have a good way to initialize an array with some default values during compile time, however we do have an easy way to initialize Option during compile time by storing None there.

As to the runtime initialization, for the example sake I will resort to implementing Default trait. This gives us the following code:

pub struct AnObject {
    /* there might be some fields here */
}

impl Default for AnObject {
    fn default() -> AnObject {
        AnObject {}
    }
}

pub fn allocate_slice(size: usize) -> Option<&'static mut [AnObject]> {
    const MAX_SIZE: usize = 32;
    static mut OBJECTS: Option<[AnObject; MAX_SIZE]> = None;

    if OBJECTS.is_some() {
        return None;
    }

    if size <= MAX_SIZE {
        OBJECTS = Some(Default::default());
        return Some(&mut OBJECTS.as_mut().unwrap()[..size]);
    }

    None
}

Note how using Option allowed us to get rid of BUSY flag, since Option provides us with means to figure out if the allocate_slice function has been called before or not.

Naturally, if you want to be able to satisfy more than one allocation from allocate_slice function you’d have to keep track what parts of the array has been allocated already and just one Option wouldn’t be enough.

The OBJECTS.as_mut() just converts the Option<[AnObject; MAX_SIZE]> to an Option with a mutable refernce to the data inside. The rest should be quite straighforward.

Mutability

Unfortunately the new code doesn’t compile either. If you try to feed it to the compiler you’ll get a bunch of errors like this:

error[E0133]: use of mutable static is unsafe and requires unsafe function or block
  --> test.rs:15:8
   |
15 |     if OBJECTS.is_some() {
   |        ^^^^^^^ use of mutable static
   |
   = note: mutable statics can be mutated by multiple threads: aliasing violations or data races will cause undefined behavior

As the compiler error suggests, imagine the case of multithreaded code. If this function were to be called from multiple threads concurrently, since it doesn’t provide any kind of syncrhonization we will have a race condition on our hands.

Note though, that the problem here is more general than just a case of bad concurrency. As you can see we basically return from the function a mutable reference to the statically allocated data.

By just looking at types for Rust compiler it’s impossible to proove that we never return a mutable reference to the same object twice and therefore do not create multiple mutable references.

Coincidentally (or maybe not) when you wrap an object that you want to mutate in Mutex or some similar syncrhonization primitive in Rust you don’t have to make the Mutex itself mutable.

Why? Well, as far as Rust type system is concerned “immutable” Mutex can return a mutable reference to its internals (though it does it indirectly). So Mutex “cheats” Rust type system, but it does provide runtime guarantees that make up for that.

Not suprisingly Mutex does it via the interior mutability pattern that I mentioned above, so you can bet that the implimintation of Mutex uses unsafe Rust internally, but provides a safe interface to the users.

Can we use Mutex in this example? Unfortunately not. As of now you cannot create static Mutex in Rust because there is no way to initialize it in compile time.

We can’t even resort to the runtime initialization trick we used earlier because there is no guarantees that initialization of Option will be atomic. Not to mention, that such a static Option will have to be mutable and that completely defeats the point.

So short of implementing your own syncrhonization primitive that allows compile time initialization you will have to stick to the unafe code. So here is the version of the code I settled on:

pub unsafe fn allocate_slice(size: usize) -> Option<&'static mut [AnObject]> {
    const MAX_SIZE: usize = 32;
    static mut OBJECTS: Option<[AnObject; MAX_SIZE]> = None;

    if OBJECTS.is_some() {
        return None;
    }

    if size <= MAX_SIZE {
        OBJECTS = Some(Default::default());
        return Some(&mut OBJECTS.as_mut().unwrap()[..size]);
    }

    None
}

Generalization (Failure!)

Ok, we have a more or less sensible approach to static allocation. Can we generalize it?

Rust provides a few options to write generic, or, I should say, polimorphic code. For this particular problem we care about compile time polimorphism only. Which leaves us with a few options:

• Rust generics
• Rust macroses
• code generation.

I have a personal despise for code generation. My personal opinion here is driven by my negative experince trying to read code of the projects that involve code generation step as part of their build process. So I didn’t even consider generating code.

Having an experience with C++ templates I decided to go with Rust generics as the problem looked like an easy one. I figured that Rust has both type generics and const generics, just like C++, so the code like this should work just fine:

pub unsafe fn allocate_slice<T: Default, const N: usize>(size: usize) -> Option<&'static mut [T]> {
    static mut OBJECTS: Option<[T; N]> = None;

    if OBJECTS.is_some() {
        return None;
    }

    if size <= N {
        OBJECTS = Some(Default::default());
        return Some(&mut OBJECTS.as_mut().unwrap()[..size]);
    }

    None
}

So what is this monstrosity is supposed to mean? Well, our function has two generic parameters: the type of the allocated objects and the maximum size of the storage. There is nothing surprising there - we just replace AnObject with a generic T and hardcoded 32 with N.

I additionally require the type T to implement the Default trait to be able to initialize an array of objects of type T - that’s exactly how I did it with AnObject type before as well.

All-in-all, it’s not that bad and by C++ standards that is pretty ordinary use of generics. There is one downside with this implementation though - it doesn’t compile:

error[E0401]: can't use generic parameters from outer function
  --> test.rs:12:33
   |
11 | ...e_slice_gen<T: Default, const N: usize>(size: usize) -> Option<&'stat...
   |                - type parameter from outer function
12 | ...S: Option<[T; N]> = None;
   |               ^ use of generic parameter from outer function

error[E0401]: can't use generic parameters from outer function
  --> test.rs:12:36
   |
11 | ...e_gen<T: Default, const N: usize>(size: usize) -> Option<&'static mut...
   |                            - const parameter from outer function
12 | ...ion<[T; N]> = None;
   |            ^ use of generic parameter from outer function

error: aborting due to 2 previous errors

Turns out in Rust you cannot use generic parameters as part of static object type or initialization. The error from the Rust compiler is not particularly descriptive, but if you run rustc --explain E0401 you’ll get a few examples and should be able to understand why the error message is the way it is.

The same documentation provides a few ways to circumvent the problem for some cases, but unfortunately none of them works for me, at least not without moving problem to runtime.

The reason for this is still a mistery for me, but from googling around I got that it has more to do with the linking rather than with some fundamental property of the Rust language. You can read more by looking at this comment.

Unfortunately I don’t know enough about Rust dylibs, so it’s hard to understand why instantiation of such generics is a problem for dylibs.

BTW, if you got scared by “monomorphisation” don’t be. Behind the scary word there is an easy to understand concept. Just take a look at static dispatch.

This leaves us with the Rust macroses as the last resort. However I didn’t go that way and left the code as it’s without trying to further generalize it. You can take that as an exercise and implement a Rust macro for static memory allocation.

Instead of conclusion

Well, I didn’t expect that working with statics in Rust would be that much of a pain. I’d say Rust would benefit a little bit from introducing a concept of zero initialized types.

And judjung by existance of intrinsics::assert_zero_valid Rust creators do not object to the concept on the fundamental level. With some efforst it could turned into some kind of special trait Zero, similarly to Copy, Sync or Send.

Anyways, all well that ends well. I learned something new (for example, that Rust generics aren’t quite at the same level as C++ templates), so that’s something.

In this post I’m going to cover the problem that Devicetree is trying to solve, briefly touch on the available alternatives and finally show some code for parsing the binary representation of the Devicetree (a. k. a. Flattened Device Tree or DTB).

All the sources are available on GitHub.

Introduction

When you boot your PC it somehow figures out how many CPUs the system has, how much memory is installed in the system, it figures out what HDD or SSD connected to the system, that there is a keyboard and a mouse, etc.

Likely you don’t need to install a new OS when you add more memory to the system or when you change a mouse. So the same OS can serve multiple different variants of hardware. To put it another way OS doesn’t always know in advance what hardware it runs on and has in some way discover that information.

There are multiple ways OS can discover that information. For example, most of external devices directly or indirectly connect to the system via PCI and USB. Those two support means to automatically enumerate connected devices and find out some basic information about them. Using this basic information OS can figure out if it has a driver that supports the connected devices and loads it.

However, CPUs and memory are not some kind of PCI or USB devices. PCI and USB host controllers cannot depend on PCI and USB enumeration mechanisms either. So for those a different mechanism have to be used.

In simplest cases OS and drivers can just probe for the connected devices. That basically means that a driver can try to interact with the device in hope that it’s there. If the device responds, then it must be there, and it doesn’t respond, then it’s not there. It doesn’t work though with things like memory.

When the simplest method doesn’t work, in the PC world the problem can be addressed via BIOS, UEFI, ACPI or a combination of those. They provide various interfaces to explore the available memory and basic hardware.

However hardware platforms in the PC world are more or less standartized. In the embedded systems worlds there is a bit more variety and there an alternative configuration interface became popular: Devicetree Specification.

Historically Devicetree Specification originates from Open Firmware which for most intents and purposes is long gone now, but the Devicetree Specification is alive and well.