Structs, arrays and linked lists in assembly

A C function passes your assembly a pointer to a struct student, and the assembly needs one number from it: the student’s marks. Machine code has no field names, so the marks are simply the 4 bytes that start 16 bytes past that pointer, and the ABIapplication binary interface (ABI): The rules that let separately compiled machine code work together on one platform, from the size of each C type and the calling convention to the format of object files. More in “Calling conventions: arguments and returns” is what puts them there.

Structs, arrays and linked lists in assembly all come down to that idea, an address plus a byte offset. A struct is a set of fields at fixed offsets, an array of structs repeats the struct at a fixed distance, and a linked listlinked list: A chain of records in which each node holds the address of the next one and the last holds a null pointer, so reaching a node means following every pointer before it from the head. keeps the next node’s address inside each node. Get one offset wrong and nothing complains: the program reads its neighbour’s bytes and carries on.

Each member of a struct sits at an aligned offset

The record used throughout is struct student { char name[16]; int marks; double cgpa; }. Its members hold 16 + 4 + 8 = 28 bytes, yet sizeof reports 32. The extra 4 bytes are paddingstruct padding: Unused bytes a compiler places between the members of a struct, or after the last one, so that every member starts at its alignment and every element of an array of the struct does too., and the 64-bit ABIs of Linux and macOS place them by the same three rules:

• Every type has an alignmentalignment: The rule that a value of a type must start at an address that is a multiple of a fixed number of bytes: 4 for an int and 8 for a double or a pointer on 64-bit ABIs.: 1 for a char, 4 for an int, 8 for a double, a long or a pointer.
• Members stay in the order they are declared, and each starts at the next offset that is a multiple of its alignment.
• The struct takes the largest alignment among its members, and its size rounds up to a multiple of it.

Step through the 32 bytes and watch the gap open in front of cgpa:

The name fills bytes 0 to 15, and the int fits at 16 because 16 is a multiple of 4. The double cannot start at 20, so 4 padding bytes push it to 24, and 24 + 8 = 32 is already a multiple of 8, so no padding follows it. A record that ends on a small member does get some: struct { long id; char grade; } holds 9 bytes of data and takes 16, so the long of the next array element still starts on a multiple of 8. The C standard allows unnamed padding inside and after a struct, and each ABI document fixes exactly where it goes, so every compiler for one ABI produces the same layout.

Assembly reads a field with one load at its offset

The C compiler already knows the layout, so let it print the numbers. The harness prints sizeof and the offsetofoffsetof: A C macro from stddef.h that gives the distance in bytes from the start of a struct to one of its members, as a constant the compiler works out from the ABI's layout rules. of each member, then hands Meera’s record to an AArch64 function that returns her marks:

// struct student has three members of different sizes. The C side prints where each
// one sits and how big the whole record is; the assembly side reads one field by its
// offset. Compile together: clang -o student student.c marks.s
#include <stdio.h>
#include <stddef.h>

struct student {
    char   name[16];   // 16 bytes, alignment 1
    int    marks;      // 4 bytes, alignment 4
    double cgpa;       // 8 bytes, alignment 8
};

// Defined in marks.s: return the marks field, read with a single load at its offset.
int student_marks(const struct student *s);

int main(void) {
    printf("sizeof(struct student) = %zu\n", sizeof(struct student));
    printf("offsetof name  = %zu\n", offsetof(struct student, name));
    printf("offsetof marks = %zu\n", offsetof(struct student, marks));
    printf("offsetof cgpa  = %zu\n", offsetof(struct student, cgpa));

    struct student meera = { "Meera", 87, 9.12 };
    printf("assembly read of marks: %d\n", student_marks(&meera));
    return 0;
}

// student_marks(const struct student *s) -> int
// x0 holds the address of the record. marks is a 4-byte int that the ABI places
// 16 bytes in, so one load with a +16 offset returns it. No field name survives into
// the machine code; only the number 16 does.
.text
.globl _student_marks
.p2align 2
_student_marks:
    ldr  w0, [x0, #16]      // read marks: base + the field's byte offset
    ret

"""Read a struct's layout from C, and one field from assembly.

student.c prints the size of struct student {char name[16]; int marks; double cgpa;} and the offset of each member,
then calls an AArch64 function that returns marks with a single load. The offsets are 0, 16 and 24 and the size 32,
so the assembly reads marks at [x0, #16]. The disassembly shows that one load.
"""
import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run(
    """
# Build the C harness together with the AArch64 field reader, then run it.
clang -o record/student record/student.c record/marks.s
./record/student; echo "exit=$?"
# The reader is a single load at the marks offset; the field name is gone, only 16 remains.
llvm-objdump -d record/student | sed -n '/<_student_marks>:/,/ret/p'
"""
)

# Build the C harness together with the AArch64 field reader, then run it.
$ clang -o record/student record/student.c record/marks.s
$ ./record/student; echo "exit=$?"
sizeof(struct student) = 32
offsetof name  = 0
offsetof marks = 16
offsetof cgpa  = 24
assembly read of marks: 87
exit=0
# The reader is a single load at the marks offset; the field name is gone, only 16 remains.
$ llvm-objdump -d record/student | sed -n '/<_student_marks>:/,/ret/p'
0000000100000594 <_student_marks>:
100000594: b9401000    	ldr	w0, [x0, #0x10]
100000598: d65f03c0    	ret

C printed offsets 0, 16 and 24 and a size of 32, and the assembly returned 87 with a single ldr w0, [x0, #16]. The pointer arrives in x0 and the field’s offset rides in the instruction as an immediate, the base-plus-offset form of addressing modes. The result goes back in w0, where the C prototype expects an int. The disassembly prints the offset as #0x10, and nothing in the machine code says the field is called marks. A 32-bit load into w0 takes exactly the 4 bytes of the int; ldr x0 at the same offset would also pull in the 4 padding bytes after it.

The same address-plus-offset idea carries everything that follows. Arrays of structs repeat the record at a stridearray stride: The distance in bytes from one element of an array to the next. For an array of structs it is the struct's size, padding included, so element i starts at the base plus i times the stride. of sizeof bytes, so element i starts at the base plus i times the stride. Linked lists in assembly are walked by pointer chasingpointer chasing: Walking a data structure by loading an address from memory and then loading through that address, as a linked-list walk does at every node.: each node holds the next node’s address, so every step loads that address before it can move on. Offsets generated from C are written by a small C program into a file the assembly includes, so no offset is typed by hand. The long double type is the member to watch, because its size differs between the Apple and Linux ABIs.

Practise: move a field and predict the offsets

Copy record/student.c and record/marks.s to a folder of your own and build them with the clang line of the session above. Write each prediction down before you run.

1. Add short year; right after marks, give it a value in the initializer, and predict all four offsets and the size.
2. Move year above marks, predict again, run, and change the one number in marks.s that now reads the wrong bytes.
3. Make marks a long, and work out whether its offset, its load or both must change in marks.s.

Arrays of structs, two ABIs and an offset that drifts, run and fixed Pro: opens with a Pro, Premium or Ultimate pass

Linked lists in assembly: length, search, reversal and a cycle check, recorded Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Each of these takes the layout rules into a situation from real code: a struct written to a file under one ABI and read under another, a record that changed beneath hand-written assembly, and a list that might loop.

Key takeaways

• A struct’s members keep their declared order, each starts at the next multiple of its alignment, and the size rounds up to the largest alignment, so struct student is 32 bytes with cgpa at 24.
• Padding is part of every record: the 4 bytes before cgpa are why summing the member sizes gives 28 instead of 32.
• Machine code keeps offsets, not field names, so ldr w0, [x0, #16] reads the marks only because C placed them at 16, and the width of the load must match the field.
• Asking the compiler for sizeof and offsetof instead of counting bytes by hand gives the numbers that arrays of structs and linked lists in assembly are built on.