From: Minep Date: Sun, 3 Jul 2022 12:29:37 +0000 (+0100) Subject: feat: cake (slab) allocator, for dynamic continuous physical page allocation X-Git-Url: https://scm.lunaixsky.com/lunaix-os.git/commitdiff_plain/c3f8598f7b2e540e4040955f313a7d05de715c99?ds=sidebyside;hp=-c feat: cake (slab) allocator, for dynamic continuous physical page allocation --- c3f8598f7b2e540e4040955f313a7d05de715c99 diff --git a/lunaix-os/includes/lunaix/mm/cake.h b/lunaix-os/includes/lunaix/mm/cake.h new file mode 100644 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 + +#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 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 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 +#include +#include +#include +#include +#include + +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 "

\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 9c0d3eb..4503535 100644 --- 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) { - (!(&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; } diff --git a/lunaix-os/kernel/mm/valloc.c b/lunaix-os/kernel/mm/valloc.c new file mode 100644 index 0000000..4429562 --- /dev/null +++ b/lunaix-os/kernel/mm/valloc.c @@ -0,0 +1,46 @@ +#include + +#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 3a6ea62..bef7bb7 100644 --- a/lunaix-os/kernel/proc0.c +++ b/lunaix-os/kernel/proc0.c @@ -2,7 +2,9 @@ #include #include #include +#include #include +#include #include #include #include @@ -110,11 +112,14 @@ extern multiboot_info_t* _k_init_mb_info; /* k_init.c */ void init_platform() { - assert_msg(kalloc_init(), "Fail to initialize heap"); - // 锁定所有系统预留页（内存映射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(); @@ -126,6 +131,8 @@ init_platform() pci_print_device(); ahci_list_device(); + cake_stats(); + syscall_install(); console_start_flushing();