lunaix-os/kernel/mm/cake.c

   1 /**
   2  * @file cake.c
   3  * @author Lunaixsky (zelong56@gmail.com)
   4  * @brief A simplified cake(slab) allocator.
   5  *          P.s. I call it cake as slab sounds more 'ridge' to me. :)
   6  * @version 0.1
   7  * @date 2022-07-02
   8  *
   9  * @copyright Copyright (c) 2022
  10  *
  11  */
  12
  13 #include <klibc/string.h>
  14 #include <lunaix/mm/cake.h>
  15 #include <lunaix/mm/page.h>
  16 #include <lunaix/spike.h>
  17 #include <lunaix/syslog.h>
  18
  19 LOG_MODULE("CAKE")
  20
  21 #define CACHE_LINE_SIZE 128
  22
  23 struct cake_pile master_pile;
  24
  25 struct llist_header piles = { .next = &piles, .prev = &piles };
  26
  27 void*
  28 __alloc_cake(unsigned int cake_pg)
  29 {
  30     struct leaflet* leaflet = alloc_leaflet(count_order(cake_pg));
  31     if (!leaflet) {
  32         return NULL;
  33     }
  34
  35     return (void*)vmap(leaflet, KERNEL_DATA);
  36 }
  37
  38 struct cake_s*
  39 __new_cake(struct cake_pile* pile)
  40 {
  41     struct cake_s* cake = __alloc_cake(pile->pg_per_cake);
  42
  43     if (!cake) {
  44         return NULL;
  45     }
  46
  47     u32_t max_piece = pile->pieces_per_cake;
  48
  49     assert(max_piece);
  50
  51     cake->first_piece = (void*)((ptr_t)cake + pile->offset);
  52     cake->next_free = 0;
  53     pile->cakes_count++;
  54
  55     piece_index_t* free_list = cake->free_list;
  56     for (size_t i = 0; i < max_piece - 1; i++) {
  57         free_list[i] = i + 1;
  58     }
  59     free_list[max_piece - 1] = EO_FREE_PIECE;
  60
  61     llist_append(&pile->free, &cake->cakes);
  62
  63     return cake;
  64 }
  65
  66 void
  67 __init_pile(struct cake_pile* pile,
  68             char* name,
  69             unsigned int piece_size,
  70             unsigned int pg_per_cake,
  71             int options)
  72 {
  73     if (!pile) {
  74         return;
  75     }
  76
  77     unsigned int offset = sizeof(long);
  78
  79     // 默认每块儿蛋糕对齐到地址总线宽度
  80     if ((options & PILE_ALIGN_CACHE)) {
  81         // 对齐到128字节缓存行大小，主要用于DMA
  82         offset = CACHE_LINE_SIZE;
  83     }
  84
  85     piece_size = ROUNDUP(piece_size, offset);
  86     *pile = (struct cake_pile){ .piece_size = piece_size,
  87                                 .cakes_count = 0,
  88                                 .pieces_per_cake =
  89                                   (pg_per_cake * PAGE_SIZE) /
  90                                   (piece_size + sizeof(piece_index_t)),
  91                                 .pg_per_cake = pg_per_cake };
  92
  93     unsigned int free_list_size = pile->pieces_per_cake * sizeof(piece_index_t);
  94
  95     pile->offset = ROUNDUP(sizeof(struct cake_s) + free_list_size, offset);
  96     pile->pieces_per_cake -= ICEIL((pile->offset - free_list_size), piece_size);
  97
  98     strncpy(pile->pile_name, name, PILE_NAME_MAXLEN);
  99
 100     llist_init_head(&pile->free);
 101     llist_init_head(&pile->full);
 102     llist_init_head(&pile->partial);
 103     llist_append(&piles, &pile->piles);
 104 }
 105
 106 void
 107 cake_init()
 108 {
 109     __init_pile(&master_pile, "pinkamina", sizeof(master_pile), 1, 0);
 110 }
 111
 112 struct cake_pile*
 113 cake_new_pile(char* name,
 114               unsigned int piece_size,
 115               unsigned int pg_per_cake,
 116               int options)
 117 {
 118     struct cake_pile* pile = (struct cake_pile*)cake_grab(&master_pile);
 119
 120     // must aligned to napot order!
 121     assert(is_pot(pg_per_cake));
 122
 123     __init_pile(pile, name, piece_size, pg_per_cake, options);
 124
 125     return pile;
 126 }
 127
 128 void
 129 cake_set_constructor(struct cake_pile* pile, pile_cb ctor)
 130 {
 131     pile->ctor = ctor;
 132 }
 133
 134 void*
 135 cake_grab(struct cake_pile* pile)
 136 {
 137     struct cake_s *pos, *n;
 138     if (!llist_empty(&pile->partial)) {
 139         pos = list_entry(pile->partial.next, typeof(*pos), cakes);
 140     } else if (llist_empty(&pile->free)) {
 141         pos = __new_cake(pile);
 142     } else {
 143         pos = list_entry(pile->free.next, typeof(*pos), cakes);
 144     }
 145
 146     if (!pos)
 147         return NULL;
 148
 149     piece_index_t found_index = pos->next_free;
 150     pos->next_free = pos->free_list[found_index];
 151     pos->used_pieces++;
 152     pile->alloced_pieces++;
 153
 154     llist_delete(&pos->cakes);
 155     if (pos->free_list[pos->next_free] == EO_FREE_PIECE) {
 156         llist_append(&pile->full, &pos->cakes);
 157     } else {
 158         llist_append(&pile->partial, &pos->cakes);
 159     }
 160
 161     void* ptr =
 162       (void*)((ptr_t)pos->first_piece + found_index * pile->piece_size);
 163
 164     if (pile->ctor) {
 165         pile->ctor(pile, ptr);
 166     }
 167
 168     return ptr;
 169 }
 170
 171 int
 172 cake_release(struct cake_pile* pile, void* area)
 173 {
 174     piece_index_t piece_index;
 175     size_t dsize = 0;
 176     struct cake_s *pos, *n;
 177     struct llist_header* hdrs[2] = { &pile->full, &pile->partial };
 178
 179     for (size_t i = 0; i < 2; i++) {
 180         llist_for_each(pos, n, hdrs[i], cakes)
 181         {
 182             if (pos->first_piece > area) {
 183                 continue;
 184             }
 185             dsize = (ptr_t)(area - pos->first_piece);
 186             piece_index = dsize / pile->piece_size;
 187             if (piece_index < pile->pieces_per_cake) {
 188                 goto found;
 189             }
 190         }
 191     }
 192
 193     return 0;
 194
 195 found:
 196     assert(!(dsize % pile->piece_size));
 197     pos->free_list[piece_index] = pos->next_free;
 198     pos->next_free = piece_index;
 199
 200     assert_msg(pos->free_list[piece_index] != pos->next_free, "double free");
 201
 202     pos->used_pieces--;
 203     pile->alloced_pieces--;
 204
 205     llist_delete(&pos->cakes);
 206     if (!pos->used_pieces) {
 207         llist_append(&pile->free, &pos->cakes);
 208     } else {
 209         llist_append(&pile->partial, &pos->cakes);
 210     }
 211
 212     *((unsigned int*)area) = DEADCAKE_MARK;
 213
 214     return 1;
 215 }
 216
 217 void
 218 cake_ctor_zeroing(struct cake_pile* pile, void* piece)
 219 {
 220     memset(piece, 0, pile->piece_size);
 221 }