How to write your own Operating System (x86_64): Physical Memory Management
Πως να γράψετε το δικό σας Λειτουργικό Σύστημα (x86_64): Διαχείρηση φυσικής μνήμης
IntroductionΕισαγωγή
In our previous articles, we showed how to implement a bootloader, how to enter the long mode, how to deal with interrupts and how to implement multitasking. In this article, we will see how we manage physical memory. Before we can allocate memory we need a way to track the available physical memory. Initially, we can get -during the booting- the usable and reserved memory ranges from BIOS. Then we have to use a system to mark the memory areas we allocated. The two most common methods are the frame bitmap system which is relatively simple and the buddy system which is more complex. Here, we will implement the bitmap method where each bit represents the status (used or free) of a single physical frame (we set the frame size equal to 4096 bytes).
Σε προηγούμενα άρθρα μας, είδαμε πώς να υλοποιήσουμε έναν εκκινητή, πώς να μπούμε στη λειτουργία μακράς κατάστασης, πως να διαχειριστούμε τις Διακοπές και πώς να υλοποιήσουμε πολυδιεργασία (multitasking). Σε αυτό το άρθρο θα δούμε πως διαχειριζόμαστε τη φυσική μνήμη. Πριν μπορέσουμε να δεσμεύσουμε μνήμη, χρειαζόμαστε έναν τρόπο να παρακολουθούμε τη διαθέσιμη φυσική μνήμη. Αρχικά, μπορούμε -κατά την εκκίνηση- να λάβουμε τις χρησιμοποιήσιμες και δεσμευμένες περιοχές μνήμης από το BIOS. Έπειτα, θα πρέπει να χρησιμοποιήσουμε ένα σύστημα για να σημειώνουμε τις περιοχές μνήμης που δεσμεύουμε. Οι δύο πιο συνηθισμένες μέθοδοι είναι το σύστημα δυαδικού χάρτη (bitmap) πλαισίων που ειναι σχετικά απλό και το σύστημα συνεταίρων (buddy) που είναι πιο σύνθετο. Εδώ, θα υλοποιήσουμε τη μέθοδο δυαδικού χάρτη, όπου κάθε δυαδικό ψηφίο (bit) αντιπροσωπεύει την κατάσταση (χρησιμοποιημένο ή ελεύθερο) ενός πλαισίου φυσικής μνήμης (ορίζουμε το μέγεθος πλαισίου ίσο με 4096 bytes).
CodeΚώδικας
stage2/e280_mapping.asm
The E820 map is a memory map that can be provided by a computer’s BIOS to the operating system during boot. Each E820 entry describes a region of physical memory, including its starting address, size, and type (1 => usable RAM, not 1 => reserved space). Operating systems use this map to understand which parts of memory are safe to use and which are reserved for other purposes, ensuring correct and efficient memory management. To get the E820 memory map, we call BIOS interrupt INT 0x15 with EAX = 0xE820 (thus the name), passing a buffer in ES:DI, its size in ECX and setting EDX = 'SMAP'. The BIOS returns only a single memory range entry per call, and we should repeat the call until we get all the entries. This is typically done in real mode during early boot, before switching to the long mode. For this reason, we have added this call early in our stage2/bootstage2.asm.
Ο χάρτης E820 είναι ένας χάρτης μνήμης που μπορεί να δοθεί από το BIOS του υπολογιστή στο λειτουργικό σύστημα κατά την εκκίνηση. Κάθε καταχώρηση του E820 περιγράφει μια περιοχή της φυσικής μνήμης, συμπεριλαμβανομένης της αρχικής της διεύθυνσης, του μεγέθους της και του τύπου της (1 => χρησιμοποιήσιμη RAM, οτιδήποτε άλλο => δεσμευμένος χώρος). Τα λειτουργικά συστήματα χρησιμοποιούν αυτόν τον χάρτη για να καταλάβουν ποια τμήματα της μνήμης είναι ασφαλή για χρήση και ποια είναι δεσμευμένα για άλλους σκοπούς, εξασφαλίζοντας τη σωστή και απρόσκοπτη διαχείριση της μνήμης. Για να πάρουμε τον χάρτη μνήμης E820, καλούμε τη διακοπή BIOS INT 0x15 με EAX = 0xE820 (εξ ου και το όνομα), περνώντας τη διεύθυνση της περιοχής αποθήκευσης στους ES:DI, το μέγεθός της στον ECX και θέτοντας EDX = 'SMAP'. Το BIOS επιστρέφει μόνο μία καταχώρηση περιοχής μνήμης ανά κλήση, και θα πρέπει να επαναλαμβάνουμε την κλήση μέχρι να πάρουμε όλες τις καταχωρήσεις. Αυτό συνήθως γίνεται σε λειτουργία πραγματικής κατάστασης (real mode) κατά το αρχικό στάδιο εκκίνησης, πριν τη μετάβαση σε λειτουργία μακράς κατάστασης (long mode). Για αυτό το λόγο, προσθέσαμε αυτή την κλήση στο αρχικό μέρος του αρχείου μας stage2/bootstage2.asm.
BITS 16
;---Initialized data------------------------------------------------------------
e820_mmap_entries db 0
e820_mmap_buffer: times 128*20 db 0 ; Allocate space for 128 E820 map entries.
;---Code------------------------------------------------------------------------
Get_E820_map:
;******************************************************************************;
; Prepare paging ;
;------------------------------------------------------------------------------;
; Rerurns: ;
; bx = number of entries (Each entry is 20 bytes) ;
; es:di = start of array (you decide where) ;
;******************************************************************************;
pusha ; Store registers
push es
xor ebx, ebx ; ebx = 0 (continuation value / entry counter)
mov di, e820_mmap_buffer ; es:di = destination buffer
xor ax, ax
mov es, ax ; es = 0 (buffer below 1MB).
.next_entry:
mov eax, 0xE820 ; eax = 0xE820
mov edx, 0x534D4150 ; edx = 'SMAP'
mov ecx, 20 ; ecx = size of buffer (at least 20)
mov [abs e820_mmap_entries], ebx ; Store number of entries
int 0x15 ; Call BIOS interrupt 15
jc .done ; CF=1 => Unsupported function (or error or end)
cmp eax, 0x534D4150 ; On success, eax must have been reset to "SMAP"
jne .done
test ebx, ebx ; ebx = 0 => List is only 1 entry (worthless)
je .done
add di, 20 ; Next buffer slot
cmp ebx, 128 ; Limit to 128 entries
jae .done
jmp .next_entry
.done:
pop es
popa ; Restore registers
retkernel/pma.asm
Here we have a function (PMA_init) that initialize the Physical Memory Allocator (PMA) based on the E820 map. First, we mark the entire bitmap as USED (for safety). Then we mark usable regions (from E820) as FREE. Finally, we mark as USED the memory we want to be reserved for the stack and the memory occupied by the kernel, the paging tables and by the tracking structure itself (i.e. the bitmap). Moreover, we provide functions to allocate (PMA_alloc_frame) and free (PMA_free_frame) frames. These functions are the backbone of our PMA, allowing the rest of the kernel (like the virtual memory manager and/or the heap memory manager) to request and release physical memory.
Εδώ έχουμε μια συνάρτηση (PMA_init) που αρχικοποιεί τον Physical Memory Allocator (PMA) με βάση τον χάρτη E820. Πρώτα από όλα, σημειώνουμε ολόκληρο τον δυαδικό χάρτη (bitmap) ως ΧΡΗΣΙΜΟΠΟΙΗΜΕΝΟ (για λόγους ασφάλειας). Έπειτα, σημειώνουμε ως ΕΛΕΥΘΕΡΕΣ τις αξιοποιήσιμες περιοχές (από τον E820). Τέλος, σημειώνουμε ως ΧΡΗΣΙΜΟΠΟΙΗΜΕΝΗ τη μνήμη που θέλουμε να δεσμευτεί για τη στοίβα και τη μνήμη που καταλαμβάνει ο πυρήνας, οι πίνακες σελιδοποίησης και ο ίδιος ο δυαδικός χάρτης (bitmap). Επιπλέον, παρέχουμε συναρτήσεις για δέσμευση (PMA_alloc_frame) και αποδέσμευση (PMA_free_frame) πλαισίων. Αυτές οι συναρτήσεις αποτελούν τον βασικό μηχανισμό του PMA, που επιτρέπει στο υπόλοιπο τμήμα του πυρήνα (όπως ο διαχειριστής εικονικής μνήμης ή/και ο διαχειριστής μνήμης σωρού) να ζητάει και να απελευθερώνει φυσική μνήμη.
BITS 64
;---Constants-------------------------------------------------------------------
FRAME_FACTOR equ 12 ; Used in fast shift operations
FRAME_SIZE equ (1 << FRAME_FACTOR) ; Frame size = 4096
;---Initialized data------------------------------------------------------------
PMA_bitmap_address dq 0x100000 ; Physical address of the bitmap (default at 1MB)
PMA_max_frames dq 0
PMA_bitmap_size_bytes dq 0
PMA_highest_address dq 0
;---Code------------------------------------------------------------------------
PMA_init:
;******************************************************************************;
; Initializes the bitmap-based Physical Memory Allocator (PMA). ;
;******************************************************************************;
push rax
push rbx
push rcx
push rsi
push rdi
push r14
; --- PHASE 1: Determine highest address and bitmap size ---
xor r14, r14 ; r14 = 0 (will save the highest address)
mov rcx, [abs e820_mmap_entries] ; rcx = number of entries (loop counter)
mov rsi, e820_mmap_buffer ; rsi = E820 map address
.find_max_loop:
mov rax, [rsi] ; Read current E820 entry base address
mov rbx, [rsi + 8] ; Read current E820 entry length
cmp dword [rsi + 16], 1 ; Check if this is usable RAM (Type 1)
jne .next_entry ; If not, move to next entry
add rax, rbx ; rax = end address (base + length)
cmp rax, r14 ; Is current end address (rax) higher?
jle .next_entry ; If not, move to next entry
mov r14, rax ; if yes, update highest address (r14)
.next_entry:
add rsi, 20 ; Move to next E820 entry (20 bytes)
loop .find_max_loop
mov rax, r14 ; r14 = highest physical address + 1
sub rax, 1 ; rax = highest physical address
mov [abs PMA_highest_address], rax ; Store highest physical address
cmp rax, 0x100000 ; Check if we have more than 1MB memory
jg .RAM_is_greater_than_1MB ; If not...
mov qword [abs PMA_bitmap_address], 0x20000 ; Move PMA_bitmap_address lower
.RAM_is_greater_than_1MB:
shr rax, FRAME_FACTOR ; Max frame index = address / FRAME_SIZE
inc rax ; rax = Total number of frames
mov [abs PMA_max_frames], rax ; Store total number of frames
; Calculate bitmap size in bytes: rax = (Max Frames + 7) / 8
add rax, 7
shr rax, 3
mov [abs PMA_bitmap_size_bytes], rax ; Store bitmap size
; --- PHASE 2: Initialize bitmap and mark everything as USED (1) ---
mov rdi, [abs PMA_bitmap_address] ; Destination address (Bitmap start)
mov rcx, [abs PMA_bitmap_size_bytes] ; Byte count
shr rcx, 3
mov rax, 0xFFFFFFFFFFFFFFFF ; Value to fill (all 1s = USED)
rep stosq ; Fill bitmap with 1
; --- PHASE 3: Mark USABLE regions as FREE (0) ---
mov rcx, [abs e820_mmap_entries] ; rcx = entry count (loop counter)
mov rsi, e820_mmap_buffer ; rsi = E820 map address
mov r10, 0 ; r10 = 0 (set frame as free)
.mark_free_loop:
cmp dword [rsi + 16], 1 ; Check if entry is USABLE RAM (Type 1)
jne .next_entry_mark ; If not, move to next entry
mov rdi, [rsi] ; rdi = E820 entry base address
mov rdx, [rsi + 8] ; rdx = E820 entry length
call PMA_mark_range ; Call to mark this range as FREE
.next_entry_mark:
add rsi, 20 ; Move to next E820 entry (20 bytes)
loop .mark_free_loop
; --- PHASE 4: Mark RESERVED regions (Kernel, Bitmap, I/O) as USED (1) ---
mov r10, 1 ; r10 = 1 (set frames as USED)
; 1. Mark the STACK as USED (Start=0x0, Length=0x7c00)
mov rdi, 0x0
mov rdx, Stage1_entrypoint ; rdx = stack base
call PMA_mark_range
; 2. Mark KERNEL code/data as USED
mov rdi, kernel_start
mov rdx, kernel_end
sub rdx, rdi ; rdx = kernel size
call PMA_mark_range
; 3. Mark PAGING TABLES as USED
mov rdi, PAGING_DATA
mov rdx, 4 * 4096
call PMA_mark_range
; 4. Mark BITMAP Storage as USED
mov rdi, [abs PMA_bitmap_address]
mov rdx, [abs PMA_bitmap_size_bytes]
call PMA_mark_range
pop r14
pop rdi
pop rsi
pop rcx
pop rbx
pop rax
ret
PMA_mark_range:
;******************************************************************************;
; Marks a contiguous physical memory range as USED (set bits to 1). ;
;******************************************************************************;
; rdi: Start Address ;
; rdx: Length (in bytes) ;
; r10: 0 (FREE) or 1 (USED) ;
;******************************************************************************;
push rax
push rbx
push rcx
push rdx
push rsi
push rdi
test rdx, rdx ; Check if length is zero
jz .done
; Calculate start frame index (address / FRAME_SIZE)
mov rsi, rdi ; rsi = start address
shr rsi, FRAME_FACTOR ; rsi = start frame index
; Calculate end address and end frame index
lea rbx, [rdi + rdx - 1] ; rbx = end address (last byte of range)
shr rbx, FRAME_FACTOR ; rbx = end frame index
mov rax, rsi ; rax = start frame index
.slow_mark_bits:
call PMA_mark_frame ; Mark current frame (rax=frame index, r10=0/1)
inc rax ; Next frame index
cmp rax, rbx ; Did we reach the end?
ja .done
test rax, 7 ; Is frame index divisible by 8?
jz .fast_mark_bytes ; If yes, start of a byte reached, go for speed
jmp .slow_mark_bits
.fast_mark_bytes:
mov rcx, rbx
sub rcx, rax
inc rcx ; rcx = rbx - rax + 1 = number of remaining frames
shr rcx, 3 ; rcx = rcx / 8 = number of bytes to fill
test rcx, rcx ; If rcx is 0, no whole bytes remain, go to trail bits
jz .trail_bits
call PMA_fast_mark_using_bytes
shl rcx, 3
add rax, rcx ; rax = rax + rcx * 8 = next frame index to process
.trail_bits:
jmp .slow_mark_bits ; Jump to mark loop
.done:
pop rdi
pop rsi
pop rdx
pop rcx
pop rbx
pop rax
ret
PMA_fast_mark_using_bytes:
;******************************************************************************;
; Marks very fast a series of frames (it should be byte-aligned) ;
;******************************************************************************;
; rax: Start frame index ;
; rcx: Number of frames ;
; r10: 0 (FREE) or 1 (USED) ;
;******************************************************************************;
push rax
push rcx
push rdi
mov rdi, [abs PMA_bitmap_address]
shr rax, 3
add rdi, rax ; rdi = bitmap base + (frame index / 8)
xor rax, rax ; rax = 0
test r10, r10 ; Check r10 to decide the AL fill value
jz .set_free
mov al, 0xFF ; Value to fill (all 1s = USED)
.set_free:
rep stosb ; Fill bitmap with al value (0xFF for USED, 0x00 for FREE)
pop rdi
pop rcx
pop rax
ret
PMA_mark_frame:
;******************************************************************************;
; Marks a frame as FREE (0) or USED (1). ;
;******************************************************************************;
; rax: Frame index ;
; r10: 0 (FREE) or 1 (USED) ;
;******************************************************************************;
push rax
push rcx
push rdx
mov rcx, rax ; rcx = rax = frame index
shr rax, 3 ; Byte offset = frame_index / 8
and cl, 7 ; Bit position = frame_index % 8
mov dl, 1
shl dl, cl ; dl = 1 << bit_position
mov rcx, [abs PMA_bitmap_address]
test r10, r10 ; Check r10: 0 -> Mark FREE, 1 -> Mark USED
jz .unset
or byte [rcx + rax], dl ; Set bit (Mark USED)
jmp .done
.unset:
not dl ; dl = ~(1 << bit_position)
and byte [rcx + rax], dl ; Clear bit (Mark Free)
.done:
pop rdx
pop rcx
pop rax
ret
PMA_alloc_frame:
;******************************************************************************;
; Allocates a single physical memory frame. ;
;------------------------------------------------------------------------------;
; Returns: rax = Physical Address of the free frame, or 0 if failure. ;
;******************************************************************************;
push rbx
push rcx
push rdx
push rsi
push rdi
push r10
mov rcx, [abs PMA_bitmap_size_bytes] ; rcx = total bytes in bitmap
mov rsi, [abs PMA_bitmap_address] ; rsx = bitmap base address
xor rbx, rbx ; rbx = 0 (Current byte offset)
.search_byte_loop:
cmp rbx, rcx ; Did we reach the end?
jae .fail_alloc ; If yes, we failed to alloc a frame
mov al, [rsi + rbx] ; Load a byte from bitmap
cmp al, 0xFF ; Are all bits 1 (frames USED)?
je .next_byte ; If yes, move to next byte
; Found byte with free bits
movzx rax, al ; Zero-extend byte to qword
not rax ; Invert: free bits become 1
bsf rax, rax ; Find first free bit position (0-7)
; Calculate frame index: rdi = (byte_offset * 8) + bit_position
mov rdi, rbx
shl rdi, 3 ; byte_offset * 8
add rdi, rax ; + bit_position = frame index
; Mark frame as used
mov rax, rdi ; rdi = Frame index
mov r10, 1 ; r10 = 1 (mark frame as USED)
call PMA_mark_frame
; Calculate physical address: rax = frame index * FRAME_SIZE
mov rax, rdi
shl rax, FRAME_FACTOR ; rax = physical address
jmp .done_alloc
.next_byte:
inc rbx
jmp .search_byte_loop
.fail_alloc:
xor rax, rax ; rax = 0 (we failed to allocate a frame).
.done_alloc:
pop r10
pop rdi
pop rsi
pop rdx
pop rcx
pop rbx
ret
PMA_free_frame:
;******************************************************************************;
; Allocates a single physical memory frame. ;
;------------------------------------------------------------------------------;
; rdi = Physical Address of the frame to free ;
;******************************************************************************;
test rdi, rdi
jz .done
push rax
push r10
mov r10, 0 ; r10 = 0 (set frame as FREE)
mov rax, rdi
shr rax, FRAME_FACTOR
call PMA_mark_frame
pop r10
pop rax
.done:
retkernel/kernel.asm
In our main kernel.asm file we have added code that demonstrate the functionality of our Physical Memory Allocator. On top of that, we have implemented in our debug.asm file, functions that visualize the E280 map (Print_E280_memory_map) and the frame bitmap (Print_PMA_frame_bitmap).
Στο κύριο αρχείο kernel.asm έχουμε προσθέσει κώδικα που επιδεικνύει τη λειτουργικότητα του Physical Memory Allocator. Επιπλέον, έχουμε υλοποιήσει στο αρχείο debug.asm συναρτήσεις που οπτικοποιούν τον χάρτη E280 (Print_E280_memory_map) και τον δυαδικό χάρτη (Print_PMA_frame_bitmap).
...
; Print the E280 memory mapping entries.
mov ah, (VGA_COLOR_BLUE << 4) | VGA_COLOR_WHITE
mov r8, 1 ; x = 1
mov r9, 1 ; y = 1
call Print_E280_memory_map
; Initialize the Physical Memory Allocator (PMA).
call PMA_init
; Print PMA info
mov ah, (VGA_COLOR_BLACK << 4) | VGA_COLOR_WHITE
mov r8, 1 ; x = 1
mov r9, 11 ; y = 11
call Print_PMA_info
...
; Task 2: We set r10 to 0 and we increase it by one in a loop.
Task2:
; Print Task 2 header
mov ah, (VGA_COLOR_BROWN << 4) | VGA_COLOR_WHITE
mov r8, 49 ; x = 40
mov r9, 6 ; y = 6
mov rsi, task2_header
Call Print
mov r8, 49 ; x = 49
mov r9, 7 ; y = 7
mov r10, 0
.loop:
; Allocate a PMA frame
push rax
Call PMA_alloc_frame
mov rdi, rax ; rdi = rax = address of allocated frame
pop rax
; Increase and print number of ticks
inc r10
Call Print_hex
; Release the PMA frame
call PMA_free_frame
jmp Task2.loop
... Running our codeΕκτέλεση του κώδικά μας
We can test our code very easily using an emulator like QEMU:
Μπορούμε να δοκιμάσουμε τον κώδικά μας πολύ εύκολα, χρησιμοποιώντας έναν εξομοιωτή όπως ο QEMU:
$ make
$ qemu-system-x86_64 -m 2M -drive format=raw,file=os.bin
When you run it, you will notice that two of the frames are allocated dynamically and freed constantly (one is for task 2 and the other is for task 3)
Όταν τον τρέξετε, θα παρατηρήσετε ότι δύο από τα πλαίσια δεσμεύονται δυναμικά και αποδεσμεύονται συνεχώς (το ένα αφορά το task 2 και το άλλο αφορά το task 3).
Full codeΠλήρης κώδικας
You can download the full code from here: code
Μπορείτε να κατεβάσετε τον πλήρη κώδικα απο εδώ: κώδικας