Add physical page (frame) allocator.

7 files changed, 123 insertions, 7 deletions

diff --git a/kernel/Makefile b/kernel/Makefile
index 34e6a2e..572bb3a 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -11,7 +11,8 @@ LDFLAGS = -T linker.ld -ffreestanding -O2 -nostdlib -lgcc
 
 OBJ = lib/string.o lib/printf.o \
 	l0/loader.o l0/kmain.o l0/dbglog.o l0/sys.o \
-	l0/gdt.o l0/idt.o l0/interrupt.o
+	l0/gdt.o l0/idt.o l0/interrupt.o \
+	l0/frame.o
 OUT = kernel.bin
 
 all: $(OUT)
diff --git a/kernel/config.h b/kernel/config.h
index b1a97b2..ad3dfb2 100644
--- a/kernel/config.h
+++ b/kernel/config.h
@@ -14,10 +14,11 @@
 #endif
 
 
-extern char k_highhalf_addr;	// defined in linker script : 0xC0000000
-#define K_HIGHHALF_ADDR ((void*)&k_highhalf_addr)
+extern char k_highhalf_addr, k_end_addr;	// defined in linker script : 0xC0000000
+#define K_HIGHHALF_ADDR ((size_t)&k_highhalf_addr)
+#define K_END_ADDR ((size_t)&k_end_addr)
 
-#define OS_NAME "Macroscope"
+#define OS_NAME "macrO.Scope"
 #define OS_VERSION "0.0.1"
 
 // Comment to disable either form of debug log output
diff --git a/kernel/include/frame.h b/kernel/include/frame.h
new file mode 100644
index 0000000..9ffafb3
--- /dev/null
+++ b/kernel/include/frame.h
@@ -0,0 +1,14 @@
+#pragma once
+
+#include <sys.h>
+
+// frame.h : physical memory allocator
+
+void frame_init_allocator(size_t total_ram, void** kernel_data_end);
+
+uint32_t frame_alloc(size_t n);		// allocate n consecutive frames (returns 0 on failure)
+void frame_free(uint32_t base, size_t n);
+
+void dbg_print_frame_stats();
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/kernel/include/sys.h b/kernel/include/sys.h
index 2304eec..a9d2d4c 100644
--- a/kernel/include/sys.h
+++ b/kernel/include/sys.h
@@ -29,4 +29,18 @@ void panic_assert(const char* assertion, const char* file, int line);
 
 #define BOCHS_BREAKPOINT asm volatile("xchg %bx, %bx")
 
+
+// Utility functions for memory alignment
+
+#define PAGE_SIZE		0x1000
+#define PAGE_MASK		0xFFFFF000
+#define PAGE_ALIGN_DOWN(x)	(((size_t)x) & PAGE_MASK) 
+#define PAGE_ALIGN_UP(x)  	((((size_t)x)&(~PAGE_MASK)) == 0 ? ((size_t)x) : (((size_t)x) & PAGE_MASK) + PAGE_SIZE)
+#define PAGE_ID(x)			(((size_t)x) / PAGE_SIZE)
+
+#define MASK4			0xFFFFFFFC
+#define ALIGN4_UP(x)	((((size_t)x)&(~MASK4)) == 0 ? ((size_t)x) : (((size_t)x) & MASK4) + 4)
+#define ALIGN4_DOWN(x)	(((size_t)x)&MASK4)
+
+
 /* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/kernel/l0/frame.c b/kernel/l0/frame.c
new file mode 100644
index 0000000..1f16eaf
--- /dev/null
+++ b/kernel/l0/frame.c
@@ -0,0 +1,73 @@
+#include <frame.h>
+#include <dbglog.h>
+
+// TODO: buddy allocator
+// this is a simple bitmap allocator
+	
+#define INDEX_FROM_BIT(a) (a/(8*4))
+#define OFFSET_FROM_BIT(a) (a%(8*4))
+
+static uint32_t *frame_bitset;
+static uint32_t nframes, nused_frames;
+static uint32_t begin_search_at;
+
+void frame_init_allocator(size_t total_ram, void** kernel_data_end) {
+	nframes = PAGE_ID(total_ram);
+
+	frame_bitset = (uint32_t*)ALIGN4_UP((size_t)*kernel_data_end);
+	*kernel_data_end = (void*)frame_bitset + ALIGN4_UP(nframes / 8);
+
+	for (size_t i = 0; i < ALIGN4_UP(nframes / 8)/4; i++)
+		frame_bitset[i] = 0;
+
+	nused_frames = 0;
+
+	size_t kernel_pages = PAGE_ALIGN_UP((size_t)*kernel_data_end - K_HIGHHALF_ADDR)/PAGE_SIZE;
+	for (size_t i = 0; i < kernel_pages; i++) {
+		size_t idx = INDEX_FROM_BIT(i);
+		size_t ofs = OFFSET_FROM_BIT(i);
+		frame_bitset[idx] |= (0x1 << ofs);
+		nused_frames++;
+	}
+	begin_search_at = INDEX_FROM_BIT(kernel_pages);
+}
+
+uint32_t frame_alloc(size_t n) {
+	if (n > 32) return 0;
+
+	for (uint32_t i = begin_search_at; i < INDEX_FROM_BIT(nframes); i++) {
+		if (frame_bitset[i] == 0xFFFFFFFF) {
+			if (i == begin_search_at) begin_search_at++;
+			continue;
+		}
+
+		for (uint32_t j = 0; j < 32 - n + 1; j++) {
+			uint32_t to_test = (0xFFFFFFFF >> (32 - n)) << j;
+			if (!(frame_bitset[i]&to_test)) {
+				frame_bitset[i] |= to_test;
+				nused_frames += n;
+				return i * 32 + j;
+			}
+		}
+	}
+	return 0;
+}
+
+void frame_free(uint32_t base, size_t n) {
+	for (size_t x = 0; x < n; x++) {
+		uint32_t idx = INDEX_FROM_BIT(base + n);
+		uint32_t ofs = OFFSET_FROM_BIT(base + n);
+		if (frame_bitset[idx] & (0x1 << ofs)) {
+			frame_bitset[idx] &= ~(0x1 << ofs);
+			nused_frames--;
+		}
+	}
+	if (INDEX_FROM_BIT(base) < begin_search_at)
+		begin_search_at = INDEX_FROM_BIT(base);
+}
+
+void dbg_print_frame_stats() {
+	dbg_printf("Used frames: %d/%d\n", nused_frames, nframes);
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/kernel/l0/kmain.c b/kernel/l0/kmain.c
index 7665cb0..b4e2ef1 100644
--- a/kernel/l0/kmain.c
+++ b/kernel/l0/kmain.c
@@ -5,6 +5,7 @@
 
 #include <gdt.h>
 #include <idt.h>
+#include <frame.h>
 
 void breakpoint_handler(registers_t *regs) {
 	dbg_printf("Breakpoint! (int3)\n");
@@ -23,13 +24,25 @@ void kmain(struct multiboot_info_t *mbd, int32_t mb_magic) {
 
 	idt_init(); dbg_printf("IDT set up.\n");
 	idt_set_ex_handler(EX_BREAKPOINT, breakpoint_handler);
-
-	asm volatile("int $0x3");
+	asm volatile("int $0x3");	// test breakpoint
 
 	size_t total_ram = ((mbd->mem_upper + mbd->mem_lower) * 1024);
 	dbg_printf("Total ram: %d Kb\n", total_ram / 1024);
 	// paging_init(totalRam);
 
+	// used for allocation of data structures before malloc is set up
+	// a pointer to this pointer is passed to the functions that might have
+	// to allocate memory ; they just increment it of the allocated quantity
+	void* kernel_data_end = (void*)K_END_ADDR;
+	frame_init_allocator(total_ram, &kernel_data_end);
+	dbg_printf("kernel_data_end: 0x%p\n", kernel_data_end);
+	dbg_print_frame_stats();
+
+	// TODO:
+	// - setup allocator for physical pages (eg: buddy allocator, see OSDev wiki)
+	// - setup allocator for virtual memory space
+	// - setup paging
+
 	PANIC("Reached kmain end! Falling off the edge.");
 }
 
diff --git a/kernel/linker.ld b/kernel/linker.ld
index 8ea7854..c92155c 100644
--- a/kernel/linker.ld
+++ b/kernel/linker.ld
@@ -36,7 +36,7 @@ SECTIONS{
 		ebss = .;
 	}
 
-	end = .; _end = .; __end = .;
+	k_end_addr = .;
 }
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/