ticket locks

14 files changed, 82 insertions, 80 deletions

diff --git a/sys/Makefile b/sys/Makefile
index 02ee0df..a766174 100644
--- a/sys/Makefile
+++ b/sys/Makefile
@@ -8,11 +8,11 @@ TARGETDIR=../mainboard/${TARGET}
 .endif
 
 SRC=\
-    kern/entry.S\
-    kern/init.c\
-    kern/printf.c\
-    kern/mm/kalloc.c\
-    kern/spinlock.c\
+    sys/entry.S\
+    sys/init.c\
+    sys/printf.c\
+    sys/mm/kalloc.c\
+    sys/smp/spinlock.c\
     dev/fdt/fdt.c
     
 
@@ -25,8 +25,9 @@ ${BUILDDIR}/kernel.elf: ${SRC}
 		-DLOAD_ADDR=${LOAD_ADDR}\
 		-DNPROC=${NPROC}\
 		-DPAGE_SIZE=${PAGE_SIZE}\
+		-I ../include\
 		-I ./include\
-		${CFLAGS} -T kern/kernel.lds ${LDFLAGS}\
+		${CFLAGS} -T sys/kernel.lds ${LDFLAGS}\
 		-L../lib/${BUILDDIR}/\
 		-l:libc.a\
 		-o $@
diff --git a/sys/dev/cpu.c b/sys/dev/cpu.c
deleted file mode 100644
index f96b807..0000000
--- a/sys/dev/cpu.c
+++ /dev/null
@@ -1,6 +0,0 @@
-#include <cpu.h> 
-
-extern struct hart harts[NPROC];
-
-
-
diff --git a/sys/dev/fdt/fdt.c b/sys/dev/fdt/fdt.c
index 4b132e2..0bd0a52 100644
--- a/sys/dev/fdt/fdt.c
+++ b/sys/dev/fdt/fdt.c
@@ -20,9 +20,10 @@ fdt_walk(struct fdt_header *header)
         printf("header->size_dt_strings: %d\n", fdt_uint32(header->size_dt_strings));
         printf("header->size_dt_struct: %d\n",  fdt_uint32(header->size_dt_struct));
 
-        uint8_t *dts = header + fdt_uint32(header->off_dt_struct) + sizeof(uint32_t);
-        uint8_t *dtstr = header + fdt_uint32(header->off_dt_strings);
-        printf("parsing dt struct @%p...\n", dts);
-        printf(dts);
+	printf("walking the memory reservation block...\n");
+	struct fdt_reserve_entry *p = header + fdt_uint32(header->off_mem_rsvmap);
+//	do {
+//		printf("reserved entry at %p with size %i\n", p->address, p->size);
+//		p++;
+//	} while (!(p->size == 0 && p->address == 0));
 }
-
diff --git a/sys/include/asm.h b/sys/include/asm.h
index 86e6354..0995f88 100644
--- a/sys/include/asm.h
+++ b/sys/include/asm.h
@@ -50,6 +50,7 @@ read_tp(void)
 {
         uint64_t x;
         asm volatile("addi %0, tp, 0" : "=r"(x));
+	return x;
 }
 
 #endif /* _ASM_H */ 
diff --git a/sys/include/fdt.h b/sys/include/fdt.h
index ca1cea0..77c9d6e 100644
--- a/sys/include/fdt.h
+++ b/sys/include/fdt.h
@@ -40,7 +40,7 @@ struct fdt_node_header {
 	char name[];
 };
 
-void    walk_fdt(struct fdt_header *header);
+void    fdt_walk(struct fdt_header *header);
 
 #define FDT_MAGIC	0xd00dfeed	/* 4: version, 4: total size */
 #define FDT_TAGSIZE	sizeof(fdt32_t)
diff --git a/sys/include/mm/kalloc.h b/sys/include/kalloc.h
index 10adbda..10adbda 100644
--- a/sys/include/mm/kalloc.h
+++ b/sys/include/kalloc.h
diff --git a/sys/include/spinlock.h b/sys/include/spinlock.h
index ef81499..82c1585 100644
--- a/sys/include/spinlock.h
+++ b/sys/include/spinlock.h
@@ -1,15 +1,17 @@
-#ifndef _LOCK_H
-#define _LOCK_H
+#ifndef _SPINLOCK_H
+#define _SPINLOCK_H
 
-struct spinlock {
-        int locked;
-	int tp;
-};
+/* fifo ticket lock implementation */ 
 
-void initlock(struct spinlock *);
+typedef struct _spinlock {
+	int ticket;
+	int turn;
+} spinlock_t;
 
-void acquire(struct spinlock *);
+void initlock(spinlock_t *);
 
-void release(struct spinlock *);
+void acquire(spinlock_t *);
 
-#endif /* _LOCK_H */
+void release(spinlock_t *);
+
+#endif /* _SPINLOCK_H */
diff --git a/sys/kern/spinlock.c b/sys/kern/spinlock.c
deleted file mode 100644
index ade270f..0000000
--- a/sys/kern/spinlock.c
+++ /dev/null
@@ -1,38 +0,0 @@
-#include <asm.h>
-#include <spinlock.h>
-
-void 
-initlock(struct spinlock *l)
-{
-        l->locked = 0;
-}
-
-void 
-acquire(struct spinlock *l)
-{
-	sie_disable();
-
-	if (l->locked)
-		return;
-
-	while (__sync_lock_test_and_set(&l->locked, 1))
-			;
-
-	__sync_synchronize();
-}
-
-void 
-release(struct spinlock *l) 
-{
-	sie_disable(); // avoid deadlock
-
-	if (l->locked)
-		return;  // interrupts are still disabled, what to do here?
-
-	/* fence */
-	__sync_synchronize();
-
-	__sync_lock_release(&l->locked);
-
-	sie_enable();
-}
diff --git a/sys/kern/entry.S b/sys/sys/entry.S
index 9bf72ea..9bf72ea 100644
--- a/sys/kern/entry.S
+++ b/sys/sys/entry.S
diff --git a/sys/kern/init.c b/sys/sys/init.c
index a58d3bc..e5cb4e4 100644
--- a/sys/kern/init.c
+++ b/sys/sys/init.c
@@ -1,7 +1,7 @@
 #include <fdt.h>
-#include <mm/kalloc.h>
-#include <printf.h>
+#include <kalloc.h>
 #include <spinlock.h>
+#include <printf.h>
 #include <sbi.h>
 #include <stdint.h>
 
@@ -16,7 +16,6 @@ init(unsigned long hartid, struct fdt_header *fdt)
 {
 
 	printf("booting from hart #%d\n", hartid);
-        asm volatile ("mv tp, %0" : : "r"(hartid));
 	if (fdt_uint32(fdt->magic) == FDT_HEADER_MAGIC) 
 		printf("found flattened device tree at %p!\n", (uint64_t)fdt);
         
@@ -25,6 +24,7 @@ init(unsigned long hartid, struct fdt_header *fdt)
 
         printf("setting up the heap at %p\n", HEAP_START);
         kalloc_init();
+	printf_init();
         printf("done!\n");
        // printf("printing free pages:\n");
        ///walkfree();
diff --git a/sys/kern/kernel.lds b/sys/sys/kernel.lds
index 2e2fe29..2e2fe29 100644
--- a/sys/kern/kernel.lds
+++ b/sys/sys/kernel.lds
diff --git a/sys/kern/mm/kalloc.c b/sys/sys/mm/kalloc.c
index bfd4f3f..a574c41 100644
--- a/sys/kern/mm/kalloc.c
+++ b/sys/sys/mm/kalloc.c
@@ -1,8 +1,10 @@
 #include <stddef.h>
+#include <spinlock.h>
+#include <fdt.h>
 #include <stdint.h>
 #include <string.h>
 #include <printf.h>
-#include <mm/kalloc.h>
+#include <kalloc.h>
 
 extern uint64_t HEAP_START; 
 
@@ -11,16 +13,19 @@ typedef struct freenode {
 } freenode_t;
 
 freenode_t *head = NULL;
+static spinlock_t mutex;
 
 void *
 kalloc(void) 
 {
+	acquire(&mutex);
 	freenode_t *p = head;
-
+	
 	if (p == NULL)
 		return NULL;
 
 	head = p->next;
+	release(&mutex);
 	return p;
 }
 
@@ -35,17 +40,20 @@ kzalloc(void)
 void
 kfree(void *p)
 {
-	if (p == NULL)
+	if (p == NULL || (uint64_t)p % (uint64_t)PAGE_SIZE)
 		return;
 
+	acquire(&mutex);
 	freenode_t *tmp = head;
 	head = p;
 	head->next = tmp;
+	release(&mutex);
 }
 
 void
 kalloc_init(void)
 {
+	initlock(&mutex);
         freenode_t *p = (freenode_t*)HEAP_START;
         for (;(unsigned long)p + PAGE_SIZE <= (HEAP_START + 0x100000); p += PAGE_SIZE) {
                 kfree(p);
diff --git a/sys/kern/printf.c b/sys/sys/printf.c
index 89add9e..19b2315 100644
--- a/sys/kern/printf.c
+++ b/sys/sys/printf.c
@@ -6,8 +6,7 @@
 
 static char digits[] = "0123456789abcdef";
 
-struct spinlock mutex;
-int locked = 0;
+static spinlock_t mutex;
 
 int
 puts(const char *str)
@@ -59,9 +58,7 @@ printf(const char *fmt, ...)
         int i, c, _locked;
         char *s;
 
-	_locked = locked;
-	if (_locked)
-		acquire(&mutex);
+	acquire(&mutex);
 
         va_start(ap, fmt);
 
@@ -90,12 +87,10 @@ printf(const char *fmt, ...)
                                 break;
                 }
         }
-	if (_locked)
-		release(&mutex);
+	release(&mutex);
 }
 
 void printf_init(void)
 {
 	initlock(&mutex);
-	locked = 1;
 }
diff --git a/sys/sys/smp/spinlock.c b/sys/sys/smp/spinlock.c
new file mode 100644
index 0000000..ff48a84
--- /dev/null
+++ b/sys/sys/smp/spinlock.c
@@ -0,0 +1,38 @@
+/* simple ticket spinlock implementation as outlined by
+ * John M. Mellor-Crummey and Michael L. Scott. 1991. 
+ * Algorithms for scalable synchronization on shared-memory multiprocessors. 
+ * ACM Trans. Comput. Syst. 9, 1 (Feb. 1991), 21–65. https://doi.org/10.1145/103727.103729 
+ */
+#include <asm.h>
+#include <spinlock.h>
+#include <printf.h>
+#include <sbi.h>
+
+void 
+initlock(spinlock_t *l)
+{
+	l->ticket = 0;
+	l->turn = 0;
+}
+
+void 
+acquire(spinlock_t *l)
+{
+	sie_disable(); 
+
+
+	int myturn = __sync_fetch_and_add(&l->ticket, 1);
+	while (l->turn != myturn)
+		;
+	__sync_synchronize();
+}
+
+void 
+release(spinlock_t *l) 
+{
+	sie_disable(); 
+
+	__sync_add_and_fetch(&l->turn, 1);
+
+	sie_enable();
+}