Bits, Pointers and Memory
There is a function
called malloc. Programs call it when they need memory and it hands back a number. It is
a few hundred lines of C, it runs inside almost everything you have ever used, and hardly anybody who
calls it has read it. Can you write one?
Not yet. malloc hands out bytes, and a byte will agree to be
almost anything. So start with how to read the code on these pages, then the eight switches, and work
up: numbers that wrap, decimals that cannot be stored, letters that need four bytes, addresses, the two
places memory comes from. By Step 11 you are the allocator, servicing requests by hand.
Nothing here gets described and then left alone. You will overflow an integer on purpose, cut a word in half through the middle of a letter, read past the end of an array to see what is parked next door, and fragment a heap so badly that a small request fails with most of the memory sitting empty. The mechanism turns up after the failure, as the fix for it.
The steps, in order
The code on these pages, and how to read it
You will meet short pieces of C on almost every page here. C is a programming language: a way of writing instructions down precisely enough that a machine can carry them out. It was designed in 1972, most operating systems are still written in it, and it hides less of the machine than anything else in common use, which is why it is the one used in this course. You never have to write any of it. Every listing here is read, not typed.
A machine cannot run text, so a second program called the compiler reads what you wrote and turns it into the numbered instructions the processor obeys. That happens once, before your program ever runs. By the time the program is running the compiler has finished and gone, which turns out to matter in about half the steps that follow.
Do I have to type any of this in?
No. Every listing in this course is there to be read, the way you would read a recipe without cooking it. Nothing you press is being compiled, and no lab is running code you wrote.
Each lab is a working model of the mechanism the listing describes. The point of reading the C is that the listing and the model are talking about the same thing, so you can check one against the other.
A short list of shapes covers almost every line you will meet. Take each fragment below, decide what you think it says, then look.
A program is a whole list of instructions. A statement is one
of those instructions, usually one line ending in a semicolon. A variable is a named box in
memory holding a value, and int x; is a declaration: it asks for the box and gives it
a name. A function is a named piece of a program you can go off and run from anywhere, handing it
values and getting one back. Those four words carry the rest of the course.
#include <stdio.h> /* bring in the printing tools */
int add(int a, int b) { /* a function: two numbers in, one number back */
return a + b;
}
int main(void) { /* every C program starts at main */
int x = 2; /* set aside a box called x and put 2 in it */
int y = add(x, 3); /* run add with 2 and 3, so y ends up 5 */
if (y == 5) { /* two equals signs, so this is a question */
printf("%d\n", y); /* print the number, then start a new line */
}
return 0;
}
What are main and printf doing there?
main is the function the machine calls first. Every C program has exactly one, and when
main returns the program is over. return 0 is the program's way of saying it finished
without trouble.
printf is the standard way of printing in C. Inside its text, %d means put
a number here, and the number comes from the value listed after the text. \n is not two
characters on the screen; it is one instruction meaning start a new line. Both turn up again in Step 9.
Reading a line is one skill. Writing one is another, and it is worth ten minutes now so that no listing later on is a picture rather than a sentence.
x = 8; and, further down,
the line if (x == 8). One of those changes something and one of them only asks. Which is
which, and what would happen if the second one were written with a single equals sign?x = 8; puts 8 into x.
if (x == 8) asks a question and answers true or false. Write if (x = 8) and C
does not complain: it puts 8 into x, then treats the result, 8, as the answer to the question, and
anything that is not zero counts as yes. So the branch runs every single time and x has been quietly
changed on the way past. This bug is old enough to have a standard defence, which is writing the
constant first: if (8 == x) refuses to compile if you drop an equals sign.Why does C let you put an assignment inside an if at all?
Because in C an assignment performs an instruction and also produces a value, which is the value that
was stored. That lets you write while ((c = next()) != 0), which reads the next thing,
keeps it, and tests it in one line. Working programmers do use it.
The price is that the mistake and the trick are spelled the same way, so the compiler cannot tell them apart. Modern compilers ask you to write extra brackets round a deliberate one, and warn about the rest.
Eight bytes, seven meanings
Here are eight bytes. Not eight numbers and not eight letters: eight bytes, which is eight groups of eight switches, each switch either on or off. That is the entire contents of the machine's memory, repeated a few billion times. One switch is called a bit, short for binary digit: the smallest thing a machine can remember and the smallest thing you can change. Eight bits make a byte. From here on those are the two words used, and they mean exactly the switches you are looking at.
Why eight switches make 256 patterns
One switch has two settings. Add a second and each of those two splits into two, so there are four. A third gives eight. Every switch you add doubles the count, so eight of them give 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2, which is 256.
That is why a byte counts 0 to 255 and then stops. There is no 256th pattern left over to hold the next number.
A byte does not know what it is. It holds a pattern. Whether that pattern counts as
the number 72, the letter H, or how much red is in one pixel is decided by the code doing the
reading, and nothing about that decision is recorded in the byte.
So change the bytes below and read them seven ways at once. Between one reading and the next, the bytes do not move. Only the question changes. A stretch of memory set aside to hold something, with nothing yet said about what, is called a buffer. The eight bytes below are a buffer, and the seven buttons are seven different opinions about what is in it.
What the 0x in front of a number means
The boxes below label each byte with two characters, like 48 or C8. That
is base sixteen, usually called hex. The digits run 0 to 9 and then carry on with A, B, C, D, E, F, so A
is ten and F is fifteen.
One hex digit covers exactly four bits, so two of them cover one byte with nothing left over. When
you see 0x48, the 0x is only a label saying read the rest as hex. The value
is 4 sixteens plus 8, which is 72.
When you write int x, no byte anywhere changes. You are telling
the compiler which of these readings to use, so it can pick the right instructions and the right number of
bytes. A type is a note to the compiler about how to interpret bytes that neither of you has seen yet,
and if the note is wrong, nothing on the machine will notice.
Who is this compiler, and what does it do with what I write?
Step 0 said what the compiler is: the second program that reads your text and turns it into the numbered instructions the processor obeys. The part that matters here is what one of those instructions is, and when the turning happens. One instruction is one small thing the hardware knows how to do: fetch four bytes, add two numbers, jump somewhere else. The turning happens once, before your program starts, so by the time the program is running the compiler has finished and is not there to help.
That is why the callout matters. Writing int x changes no byte at the time the program
runs. It is a message to the compiler, saying: whenever I use the name x, set aside four bytes for it
and read them as a whole number. The compiler takes you at your word and generates instructions to
match. If those bytes really held a letter, or half of a decimal number, nothing anywhere will ever
find out.
1 into
a file. A program on a different machine reads those same four bytes back as a 32-bit number and gets
16,777,216. The file was not corrupted and neither program has a bug in its arithmetic. What
happened?01 00 00 00, the other read it as 0x01000000, which is 16,777,216. Both did
exactly what they were told. This is why file formats and network protocols always state their byte
order in writing. The bytes carry no hint of it.Where 16,777,216 comes from
The four bytes in the file were 01 00 00 00. The second machine treated the first byte
as the most important one, so that lone 1 was not counting single units. It was counting 256 x 256 x
256.
Multiply that out and you get 16,777,216. Moving a byte one place up the line multiplies what it is worth by 256, the same way moving a digit left in ordinary decimal multiplies it by ten.
Bit operations, with intent
There are four operations worth knowing, and each one exists because somebody wanted to reach into a byte and change part of it while leaving the rest untouched.
AND with a 0 forces a bit off and AND with a 1 leaves it alone, so AND is how you keep
some bits and discard the others. OR with a 1 forces a bit on and leaves the rest alone. XOR with a 1 flips
it. A left shift slides the whole pattern one place up, which doubles the number, for the same reason that
moving a digit left multiplies by ten in decimal. In C each of these is written as a symbol rather than a
word. & is AND, | is OR and ^ is XOR. ~ flips
every bit on its own, << is a left shift, and >> is the shift the
other way. Those symbols are the buttons in the lab below. In the listing, anything between /* and
*/ is a comment: a note for whoever is reading, which the machine throws away before it runs
anything.
Which way is up, and what a shift the other way does
Bits are written with the biggest one on the left, the same as decimal. So a left shift moves every bit towards the big end and the number doubles. The bit that runs off the left is gone, and a 0 arrives at the right to fill in.
A right shift is the mirror image. Every bit slides one place towards the small end, the bottom bit
falls off, and the number halves, rounding down when it was odd. x >> 1 turns 9 into
4.
x & 0b00001111 /* keep the bottom four bits, zero the rest */ x | 0b10000000 /* turn the top bit on, touch nothing else */ x ^ 0b11111111 /* flip every bit */ x << 3 /* slide up three places, same as x * 8 */
I have not seen 0b before
0b works the same way as 0x. It says read the rest as binary, one
character per bit, so 0b00001111 is a byte with the bottom four bits on and the top four
off.
That same byte could be written 0x0F in hex or 15 in decimal. Three
spellings, one pattern of switches. Binary is used here because it shows you exactly which bits the
operation is going to touch.
Below is a starting pattern and a target. Reach the target and the counter tells you how many operations it took. Most can be done in one. The last two fix the mask instead, so an all-purpose XOR shortcut is unavailable and you have to combine operations.
x & mask. The top row changes
to match the target row and the last badge turns to "solved". Then press "Next puzzle" for the
next one.A mask is a pattern of 1s marking the bits you care about. AND with it to read those bits and ignore the rest; OR with it to set them. The name comes from painting: you cover the parts you do not want touched and work freely over the rest. Almost every line of low-level code that looks cryptic is doing this and nothing more.
AND, OR and XOR on one bit at a time
Each operation takes one bit from each side and produces one bit. AND gives 1 only when both are 1. OR gives 1 when at least one is 1. XOR gives 1 when exactly one is 1, so it is the odd-one-out test.
The machine does that for all eight positions at once, and no position affects its neighbours. Work out a single column and you have worked out the whole byte.
0xAARRGGBB, where each letter pair marks a slot rather than being a real hex digit: AA is
where alpha's two hex digits go, RR is where red's go, and so on. You need green on its own, as a
number from 0 to 255. Which pair of steps gets it?Eight answers in one byte
Quite often what a program has to remember is exactly eight yes-or-no answers. Can this user read the file? Write it? Delete it? Eight separate variables cost eight bytes and eight trips to memory. Eight bits cost one byte and one trip.
Each answer gets a bit position, and each position gets a name whose value is that single bit: 1, 2, 4, 8, 16, 32, 64, 128. After that the operations from Step 2 do all the work. OR to grant, AND with the inverse to revoke, AND to test.
Why the values go 1, 2, 4, 8 and not 1, 2, 3, 4
Each name has to stand for one bit on its own, and a single bit is worth whatever its position is worth: the rightmost 1, then 2, 4, 8, 16, 32, 64, 128. Those are the only eight numbers with exactly one bit switched on.
Pick 3 instead and you have quietly chosen two bits, so granting it would set two permissions and testing it would ask about both at once. The doubling is what keeps each flag to itself.
#define READ 1 /* 0b00000001 */
#define WRITE 2 /* 0b00000010 */
#define ADMIN 64 /* 0b01000000 */
perms |= WRITE; /* grant */
perms &= ~WRITE; /* revoke */
if (perms & ADMIN) { ... } /* test */
What are #define and if doing in that listing?
#define READ 1 does not make a variable and does not use any memory. It tells the
compiler: everywhere the word READ appears in this file, put the number 1 there instead, before
anything else happens. It is a rename done in the text, so that the code can say READ where it means 1
and still make sense to somebody reading it a year later. Nothing of it survives into the running
program.
if (perms & ADMIN) { ... } runs whatever is inside the curly brackets, and only
then, when the answer in the round brackets comes out as anything other than zero. The
... is not real code; it stands in for whatever this program does for an administrator. So
the line reads: work out perms AND ADMIN, and if the result is not zero, do the admin part.
The ~ and the |= in those lines
~ flips every bit, so ~WRITE is a byte that is 1 everywhere except at the
WRITE position. AND against that keeps everything else and clears the one bit, which is exactly what
revoking has to do.
perms |= WRITE is shorthand for perms = perms | WRITE. The same shortening
works for &=, and for += if you have met that one.
perms |= EXEC;. Press it again
to watch the same line become the revoke.m be WRITE | ADMIN, the two of them
ORed into one mask. Then perms & m comes out non-zero when either one is
granted. (perms & m) == m is true only when both are. That double equals sign
is a question, not an instruction: one equals sign puts a value into something, two equals signs ask
whether two things are the same. The two lines look almost identical and they answer different
questions, and picking the wrong one is a security bug rather than a typo.chmod 755, the command that sets who is allowed to touch a
file on a Mac or a Linux machine, is nine of these flags written as three digits. When two computers talk
over the internet they send small parcels called packets, and the three answers start talking,
got it and I am finished are three single bits in one byte of every parcel. A processor
keeps its own answers the same way: was the last result zero, did it run off the end, each one bit in one
special byte inside the chip. Open a file in C and the second thing you hand it is a set of flags ORed
together. Once you can read one packed byte you can read all of them.
What the 755 in chmod is saying
755 is three digits in base eight: one for the owner, one for the group, one for everybody else. Each digit is three bits, worth 4 for read, 2 for write, 1 for execute. So 7 is 4 plus 2 plus 1, all three, and 5 is read and execute but not write.
Base eight is used because one octal digit is exactly three bits and permissions happen to come in threes. Nothing later needs this, so skip it if changing base is one thing too many today.
READ=1, WRITE=2,
EXEC=4. A permission byte arrives holding the number 6. The code says
if (perms & (READ|WRITE)) and treats a true result as "this user can read
and write". What does 6 actually allow, and does the check pass?if fires, and READ was never granted. A test for
"all of these" has to compare against the mask: (perms & m) == m. This is the difference
between "any" and "all" hiding inside one &, and it has let people into places they
should not have been.Where integers break
An integer variable is a fixed number of bits, and a fixed number of bits holds a fixed number of different values. Eight bits gives 256 of them. That is not a detail to be careful about later. It decides exactly what happens at the edge. It is worth predicting before you look.
Two words for what you are about to watch. A register is the slot inside the processor where the arithmetic actually happens, and it is exactly as wide as the variable, eight bits here. A carry is the extra 1 that a sum produces when a column fills up, the same 1 you write above the next column when adding by hand. The trouble is that there is no next column.
An 8-bit unsigned variable is holding 255, which is all eight bits on. You add 1. Commit to an answer, then run it.
How a byte holds a negative number
In signed mode the top bit reads as a minus sign, but the rest is not simply the size. The pattern that would be 255 unsigned is read as -1, 254 as -2, and so on downwards. The whole top half of the range folds over to the negative side, which is why a signed byte runs -128 to 127.
It is arranged that way so the adding circuit does not have to care which kind it is holding. Add 1 to the pattern for -1 and you land on the pattern for 0, using the same addition that works for positive numbers.
+1. Every bit in the row turns off at once and the value badge
reads 0. The narration under the buttons says in words what just happened.Older systems store the time as a count of seconds since 1970 in a 32-bit signed integer. That counter runs out on 19 January 2038, at which point the date becomes 1901, the same shape of bug as the year 2000, with a fixed deadline. Ariane 5's first flight was lost in 1996 to a 64-bit float converted into a 16-bit integer that could not hold it. Overflow does not look dramatic from the inside; it looks like a small number.
Why the deadline is 2038 and not some other year
A 32-bit signed integer stops at 2,147,483,647. That many seconds is a little over 68 years, and the count started at the beginning of 1970, so the last second it can hold falls in January 2038.
The fix is to count in 64 bits, which pushes the limit further out than anyone needs to plan for, and most systems have already moved. Nothing later in this course rests on the date arithmetic.
for (unsigned char i = 10; i >= 0; i--). How many times does the loop body run?i is 0 the body runs, then
i-- wraps it round to 255, and 255 >= 0 is true. It is true for every value
an unsigned char can hold, so the condition can never end the loop. The bug is not in the counting; it
is in asking an unsigned type a question that only makes sense for a signed one.Reading that for loop
The three parts between the semicolons are: start with i at 10, keep going while
i >= 0, and after each pass subtract 1 from i. unsigned char
is C's name for a one-byte number that is never allowed to be negative.
The condition is tested before every pass, including the first. A loop ends when that test finally comes out false, so a test that can never be false is a loop with no way out.
Why 0.1 plus 0.2 is not 0.3
Ask any language you like for 0.1 + 0.2 and you get
0.30000000000000004. This is not a bug in the language. All of them do it, and all of them are
performing the addition correctly.
A double has 64 bits: one for the sign, eleven for an exponent, fifty-two for the digits. It stores numbers the way scientific notation does: some digits, times two to some power. In base two, one tenth is a repeating fraction, exactly as one third is in base ten. Fifty-two bits is where the repeating stops.
What "times two to some power" means
Scientific notation writes a number as a few digits plus a scale, like 3.2 times 10 to the power 5 for 320,000. The digits carry the precision and the power of ten carries the size, and moving the power up or down slides the number without touching the digits.
A double does the same job in base two: some digits, times two to some power. The fifty-two bits hold the digits and the eleven exponent bits hold the power. That is how one 64-bit pattern can cover both tiny and enormous numbers.
I have not seen 2⁵³ or 2^-4 before
A small raised number means how many times to multiply, so 2⁵ is 2 x 2 x 2 x 2 x 2, which is 32, and
2⁵³ is 2 multiplied by itself fifty-three times. When a page cannot print the number small and raised,
the same thing is written with a hat: 2^53 means 2⁵³, and 5^3 means 5 x 5 x
5. The lab below uses the hat form because it is what code uses.
A minus in there flips it into a division. 2^-4 is 1 divided by 2⁴, which is one
sixteenth, or 0.0625. So the powers run 2^0 = 1, 2^1 = 2, 2^2 = 4 going up, and 2^-1 = a half, 2^-2 = a
quarter going down. That single ruler covers everything from the enormous to the almost nothing, which
is exactly what a double needs.
Why one tenth cannot be written exactly in base two
In base ten you can write out any fraction whose bottom number is built from 2s and 5s, because ten is 2 times 5. A third is not built that way, so 1/3 comes out as 0.333 going on forever.
Base two only has 2s to work with. A half, a quarter, an eighth and a sixteenth are exact. A tenth needs a 5 underneath, so in binary it repeats forever, and storing it means cutting the repeat off after fifty-two bits. What gets kept is very close to 0.1 and is not 0.1.
Take a number apart below and look at what was actually stored instead of what you typed.
How to read that bottom slider. It does not change the number you typed. It asks a separate question: if you were working with numbers roughly this big, how far apart would the storable ones be? Drag it hard left first, where numbers are tiny and the gaps are far smaller than anything you would ever notice. Then drag it slowly right. The label 2^0 means 1, 2^10 means about a thousand, 2^30 about a billion, 2^53 about nine thousand million million. Watch the gap grow, and stop the moment the gap passes 1. From there on, doubles cannot count whole numbers any more, and adding 1 to one lands you back where you started. That crossing point is the whole reason for this slider.
What is special about 2 to the 53rd
A double stores fifty-two digit bits, plus one leading bit that is always 1 and therefore never needs storing. That is fifty-three bits of precision. While a whole number fits in fifty-three bits, it has its own exact pattern and nothing is lost.
Past that point the gap between one representable value and the next grows to 2, then 4, then 8. Whole numbers start being skipped, and adding 1 lands you back where you started. Nothing later in the course depends on the figure.
Do not compare floats with ==; compare the size of the
difference against a small tolerance. And do not store money in a float. Count whole cents in an
integer and divide only when you print. Every currency rounding scandal you have read about started with
somebody assuming a decimal fraction was stored exactly.
0.10 to a running total ten times and then
checks total == 1.00. The check fails. Which fix would a professional reach for?A character is not a byte
For a long time text was simple: 128 characters, one byte each, and A
was 65. That was ASCII, and it was built for English on a teletype.
Why ASCII stopped at 128 when a byte holds 256
ASCII was settled in the early 1960s and used seven bits rather than eight, because the spare bit was wanted for checking that a character had survived the wire. Seven bits gives 128 slots, and 128 was more than enough for English.
That spare eighth bit is the reason UTF-8 could be bolted on later without breaking anything: every ASCII byte has a 0 on top, so a byte with a 1 on top was free to mean something new. Skip this if the history is not what you came for.
Then everybody else needed their alphabet, and 128 slots do not cover Sinhala and Chinese and Arabic and a picture of a coffee cup. Unicode gives every character a number, well past a hundred thousand of them. UTF-8 is the arrangement that stores those numbers as bytes: the original 128 stay one byte each, so old English text is already valid UTF-8, and everything else spreads into two, three or four bytes, marked so a reader can always tell where a character begins.
What a code point is, and how the marking works
A code point is the number Unicode handed to a character. The letter A is 65 and a hot drink is 9749.
The number says nothing about storage. UTF-8 is one particular way of turning it into bytes. Written
down, code points are given with U+ in front and the rest in hex, the base sixteen from
Step 1. So the letter A is U+41, which is the same 65, and the hot drink is
U+2615. Every Unicode chart in the world spells them that way, and so does the lab
below.
The marking lives in the top bits. A byte starting 0 is a whole one-byte character. A byte starting 110 announces two bytes, 1110 announces three, 11110 announces four, and every follow-on byte starts 10. So a byte starting 10 is always a middle and never a beginning, which is how a reader can find the start of a character from anywhere in the stream.
Type something below. Then cut it in half.
For the family emoji 👩👩👦: 18 bytes of UTF-8, 5 Unicode code
points, and 1 thing a reader would call a character. Ask a language for its length and you get whichever
of the three that language happens to count: bytes in Go, code units in JavaScript and Java, code points
in Python. None of them is wrong; they are answering different questions, and you have to know which one
you asked.
A code unit is not a code point
A code unit is the chunk a particular encoding works in. UTF-8 works in bytes, so its code unit is one byte. JavaScript and Java store text in 16-bit chunks, so theirs is two bytes. That arrangement has a name of its own, UTF-8's sixteen-bit cousin: UTF-16. It is the second badge above the boxes in the lab.
Characters past a certain point need two of those 16-bit chunks, which is why one emoji can report a length of 2 in JavaScript while Python, counting code points, says 1. Both counted correctly. They counted different things.
A pointer is a number
Every byte in memory has a number: its address. That is all an address is: which slot. So a variable holding an address is a variable holding an ordinary number, and the only thing that makes it a pointer is what the surrounding code intends to do with it.
Two operations, and no others. &x means "the address of x".
*p means "go to the address in p and use whatever is sitting there". Mixing those two up is
most of what makes pointers feel hard, and both of them are visible in the strip below.
The star means two different things
In int *p the star belongs to the type. It says p is a pointer to an int, and nothing is
being read. In *p partway through a statement the star is an instruction: go to the address
in p and use whatever is there.
Same character, two jobs, sorted out by where it sits. Declarations describe; statements act. Reading the line aloud in words rather than symbols settles most of the confusion.
Point p somewhere, then read through it.
read *p, then press
p = p + 1 and read again. Each row of the strip is four bytes of memory: on the left
their address in hex, in the middle the number stored in them, on the right the name your program uses
for them if it has one. The rows with a dashed edge belong to other parts of the program and are none
of your business; click one of those rows to aim p at it anyway. p is itself one of the
rows, because a pointer is an ordinary variable holding an ordinary number.p = NULL button, and read. Then point it past
the end of the strip and read that. On a real machine one of those crashes immediately and the other
quietly hands you a number, and which you get depends on what the operating system happens to have
mapped rather than on anything in your program.What "nothing" means for a pointer
A pointer has to hold some number, so C picks address 0 to mean this one is not aimed at anything
yet. It is written NULL, and it is the standard way of saying do not follow me.
Address 0 is deliberately left unusable by the operating system, the program that starts your program and decides which addresses it is allowed to touch. So following a null pointer stops the program instead of quietly reading somebody else's data. A crash you can find beats a wrong answer you cannot.
It carries an address and a claim about the type living there. Nothing checks
the claim. Cast a pointer to a different type and the same bytes will be read the new way without
complaint. That is Step 1 arriving with consequences. It is why void * exists, a pointer
carrying an address and no claim at all about what type lives there. It is why casting pointers is
treated as a serious act in every code review. And it is why a wrong cast produces confident nonsense
instead of an error.
What casting a pointer is
A cast is you telling the compiler to treat a value as a different type. For a pointer it moves nothing and changes no byte. It changes only the claim about what type lives at that address, and therefore how many bytes a read takes and how they get put together.
That is why writing one is treated as a serious act. The compiler stops checking and starts believing you, and the same bytes come back as a different number with no complaint from anywhere.
int *p points at a 4-byte int. How
much memory does p itself take up?Off the end of the array
An array is a row of items of the same kind, kept one after another and
reached by number rather than by name: a[0] is the first, a[1] the second, and an
array of six ends at a[5]. Underneath, it is the address of its first item plus a promise that
the rest follow immediately. So a[3] is arithmetic: start, plus 3 times the size of one item.
The compiler turns a[i] into *(a + i) and the two spellings mean the same thing
so exactly that 3[a] also compiles and works.
Why is the first item a[0] and not a[1]?
The number in the brackets is not a position in a queue. It is a distance from the start.
a[0] means the item no distance at all from the beginning, which is the first one.
a[3] means three items along from the beginning. Read as a distance, the numbering stops
being strange, and the arithmetic in the lab below is exactly that distance times the size of one
item.
It also sets the trap this whole step is about. An array of six items has distances 0, 1, 2, 3, 4
and 5, so the last one is a[5], and a[6] is already outside the array while
looking completely reasonable on the page. Writing 6 where 5 was meant is the most common mistake in
this subject, and it is the one you are about to make on purpose.
Why a + 3 does not mean the address plus 3
Pointer arithmetic counts items, not bytes. If a points at 4-byte ints then
a + 3 is the address of a plus 12, because the compiler multiplies by the size
of one item on your behalf.
That is why the type of a pointer matters even though the address is only a number. Change
int * to char * and the same + 3 moves three bytes instead of
twelve.
Why 3[a] really compiles
a[i] is defined as shorthand for *(a + i), and ordinary addition does not
care which side each number sits on. So *(3 + a) means the same thing, and
3[a] is its shorthand.
Nobody designed that in and nobody writes it on purpose. It falls out of the definition, and it is worth a look only because it shows how thin the array notation really is. Nothing later needs it.
Which raises a question C does not answer. What happens when i is 9 and
the array holds 6? The arithmetic still works fine. It produces an address, and there is something at that
address, because there is something at every address.
So read past the end and find out what is parked next door.
i = 5 and then
read a[i]. That is the last real item, and the narration says so. Now press
i = 6 and read again: the address arithmetic works exactly as before and hands you a
number that was never part of the array.a[6] and watch the loop
counter change value. Nothing errored. The array did not object, because there is nothing there to
object with. No length is stored anywhere and no check is generated. That single absence is behind a
large share of the security holes in the world.Python and Java check every index and raise an exception, which is a controlled stop that the program is given a chance to catch and deal with. Rust checks too, and lets you opt out in writing. C checks nothing, because a check costs an instruction and C was designed when that mattered enormously. The trade is real and it is still argued about, but note what you are buying: one comparison per access, in exchange for the entire category of bug you just caused.
buf[i] where buf holds
8 bytes and i is 12. According to the language, what happens?What "undefined behaviour" means
The C standard is a written agreement about what code has to do. For certain mistakes it deliberately says nothing at all, and those cases are called undefined behaviour. The program is then allowed to do anything: hand back a neighbour's value, stop dead, or look fine.
The awkward part is what compilers do with that silence. Optimisation is the compiler's own work to make the finished program faster, mostly by throwing away anything it can prove is not needed. Since the standard promises this case never arises, a compiler may optimise on the assumption that it never arises, and remove a check you wrote. So the outcome can change the moment you turn optimisation on.
The stack: frames that vanish
When a function starts, its local variables need somewhere to live. When it returns, they do not. Last one in is the first one out, which is a stack exactly, and the machine keeps one permanently for the job.
What a function is, and what calling one means
A function, from the four words in Step 0, is a named piece of a program you can go off and run from
anywhere, so that it does not have to be written out again. It usually takes a value or two in and
hands one back. The line
int inner(int m) reads: here is a function called inner; hand it one whole number, which
it will call m while it works; it will hand back a whole number when it is done. A variable declared
inside it, like int s, is called a local. It belongs to that one run of that one
function, and no other part of the program can see it or reach it.
Calling a function means stopping what you were doing, going off to run it, and coming back to the
exact spot you left. Returning is the coming back, and return s carries a value home with
it. That leaving and coming back is the whole subject of this step. The machine has to write down
where home was. It has to find somewhere to keep the locals while the function runs, and it has to
take that somewhere back afterwards.
Why it is called a stack
Think of a pile of plates. You add to the top and you take from the top, so the plate you put down last is the one you pick up first. Nothing is ever pulled out of the middle.
Function calls have exactly that shape. If main calls outer and outer calls inner, inner has to finish before outer can, and outer before main. The last call started is always the first to end.
A call pushes a frame: room for that call's locals, plus the address to come back to. A return pops it. Both cost one addition to a register, which is why locals are the cheapest memory there is and why you never free them.
A register, and the address to come back to
The register from Step 4, the slot inside the processor where the arithmetic happens, is also far quicker to reach than memory, and a processor has a handful of them. One of that handful, the stack pointer, holds the address where the used part of the stack currently ends. Moving that one number is how a frame gets claimed or dropped.
The address to come back to is called the return address. A call writes down the spot in the calling function it should resume at, then jumps away. A return reads that address back and jumps to it.
Step through three nested calls and watch the frames appear.
main is where a C program starts; it puts 3 in x and calls
outer with it. outer doubles whatever it is given and passes the result to
inner. inner adds 1 and hands it back. So 3 becomes 6 becomes 7. The last line
prints it: printf is the standard way of printing in C, the %d inside its
text means put a number here, and \n means start a new line. Press "Step ▶" and watch
two things at once, the highlighted line on the left and the tower on the right growing a box for
every call and losing one for every return.Then switch to the recursion mode and push the depth up. The frames pile downward until they run into the limit, and the program dies with the error whose picture this is. There is no allocation failure to check and nothing to catch. The stack is a fixed-size region, decided before your program started running.
What recursion is
A recursive function is one that calls itself, usually on a slightly smaller version of the same problem, until it reaches a case simple enough to answer outright. Counting down to zero is the plainest example there is.
Each of those calls needs its own frame, because each has its own copy of the locals. So a recursion a hundred thousand deep asks for a hundred thousand frames at the same time, and that is what runs the stack out.
A frame's lifetime is exactly the call. Anything that has to outlive the call cannot live there, and a pointer to a local, returned to the caller, aims at bytes the very next call will write over. Step to the moment inner returns and watch its frame go dead: the numbers are still sitting in those bytes, and nobody owns them any more. Step 10 is about the other place things can live.
int big[1000000]; as a local
variable, and the program dies before the first statement of that function runs. Why?The heap, and the holes in it
Some things have to outlive the call that made them. A function that reads a file cannot put the contents in a local, because the caller wants them after the function is gone. So there is a second region with no automatic ending: you ask for a block, you get an address, and it stays yours until you say otherwise.
The two words for this: malloc and free
In C the request is malloc(n), which asks for n bytes and hands back the address of a
block that size, or nothing at all if it cannot be done. free(p) gives that block back.
Other languages spell it differently: new in C++ and Java, and in Python the request
happens without you writing anything. The two jobs, hand out and take back, sit underneath all of them.
That freedom is the whole problem. A stack only ever frees the top, so it never leaves gaps behind. A heap frees whatever you name, in whatever order you name it, so gaps are guaranteed, and a gap is only useful to a request small enough to fit inside it.
Fragmentation, on a bookshelf
Picture a full shelf. Take out five thin books from five places along it and you have five gaps and plenty of free shelf in total. Now try to fit one thick book. It goes nowhere, even though the space exists.
The heap has that problem, and it cannot slide the remaining blocks along to close the gaps, because programs are holding the addresses of those blocks and every one of them would become wrong.
Allocate and free below. Then press the button that fragments it on purpose.
The stack is fast, automatic, small, and rigid about order. The heap is
slower, manual, large, and free about order. A local costs one register addition; a malloc
costs a search through bookkeeping. Prefer the stack whenever the lifetime allows, and the whole reason
the heap exists is the cases where it does not.
Where the heap gets its memory from
The allocator is ordinary code inside your program rather than part of the hardware. When its own supply runs low it asks the operating system for a larger region, in big chunks, and then hands out small pieces of that region itself.
That is why a single malloc is usually quick: most calls never reach the operating
system at all. Only the occasional one that needs fresh territory does.
Write the allocator
You now know enough to write malloc, so write it. An allocator keeps a
list of the free pieces. A request walks that list, picks a piece big enough, cuts off what it needs and
leaves the remainder free. A free puts a piece back, and if the pieces either side of it are also free,
welds all three into one.
Search, split, return, coalesce. That is the design. Every block also carries a
small header, because free(p) is handed nothing but an address and still has to know how big
the block was.
What a linked list is
A linked list is a chain. Each piece holds some data plus the address of the next piece, and the last one leaves that slot empty to show the chain has ended. To find something you start at the front and follow the addresses one at a time.
The allocator uses one because pieces appear and disappear all over the heap. Adding or removing a link is a matter of writing one address, with nothing to shuffle along.
typedef struct block {
size_t size; /* the header: how many units this block spans */
int free;
struct block *next; /* the free list is a linked list */
} block;
void *my_malloc(size_t want) {
for (block *b = head; b; b = b->next) /* search */
if (b->free && b->size >= want) {
split(b, want); /* split */
b->free = 0;
return (void *)(b + 1); /* skip the header */
}
return NULL; /* out of room */
}
Reading that C: struct, size_t and the arrow
A struct is a few named fields kept side by side under one name, so a block
here is a size, a free flag and a next address in one lump. size_t is the type C uses for
sizes and counts, and it is never negative.
b->next means follow the pointer b and take the field called next. It is the same as
(*b).next, only easier on the eyes. And b + 1 on a block pointer steps over
exactly one whole header, which is how the caller ends up with the first byte after it.
Reading my_malloc one line at a time
The first lump sets up the shape of a block and gives that shape the short name
block, which is what typedef does: it invents a name for a type so the rest
of the code can be shorter. Inside the shape, size is how many units this block spans,
free is a yes-or-no answer kept as 1 or 0, and next holds the address of
another block, which is what strings them into a chain.
The loop line says: start with b at the front of the chain, and each time round move b along to the
next link. The middle part, the lone b, is the test for carrying on, and in C anything
that is not zero counts as yes. The last link's next is 0, so that single letter means "while we have
not fallen off the end". && means and, so
b->free && b->size >= want reads: this block is free, and it is at least
as big as the request. NULL at the bottom is the address 0 from Step 7, meaning nothing
was found. At the end, (void *)(b + 1) hands back the address just past the header, with
no claim about what type lives there, because the caller asked for space rather than for the label on
it.
Below, you are the allocator. Requests arrive one at a time and you choose which free piece serves each one. Turn coalescing off first, and watch what your free list becomes.
Coalescing, with numbers
Say the heap runs from 0 to 20, and the pieces covering 0 to 4 and 4 to 9 are both free. Without coalescing the list holds a 4 and a 5 and a request for 7 fails. With it, they were welded together the moment the second one was freed, the list holds a 9 and the request is served.
The test is about neighbours in the heap, not neighbours in the list. Two pieces can sit next to each other in the free list and be nowhere near each other in memory.
Separate free lists per size class, so the search is short. A header at both ends of a block, so a free can find its left-hand neighbour without walking. One separate pool per thread, a thread being a second line of execution running inside the same program, so that two of them do not fight over one list. Requests over a few hundred kilobytes handed straight to the operating system and given back on free. Every one of those is a refinement of the four verbs you just performed by hand.
free would most likely have avoided
it?Four bugs this makes possible
Manual memory has two rules. Free everything you allocate, once. Never touch a block after freeing it. Both are easy to state and hard to obey across a hundred thousand lines written by forty people, and each way of breaking them has a name and a well-known shape.
The names for the four ways it goes wrong
A leak is memory you allocate and never free, so it stays claimed until the program ends. A double free is freeing the same block twice, which damages the allocator's own bookkeeping rather than your data.
A use after free is reading or writing a block you already handed back. The fourth is the same mistake made on the stack rather than the heap: keeping the address of a local variable after the function it lived in has returned, so those bytes are handed to whoever is called next. Those four are the tabs below. There is a fifth worth knowing by name, an overflow, which is writing past the end of the block you were given and into whatever the allocator parked next door. That one you have already caused, to an array, in Step 8.
All four are below as scripted scenarios in the model heap from the last two steps. Cause each one deliberately, in order, and watch what the model does wrong.
Sanitizers keep a shadow record of which bytes are live and stop the program at the first bad access. Garbage-collected languages free nothing by hand and pay for it in pauses and memory. Rust tracks who owns each block at compile time and refuses to build code that could do any of these four. None of them makes the mechanism disappear. They each add a bookkeeper, and they each charge for it.
What a garbage-collected language does instead
In Java, Python, Go and JavaScript you never call free. Part of the runtime, the collector, works out which blocks can still be reached by following every pointer the program holds, and reclaims everything else.
Nothing reachable is taken away and nothing unreachable survives, so three of these four bugs cannot happen. The price is the collector's own work: it takes time, it needs spare memory to operate in, and it usually pauses your program while it runs.
How a sanitizer catches the read that worked
A sanitizer keeps a second, hidden map with an entry for every few bytes of your memory, saying whether those bytes are currently allowed to be touched. Freeing a block marks its bytes off limits and holds them out of circulation for a while, so the next read of them is caught instead of quietly served.
Every memory access in the program gets a check against that map added to it, which is why the program runs several times slower and why this is a testing tool rather than something left switched on.
Why field order changes the size
The hardware has opinions about addresses. A 4-byte integer is fetched fastest when its address is a multiple of 4, and on some processors reading it anywhere else is not slow but forbidden. So the compiler will not put your fields wherever they happen to land.
What a structure is
A structure, struct in C, is a group of named fields stored side by side and handled as
one value. A field can be a number, a character, a pointer, or another structure.
The point of this step is that side by side does not mean touching. The compiler decides where inside the lump each field sits, and it will leave gaps wherever the hardware wants them.
It inserts padding: unused bytes whose only job is to push the next field onto an
address the hardware likes. Then it pads the end of the whole structure too, so that an array of them keeps
every copy aligned. None of this is in your source code and all of it is in the size. Two words the lab
uses for it. An offset is how far a field sits from the start of the structure, counted in bytes, so
the first field is always at offset 0 and a field at offset 12 begins twelve bytes in. And
sizeof is how you ask C how big something really is: sizeof(struct record) hands back
the total in bytes, padding included, which is the number in the first badge and the only number worth
trusting.
Why the hardware wants a multiple of 4
Memory is not fetched one byte at a time. It arrives in fixed-size chunks with fixed starting points. A 4-byte number that begins at a multiple of 4 sits inside one chunk and comes back in one fetch.
Let it start at address 6 instead and it straddles two chunks. Now the processor needs two fetches and has to stitch the halves together, and some processors refuse outright rather than do it.
Reorder the fields and watch the number change.
What "fitting in cache" means
The cache is a small, fast copy of recently used memory that sits right next to the processor. A read served from cache is many times quicker than one that has to travel out to main memory.
It only holds a few megabytes, so the smaller each record is, the more of them fit and the more often the answer is already close by. That is why taking a third off the size of a record can matter more than the code that walks through them.
Order fields from largest to smallest when a structure is stored in bulk.
Never work out a size by adding up the fields. Ask for sizeof, because your arithmetic will
be wrong. Never write a structure to a file by copying its raw bytes, and never send it down a socket
that way either, a socket being a program's end of a connection to another machine. The padding is not
specified, so the machine at the other end may pad differently. And #pragma pack, an instruction to the compiler rather than a
piece of the program, does remove the padding, at the price of slower reads and, on some processors, a
crash.
char, a
double, and another char. A double must sit at a multiple of 8. What does
sizeof report?Where to go next
- Data Structures: you have the row of numbered boxes and you know what a pointer is, which is everything needed to build linked lists, hash tables and trees on top of them.
- How a Program Runs: the compiler, the linker, and what an executable actually contains before the operating system hands it a stack and a heap.
- Performance Engineering: caches, cache lines, and why the field order you just played with can matter more than the algorithm.
You started with eight switches. Numbers, letters, colours, addresses, frames, free lists and a working allocator all turned out to be arrangements of those switches plus an agreement about how to read them. Nobody handed those agreements down. People worked them out, wrote them down, and argued about the details, which is the part you have now done too.
A pointer needs an object, bounds and a live lifetime
An address-shaped number is not the whole meaning of a pointer. A valid pointer is tied to a particular allocated object, may point within that object or one position past its end, and may be used only while the object is alive. The one-past pointer is useful for loop comparisons but must not be dereferenced.
Two pointers alias when they can name overlapping storage. The compiler must preserve permitted
aliasing, but C also has effective-type and restrict rules that let it assume some pointers do
not overlap. Breaking those rules is undefined behaviour, even when the bytes appear to contain the expected value.
free. Lifetime, not appearance, decides whether the access is valid.Why memcpy is the safe byte bridge
memcpy copies object representations through character bytes without asking the compiler to treat one typed object as an unrelated type. Use it for bit inspection, and decode external formats field by field.
Virtual addresses are translated a page at a time
A process normally uses virtual addresses. The memory-management unit splits an address into a virtual page number and an offset, then uses page tables to find a physical frame with the same offset. A TLB caches recent translations.
If no valid mapping exists, the processor raises a page fault. The operating system may load a permitted page, grow a mapped region, copy a shared page before writing, or terminate the process. A fault is an event; whether it is recoverable depends on the mapping and access rights.
Protection comes with translation
Page-table entries can allow read, write and execute independently and can distinguish user from kernel access. ASLR changes placements; guard pages leave mappings deliberately absent. Neither replaces bounds-safe code.
Caches move lines, so access order changes speed
Processors fetch memory in cache lines rather than isolated bytes. Sequential access reuses nearby bytes; jumping among distant addresses spends more time waiting and may evict useful lines. Spatial and temporal locality describe those two kinds of reuse.
Two threads can also slow each other without sharing a logical variable. If their separate counters occupy the same cache line, each write transfers ownership of the line between cores. This false sharing is a performance problem, not proof of a data race.
Measure before changing layout
Use representative inputs and hardware counters where available. Continue with Performance Engineering for cache hierarchies, rooflines, profiling and statistically sound timing.
Threads need ordering as well as indivisible updates
A data race occurs when threads access the same memory concurrently, at least one access writes, and the language supplies no ordering between them. In C and C++, a data race is undefined behaviour. An atomic read-modify-write prevents a torn or lost update, but it does not automatically publish every neighbouring field correctly.
Mutexes provide mutual exclusion and ordering. Atomics use memory orders such as relaxed or acquire/release; those names describe which earlier writes another thread is guaranteed to observe. Start with locks and documented invariants before reaching for a weaker order.
Volatile is not a thread lock
volatile is used for observable accesses such as device registers and signal-related cases defined by the language. It does not make a compound update atomic or establish cross-thread ordering.
Find the first invalid access, not the final crash
Memory corruption often crashes later than the bad write. Reproduce with the smallest input, preserve the first diagnostic and classify the failure: bounds, lifetime, initialisation, alignment, race or ownership. Add assertions around the contract instead of guessing from the last damaged value.
AddressSanitizer targets bounds and use-after-free; UndefinedBehaviorSanitizer checks selected undefined operations; MemorySanitizer finds uninitialised reads on supported platforms; ThreadSanitizer looks for races. Valgrind-style dynamic tools provide another route. Each tool has coverage limits, overhead and false-negative cases.
Prevention changes the default
Ownership APIs, slices with lengths, RAII, garbage collection and Rust borrowing prevent different bug classes. Foreign-function and unsafe boundaries still need explicit lifetime, layout and thread-safety contracts. Continue with Memory Exploits for attacker-controlled consequences.