Memory Is One Array

03 · Memory Is One Array¶

The question¶

If memory is one array of bytes, what is a C declaration saying about it?

A declaration is not read left to right, and every piece of one turns into something concrete — an amount of storage, a width to step by, an instruction the compiler emits. This chapter takes declarations a few at a time and checks what each one means against what the compiler emitted, rather than against a rule for reading them.

Change the program as you go. ./run firstc builds and runs it, and the fastest way to find out whether you have the model is to predict what an edit will print before you make it.

If you are not sure whether you want this chapter or ch04, Part I routes you.

The material¶

One whole program¶

Every piece of C you have seen in this book so far has been a fragment — lifted out of a file, with no beginning and no end. Here is a complete one, and it is the shortest complete one this book has.

/* firstc — one complete C program, before any of the parts.
 *
 * Copyright 2026 Chris Snow. Apache-2.0 — see LICENSE-CODE.
 *
 * The memory-as-one-array chapter shows this file whole, because until now every piece of C in this book has been a
 * fragment lifted out of somewhere larger. A reader who has never written C has never seen where
 * the pieces go.
 *
 * It is also the chapter's first measurement, and it is deliberately not an address. Printing one
 * would show a number that differs on every run and means nothing on its own; what is worth
 * seeing is the *relationships* between addresses, which are the same every time:
 *
 *   that `*&x` is `x` again, so `&` and `*` undo each other;
 *   that `p + 1` moves by the size of what `p` points at, and by nothing else.
 *
 *   cc -o firstc firstc.c && ./firstc
 */

#include <stdint.h>
#include <stdio.h>

int main(void) {
  int value = 42;

  /* `&value` is where it lives; `*` goes back to what lives there. The two are inverses, and
   * this line is the whole of that claim. */
  int *where = &value;
  printf("firstc value %d roundtrip %d\n", value, *where);

  /* Two arrays, same length, different element type. The distance between one element and the
   * next is not one byte — it is one *element*, and how big an element is comes from the type. */
  int32_t narrow[2];
  int64_t wide[2];
  printf("firstc step int32 %td\n", (char *)&narrow[1] - (char *)&narrow[0]);
  printf("firstc step int64 %td\n", (char *)&wide[1] - (char *)&wide[0]);

  printf("end firstc\n");
  return 0;
}

Four things in it are not the subject of this chapter and are worth naming once so they stop being in the way.

#include pastes in a file of declarations, so that printf is a name the compiler has heard of before you use it. main is where a program starts, and there is exactly one. printf writes to the terminal, and the %d in its first argument is a hole the next argument fills. return 0 at the end of main is the program’s exit status, and zero means nothing went wrong.

Build it and run it:

./run firstc

That is the whole loop this part asks you to get into: change the source, run it again, look at what came out. ./run knows how every program in this book is built — which compiler, which flags, which machine — so the only thing you have to think about is the source. ./run --list shows the lot.

Conditions: target host · aarch64 cross build, any machine — run under user-mode QEMU for counts only · aarch64-linux-gnu-gcc · -O2 -g -Wall -Wextra -static · 2026-09-17 · Source: bench/results/firstc.json, code hash dc5dabccb8df99aa.

The rest of the chapter explains why those four numbers are what they are.

Memory is one array, and everything has an index¶

The language you already use has named things that hold values, and a runtime that knows where they are. C has one array of bytes, numbered from zero, and everything you declare is a stretch of it. That is the model, not a simplification for teaching, and every difficulty later in the book is a difficulty about it.

Three questions follow, and they are the ones worth asking of any C you read:

• Where does this live? In the current call’s region, in one that lasts the whole run, or in memory somebody asked for.

• How long does it stay there? Until the function returns, for ever, or until somebody says otherwise.

• How big is it? A question about its type, and the reason types exist at all.

“Where” has a coarse answer and a precise one. The coarse one is the region. The precise one is an index — the position of the thing’s first byte in that one array — and an address is that index, and nothing else.

& and *, watched rather than described¶

Two operators, and they are inverses.

&x gives the index of where x lives. *p goes to the index held in p — a pointer, a variable whose value is an index — and reads what is there. So *&x is x again, which is the second row of the table above, printed by a program rather than asserted by a paragraph.

The program never prints an address, because an address is different every time the program runs and means nothing by itself; there is no fact in it. What is the same every time — and what is worth knowing — is the relationship between two addresses. The last two rows are that relationship, and they are the whole of pointer arithmetic.

Two arrays, both of two elements. The distance from the first element to the second is four bytes in one and eight in the other, and nothing in the expression that computed it said four or eight. The type did.

A pointer is an index with a type stapled to it¶

int *p says: p holds an index, and what lives at that index is an int. The type is not decoration. It is how the compiler knows how many bytes to take, how to interpret them, and — this is the part that surprises people — how far one step is.

That is the fact from the outside. Here it is from underneath.

Two functions, each taking a pointer and returning the element after the one it points at. The source of each is the same three characters, p + 1.

int32_t sysfs_step_narrow(const int32_t *p) { return *(p + 1); }

int64_t sysfs_step_wide(const int64_t *p) { return *(p + 1); }

If 4(a0) and the address column are unfamiliar, ch02 is the key for reading these. What is needed here is one line of it: parentheses mean memory, and the number in front is a byte offset, so 4(a0) is the memory four bytes past the address in a0. Watch that number.

The narrow one:

sysfs_step_narrow compiled for riscv64 at -O2 — the xv6 target’s instruction set, 2 instructions.

0000000000000000 <sysfs_step_narrow>:
   0:	lw	a0,4(a0)
   2:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/declarations-riscv64.json, code hash 2cf5e7f79ec7d0c2.

The wide one:

sysfs_step_wide compiled for riscv64 at -O2 — the xv6 target’s instruction set, 2 instructions.

0000000000000004 <sysfs_step_wide>:
   4:	ld	a0,8(a0)
   6:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/declarations-riscv64.json, code hash 2cf5e7f79ec7d0c2.

One load each, and they are not the same load. The narrow one loads a word from four bytes along; the wide one loads a doubleword from eight. (The ret after it is the function returning, which is why each listing is two instructions rather than one.) + 1 never means “one byte”. It means one element, and the element size comes from the type, and the type is not in the expression you are reading.

This is why a pointer’s type matters even when you never dereference it — never apply * to it — and it is why a cast to a different pointer type changes what arithmetic on it does. Nothing about p + 1 on the page tells you the answer; you have to know what p was declared as.

Reading a declaration¶

C declarations are famously hard to read and the reason is that they are written to mirror use. int *p is not “p is a pointer to int” written awkwardly. It is “the expression *p has type int” — the declaration shows you the shape of the thing that finally yields an int.

Once you know that, the rule is mechanical: start at the name, and read outwards, taking whatever binds tightest first. [] and () bind tighter than *, and parentheses override.

The two pairs that differ only by parentheses are the ones worth doing slowly, and they are not a puzzle for its own sake: int (*f)(void) is how every device driver in ch19 is reached, and const int * against int *const is a distinction the kernel relies on constantly to say which of two things it promises not to change.

Problem 3.1 is this table, generated rather than reproduced, with declarations you have not seen.

Arrays, and why a pointer cannot carry a length¶

An array is a run of elements, and its name in most expressions turns into the index of its first one. Pass an array to a function and what arrives is a pointer — the length does not travel with it, and cannot, because there is nowhere in a pointer to put it.

That is why every kernel function that takes a buffer also takes a count. It is not a style preference; there is no alternative. ch05 shows the compiler discarding a length written into a parameter’s brackets, and ch13 has the bug it causes.

A string in C is this with one extra convention: a run of bytes ending in a zero byte. The zero is the length, stored at the end instead of the beginning, which makes finding the length a loop rather than a lookup and makes forgetting to write it a bug that reads off the end of the array.

Structs, and what -> really is¶

A struct is several objects at fixed offsets from one address. record->third means: take the index in record, add the offset of third, and read what is there.

int64_t sysfs_reach_through(const struct sysfs_record *record) {
  return record->third + record->second;
}

sysfs_reach_through compiled for riscv64 at -O2 — the xv6 target’s instruction set, 4 instructions.

0000000000000008 <sysfs_reach_through>:
   8:	lw	a4,4(a0)
   a:	ld	a0,8(a0)
   c:	add	a0,a0,a4
   e:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/declarations-riscv64.json, code hash 2cf5e7f79ec7d0c2.

Two loads and an add. There is no member lookup. The names second and third do not exist by the time the machine sees this; they became the numbers in those two load instructions, decided when the file was compiled. a->b is exactly (*a).b, and both are exactly “an offset on a load”.

Which offsets, and why they are not simply the sum of the sizes before them, is ch13’s subject. What matters here is that the offsets are fixed at compile time and the name is gone.

Casts, and the two kinds of arithmetic¶

A cast says “treat these bytes as this type instead”. Between pointer types it changes nothing about the bytes and everything about what arithmetic on them means, because the type is what sets the step size.

A kernel casts constantly between a pointer and a plain integer, because an address genuinely is a number there — a physical page is a number, a device register is a number — and the two kinds of arithmetic are different:

• Pointer arithmetic scales by the element. p + 1 moves by sizeof(*p), the size in bytes of what p points at.

• Address arithmetic does not. (uint64)p + 1 moves by one byte.

Rounding an address to a page boundary is address arithmetic, which is why the kernel’s rounding macros cast to an integer type first and back afterwards. Problem 3.3 is writing the pair, and the thing to get right is that rounding up and rounding down are not the same expression with a different sign.

A structure that points at its own kind¶

The last construct, and the one that makes the next chapter possible.

struct node {
  int value;
  struct node *next;
};

A struct cannot contain itself — it would have no size — but it can contain the index of another one, because an index has a size regardless of what it points at. That single fact is what every list, tree and queue in the kernel is built from, and ch04 shows the free list xv6 makes out of the free memory itself.

What we measured¶

Nothing here is a cost. Two things, and they are the same fact seen from two sides.

First, what the program printed — the chapter’s claims in a form you can reproduce: that *&x is x, and that consecutive elements are one element apart rather than one byte. The runner refuses to stamp a run where either stops holding, because the chapter asks the reader to take both on trust for exactly as long as it takes to run the program.

Then three listings, captured by the machinery ch12 explains and re-captured by CI on every push, showing the same two facts from underneath: that p + 1 compiles to a different offset for different element types, and that -> compiles to an offset on a load with no lookup of any kind.

Both are facts about what this compiler did. That they are required is a claim about the standard ISO/IEC JTC1/SC22/WG14 (2018) and would hold on a compiler emitting entirely different instructions.

What this cannot tell you¶

How to program. Deliberately. Control flow, functions, operators and the shape of a program are assumed from whatever language you already use, and C spells them much as it does. What is not assumed is the memory model, because that is the part your other language was built to hide.

What any of this costs. No chapter in this part has a clock in it. ch25 is where following a pointer acquires a price, and the price turns out to depend on something no listing here can show.

Why the struct offsets are what they are. This chapter shows that -> becomes an offset. It does not say how the offsets were chosen, and the answer is not “add up the sizes” — ch13 takes it apart.

Whether your pointer is valid. C has no answer to this and neither does the hardware, until ch18. A pointer is an index; nothing checks that the index means anything.

Problems¶

Three, in tests/memory_is_one_array/declarations.c.

3.1 — Say what each declaration names. The test generates declarations and asks you to classify them. The two that differ only by parentheses are the point of the exercise, and they are the two you will meet again in ch19.

python3 -m pytest tests/memory_is_one_array/test_problem_1_declarations.py

3.2 — Walk a buffer without an index. Reimplement three of the routines the kernel supplies for itself, using pointers that move rather than a subscript. The versions in kernel/string.c are written this way, and the exercise is so that you can read them.

python3 -m pytest tests/memory_is_one_array/test_problem_2_walking.py

3.3 — Round an address both ways. Given an address and a power-of-two alignment, round up and round down. Address arithmetic, not pointer arithmetic, and the kernel does this on every page it touches.

python3 -m pytest tests/memory_is_one_array/test_problem_3_rounding.py

Where to go next¶

The C standard ISO/IEC JTC1/SC22/WG14 (2018) is the authority on the claims here that are about the language rather than about a compiler — §6.5.6 on what adding an integer to a pointer means, and §6.7.6 on how a declaration is assembled from the inside out.

ch04 is next, and it is the chapter for a reader who already writes C. Every assumption an application programmer is entitled to make — that allocation succeeds, that the library is there, that memory is memory, that one thread is looking — stops holding, and the chapter counts what is missing rather than asserting it.