Segmentation and Paging in Linux

The goal of both paging and segmentation is ultimately the same – to provide a way to translate virtual or logical addresses into physical addresses, that actually exist in the RAM.

Segmentation

Segmentation in Linux is not really used as the main virtualization technique anymore, and is kept mainly as a relic from the past.

There is a segment register for the code and the data segment in the program, as well as a bunch of other segments, which we won’t discuss. But each of these segments are described by a segment descriptor which is an 8 byte  entity.  There is obviously a bunch of stuff in each segment descriptor, but it mainly has the base address for each segment, its bounds and so on. The list of all the segment descriptors is maintained by the kernel in the Global Descriptor Table (GDT).  There is 1 GDT per every processor.  The kernel can also use a per-process descriptor table also called the Local Descriptor Table (LDT),  but this is rarely used.

So how do we get to the segment descriptors? Each segment register stores a segment selector.  A segment selector is a 16 bit entity. The 2 LSBs stand for the Requested Privilege Level (RPL).  Clearly it can represent 4 different privilege levels. The privilege levels 0-2 are all considered to be kernel mode whereas  level 3 is considered to be user mode. Thus this provides an easy way to protect the user mode from performing kernel-mode operations. The next bit is either a 0 or 1 indicating whether we should be using a GDT or LDT. Finally the remaining 13 MSBs are an index into the GDT(LDT) for the segment descriptor corresponding to the segment. In practice though, it isn’t necessary to access the GDT each time we need to look up a segment descriptor. Whenever there is a context switch, the kernel will initialize the segment registers with the corresponding segment selectors for the new process. At the same time, there are also corresponding non-programmable registers that will store the segment descriptor for the segment. Thus the  GDT needs to be looked up just once, during the context switch.

 

Paging

Paging in linux just provides a means to translate the virtual page numbers (VPN) to the corresponding physical page numbers. The typical way to do this is to maintain a page table. A page table simply provides a mapping from each VPN to the corresponding PPN.  Unfortunately, even for 32 bit architectures, this would mean having 2^32 entries, in the main memory.

The CR3 register stores the base address of the page table. Obviously, since each process will have a different VPN -> PPN mapping, there is a separate page table for each process. Whenever there is a context switch, the kernel saves the CR3 for the process in its task_struct and restores the CR3 from the task_struct for the new process.

Thus in linux, a page table is usually multi-level. First let’s talk about 32 bit architectures.  In this case the CR3 register points to page directory, the page directory in turn points to the page table. Each VPN is thus split into 3 parts. The first 10 MS bits are the index into the page directory and the next 10 bits are an index into the page table. Finally the last 12 bits are the actual offset in the page.  In case of 64 bit architectures, there is even more level of indirection.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s