Welcome to the Spring 2003 Edition of 15-412

Carnegie Mellon
SCS logo

Computer Science Department

Guide to Understanding Segmentation

In these projects, we will be using segmentation as little as possible. Often segmentation is used to increase protection and robustness. In order to simplify the kernel however we will not be using segmentation to achieve these goals. Unfortunately we must still use segmentation in some limited degree to satisfy the x86 architecture's requirements. This document summarizes segmentation as far as the x86 is concerned. Note that you do NOT have to understand how to modify things like the global descriptor table. You simply need to understand what segment selectors need to be in what segment registers when (and what a segment register and selector is).

To begin, let's take another look at privilege levels. At any given time, the CPU is executing at one of four privilege levels. The privilege levels are organized something like this (this diagram is taken right out of intel-sys.pdf, chapter 4, section 5):

In these projects (as is the case with many operating systems), only privilege levels 0 and 3 will be used. Privilege level 0 (PL0) corresponds to kernel mode, while privilege level 3 (PL3) corresponds to user mode. The privilege level of the currently executing process is stored in the bottom two bits (the RPL) of the segment selectors in the %CS and %SS registers (this implies that those two bits must be the same). We will look more at segment selectors in just a moment.

Protecting the Kernel

We would naturally like to protect the kernel from being tampered with by meddling user processes. We could use segmentation to do this, but because we are trying to avoid segmentation, we will use the paging mechanism. Each page table entry has a bit for user/supervisor. This bit controls whether the page is accessible from user mode (PL3). Note that there is also a similar bit in the page directory entry. These two bits combine to specify the overall access characteristics of the page.

So, in order to use paging to protect the kernel area, that means that our user processes will have to execute in user mode (PL3). This might be obvious to some, but it is important to conciously realize the reasons why we do not just run all the code, kernel and user, in kernel mode (PL0) or run all the code in user mode (PL3). In order to have all memory accesses checked by the hardware automatically, we need to make use of the privilege level mechanism (and either segmentation or paging - in our case, paging).

So now, we've established that we have to have two separate privilege levels in the system. The kernel will run at privilege level 0, and the user processes will run at privilege level 3. Now that we know that, let's take a closer look at what segmentation is, what we have to do to use it, and how our privilege level constraints interact with it.

Segmentation

Here are two excerpts from intel-sys.pdf (page 65) about segmentation.

The memory management facilities of the IA-32 architecture are divided into two parts: segmentation and paging. Segmentation provides a mechanism of isolating individual code, data, and stack modules so that multiple programs (or tasks) can run on the same processor without interfering with one another. Paging provides a mechanism for implementing a conventional demand-paged, virtual-memory system where sections of a program's execution environment are mapped into physical memory as needed. Paging can also be used to provide isolation between multiple tasks. When operating in protected mode, some form of segmentation must be used. There is no mode bit to disable segmentation. The use of paging, however, is optional.

As shown in Figure 3-1, segmentation provides a mechanism for dividing the processor’s addressable memory space (called the linear address space) into smaller protected address spaces called segments. Segments can be used to hold the code, data, and stack for a program or to hold system data structures (such as a TSS or LDT). If more than one program (or task) is running on a processor, each program can be assigned its own set of segments. The processor then enforces the boundaries between these segments and insures that one program does not interfere with the execution of another program by writing into the other program's segments. The segmentation mechanism also allows typing of segments so that the operations that may be performed on a particular type of segment can be restricted.

As is evident from this description, segmentation is a powerful tool for providing protection and robustness. A segment is a single contiguous portion of a process' address space. Segments can be of any size (a single byte to 4 gigabytes), start at any location, and have many different access characteristics (privilege level required to access, readable, writeable, executable, etc).

To define a segment, we use a segment descriptor. This is quite like installing an entry in the interrupt descriptor table you are already familiar with. The segment descriptor gets installed in the global descriptor table. It is also possible for segment descriptors to be installed in a local descriptor table, however we will not be using this option. Segment descriptors have the following format:

The segment descriptor contains everything you would expect it to: the segment's start address, its size, the privilege level required to access it (DPL), and the type of the segment (this is something like CODE/EXEC, READ/WRITE, READONLY, etc). Once we have defined a segment descriptor, it would be nice to have an easy way to refer to the segment. One way to do this is to simply refer to the segment's index in the global descriptor table. This is the principal behind the segment selector.

A segment selector is a 32-bit object that specifies a segment by its index in either the global or local descriptor table (again, we'll only be using the global table). Here is the exact format of a segment selector:

The important part for you to consider is the top 13 bits. These 13 bits are the index into the descriptor table. The 3rd bit, which determines whether the index is into a local descriptor table or the global descriptor table, will always be 0 in our case (we will only be using the GDT). The last two bits form the RPL, or request privelege level. For reasons I will not go into here, we always want this to be equal to the privelege level of the code which will be accessing it. We will look at this again a little later.

Using Segmentation

Now that we know how to define and refer to segments, let's look at how they are used. Every 32 bit address in the x86 architecture is actually initially accompanied by a segment selector. The segmentation layer of address translation, which occurs above the level of paging (recall the slides on "the life of a memory access" in the lecture on project 3), simply consists of finding the base address of the segment referenced by the segment selector, and adding that base address to the 32 bit address. This gives us our overall 32 bit address after segmentation has been applied. Note that there are also privilege level checks that occur during this step. If the CPU is currently executing at PL3, and the segment it is trying to refer to has a DPL (in its descriptor, see above) less than 3, a general protection fault will occur.

So, we know that there are these segment selectors which accompany every 32 bit address. But where do these segment selectors come from? The segment selector used to define which segment a memory access is in depends on the kind of memory access that occured.

For instruction fetches, the segment selector is taken from the %CS register.
For stack related operations (such as push and pop), the segment selector is taken from the %SS register.
For any other type of memory access, the segment selector is taken from the %DS register, unless the instruction explicitly requests the use of a different segment register (%ES,%FS, or %GS).

When you enter the main() function in the kernel.c we provided for project 3, OSKit has set up two segments for you to use: KERNEL_CS and KERNEL_DS. These #defines are actually 32 bit segment selectors that refer to a PLO code segment that goes from address 0x0 all the way up to 0xFFFFFFFF (KERNEL_CS), and a PL0 data segment that also spans the entire address space (KERNEL_DS). This was true in project 1 as well. Since we would like to make minimal use of paging, these segments work well. Since their base address is 0, when we apply segmentation to our addresses, the value of the addresses do not change.

So, to avoid segmentation, all we needed to do in project 1 (OSKit took care of this for you) is place KERNEL_CS into the %CS register, and KERNEL_DS into the %SS, %DS, %ES, %FS, and %GS registers. We can use KERNEL_DS for the stack and data segment registers since they all need to reference a read/write data segment (and our single read/write data segment spans the entire address space). We loaded these segment registers once, and never had to worry about them again. The hardware transparently applied these segments to all our memory accesses, however since the base address of both segments was zero, the layer of segmentation had no effect on the addresses.

Unlike project 1 however, in project 3 we need two different privilege levels (recall from the beginning of this document). User code needs to execute in PL3, and kernel code needs to execute in PL0. This is going to complicate our segmentation situation somewhat, because those two segments we already have defined (KERNEL_CS and KERNEL_DS) require a privilege level of 0 to access them (their descriptor DPL is 0). So, we will need to create two new segments, USER_CS and USER_DS. These segments will be the same as the PL0 ones in terms of their size and location (they will span the entire address space and start at 0). However they will only require PL3 to access.

The function install_user_segs(int user_cs_idx, int user_ds_idx) installs a user DPL code segment at index user_cs_idx in the global descriptor table, and likewise puts a user DPL data segment at index user_ds_idx in the global descriptor table. It does not put segment selectors for these segments into the segment registers. You would not want that, because you will likely be calling this from within your kernel. We have defined the indices that you will be installing these segment descriptors to. They are USER_CS_IDX and USER_DS_IDX.

To switch into user mode (PL3), you will set up an iret block that contains a stack segment selector and a code segment selector. The segment selectors for the stack and code segment must have an RPL of 3, since that defines the privilege level. They are located in the GDT, so the TI bit (bit 3) is zero. The index of the selector will be USER_CS_IDX for the code segment, and USER_DS_IDX for the stack segment. We have defined these segment selectors for you in seg.h. They are USER_CS_SEGSEL and USER_DS_SEGSEL.

The code and stack segment registers are changed automatically when you take an interrupt or exception. This happens because when you set up your interrupt and exception handlers in the IDT, you specified that they were DPL 0. This means the handlers need to be executed at privilege level zero. You also specified that the code segment was KERNEL_CS. The stack switches automatically to a value defined in the hardware task OSKit has set up (this is similar to the value set by the set_esp0 function).

Before you iret to user mode, remember you need to install segment selectors into the data segment registers as well. You can use the same segment selector that you put into the stack segment register, USER_DS_SEGSEL.

Finally, you need to remember to save and restore those data segment registers along with the rest of the process' context on a context switch. Once you bootstrap a new process, its code and stack segment selectors will be saved automatically by the interrupt mechanism (look at the iret block, the CS and SS values are saved in there). However the data segment registers are not saved. These could be changed while you are in kernel mode to point to segments requiring PL0 to access. If you resumed executing a user process with that, the first time it attempted a memory access it would receive a general protection fault. So, make sure to save and restore those data segment registers.