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.  This is an error if T is not blocked.
 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   ASSERT (t->status == THREAD_BLOCKED);
 197   list_push_back (&ready_list, &t->elem);
 198   t->status = THREAD_READY;
 199   intr_set_level (old_level);
 200 }
 201
 202 /* Returns the name of the running thread. */
 203 const char *
 204 thread_name (void)
 205 {
 206   return thread_current ()->name;
 207 }
 208
 209 /* Returns the running thread.
 210    This is running_thread() plus a couple of sanity checks.
 211    See the big comment at the top of thread.h for details. */
 212 struct thread *
 213 thread_current (void)
 214 {
 215   struct thread *t = running_thread ();
 216
 217   /* Make sure T is really a thread.
 218      If either of these assertions fire, then your thread may
 219      have overflowed its stack.  Each thread has less than 4 kB
 220      of stack, so a few big automatic arrays or moderate
 221      recursion can cause stack overflow. */
 222   ASSERT (is_thread (t));
 223   ASSERT (t->status == THREAD_RUNNING);
 224
 225   return t;
 226 }
 227
 228 /* Returns the running thread's tid. */
 229 tid_t
 230 thread_tid (void)
 231 {
 232   return thread_current ()->tid;
 233 }
 234
 235 /* Deschedules the current thread and destroys it.  Never
 236    returns to the caller. */
 237 void
 238 thread_exit (void)
 239 {
 240   ASSERT (!intr_context ());
 241
 242   /* Just set our status to dying and schedule another process.
 243      We will be destroyed during the call to schedule_tail(). */
 244   intr_disable ();
 245   thread_current ()->status = THREAD_DYING;
 246   schedule ();
 247   NOT_REACHED ();
 248 }
 249
 250 /* Yields the CPU.  The current thread is not put to sleep and
 251    may be scheduled again immediately at the scheduler's whim. */
 252 void
 253 thread_yield (void)
 254 {
 255   struct thread *cur = thread_current ();
 256   enum intr_level old_level;
 257
 258   ASSERT (!intr_context ());
 259
 260   old_level = intr_disable ();
 261   list_push_back (&ready_list, &cur->elem);
 262   cur->status = THREAD_READY;
 263   schedule ();
 264   intr_set_level (old_level);
 265 }
 266
 267 /* Puts the current thread to sleep.  It will not be scheduled
 268    again until awoken by thread_unblock().
 269
 270    This function must be called with interrupts turned off.  It
 271    is usually a better idea to use one of the synchronization
 272    primitives in synch.h. */
 273 void
 274 thread_block (void)
 275 {
 276   ASSERT (!intr_context ());
 277   ASSERT (intr_get_level () == INTR_OFF);
 278
 279   thread_current ()->status = THREAD_BLOCKED;
 280   schedule ();
 281 }
 282 \f
 283 /* Idle thread.  Executes when no other thread is ready to run. */
 284 static void
 285 idle (void *aux UNUSED)
 286 {
 287   idle_thread = thread_current ();
 288
 289   for (;;)
 290     {
 291       /* Let someone else run. */
 292       intr_disable ();
 293       thread_block ();
 294       intr_enable ();
 295
 296       /* Use CPU `hlt' instruction to wait for interrupt. */
 297       asm ("hlt");
 298     }
 299 }
 300
 301 /* Function used as the basis for a kernel thread. */
 302 static void
 303 kernel_thread (thread_func *function, void *aux)
 304 {
 305   ASSERT (function != NULL);
 306
 307   intr_enable ();       /* The scheduler runs with interrupts off. */
 308   function (aux);       /* Execute the thread function. */
 309   thread_exit ();       /* If function() returns, kill the thread. */
 310 }
 311 \f
 312 /* Returns the running thread. */
 313 struct thread *
 314 running_thread (void)
 315 {
 316   uint32_t *esp;
 317
 318   /* Copy the CPU's stack pointer into `esp', and then round that
 319      down to the start of a page.  Because `struct thread' is
 320      always at the beginning of a page and the stack pointer is
 321      somewhere in the middle, this locates the curent thread. */
 322   asm ("movl %%esp, %0\n" : "=g" (esp));
 323   return pg_round_down (esp);
 324 }
 325
 326 /* Returns true if T appears to point to a valid thread. */
 327 static bool
 328 is_thread (struct thread *t)
 329 {
 330   return t != NULL && t->magic == THREAD_MAGIC;
 331 }
 332
 333 /* Creates a new thread named NAME and initializes its fields.
 334    Returns the new thread if successful or a null pointer on
 335    failure. */
 336 static struct thread *
 337 new_thread (const char *name)
 338 {
 339   struct thread *t;
 340
 341   ASSERT (name != NULL);
 342
 343   t = palloc_get (PAL_ZERO);
 344   if (t != NULL)
 345     init_thread (t, name);
 346
 347   return t;
 348 }
 349
 350 /* Initializes T as a new, blocked thread named NAME. */
 351 static void
 352 init_thread (struct thread *t, const char *name)
 353 {
 354   memset (t, 0, sizeof *t);
 355   t->status = THREAD_BLOCKED;
 356   strlcpy (t->name, name, sizeof t->name);
 357   t->stack = (uint8_t *) t + PGSIZE;
 358   t->magic = THREAD_MAGIC;
 359 }
 360
 361 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 362    returns a pointer to the frame's base. */
 363 static void *
 364 alloc_frame (struct thread *t, size_t size)
 365 {
 366   /* Stack data is always allocated in word-size units. */
 367   ASSERT (is_thread (t));
 368   ASSERT (size % sizeof (uint32_t) == 0);
 369
 370   t->stack -= size;
 371   return t->stack;
 372 }
 373
 374 /* Chooses and returns the next thread to be scheduled.  Should
 375    return a thread from the run queue, unless the run queue is
 376    empty.  (If the running thread can continue running, then it
 377    will be in the run queue.)  If the run queue is empty, return
 378    idle_thread. */
 379 static struct thread *
 380 next_thread_to_run (void)
 381 {
 382   if (list_empty (&ready_list))
 383     return idle_thread;
 384   else
 385     return list_entry (list_pop_front (&ready_list), struct thread, elem);
 386 }
 387
 388 /* Destroys T, which must be in the dying state and must not be
 389    the running thread. */
 390 static void
 391 destroy_thread (struct thread *t)
 392 {
 393   ASSERT (is_thread (t));
 394   ASSERT (t->status == THREAD_DYING);
 395   ASSERT (t != thread_current ());
 396
 397 #ifdef USERPROG
 398   addrspace_destroy (t);
 399 #endif
 400   if (t != initial_thread)
 401     palloc_free (t);
 402 }
 403
 404 /* Completes a thread switch by activating the new thread's page
 405    tables, and, if the previous thread is dying, destroying it.
 406
 407    At this function's invocation, we just switched from thread
 408    PREV, the new thread is already running, and interrupts are
 409    still disabled.  This function is normally invoked by
 410    thread_schedule() as its final action before returning, but
 411    the first time a thread is scheduled it is called by
 412    switch_entry() (see switch.S).
 413
 414    After this function and its caller returns, the thread switch
 415    is complete. */
 416 void
 417 schedule_tail (struct thread *prev)
 418 {
 419   struct thread *cur = running_thread ();
 420
 421   ASSERT (intr_get_level () == INTR_OFF);
 422
 423   /* Mark us as running. */
 424   cur->status = THREAD_RUNNING;
 425
 426 #ifdef USERPROG
 427   /* Activate the new address space. */
 428   addrspace_activate (cur);
 429 #endif
 430
 431   /* If the thread we switched from is dying, destroy it.
 432      This must happen late because it's not a good idea to
 433      e.g. destroy the page table you're currently using. */
 434   if (prev != NULL && prev->status == THREAD_DYING)
 435     destroy_thread (prev);
 436 }
 437
 438 /* Schedules a new process.  At entry, interrupts must be off and
 439    the running process's state must have been changed from
 440    running to some other state.  This function finds another
 441    thread to run and switches to it. */
 442 static void
 443 schedule (void)
 444 {
 445   struct thread *cur = running_thread ();
 446   struct thread *next = next_thread_to_run ();
 447   struct thread *prev = NULL;
 448
 449   ASSERT (intr_get_level () == INTR_OFF);
 450   ASSERT (cur->status != THREAD_RUNNING);
 451   ASSERT (is_thread (next));
 452
 453   if (cur != next)
 454     prev = switch_threads (cur, next);
 455   schedule_tail (prev);
 456 }
 457
 458 /* Returns a tid to use for a new thread. */
 459 static tid_t
 460 allocate_tid (void)
 461 {
 462   static tid_t next_tid = 1;
 463   tid_t tid;
 464
 465   lock_acquire (&tid_lock);
 466   tid = next_tid++;
 467   lock_release (&tid_lock);
 468
 469   return tid;
 470 }
 471 \f
 472 /* Offset of `stack' member within `struct thread'.
 473    Used by switch.S, which can't figure it out on its own. */
 474 uint32_t thread_stack_ofs = offsetof (struct thread, stack);