Segmentation and Paging in x86

As x86 CPU starts running in real mode which you probably don't want to use and will either want to switch to 32bit mode with paging enabled or 64 bit mode (aka long mode) we need to change mode of execution somehow. To do that we need to configure CPU and execute certain instructions. That means we will need work for a little bit (just a little bit) in real mode and understand how CPU behaves in that mode.

A little bit of history

When Intel first designed x86 it had an idea that every memory item would be in a segment of memory. Each segment was a small chunk of memory of a specific size. Each segment would be serve different purpose. Code segment (CS) would be used to store executable code. Default segment (DS)* would be used to store data. Stack segment (SS) would contain stack information. Extended segment (ES) would be used for whatever programmer intended it for. Later on the portfolio of segment registers was extended to FS and GS. These ones don't have a processor defined purpose but programmer can choose what to use them for herself/himself. In the end modern x86 CPUs have the following segment selectors: CS, DS, SS, ES, FS, GS.

Unless you have enabled paging on your CPU your processor is operating in segmentation mode.

The CPU uses these segments when executing certain instructions. For example when fetching next instruction the CPU uses CS segment to calculate physical address where the instruction can be found. When using mov instruction it uses DS and when using doing push or pop it it uses SS.

Segmentation in real mode

As CPU starts in real mode let's first talk about how segmentation works in this mode.

In real mode segmentation is relatively simple. A logical address of form A:B (where A ∈ [CS, SS, DS, ES, FS, GS]) is used. This logical address is then translated into physical address by using A * 0x10 + B. Since in real mode registers are limited to 16bits for addressing this allows us to address 2^16 = 64Kb of memory within a single segment.

Segmentation in protected mode

In protected mode we use the same form A:B as in real mode except in protected mode A is not an absolute value of the segment but a segment selector. Selector is an index into a table. Each of the entries in the table describe segment (physical address, protection level, etc...). Physical address of the segment is read from the table entry (which is also know as segment selector) and B (aka offset) is added to that physical address to get actual physical address of the memory location.

There are two tables where segment selectors can be stored. They are called Global Descriptor Table (aka GDT) and Local Descriptor Table (LDT).

What this means that before we can switch our CPU into protected mode we need to set up at least GDT.

Fortunately, there's a good chance you will never need to set up GDT for protected mode as x86 can switch into protected mode with paging enabled straight from real mode.

Paging

Paging is a different way of accessing physical memory. Instead of memory being divided into segments it is divided into pages and frames. Frame is a block of physical memory of a specific size (e.g. 4Kb) while page is a block of virtual memory of the same size. Pages are same size as frames. In this mode program does not access memory using physical address. Instead it virtual memory addresses are used. Those virtual addresses are translated into physical addresses by CPU. This is a very expensive process compared to accessing memory directly and almost all CPUs have additional circuitry to help with that. That circuitry is called MMU or Memory Management Unit.

Following image illustrates memory translation process. Keep in mind that the image is simplified a lot and does not represent exactly what happens in a CPU. It does however illustrate basic concepts that we will build upon when we will be setting up paging.

For a CPU to translate a virtual address 0x5006 into a physical address the CPU first takes a prefix and looks up that prefix in its "page table" and finds what physical address is associated with that prefix. For now you can think of page table a special place in CPU. In our case physical address associated with page table entry 0x500 is 0x0011. CPU then takes that address (0x011) and adds the last part of the address (0x6). 0x0010 + 0x6 = 0x0016. And that's how CPU translates virtual address 0x5006 to physical address 0x0016.

This approach can be extended to multi-level page tables:

In the above image first two bytes are used as index into "Page directory". The following byte is used as an index into "Page table" and the last byte is offset within memory page.

x86 processors normally use 3 or 4 level paging with most recent ones being able to use even 5 level paging system.

Conclusion

Using paging allows us to do create arbitrary memory layouts and better utilise memory. It also allows us to implement more complex scenarios where each process has its own address space. In this series we will use very simple paging "strategies" (e.g. identity mapping) but for those who are interested and would like to know more I suggest reading Operating Systems: Three Easy Pieces - http://pages.cs.wisc.edu/~remzi/OSTEP/.

If you have any questions / comments please leave them below.

Notes:

• Default segment is often known as data segment.