Two Programs Can Hold the Same Address and Never Collide

Start two copies of the same program and have each print the address of a

variable. On a machine with the hardening features turned off, they print the

same number. Both programs then write different values through that address,

and neither one sees the other's write.

That is not a trick and nothing was faked. The number is real, the write went

through, and the two writes landed in different places in the memory chips.

The resolution is that the number in your pointer was never a location. It is

an index into a map, the map belongs to the process, and each process has its

own. When the processor executes your load, it consults the map belonging to

whichever process is currently running, finds the hardware location, and reads

that. Change which process is running and the same number resolves somewhere

else.

Notice what the marked rows make possible. Forty processes running the same

library hold forty maps, all of which name one copy of the code in hardware.

Nothing was copied, nothing is kept in sync, and the saving is not a clever

optimisation layered on top. It is what a map does.

The obvious way to build this map is a table with one entry per address. Count

the cost before dismissing it. A 64-bit machine has more addresses than there

are atoms worth caring about, and even a program using four gigabytes would

need four billion entries, each of them large enough to hold a hardware

location. The map would be many times the size of the memory it describes, and

every process would need one.

So the map does not work per byte. It works in fixed-size blocks, four

kilobytes on most machines. An address splits into two parts: the high bits

name a block and are looked up, and the low bits are an offset inside that

block and pass through translation untouched.

Two consequences follow immediately and both matter later. The map now needs

one entry per four thousand bytes rather than per byte, which is four thousand

times smaller. And translation happens once per block rather than once per

byte, so two addresses in the same block cost one lookup between them.

The second point is worth sitting with. Walking through a block of memory in

order does one translation and then three thousand and ninety-five free

accesses. Walking through memory in steps of four thousand and ninety-six does

a translation every single time. Same number of bytes read, wildly different

cost, and the whole difference is the map.

Even with blocks, a single flat table is too large for a 64-bit address space.

So the map is a tree. Each level is itself a block of memory holding entries,

each entry pointing at the next level down, and the address is cut into pieces

that index one level each.

Read the lower path again. Your program issued one load. The hardware performed

four memory reads to find out where to do the fifth. If that were the normal

case, every program would run at a fifth of its speed, and the entire scheme

would never have been built. It is not the normal case, for a reason that is

the subject of the next lesson.

It is tempting to read all this as a tax, something clever people would have

removed if they could. The opposite is true. Four features that nobody would

give up are the same mechanism viewed from different angles.

Isolation comes first. A process cannot name memory that is not in its map, so

it cannot read another process's data even by accident, even with a wild

pointer, even deliberately. This is not checked by software on each access. It

is enforced by the fact that the address has no meaning outside the map.

Sharing is the marked rows in the first figure. One copy of a library in

hardware, named by every map that wants it. The same mechanism lets two

processes agree to share a region on purpose, which is the cheapest way for

them to communicate.

A heap that grows is the third. When a program asks for more memory, no memory

has to move and nothing has to be contiguous in hardware. Entries are added to

the map, pointing at whatever blocks happen to be free. The program sees one

continuous region; the hardware holds it scattered.

And files you read by dereferencing a pointer are the fourth. Map a file into

your address space and the entries initially point nowhere at all; touching

them causes the system to fetch the data. The file is read by the act of

reading memory, with no request made and no buffer copied. That is a strange

thing to be able to do, and it falls out of the map being an editable object

rather than a fixed property of the machine.

The cost of all four is one translation per block, which is nearly free when a

small cache is doing its job and expensive when it is not. What that cache

costs, how big it is, and what happens to your program when your working set

outgrows it, is where this course goes next.