Computer hardware

IMEC (1984-, Belgium)

imec: The Semiconductor Watering Hole by Asianometry (2022)

Source. A key thing they do is have a small prototype fab that brings in-development equipment from different vendors together to make sure the are working well together. Cool.

As mentioned at youtu.be/16BzIG0lrEs?t=397 from Video "Applied Materials by Asianometry (2021)", originally the companies fabs would make their own equipment. But eventually things got so complicated that it became worth it for separate companies to focus on equipment, which then then sell to the fabs.

ASML Holding (1984-)

As of 2020 leading makers of the most important fab photolithography equipment.

ASML: TSMC's Critical Supplier by Asianometry (2021)

Source.

Video 2.

How ASML Won Lithography by Asianometry (2021)

Source.

First there were dominant Elmer and Geophysics Corporation of America dominating the market.

Then a Japanese government project managed to make Nikon and Canon Inc. catch up, and in 1989, when Ciro Santilli was born, they had 70% of the market.

youtu.be/SB8qIO6Ti_M?t=240 In 1995, ASML had reached 25% market share. Then it managed the folloging faster than the others:

TwinScan, reached 50% market share in 2002
Immersion litography
EUV. There was a big split between EUV vs particle beams, and ASML bet on EUV and EUV won.
youtu.be/SB8qIO6Ti_M?t=459 they have an insane number of software engineers working on software for the machine, which is insanely complex. They are big on UML.
youtu.be/SB8qIO6Ti_M?t=634 they use ZEISS optics, don't develop their own. More precisely, the majority owned subsidiary Carl Zeiss SMT.
youtu.be/SB8qIO6Ti_M?t=703 IMEC collaborations worked well. Notably the ASML/Philips/ZEISS trinity

www.youtube.com/watch?v=XLNsYecX_2Q ASML: Chip making goes vacuum with EUV (2009) Self promotional video, some good shots of their buildings.

ASM International (1964)

Parent/predecessor of ASML.

Applied Materials (1967-)

Applied Materials by Asianometry (2021)

Source. They are chemical vapor deposition fanatics basically.

Power, performance and area (PPA)

en.wikichip.org/wiki/power-performance-area

This is the mantra of the semiconductor industry:

power and area are the main limiting factors of chips, i.e., your budget:
- chip area is ultra expensive because there are sporadic errors in the fabrication process, and each error in any part of the chip can potentially break the entire chip. Although there are
  The percentage of working chips is called the yield.
  In some cases however, e.g. if the error only affects single CPU of a multi-core CPU, then they actually deactivate the broken CPU after testing, and sell the worse CPU cheaper with a clear branding of that: this is called binning www.tomshardware.com/uk/reviews/glossary-binning-definition,5892.html
- power is a major semiconductor limit as of 2010's and onwards. If everything turns on at once, the chip would burn. Designs have to account for that.
performance is the goal.
Conceptually, this is basically a set of algorithms that you want your hardware to solve, each one with a respective weight of importance.
Serial performance is fundamentally limited by the longest path that electrons have to travel in a given clock cycle.
The way to work around it is to create pipelines, splitting up single operations into multiple smaller operations, and storing intermediate results in memories.

Wafer (electronics)

Czochralski method

Semiconductor fabrication plant (foundry, Fab)

They put a lot of expensive equipment together, much of it made by other companies, and they make the entire chip for companies ordering them.

Company with a semiconductor fabrication plant

A list of fabs can be seen at: en.wikipedia.org/wiki/List_of_semiconductor_fabrication_plants and basically summarizes all the companies that have fabs.

Fairchild Semiconductor

Some nice insights at: Robert Noyce: The Man Behind the Microchip by Leslie Berlin (2006).

GlobalFoundries (2009, AMD spinout)

AMD just gave up this risky part of the business amidst the fabless boom. Sound like a wise move. They then fell more and more away from the state of the art, and moved into more niche areas.

Infineon Technologies (1999)

SMIC (Chinese TSMC)

SMIC, Explained by Asianometry (2021)

Source.

TSMC

One of the companies that has fabs, which buys machines from companies such as ASML and puts them together in so called "silicon fabs" to make the chips

As the quintessential fabless fab, there is on thing TSMC can never ever do: sell their own design! It must forever remain a fab-only company, that will never compete with its customers. This is highlighted e.g. at youtu.be/TRZqE6H-dww?t=936 from Video "How Nvidia Won Graphics Cards by Asianometry (2021)".

How Taiwan Created TSMC by Asianometry (2020)

Source. Some points:

UCM failed because it focused too much on the internal market, and was shielded from external competition, so it didn't become world leading
one of TSMC's great advances was the fabless business model approach.
they managed to do large technology transfers from the West to kickstart things off
one of their main victories was investing early in CMOS, before it became huge, and winning that market

Semiconductor fabrication step

Chemical vapor deposition

Photolithography

Extreme ultraviolet lithography (EUV)

Photomask

Standard cell library

Basically what register transfer level compiles to in order to achieve a real chip implementation.

After this is done, the final step is place and route.

They can be designed by third parties besides the semiconductor fabrication plants. E.g. Arm Ltd. markets its Artisan Standard Cell Libraries as mentioned e.g. at: web.archive.org/web/20211007050341/https://developer.arm.com/ip-products/physical-ip/logic This came from a 2004 acquisition: www.eetimes.com/arm-to-acquire-artisan-components-for-913-million/, obviously.

The standard cell library is typically composed of a bunch of versions of somewhat simple gates, e.g.:

AND with 2 inputs
AND with 3 inputs
AND with 4 inputs
OR with 2 inputs
OR with 3 inputs

and so on.

Each of those gates has to be designed by hand as a 3D structure that can be produced in a given fab.

Simulations are then carried out, and the electric properties of those structures are characterized in a standard way as a bunch of tables of numbers that specify things like:

how long it takes for electrons to pass through
how much heat it produces

Those are then used in power, performance and area estimates.

Open source standard cell library

Open source ones:

www.quora.com/Are-there-good-open-source-standard-cell-libraries-to-learn-IC-synthesis-with-EDA-tools/answer/Ciro-Santilli Are there good open source standard cell libraries to learn IC synthesis with EDA tools?

Electronic design automation (EDA)

A set of software programs that compile high level register transfer level languages such as Verilog into something that a fab can actually produce. One is reminded of a compiler toolchain but on a lower level.

The most important steps of that include:

logic synthesis: mapping the Verilog to a standard cell library
place and route: mapping the synthesis output into the 2D surface of the chip

Electronic design automation phase

Logic synthesis

Step of electronic design automation that maps the register transfer level input (e.g. Verilog) to a standard cell library.

The output of this step is another Verilog file, but one that exclusively uses interlinked cell library components.

Place and route

Given a bunch of interlinked standard cell library elements from the logic synthesis step, actually decide where exactly they are going to go on 2D (stacked 2D) integrated circuit surface.

Sample output format of place and route would be GDSII.

Integrated circuit layout

GDSII

EDA company

The main ones as of 2020 are:

Mentor Graphics, which was bought by Siemens in 2017
Cadence Design Systems
Synopsys

Cadence Design Systems

Mentor Graphics

Synopsys

Open source EDA tool

qflow

Cool looking open source EDA toolchain:

They apparently even produced a real working small RISC-V chip with the flow, not bad.

Semiconductor process node

Semiconductor device fabrication bibilography

Asianometry

www.youtube.com/channel/UC1LpsuAUaKoMzzJSEt5WImw

Very good channel to learn some basics of semiconductor device fabrication!

Focuses mostly on the semiconductor industry.

youtu.be/aL_kzMlqgt4?t=661 from Video "SMIC, Explained by Asianometry (2021)" from mentions he is of Chinese ascent, ancestors from Ningbo. Earlier in the same video he mentions he worked on some startups. He doesn't appear to speak perfect Mandarin Chinese anymore though based on pronounciation of Chinese names.

asianometry.substack.com/ gives an abbreviated name "Jon Y".

Reflecting on Asianometry in 2022 by Asianometry (2022)

Source. Mentions his insane work schedule: 4 hours research in the morning, then day job, then editing and uploading until midnight. Appears to be based in Taipei. Two videos a week. So even at the current 400k subs, he still can't make a living.

Integrated circuit (IC)

It is quite amazing to read through books such as The Supermen: The Story of Seymour Cray by Charles J. Murray (1997), as it makes you notice that earlier CPUs (all before the 70's) were not made with integrated circuits, but rather smaller pieces glued up on PCBs! E.g. the arithmetic logic unit was actually a discrete component at one point.

The reason for this can also be understood quite clearly by reading books such as Robert Noyce: The Man Behind the Microchip by Leslie Berlin (2006). The first integrated circuits were just too small for this. It was initially unimaginable that a CPU would fit in a single chip! Even just having a very small number of components on a chip was already revolutionary and enough to kick-start the industry. Just imagine how much money any level of integration saved in those early days for production, e.g. as opposed to manually soldering point-to-point constructions. Also the reliability, size an weight gains were amazing. In particular for military and spacial applications originally.

A briefing on semiconductors by Fairchild Semiconductor (1967)

Source.

Uploaded by the Computer History Museum. There is value in tutorials written by early pioneers of the field, this is pure gold.

Shows:

photomasks
silicon ingots and wafer processing

Interconnect (integrated_circuits, Chip interconnect)

Application-specific integrated circuit (ASIC, Hardware acceleration)

System on a chip (SoC)

Register transfer level (RTL)

The only two truly relevant RTL languages as of 2020 are: Verilog and VHDL. Everything else compiles to those, because that's all that EDA vendors support.

Much like a C compiler abstracts away the CPU assembly to:

increase portability across ISAs
do optimizations that programmers can't feasibly do without going crazy

Compilers for RTL languages such as Verilog and VHDL abstract away the details of the specific semiconductor technology used for those exact same reasons.

The compilers essentially compile the RTL languages into a standard cell library.

Examples of companies that work at this level include:

Intel. Intel also has semiconductor fabrication plants however.
Arm which does not have fabs, and is therefore called a "fabless" company.

High-level synthesis

Fabless manufacturing

In the past, most computer designers would have their own fabs.

But once designs started getting very complicated, it started to make sense to separate concerns between designers and fabs.

What this means is that design companies would primarily write register transfer level, then use electronic design automation tools to get a final manufacturable chip, and then send that to the fab.

It is in this point of time that TSMC came along, and benefied and helped establish this trend.

The term "Fabless" could in theory refer to other areas of industry besides the semiconductor industry, but it is mostly used in that context.

Fabless semiconductor company

Logic gate

Truth table

Verilog

Examples under verilog, more details at Verilator.

Value change dump (VCD)

Verilator

Verilog simulator that transpiles to C++.

One very good thing about this is that it makes it easy to create test cases directly in C++. You just supply inputs and clock the simulation directly in a C++ loop, then read outputs and assert them with assert(). And you can inspect variables by printing them or with GDB. This is infinitely more convenient than doing these IO-type tasks in Verilog itself.

Some simulation examples under verilog.

First install Verilator. On Ubuntu:

sudo apt install verilator

Tested on Verilator 4.038, Ubuntu 22.04.

Run all examples, which have assertions in them:

cd verilator
make run

File structure is for example:

verilog/counter.v: Verilog file
verilog/counter.cpp: C++ loop which clocks the design and runs tests with assertions on the outputs
verilog/counter.params: gcc compilation flags for this example
verilog/counter_tb.v: Verilog version of the C++ test. Not used by Verilator. Verilator can't actually run out _tb files, because they do in Verilog IO things that we do better from C++ in Verilator, so Verilator didn't bother implementing them. This is a good thing.

Example list:

verilog/negator.v, verilog/negator.cpp: the simplest non-identity combinatorial circuit!
verilog/counter.v, verilog/counter.cpp: sequential hello world. Synchronous active high reset with active high enable signal. Adapted from: www.asic-world.com/verilog/first1.html
verilog/subleq.v, verilog/subleq.cpp: subleq one instruction set computer with separated instruction and data RAMs

Verilator interactive example

The example under verilog/interactive showcases how to create a simple interactive visual Verilog example using Verilator and SDL.

https://raw.githubusercontent.com/cirosantilli/media/master/verilog-interactive.gif

You could e.g. expand such an example to create a simple (or complex) video game for example if you were insane enough. But please don't waste your time doing that, Ciro Santilli begs you.

The example is also described at: stackoverflow.com/questions/38108243/is-it-possible-to-do-interactive-user-input-and-output-simulation-in-vhdl-or-ver/38174654#38174654

Usage: install dependencies:

sudo apt install libsdl2-dev verilator

then run as either:

make run RUN=and2
make run RUN=move

Tested on Verilator 4.038, Ubuntu 22.04.

File overview:

In those examples, the more interesting application specific logic is delegated to Verilog (e.g.: move game character on map), while boring timing and display matters can be handled by SDL and C++.

VHDL

Examples under vhdl, more details at: GHDL.

GHDL

github.com/ghdl/ghdl

Examples under vhdl.

First install GHDL. On Ubuntu:

sudo apt install verilator

Tested on Verilator 1.0.0, Ubuntu 22.04.

Run all examples, which have assertions in them:

cd vhdl
./run

Files:

Examples
- Basic
  - vhdl/hello_world_tb.vhdl: hello world
  - vhdl/min_tb.vhdl: min
  - vhdl/assert_tb.vhdl: assert
- Lexer
  - vhdl/comments_tb.vhdl: comments
  - vhdl/case_insensitive_tb.vhdl: case insensitive
  - vhdl/whitespace_tb.vhdl: whitespace
  - vhdl/literals_tb.vhdl: literals
- Flow control
  - vhdl/procedure_tb.vhdl: procedure
  - vhdl/function_tb.vhdl: function
- vhdl/operators_tb.vhdl: operators
- Types
  - vhdl/integer_types_tb.vhdl: integer types
  - vhdl/array_tb.vhdl: array
  - vhdl/record_tb.vhdl.bak: record. TODO fails with "GHDL Bug occurred" on GHDL 1.0.0
  - vhdl/generic_tb.vhdl: generic
- vhdl/package_test_tb.vhdl: Packages
  - vhdl/standard_package_tb.vhdl: standard package
  - textio
    * vhdl/write_tb.vhdl: write
    * vhdl/read_tb.vhdl: read
  - vhdl/std_logic_tb.vhdl: std_logic
- vhdl/stop_delta_tb.vhdl: --stop-delta
Applications
- Combinatoric
  - vhdl/adder.vhdl: adder
  - vhdl/sqrt8_tb.vhdl: sqrt8
- Sequential
  - vhdl/clock_tb.vhdl: clock
  - vhdl/counter.vhdl: counter
Helpers
* vhdl/template_tb.vhdl: template

Microarchitecture

Computer hardware component type

Processor (computing)

Instruction set architecture (ISA)

The main interface between the central processing unit and software.

Assembly language

A human readable way to write instructions for an instruction set architecture.

One of the topics covered in Ciro Santilli's Linux Kernel Module Cheat.

Assembler (computing)

GNU Assembler (GNU GAS)

Calling convention

List of instruction set architectures

List of instruction set architecture.

One instruction set computer (OISC)

stackoverflow.com/questions/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869

ARM architecture family

This ISA basically completely dominated the smartphone market of the 2010s and beyond, but it started appearing in other areas as the end of Moore's law made it more economical logical for large companies to start developing their own semiconductor, e.g. Google custom silicon, Amazon custom silicon.

It is exciting to see ARM entering the server, desktop and supercomputer market circa 2020, beyond its dominant mobile position and roots.

Ciro Santilli likes to see the underdogs rise, and bite off dominant ones.

The excitement also applies to RISC-V possibly over ARM mobile market one day conversely however.

Basically, as long as were a huge company seeking to develop a CPU and able to control your own ecosystem independently of Windows' desktop domination (held by the need for backward compatibility with a billion end user programs), ARM would be a possibility on your mind.

in 2020, the Fugaku supercomputer, which uses an ARM-based Fujitsu designed chip, because the number 1 fastest supercomputer in TOP500: www.top500.org/lists/top500/2021/11/
It was later beaten by another x86 supercomputer www.top500.org/lists/top500/2022/06/, but the message was clearly heard.
2012 hackaday.com/2012/07/09/pedal-powered-32-core-arm-linux-server/ pedal-powered 32-core Arm Linux server. A publicity stunt, but still, cool.
AWS Graviton

PowerPC

RISC-V

The leading no-royalties options as of 2020.

China has been a major RISC-V potential user in the late 2010s, since the country is trying to increase its semiconductor industry independence, especially given economic sanctions imposed by the USA.

E.g. a result of this, the RISC-V Foundation moved its legal headquarters to Switzerland in 2019 to try and overcome some of the sanctions.

RISC-V International (RISC-V Foundation)

SiFive

Leading RISC-V consultants as of 2020, they are basically trying to become the Red Hat of the semiconductor industry.

RISC-V timer

RISC-V priviledged ISA

RISC-V MSTATUS register

RISC-V MSTATUS.MIE field

x86

x86 Paging Tutorial

This tutorial explains the very basics of how paging works, with focus on x86, although most high level concepts will also apply to other instruction set architectures, e.g. ARM.

The goals are to:

demonstrate minimal concrete simplified paging examples that will be useful to those learning paging for the first time
explain the motivation behind paging

This tutorial was extracted and expanded from this Stack Overflow answer.

Sample code

Minimal example: github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Like everything else in programming, the only way to really understand this is to play with minimal examples.

What makes this a "hard" subject is that the minimal example is large because you need to make your own small OS.

Intel manual

Although it is impossible to understand without examples in mind, try to get familiar with the manuals as soon as possible.

Intel describes paging in the Intel Manual Volume 3 System Programming Guide - 325384-056US September 2015 Chapter 4 "Paging".

Specially interesting is Figure 4-4 "Formats of CR3 and Paging-Structure Entries with 32-Bit Paging", which gives the key data structures.

Application

Paging makes it easier to compile and run two programs or threads at the same time on a single computer.

For example, when you compile two programs, the compiler does not know if they are going to be running at the same time or not.

So nothing prevents it from using the same RAM address, say, 0x1234, to store a global variable.

And thread stacks, that must be contiguous and keep growing down until they overwrite each other, are an even bigger issue!

But if two programs use the same address and run at the same time, this is obviously going to break them!

Paging solves this problem beautifully by adding one degree of indirection:

(logical) ------------> (physical)
             paging

Where:

logical addresses are what userland programs see, e.g. the contents of rsi in mov eax, [rsi].
They are often called "virtual" addresses as well.
physical addresses can be though of the values that go to physical RAM index wires.
But keep in mind that this is not 100% true because of further indirections such as:
- memory-mapped I/O regions
- multi channel memory

Compilers don't need to worry about other programs: they just use simple logical addresses.

As far as programs are concerned, they think they can use any address between 0 and 4GiB (2^32, FFFFFFFF) on 32-bit systems.

The OS then sets up paging so that identical logical addresses will go into different physical addresses and not overwrite each other.

This makes it much simpler to compile programs and run them at the same time.

Paging achieves that goal, and in addition:

the switch between programs is very fast, because it is implemented by hardware
the memory of both programs can grow and shrink as needed without too much fragmentation
one program can never access the memory of another program, even if it wanted to.
This is good both for security, and to prevent bugs in one program from crashing other programs.

Or if you like non-funny jokes:

Figure 1.
Comparison between the Linux kernel userland memory virtualization and The Matrix
. Source. Is this RAM real?

Hardware implementation

Paging is implemented by the CPU hardware itself.

Paging could be implemented in software, but that would be too slow, because every single RAM memory access uses it!

Operating systems must setup and control paging by communicating to the CPU hardware. This is done mostly via:

the CR3 register, which tells the CPU where the page table is in RAM memory
writing the correct paging data structures to the RAM pointed to the CR3 register.
Using RAM data structures is a common technique when lots of data must be transmitted to the CPU as it would cost too much to have such a large CPU register.
The format of the configuration data structures is fixed _by the hardware_, but it is up to the OS to set up and manage those data structures on RAM correctly, and to tell the hardware where to find them (via cr3).
Then some heavy caching is done to ensure that the RAM access will be fast, in particular using the TLB.
Another notable example of RAM data structure used by the CPU is the IDT which sets up interrupt handlers.
The OS makes it impossible for programs to change the paging setup directly without going through the OS:
CR3 cannot be modified in ring 3. The OS runs in ring 0. See also:
- stackoverflow.com/questions/5957570/what-is-the-difference-between-the-kernel-space-and-the-user-space/44285809#44285809
- stackoverflow.com/questions/18717016/what-are-ring-0-and-ring-3-in-os
the page table structures are made invisible to the process using paging itself!

Processes can however make requests to the OS that cause the page tables to be modified, notably:

stack size changes
brk and mmap calls, see also: stackoverflow.com/questions/6988487/what-does-brk-system-call-do/31082353#31082353

The kernel then decides if the request will be granted or not in a controlled manner.

Segmentation

In x86 systems, there may actually be 2 address translation steps:

first segmentation
then paging

like this:

(logical) ------------------> (linear) ------------> (physical)
             segmentation                 paging

The major difference between paging and segmentation is that:

paging splits RAM into equal sized chunks called pages
segmentation splits memory into chunks of arbitrary sizes

This is the main advantage of paging, since equal sized chunks make things more manageable by reducing memory fragmentation problems. See also:

Paging came after segmentation historically, and largely replaced it for the implementation of virtual memory in modern OSs.

Paging has become so much more popular that support for segmentation was dropped in x86-64 in 64-bit mode, the main mode of operation for new software, where it only exists in compatibility mode, which emulates IA-32.

Example: simplified single-level paging scheme

This is an example of how paging operates on a _simplified_ version of a x86 architecture to implement a virtual memory space with a 20 | 12 address split (4 KiB page size).

Single level paging scheme visualization

This is how the memory could look like in a single level paging scheme:

Links   Data                    Physical address

      +-----------------------+ 2^32 - 1
      |                       |
      .                       .
      |                       |
      +-----------------------+ page0 + 4k
      | data of page 0        |
+---->+-----------------------+ page0
|     |                       |
|     .                       .
|     |                       |
|     +-----------------------+ pageN + 4k
|     | data of page N        |
|  +->+-----------------------+ pageN
|  |  |                       |
|  |  .                       .
|  |  |                       |
|  |  +-----------------------+ CR3 + 2^20 * 4
|  +--| entry[2^20-1] = pageN |
|     +-----------------------+ CR3 + 2^20 - 1 * 4
|     |                       |
|     .    many entires       .
|     |                       |
|     +-----------------------+ CR3 + 2 * 4
|  +--| entry[1] = page1      |
|  |  +-----------------------+ CR3 + 1 * 4
+-----| entry[0] = page0      |
   |  +-----------------------+ <--- CR3
   |  |                       |
   |  .                       .
   |  |                       |
   |  +-----------------------+ page1 + 4k
   |  | data of page 1        |
   +->+-----------------------+ page1
      |                       |
      .                       .
      |                       |
      +-----------------------+  0

Notice that:

the CR3 register points to the first entry of the page table
the page table is just a large array with 2^20 page table entries
each entry is 4 bytes big, so the array takes up 4 MiB
each page table contains the physical address a page
each page is a 4 KiB aligned 4KiB chunk of memory that user processes may use
we have 2^20 table entries. Since each page is 4KiB == 2^12, this covers the whole 4GiB (2^32) of 32-bit memory

Single level paging scheme numerical translation example

Suppose that the OS has setup the following page tables for process 1:

entry index   entry address       page address   present
-----------   ------------------  ------------   -------
0             CR3_1 + 0      * 4  0x00001        1
1             CR3_1 + 1      * 4  0x00000        1
2             CR3_1 + 2      * 4  0x00003        1
3             CR3_1 + 3      * 4                 0
...
2^20-1        CR3_1 + 2^20-1 * 4  0x00005        1

and for process 2:

entry index   entry address       page address   present
-----------   -----------------   ------------   -------
0             CR3_2 + 0      * 4  0x0000A        1
1             CR3_2 + 1      * 4  0x12345        1
2             CR3_2 + 2      * 4                 0
3             CR3_2 + 3      * 4  0x00003        1
...
2^20-1        CR3_2 + 2^20-1 * 4  0xFFFFF        1

Before process 1 starts running, the OS sets its cr3 to point to the page table 1 at CR3_1.

When process 1 tries to access a linear address, this is the physical addresses that will be actually accessed:

linear     physical
---------  ---------
00000 001  00001 001
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00002 000  00003 000
FFFFF 000  00005 000

To switch to process 2, the OS simply sets cr3 to CR3_2, and now the following translations would happen:

linear     physical
---------  ---------
00000 002  0000A 002
00000 003  0000A 003
00000 FFF  0000A FFF
00001 000  12345 000
00001 001  12345 001
00001 FFF  12345 FFF
00004 000  00003 000
FFFFF 000  FFFFF 000

Step-by-step translation for process 1 of logical address 0x00000001 to physical address 0x00001001:

split the linear address into two parts:
```
| page (20 bits) | offset (12 bits) |
```
So in this case we would have:
*page = 0x00000. This part must be translated to a physical location.
*offset = 0x001. This part is added directly to the page address, and is not translated: it contains the position _within_ the page.
look into Page table 1 because cr3 points to it.
The hardware knows that this entry is located at RAM address CR3 + 0x00000 * 4 = CR3:
*0x00000 because the page part of the logical address is 0x00000
*4 because that is the fixed size in bytes of every page table entry
since it is present, the access is valid
by the page table, the location of page number 0x00000 is at 0x00001 * 4K = 0x00001000.
to find the final physical address we just need to add the offset:
```
  00001 000
+ 00000 001
  ---------
  00001 001
```
because 00001 is the physical address of the page looked up on the table and 001 is the offset.
We shift 00001 by 12 bits because the pages are always aligned to 4KiB.
The offset is always simply added the physical address of the page.
the hardware then gets the memory at that physical location and puts it in a register.

Another example: for logical address 0x00001001:

the page part is 00001, and the offset part is 001
the hardware knows that its page table entry is located at RAM address: CR3 + 1 * 4 (1 because of the page part), and that is where it will look for it
it finds the page address 0x00000 there
so the final address is 0x00000 * 4k + 0x001 = 0x00000001

Multiple addresses translate to a single physical address

The same linear address can translate to different physical addresses for different processes, depending only on the value inside cr3.

Both linear addresses 00002 000 from process 1 and 00004 000 from process 2 point to the same physical address 00003 000. This is completely allowed by the hardware, and it is up to the operating system to handle such cases.

This often in normal operation because of Copy-on-write (COW), which be explained elsewhere.

Such mappings are sometime called "aliases".

Identity mapping

FFFFF 000 points to its own physical address FFFFF 000. This kind of translation is called an "identity mapping", and can be very convenient for OS-level debugging.

Page faults

What if Process 1 tries to access 0x00003000, which is not present?

The hardware notifies the software via a Page Fault Exception.

When an exception happens, the CPU jumps to an address that the OS had previously registered as the fault handler. This is usually done at boot time by the OS.

This could happen for example due to a programming error:

int *is = malloc(1);
is[2] = 1;

but there are cases where it is not a bug, for example in Linux when:

the program wants to increase its stack.
It just tries to accesses a certain byte in a given possible range, and if the OS is happy it adds that page to the process address space, otherwise, it sends a signal to the process.
the page was swapped to disk.
The OS will need to do some work behind the processes back to get the page back into RAM.
The OS can discover that this is the case based on the contents of the rest of the page table entry, since if the present flag is clear, the other entries of the page table entry are completely left for the OS to to what it wants.
On Linux for example, when present = 0:
- if all the fields of the page table entry are 0, invalid address.
- else, the page has been swapped to disk, and the actual values of those fields encode the position of the page on the disk.

In any case, the OS needs to know which address generated the Page Fault to be able to deal with the problem. This is why the nice IA32 developers set the value of cr2 to that address whenever a Page Fault occurs. The exception handler can then just look into cr2 to get the address.

Page table entries

The exact format of table entries is fixed _by the hardware_.

Each page entry can be seen as a struct with many fields.

The page table is then an array of struct.

On this simplified example, the page table entries contain only two fields:

bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag

so in this example the hardware designers could have chosen the size of the page table to b 21 instead of 32 as we've used so far.

All real page table entries have other fields, notably fields to set pages to read-only for Copy-on-write. This will be explained elsewhere.

It would be impractical to align things at 21 bits since memory is addressable by bytes and not bits. Therefore, even in only 21 bits are needed in this case, hardware designers would probably choose 32 to make access faster, and just reserve bits the remaining bits for later usage. The actual value on x86 is 32 bits.

Here is a screenshot from the Intel manual image "Formats of CR3 and Paging-Structure Entries with 32-Bit Paging" showing the structure of a page table in all its glory: Figure 1. "x86 page entry format".

The fields are explained in the manual just after.

Page size choice

Why are pages 4KiB anyways?

There is a trade-off between memory wasted in:

page tables
extra padding memory within pages

This can be seen with the extreme cases:

if the page size were 1 byte:
- granularity would be great, and the OS would never have to allocate unneeded padding memory
- but the page table would have 2^32 entries, and take up the entire memory!
if the page size were 4GiB:
- we would need to swap 4GiB to disk every time a new process becomes active
- the page size would be a single entry, so it would take almost no memory at all

x86 designers have found that 4KiB pages are a good middle ground.

Example: multi-level paging scheme

The problem with single-level paging

The problem with a single-level paging scheme is that it would take up too much RAM: 4G / 4K = 1M entries _per_ process.

If each entry is 4 bytes long, that would make 4M _per process_, which is too much even for a desktop computer: ps -A | wc -l says that I am running 244 processes right now, so that would take around 1GB of my RAM!

For this reason, x86 developers decided to use a multi-level scheme that reduces RAM usage.

The downside of this system is that is has a slightly higher access time, as we need to access RAM more times for each translation.

K-ary trees to the rescue

The algorithmically minded will have noticed that paging requires associative array (like Java Map of Python dict()) abstract data structure where:

the keys are linear pages addresses, thus of integer type
the values are physical page addresses, also of integer type

The single level paging scheme uses a simple array implementation of the associative array:

the keys are the array index
this implementation is very fast in time
but it is too inefficient in memory

and in C pseudo-code it looks like this:

linear_address[0]      = physical_address_0
linear_address[1]      = physical_address_1
linear_address[2]      = physical_address_2
...
linear_address[2^20-1] = physical_address_N

But there another simple associative array implementation that overcomes the memory problem: an (unbalanced) k-ary tree.

A K-ary tree, is just like a binary tree, but with K children instead of 2.

Using a K-ary tree instead of an array implementation has the following trade-offs:

it uses way less memory
it is slower since we have to de-reference extra pointers

In C-pseudo code, a 2-level K-ary tree with K = 2^10 looks like this:

level0[0] = &level1_0[0]
    level1_0[0]      = physical_address_0_0
    level1_0[1]      = physical_address_0_1
    ...
    level1_0[2^10-1] = physical_address_0_N
level0[1] = &level1_1[0]
    level1_1[0]      = physical_address_1_0
    level1_1[1]      = physical_address_1_1
    ...
    level1_1[2^10-1] = physical_address_1_N
...
level0[N] = &level1_N[0]
    level1_N[0]      = physical_address_N_0
    level1_N[1]      = physical_address_N_1
    ...
    level1_N[2^10-1] = physical_address_N_N

and we have the following arrays:

one directory, which has 2^10 elements. Each element contains a pointer to a page table array.
up to 2^10 pagetable arrays. Each one has 2^10 4 byte page entries.

and it still contains 2^10 * 2^10 = 2^20 possible keys.

K-ary trees can save up a lot of space, because if we only have one key, then we only need the following arrays:

one directory with 2^10 entries
one pagetable at directory[0] with 2^10 entries
all other directory[i] are marked as invalid, don't point to anything, and we don't allocate pagetable for them at all

Why not a balanced tree

Learned readers will ask themselves: so why use an unbalanced tree instead of balanced one, which offers better asymptotic times en.wikipedia.org/wiki/Self-balancing_binary_search_tree?

Likely:

the maximum number of entries is small enough due to memory size limitations, that we won't waste too much memory with the root directory entry
different entries would have different levels, and thus different access times
tree rotations would likely make caching more complicated

How the K-ary tree is used in x86

x86's multi-level paging scheme uses a 2 level K-ary tree with 2^10 bits on each level.

Addresses are now split as:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Then:

the top 10 bits are used to walk the top level of the K-ary tree (level0)
The top table is called a "directory of page tables".
cr3 now points to the location on RAM of the page directory of the current process instead of page tables.
Page directory entries are very similar to page table entries except that they point to the physical addresses of page tables instead of physical addresses of pages.
Each directory entry also takes up 4 bytes, just like page entries, so that makes 4 KiB per process minimum.
Page directory entries also contain a valid flag: if invalid, the OS does not allocate a page table for that entry, and saves memory.
Each process has one and only one page directory associated to it (and pointed to by cr3), so it will contain at least 2^10 = 1K page directory entries, much better than the minimum 1M entries required on a single-level scheme.
the next 10 bits are used to walk the second level of the K-ary tree (level1)
Second level entries are also called page tables like the single level scheme.
Page tables are only allocated only as needed by the OS.
Each page table has only 2^10 = 1K page table entries instead of 2^20 for the single paging scheme.
Each process can now have up to 2^10 page tables instead of 2^20 for the single paging scheme.
the offset is again not used for translation, it only gives the offset within a page

One reason for using 10 bits on the first two levels (and not, say, 12 | 8 | 12 ) is that each Page Table entry is 4 bytes long. Then the 2^10 entries of Page directories and Page Tables will fit nicely into 4Kb pages. This means that it faster and simpler to allocate and deallocate pages for that purpose.

Multi-level paging scheme numerical translation example

Page directory given to process by the OS:

entry index   entry address      page table address  present
-----------   ----------------   ------------------  --------
0             CR3 + 0      * 4   0x10000             1
1             CR3 + 1      * 4                       0
2             CR3 + 2      * 4   0x80000             1
3             CR3 + 3      * 4                       0
...
2^10-1        CR3 + 2^10-1 * 4                       0

Page tables given to process by the OS at PT1 = 0x10000000 (0x10000 * 4K):

entry index   entry address      page address  present
-----------   ----------------   ------------  -------
0             PT1 + 0      * 4   0x00001       1
1             PT1 + 1      * 4                 0
2             PT1 + 2      * 4   0x0000D       1
...                                  ...
2^10-1        PT1 + 2^10-1 * 4   0x00005       1

Page tables given to process by the OS at PT2 = 0x80000000 (0x80000 * 4K):

entry index   entry address     page address  present
-----------   ---------------   ------------  ------------
0             PT2 + 0     * 4   0x0000A       1
1             PT2 + 1     * 4   0x0000C       1
2             PT2 + 2     * 4                 0
...
2^10-1        PT2 + 0x3FF * 4   0x00003       1

where PT1 and PT2: initial position of page table 1 and page table 2 for process 1 on RAM.

With that setup, the following translations would happen:

linear    10 10 12 split  physical
--------  --------------  ----------
00000001  000 000 001     00001001
00001001  000 001 001     page fault
003FF001  000 3FF 001     00005001
00400000  001 000 000     page fault
00800001  002 000 001     0000A001
00801004  002 001 004     0000C004
00802004  002 002 004     page fault
00B00001  003 000 000     page fault

Let's translate the linear address 0x00801004 step by step:

In binary the linear address is:

0    0    8    0    1    0    0    4
0000 0000 1000 0000 0001 0000 0000 0100

Grouping as 10 | 10 | 12 gives:

0000000010 0000000001 000000000100
0x2        0x1        0x4

which gives:

page directory entry = 0x2
page table     entry = 0x1
offset               = 0x4

So the hardware looks for entry 2 of the page directory.

The page directory table says that the page table is located at 0x80000 * 4K = 0x80000000. This is the first RAM access of the process.
Since the page table entry is 0x1, the hardware looks at entry 1 of the page table at 0x80000000, which tells it that the physical page is located at address 0x0000C * 4K = 0x0000C000. This is the second RAM access of the process.
Finally, the paging hardware adds the offset, and the final address is 0x0000C004.

Page faults occur if either a page directory entry or a page table entry is not present.

The Intel manual gives a picture of this translation process in the image "Linear-Address Translation to a 4-KByte Page using 32-Bit Paging": Figure 1. "x86 page translation process"

Figure 1.
x86 page translation process
.

64-bit architectures

64 bits is still too much address for current RAM sizes, so most architectures will use less bits.

x86_64 uses 48 bits (256 TiB), and legacy mode's PAE already allows 52-bit addresses (4 PiB). 56-bits is a likely future candidate.

12 of those 48 bits are already reserved for the offset, which leaves 36 bits.

If a 2 level approach is taken, the best split would be two 18 bit levels.

But that would mean that the page directory would have 2^18 = 256K entries, which would take too much RAM: close to a single-level paging for 32 bit architectures!

Therefore, 64 bit architectures create even further page levels, commonly 3 or 4.

x86_64 uses 4 levels in a 9 | 9 | 9 | 9 scheme, so that the upper level only takes up only 2^9 higher level entries.

The 48 bits are split equally into two disjoint parts:

----------------- FFFFFFFF FFFFFFFF
Top half
----------------- FFFF8000 00000000


Not addressable


----------------- 00007FFF FFFFFFFF
Bottom half
----------------- 00000000 00000000

A 5-level scheme is emerging in 2016: software.intel.com/sites/default/files/managed/2b/80/5-level_paging_white_paper.pdf which allows 52-bit addresses with 4k pagetables.

PAE