Memory management - PART I

It is been a long time, the topic I choose now is memory management is a vast topic. This blog is my understanding based on "Understanding Linux Kernel"

Before starting into this topic, we will discuss about some basic, how bus are connected with CPU.

two type of bus are connected with CPU front side bus and backside bus.
front side bus - bus that connect CPU and most other components in computer like memory, bridge.
Back side bus - separate connection between processor and level 2 cache.

The above figure explain you how the peripheral been connected to processor.

Now we will see how an executable code get executed. If CPU need to execute a program it need to bring the code from hard disk to ram. Let say if we have N process each for different use cases and size. Then it need to bring it to memory and executed. CPU can execute only one at a time then there should be queue to maintain it. There are lot of background process like scheduler will be running to maintain fair chances to all. But how address of the code get mapped?

Different binding mechanism:

Before starting this you need to understand C compilation process. Which will help you to understand clearly. Here is some crisp message - compiler generate relocatable object files and loader generate absolute address. So when a C program is compiled it hold just a relative address. So that it can get mapped to memory. How a compiled C code get mapped to memory does it mapped randomly or how it get mapped? who help it to get mapped? how a executable code fetched from storage to memory? - I won't share this I will ask the reader to share their answer in comments.

1. Compile time binding

Compiler generate code which bind with physical address. which can't be loaded other than mapped location.

2. Load time binding

Compiler generate a relative address and loader bind that address to absolute address. So the code can be loaded to any location. but once it loaded to that location it can't be remapped to different location.

3. Execution time binding

Here it is same as above but it can be loaded and reloaded to any location in memory during run time. It required a special hardware to do so. because the CPU generate relative address it has to get mapped to corresponding to program.

Now we understand the different mechanism. Hey! If we look above CPU will be using relative address i.e, logical address and there will be hardware mechanism that convert the logical address to physical address.

Different CPU modes 

Protected Modes - (PE - 0) - Instruction and architectural features are available. It is the recommended mode for all new application and Operating system.

Real address Modes - (PE - 1, VM - 0) - provide programming environment of 8086. When powered on CPU runs in real mode. In real mode the cpu address 16 bits memory.

System Management Mode -  provide system wide handling functions like power management, system hardware control or proprietary design code.

Virtual Mode - (PE - 1, VM - 1) - In this mode processor execute 8086 software in a protected, multitasking environment.

there two different type of addressing, byte addressing and segment addressing. Segment + byte addressing will provide better way to access or address byte in memory.


System Registers
EFLAGS - control task, mode switching, interrupt handling, instruction tracing and access rights.

Control registers - indicates support for specific processor capabilities within Operatin system.

Cr0 - control flags, that control operating state of processor.

Cr1 - Reserved.

Cr2 - Page Fault linear address.

Cr3 - Physical address of the base of page directory. If you look into this the physical address hold 20 bits and remaining 12 bits are set as zero. if 12 bits are zero then physical address is aligned to 4K(4096) base address.

Cr4 - contains group of flags that enable and allow access to only privilege mode.

Debug registers - allow setting of break points for use in debugging programs and system software.

Segment Selector register - there are six segment selector registers CS, DS, ES, FS and GS each 16 bit size.

Memory Management regsters - GDTR(Global Descriptor Table Register), LDTR(Local Descriptor Table Register), IDTR(Interrupt Descriptor Table Register), TSS(Task State Segment). Both GDTR and IDTR comes under system table register, hold 48bit in which 32bit Linear base address and 16bit Table limits. 
Where us Task register and LDTR hold 64bit in which 16bit segment selector, 32 bit base address, 16 bit segment limits.
When task switch occurs, TSS is automatically loaded with segment selector and descriptor for TSS.

Model specific registers - group of registers primarily to operating system or executive producers.

Why we need all the above thing to understand memory management?

Let start with system boot

we know that CPU system cannot boot by it own. So how actually a system start when we click the power button. When power ON CPU enter into real mode. i.e it is compatible to lower version 8086. Therefore it can address only 16 bit address. CS register hold 0xFFFF and EIP points to 0x0. If there is no default code to execute the system crashes.

Since it can address only 16bit the BIOS code is kept low like 8KB in size and stored in ROM(Flash). So that every time the system start BIOS code get executed.

BIOS puts interrupt vector table at beginning which is a size of 1KB = 256 x each 4 bytes. When you compiled the code you will notice some segment like code, data, stack, heap. whereas code and data are created during compile time and remaining get created while running. Now for the things to get loaded there will be linker scripts which will provide information about that. BIOS data memory get loaded into memory next to it. After that interrupt service routine get loaded.i.e from 0xE05B to 0xFFFE.
First BIOS will load bootsec into the memory. where us bootsec load the remaining sector into memory.

Where is actually bootsec is present? bootsec it present in first sector of floppy disk or hard disk. Which can be modified in the boot screen. BIOS load the bootsector at 0x7C00. In real mode the maximum memory it can address is 1MB(0x00000 ~ 0xFFFFF).

After bootsec loading the OS it need to do the following functionalities,
1. enabling 32 bit addressing control
2. enabling the protected mode.
3. establishing interrupt service mechanism.
4. conducting issues about protected mode.
5. building memory paging mechanism.
6. preparing for main function.

disable interrupt EFLAG - copy core program to 0x0000 because BIOS no longer needed and its interrupt vector too. 
OS can't run without interruption - system call, peripheral interaction, scheduling.

After loading the OS/Kernel, initial value of GDTR and IDTR need to be set. GDT is the only array that store the segment register value in the system. It is an entrance to all program. It hold 
1. total list of all process, 
2. storing every task LDT address and TSS for segment addressing, 
3. site protection and 
4. recovery.

Program need entrance of GDT when using segment descriptor through segment register.

IDT - entrance for all interrupt service routine.
Is there any difference between IDT and IVT?
IVT Interrupt Vector Table, it contain only address for particular service routine used only in real mode.  
IDT Interrupt Descriptor Table, it contain complex structure to handle interrupt while CPU running in protected mode.

Enabling 32 bit addressing
In real mode the CPU can address upto 0xFFFFF(1MB) when it tried to address more than that the CPU roll back to beginning of the memory.

modify/register the corresponding interrupt in interrupt vector table.

switch to protected mode by modifying the register CR0

bootsect -> setup.S -> head.S -> main

before loading main, some prerequiste need to be done which is done by head.S
1. manages the layout of kernel program in memory.
2. creating kernel paging system in the memory space.
 create page table directory
 page table
 buffer
 GDT
 IDT
 
3. The size of head.S is approximately 25KB, arch/i386/kernel/head.S

Segment selector(16 bits) is associated with each segment descriptor, software use this to point the location of segment descriptor. whether it is located in GDT or LDT, requester privilege level. remaining 13 bit is used to address whether segment descriptor is located in GDT or LDT.

processor addressable memory space - linear address
linear address space to small protected address space - segment.
to address a byte in a segment we required a different mechanism called Logical address -> segment + offset


Why we actually this many type of conversion?
Logical address hold segment selector + 32 bit offset, that map program segment assigned by compiler. It give you a protection to your that it won't affect or change the other code. Unless you understand the virtual memory concept you won't understand the need of address translation of linear to physical.

Linear address is common to both user mode and kernel mode, both linear addressing limits is 2 power 32 -1. Where as the field in corresponding descriptor hold the key difference.

another key thing is kernel is just a one execuatble code, so when ever switching happens from user to kernel mode. _KERNEL_CS_ holds the same value.

Paging - linear to physical addressing. key things for paging are page table directory, page table.
In CR0, there is a seperate field used tell whether paging is enabled or not. If it is not enabled it directly point linear address as physical address.

CR3 hold the entry of page directory.

Linear address -> Directory(31 - 22)| Table(21 -12)| Offset(11 - 0)


Address type:
user virtual address: address seen by user program not a direct physical address.

Physical address: address used by processor and memory

Bus address: address between peripheral buses and memory. IOMMU that remaps address between physical address and IO bus address.

Kernel Logical address: normal address space of the kernel. Occupy same portion of physical memory. The address are stored in void * or unsinged long.
example: memory allocated using kmalloc.

Kernel virtual address: simialr to logical address. There is no one to one mapping to physical address. example: memory allocated using vmalloc().

logical address -> __pa() -> Physical address.
logical address <- __va() <- Physical address.

Memory is splited in chunk of memory called page. each page size is 4096(PAGE_SIZE) = xxxxx000. where as "xxxxx" is a page frame number.

to be continue in Part II....