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 quite 'rigid' 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 static struct cake_pile master_pile, fl_pile, cakes;
  24
  25 struct llist_header piles = { .next = &piles, .prev = &piles };
  26
  27 static inline bool
  28 embedded_pile(struct cake_pile* pile)
  29 {
  30     return !(pile->options & PILE_FL_EXTERN);
  31 }
  32
  33 static void*
  34 __alloc_cake_pages(unsigned int cake_pg)
  35 {
  36     struct leaflet* leaflet = alloc_leaflet(count_order(cake_pg));
  37     if (!leaflet) {
  38         return NULL;
  39     }
  40
  41     return (void*)vmap(leaflet, KERNEL_DATA);
  42 }
  43
  44 static struct cake_fl*
  45 __alloc_fl(piece_t prev_id, piece_t max_len) {
  46     unsigned int i, j;
  47     struct cake_fl* cake_fl;
  48
  49     cake_fl = cake_grab(&fl_pile);
  50     for (i = 0, j=prev_id; i < CAKE_FL_MAXLEN && j < max_len; i++, j++)
  51     {
  52         cake_fl->indices[i] = j + 1;
  53     }
  54
  55     for (i -= 1; j == max_len && i < CAKE_FL_SIZE; i++) {
  56         cake_fl->indices[i] = EO_FREE_PIECE;
  57     }
  58
  59     cake_fl->next = NULL;
  60     return cake_fl;
  61 }
  62
  63 static void
  64 __free_fls(struct cake_s* cake) {
  65     unsigned int i, j;
  66     struct cake_fl *cake_fl, *next;
  67
  68     cake_fl = cake->fl;
  69     while (cake_fl)
  70     {
  71         next = cake_fl->next;
  72         cake_release(&fl_pile, cake_fl);
  73         cake_fl = next;
  74     }
  75
  76     cake->fl = NULL;
  77 }
  78
  79 static piece_t*
  80 __fl_slot(struct cake_s* cake, piece_t index)
  81 {
  82     int id_acc;
  83     struct cake_fl* cake_fl;
  84     struct cake_pile* pile;
  85
  86     pile = cake->owner;
  87     if (embedded_pile(pile)) {
  88         return &cake->free_list[index];
  89     }
  90
  91     id_acc = 0;
  92     cake_fl = cake->fl;
  93     while (index >= CAKE_FL_MAXLEN)
  94     {
  95         index  -= CAKE_FL_MAXLEN;
  96         id_acc += CAKE_FL_MAXLEN;
  97
  98         if (cake_fl->next) {
  99             cake_fl = cake_fl->next;
 100             continue;
 101         }
 102
 103         cake_fl = __alloc_fl(id_acc, pile->pieces_per_cake);
 104         cake_fl->next = cake_fl;
 105     }
 106
 107     return &cake_fl->indices[index];
 108 }
 109
 110 static inline struct cake_s*
 111 __create_cake_extern(struct cake_pile* pile)
 112 {
 113     struct cake_s* cake;
 114
 115     cake = cake_grab(&cakes);
 116     if (unlikely(!cake)) {
 117         return NULL;
 118     }
 119
 120     cake->first_piece = __alloc_cake_pages(pile->pg_per_cake);
 121     cake->fl = __alloc_fl(0, pile->pieces_per_cake);
 122     cake->next_free = 0;
 123
 124     return cake;
 125 }
 126
 127 static inline struct cake_s*
 128 __create_cake_embed(struct cake_pile* pile)
 129 {
 130     struct cake_s* cake;
 131
 132     cake = __alloc_cake_pages(pile->pg_per_cake);
 133     if (unlikely(!cake)) {
 134         return NULL;
 135     }
 136
 137     u32_t max_piece = pile->pieces_per_cake;
 138
 139     assert(max_piece);
 140
 141     cake->first_piece = (void*)((ptr_t)cake + pile->offset);
 142     cake->next_free = 0;
 143
 144     piece_t* free_list = cake->free_list;
 145     for (size_t i = 0; i < max_piece - 1; i++) {
 146         free_list[i] = i + 1;
 147     }
 148     free_list[max_piece - 1] = EO_FREE_PIECE;
 149
 150     return cake;
 151 }
 152
 153 static struct cake_s*
 154 __new_cake(struct cake_pile* pile)
 155 {
 156     struct cake_s* cake;
 157
 158     if (embedded_pile(pile)) {
 159         cake = __create_cake_embed(pile);
 160     }
 161     else {
 162         cake = __create_cake_extern(pile);
 163     }
 164
 165     cake->owner = pile;
 166     pile->cakes_count++;
 167     llist_append(&pile->free, &cake->cakes);
 168
 169     return cake;
 170 }
 171
 172 static void
 173 __init_pile(struct cake_pile* pile,
 174             char* name,
 175             unsigned int piece_size,
 176             unsigned int pg_per_cake,
 177             int options)
 178 {
 179     if (!pile) {
 180         return;
 181     }
 182
 183     unsigned int offset = sizeof(long);
 184
 185     // 默认每块儿蛋糕对齐到地址总线宽度
 186     if ((options & PILE_ALIGN_CACHE)) {
 187         // 对齐到128字节缓存行大小，主要用于DMA
 188         offset = CACHE_LINE_SIZE;
 189     }
 190
 191     piece_size = ROUNDUP(piece_size, offset);
 192     *pile = (struct cake_pile){ .piece_size = piece_size,
 193                                 .cakes_count = 0,
 194                                 .options = options,
 195                                 .pg_per_cake = pg_per_cake };
 196
 197     if (!embedded_pile(pile)) {
 198         pile->offset = 0;
 199         pile->pieces_per_cake = (pg_per_cake * PAGE_SIZE) / piece_size;
 200     }
 201     else {
 202         unsigned int free_list_size;
 203
 204         pile->pieces_per_cake
 205             = (pg_per_cake * PAGE_SIZE) /
 206               (piece_size + sizeof(piece_t));
 207
 208         free_list_size
 209             = pile->pieces_per_cake * sizeof(piece_t);
 210
 211         pile->offset
 212             = ROUNDUP(sizeof(struct cake_s) + free_list_size, offset);
 213         pile->pieces_per_cake
 214             -= ICEIL((pile->offset - free_list_size), piece_size);
 215     }
 216
 217     strncpy(pile->pile_name, name, PILE_NAME_MAXLEN);
 218
 219     llist_init_head(&pile->free);
 220     llist_init_head(&pile->full);
 221     llist_init_head(&pile->partial);
 222     llist_append(&piles, &pile->piles);
 223 }
 224
 225 static void
 226 __destory_cake(struct cake_s* cake)
 227 {
 228     // Pinkie Pie is going to MAD!
 229
 230     struct leaflet* leaflet;
 231     struct cake_pile* owner;
 232     pfn_t _pfn;
 233     ptr_t page_va;
 234
 235     owner = cake->owner;
 236     assert(!cake->used_pieces);
 237
 238     llist_delete(&cake->cakes);
 239     owner->cakes_count--;
 240
 241     if (!embedded_pile(owner)) {
 242         page_va = __ptr(cake->first_piece);
 243         __free_fls(cake);
 244         cake_release(&cakes, cake);
 245     }
 246     else {
 247         page_va = __ptr(cake);
 248     }
 249
 250     _pfn = pfn(vmm_v2p(page_va));
 251     leaflet = ppfn_leaflet(_pfn);
 252     vunmap(page_va, leaflet);
 253
 254     leaflet_return(leaflet);
 255 }
 256
 257 void
 258 cake_init()
 259 {
 260     // pinkamina is our master, no one shall precede her.
 261     __init_pile(&master_pile, "pinkamina",
 262                 sizeof(master_pile), 1, 0);
 263
 264     __init_pile(&fl_pile, "gummy", \
 265                 sizeof(struct cake_fl), 1, 0);
 266     __init_pile(&cakes, "cakes", \
 267                 sizeof(struct cake_s), 1, 0);
 268 }
 269
 270 struct cake_pile*
 271 cake_new_pile(char* name,
 272               unsigned int piece_size,
 273               unsigned int pg_per_cake,
 274               int options)
 275 {
 276     struct cake_pile* pile = (struct cake_pile*)cake_grab(&master_pile);
 277
 278     // must aligned to napot order!
 279     assert(is_pot(pg_per_cake));
 280
 281     __init_pile(pile, name, piece_size, pg_per_cake, options);
 282
 283     return pile;
 284 }
 285
 286 void
 287 cake_set_constructor(struct cake_pile* pile, pile_cb ctor)
 288 {
 289     pile->ctor = ctor;
 290 }
 291
 292 void*
 293 cake_grab(struct cake_pile* pile)
 294 {
 295     struct cake_s *pos, *n;
 296     if (!llist_empty(&pile->partial)) {
 297         pos = list_entry(pile->partial.next, typeof(*pos), cakes);
 298     } else if (llist_empty(&pile->free)) {
 299         pos = __new_cake(pile);
 300     } else {
 301         pos = list_entry(pile->free.next, typeof(*pos), cakes);
 302     }
 303
 304     if (!pos)
 305         return NULL;
 306
 307     void* piece;
 308     piece_t found_index, *fl_slot;
 309
 310     found_index = pos->next_free;
 311     fl_slot = __fl_slot(pos, found_index);
 312
 313     pos->next_free = *fl_slot;
 314     pos->used_pieces++;
 315     pile->alloced_pieces++;
 316
 317     llist_delete(&pos->cakes);
 318
 319     fl_slot = __fl_slot(pos, pos->next_free);
 320     if (*fl_slot == EO_FREE_PIECE) {
 321         llist_append(&pile->full, &pos->cakes);
 322     } else {
 323         llist_append(&pile->partial, &pos->cakes);
 324     }
 325
 326     piece =
 327       (void*)(__ptr(pos->first_piece) + found_index * pile->piece_size);
 328
 329     if (pile->ctor) {
 330         pile->ctor(pile, piece);
 331     }
 332
 333     return piece;
 334 }
 335
 336 int
 337 cake_release(struct cake_pile* pile, void* area)
 338 {
 339     piece_t piece_index;
 340     size_t dsize = 0, maybe_index;
 341
 342     piece_t *fl_slot;
 343     struct cake_s *pos, *n;
 344     struct llist_header* hdrs[2] = { &pile->full, &pile->partial };
 345
 346     for (size_t i = 0; i < 2; i++) {
 347         llist_for_each(pos, n, hdrs[i], cakes)
 348         {
 349             if (pos->first_piece > area) {
 350                 continue;
 351             }
 352
 353             dsize = __ptr(area - pos->first_piece);
 354             maybe_index = dsize / pile->piece_size;
 355
 356             if (maybe_index < pile->pieces_per_cake) {
 357                 piece_index = (piece_t)maybe_index;
 358                 goto found;
 359             }
 360         }
 361     }
 362
 363     return 0;
 364
 365 found:
 366     assert(!(dsize % pile->piece_size));
 367
 368     assert_msg(piece_index != pos->next_free, "double free");
 369
 370     fl_slot = __fl_slot(pos, piece_index);
 371     *fl_slot = pos->next_free;
 372     pos->next_free = piece_index;
 373
 374     pos->used_pieces--;
 375     pile->alloced_pieces--;
 376
 377     llist_delete(&pos->cakes);
 378     if (!pos->used_pieces) {
 379         llist_append(&pile->free, &pos->cakes);
 380     } else {
 381         llist_append(&pile->partial, &pos->cakes);
 382     }
 383
 384     *((unsigned int*)area) = DEADCAKE_MARK;
 385
 386     return 1;
 387 }
 388
 389 void
 390 cake_ctor_zeroing(struct cake_pile* pile, void* piece)
 391 {
 392     memset(piece, 0, pile->piece_size);
 393 }
 394
 395 static inline void
 396 __reclaim(struct cake_pile *pile)
 397 {
 398     struct cake_s *pos, *n;
 399     llist_for_each(pos, n, &pile->free, cakes)
 400     {
 401         __destory_cake(pos);
 402     }
 403 }
 404
 405 void
 406 cake_reclaim_freed()
 407 {
 408     struct cake_pile *pos, *n;
 409     llist_for_each(pos, n, &master_pile.piles, piles)
 410     {
 411         __reclaim(pos);
 412     }
 413 }