pintos-os.org Git - pintos-anon/blob - src/threads/thread.c

   1 #include "thread.h"
   2 #include <stddef.h>
   3 #include "debug.h"
   4 #include "interrupt.h"
   5 #include "intr-stubs.h"
   6 #include "lib.h"
   7 #include "mmu.h"
   8 #include "palloc.h"
   9 #include "random.h"
  10 #include "switch.h"
  11 #ifdef USERPROG
  12 #include "gdt.h"
  13 #endif
  14
  15 /* Value for struct thread's `magic' member.
  16    Used to detect stack overflow.  See the big comment at the top
  17    of thread.h for details. */
  18 #define THREAD_MAGIC 0x1234abcdu
  19
  20 /* List of processes in THREAD_READY state, that is, processes
  21    that are ready to run but not actually running. */
  22 static struct list run_queue;
  23
  24 /* Idle thread. */
  25 static struct thread *idle_thread;      /* Thread. */
  26 static void idle (void *aux UNUSED);    /* Thread function. */
  27
  28 /* Stack frame for kernel_thread(). */
  29 struct kernel_thread_frame
  30   {
  31     void *eip;                  /* Return address. */
  32     thread_func *function;      /* Function to call. */
  33     void *aux;                  /* Auxiliary data for function. */
  34   };
  35
  36 static void kernel_thread (thread_func *, void *aux);
  37
  38 static struct thread *running_thread (void);
  39 static struct thread *next_thread_to_run (void);
  40 static struct thread *new_thread (const char *name);
  41 static void init_thread (struct thread *, const char *name);
  42 static bool is_thread (struct thread *);
  43 static void *alloc_frame (struct thread *, size_t size);
  44 static void destroy_thread (struct thread *);
  45 static void schedule (void);
  46 void schedule_tail (struct thread *prev);
  47
  48 /* Initializes the threading system by transforming the code
  49    that's currently running into a thread.  Note that this is
  50    possible only because the loader was careful to put the bottom
  51    of the stack at a page boundary; it won't work in general.
  52    Also initializes the run queue.
  53
  54    After calling this function, be sure to initialize the page
  55    allocator before trying to create any threads with
  56    thread_create(). */
  57 void
  58 thread_init (void)
  59 {
  60   struct thread *t;
  61
  62   ASSERT (intr_get_level () == INTR_OFF);
  63
  64   /* Set up a thread structure for the running thread. */
  65   t = running_thread ();
  66   init_thread (t, "main");
  67   t->status = THREAD_RUNNING;
  68
  69   /* Initialize run queue. */
  70   list_init (&run_queue);
  71 }
  72
  73 /* Starts preemptive thread scheduling by enabling interrupts.
  74    Also creates the idle thread. */
  75 void
  76 thread_start (void)
  77 {
  78   /* Create idle thread. */
  79   idle_thread = thread_create ("idle", idle, NULL);
  80   idle_thread->status = THREAD_BLOCKED;
  81
  82   /* Enable interrupts. */
  83   intr_enable ();
  84 }
  85
  86 /* Creates a new kernel thread named NAME, which executes
  87    FUNCTION passing AUX as the argument, and adds it to the ready
  88    queue.  If thread_start() has been called, then the new thread
  89    may be scheduled before thread_create() returns.  Use a
  90    semaphore or some other form of synchronization if you need to
  91    ensure ordering. */
  92 struct thread *
  93 thread_create (const char *name, thread_func *function, void *aux)
  94 {
  95   struct thread *t;
  96   struct kernel_thread_frame *kf;
  97   struct switch_entry_frame *ef;
  98   struct switch_threads_frame *sf;
  99
 100   ASSERT (function != NULL);
 101
 102   t = new_thread (name);
 103
 104   /* Stack frame for kernel_thread(). */
 105   kf = alloc_frame (t, sizeof *kf);
 106   kf->eip = NULL;
 107   kf->function = function;
 108   kf->aux = aux;
 109
 110   /* Stack frame for switch_entry(). */
 111   ef = alloc_frame (t, sizeof *ef);
 112   ef->eip = (void (*) (void)) kernel_thread;
 113
 114   /* Stack frame for switch_threads(). */
 115   sf = alloc_frame (t, sizeof *sf);
 116   sf->eip = switch_entry;
 117
 118   /* Add to run queue. */
 119   thread_unblock (t);
 120
 121   return t;
 122 }
 123
 124 #ifdef USERPROG
 125 /* Starts a new thread running a user program loaded from
 126    FILENAME, and adds it to the ready queue.  If thread_start()
 127    has been called, then new thread may be scheduled before
 128    thread_execute() returns.*/
 129 bool
 130 thread_execute (const char *filename)
 131 {
 132   struct thread *t;
 133   struct intr_frame *if_;
 134   struct switch_entry_frame *ef;
 135   struct switch_threads_frame *sf;
 136   void (*start) (void);
 137
 138   ASSERT (filename != NULL);
 139
 140   t = new_thread (filename);
 141   if (t == NULL)
 142     return false;
 143
 144   if (!addrspace_load (t, filename, &start))
 145     PANIC ("%s: program load failed", filename);
 146
 147   /* Interrupt frame. */
 148   if_ = alloc_frame (t, sizeof *if_);
 149   if_->es = SEL_UDSEG;
 150   if_->ds = SEL_UDSEG;
 151   if_->eip = start;
 152   if_->cs = SEL_UCSEG;
 153   if_->eflags = FLAG_IF | FLAG_MBS;
 154   if_->esp = PHYS_BASE;
 155   if_->ss = SEL_UDSEG;
 156
 157   /* Stack frame for switch_entry(). */
 158   ef = alloc_frame (t, sizeof *ef);
 159   ef->eip = intr_exit;
 160
 161   /* Stack frame for switch_threads(). */
 162   sf = alloc_frame (t, sizeof *sf);
 163   sf->eip = switch_entry;
 164
 165   /* Add to run queue. */
 166   thread_unblock (t);
 167
 168   return true;
 169 }
 170 #endif
 171
 172 /* Transitions a blocked thread T from its current state to the
 173    ready-to-run state.  If T is not blocked, there is no effect.
 174    (Use thread_yield() to make the running thread ready.) */
 175 void
 176 thread_unblock (struct thread *t)
 177 {
 178   enum intr_level old_level;
 179
 180   ASSERT (is_thread (t));
 181
 182   old_level = intr_disable ();
 183   if (t->status == THREAD_BLOCKED)
 184     {
 185       list_push_back (&run_queue, &t->elem);
 186       t->status = THREAD_READY;
 187     }
 188   intr_set_level (old_level);
 189 }
 190
 191 /* Returns the name of thread T. */
 192 const char *
 193 thread_name (struct thread *t)
 194 {
 195   ASSERT (is_thread (t));
 196   return t->name;
 197 }
 198
 199 /* Returns the running thread.
 200    This is running_thread() plus a couple of sanity checks.
 201    See the big comment at the top of thread.h for details. */
 202 struct thread *
 203 thread_current (void)
 204 {
 205   struct thread *t = running_thread ();
 206
 207   /* Make sure T is really a thread.
 208      If either of these assertions fire, then your thread may
 209      have overflowed its stack.  Each thread has less than 4 kB
 210      of stack, so a few big automatic arrays or moderate
 211      recursion can cause stack overflow. */
 212   ASSERT (is_thread (t));
 213   ASSERT (t->status == THREAD_RUNNING);
 214
 215   return t;
 216 }
 217
 218 /* Deschedules the current thread and destroys it.  Never
 219    returns to the caller. */
 220 void
 221 thread_exit (void)
 222 {
 223   ASSERT (!intr_context ());
 224
 225   /* Just set our status to dying and schedule another process.
 226      We will be destroyed during the call to schedule_tail(). */
 227   intr_disable ();
 228   thread_current ()->status = THREAD_DYING;
 229   schedule ();
 230   NOT_REACHED ();
 231 }
 232
 233 /* Yields the CPU.  The current thread is not put to sleep and
 234    may be scheduled again immediately at the scheduler's whim. */
 235 void
 236 thread_yield (void)
 237 {
 238   struct thread *cur = thread_current ();
 239   enum intr_level old_level;
 240
 241   ASSERT (!intr_context ());
 242
 243   old_level = intr_disable ();
 244   list_push_back (&run_queue, &cur->elem);
 245   cur->status = THREAD_READY;
 246   schedule ();
 247   intr_set_level (old_level);
 248 }
 249
 250 /* Puts the current thread to sleep.  It will not be scheduled
 251    again until awoken by thread_unblock().
 252
 253    This function must be called with interrupts turned off.  It
 254    is usually a better idea to use one of the synchronization
 255    primitives in synch.h. */
 256 void
 257 thread_block (void)
 258 {
 259   ASSERT (!intr_context ());
 260   ASSERT (intr_get_level () == INTR_OFF);
 261
 262   thread_current ()->status = THREAD_BLOCKED;
 263   schedule ();
 264 }
 265 \f
 266 /* Idle thread.  Executes when no other thread is ready to run. */
 267 static void
 268 idle (void *aux UNUSED)
 269 {
 270   for (;;)
 271     {
 272       /* Wait for an interrupt. */
 273       DEBUG (idle, "idle");
 274       asm ("hlt");
 275
 276       /* Let someone else run. */
 277       intr_disable ();
 278       thread_block ();
 279       intr_enable ();
 280     }
 281 }
 282
 283 /* Function used as the basis for a kernel thread. */
 284 static void
 285 kernel_thread (thread_func *function, void *aux)
 286 {
 287   ASSERT (function != NULL);
 288
 289   intr_enable ();       /* The scheduler runs with interrupts off. */
 290   function (aux);       /* Execute the thread function. */
 291   thread_exit ();       /* If function() returns, kill the thread. */
 292 }
 293 \f
 294 /* Returns the running thread. */
 295 struct thread *
 296 running_thread (void)
 297 {
 298   uint32_t *esp;
 299
 300   /* Copy the CPU's stack pointer into `esp', and then round that
 301      down to the start of a page.  Because `struct thread' is
 302      always at the beginning of a page and the stack pointer is
 303      somewhere in the middle, this locates the curent thread. */
 304   asm ("movl %%esp, %0\n" : "=g" (esp));
 305   return pg_round_down (esp);
 306 }
 307
 308 /* Returns true if T appears to point to a valid thread. */
 309 static bool
 310 is_thread (struct thread *t)
 311 {
 312   return t != NULL && t->magic == THREAD_MAGIC;
 313 }
 314
 315 /* Creates a new thread named NAME and initializes its fields.
 316    Returns the new thread if successful or a null pointer on
 317    failure. */
 318 static struct thread *
 319 new_thread (const char *name)
 320 {
 321   struct thread *t;
 322
 323   ASSERT (name != NULL);
 324
 325   t = palloc_get (PAL_ZERO);
 326   if (t != NULL)
 327     init_thread (t, name);
 328
 329   return t;
 330 }
 331
 332 /* Initializes T as a new, blocked thread named NAME. */
 333 static void
 334 init_thread (struct thread *t, const char *name)
 335 {
 336   memset (t, 0, sizeof *t);
 337   strlcpy (t->name, name, sizeof t->name);
 338   t->stack = (uint8_t *) t + PGSIZE;
 339   t->status = THREAD_BLOCKED;
 340   t->magic = THREAD_MAGIC;
 341 }
 342
 343 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 344    returns a pointer to the frame's base. */
 345 static void *
 346 alloc_frame (struct thread *t, size_t size)
 347 {
 348   /* Stack data is always allocated in word-size units. */
 349   ASSERT (is_thread (t));
 350   ASSERT (size % sizeof (uint32_t) == 0);
 351
 352   t->stack -= size;
 353   return t->stack;
 354 }
 355
 356 /* Chooses and returns the next thread to be scheduled.  Should
 357    return a thread from the run queue, unless the run queue is
 358    empty.  (If the running thread can continue running, then it
 359    will be in the run queue.)  If the run queue is empty, return
 360    idle_thread. */
 361 static struct thread *
 362 next_thread_to_run (void)
 363 {
 364   if (list_empty (&run_queue))
 365     return idle_thread;
 366   else
 367     return list_entry (list_pop_front (&run_queue), struct thread, elem);
 368 }
 369
 370 /* Destroys T, which must be in the dying state and must not be
 371    the running thread. */
 372 static void
 373 destroy_thread (struct thread *t)
 374 {
 375   ASSERT (is_thread (t));
 376   ASSERT (t->status == THREAD_DYING);
 377   ASSERT (t != thread_current ());
 378
 379 #ifdef USERPROG
 380   addrspace_destroy (t);
 381 #endif
 382   palloc_free (t);
 383 }
 384
 385 /* Completes a thread switch by activating the new thread's page
 386    tables, and, if the previous thread is dying, destroying it.
 387
 388    At this function's invocation, we just switched from thread
 389    PREV, the new thread is already running, and interrupts are
 390    still disabled.  This function is normally invoked by
 391    thread_schedule() as its final action before returning, but
 392    the first time a thread is scheduled it is called by
 393    switch_entry() (see switch.S).
 394
 395    After this function and its caller returns, the thread switch
 396    is complete. */
 397 void
 398 schedule_tail (struct thread *prev)
 399 {
 400   struct thread *cur = running_thread ();
 401
 402   ASSERT (intr_get_level () == INTR_OFF);
 403
 404   /* Mark us as running. */
 405   cur->status = THREAD_RUNNING;
 406
 407 #ifdef USERPROG
 408   /* Activate the new address space. */
 409   addrspace_activate (cur);
 410 #endif
 411
 412   /* If the thread we switched from is dying, destroy it.
 413      This must happen late because it's not a good idea to
 414      e.g. destroy the page table you're currently using. */
 415   if (prev != NULL && prev->status == THREAD_DYING)
 416     destroy_thread (prev);
 417 }
 418
 419 /* Schedules a new process.  At entry, interrupts must be off and
 420    the running process's state must have been changed from
 421    running to some other state.  This function finds another
 422    thread to run and switches to it. */
 423 static void
 424 schedule (void)
 425 {
 426   struct thread *cur = running_thread ();
 427   struct thread *next = next_thread_to_run ();
 428   struct thread *prev = NULL;
 429
 430   ASSERT (intr_get_level () == INTR_OFF);
 431   ASSERT (cur->status != THREAD_RUNNING);
 432   ASSERT (is_thread (next));
 433
 434   if (cur != next)
 435     prev = switch_threads (cur, next);
 436   schedule_tail (prev);
 437 }
 438 \f
 439 /* Offset of `stack' member within `struct thread'.
 440    Used by switch.S, which can't figure it out on its own. */
 441 uint32_t thread_stack_ofs = offsetof (struct thread, stack);