From 283d5ab4c964ab525e45fcade06d6fd7e977c43e Mon Sep 17 00:00:00 2001 From: Mole Shang <135e2@135e2.dev> Date: Thu, 18 Jan 2024 17:35:27 +0800 Subject: lab syscall: finish Conflicts: kernel/syscall.c kernel/syscall.h user/user.h user/usys.pl --- kernel/kalloc.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'kernel/kalloc.c') diff --git a/kernel/kalloc.c b/kernel/kalloc.c index 0699e7e..c2fdb86 100644 --- a/kernel/kalloc.c +++ b/kernel/kalloc.c @@ -80,3 +80,17 @@ kalloc(void) memset((char*)r, 5, PGSIZE); // fill with junk return (void*)r; } + +int +get_freemem(void) +{ + int n; + struct run *r; + + acquire(&kmem.lock); + for (n = 0, r = kmem.freelist; r; r = r->next) + n++; + release(&kmem.lock); + + return n * PGSIZE; +} -- cgit v1.2.3 From 4a6593f1a6f666c618d303a4858c4c6d31b41c63 Mon Sep 17 00:00:00 2001 From: Mole Shang <135e2@135e2.dev> Date: Sun, 11 Feb 2024 17:51:28 +0800 Subject: lab cow: finish --- kernel/kalloc.c | 43 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 42 insertions(+), 1 deletion(-) (limited to 'kernel/kalloc.c') diff --git a/kernel/kalloc.c b/kernel/kalloc.c index c2fdb86..581f0f6 100644 --- a/kernel/kalloc.c +++ b/kernel/kalloc.c @@ -23,10 +23,41 @@ struct { struct run *freelist; } kmem; +int phypg_refcnt[PHYSTOP/PGSIZE]; + +// Increase the refcnt +int +refcnt_inc(uint64 pa) +{ + acquire(&kmem.lock); + int *prefcnt = &phypg_refcnt[pa/PGSIZE]; + if(pa > PHYSTOP || *prefcnt < 1) + panic("increase refcnt"); + (*prefcnt)++; + release(&kmem.lock); + return *prefcnt; +} + +// Decrease the refcnt +int +refcnt_dec(uint64 pa) +{ + acquire(&kmem.lock); + int *prefcnt = &phypg_refcnt[pa/PGSIZE]; + if(pa > PHYSTOP || *prefcnt < 1) + panic("decrease refcnt"); + (*prefcnt)--; + release(&kmem.lock); + return *prefcnt; +} + void kinit() { initlock(&kmem.lock, "kmem"); + // init all refcnt to 1, which would later be freed to 0 by kfree() + for(uint64 p = PGROUNDUP((uint64)end); p + PGSIZE <= PHYSTOP; p += PGSIZE) + phypg_refcnt[p/PGSIZE] = 1; freerange(end, (void*)PHYSTOP); } @@ -51,6 +82,12 @@ kfree(void *pa) if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) panic("kfree"); + refcnt_dec((uint64)pa); + + if(phypg_refcnt[(uint64)pa/PGSIZE] > 0) + // We still have refs to this phy page, do not actually free it + return; + // Fill with junk to catch dangling refs. memset(pa, 1, PGSIZE); @@ -72,8 +109,12 @@ kalloc(void) acquire(&kmem.lock); r = kmem.freelist; - if(r) + if(r){ + if(phypg_refcnt[(uint64)r/PGSIZE]) + panic("kalloc: invalid refcnt"); + phypg_refcnt[(uint64)r/PGSIZE] = 1; kmem.freelist = r->next; + } release(&kmem.lock); if(r) -- cgit v1.2.3 From 16f51058790ba5779cf46de18e6a266f2fac0a1d Mon Sep 17 00:00:00 2001 From: Mole Shang <135e2@135e2.dev> Date: Wed, 14 Feb 2024 23:10:54 +0800 Subject: lab lock/kalloc: finish --- kernel/kalloc.c | 91 ++++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 71 insertions(+), 20 deletions(-) (limited to 'kernel/kalloc.c') diff --git a/kernel/kalloc.c b/kernel/kalloc.c index 581f0f6..85cf6b7 100644 --- a/kernel/kalloc.c +++ b/kernel/kalloc.c @@ -9,6 +9,9 @@ #include "riscv.h" #include "defs.h" +// NOTE: leave interrupts disabled to avoid deadlocks & race conditions when using this macro!!! +#define CUR_KMEM (kmem_list[cpuid()]) + void freerange(void *pa_start, void *pa_end); extern char end[]; // first address after kernel. @@ -18,23 +21,27 @@ struct run { struct run *next; }; -struct { +struct kmem { struct spinlock lock; struct run *freelist; -} kmem; +}; + +struct kmem kmem_list[NCPU]; int phypg_refcnt[PHYSTOP/PGSIZE]; +struct spinlock refcnt_lock; + // Increase the refcnt int refcnt_inc(uint64 pa) { - acquire(&kmem.lock); + acquire(&refcnt_lock); int *prefcnt = &phypg_refcnt[pa/PGSIZE]; if(pa > PHYSTOP || *prefcnt < 1) panic("increase refcnt"); (*prefcnt)++; - release(&kmem.lock); + release(&refcnt_lock); return *prefcnt; } @@ -42,22 +49,27 @@ refcnt_inc(uint64 pa) int refcnt_dec(uint64 pa) { - acquire(&kmem.lock); + acquire(&refcnt_lock); int *prefcnt = &phypg_refcnt[pa/PGSIZE]; if(pa > PHYSTOP || *prefcnt < 1) panic("decrease refcnt"); (*prefcnt)--; - release(&kmem.lock); + release(&refcnt_lock); return *prefcnt; } void kinit() { - initlock(&kmem.lock, "kmem"); + for(int i = 0; i < NCPU; i++){ + static char lock_name[8]; + snprintf(lock_name, sizeof(lock_name), "kmem.%d", i); + initlock(&kmem_list[i].lock, lock_name); + } // init all refcnt to 1, which would later be freed to 0 by kfree() for(uint64 p = PGROUNDUP((uint64)end); p + PGSIZE <= PHYSTOP; p += PGSIZE) phypg_refcnt[p/PGSIZE] = 1; + initlock(&refcnt_lock, "refcnt"); freerange(end, (void*)PHYSTOP); } @@ -93,10 +105,13 @@ kfree(void *pa) r = (struct run*)pa; - acquire(&kmem.lock); - r->next = kmem.freelist; - kmem.freelist = r; - release(&kmem.lock); + push_off(); + struct kmem *kmem = &CUR_KMEM; + acquire(&kmem->lock); + r->next = kmem->freelist; + kmem->freelist = r; + release(&kmem->lock); + pop_off(); } // Allocate one 4096-byte page of physical memory. @@ -107,18 +122,53 @@ kalloc(void) { struct run *r; - acquire(&kmem.lock); - r = kmem.freelist; + push_off(); + struct kmem *kmem = &CUR_KMEM; + acquire(&kmem->lock); + r = kmem->freelist; if(r){ + acquire(&refcnt_lock); if(phypg_refcnt[(uint64)r/PGSIZE]) panic("kalloc: invalid refcnt"); phypg_refcnt[(uint64)r/PGSIZE] = 1; - kmem.freelist = r->next; + release(&refcnt_lock); + kmem->freelist = r->next; + } + + // release the origin lock to avoid deadlocks + release(&kmem->lock); + + if(!r){ + // try to steal mem from other cpu's kmem + for(int i = 0; i < NCPU; i++){ + if(kmem == &kmem_list[i]) + continue; + + acquire(&kmem_list[i].lock); + struct run *f = kmem_list[i].freelist; + if(f){ + r = f; + kmem_list[i].freelist = f->next; + } + if(r){ + // acquire the refcnt lock to set refcnt + // lock is a must to prevent refcnt races + acquire(&refcnt_lock); + // release previous lock now + release(&kmem_list[i].lock); + if(phypg_refcnt[(uint64)r/PGSIZE]) + panic("kalloc: invalid refcnt"); + phypg_refcnt[(uint64)r/PGSIZE] = 1; + release(&refcnt_lock); + break; + } + release(&kmem_list[i].lock); + } } - release(&kmem.lock); if(r) memset((char*)r, 5, PGSIZE); // fill with junk + pop_off(); return (void*)r; } @@ -128,10 +178,11 @@ get_freemem(void) int n; struct run *r; - acquire(&kmem.lock); - for (n = 0, r = kmem.freelist; r; r = r->next) - n++; - release(&kmem.lock); - + for(int i = 0; i < NCPU; i++){ + acquire(&kmem_list[i].lock); + for(n = 0, r = kmem_list[i].freelist; r; r = r->next) + n++; + release(&kmem_list[i].lock); + } return n * PGSIZE; } -- cgit v1.2.3