+
+/**** DO NOT USE ****/
+
/**
* @file kalloc.c
* @author Lunaixsky
* @copyright Copyright (c) 2022
*
*/
-#include <lunaix/mm/dmm.h>
-#include <lunaix/mm/kalloc.h>
-#include <lunaix/mm/vmm.h>
-
-#include <lunaix/common.h>
-#include <lunaix/spike.h>
-
-#include <klibc/string.h>
+// #include <lunaix/mm/dmm.h>
+// #include <lunaix/mm/kalloc.h>
+// #include <lunaix/mm/vmm.h>
-#include <stdint.h>
+// #include <lunaix/common.h>
+// #include <lunaix/spike.h>
-extern uint8_t __kernel_heap_start;
+// #include <klibc/string.h>
-void*
-lx_malloc_internal(heap_context_t* heap, size_t size);
-
-void
-place_chunk(uint8_t* ptr, size_t size);
+// #include <stdint.h>
-void
-lx_free_internal(void* ptr);
+// extern uint8_t __kernel_heap_start;
+
+// void*
+// lx_malloc_internal(heap_context_t* heap, size_t size);
+
+// void
+// place_chunk(uint8_t* ptr, size_t size);
-void*
-coalesce(uint8_t* chunk_ptr);
+// void
+// lx_free_internal(void* ptr);
-void*
-lx_grow_heap(heap_context_t* heap, size_t sz);
+// void*
+// coalesce(uint8_t* chunk_ptr);
+
+// void*
+// lx_grow_heap(heap_context_t* heap, size_t sz);
-/*
- At the beginning, we allocate an empty page and put our initial marker
+// /*
+// At the beginning, we allocate an empty page and put our initial marker
- | 4/1 | 0/1 |
- ^ ^ brk
- start
+// | 4/1 | 0/1 |
+// ^ ^ brk
+// start
- Then, expand the heap further, with HEAP_INIT_SIZE (evaluated to 4096, i.e.,
- 1 pg size) This will allocate as much pages and override old epilogue marker
- with a free region hdr and put new epilogue marker. These are handled by
- lx_grow_heap which is internally used by alloc to expand the heap at many
- moment when needed.
+// Then, expand the heap further, with HEAP_INIT_SIZE (evaluated to 4096,
+// i.e.,
+// 1 pg size) This will allocate as much pages and override old epilogue
+// marker with a free region hdr and put new epilogue marker. These are
+// handled by lx_grow_heap which is internally used by alloc to expand the
+// heap at many moment when needed.
- | 4/1 | 4096/0 | ....... | 4096/0 | 0/1 |
- ^ ^ brk_old ^
- start brk
+// | 4/1 | 4096/0 | ....... | 4096/0 | 0/1 |
+// ^ ^ brk_old ^
+// start brk
- Note: the brk always point to the beginning of epilogue.
-*/
+// Note: the brk always point to the beginning of epilogue.
+// */
-static heap_context_t kheap;
+// static heap_context_t kheap;
-int
-kalloc_init()
-{
- kheap.start = KHEAP_START;
- kheap.brk = NULL;
- kheap.max_addr =
- (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方
-
- for (size_t i = 0; i < KHEAP_SIZE_MB >> 2; i++) {
- vmm_set_mapping(PD_REFERENCED,
- (uintptr_t)kheap.start + (i << 22),
- 0,
- PG_PREM_RW,
- VMAP_NOMAP);
- }
-
- if (!dmm_init(&kheap)) {
- return 0;
- }
-
- SW(kheap.start, PACK(4, M_ALLOCATED));
- SW(kheap.start + WSIZE, PACK(0, M_ALLOCATED));
- kheap.brk += WSIZE;
-
- return lx_grow_heap(&kheap, HEAP_INIT_SIZE) != NULL;
-}
-
-void*
-lxmalloc(size_t size)
-{
- mutex_lock(&kheap.lock);
- void* r = lx_malloc_internal(&kheap, size);
- mutex_unlock(&kheap.lock);
-
- return r;
-}
-
-void*
-lxcalloc(size_t n, size_t elem)
-{
- size_t pd = n * elem;
-
- // overflow detection
- if (pd < elem || pd < n) {
- return NULL;
- }
-
- void* ptr = lxmalloc(pd);
- if (!ptr) {
- return NULL;
- }
-
- return memset(ptr, 0, pd);
-}
-
-void
-lxfree(void* ptr)
-{
- if (!ptr) {
- return;
- }
- mutex_lock(&kheap.lock);
-
- uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
- uint32_t hdr = LW(chunk_ptr);
- size_t sz = CHUNK_S(hdr);
- uint8_t* next_hdr = chunk_ptr + sz;
-
- // make sure the ptr we are 'bout to free makes sense
- // the size trick is stolen from glibc's malloc/malloc.c:4437 ;P
-
- assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr & 0x3),
- "free(): invalid pointer");
-
- assert_msg(sz > WSIZE, "free(): invalid size");
-
- SW(chunk_ptr, hdr & ~M_ALLOCATED);
- SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED);
- SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
-
- coalesce(chunk_ptr);
-
- mutex_unlock(&kheap.lock);
-}
-
-void*
-lx_malloc_internal(heap_context_t* heap, size_t size)
-{
- // Simplest first fit approach.
-
- if (!size) {
- return NULL;
- }
-
- uint8_t* ptr = heap->start;
- // round to largest 4B aligned value
- // and space for header
- size = ROUNDUP(size + WSIZE, BOUNDARY);
- while (ptr < (uint8_t*)heap->brk) {
- uint32_t header = *((uint32_t*)ptr);
- size_t chunk_size = CHUNK_S(header);
- if (!chunk_size && CHUNK_A(header)) {
- break;
- }
- if (chunk_size >= size && !CHUNK_A(header)) {
- // found!
- place_chunk(ptr, size);
- return BPTR(ptr);
- }
- ptr += chunk_size;
- }
-
- // if heap is full (seems to be!), then allocate more space (if it's
- // okay...)
- if ((ptr = lx_grow_heap(heap, size))) {
- place_chunk(ptr, size);
- return BPTR(ptr);
- }
-
- // Well, we are officially OOM!
- return NULL;
-}
-
-void
-place_chunk(uint8_t* ptr, size_t size)
-{
- uint32_t header = *((uint32_t*)ptr);
- size_t chunk_size = CHUNK_S(header);
- *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
- uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
- uint32_t diff = chunk_size - size;
-
- if (!diff) {
- // if the current free block is fully occupied
- uint32_t n_hdr = LW(n_hdrptr);
- // notify the next block about our avaliability
- SW(n_hdrptr, n_hdr & ~0x2);
- } else {
- // if there is remaining free space left
- uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
- SW(n_hdrptr, remainder_hdr);
- SW(FPTR(n_hdrptr, diff), remainder_hdr);
-
- /*
- | xxxx | | |
-
- |
- v
-
- | xxxx | |
- */
- coalesce(n_hdrptr);
- }
-}
-
-void*
-coalesce(uint8_t* chunk_ptr)
-{
- uint32_t hdr = LW(chunk_ptr);
- uint32_t pf = CHUNK_PF(hdr);
- uint32_t sz = CHUNK_S(hdr);
-
- uint32_t n_hdr = LW(chunk_ptr + sz);
-
- if (CHUNK_A(n_hdr) && pf) {
- // case 1: prev is free
- uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
- size_t prev_chunk_sz = CHUNK_S(prev_ftr);
- uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
- SW(chunk_ptr - prev_chunk_sz, new_hdr);
- SW(FPTR(chunk_ptr, sz), new_hdr);
- chunk_ptr -= prev_chunk_sz;
- } else if (!CHUNK_A(n_hdr) && !pf) {
- // case 2: next is free
- size_t next_chunk_sz = CHUNK_S(n_hdr);
- uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
- SW(chunk_ptr, new_hdr);
- SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
- } else if (!CHUNK_A(n_hdr) && pf) {
- // case 3: both free
- uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
- size_t next_chunk_sz = CHUNK_S(n_hdr);
- size_t prev_chunk_sz = CHUNK_S(prev_ftr);
- uint32_t new_hdr =
- PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
- SW(chunk_ptr - prev_chunk_sz, new_hdr);
- SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
- chunk_ptr -= prev_chunk_sz;
- }
-
- // (fall through) case 4: prev and next are not free
- return chunk_ptr;
-}
-
-void*
-lx_grow_heap(heap_context_t* heap, size_t sz)
-{
- void* start;
-
- // The "+ WSIZE" capture the overhead for epilogue marker
- if (!(start = lxsbrk(heap, sz + WSIZE, 0))) {
- return NULL;
- }
- sz = ROUNDUP(sz, BOUNDARY);
-
- // minus the overhead for epilogue, keep the invariant.
- heap->brk -= WSIZE;
-
- uint32_t old_marker = *((uint32_t*)start);
- uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
- SW(start, free_hdr);
- SW(FPTR(start, sz), free_hdr);
- SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
-
- return coalesce(start);
-}
\ No newline at end of file
+// int
+// kalloc_init()
+// {
+// kheap.start = KHEAP_START;
+// kheap.brk = NULL;
+// kheap.max_addr =
+// (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方
+
+// for (size_t i = 0; i < KHEAP_SIZE_MB >> 2; i++) {
+// vmm_set_mapping(PD_REFERENCED,
+// (uintptr_t)kheap.start + (i << 22),
+// 0,
+// PG_PREM_RW,
+// VMAP_NOMAP);
+// }
+
+// if (!dmm_init(&kheap)) {
+// return 0;
+// }
+
+// SW(kheap.start, PACK(4, M_ALLOCATED));
+// SW(kheap.start + WSIZE, PACK(0, M_ALLOCATED));
+// kheap.brk += WSIZE;
+
+// return lx_grow_heap(&kheap, HEAP_INIT_SIZE) != NULL;
+// }
+
+// void*
+// lxmalloc(size_t size)
+// {
+// mutex_lock(&kheap.lock);
+// void* r = lx_malloc_internal(&kheap, size);
+// mutex_unlock(&kheap.lock);
+
+// return r;
+// }
+
+// void*
+// lxcalloc(size_t n, size_t elem)
+// {
+// size_t pd = n * elem;
+
+// // overflow detection
+// if (pd < elem || pd < n) {
+// return NULL;
+// }
+
+// void* ptr = lxmalloc(pd);
+// if (!ptr) {
+// return NULL;
+// }
+
+// return memset(ptr, 0, pd);
+// }
+
+// void
+// lxfree(void* ptr)
+// {
+// if (!ptr) {
+// return;
+// }
+// mutex_lock(&kheap.lock);
+
+// uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
+// uint32_t hdr = LW(chunk_ptr);
+// size_t sz = CHUNK_S(hdr);
+// uint8_t* next_hdr = chunk_ptr + sz;
+
+// // make sure the ptr we are 'bout to free makes sense
+// // the size trick is stolen from glibc's malloc/malloc.c:4437 ;P
+
+// assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr &
+// 0x3),
+// "free(): invalid pointer");
+
+// assert_msg(sz > WSIZE, "free(): invalid size");
+
+// SW(chunk_ptr, hdr & ~M_ALLOCATED);
+// SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED);
+// SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
+
+// coalesce(chunk_ptr);
+
+// mutex_unlock(&kheap.lock);
+// }
+
+// void*
+// lx_malloc_internal(heap_context_t* heap, size_t size)
+// {
+// // Simplest first fit approach.
+
+// if (!size) {
+// return NULL;
+// }
+
+// uint8_t* ptr = heap->start;
+// // round to largest 4B aligned value
+// // and space for header
+// size = ROUNDUP(size + WSIZE, BOUNDARY);
+// while (ptr < (uint8_t*)heap->brk) {
+// uint32_t header = *((uint32_t*)ptr);
+// size_t chunk_size = CHUNK_S(header);
+// if (!chunk_size && CHUNK_A(header)) {
+// break;
+// }
+// if (chunk_size >= size && !CHUNK_A(header)) {
+// // found!
+// place_chunk(ptr, size);
+// return BPTR(ptr);
+// }
+// ptr += chunk_size;
+// }
+
+// // if heap is full (seems to be!), then allocate more space (if it's
+// // okay...)
+// if ((ptr = lx_grow_heap(heap, size))) {
+// place_chunk(ptr, size);
+// return BPTR(ptr);
+// }
+
+// // Well, we are officially OOM!
+// return NULL;
+// }
+
+// void
+// place_chunk(uint8_t* ptr, size_t size)
+// {
+// uint32_t header = *((uint32_t*)ptr);
+// size_t chunk_size = CHUNK_S(header);
+// *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
+// uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
+// uint32_t diff = chunk_size - size;
+
+// if (!diff) {
+// // if the current free block is fully occupied
+// uint32_t n_hdr = LW(n_hdrptr);
+// // notify the next block about our avaliability
+// SW(n_hdrptr, n_hdr & ~0x2);
+// } else {
+// // if there is remaining free space left
+// uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED |
+// M_PREV_ALLOCATED); SW(n_hdrptr, remainder_hdr); SW(FPTR(n_hdrptr,
+// diff), remainder_hdr);
+
+// /*
+// | xxxx | | |
+
+// |
+// v
+
+// | xxxx | |
+// */
+// coalesce(n_hdrptr);
+// }
+// }
+
+// void*
+// coalesce(uint8_t* chunk_ptr)
+// {
+// uint32_t hdr = LW(chunk_ptr);
+// uint32_t pf = CHUNK_PF(hdr);
+// uint32_t sz = CHUNK_S(hdr);
+
+// uint32_t n_hdr = LW(chunk_ptr + sz);
+
+// if (CHUNK_A(n_hdr) && pf) {
+// // case 1: prev is free
+// uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
+// size_t prev_chunk_sz = CHUNK_S(prev_ftr);
+// uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
+// SW(chunk_ptr - prev_chunk_sz, new_hdr);
+// SW(FPTR(chunk_ptr, sz), new_hdr);
+// chunk_ptr -= prev_chunk_sz;
+// } else if (!CHUNK_A(n_hdr) && !pf) {
+// // case 2: next is free
+// size_t next_chunk_sz = CHUNK_S(n_hdr);
+// uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
+// SW(chunk_ptr, new_hdr);
+// SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
+// } else if (!CHUNK_A(n_hdr) && pf) {
+// // case 3: both free
+// uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
+// size_t next_chunk_sz = CHUNK_S(n_hdr);
+// size_t prev_chunk_sz = CHUNK_S(prev_ftr);
+// uint32_t new_hdr =
+// PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
+// SW(chunk_ptr - prev_chunk_sz, new_hdr);
+// SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
+// chunk_ptr -= prev_chunk_sz;
+// }
+
+// // (fall through) case 4: prev and next are not free
+// return chunk_ptr;
+// }
+
+// void*
+// lx_grow_heap(heap_context_t* heap, size_t sz)
+// {
+// void* start;
+
+// // The "+ WSIZE" capture the overhead for epilogue marker
+// if (!(start = lxsbrk(heap, sz + WSIZE, 0))) {
+// return NULL;
+// }
+// sz = ROUNDUP(sz, BOUNDARY);
+
+// // minus the overhead for epilogue, keep the invariant.
+// heap->brk -= WSIZE;
+
+// uint32_t old_marker = *((uint32_t*)start);
+// uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
+// SW(start, free_hdr);
+// SW(FPTR(start, sz), free_hdr);
+// SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
+
+// return coalesce(start);
+// }
\ No newline at end of file
#include <hal/apic.h>
#include <hal/cpu.h>
+#include <lunaix/mm/cake.h>
#include <lunaix/mm/kalloc.h>
#include <lunaix/mm/pmm.h>
#include <lunaix/mm/valloc.h>
#include <lunaix/syscall.h>
#include <lunaix/syslog.h>
-#define MAX_PROCESS 512
+#define PROC_TABLE_SIZE 8192
+#define MAX_PROCESS (PROC_TABLE_SIZE / sizeof(uintptr_t))
volatile struct proc_info* __current;
struct scheduler sched_ctx;
+struct cake_pile* proc_pile;
+
LOG_MODULE("SCHED")
void
sched_init()
{
- size_t pg_size = ROUNDUP(sizeof(struct proc_info) * MAX_PROCESS, 0x1000);
+ // size_t pg_size = ROUNDUP(sizeof(struct proc_info) * MAX_PROCESS, 0x1000);
- for (size_t i = 0; i <= pg_size; i += 4096) {
- uintptr_t pa = pmm_alloc_page(KERNEL_PID, PP_FGPERSIST);
- vmm_set_mapping(
- PD_REFERENCED, PROC_START + i, pa, PG_PREM_RW, VMAP_NULL);
- }
+ // for (size_t i = 0; i <= pg_size; i += 4096) {
+ // uintptr_t pa = pmm_alloc_page(KERNEL_PID, PP_FGPERSIST);
+ // vmm_set_mapping(
+ // PD_REFERENCED, PROC_START + i, pa, PG_PREM_RW, VMAP_NULL);
+ // }
+
+ proc_pile = cake_new_pile("proc", sizeof(struct proc_info), 1, 0);
+ cake_set_constructor(proc_pile, cake_ctor_zeroing);
- sched_ctx = (struct scheduler){ ._procs = (struct proc_info*)PROC_START,
+ sched_ctx = (struct scheduler){ ._procs = vzalloc(PROC_TABLE_SIZE),
.ptable_len = 0,
.procs_index = 0 };
}
void
check_sleepers()
{
- struct proc_info* leader = &sched_ctx._procs[0];
+ struct proc_info* leader = sched_ctx._procs[0];
struct proc_info *pos, *n;
time_t now = clock_systime();
llist_for_each(pos, n, &leader->sleep.sleepers, sleep.sleepers)
redo:
do {
ptr = (ptr + 1) % sched_ctx.ptable_len;
- next = &sched_ctx._procs[ptr];
- } while (next->state != PS_READY && ptr != prev_ptr);
+ next = sched_ctx._procs[ptr];
+ } while (!next || (next->state != PS_READY && ptr != prev_ptr));
sched_ctx.procs_index = ptr;
return (__current->sleep.wakeup_time - clock_systime()) / 1000U;
}
+ struct proc_info* root_proc = sched_ctx._procs[0];
__current->sleep.wakeup_time = clock_systime() + seconds * 1000;
- llist_append(&sched_ctx._procs[0].sleep.sleepers,
- &__current->sleep.sleepers);
+ llist_append(&root_proc->sleep.sleepers, &__current->sleep.sleepers);
__current->intr_ctx.registers.eax = seconds;
__current->state = PS_BLOCKED;
__current->sleep.alarm_time = seconds ? now + seconds * 1000 : 0;
+ struct proc_info* root_proc = sched_ctx._procs[0];
if (llist_empty(&__current->sleep.sleepers)) {
- llist_append(&sched_ctx._procs[0].sleep.sleepers,
- &__current->sleep.sleepers);
+ llist_append(&root_proc->sleep.sleepers, &__current->sleep.sleepers);
}
return prev_ddl ? (prev_ddl - now) / 1000 : 0;
alloc_process()
{
pid_t i = 0;
- for (; i < sched_ctx.ptable_len && sched_ctx._procs[i].state != PS_DESTROY;
- i++)
+ for (; i < sched_ctx.ptable_len && sched_ctx._procs[i]; i++)
;
if (i == MAX_PROCESS) {
sched_ctx.ptable_len++;
}
- struct proc_info* proc = &sched_ctx._procs[i];
- memset(proc, 0, sizeof(*proc));
+ struct proc_info* proc = cake_grab(proc_pile);
proc->state = PS_CREATED;
proc->pid = i;
llist_init_head(&proc->sleep.sleepers);
waitq_init(&proc->waitqueue);
+ sched_ctx._procs[i] = proc;
+
return proc;
}
void
commit_process(struct proc_info* process)
{
- assert(process == &sched_ctx._procs[process->pid]);
+ assert(process == sched_ctx._procs[process->pid]);
if (process->state != PS_CREATED) {
__current->k_status = EINVAL;
// every process is the child of first process (pid=1)
if (!process->parent) {
- process->parent = &sched_ctx._procs[1];
+ process->parent = sched_ctx._procs[1];
}
llist_append(&process->parent->children, &process->siblings);
__current->k_status = EINVAL;
return;
}
- struct proc_info* proc = &sched_ctx._procs[index];
- proc->state = PS_DESTROY;
+ struct proc_info* proc = sched_ctx._procs[index];
+ sched_ctx._procs[index] = 0;
+
llist_delete(&proc->siblings);
for (size_t i = 0; i < VFS_MAX_FD; i++) {
vmm_unmount_pd(PD_MOUNT_1);
+ cake_release(proc_pile, proc);
+
return pid;
}
if (index < 0 || index > sched_ctx.ptable_len) {
return NULL;
}
- return &sched_ctx._procs[index];
+ return sched_ctx._procs[index];
}
int
return 0;
if (pid >= sched_ctx.ptable_len)
return 0;
- struct proc_info* proc = &sched_ctx._procs[pid];
+ struct proc_info* proc = sched_ctx._procs[pid];
struct proc_info* parent = proc->parent;
// 如果其父进程的状态是terminated 或 destroy中的一种
git://scm.lunaixsky.com / lunaix-os.git / commitdiff
