create dtb allocator

the parent commit (b106df2447d23d6b3fcffa7cc87edde218d054f3) discussed
the possibility of creating dtb device discovery. for that, we have
replaced wdt device discovery with dtb device discovery. in the future,
we will use the pci kernel module to use device discovery via a PCI
controller

9 files changed, 231 insertions, 49 deletions

diff --git a/include/bump.h b/include/bump.h
new file mode 100644
index 0000000..81cd571
--- /dev/null
+++ b/include/bump.h
@@ -0,0 +1,10 @@
+#pragma once
+#include <types.h>
+#include <dtb.h>
+#include <mem.h>
+#define EHEAP_SIZE (512 * 1024)
+
+
+void* kemalloc(size_t size);
+struct mem_info *km_find_memory(struct dt_node *head);
+
diff --git a/include/common.h b/include/common.h
new file mode 100644
index 0000000..86f1f9c
--- /dev/null
+++ b/include/common.h
@@ -0,0 +1,19 @@
+#pragma once
+#include <types.h>
+
+static inline size_t strlen(const char *s) {
+    size_t len = 0;
+    while (*s++) {
+        ++len;
+    }
+    return len;
+}
+static inline int strcmp(const char *str1, const char* str2) {
+    while (*str1 && (*str1 == *str2)) {
+        ++str1;
+        ++str2;
+    }
+    return *(const unsigned char *)str1 - *(const unsigned char *)str2;
+}
+
+
diff --git a/include/dtb.h b/include/dtb.h
new file mode 100644
index 0000000..1f8f14f
--- /dev/null
+++ b/include/dtb.h
@@ -0,0 +1,46 @@
+#pragma once
+#include <types.h>
+
+#define FDT_MAGIC 0xEDFE0DD0
+#define FDT_BEGIN_NODE 1
+#define FDT_END_NODE 2
+#define FDT_PROP 3
+#define FDT_NOP 4
+#define FDT_END 9
+
+#define DTB_MAX_NODES 16 
+
+struct dt_node {
+    char *name;
+    struct dt_prop *props;
+    struct dt_node *children;
+    struct dt_node *next;
+};
+
+struct dt_prop {
+    char *name;
+    char *value;
+    size_t len;
+    struct dt_prop *next;
+};
+
+struct fdt_header {
+    uint32_t magic;
+    uint32_t totalsize;
+    uint32_t off_dt_struct;
+    uint32_t off_dt_strings;
+    uint32_t off_mem_rsvmap;
+    uint32_t version;
+    uint32_t last_comp_version;
+    uint32_t boot_cpuid_phys;
+    uint32_t size_dt_strings;
+    uint32_t size_dt_struct;
+};
+
+struct dt_node *dt_parse(void *fdt);
+void *dt_get_prop(struct dt_node *node, char *name, size_t *len);
+uint32_t dt_read_u32(struct dt_node *node, char *name, uint32_t *out);
+
+
+struct dt_node *dt_node_alloc(char *name);
+struct dt_prop *dt_prop_alloc(char *name, void *value, size_t len);
diff --git a/include/mem.h b/include/mem.h
index 12976df..6135786 100644
--- a/include/mem.h
+++ b/include/mem.h
@@ -1,8 +1,6 @@
 #pragma once
 #include <types.h>
 
-#define EHEAP_SIZE (512 * 1024)
-
 typedef enum {
     PAGE_FREE,
     PAGE_ALLOCATED
@@ -14,6 +12,11 @@ struct page {
     struct page* next;
 };
 
+struct mem_info {
+    void* start;
+    size_t size;
+};
+
 void* kmalloc(size_t size);
 void* memcpy(void* to, const void* from,size_t size);
 
diff --git a/include/wdt.h b/include/wdt.h
deleted file mode 100644
index 31739ab..0000000
--- a/include/wdt.h
+++ /dev/null
@@ -1,18 +0,0 @@
-#pragma once
-#include <types.h>
-
-#define WDT_MAGIC 0x67674141
-
-struct wdt_device {
-    uint32_t type;
-    uint32_t driver_id;
-    uint32_t start;
-    uint32_t size;
-};
-
-struct wdt_root {
-    uint32_t magic;
-    uint32_t count;
-    struct wdt_device devices[];
-};
-
diff --git a/kernel/bump.c b/kernel/bump.c
new file mode 100644
index 0000000..369f92f
--- /dev/null
+++ b/kernel/bump.c
@@ -0,0 +1,49 @@
+#include <bump.h>
+#include <common.h>
+
+static char eheap[EHEAP_SIZE] = {0};
+static size_t eheap_off = 0;
+
+struct mem_info *km_find_memory(struct dt_node *head) {
+    struct dt_node *child = head->children;
+    while (child) {
+        return km_find_memory(child);
+        child = child->next;
+    }
+
+    if (strlen(head->name) != 0) {
+        struct dt_prop *prop_head = head->props;
+        while (prop_head) {
+            if (strcmp(prop_head->name, "device_type") == 0
+                && strcmp(prop_head->value, "memory") == 0) {
+                size_t len = 0;
+                uint32_t *reg = (uint32_t *)dt_get_prop(head, "reg", &len);
+                if (reg && len >= 8) {
+                    uint32_t base = be32_to_cpu(reg[0]);
+                    uint32_t size = be32_to_cpu(reg[1]);
+                    struct mem_info *ret = kemalloc(sizeof(struct mem_info));
+                    ret->start = (void*)base;
+                    ret->size = (size_t)size;
+
+                    return ret;
+                }
+            }
+            prop_head = prop_head->next;
+        }
+    }
+    return NULL;
+} 
+
+
+void* kemalloc(size_t size) {
+    size = (size + 7) & ~7;
+
+    if (eheap_off + size > EHEAP_SIZE) {
+        return NULL;
+    }
+
+    void *ptr = &eheap[eheap_off];
+    eheap_off += size;
+    return ptr;
+}
+
diff --git a/kernel/dtb.c b/kernel/dtb.c
new file mode 100644
index 0000000..99b1679
--- /dev/null
+++ b/kernel/dtb.c
@@ -0,0 +1,86 @@
+
+#include <dtb.h>
+#include <bump.h>
+#include <common.h>
+
+struct dt_node *dt_parse(void *fdt) {
+    struct fdt_header *hdr = fdt;
+
+    if (hdr->magic != FDT_MAGIC) {
+        return NULL;
+    }
+
+    uint32_t *p = (uint32_t *)(fdt + be32_to_cpu(hdr->off_dt_struct));
+    char *strings = fdt + be32_to_cpu(hdr->off_dt_strings);
+
+    struct dt_node *root = NULL;
+    struct dt_node *stack[DTB_MAX_NODES];
+    int sp = 0;
+
+    while (1) {
+        uint32_t token = be32_to_cpu(*p++);
+        switch (token) {
+            case FDT_BEGIN_NODE: {
+                char *name = (char *)p;
+                p += (strlen(name) + 3) / 4;
+
+                struct dt_node *node = dt_node_alloc(name);
+                if (sp == 0) {
+                    root = node;
+                } else {
+                    node->next = stack[sp-1]->children;
+                    stack[sp-1]->children = node;
+                }
+                stack[sp++] = node;
+                break;
+            }
+            case FDT_PROP: {
+                uint32_t len = be32_to_cpu(*p++);
+                uint32_t nameoff = be32_to_cpu(*p++);
+                void *value = p;
+                p += (len + 3) / 4;
+
+                struct dt_prop *prop = dt_prop_alloc(strings + nameoff, value, len);
+                prop->next = stack[sp-1]->props;
+                stack[sp-1]->props = prop;
+                break;
+            }
+            case FDT_END_NODE: 
+                sp--;
+                break;
+            case FDT_END:
+                return root;
+        }
+    }
+}
+
+void *dt_get_prop(struct dt_node *node, char *name, size_t *len)  {
+    for (struct dt_prop *p = node->props; p; p = p->next) {
+        if (strcmp(p->name, name) == 0) {
+            if (len) *len = p->len;
+            return p->value;
+        }
+    }
+    return NULL;
+}
+
+struct dt_node *dt_node_alloc(char *name) {
+    struct dt_node *node = kemalloc(sizeof(struct dt_node));
+    node->name = name;
+    node->props = NULL;
+    node->children = NULL;
+    node->next = NULL;
+    return node;
+}
+
+struct dt_prop *dt_prop_alloc(char *name, void *value, size_t len) {
+    struct dt_prop *prop = kemalloc(sizeof(struct dt_prop));
+    prop->name = name;
+    prop->value = value;
+    prop->len = len;
+    prop->next = NULL;
+
+    return prop;
+}
+
+
diff --git a/kernel/kernel.c b/kernel/kernel.c
index 3dbf0d1..568d8a3 100644
--- a/kernel/kernel.c
+++ b/kernel/kernel.c
@@ -1,5 +1,6 @@
 #include <types.h>
-#include <wdt.h>
+#include <dtb.h>
+#include <bump.h>
 #define UART_BASE 0x10000000  // Example UART address
 
 static inline void putchar(char c) {
@@ -13,19 +14,17 @@ static void print_string(const char *str) {
     }
 }
 
-void kernel_main(void *wdt) {
-    struct wdt_root *root = wdt;
-    print_string("deserialized all!\n");
-    uint32_t count = root->count;
-    for (uint32_t i = 0; i < count; i++) {
-        print_string("deserializing wdt node!\n");
-        print_string("device type: ");
-        if (root->devices[i].type == 0) {
-            print_string("mem");
-        } else {
-            print_string("unknown");
-        }
-        print_string("\n");
+void kernel_main(size_t hart, void *fdt) {
+    (void)hart;
+
+    struct dt_node *head = dt_parse(fdt);
+    struct mem_info *info = km_find_memory(head);
+
+    if (info) {
+        print_string("found memory!\n");
+    } else {
+        print_string("could not find memory!\n");
     }
+
     while(1);
 }
diff --git a/kernel/mem.c b/kernel/mem.c
index 531dd81..3a0b19b 100644
--- a/kernel/mem.c
+++ b/kernel/mem.c
@@ -1,25 +1,12 @@
 #include <types.h>
 #include <mem.h>
-
-static char eheap[EHEAP_SIZE] = {0};
-static size_t eheap_off = 0;
+#include <dtb.h>
+#include <common.h>
 
 void* kmalloc(size_t size) {
     return (void*)size;
 }
 
-void* kemalloc(size_t size) {
-    size = (size + 7) & ~7;
-
-    if (eheap_off + size > EHEAP_SIZE) {
-        return NULL;
-    }
-
-    void *ptr = &eheap[eheap_off];
-    eheap_off += size;
-    return ptr;
-}
-
 void* memcpy(void *to, const void *from, size_t size) {
     char *dest = (char *)to;
     const char *src = (const char *)from;
@@ -30,3 +17,4 @@ void* memcpy(void *to, const void *from, size_t size) {
 
     return dest;
 }
+