feat: cake (slab) allocator, for dynamic continuous physical page allocation

diff --git a/lunaix-os/includes/lunaix/mm/cake.h b/lunaix-os/includes/lunaix/mm/cake.h
new file mode 100644 (file)
index 0000000..8e971d8
--- /dev/null
+++ b/lunaix-os/includes/lunaix/mm/cake.h
@@ -0,0 +1,74 @@
+#ifndef __LUNAIX_SLAB_H
+#define __LUNAIX_SLAB_H
+
+#include <lunaix/ds/llist.h>
+
+#define PILE_NAME_MAXLEN 20
+
+struct cake_pile
+{
+    struct llist_header piles;
+    struct llist_header full;
+    struct llist_header partial;
+    struct llist_header free;
+    unsigned int piece_size;
+    unsigned int cakes_count;
+    unsigned int alloced_pieces;
+    unsigned int pieces_per_cake;
+    unsigned int pg_per_cake;
+    char pile_name[PILE_NAME_MAXLEN];
+};
+
+typedef unsigned int piece_index_t;
+
+#define EO_FREE_PIECE (-1)
+
+struct cake_s
+{
+    struct llist_header cakes;
+    void* first_piece;
+    unsigned int used_pieces;
+    unsigned int next_free;
+    piece_index_t free_list[0];
+};
+
+/**
+ * @brief 创建一个堆
+ *
+ * @param name 堆名称
+ * @param piece_size 每个蛋糕上可以被切分的大小
+ * @param pg_per_cake 每个蛋糕所占据的页数
+ * @return struct cake_pile*
+ */
+struct cake_pile*
+cake_new_pile(char* name, unsigned int piece_size, unsigned int pg_per_cake);
+
+/**
+ * @brief 拿一块儿蛋糕
+ *
+ * @param pile
+ * @return void*
+ */
+void*
+cake_grab(struct cake_pile* pile);
+
+/**
+ * @brief 归还一块儿蛋糕
+ *
+ * @param pile
+ * @param area
+ */
+int
+cake_release(struct cake_pile* pile, void* area);
+
+void
+cake_init();
+
+/**
+ * @brief 统计蛋糕数量 - 问问Pinkie :D
+ *
+ */
+void
+cake_stats();
+
+#endif /* __LUNAIX_VALLOC_H */

diff --git a/lunaix-os/includes/lunaix/mm/valloc.h b/lunaix-os/includes/lunaix/mm/valloc.h
new file mode 100644 (file)
index 0000000..ee646e5
--- /dev/null
+++ b/lunaix-os/includes/lunaix/mm/valloc.h
@@ -0,0 +1,13 @@
+#ifndef __LUNAIX_VALLOC_H
+#define __LUNAIX_VALLOC_H
+
+void*
+valloc(unsigned int size);
+
+void
+vfree(void* ptr);
+
+void
+valloc_init();
+
+#endif /* __LUNAIX_VALLOC_H */

diff --git a/lunaix-os/kernel/mm/cake.c b/lunaix-os/kernel/mm/cake.c
new file mode 100644 (file)
index 0000000..2117286
--- /dev/null
+++ b/lunaix-os/kernel/mm/cake.c
@@ -0,0 +1,182 @@
+/**
+ * @file valloc.c
+ * @author Lunaixsky (zelong56@gmail.com)
+ * @brief A simplified cake(slab) allocator.
+ *          P.s. I call it cake as slab sounds more 'ridge' to me. :)
+ * @version 0.1
+ * @date 2022-07-02
+ *
+ * @copyright Copyright (c) 2022
+ *
+ */
+
+#include <klibc/string.h>
+#include <lunaix/mm/cake.h>
+#include <lunaix/mm/pmm.h>
+#include <lunaix/mm/vmm.h>
+#include <lunaix/spike.h>
+#include <lunaix/syslog.h>
+
+LOG_MODULE("CAKE")
+
+#define SLAB_SIZE PG_SIZE
+
+struct cake_pile master_pile;
+
+struct llist_header piles = { .next = &piles, .prev = &piles };
+
+void*
+__alloc_cake(unsigned int cake_pg)
+{
+    uintptr_t pa = pmm_alloc_cpage(KERNEL_PID, cake_pg, 0);
+    return vmm_vmap(pa, cake_pg * PG_SIZE, PG_PREM_RW);
+}
+
+struct cake_s*
+__new_cake(struct cake_pile* pile)
+{
+    struct cake_s* cake = __alloc_cake(pile->pg_per_cake);
+
+    int max_piece = pile->pieces_per_cake;
+
+    cake->first_piece =
+      (void*)((uintptr_t)(cake + 1) + max_piece * sizeof(piece_index_t));
+    cake->next_free = 0;
+
+    piece_index_t* free_list = &cake->free_list;
+    for (size_t i = 0; i < max_piece - 1; i++) {
+        free_list[i] = i + 1;
+    }
+    free_list[max_piece - 1] = EO_FREE_PIECE;
+
+    llist_append(&pile->free, &cake->cakes);
+
+    return cake;
+}
+
+void
+__init_pile(struct cake_pile* pile,
+            char* name,
+            unsigned int piece_size,
+            unsigned int pg_per_cake)
+{
+    *pile = (struct cake_pile){ .piece_size = piece_size,
+                                .cakes_count = 1,
+                                .pieces_per_cake =
+                                  (pg_per_cake * PG_SIZE) /
+                                  (piece_size + sizeof(piece_index_t)),
+                                .pg_per_cake = pg_per_cake };
+
+    strncpy(&pile->pile_name, name, PILE_NAME_MAXLEN);
+
+    llist_init_head(&pile->free);
+    llist_init_head(&pile->full);
+    llist_init_head(&pile->partial);
+    llist_append(&piles, &pile->piles);
+}
+
+void
+cake_init()
+{
+    __init_pile(&master_pile, "master", sizeof(master_pile), 1);
+}
+
+struct cake_pile*
+cake_new_pile(char* name, unsigned int piece_size, unsigned int pg_per_cake)
+{
+    struct cake_pile* pile = (struct cake_pile*)cake_grab(&master_pile);
+
+    __init_pile(pile, name, piece_size, pg_per_cake);
+
+    return pile;
+}
+
+void*
+cake_grab(struct cake_pile* pile)
+{
+    struct cake_s *pos, *n;
+    llist_for_each(pos, n, &pile->partial, cakes)
+    {
+        if (pos->next_free != EO_FREE_PIECE) {
+            goto found;
+        }
+    }
+
+    if (llist_empty(&pile->free)) {
+        pos = __new_cake(pile);
+    } else {
+        pos = list_entry(pile->free.next, typeof(*pos), cakes);
+    }
+
+found:
+    piece_index_t found_index = pos->next_free;
+    pos->next_free = pos->free_list[found_index];
+    pos->used_pieces++;
+    pile->alloced_pieces++;
+
+    llist_delete(&pos->cakes);
+    if (pos->next_free == EO_FREE_PIECE) {
+        llist_append(&pile->full, &pos->cakes);
+    } else {
+        llist_append(&pile->partial, &pos->cakes);
+    }
+
+    return (void*)((uintptr_t)pos->first_piece +
+                   found_index * pile->piece_size);
+}
+
+int
+cake_release(struct cake_pile* pile, void* area)
+{
+    piece_index_t area_index;
+    struct cake_s *pos, *n;
+    struct llist_header* hdrs[2] = { &pile->full, &pile->partial };
+
+    for (size_t i = 0; i < 2; i++) {
+        llist_for_each(pos, n, hdrs[i], cakes)
+        {
+            if (pos->first_piece > area) {
+                continue;
+            }
+            area_index =
+              (uintptr_t)(area - pos->first_piece) / pile->piece_size;
+            if (area_index < pile->pieces_per_cake) {
+                goto found;
+            }
+        }
+    }
+
+    return 0;
+
+found:
+    pos->free_list[area_index] = pos->next_free;
+    pos->next_free = area_index;
+    pos->used_pieces--;
+    pile->alloced_pieces--;
+
+    llist_delete(pos);
+    if (!pos->used_pieces) {
+        llist_append(&pile->free, &pos->cakes);
+    } else {
+        llist_append(&pile->partial, &pos->cakes);
+    }
+
+    return 1;
+}
+
+void
+cake_stats()
+{
+    kprintf(KDEBUG "<name> <cake> <pg/c> <p/c> <alloced>\n");
+
+    struct cake_pile *pos, *n;
+    llist_for_each(pos, n, &piles, piles)
+    {
+        kprintf("%s %d %d %d %d\n",
+                pos->pile_name,
+                pos->cakes_count,
+                pos->pg_per_cake,
+                pos->pieces_per_cake,
+                pos->alloced_pieces);
+    }
+}
\ No newline at end of file

diff --git a/lunaix-os/kernel/mm/pmm.c b/lunaix-os/kernel/mm/pmm.c
index 9c0d3eb44272bda83e4fbe931408261a6801ba75..450353538d6d17d38ad02ec7a3ee88d2fdec5488 100644 (file)
--- a/lunaix-os/kernel/mm/pmm.c
+++ b/lunaix-os/kernel/mm/pmm.c
@@ -66,10 +66,10 @@ pmm_alloc_cpage(pid_t owner, size_t num_pages, pp_attr_t attr)
     size_t p2 = 0;
 
     while (p2 < max_pg && p2 - p1 < num_pages) {
     size_t p2 = 0;
 
     while (p2 < max_pg && p2 - p1 < num_pages) {

-        (!(&pm_table[p2])->ref_counts) ? (p2++) : (p1 = p2);
+        (!(&pm_table[p2])->ref_counts) ? (p2++) : (p1 = ++p2);

     }
 
     }
 

-    if (p2 < max_pg) {
+    if (p2 == max_pg && p2 - p1 < num_pages) {

         return NULL;
     }
 
         return NULL;
     }
 

diff --git a/lunaix-os/kernel/mm/valloc.c b/lunaix-os/kernel/mm/valloc.c
new file mode 100644 (file)
index 0000000..4429562
--- /dev/null
+++ b/lunaix-os/kernel/mm/valloc.c
@@ -0,0 +1,46 @@
+#include <lunaix/mm/cake.h>
+
+#define MAX_CLASS 6
+
+static char piles_names[MAX_CLASS][PILE_NAME_MAXLEN] = {
+    "valloc_128", "valloc_256", "valloc_512",
+    "valloc_1k",  "valloc_2k",  "valloc_4k"
+};
+
+static struct cake_pile* piles[MAX_CLASS];
+
+void
+valloc_init()
+{
+    for (size_t i = 0; i < MAX_CLASS; i++) {
+        int size = 1 << (i + 7);
+        piles[i] = cake_new_pile(&piles_names[i], size, size > 1024 ? 8 : 1);
+    }
+}
+
+void*
+valloc(unsigned int size)
+{
+    size_t i = 0;
+    for (; i < MAX_CLASS; i++) {
+        if (piles[i]->piece_size > size) {
+            goto found_class;
+        }
+    }
+
+    return NULL;
+
+found_class:
+    return cake_grab(piles[i]);
+}
+
+void
+vfree(void* ptr)
+{
+    size_t i = 0;
+    for (; i < MAX_CLASS; i++) {
+        if (cake_release(piles[i], ptr)) {
+            return;
+        }
+    }
+}
\ No newline at end of file

diff --git a/lunaix-os/kernel/proc0.c b/lunaix-os/kernel/proc0.c
index 3a6ea62116aea40654d96c93ee97a39ac8c1167f..bef7bb7316f896afa4cc8e77c90cdcada4ec672d 100644 (file)
--- a/lunaix-os/kernel/proc0.c
+++ b/lunaix-os/kernel/proc0.c
@@ -2,7 +2,9 @@
 #include <lunaix/common.h>
 #include <lunaix/lunistd.h>
 #include <lunaix/lxconsole.h>
 #include <lunaix/common.h>
 #include <lunaix/lunistd.h>
 #include <lunaix/lxconsole.h>

+#include <lunaix/mm/cake.h>

 #include <lunaix/mm/pmm.h>
 #include <lunaix/mm/pmm.h>

+#include <lunaix/mm/valloc.h>

 #include <lunaix/mm/vmm.h>
 #include <lunaix/peripheral/ps2kbd.h>
 #include <lunaix/proc.h>
 #include <lunaix/mm/vmm.h>
 #include <lunaix/peripheral/ps2kbd.h>
 #include <lunaix/proc.h>


@@ -110,11 +112,14 @@ extern multiboot_info_t* _k_init_mb_info; /* k_init.c */
 void
 init_platform()
 {
 void
 init_platform()
 {

-    assert_msg(kalloc_init(), "Fail to initialize heap");
-

     // 锁定所有系统预留页（内存映射IO，ACPI之类的），并且进行1:1映射
     lock_reserved_memory();
 
     // 锁定所有系统预留页（内存映射IO，ACPI之类的），并且进行1:1映射
     lock_reserved_memory();
 

+    cake_init();
+
+    assert_msg(kalloc_init(), "Fail to initialize heap");
+    valloc_init();
+

     acpi_init(_k_init_mb_info);
     apic_init();
     ioapic_init();
     acpi_init(_k_init_mb_info);
     apic_init();
     ioapic_init();


@@ -126,6 +131,8 @@ init_platform()
     pci_print_device();
     ahci_list_device();
 
     pci_print_device();
     ahci_list_device();
 

+    cake_stats();
+

     syscall_install();
 
     console_start_flushing();
     syscall_install();
 
     console_start_flushing();