From a136ca38d83fae60994a54f5da88120e545895e1 Mon Sep 17 00:00:00 2001 From: Lunaixsky Date: Wed, 14 Aug 2024 22:54:37 +0100 Subject: [PATCH] Improve cake allocator's memory utilisation (#43) * allow cake metadata to be separated and improve the utilisation * add method to reclaim the freed cakes * adjust threshold to make all valloc > 128 use non-embed pile --- lunaix-os/includes/lunaix/mm/cake.h | 29 +++- lunaix-os/kernel/mm/cake.c | 249 ++++++++++++++++++++++++---- lunaix-os/kernel/mm/cake_export.c | 5 +- lunaix-os/kernel/mm/valloc.c | 33 +++- 4 files changed, 278 insertions(+), 38 deletions(-) diff --git a/lunaix-os/includes/lunaix/mm/cake.h b/lunaix-os/includes/lunaix/mm/cake.h index cf1c16e..d880531 100644 --- a/lunaix-os/includes/lunaix/mm/cake.h +++ b/lunaix-os/includes/lunaix/mm/cake.h @@ -6,7 +6,8 @@ #define PILE_NAME_MAXLEN 20 -#define PILE_ALIGN_CACHE 1 +#define PILE_ALIGN_CACHE 0b0001 +#define PILE_FL_EXTERN 0b0010 struct cake_pile; @@ -24,22 +25,39 @@ struct cake_pile u32_t alloced_pieces; u32_t pieces_per_cake; u32_t pg_per_cake; + u32_t options; char pile_name[PILE_NAME_MAXLEN+1]; pile_cb ctor; }; -typedef unsigned int piece_index_t; +typedef unsigned short piece_t; -#define EO_FREE_PIECE ((u32_t)-1) +#define EO_FREE_PIECE ((piece_t)-1) + +#define CAKE_FL_SIZE 128 +#define CAKE_FL_MAXLEN \ + ((unsigned int)((CAKE_FL_SIZE - sizeof(ptr_t)) / sizeof(piece_t))) +struct cake_fl +{ + piece_t indices[CAKE_FL_MAXLEN]; + struct cake_fl* next; +} align(CAKE_FL_SIZE); struct cake_s { struct llist_header cakes; + struct cake_pile* owner; void* first_piece; unsigned int used_pieces; unsigned int next_free; - piece_index_t free_list[0]; + union { + struct cake_fl* fl; + struct { + void* rsvd; + piece_t free_list[0]; + }; + }; }; /** @@ -83,6 +101,9 @@ cake_init(); void cake_export(); +void +cake_reclaim_freed(); + /********** some handy constructor ***********/ void diff --git a/lunaix-os/kernel/mm/cake.c b/lunaix-os/kernel/mm/cake.c index d9ef381..b1e699f 100644 --- a/lunaix-os/kernel/mm/cake.c +++ b/lunaix-os/kernel/mm/cake.c @@ -2,7 +2,7 @@ * @file cake.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. :) + * P.s. I call it cake as slab sounds quite 'rigid' to me :) * @version 0.1 * @date 2022-07-02 * @@ -20,12 +20,18 @@ LOG_MODULE("CAKE") #define CACHE_LINE_SIZE 128 -struct cake_pile master_pile; +static struct cake_pile master_pile, fl_pile, cakes; struct llist_header piles = { .next = &piles, .prev = &piles }; -void* -__alloc_cake(unsigned int cake_pg) +static inline bool +embedded_pile(struct cake_pile* pile) +{ + return !(pile->options & PILE_FL_EXTERN); +} + +static void* +__alloc_cake_pages(unsigned int cake_pg) { struct leaflet* leaflet = alloc_leaflet(count_order(cake_pg)); if (!leaflet) { @@ -35,35 +41,135 @@ __alloc_cake(unsigned int cake_pg) return (void*)vmap(leaflet, KERNEL_DATA); } -struct cake_s* -__new_cake(struct cake_pile* pile) +static struct cake_fl* +__alloc_fl(piece_t prev_id, piece_t max_len) { + unsigned int i, j; + struct cake_fl* cake_fl; + + cake_fl = cake_grab(&fl_pile); + for (i = 0, j=prev_id; i < CAKE_FL_MAXLEN && j < max_len; i++, j++) + { + cake_fl->indices[i] = j + 1; + } + + for (i -= 1; j == max_len && i < CAKE_FL_SIZE; i++) { + cake_fl->indices[i] = EO_FREE_PIECE; + } + + cake_fl->next = NULL; + return cake_fl; +} + +static void +__free_fls(struct cake_s* cake) { + unsigned int i, j; + struct cake_fl *cake_fl, *next; + + cake_fl = cake->fl; + while (cake_fl) + { + next = cake_fl->next; + cake_release(&fl_pile, cake_fl); + cake_fl = next; + } + + cake->fl = NULL; +} + +static piece_t* +__fl_slot(struct cake_s* cake, piece_t index) +{ + int id_acc; + struct cake_fl* cake_fl; + struct cake_pile* pile; + + pile = cake->owner; + if (embedded_pile(pile)) { + return &cake->free_list[index]; + } + + id_acc = 0; + cake_fl = cake->fl; + while (index >= CAKE_FL_MAXLEN) + { + index -= CAKE_FL_MAXLEN; + id_acc += CAKE_FL_MAXLEN; + + if (cake_fl->next) { + cake_fl = cake_fl->next; + continue; + } + + cake_fl = __alloc_fl(id_acc, pile->pieces_per_cake); + cake_fl->next = cake_fl; + } + + return &cake_fl->indices[index]; +} + +static inline struct cake_s* +__create_cake_extern(struct cake_pile* pile) { - struct cake_s* cake = __alloc_cake(pile->pg_per_cake); + struct cake_s* cake; + + cake = cake_grab(&cakes); + if (unlikely(!cake)) { + return NULL; + } - if (!cake) { + cake->first_piece = __alloc_cake_pages(pile->pg_per_cake); + cake->fl = __alloc_fl(0, pile->pieces_per_cake); + cake->next_free = 0; + + return cake; +} + +static inline struct cake_s* +__create_cake_embed(struct cake_pile* pile) +{ + struct cake_s* cake; + + cake = __alloc_cake_pages(pile->pg_per_cake); + if (unlikely(!cake)) { return NULL; } u32_t max_piece = pile->pieces_per_cake; assert(max_piece); - + cake->first_piece = (void*)((ptr_t)cake + pile->offset); cake->next_free = 0; - pile->cakes_count++; - piece_index_t* free_list = cake->free_list; + piece_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; + return cake; +} + +static struct cake_s* +__new_cake(struct cake_pile* pile) +{ + struct cake_s* cake; + + if (embedded_pile(pile)) { + cake = __create_cake_embed(pile); + } + else { + cake = __create_cake_extern(pile); + } + + cake->owner = pile; + pile->cakes_count++; llist_append(&pile->free, &cake->cakes); return cake; } -void +static void __init_pile(struct cake_pile* pile, char* name, unsigned int piece_size, @@ -85,15 +191,28 @@ __init_pile(struct cake_pile* pile, piece_size = ROUNDUP(piece_size, offset); *pile = (struct cake_pile){ .piece_size = piece_size, .cakes_count = 0, - .pieces_per_cake = - (pg_per_cake * PAGE_SIZE) / - (piece_size + sizeof(piece_index_t)), + .options = options, .pg_per_cake = pg_per_cake }; - unsigned int free_list_size = pile->pieces_per_cake * sizeof(piece_index_t); - - pile->offset = ROUNDUP(sizeof(struct cake_s) + free_list_size, offset); - pile->pieces_per_cake -= ICEIL((pile->offset - free_list_size), piece_size); + if (!embedded_pile(pile)) { + pile->offset = 0; + pile->pieces_per_cake = (pg_per_cake * PAGE_SIZE) / piece_size; + } + else { + unsigned int free_list_size; + + pile->pieces_per_cake + = (pg_per_cake * PAGE_SIZE) / + (piece_size + sizeof(piece_t)); + + free_list_size + = pile->pieces_per_cake * sizeof(piece_t); + + pile->offset + = ROUNDUP(sizeof(struct cake_s) + free_list_size, offset); + pile->pieces_per_cake + -= ICEIL((pile->offset - free_list_size), piece_size); + } strncpy(pile->pile_name, name, PILE_NAME_MAXLEN); @@ -103,10 +222,49 @@ __init_pile(struct cake_pile* pile, llist_append(&piles, &pile->piles); } +static void +__destory_cake(struct cake_s* cake) +{ + // Pinkie Pie is going to MAD! + + struct leaflet* leaflet; + struct cake_pile* owner; + pfn_t _pfn; + ptr_t page_va; + + owner = cake->owner; + assert(!cake->used_pieces); + + llist_delete(&cake->cakes); + owner->cakes_count--; + + if (!embedded_pile(owner)) { + page_va = __ptr(cake->first_piece); + __free_fls(cake); + cake_release(&cakes, cake); + } + else { + page_va = __ptr(cake); + } + + _pfn = pfn(vmm_v2p(page_va)); + leaflet = ppfn_leaflet(_pfn); + vunmap(page_va, leaflet); + + leaflet_return(leaflet); +} + void cake_init() { - __init_pile(&master_pile, "pinkamina", sizeof(master_pile), 1, 0); + // pinkamina is our master, no one shall precede her. + __init_pile(&master_pile, "pinkamina", + sizeof(master_pile), 1, 0); + + __init_pile(&fl_pile, "gummy", \ + sizeof(struct cake_fl), 1, 0); + __init_pile(&cakes, "cakes", \ + sizeof(struct cake_s), 1, 0); } struct cake_pile* @@ -145,33 +303,40 @@ cake_grab(struct cake_pile* pile) if (!pos) return NULL; + + void* piece; + piece_t found_index, *fl_slot; + + found_index = pos->next_free; + fl_slot = __fl_slot(pos, found_index); - piece_index_t found_index = pos->next_free; - pos->next_free = pos->free_list[found_index]; + pos->next_free = *fl_slot; pos->used_pieces++; pile->alloced_pieces++; llist_delete(&pos->cakes); - if (pos->free_list[pos->next_free] == EO_FREE_PIECE) { + + fl_slot = __fl_slot(pos, pos->next_free); + if (*fl_slot == EO_FREE_PIECE) { llist_append(&pile->full, &pos->cakes); } else { llist_append(&pile->partial, &pos->cakes); } - void* ptr = - (void*)((ptr_t)pos->first_piece + found_index * pile->piece_size); + piece = + (void*)(__ptr(pos->first_piece) + found_index * pile->piece_size); if (pile->ctor) { - pile->ctor(pile, ptr); + pile->ctor(pile, piece); } - return ptr; + return piece; } int cake_release(struct cake_pile* pile, void* area) { - piece_index_t piece_index; + piece_t piece_index; size_t dsize = 0; struct cake_s *pos, *n; struct llist_header* hdrs[2] = { &pile->full, &pile->partial }; @@ -194,10 +359,14 @@ cake_release(struct cake_pile* pile, void* area) found: assert(!(dsize % pile->piece_size)); - pos->free_list[piece_index] = pos->next_free; + + piece_t *fl_slot; + + fl_slot = __fl_slot(pos, piece_index); + *fl_slot = pos->next_free; pos->next_free = piece_index; - assert_msg(pos->free_list[piece_index] != pos->next_free, "double free"); + assert_msg(*fl_slot != pos->next_free, "double free"); pos->used_pieces--; pile->alloced_pieces--; @@ -218,4 +387,24 @@ void cake_ctor_zeroing(struct cake_pile* pile, void* piece) { memset(piece, 0, pile->piece_size); +} + +static inline void +__reclaim(struct cake_pile *pile) +{ + struct cake_s *pos, *n; + llist_for_each(pos, n, &pile->free, cakes) + { + __destory_cake(pos); + } +} + +void +cake_reclaim_freed() +{ + struct cake_pile *pos, *n; + llist_for_each(pos, n, &master_pile.piles, piles) + { + __reclaim(pos); + } } \ No newline at end of file diff --git a/lunaix-os/kernel/mm/cake_export.c b/lunaix-os/kernel/mm/cake_export.c index 377a9ad..e2ecb3a 100644 --- a/lunaix-os/kernel/mm/cake_export.c +++ b/lunaix-os/kernel/mm/cake_export.c @@ -18,7 +18,7 @@ void __cake_stat_reset(struct twimap* map) { map->index = container_of(&piles, struct cake_pile, piles); - twimap_printf(map, "name, n_cakes, pg/cake, slices/cake, n_slices\n"); + twimap_printf(map, "name cakes pages size slices actives\n"); } void @@ -26,10 +26,11 @@ __cake_rd_stat(struct twimap* map) { struct cake_pile* pos = twimap_index(map, struct cake_pile*); twimap_printf(map, - "%s %d %d %d %d\n", + "%s %d %d %d %d %d\n", pos->pile_name, pos->cakes_count, pos->pg_per_cake, + pos->piece_size, pos->pieces_per_cake, pos->alloced_pieces); } diff --git a/lunaix-os/kernel/mm/valloc.c b/lunaix-os/kernel/mm/valloc.c index 67c8eac..d2baa35 100644 --- a/lunaix-os/kernel/mm/valloc.c +++ b/lunaix-os/kernel/mm/valloc.c @@ -5,6 +5,9 @@ #define CLASS_LEN(class) (sizeof(class) / sizeof(class[0])) +// threshold to use external cake metadata +#define EXTERN_THRESHOLD 128 + static char piles_names[][PILE_NAME_MAXLEN] = { "valloc_8", "valloc_16", "valloc_32", "valloc_64", @@ -12,6 +15,24 @@ static char piles_names[][PILE_NAME_MAXLEN] = "valloc_2k", "valloc_4k", "valloc_8k" }; +#define M128 (4) +#define M1K (M128 + 3) + +static int page_counts[] = +{ + [0] = 1, + [1] = 1, + [2] = 1, + [3] = 1, + [M128 ] = 1, + [M128 + 1] = 2, + [M128 + 2] = 2, + [M1K ] = 4, + [M1K + 1 ] = 4, + [M1K + 2 ] = 8, + [M1K + 3 ] = 8 +}; + static char piles_names_dma[][PILE_NAME_MAXLEN] = { "valloc_dma_128", "valloc_dma_256", "valloc_dma_512", @@ -24,16 +45,24 @@ static struct cake_pile* piles_dma[CLASS_LEN(piles_names_dma)]; void valloc_init() { + int opts = 0; for (size_t i = 0; i < CLASS_LEN(piles_names); i++) { int size = 1 << (i + 3); - piles[i] = cake_new_pile(piles_names[i], size, size > 1024 ? 8 : 1, 0); + if (size >= EXTERN_THRESHOLD) { + opts |= PILE_FL_EXTERN; + } + piles[i] = cake_new_pile(piles_names[i], size, page_counts[i], opts); } + opts = PILE_ALIGN_CACHE; // DMA 内存保证128字节对齐 for (size_t i = 0; i < CLASS_LEN(piles_names_dma); i++) { int size = 1 << (i + 7); + if (size >= EXTERN_THRESHOLD) { + opts |= PILE_FL_EXTERN; + } piles_dma[i] = cake_new_pile( - piles_names_dma[i], size, size > 1024 ? 4 : 1, PILE_ALIGN_CACHE); + piles_names_dma[i], size, page_counts[M128 + i], opts); } } -- 2.27.0