From: Ben Pfaff <blp@cs.stanford.edu>
Date: Thu, 2 Sep 2004 08:12:53 +0000 (+0000)
Subject: Redo and improve thread scheduling startup.
X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=828d300fd2039b686b69244c2bd6f8b87645086d

Redo and improve thread scheduling startup.
In the process make it possible to use locks before the preemptive
scheduler is turned on.
This lets us add locking to the page allocator.
---

diff --git a/src/threads/init.c b/src/threads/init.c
index ec71cec..b099d02 100644
--- a/src/threads/init.c
+++ b/src/threads/init.c
@@ -41,10 +41,11 @@ static bool format_filesys;
 static char *initial_program;
 #endif
 
-static thread_func main_thread;
 static void ram_init (void);
 static void argv_init (void);
 
+int main (void) NO_RETURN;
+
 int
 main (void)
 {
@@ -60,6 +61,7 @@ main (void)
   argv_init ();
 
   /* Initialize memory system, segments, paging. */
+  thread_init ();
   palloc_init ();
   paging_init ();
 #ifdef USERPROG
@@ -79,30 +81,29 @@ main (void)
   exception_init ();
 #endif
 
-  /* Do everything else in a system thread. */
-  thread_init ();
-  thread_create ("main", main_thread, NULL);
+  /* Start thread scheduler and enable interrupts. */
   thread_start ();
-}
 
-/* Initial thread. */
-static void
-main_thread (void *aux UNUSED) 
-{
 #ifdef FILESYS
+  /* Initialize filesystem. */
   disk_init ();
   filesys_init (format_filesys);
   fsutil_run ();
 #endif
 
+  printk ("Boot complete.\n");
+
 #ifdef USERPROG
+  /* Run a user program. */
   if (initial_program != NULL)
-    thread_execute (initial_program);
-  else
-    PANIC ("no initial program specified");
-#else
-  PANIC ("boot successful");
+    {
+      printk ("\nExecuting '%s':\n", initial_program);
+      thread_execute (initial_program); 
+    }
 #endif
+
+  /* Terminate this thread. */
+  thread_exit ();
 }
 
 /* Clear BSS and obtain RAM size from loader. */
diff --git a/src/threads/loader.S b/src/threads/loader.S
index 4e4fbb4..d67af38 100644
--- a/src/threads/loader.S
+++ b/src/threads/loader.S
@@ -181,9 +181,10 @@ read_sector:
 	
 ##### Jump to kernel entry point.
 
-	movl $LOADER_PHYS_BASE + LOADER_BASE, %esp
+	movl $LOADER_PHYS_BASE + 0x20000, %esp
 	movl $LOADER_PHYS_BASE + LOADER_KERN_BASE, %eax
-	jmp *%eax
+	call *%eax
+	jmp panic
 
 ##### GDT
 
diff --git a/src/threads/palloc.c b/src/threads/palloc.c
index 62e24ca..0b771fd 100644
--- a/src/threads/palloc.c
+++ b/src/threads/palloc.c
@@ -5,15 +5,22 @@
 #include "init.h"
 #include "loader.h"
 #include "lib.h"
+#include "list.h"
 #include "mmu.h"
+#include "synch.h"
+
+/* Page allocator.  Hands out memory in page-size chunks.
+   See malloc.h for an allocator that hands out smaller
+   chunks. */
 
 /* A free page owned by the page allocator. */
 struct page
   {
-    struct page *next;  /* Next free page, or null at end of chain. */
+    list_elem free_elem;        /* Free list element. */
   };
 
-static struct page *free_pages;
+static struct lock lock;
+static struct list free_pages;
 static uint8_t *uninit_start, *uninit_end;
 
 void
@@ -25,12 +32,15 @@ palloc_init (void)
      and end of the kernel as _start and _end.  See
      kernel.lds. */
   extern char _start, _end;
-  size_t kernel_pages;  
-  kernel_pages = (&_end - &_start + 4095) / 4096;
+  size_t kernel_pages = (&_end - &_start + 4095) / 4096;
 
   /* Then we know how much is available to allocate. */
   uninit_start = ptov (LOADER_KERN_BASE + kernel_pages * PGSIZE);
   uninit_end = ptov (ram_pages * PGSIZE);
+
+  /* Initialize other variables. */
+  lock_init (&lock, "palloc");
+  list_init (&free_pages);
 }
 
 void *
@@ -38,16 +48,20 @@ palloc_get (enum palloc_flags flags)
 {
   struct page *page;
 
-  if (free_pages == NULL && uninit_start < uninit_end) 
+  lock_acquire (&lock);
+
+  if (!list_empty (&free_pages))
+    page = list_entry (list_pop_front (&free_pages), struct page, free_elem);
+  else if (uninit_start < uninit_end) 
     {
-      palloc_free (uninit_start);
+      page = (struct page *) uninit_start;
       uninit_start += PGSIZE;
     }
+  else
+    page = NULL;
 
-  page = free_pages;
   if (page != NULL) 
     {
-      free_pages = page->next;
       if (flags & PAL_ZERO)
         memset (page, 0, PGSIZE);
     }
@@ -56,6 +70,8 @@ palloc_get (enum palloc_flags flags)
       if (flags & PAL_ASSERT)
         PANIC ("palloc_get: out of pages");
     }
+
+  lock_release (&lock);
   
   return page;
 }
@@ -64,10 +80,13 @@ void
 palloc_free (void *page_) 
 {
   struct page *page = page_;
-  ASSERT((uintptr_t) page % PGSIZE == 0);
+
+  ASSERT (page == pg_round_down (page));
 #ifndef NDEBUG
   memset (page, 0xcc, PGSIZE);
 #endif
-  page->next = free_pages;
-  free_pages = page;
+
+  lock_acquire (&lock);
+  list_push_front (&free_pages, &page->free_elem);
+  lock_release (&lock);
 }
diff --git a/src/threads/palloc.h b/src/threads/palloc.h
index 5b75e55..7250e98 100644
--- a/src/threads/palloc.h
+++ b/src/threads/palloc.h
@@ -1,10 +1,6 @@
 #ifndef HEADER_PALLOC_H
 #define HEADER_PALLOC_H 1
 
-/* Page allocator.  Hands out memory in page-size chunks.
-   See malloc.h for an allocator that hands out smaller
-   chunks. */
-
 #include <stdint.h>
 
 enum palloc_flags
diff --git a/src/threads/thread.c b/src/threads/thread.c
index d89edd6..7b34722 100644
--- a/src/threads/thread.c
+++ b/src/threads/thread.c
@@ -32,43 +32,52 @@ struct kernel_thread_frame
 
 static void kernel_thread (thread_func *, void *aux);
 
+static struct thread *running_thread (void);
 static struct thread *next_thread_to_run (void);
 static struct thread *new_thread (const char *name);
-static bool is_thread (struct thread *t);
-static void *alloc_frame (struct thread *t, size_t size);
-static void destroy_thread (struct thread *t);
+static void init_thread (struct thread *, const char *name);
+static bool is_thread (struct thread *);
+static void *alloc_frame (struct thread *, size_t size);
+static void destroy_thread (struct thread *);
 static void schedule (void);
 void schedule_tail (struct thread *prev);
 
-/* Initializes the threading system.  After calling, create some
-   threads with thread_create() or thread_execute(), then start
-   the scheduler with thread_start(). */
+/* Initializes the threading system by transforming the code
+   that's currently running into a thread.  Note that this is
+   possible only because the loader was careful to put the bottom
+   of the stack at a page boundary; it won't work in general.
+   Also initializes the run queue.
+
+   After calling this function, be sure to initialize the page
+   allocator before trying to create any threads with
+   thread_create(). */
 void
 thread_init (void) 
 {
+  struct thread *t;
+  
   ASSERT (intr_get_level () == INTR_OFF);
 
+  /* Set up a thread structure for the running thread. */
+  t = running_thread ();
+  init_thread (t, "main");
+  t->status = THREAD_RUNNING;
+
   /* Initialize run queue. */
   list_init (&run_queue);
-
-  /* Create idle thread. */
-  idle_thread = thread_create ("idle", idle, NULL);
-  idle_thread->status = THREAD_BLOCKED;
 }
 
-/* Starts the thread scheduler.  The caller should have created
-   some threads with thread_create() or thread_execute().  Never
-   returns to the caller. */
+/* Starts preemptive thread scheduling by enabling interrupts.
+   Also creates the idle thread. */
 void
 thread_start (void) 
 {
-  struct thread *t = next_thread_to_run ();
-  if (t->status == THREAD_READY)
-    list_remove (&t->rq_elem);
-  t->status = THREAD_RUNNING;
-  switch_threads (NULL, t);
+  /* Create idle thread. */
+  idle_thread = thread_create ("idle", idle, NULL);
+  idle_thread->status = THREAD_BLOCKED;
 
-  NOT_REACHED ();
+  /* Enable interrupts. */
+  intr_enable ();
 }
 
 /* Creates a new kernel thread named NAME, which executes
@@ -180,26 +189,20 @@ thread_name (struct thread *t)
   return t->name;
 }
 
-/* Returns the running thread. */
+/* Returns the running thread.
+   This is running_thread() plus a couple of sanity checks. */
 struct thread *
 thread_current (void) 
 {
-  uint32_t *esp;
-  struct thread *t;
-
-  /* Copy the CPU's stack pointer into `esp', and then round that
-     down to the start of a page.  Because `struct thread' is
-     always at the beginning of a page and the stack pointer is
-     somewhere in the middle, this locates the curent thread. */
-  asm ("movl %%esp, %0\n" : "=g" (esp));
-  t = pg_round_down (esp);
-
+  struct thread *t = running_thread ();
+  
   /* Make sure T is really a thread.
-     If this assertion fires, then your thread may have
-     overflowed its stack.  Each thread has less than 4 kB of
-     stack, so a few big automatic arrays or moderate recursion
-     can cause stack overflow. */
+     If either of these assertions fire, then your thread may
+     have overflowed its stack.  Each thread has less than 4 kB
+     of stack, so a few big automatic arrays or moderate
+     recursion can cause stack overflow. */
   ASSERT (is_thread (t));
+  ASSERT (t->status == THREAD_RUNNING);
 
   return t;
 }
@@ -274,6 +277,20 @@ kernel_thread (thread_func *function, void *aux)
   thread_exit ();       /* If function() returns, kill the thread. */
 }
 
+/* Returns the running thread. */
+struct thread *
+running_thread (void) 
+{
+  uint32_t *esp;
+
+  /* Copy the CPU's stack pointer into `esp', and then round that
+     down to the start of a page.  Because `struct thread' is
+     always at the beginning of a page and the stack pointer is
+     somewhere in the middle, this locates the curent thread. */
+  asm ("movl %%esp, %0\n" : "=g" (esp));
+  return pg_round_down (esp);
+}
+
 /* Returns true if T appears to point to a valid thread. */
 static bool
 is_thread (struct thread *t) 
@@ -293,16 +310,22 @@ new_thread (const char *name)
   
   t = palloc_get (PAL_ZERO);
   if (t != NULL)
-    {
-      strlcpy (t->name, name, sizeof t->name);
-      t->stack = (uint8_t *) t + PGSIZE;
-      t->status = THREAD_BLOCKED;
-      t->magic = THREAD_MAGIC;
-    }
-  
+    init_thread (t, name);
+
   return t;
 }
 
+/* Initializes T as a new thread named NAME. */
+static void
+init_thread (struct thread *t, const char *name)
+{
+  memset (t, 0, sizeof *t);
+  strlcpy (t->name, name, sizeof t->name);
+  t->stack = (uint8_t *) t + PGSIZE;
+  t->status = THREAD_BLOCKED;
+  t->magic = THREAD_MAGIC;
+}
+
 /* Allocates a SIZE-byte frame at the top of thread T's stack and
    returns a pointer to the frame's base. */
 static void *
@@ -360,7 +383,7 @@ destroy_thread (struct thread *t)
 void
 schedule_tail (struct thread *prev) 
 {
-  struct thread *cur = thread_current ();
+  struct thread *cur = running_thread ();
   
   ASSERT (intr_get_level () == INTR_OFF);
 
@@ -380,18 +403,17 @@ schedule_tail (struct thread *prev)
 static void
 schedule (void) 
 {
-  struct thread *cur = thread_current ();
+  struct thread *cur = running_thread ();
   struct thread *next = next_thread_to_run ();
+  struct thread *prev = NULL;
 
   ASSERT (intr_get_level () == INTR_OFF);
   ASSERT (cur->status != THREAD_RUNNING);
   ASSERT (is_thread (next));
 
   if (cur != next)
-    {
-      struct thread *prev = switch_threads (cur, next);
-      schedule_tail (prev); 
-    }
+    prev = switch_threads (cur, next);
+  schedule_tail (prev); 
 }
 
 /* Offset of `stack' member within `struct thread'.
diff --git a/src/threads/thread.h b/src/threads/thread.h
index 1dfde5a..aab1a73 100644
--- a/src/threads/thread.h
+++ b/src/threads/thread.h
@@ -35,7 +35,7 @@ struct thread
   };
 
 void thread_init (void);
-void thread_start (void) NO_RETURN;
+void thread_start (void);
 
 typedef void thread_func (void *aux);
 struct thread *thread_create (const char *name, thread_func *, void *);