Logical Address and Segmentation
From The Linux Memory Wiki
In the early days when Intel developed the 16-bit CPU, they didn't thought of the memory capacity will grown exponentially until gigabytes for today. In those time, 1MB was a tremendous amount of memory and computer that time had only few kilobytes of memory.
For your information, 16-bit can address up to only 64KB of memory. (2^16 = 65536 bytes)
Hence, soon the memory capacity has grown beyond 64KB and programmers were in big headache on how to address the memory beyond 64KB.
Soon, Intel introduced the segmentation system to solve the problem. Today, although 32-bit and 64-bit architecture has already overcome the memory addressing problem, the segmentation architecture still exists. The reason is Intel claims that segmentation may provide better programming structure for programmers.
In Linux, the kernel does not take advantage of segmentation. This is to improve portability to other architectures which have limited support on segmentation. Another reason is that the features in segmentation overlap with the Linux paging system.
Hence, we won't discuss the benifits of segmentation here, and neither will we discuss how segmentation solved 16-bit addressing problem. The important thing for you to know is how the segmentation unit works in 32-bit x86 architecture. A brief explanation is neccesacy because we cannot disable segmentation in x86 cpu and we will see how Linux has limited use on segmentation.
Contents |
The Logical Address
In x86, the logical address is consist of a 16-bit segment and 32-bit offset. The offset is the normal address you usually write in assembly program, while the value of the segment is stored in the segment registers. The segment registers are same as other general purpose registers other than they have special purposes, which is to segment addresses. There are 6 segment registers in x86: cs (Code Segment), ss(Stack Segment), ds(Data Segment), es, fs, and gs.
Each segment registers are only 16-bit (not 32-bit even for x86 and x64 architecture!) and they contains 3 data inside this 16 bits:
The first 2 bits (bits 0-1) are called the Request Privilege Level which indicates the privilege level required to access this segment. For example, if the RPL is set to 0, codes which has privilege 3 may not access this segment. (see Privilege Level)
The third bit (bit 2) is the Table Indicator. It indicates whether the CPU should load the segment descriptor from the Global Description Table (if 0) or Local Description Table (if 1). We will discuss about segment descriptors and description tables later.
The remaining 13 bits (bits 3-15) are the index to the segment descriptor.
We will start a example here and continue this example until the end of the chapter:
suppose we have a jump instruction, jmp 0x00000630,
The value 0x00000630 is the offset of the logical address and because the address refers to the next instruction, it will be located in the code segment. Thus the segment register is the %cs register which refers to code segment.
suppose the %cs register contains the following 16-bit value:
0x00000022 = 0000 0000 0000 0000 0000 0000 0010 0010
This means that the code segment requires level 3 privillege (user mode) to access,
The segment descriptor is in the Global Description Table
and the index of this segment is at 0x100, i.e. the 256th entry inside the Global Description Table.
The Segment Descriptor
The segment descriptor is an 8 bytes data stored in the memory. It contains various fields to store information about a segment. However for simplicity, we only talk about one of the field, the Base field. The base field contains the 32-bit linear address this segment points to. This base field will then be added with the offset to produce the linear address. (We omit some other details although the statement is partially correct.)
So we know that the actual linear address of the logical address jmp 0x00000630 would now be translated to jmp 0x12000630.
The Global Descriptor Table and gdtr
The Global Descriptor Table (GDT) is a table that stores the entries of the segment descriptors. The Local Descriptor Table (LDT) does the same thing except that it is customizable by user processes. We won't discuss about LDT here as it has nothing to do with the linux kernel.
We know there are many segment descriptors, each descriptors has an index and they are stored in the memory. So the question is, how do we load them from the memory?
The answer is that we have another register called the gdtr register. The gdtr register is 32-bit and it points to the physical address of the GDT. The Linux kernel has to allocate the space inside RAM for the GDT and then set the gdtr register points to the physical location. Currently we won't talk about how the kernel did this and we assume that the kernel has already created such table.
So we now have the physical address of the GDT and the index of the segment descriptor. Next we will have to multiply the index by 8 (since the segment register is 8 bytes) and add this to the physical address of GDT. Then we will get the physical address of the segment descriptor.
Continue to our example,
suppose the gdtr register has the value 0x0000A000,
We have to add (index x 8) into the table, 0x100 x 8 = 0x800,
0x800 + 0xA000 = 0xA800
Hence our segment descriptor is actually located at physical address 0x0000A800.
We first loaded the descriptor at 0xA800, and then from there we found that the base address was 0x12000000 and only we add the logical address to become 0x12000630. What a complex steps!
The Segmentation Unit
Linux Segmentation
Linux only makes use of 4 segments: The user code segment, user data segment, kernel code segment and kernel data segment. All these segments starts from 0x00000000 to 0xffffffff. (i.e. base value in segment descriptor is 0x00000000 and limit size is 0xffffffff) The only difference of the segments are the privillege levels and the type of segments.
The same mapping of all 4 segments means that in linux all logical address = linear address (Oh no all we learned about segmentation becomes useless!). In fact, this is what linux tries to do. Hence when studying following memory management, we only need to worry about 2 types of memory address - linear address and physical address.
However, we will still need to refer back segmentation when talking about other aspects of the kernel, such as process switching and interrupts, hence a basic understanding of Linux segmentation is still essential in studying the kernel.
Moreover, understanding segmentation first will help you on understanding the more complex paging mechanism, since the basic idea of paging is the same as segmentation.
Sharing of Segments
All processes and the kernel use the same sets of global segments. meaning the %cs and other segments registers are point to either the four user or kernel segments of code or data.
Prior to the Linux kernel 2.4, typically in 2.2, each process had 2 of their own dedicated segments, called the Task State Segment (TSS) and the LDT descriptor. This made a restriction to the total number of processes that can exist to be 4090 since there may be only a maximum entry of 2^13 - 1 = 8192 entries in the GDT.
Today there is no more such limitation and hence we really don't need to care so much about segmentation problems anymore.
