Mutex wait queuesno-search

6 files changed, 45 insertions, 129 deletions

diff --git a/include/lib/queue.h b/include/lib/queue.h
index 1d4899a..c6da6ed 100644
--- a/include/lib/queue.h
+++ b/include/lib/queue.h
@@ -1,33 +1,20 @@
 #ifndef LIB_QUEUE_H
 #define LIB_QUEUE_H
 
-enum EntryType {
-	VALUE_ENTRY = 0,
-	START_ENTRY = 1,
-	END_ENTRY = 2,
-};
-
 struct Entry {
 	void* value;
 	struct Entry* next;
-	unsigned long entry_type;
 };
 
 struct Queue {
 	struct Entry start;
-	struct Entry end;
 };
 
-// Add to end of queue
-void push_to_queue(struct Entry* e, struct Queue* q);
 // Add to beginning of queue
-void prepend_to_queue(struct Entry* e, struct Queue* q);
+void push_to_queue(struct Entry* e, struct Queue* q);
 // Remove from beginning of queue
 struct Entry* pop_from_queue(struct Queue* q);
-// Remove the entry after this one from its queue
+// Remove the next entry
 struct Entry* remove_next_from_queue(struct Entry* e);
-// Find an entry in a queue
-//  Returns the entry before the target entry
-struct Entry* find_value(void* value, struct Queue* q);
 
 #endif
diff --git a/include/util/mutex.h b/include/util/mutex.h
index cef4c60..da71146 100644
--- a/include/util/mutex.h
+++ b/include/util/mutex.h
@@ -16,6 +16,8 @@
 struct Mutex {
 	unsigned long pid;
 	void* addr;
+	struct Entry* locking_thread;
+	struct Entry* waiting_threads;
 } __attribute__((packed, aligned(4)));
 
 struct MutexManager {
diff --git a/kernel/lib/queue.c b/kernel/lib/queue.c
index 1fc35f6..38ef8cf 100644
--- a/kernel/lib/queue.c
+++ b/kernel/lib/queue.c
@@ -2,54 +2,23 @@
 
 void push_to_queue(struct Entry* e, struct Queue* q)
 {
-	q->end.next->next = e;
-	q->end.next = e;
-	e->next = &q->end;
-}
-
-void prepend_to_queue(struct Entry* e, struct Queue* q)
-{
 	e->next = q->start.next;
 	q->start.next = e;
-	if (e->next->entry_type == END_ENTRY)
-		q->end.next = e;
 }
 
 struct Entry* pop_from_queue(struct Queue* q)
 {
-	if (q->start.next->entry_type == END_ENTRY)
+	if (q->start.next == 0)
 		return 0;
 	struct Entry* e = q->start.next;
 	q->start.next = e->next;
-	if (e->next->entry_type == END_ENTRY)
-		q->end.next = &q->start;
 	return e;
 }
 
-struct Entry* remove_next_from_queue(struct Entry* e)
-{
-	struct Entry* prev = e;
-	struct Entry* remove = e->next;
-	struct Entry* next = remove->next;
-	if (remove->entry_type != VALUE_ENTRY)
+struct Entry* remove_next_from_queue(struct Entry* e) {
+	if (e->next == 0)
 		return 0;
-	prev->next = next;
-	if (next->entry_type == END_ENTRY)
-		next->next = prev;
-	return remove;
-}
-
-struct Entry* find_value(void* value, struct Queue* q)
-{
-	struct Entry* prev;
-	struct Entry* entry;
-	prev = &q->start;
-	entry = prev->next;
-	while (entry->entry_type != END_ENTRY) {
-		if (entry->value == value)
-			return prev;
-		prev = entry;
-		entry = prev->next;
-	}
-	return 0;
+	struct Entry* next = e->next;
+	e->next = next->next;
+	return next;
 }
diff --git a/kernel/sys/schedule.c b/kernel/sys/schedule.c
index 142ffaf..c8dc581 100644
--- a/kernel/sys/schedule.c
+++ b/kernel/sys/schedule.c
@@ -8,6 +8,7 @@
 
 extern void kernel_usr_task_loop(void);
 
+/// Initialize the scheduler
 void init_scheduler(void)
 {
 	// Set rthread to usrloopthread - an infinitely running thread so that the pointer will never be null
@@ -27,26 +28,11 @@ void init_scheduler(void)
 	// Initialize Scheduling Queues
 	for (unsigned long p = 0; p < PRIORITIES; p++) {
 		// Ready Init
-		scheduler.ready[p].start.value = 0;
-		scheduler.ready[p].start.next = &scheduler.ready[p].end;
-		scheduler.ready[p].start.entry_type = START_ENTRY;
-		scheduler.ready[p].end.value = 0;
-		scheduler.ready[p].end.next = &scheduler.ready[p].start;
-		scheduler.ready[p].end.entry_type = END_ENTRY;
+		scheduler.ready[p].start.next = 0;
 		// Mutex Wait Init
-		scheduler.mwait[p].start.value = 0;
-		scheduler.mwait[p].start.next = &scheduler.mwait[p].end;
-		scheduler.mwait[p].start.entry_type = START_ENTRY;
-		scheduler.mwait[p].end.value = 0;
-		scheduler.mwait[p].end.next = &scheduler.mwait[p].start;
-		scheduler.mwait[p].end.entry_type = END_ENTRY;
+		scheduler.mwait[p].start.next = 0;
 		// Signal Wait Init
-		scheduler.swait[p].start.value = 0;
-		scheduler.swait[p].start.next = &scheduler.swait[p].end;
-		scheduler.swait[p].start.entry_type = START_ENTRY;
-		scheduler.swait[p].end.value = 0;
-		scheduler.swait[p].end.next = &scheduler.swait[p].start;
-		scheduler.swait[p].end.entry_type = END_ENTRY;
+		scheduler.swait[p].start.next = 0;
 	}
 
 	// Initialize nextpid
@@ -60,18 +46,13 @@ void init_scheduler(void)
 		t->highest_mutex = 0;
 		thread_entries[i].value = t;
 		thread_entries[i].next = &thread_entries[(i+1)];
-		thread_entries[i].entry_type = VALUE_ENTRY;
 	}
 	// Initialize the free queue
-	scheduler.free_threads.start.value = 0;
-	scheduler.free_threads.start.entry_type = START_ENTRY;
-	scheduler.free_threads.end.value = 0;
-	scheduler.free_threads.end.entry_type = END_ENTRY;
 	scheduler.free_threads.start.next = &thread_entries[0];
-	scheduler.free_threads.end.next = &thread_entries[MAX_THREADS-1];
-	thread_entries[MAX_THREADS-1].next = &scheduler.free_threads.end;
+	thread_entries[MAX_THREADS-1].next = 0;
 }
 
+/// Push the given thread to a given priority queue
 void push_thread_to_queue(struct Thread* t, unsigned char type, unsigned char priority)
 {
 	struct Entry* entry = &thread_entries[t->offset];
@@ -86,27 +67,9 @@ void push_thread_to_queue(struct Thread* t, unsigned char type, unsigned char pr
 		return;
 	}
 	push_to_queue(entry, queue);
-	//queue->end.next->next = entry;
-	//queue->end.next = entry;
-	//entry->next = &queue->end;
-}
-
-void prepend_thread_to_queue(struct Thread* t, unsigned char type, unsigned char priority)
-{
-	struct Entry* entry = &thread_entries[t->offset];
-	struct Queue* queue;
-	if (type == THREAD_READY) {
-		queue = &scheduler.ready[priority];
-	} else if (type == THREAD_MWAIT) {
-		queue = &scheduler.mwait[priority];
-	} else if (type == THREAD_SWAIT) {
-		queue = &scheduler.swait[priority];
-	} else {
-		return;
-	}
-	prepend_to_queue(entry, queue);
 }
 
+/// Get a thread from a queue
 struct Entry* pop_thread_from_queue(unsigned char type, unsigned char priority)
 {
 	struct Entry* entry = 0;
@@ -123,6 +86,7 @@ struct Entry* pop_thread_from_queue(unsigned char type, unsigned char priority)
 	return pop_from_queue(queue);
 }
 
+/// Find thread with pid
 struct Entry* find_pid(unsigned long pid)
 {
 	for (unsigned char p = 0; p < PRIORITIES; p++) {
@@ -133,7 +97,7 @@ struct Entry* find_pid(unsigned long pid)
 		queue = &scheduler.ready[p];
 		prev = &queue->start;
 		entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pid == pid)
 				return prev;
 			prev = entry;
@@ -143,7 +107,7 @@ struct Entry* find_pid(unsigned long pid)
 		queue = &scheduler.mwait[p];
 		prev = &queue->start;
 		entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pid == pid)
 				return prev;
 			prev = entry;
@@ -153,7 +117,7 @@ struct Entry* find_pid(unsigned long pid)
 		queue = &scheduler.swait[p];
 		prev = &queue->start;
 		entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pid == pid)
 				return prev;
 			prev = entry;
@@ -163,20 +127,14 @@ struct Entry* find_pid(unsigned long pid)
 	return 0;
 }
 
+/// Find the next thread waiting on this mutex
 struct Entry* find_mutex_wait_next(void* m)
 {
-	for (unsigned char p = 0; p < PRIORITIES; p++) {
-		struct Queue* queue = &scheduler.mwait[p];
-		struct Entry* prev = &queue->start;
-		struct Entry* entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
-			if (((struct Thread*)entry->value)->mptr == m)
-				return prev;
-			prev = entry;
-			entry = entry->next;
-		}
-	}
-	return 0;
+	unsigned long spacing = (unsigned long)&mutexs[1] - (unsigned long)&mutexs[0];
+	unsigned long difference = (unsigned long)m - (unsigned long)&mutexs[0];
+	unsigned long index = difference/spacing;
+	struct Entry* entry = mutexs[index].waiting_threads;
+	return entry;
 }
 
 struct Entry* find_signal_wait_next(void* s)
@@ -185,7 +143,7 @@ struct Entry* find_signal_wait_next(void* s)
 		struct Queue* queue = &scheduler.swait[p];
 		struct Entry* prev = &queue->start;
 		struct Entry* entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->mptr == s)
 				return prev;
 			prev = entry;
@@ -200,7 +158,7 @@ struct Entry* get_unused_thread(void)
 	struct Queue* q = &scheduler.free_threads;
 	// If we have no available free threads
 	//  return null pointer
-	if (q->start.next->entry_type == END_ENTRY)
+	if (q->start.next == 0)
 		return 0;
 	// Otherwise, get the next thread
 	return pop_from_queue(q);
@@ -211,7 +169,7 @@ unsigned char find_duplicate(void* pc)
 	for (unsigned char p = 0; p < PRIORITIES; p++) {
 		struct Queue* queue = &scheduler.ready[p];
 		struct Entry* entry = queue->start.next;
-		while (entry->entry_type == VALUE_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pc == pc) {
 				return 1;
 			}
@@ -282,7 +240,7 @@ void uart_scheduler(void)
 		uart_string("Ready Queue\n");
 		entry = queue->start.next;
 		length = 0;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			uart_hex((unsigned long)entry->value);
 			uart_char(' ');
 			kmemshow32((void*)entry->value, 9);
@@ -295,7 +253,7 @@ void uart_scheduler(void)
 		uart_string("Mutex Wait Queue\n");
 		entry = queue->start.next;
 		length = 0;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			uart_hex((unsigned long)entry->value);
 			uart_char(' ');
 			kmemshow32((void*)entry->value, 9);
@@ -308,7 +266,7 @@ void uart_scheduler(void)
 		uart_string("Signal Wait Queue\n");
 		entry = queue->start.next;
 		length = 0;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			uart_hex((unsigned long)entry->value);
 			uart_char(' ');
 			kmemshow32((void*)entry->value, 9);
@@ -320,7 +278,7 @@ void uart_scheduler(void)
 	// Count number of free threads
 	struct Queue* queue = &scheduler.free_threads;
 	struct Entry* entry = queue->start.next;
-	while (entry->entry_type != END_ENTRY) {
+	while (entry != 0) {
 		entry = entry->next;
 		length++;
 	}
@@ -333,7 +291,7 @@ struct Thread* next_thread(void)
 	// Recurse through all priorities to try to find a ready thread
 	for (int p = 0; p < PRIORITIES; p++) {
 		struct Queue* rq = &scheduler.ready[p];
-		if (rq->start.next->entry_type == END_ENTRY)
+		if (rq->start.next == 0)
 			continue;
 		return rq->start.next->value;
 	}
@@ -384,7 +342,7 @@ void sched_mutex_yield(void* m)
 		push_thread_to_queue(rt->value, THREAD_MWAIT, priority);
 	// Find the thread that has the mutex locked
 	struct Mutex* mtex = m;
-	struct Entry* mutex_next = find_pid(mtex->pid);
+	struct Entry* mutex_next = mtex->locking_thread;
 	if (mutex_next == 0)
 		return;
 	// The next thread is the one with the lock
@@ -445,7 +403,7 @@ unsigned long sched_mutex_resurrect(void* m)
 		struct Entry* tentry = pop_thread_from_queue(THREAD_READY, p);
 		((struct Thread*)tentry->value)->priority = op;
 		((struct Thread*)tentry->value)->old_priority = 0xFF;
-		prepend_thread_to_queue(tentry->value, THREAD_READY, op);
+		push_thread_to_queue(tentry->value, THREAD_READY, op);
 	}
 	return 1;
 }
diff --git a/kernel/util/mutex.c b/kernel/util/mutex.c
index 997d85d..b05aee3 100644
--- a/kernel/util/mutex.c
+++ b/kernel/util/mutex.c
@@ -9,18 +9,14 @@ void mutex_init(void)
 	for (unsigned long m = 0; m < MAX_MUTEXS; m++) {
 		mutexs[m].pid = 0;
 		mutexs[m].addr = 0;
+		mutexs[m].locking_thread = 0;
+		mutexs[m].waiting_threads = 0;
 		mutex_entries[m].value = &mutexs[m];
-		mutex_entries[m].entry_type = VALUE_ENTRY;
 		mutex_entries[m].next = &mutex_entries[m+1];
 	}
 	// Initialize Free Mutexs
-	mutex_manager.free.start.value = 0;
 	mutex_manager.free.start.next = &mutex_entries[0];
-	mutex_manager.free.start.entry_type = START_ENTRY;
-	mutex_manager.free.end.value = 0;
-	mutex_manager.free.end.next = &mutex_entries[MAX_MUTEXS-1];
-	mutex_entries[MAX_MUTEXS-1].next = &mutex_manager.free.end;
-	mutex_manager.free.end.entry_type = END_ENTRY;
+	mutex_entries[MAX_MUTEXS-1].next = 0;
 }
 
 struct Mutex* create_mutex(void* addr)
@@ -44,7 +40,8 @@ unsigned char delete_mutex(struct Mutex* m)
 		return 1;
 	struct Entry* entry = &mutex_entries[index];
 	// Add it to the free queue
-	prepend_to_queue(entry, &mutex_manager.free);
+	push_to_queue(entry, &mutex_manager.free);
+	mutex_manager.used_mutexes--;
 	return 0;
 }
 
@@ -67,6 +64,7 @@ unsigned char lock_mutex(struct Mutex* m)
 		if ((unsigned char) index > rthread->highest_mutex)
 			return 2;
 		sys1(SYS_LOCK, m);
+		m->locking_thread = &mutex_entries[index];
 		return 0;
 	}
 	return 3;
diff --git a/usr/test.c b/usr/test.c
index b30fbba..3885113 100644
--- a/usr/test.c
+++ b/usr/test.c
@@ -193,6 +193,7 @@ void test_super(void)
 	draw_string((8%TEST_PER_LINE)*15, 11+5*(8/TEST_PER_LINE), "Mutex Unlock");
 	add_thread(test_results,(void*) 8, 0);idx = 0;
 
+	/*
 	static unsigned long semp = 0;
 	for (unsigned long i = 0; i < MAX_ITER; i++) {
 		semp = 1;
@@ -212,6 +213,7 @@ void test_super(void)
 	}
 	draw_string((11%TEST_PER_LINE)*15, 11+5*(11/TEST_PER_LINE), "Semaphore V");
 	add_thread(test_results,(void*) 11, 0);idx = 0;
+	*/
 }
 
 void delaytest(void)