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