Memory Management in Linux Kernel

Linux Memory Management: Chapter 02 : Segmentation
-----------------------------------------------------------------------------------------------------------------------
WRITTEN BY : Karthikeyan Raghuraman
REFERENCE : Understanding the Linux Kernel, O'Reilly Publications
DISCLAIMER : The content below is my understanding of the Chapter 1 in the above mentioned book. I myself being a newbie do not guarantee the authenticity of the following information.
CONTACT : karthikeyan dot raghuraman at gmail dot com
-----------------------------------------------------------------------------------------------------------------------

The OS is not forced to keep track of physical memory all by itself.todays Micro processors are built in with hardware which make the memory management effecient as well as robust against programming errors.

**Memory Addresses
------------------
++This is specific to the more common X86 processors.++

There are three kinds of addresses in the X86 processors.
1.LOGICAL ADDRESS
This is the SEGMENT:OFFSET representation of the actual address.
2.LINEAR ADDRESS
A single 32 bit integer that can be used to address till 4GB of space(2^32 bytes).
3.PHYSICAL ADDRESS
Used to address the memory cells in the memory chips. They are the address sent in the Address Bus.

The flow of Address Values when the address is represented in Logical Address format.

Logical Address | | Linear Address | |Physical Address
----------------->|Segmentation Unit|----------------->|Paging Unit|------------------> AddressBus
| | | |


**Address Translation in the x86 processors [1]
----------------------------------------------
The address translation occurs in two different ways
1. REAL Mode.
2. PROTECTED Mode.

REAL Mode:
This is used mainly for Backward compatibility of the processors.
BIOS uses real mode of addressing.A real mode address comprises of a segment and offset.The corresponding address is given by

SEGMENT ADDRESS * 16 + OFFSET
say u have address
FFFF:0001
then the addres is FFFF1.
FFFF * 16 = FFFF0
FFFF0 + 0001 = FFFF1

If you could recollect the x86 architecture after x386 the Global Descriptor Table/Local Descriptor tables are used for calculating the physical address. But the initialization of these registers is done when the computer is booted and is done in the REAL mode.


**PROTECTED MODE Address translation
------------------------------------
As most of the operations in the processor occurs in this mode we might need to touch base with the basics of the processor a liitle bit before proceeding with the Address translation.

* Segmentation Registers
-------------------------

We know that logical address consists of two parts. SEGMENT identifier:OFFSET

SEGMENT identifier : 16 bit field for SEGMENT SELECTOR.
OFFSET : 32 bit field.

To retrieve segment selectors quickly we have the SEGMENT REGISTERS in the processor like. There are totally 6 of these registers.
CS :Code Segment
DS :Data Segment
SS :oh no not the Reich army of Himmler;) it is Stack Segment
ES :Extended Segment
FS :
GS :

The CS register has a 2 bit field which specifies the Current Privilege level(CPL) of the CPU. 0 is highest priority and 3 is lowest priority

++ Linux uses only two priority levels. 0 and 3 for Kernel and User mode respectively.


* Segment Descriptor:
---------------------
Each segment is represented by an 8 byte segment descriptor. They are stored either in the Globat Descriptor Table(GDT) or the Local Table Descriptor(LDT).

Generally only one GDT is defined and each process has its own LDT.

<-> Address of GDT in Main memory: This is in the _gdtr_ processor register.
<-> Address of LDT in Main memory: This is in the _ldtr_ processor register.

What is in a Segment Descriptor
-------------------------------
1. BASE Field : A 32 bit field that contains the linear address of the first byte in the segment.
2. Granularity(G) bit : If set size of the segment in multiples of 4KB else in bytes
3. LIMIT field : 20 bit field. If G bit is 0 then the size may vary from 1b to 1MB else 4KB to 4GB
4. System(S) bit : If RESET indicates Kernel is using this else it is a normal segment.
5. Type Field : 4 bit field indicating the access rights for the descriptor and the segment.

* List of Segment Descriptors
------------------------------
-CS Descriptor : It can be present in GDT/LDT and has the S flag set.
-DS Descriptor : It can be present in GDT/LDT and has the S flag set. Stacks represented using Generic data segments.
-TSS Descriptor: Task State Segment Descriptor. This segment is used to save the contents of the processor registers.
It can appear only in the GDT. The TYPE field has a value 11/9<1011,1001>. S flag is cleared.
-LDTD : Local Descriptor Table Descriptor.
Indicates that the Segment Descriptor refers to a segment containing an LDT.
Present in the GDT only.
TYPE Flag : 2
S flag : 0
+Contents of this Descriptor
----------------------------
1. DPL : Descriptor Privilege Level. A 2 bit field. Represents the minimum CPL is required to access the Descriptor.
2. Segment Present Flag: This is set when the segment is in the main memory else it is reset.
3. Data/Code Flag : This flag says if Data is present or Code in the segment.
4. AVL flag : used by different OS but is ignored by LINUX.


** SEGMENT Selectors
---------------------
- Every segment register maps to a non programmable register in the processor which directs you to the Segment descriptor.
- Every time a segement register is loaded with the value in a segment selector, the corresponding segment descriptor address is stored in the non-programmable register.

What does a Segment Selector contain ?
--------------------------------------
1. A 13 bit segment descriptor entry pointer, which identifies the entry in the GDT/LDT.
2. A Table Indicator Flag which describes whether the entry is in GDT/LDT.
3. An Request Privilege Level (RPL) which is the same as CPL in the code segment descriptor.

So now we know that the value of the CPL is used in Code Segment, the LDTD and the Segment selector.

How is a logical Address converted to a Linear Address
------------------------------------------------------
gdt/ldt
.-------.
| |
|_______|
.-----> |descriptor
|_______|-------------> + -----> Linear Address
| | | |
| | | |
| `-------' |
| |
+<----- gdtr/ldtr |
| ---------- |
| ---------- |
X 8 ^ |
| | |
------------------ ---------------
Index | TI : Offset
------------------ ---------------
Segment Selector
------------------------------------------
Logical Address

Explanation
------------
1. The Segment Selector has the Fields Index<13 bit> and the Table Index Flag<1bit>
2. Each Segment Descriptor is 8 byte long.
3. If the Descriptor X is stored at address MM in the memory, the next Descriptor will be at MM+8.
4. Hence to obtain the address of the descriptors, the Index is MULTIPLIED BY 8.
5. The Table Index flag is used to determine if the table is in the LDT/GDT.
6. If GDT then the GDTR value is added to the result of step 3 else the LDTR is added.
7. Now the value in step 6 represents the address of the descriptor in the GDT/LDT.8. Access the Descriptor.
9. Now from the Descriptor's Base Field<32 bit field> we get the first byte of the segment.
10. Now to this value add the offset in the Logical address.
11. The value in Step 10 is the Linear address.

Gyan:
----
The first byte of the GDT/LDT is always zero. This is to ensure that a logical Address with a Null Segment selector is invalid.
The Maximum number of segment descriptors that can be stored in GDT is (2^13 - 1 =8191)


the above topics covered the basics of Segmentation in a x86 processor.
Now for some Linux stuff

**Segmentation in Linux
-----------------------
Does Linux use Segmentation ?? the fact is it uses it in the most limited way.
Linux relies mainly on Paging than on Segmentation. This is because
- Memory Management is easy when all the processes use the same segment register value, this boils down to
the processes using the same set of linear addresses
- Linux is ported into many systems. The RISC architecture systems do not support/in a limited way provide segmentation.

In this architecture it is possible to store all the segments in a single GDT.why this is not a limiting factor>

LDT are not used by the KERNEL, but an Interface is exposed which allows the process to create there own LDTs.

Segments Used by LINUX
-----------------------
* The kernel code segment. The GDT entries for this are
- Base : 0x00000000
- Limit: 0xFFFFF
- G : 1
- S : 1
- Type : 0xA
- DPL : 0
- D/B : 1

The KERNEL mode segment selector is given by the macro __KERNEL_CS. To address this segment the kernel loads
the return value of this macro in to the CS register.

* The Kernel Data Segment The GDT entries are
- Base : 0x00000000
- Limit: 0xFFFFF
- G : 1
- S : 1
- Type : 2 ** this is the only variation with the above
- DPL : 0
- D/B : 1

The KERNEL mode segment selector is given by the macro __KERNEL_DS.

* The User Code Segment. The GDT entries are
- Base : 0x00000000
- Limit: 0xFFFFF
- G : 1
- S : 1
- Type : 0xA
- DPL : 3
- D/B : 1

This segment can be accessed in both the Kernel and the User modes.
The segment selector is defined by the Macro __USER_CS.

* The User Data Segment. The GDT entries are
- Base : 0x00000000
- Limit: 0xFFFFF
- G : 1
- S : 1
- Type : 2.
- DPL : 3
- D/B : 1

The KERNEL mode segment selector is given by the macro __USER_DS.

Segmentation was introduced for the logical distinction between different types of codes.What we find from the above
descriptions of the GDT entries is, all the different actually overlap which each other which kind of defeats the
purpose of segmentation introduced in the x86 processors.

So we could say that LINUX uses segmentation in such a limited way, that it could actually do away with it.

* Task State Segment.
The descriptors of these segments are stored in the GDT.
Base : this is associated with the tss field of each process
G : this is cleared.
Limit: 0xEB
Type : 9/11
DPL : 0

* A Default LDT Segment

This segment is shared by all processes.

Stored in the default_ldt variable.
Includes a single null Segment Descriptor.
Each process has its own LDT segment descriptor.

Generally the values are set as
Base Field : default_ldt value.
Limit : 7

If a process requires an LDT then a new 4096Byte segment is created. The default LDT segment descriptor
for this process is replaced with the value of the current segment in the GDT.

GYAN:
-----
Now for each process the system has to maintain two descriptors, One for TSS and one for LDT.
So totally 12 entries.
No of entries that could be made in the GDT is 2^13 - 1 = 8191
No of processes that can run in the system at any moment is (8191-12)/2 ~ 4090