* @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
*
#include <klibc/string.h>
#include <lunaix/mm/cake.h>
-#include <lunaix/mm/pmm.h>
-#include <lunaix/mm/vmm.h>
+#include <lunaix/mm/page.h>
#include <lunaix/spike.h>
#include <lunaix/syslog.h>
#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)
{
- uintptr_t pa = pmm_alloc_cpage(KERNEL_PID, cake_pg, 0);
- if (!pa) {
+ 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) {
return NULL;
}
- return vmm_vmap(pa, cake_pg * PG_SIZE, PG_PREM_RW);
+
+ 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)
{
- struct cake_s* cake = __alloc_cake(pile->pg_per_cake);
+ int id_acc;
+ struct cake_fl* cake_fl;
+ struct cake_pile* pile;
- if (!cake) {
+ 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;
+
+ cake = cake_grab(&cakes);
+ if (unlikely(!cake)) {
+ return NULL;
+ }
+
+ 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;
}
- int max_piece = pile->pieces_per_cake;
+ u32_t max_piece = pile->pieces_per_cake;
- cake->first_piece = (void*)((uintptr_t)cake + pile->offset);
+ 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,
unsigned int offset = sizeof(long);
// 默认每块儿蛋糕对齐到地址总线宽度
- if ((options & PILE_CACHELINE)) {
+ if ((options & PILE_ALIGN_CACHE)) {
// 对齐到128字节缓存行大小，主要用于DMA
offset = CACHE_LINE_SIZE;
}
piece_size = ROUNDUP(piece_size, offset);
*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)),
+ .cakes_count = 0,
+ .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);
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*
{
struct cake_pile* pile = (struct cake_pile*)cake_grab(&master_pile);
+ // must aligned to napot order!
+ assert(is_pot(pg_per_cake));
+
__init_pile(pile, name, piece_size, pg_per_cake, options);
return pile;
if (!pos)
return NULL;
- piece_index_t found_index = pos->next_free;
- pos->next_free = pos->free_list[found_index];
+ void* piece;
+ piece_t found_index, *fl_slot;
+
+ found_index = pos->next_free;
+ fl_slot = __fl_slot(pos, found_index);
+
+ pos->next_free = *fl_slot;
pos->used_pieces++;
pile->alloced_pieces++;
llist_delete(&pos->cakes);
- if (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*)((uintptr_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, maybe_index;
+
+ piece_t *fl_slot;
struct cake_s *pos, *n;
struct llist_header* hdrs[2] = { &pile->full, &pile->partial };
if (pos->first_piece > area) {
continue;
}
- piece_index =
- (uintptr_t)(area - pos->first_piece) / pile->piece_size;
- if (piece_index < pile->pieces_per_cake) {
+
+ dsize = __ptr(area - pos->first_piece);
+ maybe_index = dsize / pile->piece_size;
+
+ if (maybe_index < pile->pieces_per_cake) {
+ piece_index = (piece_t)maybe_index;
goto found;
}
}
return 0;
found:
- pos->free_list[piece_index] = pos->next_free;
+ assert(!(dsize % pile->piece_size));
+
+ assert_msg(piece_index != pos->next_free, "double free");
+
+ fl_slot = __fl_slot(pos, piece_index);
+ *fl_slot = pos->next_free;
pos->next_free = piece_index;
+
pos->used_pieces--;
pile->alloced_pieces--;
llist_append(&pile->partial, &pos->cakes);
}
+ *((unsigned int*)area) = DEADCAKE_MARK;
+
return 1;
}
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
git://scm.lunaixsky.com / lunaix-os.git / blobdiff