From physical RAM to Virtual Memory

Image for post
Image for post

This post is a personal “pot-pourri” of some researches I have made on main memory (RAM) and OS initialization steps …

Plan

  • CPU real mode
  • CPU protected mode
  • Paging
  • Kernel memory management
  • Process memory management
  • ELF extension
  • Linux booting steps (for main memory)

CPU real mode

Most CPUs (Intel) start in “real mode”.
This mode can address 20 bits of memory.
Thus, a total of 1MB is available: from 00000H to FFFFFH.
This 1 MB is also known as “conventional memory” (it was considered as a large amount back at that time).

Memory is accessed by putting the right values in the right registers:

  • One value for the segment into one “segment register” such as CS or SS or DS, …
  • One value for the “offset” into the appropriate offset register (IP or SP or SI, …)

CS = Code Segment = Made to contain the instructions of the program
SS = Stack Segment = Made to keep track of the subroutine calls
DS = Data Segment = Made to contain static variables and global variables

Image for post
Image for post
Figure 1 — Segment and offset registers

Hence, the combination of a segment selector value and an offset value points to a specific address in RAM.

MS-DOS OS runs in real mode. Real mode has different limitations:
→ No memory protection, any address memory is accessible
→ No multitasking
→ No code privilege
→ Memory isn’t that big … (only 1 MB)

CPU protected mode

Protected mode enables:

  • Multitasking thanks to segment protections
  • More memory as it uses 32 bits
  • Segments of different sizes (could be more than 64KB)

CPUs start in real mode but then enable protected mode by setting up a Global Descriptor Table (GDT) in the RAM and then turning the “protection enable” (PE) bit to 1 in the CR0 register.
GDTR is a register pointing to the beginning of the GDT table in the RAM.

The GDT which is setup in the RAM must have at least 3 entries:
→ a null descriptor
→ a code segment descriptor
→ a data segment descriptor

Each GDT entry (called descriptor) is 8 Bytes:

Image for post
Image for post
Figure 2 — A GDT descriptor entry

An entry in the GDT table contains informations on the segment such as:
→ segment base address
→ segment limit
→ access right (DPL value: 0 to 3)
→ descriptor type (read / execute only ?)

In protected mode, segment registers (such as CS, SS, DS, …) now point to an entry in the GDT.
Figure 3 represents what a register such as CS could contain under protected mode.

Image for post
Image for post
Figure 3 — GDT entry pointer (CS for instance)

As you can see the privilege is stored in RPL.
This can be used to distinguish kernel and user code (0 and 3).

Therefore if a CS segment has a RPL value of 3 (user) and is trying to reach a segment described as 0 it would cause an error / exception as 3 being not enough permission (user space) to access kernel (0) segment.

Image for post
Image for post
Figure 4 — protected mode segmentation

x86 CPU protected mode allows the creation of segments with different sizes.
However Linux doesn’t use memory segmentation (considered as ‘legacy’).
Linux uses a “flat memory” model.
Indeed, in the Linux kernel code, all segments (KERNEL_CS, KERNEL_DS, USER_CS, USER_DS) overlap each other and have the same unlimited size !

Image for post
Image for post
Figure 5 — Linux kernel segmentation initialization

Once flat addressing has been set up (as a ‘dumb’ and ‘useless’ segmentation), the Linux kernel will then build a ‘paging’ system on top to create and manage the virtual memory (for both kernel and user space).

Paging

Linux uses paging to create and manage a virtual memory.
To enable paging, the OS will first need to set up some structures:

  • A page directory (PD)
  • A page table (PT)

Page directory

The page directory (PD) contains entries for each page table along some metadata:

Image for post
Image for post
Figure 6 — page directory entry

A page directory consists of 1024 * 32-bit entries.

Each entry holds the address of a page table.

There is only one page directory in the computer / kernel.

Page table

Image for post
Image for post
Figure 7 — page table entry

Page table is an array of 1024 * 32-bit entries (conveniently fitting into a single 4KB page).

Each entry points to the physical address of a page (page is aka ‘frame’ for the hardware).

When a process is created, the Linux kernel gives it a page table (hence an entry in the page directory is created). The process will then be able to allocate memory with syscalls such as “malloc” which will create page entries in the page table.

Paging tables and directory illustrations

Image for post
Image for post
Figure 8 — paging in 32 bits

With paging enabled, each linear address will be translated thanks to PD, then PT, then Offset.

CR3 is a register holding the base address of the page directory (PD). This register never change and is used by the hardware to translate addresses.

Image for post
Image for post
Figure 9 — paging in 64 bits: some intermediary tables are added

Paging is also a hardware feature as special components are involved in the ‘address resolution’.

Indeed, once the page directory has been created by the OS and made available to the CPU thanks to registers (CR3 for instance). The hardware understands how paging work and can handle address translation thanks to the Memory Management Unit (MMU).

Image for post
Image for post
Figure 10 — hardware paging

The Translation Look-aside Buffer (TLB) is a cache used to improve speed.
We can now understand why main memory operations are relatively slow for the CPU.

Number of CPU cycles for different accesses:

1 cycle to read a register
4 cycles to reach to L1 cache
10 cycles to reach L2 cache
75 cycles to reach L3 cache
100+ cycles to reach main memory.
https://www.gamedev.net/forums/topic/599592-memory-access-and-cpu-cycles/

Kernel memory management

The C standard library has a lot of functions related to memory such as “malloc, realloc, calloc, free”.
The Linux C kernel code is self contained and does not rely on the C standard library.
In other words, the kernel doesn’t use malloc, realloc, calloc.

→ So how does the kernel allocate memory (for itself) ? 🤔

The kernel contains implementations of many of the C library’s functions, or variants (for example, printk instead of printf); but they don’t all follow the standard exactly. In some circumstances, the implementations of C library functions in the compiler are used instead.
(https://unix.stackexchange.com/questions/590108/is-the-standard-c-library-loaded-by-default-in-main-memory-in-linux)

Interesting functions created and available for the kernel:
__get_free_page() = returns one free page (low level kernel function)
__get_free_pages() = give a number of consecutive pages (low level kernel function)

→ Can the Linux kernel use a ‘heap’ 🤔

With pure C, without any library, only automatic and static variables are available; no heap allocation.
However, heap allocation is still possible in the kernel space thanks to ‘kmalloc’:
kmalloc is the normal method of allocating memory for objects smaller than page size in the kernel.
The maximum size allocatable by kmalloc() is 1024 pages, or 4MB on x86.

Image for post
Image for post
Figure 11 — Linux kernel layout

I don’t know why but I guess there is a heap in the kernel space (the one used with kmalloc) in Figure 11 above.

kmalloc can be called with different parameters:

Image for post
Image for post
Figure 12 — kmalloc parameters

Process memory management

Image for post
Image for post
Figure 13 — a process memory space

If a program uses recursion without any condition check, it could “overflow” the stack and cause the famous “stack overflow” error.
To avoid that, the developer has to check that:
→ Recursive functions are not “infinite”
→ Function uses “Tail recursion” (the recursive call is the last element executed by the function).

Image for post
Image for post
Figure 14 — memory structures (from kernel viewpoint)

ELF extension

A program is stored as a binary file with a .elf extension (for Executable and Linkable Format) or .exe
ELF is generally the output of a compiler.

ELF binary is divided between:

  1. ELF header
  2. File data

The readelf command shows the details of an ELF file.

Before execution, the Kernel needs to load and to parse the binary. The function load_elf_binary is called, this function checks if the ELF header is valid, and it also sets several pointers: code, brk and stack.
http://shell-storm.org/blog/Linux-process-execution-and-the-useless-ELF-header-fields/

Linux memory booting steps

When the kernel gets the control:

  • It creates a GDT table with the 3 base entries overlapping (in order to get linear = physical address for flat addressing)
  • Saves the GDT memory location into GDTR register
  • Loads an IDT table in memory (for interrupts)
  • Saves the IDT memory location into IDTR register
  • Enables protected mode (it will use the flat addressing GDT table)
  • Create necessary structures for paging: directory and table pages

How is paging enabled at boot time ?

During the boot process, the kernel builds page tables before enabling virtual memory in the CPU. The initial paging tables map two virtual ranges onto the first 8 megabytes of physical memory. The first range is called the identity mapping and it maps virtual addresses 0–8MB (not sure on the 8MB, but something like that) onto physical addresses 0–8MB. The second virtual range maps another ~8MB starting at virtual address 0xc0000000 onto the 0–8MB of physical memory.
That way, immediately after the paging is enabled, things are still working OK thanks to the identity mapping. The kernel can then jump to the 0xc0000000 addresses and it will also work thanks to the second range. It then calls a function called ‘zap_low_mappings’ or something like that to blow away the identity mapping. Everything is up and running as far as paging goes by then.
https://manybutfinite.com/comments/kernel-memory.html

Conclusion

I hope you enjoyed this post, I do not guarantee it to be error free.
Thus, if you detect any error, don’t hesitate to let me know, it would be greatly appreciated.

You can also follow me on twitter and check out the references below if you want to dive deeper into the subject.

References

https://en.wikipedia.org/wiki/X86_memory_segmentation
https://en.wikipedia.org/wiki/Intel_Memory_Model
https://en.wikipedia.org/wiki/Real_mode
https://en.wikipedia.org/wiki/Protected_mode
https://wiki.osdev.org/Real_Mode
https://wiki.osdev.org/GDT_Tutorial

Modes of Memory Addressing on x86
http://www.c-jump.com/CIS77/ASM/Memory/M77_0290_segment_registers_protected.htm
Whole OS booting steps
https://0xax.gitbooks.io/linux-insides/content/Booting/linux-bootstrap-2.html
Multisource and pretty complete post on paging
https://cirosantilli.com/x86-paging#example-simplified-single-level-paging-scheme
Assembly section explained
http://www.mathcs.emory.edu/~cheung/Courses/255/Syl-ARM/7-ARM/data-section.html
Processes and Kernel
https://www.coursehero.com/file/p6v70oqg/Processes-and-threads-are-tasks-The-same-taskstruct-represents-a-process-or-a/

Images

Figure 1
https://www.slideshare.net/VishalJangid1/memory-sementation-sem-69263250
Figure 2
https://en.wikipedia.org/wiki/Global_Descriptor_Table#/media/File:SegmentDescriptor.svg
Figure 3
http://www.c-jump.com/CIS77/ASM/Memory/M77_0290_segment_registers_protected.htm
Figure 4
http://www.c-jump.com/CIS77/ASM/Memory/M77_0300_protected_mode_architecture.htm
Figure 5
https://stackoverflow.com/questions/56213569/linux-memory-segmentation
Figure 6
https://wiki.osdev.org/Paging
Figure 7
https://wiki.osdev.org/Paging
Figure 8
http://valhalla.bofh.pl/~l4mer/WDM/secureread/pde-pte.htm
Figure 9
https://www.cs.uaf.edu/2012/fall/cs301/lecture/11_05_page_translation.png
Figure 10
https://www.quora.com/What-is-the-difference-between-TLB-and-MMU-in-OS
Figure 11
http://www.it.uu.se/education/course/homepage/os/vt18/module-0/mips-and-mars/mips-memory-layout/
Figure 12
http://www.cs.otago.ac.nz/cosc440/labs/lab05.pdf
Figure 13
https://www.geeksforgeeks.org/memory-layout-of-c-program/
Figure 14
https://manybutfinite.com/post/how-the-kernel-manages-your-memory/

I write my own computer science “cheatsheets” and “big pictures” as posts here. I mainly do it for myself but it may benefit others

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store