A Step-by-Step Guide to Creating Your Own ARM Operating System

1
┌───────────────────────────────────────────────────┐
2
│ EL3: Secure Monitor                               │ Highest Privilege
3
│     (Secure world management, trusted firmware)   │
4
├───────────────────────────────────────────────────┤
5
│ EL2: Hypervisor                                   │
6
│     (Virtual machine management)                  │
7
├───────────────────────────────────────────────────┤
8
│ EL1: OS Kernel                                    │ ← MeringueOS runs here
9
│     (Privileged operations, hardware access)      │
10
├───────────────────────────────────────────────────┤
11
│ EL0: Applications                                 │ Lowest Privilege
12
│    (Unprivileged code, restricted hardware access)│
13
└───────────────────────────────────────────────────┘

1
MeringueOS/
2
├── build/        # Compiled object files and binaries
3
├── src/
4
│   ├── boot/     # Boot code and kernel entry
5
│   ├── exceptions/ # Exception handling
6
│   ├── include/  # Header files
7
│   ├── lib/      # Standard library implementations
8
│   ├── memory/   # Memory management
9
│   ├── shell/    # Shell interface
10
│   └── ui/       # Text User Interface (TUI)
11
└── test/         # Test files

1
# Arm-OS Makefile
2
# Target architecture
3
ARCH = aarch64
4

5
# Cross compiler settings
6
# Note: On macOS or some systems, you may need to use aarch64-elf- instead
7
CROSS_COMPILE = aarch64-linux-gnu-
8
CC = $(CROSS_COMPILE)gcc
9
AS = $(CROSS_COMPILE)as
10
LD = $(CROSS_COMPILE)ld
11
OBJCOPY = $(CROSS_COMPILE)objcopy
12
OBJDUMP = $(CROSS_COMPILE)objdump
13

14
# Compiler flags
15
CFLAGS = -Wall -Wextra -ffreestanding -nostdlib -nostartfiles -mcpu=cortex-a72 -I./src/include
16
ASFLAGS = -mcpu=cortex-a72
17
LDFLAGS = -nostdlib
18

19
# Source directories
20
SRC_DIR = src
21
BOOT_DIR = $(SRC_DIR)/boot
22
MEMORY_DIR = $(SRC_DIR)/memory
23
EXCEPTIONS_DIR = $(SRC_DIR)/exceptions
24
UI_DIR = $(SRC_DIR)/ui
25
LIB_DIR = $(SRC_DIR)/lib
26
SHELL_DIR = $(SRC_DIR)/shell
27
INCLUDE_DIR = $(SRC_DIR)/include
28

29
# Build directories
30
BUILD_DIR = build
31
OBJ_DIR = $(BUILD_DIR)/obj
32

33
# Source files
34
ASM_SRCS = $(wildcard $(BOOT_DIR)/*.S) $(wildcard $(EXCEPTIONS_DIR)/*.S)
35
C_SRCS = $(wildcard $(BOOT_DIR)/*.c) \
36
    $(wildcard $(MEMORY_DIR)/*.c) \
37
    $(wildcard $(EXCEPTIONS_DIR)/*.c) \
38
    $(wildcard $(UI_DIR)/*.c) \
39
    $(wildcard $(LIB_DIR)/*.c) \
40
    $(wildcard $(SHELL_DIR)/*.c)
41

42
# Object files
43
ASM_OBJS = $(patsubst $(SRC_DIR)/%.S, $(OBJ_DIR)/%.o, $(ASM_SRCS))
44
C_OBJS = $(patsubst $(SRC_DIR)/%.c, $(OBJ_DIR)/%.o, $(C_SRCS))
45
OBJS = $(ASM_OBJS) $(C_OBJS)
46

47
# Output files
48
KERNEL = $(BUILD_DIR)/kernel8.elf
49
KERNEL_IMG = $(BUILD_DIR)/kernel8.img
50

51
# Targets
52
.PHONY: all clean qemu debug
53

54
all: $(KERNEL_IMG)
55

56
$(KERNEL_IMG): $(KERNEL)
57
  $(OBJCOPY) -O binary $< $@
58

59
$(KERNEL): $(OBJS) src/linker.ld | $(BUILD_DIR)
60
  $(LD) $(LDFLAGS) -T src/linker.ld -o $@ $(OBJS)
61

62
$(OBJ_DIR)/%.o: $(SRC_DIR)/%.c | $(OBJ_DIR)
63
  @mkdir -p $(dir $@)
64
  $(CC) $(CFLAGS) -c $< -o $@
65

66
$(OBJ_DIR)/%.o: $(SRC_DIR)/%.S | $(OBJ_DIR)
67
  @mkdir -p $(dir $@)
68
  $(AS) $(ASFLAGS) -c $< -o $@
69

70
$(BUILD_DIR) $(OBJ_DIR):
71
  mkdir -p $@
72
  mkdir -p $(OBJ_DIR)/boot
73
  mkdir -p $(OBJ_DIR)/memory
74
  mkdir -p $(OBJ_DIR)/exceptions
75
  mkdir -p $(OBJ_DIR)/ui
76
  mkdir -p $(OBJ_DIR)/lib
77
  mkdir -p $(OBJ_DIR)/shell
78

79
qemu: $(KERNEL_IMG)
80
  qemu-system-aarch64 -M virt -cpu cortex-a72 -m 128M -nographic -kernel $(KERNEL_IMG)
81

82
debug: $(KERNEL_IMG)
83
  qemu-system-aarch64 -M virt -cpu cortex-a72 -m 128M -nographic -kernel $(KERNEL_IMG) -S -s
84

85
clean:
86
  rm -rf $(BUILD_DIR)

1
# Cross compiler settings for macOS
2
CROSS_COMPILE = aarch64-elf-

1
# Cross compiler settings for Linux
2
CROSS_COMPILE = aarch64-linux-gnu-

1
// Add to src/include/lib/string.h
2
char* strtok(char *str, const char *delim);
3
size_t strspn(const char *s, const char *accept);
4
char* strpbrk(const char *s, const char *reject);
5

6
// Add to src/include/lib/stdio.h
7
char kgetc(void);
8
char kgetc_blocking(void);

1
$(KERNEL): $(OBJS) src/linker.ld | $(BUILD_DIR)
2
  $(LD) $(LDFLAGS) -T src/linker.ld -o $@ $(OBJS)

1
void cmd_help(int argc, char **argv) {
2
    (void)argc; (void)argv; // Suppress unused warnings
3
    kprintf("Available commands:\n");
4
    // ... rest of function
5
}

1
┌───────────────────────────────────────────────────────────────┐
2
│                      MeringueOS Kernel                        │
3
│                                                               │
4
│  ┌─────────────┐  ┌─────────────┐  ┌──────────────────────┐   │
5
│  │ Boot        │  │ Memory      │  │ Exception Handling   │   │
6
│  │ Sequence    │──▶ Management  │──▶ (Vector Table)       │   │
7
│  └─────────────┘  └─────────────┘  └──────────────────────┘   │
8
│          │                 ▲                   │              │
9
│          │                 │                   │              │
10
│          ▼                 │                   ▼              │
11
│  ┌─────────────┐  ┌─────────────┐  ┌──────────────────────┐   │
12
│  │ Kernel      │  │ Standard    │  │ UART/Console I/O     │   │
13
│  │ Heap        │◀─┤ Library     │◀─┤                      │   │
14
│  └─────────────┘  └─────────────┘  └──────────────────────┘   │
15
│          │                 ▲                  │               │
16
│          │                 │                  │               │
17
│          └────────────────┐│┌─────────────────┘               │
18
│                           │││                                 │
19
│                           ▼▼▼                                 │
20
│                    ┌─────────────┐                            │
21
│                    │ Shell       │                            │
22
│                    │ Interface   │                            │
23
│                    └─────────────┘                            │
24
└───────────────────────────────────────────────────────────────┘

1
+---------------------------------------+
2
| EL3: Secure monitor                   | Highest privilege
3
+---------------------------------------+
4
| EL2: Hypervisor                       |
5
+---------------------------------------+
6
| EL1: OS kernel                        | <- MeringueOS runs here
7
+---------------------------------------+
8
| EL0: Applications                     | Lowest privilege
9
+---------------------------------------+

1
┌─────────────┐     ┌─────────────┐     ┌─────────────┐
2
│ CPU Reset   │     │ Boot.S      │     │ Clear BSS   │
3
│ EL2 or EL3  │────▶│ Setup Stack │────▶│ Section     │
4
│ PC=Reset    │     │ Check Core  │     │             │
5
└─────────────┘     └─────────────┘     └─────────────┘
6
       │                                       │
7
       │                                       ▼
8
┌─────────────┐     ┌─────────────┐     ┌─────────────┐
9
│ Initialize  │     │ Set up      │     │ Transition  │
10
│ Subsystems  │◀─── │ Exceptions  │◀─── │ to EL1      │
11
│ Start Shell │     │ Vector Table│     │             │
12
└─────────────┘     └─────────────┘     └─────────────┘

1
/* AArch64 boot code for QEMU virt machine */
2
.section ".text.boot"
3

4
.global _start
5
_start:
6
    // Check processor ID is 0 (primary core)
7
    mrs     x0, mpidr_el1
8
    and     x0, x0, #0xFF
9
    cbz     x0, primary_core
10
    // Secondary cores loop forever
11
1:  wfe
12
    b       1b
13

14
primary_core:
15
    // Set stack pointer to _stack_top
16
    ldr     x0, =_stack_top
17
    mov     sp, x0
18

19
    // Copy .rodata section from load address to execution address
20
    ldr     x0, =_rodata_start     // Destination address
21
    ldr     x1, =_rodata_load      // Source address
22
    ldr     x2, =_rodata_end
23
    sub     x2, x2, x0             // Size to copy
24
    bl      copy_data_section
25

26
    // Copy .data section from load address to execution address
27
    ldr     x0, =_data_start       // Destination address
28
    ldr     x1, =_data_load        // Source address
29
    ldr     x2, =_data_end
30
    sub     x2, x2, x0             // Size to copy
31
    bl      copy_data_section
32

33
    // Clear BSS
34
    ldr     x0, =_bss_start
35
    ldr     x1, =_bss_end
36
    sub     x1, x1, x0
37
    cbz     x1, skip_bss_clear
38
clear_bss_loop:
39
    str     xzr, [x0], #8
40
    sub     x1, x1, #8
41
    cbnz    x1, clear_bss_loop
42
skip_bss_clear:
43

44
    // Set up exception vector table
45
    ldr     x0, =_exception_vector_table
46
    msr     vbar_el1, x0
47

48
    // Set up EL1 (kernel mode)
49
    mrs     x0, CurrentEL
50
    lsr     x0, x0, #2
51
    cmp     x0, #1
52
    beq     already_in_el1
53

54
    // If we're in EL2, configure EL1 and drop to it
55
    /* Disable EL1 timer traps */
56
    mov     x0, #0x3       // CNTHCTL_EL2.EL1PCTEN | CNTHCTL_EL2.EL1PCEN
57
    msr     cnthctl_el2, x0
58
    msr     cntvoff_el2, xzr
59

60
    /* Set EL1 execution state to AArch64 */
61
    mov     x0, #(1 << 31)      // AArch64
62
    orr     x0, x0, #(1 << 1)   // SWIO hardwired
63
    msr     hcr_el2, x0
64

65
    /* Configure EL1 */
66
    // Set up SPSR_EL2 for the transition to EL1
67
    mov     x0, #0x3c5         // DAIF + EL1h (SPSel = 1)
68
    msr     spsr_el2, x0
69

70
    /* Set EL1 entry point and switch */
71
    ldr     x0, =already_in_el1
72
    msr     elr_el2, x0
73
    eret
74

75
already_in_el1:
76
    // Enable floating point
77
    mov     x0, #0x00300000     // FPEN bits
78
    msr     cpacr_el1, x0
79
    isb
80

81
    // Jump to C code, passing boot info pointer
82
    mov     x0, #0              // For now, pass null pointer as boot info
83
    bl      kernel_main         // Call our C entry point
84

85
    // If kernel_main returns, halt the CPU
86
1:  wfe
87
    b       1b
88

89
//------------------------------------------------------------------
90
// Helper function to copy data sections
91
// x0 = destination address
92
// x1 = source address
93
// x2 = size in bytes (must be multiple of 8)
94
//------------------------------------------------------------------
95
copy_data_section:
96
    // Return immediately if source and destination are the same
97
    cmp     x0, x1
98
    beq     copy_done
99

100
    // Return if size is zero
101
    cbz     x2, copy_done
102

103
    // Add debugging output
104
    // Preserve registers used by the output routine
105
    stp     x0, x1, [sp, #-16]!
106
    stp     x2, x30, [sp, #-16]!
107

108
    // Call C debug function to print details about the copy
109
    mov     x3, x2            // Size
110
    bl      boot_debug_copy   // Call C function to print debug info
111

112
    // Restore registers
113
    ldp     x2, x30, [sp], #16
114
    ldp     x0, x1, [sp], #16
115

116
    // Perform the copy, byte by byte for safety
117
copy_byte_loop:
118
    ldrb    w4, [x1], #1     // Load a byte
119
    strb    w4, [x0], #1     // Store a byte
120
    sub     x2, x2, #1       // Decrement size
121
    cbnz    x2, copy_byte_loop
122

123
copy_done:
124
    ret

1
┌───────────────────┐      ┌───────────────────┐      ┌───────────────────┐
2
│ CPU Reset State   │      │ Initial Setup     │      │ Stack & BSS Setup │
3
│ PC = Reset Vector │─────▶│ Check Core ID     │─────▶│ Stack initialized │
4
│ EL = 2 or 3       │      │Disable secondaries│      │ BSS section zeroed│
5
└───────────────────┘      └───────────────────┘      └────────┬──────────┘
6
                                                               │
7
                                                               ▼
8
┌───────────────────┐      ┌───────────────────┐      ┌───────────────────┐
9
│ C Environment     │      │ Transition to EL1 │      │ Exception Setup   │
10
│Jump to kernel_main│◀──── │ Configure SPSRs   │◀──── │Set up vector table│
11
│ Start OS services │      │ Set return addr   │      │ Enable features   │
12
└───────────────────┘      └───────────────────┘      └───────────────────┘

1
#include <kernel.h>
2
#include <lib/stdio.h>
3

4
// External functions we'll implement later
5
extern void frame_alloc_init(const KERNEL_BOOT_PARAMS *params);
6
extern void kheap_init(void);
7
extern int tui_init(void);
8
extern void shell_loop(void);
9

10
// Debug function called from boot code before UART is initialized
11
// We need a direct hardware access version
12
static void early_debug_print(const char *str) {
13
    // UART direct access (PL011)
14
    volatile uint32_t *uart_dr = (volatile uint32_t*)0x09000000;
15
    volatile uint32_t *uart_fr = (volatile uint32_t*)0x09000018;
16

17
    while (*str) {
18
        // Wait for FIFO to have space
19
        while ((*uart_fr) & (1 << 5)); // TXFF bit
20

21
        // Send character
22
        *uart_dr = (uint32_t)*str++;
23
    }
24
}
25

26
// Debug function for section copying, called from assembly
27
void boot_debug_copy(void *dest, void *src, size_t size) {
28
    // Print directly using early UART access
29
    early_debug_print("[BOOT] Copying section: ");
30

31
    // Convert size to string manually (very simple)
32
    char size_str[16];
33
    int i = 0;
34
    int tmp = (int)size;
35

36
    // Handle special case of zero
37
    if (tmp == 0) {
38
        size_str[0] = '0';
39
        size_str[1] = '\0';
40
    } else {
41
        // Convert integer to string (backwards)
42
        while (tmp > 0) {
43
            size_str[i++] = '0' + (tmp % 10);
44
            tmp /= 10;
45
        }
46
        size_str[i] = '\0';
47

48
        // Reverse the string
49
        for (int j = 0; j < i/2; j++) {
50
            char c = size_str[j];
51
            size_str[j] = size_str[i-j-1];
52
            size_str[i-j-1] = c;
53
        }
54
    }
55

56
    early_debug_print(size_str);
57
    early_debug_print(" bytes\n");
58
}
59

60
// Kernel entry point
61
void kernel_main(KERNEL_BOOT_PARAMS *params) {
62
    // Early initialization - placeholder for UART setup
63
    // We'll assume kprintf writes to a UART for now
64

65
    kprintf("MeringueOS starting...\n");
66
    kprintf("Kernel loaded at physical address: 0x%llx\n",
67
            params ? params->kernel_phys_start : 0);
68

69
    // Debug section information
70
    kprintf("Memory Sections:\n");
71
    kprintf("  .text:   %p to %p\n", &_kernel_start, &_text_end);
72
    kprintf("  .rodata: %p to %p (load: %p)\n", &_rodata_start, &_rodata_end, &_rodata_load);
73
    kprintf("  .data:   %p to %p (load: %p)\n", &_data_start, &_data_end, &_data_load);
74
    kprintf("  .bss:    %p to %p\n", &_bss_start, &_bss_end);
75

76
    // Initialize memory management subsystem
77
    kprintf("Initializing Physical Memory Manager...\n");
78
    frame_alloc_init(params);
79

80
    kprintf("Initializing Kernel Heap Allocator...\n");
81
    kheap_init();
82

83
    // Initialize Text User Interface
84
    kprintf("Initializing TUI subsystem...\n");
85
    if (tui_init() != 0) {
86
        kprintf("Failed to initialize TUI subsystem!\n");
87
        // Continue without TUI for now
88
    }
89

90
    // Enter the shell
91
    kprintf("Starting shell...\n");
92
    shell_loop();
93

94
    // If shell returns, halt
95
    kprintf("Kernel halting.\n");
96
    while(1) {
97
        // This is equivalent to a halt
98
        asm volatile("wfi");
99
    }
100
}

1
/* Linker script for Arm-OS */
2

3
/* QEMU virt machine memory layout */
4
ENTRY(_start)
5

6
SECTIONS
7
{
8
    /* Kernel starts at 0x40100000 for QEMU virt machine */
9
    . = 0x40100000;
10
    _kernel_start = .;
11

12
    .text : ALIGN(8)
13
    {
14
        *(.text.boot)  /* Boot code first */
15
        *(.text)       /* All other code */
16
        *(.text.*)     /* Including subsections */
17
    }
18
    _text_end = .;
19

20
    .rodata : ALIGN(8)
21
    {
22
        _rodata_start = .;
23
        *(.rodata)
24
        *(.rodata.*)
25
        _rodata_end = .;
26
    }
27

28
    .data : ALIGN(8)
29
    {
30
        _data_start = .;
31
        *(.data)
32
        *(.data.*)
33
        _data_end = .;
34
    }
35

36
    /* Add symbols for load addresses (where sections are actually loaded by QEMU) */
37
    _rodata_load = LOADADDR(.rodata);
38
    _data_load = LOADADDR(.data);
39

40
    .bss : ALIGN(8)
41
    {
42
        _bss_start = .;
43
        *(.bss)
44
        *(.bss.*)
45
        *(COMMON)
46
        . = ALIGN(8);
47
        _bss_end = .;
48
    }
49

50
    .eh_frame :
51
    {
52
        *(.eh_frame)
53
    }
54

55
    . = ALIGN(8);
56

57
    /* Reserve space for the stack */
58
    . = ALIGN(16);
59
    _stack_bottom = .;
60
    . += 0x10000; /* 64 KB for stack */
61
    . = ALIGN(16);
62
    _stack_top = .;
63

64
    /* Reserve space for PMM bitmap */
65
    . = ALIGN(4096);
66
    _pmm_bitmap_start = .;
67
    . += 0x20000; /* 128 KB for PMM bitmap (can manage 4GB of RAM) */
68
    _pmm_bitmap_end = .;
69

70
    _kernel_end = .;
71
}

1
                    +-------------------+ 0x40100000
2
                    | .text (code)      |
3
                    |                   |
4
                    +-------------------+
5
                    | .rodata           |
6
                    | (constants)       |
7
                    +-------------------+
8
                    | .data             |
9
                    | (initialized vars)|
10
                    +-------------------+
11
                    | .bss              |
12
                    | (zeroed at boot)  |
13
                    +-------------------+
14
                    |                   |
15
                    | Available memory  |
16
                    |                   |
17
                    +-------------------+
18
                    | PMM bitmap        |
19
                    | (memory tracking) |
20
                    +-------------------+
21
                    | Stack (64KB)      |
22
                    | (grows downward)  |
23
       _stack_top → +-------------------+

1
#ifndef FRAME_ALLOC_H
2
#define FRAME_ALLOC_H
3

4
#include <stddef.h>
5
#include <stdint.h>
6
#include <stdbool.h>
7
#include "kernel.h"
8

9
// Define page size (typically 4KB for AArch64)
10
#define PAGE_SIZE 4096
11
#define PAGE_SHIFT 12
12

13
// Define the RAM region for QEMU virt machine
14
#define PMM_RAM_BASE 0x40000000
15

16
// Note: Linker symbols are now included from kernel.h
17

18
// Initialize the physical memory manager
19
void frame_alloc_init(const KERNEL_BOOT_PARAMS *params);
20

21
// Allocate a physical frame, returns NULL if no free frames
22
void* alloc_frame(void);
23

24
// Free a previously allocated physical frame
25
void free_frame(void *frame);
26

27
// Get information about memory
28
uint64_t pmm_get_total_memory(void);
29
uint64_t pmm_get_free_memory(void);
30
uint64_t pmm_get_highest_usable_address(void);
31

32
#endif // FRAME_ALLOC_H

1
#include <stddef.h>
2
#include <stdint.h>
3
#include <stdbool.h>
4
#include "memory/frame_alloc.h"
5
#include "lib/string.h"
6
#include "lib/stdio.h"
7

8
// For QEMU virt, RAM often starts at 0x40000000 and can be e.g., 128MB or more.
9
// Let's assume a max manageable physical address space, e.g., 1GB beyond RAM start.
10
// Adjust this based on actual QEMU configuration or dynamic detection.
11
#define PMM_MANAGEABLE_SIZE (1024ULL * 1024ULL * 1024ULL) // Manage up to 1GB
12
#define PMM_MAX_ADDRESS (PMM_RAM_BASE + PMM_MANAGEABLE_SIZE)
13
#define PMM_TOTAL_FRAMES (PMM_MANAGEABLE_SIZE / PAGE_SIZE)
14

15
// Bitmap for tracking frame usage. Each bit represents one frame.
16
// Size = Total Frames / 8 bits per byte
17
static uint8_t *frame_bitmap = &_pmm_bitmap_start;
18

19
static uint64_t total_memory = 0;
20
static uint64_t free_memory = 0;
21
static uint64_t highest_usable_address = 0;
22

23
// Helper function to set a bit in the bitmap
24
static void set_bit(size_t bit) {
25
    frame_bitmap[bit / 8] |= (1 << (bit % 8));
26
}
27

28
// Helper function to clear a bit in the bitmap
29
static void clear_bit(size_t bit) {
30
    frame_bitmap[bit / 8] &= ~(1 << (bit % 8));
31
}
32

33
// Helper function to test a bit in the bitmap
34
static bool test_bit(size_t bit) {
35
    return (frame_bitmap[bit / 8] & (1 << (bit % 8))) != 0;
36
}
37

38
// Mark a range of frames as used
39
static void mark_range_used(uint64_t base_addr, uint64_t size) {
40
    uint64_t start_frame = (base_addr >= PMM_RAM_BASE) ?
41
                          (base_addr - PMM_RAM_BASE) / PAGE_SIZE :
42
                          (UINT64_MAX);
43
    uint64_t end_addr = base_addr + size;
44
    uint64_t end_frame = (end_addr > PMM_RAM_BASE) ?
45
                        (end_addr - 1 - PMM_RAM_BASE) / PAGE_SIZE :
46
                        0;
47

48
    if (start_frame >= PMM_TOTAL_FRAMES) return; // Start address out of managed range
49
    if (end_frame >= PMM_TOTAL_FRAMES) end_frame = PMM_TOTAL_FRAMES - 1; // Cap end address
50

51
    kprintf("PMM: Marking used 0x%llx - 0x%llx (Frames %llu - %llu)\n",
52
            base_addr, base_addr + size, start_frame, end_frame);
53

54
    for (uint64_t i = start_frame; i <= end_frame; ++i) {
55
        if (!test_bit(i)) {
56
            set_bit(i);
57
            // Assuming these were initially counted as free, decrement count
58
            if (total_memory >= PAGE_SIZE) total_memory -= PAGE_SIZE;
59
            if (free_memory >= PAGE_SIZE) free_memory -= PAGE_SIZE;
60
        }
61
    }
62
}
63

64
// Mark a range of frames as free
65
static void mark_range_free(uint64_t base_addr, uint64_t size) {
66
    uint64_t start_frame = (base_addr >= PMM_RAM_BASE) ?
67
                          (base_addr - PMM_RAM_BASE) / PAGE_SIZE :
68
                          (UINT64_MAX);
69
    uint64_t end_addr = base_addr + size;
70
    uint64_t end_frame = (end_addr > PMM_RAM_BASE) ?
71
                        (end_addr - 1 - PMM_RAM_BASE) / PAGE_SIZE :
72
                        0;
73

74
    if (start_frame >= PMM_TOTAL_FRAMES) return; // Start address out of managed range
75
    if (end_frame >= PMM_TOTAL_FRAMES) end_frame = PMM_TOTAL_FRAMES - 1; // Cap end address
76

77
    kprintf("PMM: Marking free 0x%llx - 0x%llx (Frames %llu - %llu)\n",
78
            base_addr, base_addr + size, start_frame, end_frame);
79

80
    for (uint64_t i = start_frame; i <= end_frame; ++i) {
81
        if (test_bit(i)) { // Only count if it wasn't already free
82
             total_memory += PAGE_SIZE;
83
             free_memory += PAGE_SIZE;
84
             if ((PMM_RAM_BASE + (i + 1) * PAGE_SIZE) > highest_usable_address) {
85
                 highest_usable_address = PMM_RAM_BASE + (i + 1) * PAGE_SIZE;
86
             }
87
        }
88
       clear_bit(i); // Mark as free regardless
89
    }
90
}
91

92
void frame_alloc_init(const KERNEL_BOOT_PARAMS *params) {
93
    kprintf("PMM: Initializing Physical Memory Manager...\n");
94

95
    // Calculate the bitmap size
96
    size_t bitmap_size = (&_pmm_bitmap_end - &_pmm_bitmap_start);
97
    kprintf("PMM: Bitmap size: %zu bytes, located at %p\n",
98
            bitmap_size, frame_bitmap);
99

100
    // Initially, mark all manageable frames as used
101
    memset(frame_bitmap, 0xFF, bitmap_size);
102
    total_memory = 0;
103
    free_memory = 0;
104
    highest_usable_address = PMM_RAM_BASE;
105

106
    if (params) {
107
        kprintf("PMM: Kernel Physical Range: 0x%llx - 0x%llx\n",
108
                params->kernel_phys_start, params->kernel_phys_end);
109

110
        // For now, we'll simplify and just reserve the kernel address range
111
        // In a full implementation, we would parse the UEFI memory map from params
112

113
        // Mark all memory as free initially (simplified approach)
114
        mark_range_free(PMM_RAM_BASE, PMM_MANAGEABLE_SIZE);
115

116
        // Then mark kernel memory as used
117
        mark_range_used(params->kernel_phys_start,
118
                       params->kernel_phys_end - params->kernel_phys_start);
119
    } else {
120
        // No boot parameters, use linker-provided kernel boundaries
121
        uint64_t kernel_start = (uint64_t)&_kernel_start;
122
        uint64_t kernel_end = (uint64_t)&_kernel_end;
123

124
        kprintf("PMM: Kernel boundaries from linker: 0x%llx - 0x%llx\n",
125
                kernel_start, kernel_end);
126

127
        // Mark all memory as free initially
128
        mark_range_free(PMM_RAM_BASE, PMM_MANAGEABLE_SIZE);
129

130
        // Then mark kernel memory as used
131
        mark_range_used(kernel_start, kernel_end - kernel_start);
132
    }
133

134
    // Mark the bitmap itself as used (it lies within kernel memory, but just to be explicit)
135
    mark_range_used((uint64_t)frame_bitmap, bitmap_size);
136

137
    kprintf("PMM: Initialization complete. Total: %llu KB, Free: %llu KB\n",
138
            total_memory / 1024, free_memory / 1024);
139
}
140

141
void* alloc_frame(void) {
142
    // Simple linear search for first free frame
143
    for (size_t i = 0; i < PMM_TOTAL_FRAMES; i++) {
144
        if (!test_bit(i)) {
145
            set_bit(i);
146
            free_memory -= PAGE_SIZE;
147

148
            // Calculate the physical address
149
            void *frame_addr = (void*)(PMM_RAM_BASE + i * PAGE_SIZE);
150

151
            // Zero the frame for security/predictability
152
            memset(frame_addr, 0, PAGE_SIZE);
153

154
            return frame_addr;
155
        }
156
    }
157

158
    kprintf("PMM: ERROR - Out of physical frames!\n");
159
    return NULL; // No free frame found
160
}
161

162
void free_frame(void *frame) {
163
    if (!frame) return;
164

165
    uint64_t addr = (uint64_t)frame;
166

167
    // Basic validation
168
    if (addr < PMM_RAM_BASE || addr >= PMM_MAX_ADDRESS) {
169
        kprintf("PMM: Attempt to free invalid frame at %p\n", frame);
170
        return;
171
    }
172

173
    // Check alignment
174
    if (addr % PAGE_SIZE != 0) {
175
        kprintf("PMM: Attempt to free unaligned address %p\n", frame);
176
        return;
177
    }
178

179
    // Calculate the bit index
180
    size_t frame_idx = (addr - PMM_RAM_BASE) / PAGE_SIZE;
181

182
    if (frame_idx >= PMM_TOTAL_FRAMES) {
183
        kprintf("PMM: Frame index %zu out of range\n", frame_idx);
184
        return;
185
    }
186

187
    // Check if frame is currently marked as used
188
    if (!test_bit(frame_idx)) {
189
        kprintf("PMM: Warning - double free detected for frame %p\n", frame);
190
        return;
191
    }
192

193
    // Mark as free
194
    clear_bit(frame_idx);
195
    free_memory += PAGE_SIZE;
196
}
197

198
uint64_t pmm_get_total_memory(void) {
199
    return total_memory;
200
}
201

202
uint64_t pmm_get_free_memory(void) {
203
    return free_memory;
204
}
205

206
uint64_t pmm_get_highest_usable_address(void) {
207
    return highest_usable_address;
208
}

1
┌───────────────────────────────────────────────────────────────────────┐
2
│ Physical Memory (1GB Starting at 0x40000000)                          │
3
│                                                                       │
4
│ ┌─────────┐ ┌─────────┐ ┌─────────┐             ┌─────────┐           │
5
│ │ Frame 0 │ │ Frame 1 │ │ Frame 2 │    ...      │Frame N-1│           │
6
│ │ (4 KB)  │ │ (4 KB)  │ │ (4 KB)  │             │ (4 KB)  │           │
7
│ └─────────┘ └─────────┘ └─────────┘             └─────────┘           │
8
└───────────────────────────────────────────────────────────────────────┘
9
                           │
10
                           ▼
11
┌───────────────────────────────────────────────────────────────────────┐
12
│ Frame Bitmap (1 bit per frame)                                        │
13
│                                                                       │
14
│ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┐                                 │
15
│ │ 1 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │...│ (1=used, 0=free)                │
16
│ └───┴───┴───┴───┴───┴───┴───┴───┴───┘                                 │
17
│                                                                       │
18
└───────────────────────────────────────────────────────────────────────┘

1
#ifndef KHEAP_H
2
#define KHEAP_H
3

4
#include <stddef.h>
5
#include <stdint.h>
6

7
// Initialize the kernel heap
8
void kheap_init(void);
9

10
// Allocate a block of memory
11
void *kmalloc(size_t size);
12

13
// Free a previously allocated block
14
void kfree(void *ptr);
15

16
#endif // KHEAP_H

1
#include <stddef.h>
2
#include <stdint.h>
3
#include <stdbool.h>
4
#include "memory/kheap.h"
5
#include "memory/frame_alloc.h"
6
#include "lib/string.h"
7
#include "lib/stdio.h"
8

9
// Header for memory blocks (both allocated and free)
10
typedef struct heap_block {
11
    size_t size;          // Size of the data area *excluding* this header
12
    bool is_free;         // True if block is free, false if allocated
13
    struct heap_block *next; // Pointer to the next block in the heap (physical order)
14
    struct heap_block *prev; // Pointer to the previous block in the heap (physical order)
15
    struct heap_block *next_free; // Pointer to the next free block in the free list
16
    struct heap_block *prev_free; // Pointer to the previous free block in the free list
17
} heap_block_t;
18

19
#define HEAP_HEADER_SIZE sizeof(heap_block_t)
20
#define HEAP_MIN_BLOCK_SIZE (HEAP_HEADER_SIZE * 2) // Minimum size to allow splitting
21

22
// Head of the free list (doubly linked)
23
static heap_block_t *free_list_head = NULL;
24
static heap_block_t *heap_start = NULL;
25
static heap_block_t *heap_end = NULL;
26

27
// --- Free List Management ---
28

29
static void add_to_free_list(heap_block_t *block) {
30
    block->is_free = true;
31
    block->next_free = free_list_head;
32
    block->prev_free = NULL;
33
    if (free_list_head) {
34
        free_list_head->prev_free = block;
35
    }
36
    free_list_head = block;
37
}
38

39
static void remove_from_free_list(heap_block_t *block) {
40
    if (block->prev_free) {
41
        block->prev_free->next_free = block->next_free;
42
    } else {
43
        free_list_head = block->next_free; // It was the head
44
    }
45
    if (block->next_free) {
46
        block->next_free->prev_free = block->prev_free;
47
    }
48
    block->is_free = false; // Mark as not free after removal
49
    block->next_free = NULL;
50
    block->prev_free = NULL;
51
}
52

53
// --- Heap Expansion ---
54

55
static bool expand_heap(size_t min_expand_size) {
56
    // Request at least a page, or more if needed
57
    size_t pages_needed = (min_expand_size + HEAP_HEADER_SIZE + PAGE_SIZE - 1) / PAGE_SIZE;
58
    if (pages_needed == 0) pages_needed = 1;
59

60
    kprintf("KHeap: Expanding heap by %zu pages\n", pages_needed);
61

62
    heap_block_t *new_block = NULL;
63
    for (size_t i = 0; i < pages_needed; ++i) {
64
        void *frame = alloc_frame();
65
        if (!frame) {
66
            kprintf("KHeap Error: Failed to allocate frame during expansion!\n");
67
            // If we allocated some frames but not all, we should ideally free them
68
            // or add what we got. For simplicity here, we fail.
69
            return false;
70
        }
71

72
        heap_block_t *current_block = (heap_block_t *)frame;
73
        current_block->size = PAGE_SIZE - HEAP_HEADER_SIZE;
74
        current_block->is_free = true;
75
        current_block->next = NULL; // Will be linked below or by coalesce
76

77
        if (!new_block) {
78
            new_block = current_block; // Keep track of the first new block
79
        }
80

81
        // Link the new block into the main heap structure
82
        if (heap_end) {
83
            current_block->prev = heap_end;
84
            heap_end->next = current_block;
85
        } else {
86
            // This is the very first block in the heap
87
            heap_start = current_block;
88
            current_block->prev = NULL;
89
        }
90
        heap_end = current_block;
91
    }
92

93
    if (!new_block) return false; // Should not happen if alloc_frame succeeded
94

95
    // Coalesce the first new block with the previous block if it was free
96
    if (new_block->prev && new_block->prev->is_free) {
97
        heap_block_t *prev_block = new_block->prev;
98
        remove_from_free_list(prev_block); // Remove old free block
99
        prev_block->size += new_block->size + HEAP_HEADER_SIZE;
100
        prev_block->next = new_block->next;
101
        if (new_block->next) {
102
            new_block->next->prev = prev_block;
103
        }
104
        if (heap_end == new_block) {
105
             heap_end = prev_block;
106
        }
107
        new_block = prev_block; // The merged block is now the 'new' block to add
108
    }
109

110
    // Add the (potentially merged) new block to the free list
111
    add_to_free_list(new_block);
112

113
    return true;
114
}
115

116
// --- Coalescing ---
117

118
static heap_block_t* coalesce(heap_block_t *block) {
119
    if (!block || !block->is_free) return block;
120

121
    heap_block_t *current = block;
122

123
    // Coalesce with next block if it's free
124
    if (current->next && current->next->is_free) {
125
        heap_block_t *next_block = current->next;
126
        kprintf("KHeap: Coalescing forward %p (%zu) with %p (%zu)\n",
127
                current, current->size, next_block, next_block->size);
128
        remove_from_free_list(next_block); // Remove next block from free list
129
        current->size += next_block->size + HEAP_HEADER_SIZE;
130
        current->next = next_block->next;
131
        if (current->next) {
132
            current->next->prev = current;
133
        }
134
        if (heap_end == next_block) {
135
            heap_end = current;
136
        }
137
        // next_block is now merged into current, clear it for safety
138
        memset(next_block, 0, HEAP_HEADER_SIZE);
139
    }
140

141
    // Coalesce with previous block if it's free
142
    if (current->prev && current->prev->is_free) {
143
        heap_block_t *prev_block = current->prev;
144
        kprintf("KHeap: Coalescing backward %p (%zu) with %p (%zu)\n",
145
                prev_block, prev_block->size, current, current->size);
146
        remove_from_free_list(prev_block); // Previous block is already in free list, remove it
147
        prev_block->size += current->size + HEAP_HEADER_SIZE;
148
        prev_block->next = current->next;
149
        if (prev_block->next) {
150
            prev_block->next->prev = prev_block;
151
        }
152
         if (heap_end == current) {
153
            heap_end = prev_block;
154
        }
155
        // current is now merged into prev_block, clear it for safety
156
        memset(current, 0, HEAP_HEADER_SIZE);
157
        current = prev_block; // The result of the coalesce is the previous block
158
    }
159

160
    return current; // Return the potentially larger coalesced block
161
}
162

163
// --- Public API ---
164

165
void kheap_init() {
166
    free_list_head = NULL;
167
    heap_start = NULL;
168
    heap_end = NULL;
169

170
    // Pre-allocate some initial pages
171
    expand_heap(PAGE_SIZE * 4); // Pre-allocate 16KB
172

173
    kprintf("KHeap: Initialized.\n");
174
}
175

176
void* kmalloc(size_t size) {
177
    if (size == 0) {
178
        return NULL;
179
    }
180

181
    // Ensure minimum allocation size and alignment (e.g., align to 8 or 16 bytes)
182
    // For simplicity, let's align to sizeof(void*)
183
    size_t alignment = sizeof(void*);
184
    size = (size + alignment - 1) & ~(alignment - 1);
185

186
    // Add space for the header
187
    size_t total_size_needed = size + HEAP_HEADER_SIZE;
188

189
    // First-fit search
190
    heap_block_t *current_free = free_list_head;
191
    heap_block_t *best_fit = NULL;
192

193
    while (current_free) {
194
        if (current_free->size >= size) { // Found a block large enough
195
            best_fit = current_free;
196
            break; // First fit
197
        }
198
        current_free = current_free->next_free;
199
    }
200

201
    // If no block found, try to expand the heap
202
    if (!best_fit) {
203
        if (!expand_heap(total_size_needed)) {
204
            kprintf("KHeap Error: Failed to expand heap for allocation of size %zu\n", size);
205
            return NULL; // Expansion failed
206
        }
207
        // Retry finding a block (the new block should be suitable)
208
        current_free = free_list_head;
209
         while (current_free) {
210
            if (current_free->size >= size) {
211
                best_fit = current_free;
212
                break;
213
            }
214
            current_free = current_free->next_free;
215
        }
216

217
        if (!best_fit) {
218
             kprintf("KHeap Error: Still no suitable block after expansion!\n");
219
             return NULL; // Should not happen if expansion succeeded
220
        }
221
    }
222

223
    // We found a suitable block (best_fit)
224
    remove_from_free_list(best_fit); // Remove it from the free list
225

226
    // Check if we can split the block
227
    if (best_fit->size >= size + HEAP_MIN_BLOCK_SIZE) {
228
        // Split the block
229
        size_t remaining_size = best_fit->size - size - HEAP_HEADER_SIZE;
230
        heap_block_t *new_free_block = (heap_block_t *)((uint8_t *)best_fit + HEAP_HEADER_SIZE + size);
231

232
        new_free_block->size = remaining_size;
233
        new_free_block->is_free = true; // Will be added to free list
234
        new_free_block->next = best_fit->next;
235
        new_free_block->prev = best_fit;
236

237
        if (new_free_block->next) {
238
            new_free_block->next->prev = new_free_block;
239
        } else {
240
            heap_end = new_free_block; // It's the new end of the heap
241
        }
242

243
        best_fit->size = size; // Adjust size of the allocated block
244
        best_fit->next = new_free_block;
245

246
        // Add the new smaller free block to the free list
247
        add_to_free_list(new_free_block);
248
        kprintf("KHeap: Split block %p. Allocated %zu, remaining %zu at %p\n",
249
                best_fit, best_fit->size, new_free_block->size, new_free_block);
250

251
    } else {
252
        // Cannot split, allocate the whole block
253
        kprintf("KHeap: Allocated whole block %p (%zu) for size %zu\n",
254
                best_fit, best_fit->size, size);
255
    }
256

257
    best_fit->is_free = false;
258

259
    // Return pointer to the data area (after the header)
260
    void *data_ptr = (void *)((uint8_t *)best_fit + HEAP_HEADER_SIZE);
261
    // Optionally zero the allocated memory
262
    memset(data_ptr, 0, best_fit->size);
263

264
    // kprintf("KHeap: kmalloc(%zu) -> %p\n", size, data_ptr);
265
    return data_ptr;
266
}
267

268
void kfree(void *ptr) {
269
    if (!ptr) {
270
        return;
271
    }
272

273
    // Get the header from the pointer
274
    heap_block_t *block = (heap_block_t *)((uint8_t *)ptr - HEAP_HEADER_SIZE);
275

276
    // Basic validation
277
    if (block->is_free) {
278
        kprintf("KHeap Warning: Double free detected for pointer %p\n", ptr);
279
        return;
280
    }
281
    // More robust validation would involve checking magic numbers in the header
282
    // or ensuring the block pointer is within the known heap range [heap_start, heap_end].
283

284
    kprintf("KHeap: kfree(%p) - block %p, size %zu\n", ptr, block, block->size);
285
    block->is_free = true;
286

287
    // Attempt to coalesce with neighbors
288
    heap_block_t *coalesced_block = coalesce(block);
289

290
    // Add the (potentially coalesced) block back to the free list
291
    // Check if it wasn't already added by coalesce (if coalesce returned the same block)
292
    if (coalesced_block == block) {
293
         add_to_free_list(coalesced_block);
294
         kprintf("KHeap: Added block %p (%zu) to free list\n",
295
                 coalesced_block, coalesced_block->size);
296
    } else {
297
         // Coalesce already handled adding the merged block (prev_block)
298
         add_to_free_list(coalesced_block); // Ensure the final coalesced block is on the list
299
         kprintf("KHeap: Added coalesced block %p (%zu) to free list\n",
300
                 coalesced_block, coalesced_block->size);
301
    }
302
}