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

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