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

diff --git a/lunaix-os/includes/lunaix/mm/cake.h b/lunaix-os/includes/lunaix/mm/cake.h
index cf1c16e63c49bdf89fcf6db10c8c6b6cf3d6c1e4..d880531399d1d06d42cad3a59c6f463e3e14afc3 100644 (file)
--- 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_NAME_MAXLEN 20
 

-#define PILE_ALIGN_CACHE 1
+#define PILE_ALIGN_CACHE 0b0001
+#define PILE_FL_EXTERN   0b0010

 
 struct cake_pile;
 
 
 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 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;
 };
 
     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_s
 {
     struct llist_header cakes;

+    struct cake_pile* owner;

     void* first_piece;
     unsigned int used_pieces;
     unsigned int next_free;
     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_export();
 

+void
+cake_reclaim_freed();
+

 /********** some handy constructor ***********/
 
 void
 /********** some handy constructor ***********/
 
 void

diff --git a/lunaix-os/kernel/mm/cake.c b/lunaix-os/kernel/mm/cake.c
index d9ef3810d5c5831aaaa05d81e889df2df38f6698..b1e699f5307f67f43aae9d5dc60701ba921436d2 100644 (file)
--- 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.
  * @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
  *
  * @version 0.1
  * @date 2022-07-02
  *


@@ -20,12 +20,18 @@ LOG_MODULE("CAKE")
 
 #define CACHE_LINE_SIZE 128
 
 
 #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 };
 
 
 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) {
 {
     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);
 }
 
     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);
         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;
     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;
 
     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;
 }
 
     llist_append(&pile->free, &cake->cakes);
 
     return cake;
 }
 

-void
+static void

 __init_pile(struct cake_pile* pile,
             char* name,
             unsigned int piece_size,
 __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,
     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 };
 
                                 .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);
 
 
     strncpy(pile->pile_name, name, PILE_NAME_MAXLEN);
 


@@ -103,10 +222,49 @@ __init_pile(struct cake_pile* pile,
     llist_append(&piles, &pile->piles);
 }
 
     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()
 {
 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*
 }
 
 struct cake_pile*


@@ -145,33 +303,40 @@ cake_grab(struct cake_pile* pile)
 
     if (!pos)
         return NULL;
 
     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);
     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);
     }
 
         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) {
 
     if (pile->ctor) {

-        pile->ctor(pile, ptr);
+        pile->ctor(pile, piece);

     }
 
     }
 

-    return ptr;
+    return piece;

 }
 
 int
 cake_release(struct cake_pile* pile, void* area)
 {
 }
 
 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 };
     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));
 
 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;
 
     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--;
 
     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);
 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
 }
\ 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 377a9adea8b06d2cf23ee93c5f565942cf64c8bf..e2ecb3a54eb5d15da635f4be7f99b3140a25c6d5 100644 (file)
--- 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);
 __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
 }
 
 void


@@ -26,10 +26,11 @@ __cake_rd_stat(struct twimap* map)
 {
     struct cake_pile* pos = twimap_index(map, struct cake_pile*);
     twimap_printf(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->pile_name,
                   pos->cakes_count,
                   pos->pg_per_cake,

+                  pos->piece_size,

                   pos->pieces_per_cake,
                   pos->alloced_pieces);
 }
                   pos->pieces_per_cake,
                   pos->alloced_pieces);
 }

diff --git a/lunaix-os/kernel/mm/valloc.c b/lunaix-os/kernel/mm/valloc.c
index 67c8eacb3f43f45b8b68c421e72c5f157c33583e..d2baa352b05ee81f231b0739c75caa022ec175b4 100644 (file)
--- 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]))
 
 
 #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",
 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"  
 };
 
     "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",
 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()
 {
 void
 valloc_init()
 {

+    int opts = 0;

     for (size_t i = 0; i < CLASS_LEN(piles_names); i++) {
         int size = 1 << (i + 3);
     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);
     // 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_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);

     }
 }
 
     }
 }