pintos-os.org Git - pintos-anon/blob - src/userprog/process.c

   1 #include "userprog/process.h"
   2 #include <debug.h>
   3 #include <inttypes.h>
   4 #include <round.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7 #include "userprog/gdt.h"
   8 #include "userprog/pagedir.h"
   9 #include "userprog/tss.h"
  10 #include "filesys/directory.h"
  11 #include "filesys/file.h"
  12 #include "filesys/filesys.h"
  13 #include "threads/flags.h"
  14 #include "threads/init.h"
  15 #include "threads/interrupt.h"
  16 #include "threads/mmu.h"
  17 #include "threads/palloc.h"
  18 #include "threads/thread.h"
  19
  20 static thread_func execute_thread NO_RETURN;
  21 static bool load (const char *cmdline, void (**eip) (void), void **esp);
  22
  23 /* Starts a new thread running a user program loaded from
  24    FILENAME.  The new thread may be scheduled (and may even exit)
  25    before process_execute() returns.  Returns the new process's
  26    thread id, or TID_ERROR if the thread cannot be created. */
  27 tid_t
  28 process_execute (const char *filename)
  29 {
  30   char *fn_copy;
  31   tid_t tid;
  32
  33   /* Make a copy of FILENAME.
  34      Otherwise there's a race between the caller and load(). */
  35   fn_copy = palloc_get_page (0);
  36   if (fn_copy == NULL)
  37     return TID_ERROR;
  38   strlcpy (fn_copy, filename, PGSIZE);
  39
  40   /* Create a new thread to execute FILENAME. */
  41   tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy);
  42   if (tid == TID_ERROR)
  43     palloc_free_page (fn_copy);
  44   return tid;
  45 }
  46
  47 /* A thread function that loads a user process and starts it
  48    running. */
  49 static void
  50 execute_thread (void *filename_)
  51 {
  52   char *filename = filename_;
  53   struct intr_frame if_;
  54   bool success;
  55
  56   /* Initialize interrupt frame and load executable. */
  57   memset (&if_, 0, sizeof if_);
  58   if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
  59   if_.cs = SEL_UCSEG;
  60   if_.eflags = FLAG_IF | FLAG_MBS;
  61   success = load (filename, &if_.eip, &if_.esp);
  62
  63   /* If load failed, quit. */
  64   palloc_free_page (filename);
  65   if (!success)
  66     thread_exit ();
  67
  68   /* Start the user process by simulating a return from an
  69      interrupt, implemented by intr_exit (in
  70      threads/intr-stubs.S).  Because intr_exit takes all of its
  71      arguments on the stack in the form of a `struct intr_frame',
  72      we just point the stack pointer (%esp) to our stack frame
  73      and jump to it. */
  74   asm ("mov %%esp, %0; jmp intr_exit" :: "g" (&if_));
  75   NOT_REACHED ();
  76 }
  77
  78 /* Waits for thread TID to die and returns its exit status.  If
  79    it was terminated by the kernel (i.e. killed due to an
  80    exception), returns -1.  If TID is invalid or if it was not a
  81    child of the calling process, or if process_wait() has already
  82    been successfully called for the given TID, returns -1
  83    immediately, without waiting.
  84
  85    This function will be implemented in problem 2-2.  For now, it
  86    does nothing. */
  87 int
  88 process_wait (tid_t child_tid UNUSED)
  89 {
  90   return -1;
  91 }
  92
  93 /* Free the current process's resources. */
  94 void
  95 process_exit (void)
  96 {
  97   struct thread *cur = thread_current ();
  98   uint32_t *pd;
  99
 100   /* Destroy the current process's page directory and switch back
 101      to the kernel-only page directory. */
 102   pd = cur->pagedir;
 103   if (pd != NULL)
 104     {
 105       /* We must set cur->pagedir to NULL before switching page
 106          directories, or a timer interrupt might switch back to
 107          the process page directory.  The asm statement prevents
 108          GCC from reordering the assignment and the function
 109          calls.  */
 110       cur->pagedir = NULL;
 111       asm volatile ("");
 112
 113       pagedir_activate (NULL);
 114       pagedir_destroy (pd);
 115     }
 116 }
 117
 118 /* Sets up the CPU for running user code in the current
 119    thread. */
 120 void
 121 process_activate (void)
 122 {
 123   struct thread *t = thread_current ();
 124
 125   /* Activate thread's page tables. */
 126   pagedir_activate (t->pagedir);
 127
 128   /* Set thread's kernel stack for use in processing
 129      interrupts. */
 130   tss_set_esp0 ((uint8_t *) t + PGSIZE);
 131 }
 132 \f
 133 /* We load ELF binaries.  The following definitions are taken
 134    from the ELF specification, [ELF1], more-or-less verbatim.  */
 135
 136 /* ELF types.  See [ELF1] 1-2. */
 137 typedef uint32_t Elf32_Word, Elf32_Addr, Elf32_Off;
 138 typedef uint16_t Elf32_Half;
 139
 140 /* For use with ELF types in printf(). */
 141 #define PE32Wx PRIx32   /* Print Elf32_Word in hexadecimal. */
 142 #define PE32Ax PRIx32   /* Print Elf32_Addr in hexadecimal. */
 143 #define PE32Ox PRIx32   /* Print Elf32_Off in hexadecimal. */
 144 #define PE32Hx PRIx16   /* Print Elf32_Half in hexadecimal. */
 145
 146 /* Executable header.  See [ELF1] 1-4 to 1-8.
 147    This appears at the very beginning of an ELF binary. */
 148 struct Elf32_Ehdr
 149   {
 150     unsigned char e_ident[16];
 151     Elf32_Half    e_type;
 152     Elf32_Half    e_machine;
 153     Elf32_Word    e_version;
 154     Elf32_Addr    e_entry;
 155     Elf32_Off     e_phoff;
 156     Elf32_Off     e_shoff;
 157     Elf32_Word    e_flags;
 158     Elf32_Half    e_ehsize;
 159     Elf32_Half    e_phentsize;
 160     Elf32_Half    e_phnum;
 161     Elf32_Half    e_shentsize;
 162     Elf32_Half    e_shnum;
 163     Elf32_Half    e_shstrndx;
 164   };
 165
 166 /* Program header.  See [ELF1] 2-2 to 2-4.
 167    There are e_phnum of these, starting at file offset e_phoff
 168    (see [ELF1] 1-6). */
 169 struct Elf32_Phdr
 170   {
 171     Elf32_Word p_type;
 172     Elf32_Off  p_offset;
 173     Elf32_Addr p_vaddr;
 174     Elf32_Addr p_paddr;
 175     Elf32_Word p_filesz;
 176     Elf32_Word p_memsz;
 177     Elf32_Word p_flags;
 178     Elf32_Word p_align;
 179   };
 180
 181 /* Values for p_type.  See [ELF1] 2-3. */
 182 #define PT_NULL    0            /* Ignore. */
 183 #define PT_LOAD    1            /* Loadable segment. */
 184 #define PT_DYNAMIC 2            /* Dynamic linking info. */
 185 #define PT_INTERP  3            /* Name of dynamic loader. */
 186 #define PT_NOTE    4            /* Auxiliary info. */
 187 #define PT_SHLIB   5            /* Reserved. */
 188 #define PT_PHDR    6            /* Program header table. */
 189 #define PT_STACK   0x6474e551   /* Stack segment. */
 190
 191 /* Flags for p_flags.  See [ELF3] 2-3 and 2-4. */
 192 #define PF_X 1          /* Executable. */
 193 #define PF_W 2          /* Writable. */
 194 #define PF_R 4          /* Readable. */
 195
 196 static bool load_segment (struct file *, const struct Elf32_Phdr *);
 197 static bool setup_stack (void **esp);
 198
 199 /* Aborts loading an executable, with an error message. */
 200 #define LOAD_ERROR(MSG)                                 \
 201         do {                                            \
 202                 printf ("load: %s: ", filename);        \
 203                 printf MSG;                             \
 204                 printf ("\n");                          \
 205                 goto done;                              \
 206         } while (0)
 207
 208 /* Loads an ELF executable from FILENAME into the current thread.
 209    Stores the executable's entry point into *EIP
 210    and its initial stack pointer into *ESP.
 211    Returns true if successful, false otherwise. */
 212 bool
 213 load (const char *filename, void (**eip) (void), void **esp)
 214 {
 215   struct thread *t = thread_current ();
 216   struct Elf32_Ehdr ehdr;
 217   struct file *file = NULL;
 218   off_t file_ofs;
 219   bool success = false;
 220   int i;
 221
 222   /* Allocate and activate page directory. */
 223   t->pagedir = pagedir_create ();
 224   if (t->pagedir == NULL)
 225     LOAD_ERROR (("page directory allocation failed"));
 226   process_activate ();
 227
 228   /* Open executable file. */
 229   file = filesys_open (filename);
 230   if (file == NULL)
 231     LOAD_ERROR (("open failed"));
 232
 233   /* Read and verify executable header. */
 234   if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr)
 235     LOAD_ERROR (("error reading executable header"));
 236   if (memcmp (ehdr.e_ident, "\177ELF\1\1\1", 7) != 0)
 237     LOAD_ERROR (("file is not ELF"));
 238   if (ehdr.e_type != 2)
 239     LOAD_ERROR (("ELF file is not an executable"));
 240   if (ehdr.e_machine != 3)
 241     LOAD_ERROR (("ELF executable is not x86"));
 242   if (ehdr.e_version != 1)
 243     LOAD_ERROR (("ELF executable has unknown version %d",
 244                  (int) ehdr.e_version));
 245   if (ehdr.e_phentsize != sizeof (struct Elf32_Phdr))
 246     LOAD_ERROR (("bad ELF program header size"));
 247   if (ehdr.e_phnum > 1024)
 248     LOAD_ERROR (("too many ELF program headers"));
 249
 250   /* Read program headers. */
 251   file_ofs = ehdr.e_phoff;
 252   for (i = 0; i < ehdr.e_phnum; i++)
 253     {
 254       struct Elf32_Phdr phdr;
 255
 256       if (file_ofs < 0 || file_ofs > file_length (file))
 257         LOAD_ERROR (("bad file offset %ld", (long) file_ofs));
 258       file_seek (file, file_ofs);
 259
 260       if (file_read (file, &phdr, sizeof phdr) != sizeof phdr)
 261         LOAD_ERROR (("error reading program header"));
 262       file_ofs += sizeof phdr;
 263       switch (phdr.p_type)
 264         {
 265         case PT_NULL:
 266         case PT_NOTE:
 267         case PT_PHDR:
 268         case PT_STACK:
 269           /* Ignore this segment. */
 270           break;
 271         case PT_DYNAMIC:
 272         case PT_INTERP:
 273         case PT_SHLIB:
 274           /* Reject the executable. */
 275           LOAD_ERROR (("unsupported ELF segment type %d\n", phdr.p_type));
 276           break;
 277         default:
 278           printf ("unknown ELF segment type %08x\n", phdr.p_type);
 279           break;
 280         case PT_LOAD:
 281           if (!load_segment (file, &phdr))
 282             goto done;
 283           break;
 284         }
 285     }
 286
 287   /* Set up stack. */
 288   if (!setup_stack (esp))
 289     goto done;
 290
 291   /* Start address. */
 292   *eip = (void (*) (void)) ehdr.e_entry;
 293
 294   success = true;
 295
 296  done:
 297   /* We arrive here whether the load is successful or not. */
 298   file_close (file);
 299   return success;
 300 }
 301 \f
 302 /* load() helpers. */
 303
 304 static bool install_page (void *upage, void *kpage);
 305
 306 /* Loads the segment described by PHDR from FILE into user
 307    address space.  Return true if successful, false otherwise. */
 308 static bool
 309 load_segment (struct file *file, const struct Elf32_Phdr *phdr)
 310 {
 311   void *start, *end;  /* Page-rounded segment start and end. */
 312   uint8_t *upage;     /* Iterator from start to end. */
 313   off_t filesz_left;  /* Bytes left of file data (as opposed to
 314                          zero-initialized bytes). */
 315
 316   /* Is this a read-only segment?  Not currently used, so it's
 317      commented out.  You'll want to use it when implementing VM
 318      to decide whether to page the segment from its executable or
 319      from swap. */
 320   //bool read_only = (phdr->p_flags & PF_W) == 0;
 321
 322   ASSERT (file != NULL);
 323   ASSERT (phdr != NULL);
 324   ASSERT (phdr->p_type == PT_LOAD);
 325
 326   /* [ELF1] 2-2 says that p_offset and p_vaddr must be congruent
 327      modulo PGSIZE. */
 328   if (phdr->p_offset % PGSIZE != phdr->p_vaddr % PGSIZE)
 329     {
 330       printf ("%#08"PE32Ox" and %#08"PE32Ax" not congruent modulo %#x\n",
 331               phdr->p_offset, phdr->p_vaddr, (unsigned) PGSIZE);
 332       return false;
 333     }
 334
 335   /* p_offset must point within file. */
 336   if (phdr->p_offset > (Elf32_Off) file_length (file))
 337     {
 338       printf ("bad p_offset %"PE32Ox, phdr->p_offset);
 339       return false;
 340     }
 341
 342   /* [ELF1] 2-3 says that p_memsz must be at least as big as
 343      p_filesz. */
 344   if (phdr->p_memsz < phdr->p_filesz)
 345     {
 346       printf ("p_memsz (%08"PE32Wx") < p_filesz (%08"PE32Wx")\n",
 347               phdr->p_memsz, phdr->p_filesz);
 348       return false;
 349     }
 350
 351   /* Validate virtual memory region to be mapped.
 352      The region must both start and end within the user address
 353      space range starting at 0 and ending at PHYS_BASE (typically
 354      3 GB == 0xc0000000). */
 355   start = pg_round_down ((void *) phdr->p_vaddr);
 356   end = pg_round_up ((void *) (phdr->p_vaddr + phdr->p_memsz));
 357   if (start >= PHYS_BASE || end >= PHYS_BASE || end < start)
 358     {
 359       printf ("bad virtual region %08lx...%08lx\n",
 360               (unsigned long) start, (unsigned long) end);
 361       return false;
 362     }
 363
 364   /* Load the segment page-by-page into memory. */
 365   filesz_left = phdr->p_filesz + (phdr->p_vaddr & PGMASK);
 366   file_seek (file, ROUND_DOWN (phdr->p_offset, PGSIZE));
 367   for (upage = start; upage < (uint8_t *) end; upage += PGSIZE)
 368     {
 369       /* We want to read min(PGSIZE, filesz_left) bytes from the
 370          file into the page and zero the rest. */
 371       size_t read_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left;
 372       size_t zero_bytes = PGSIZE - read_bytes;
 373       uint8_t *kpage = palloc_get_page (PAL_USER);
 374       if (kpage == NULL)
 375         return false;
 376
 377       /* Do the reading and zeroing. */
 378       if (file_read (file, kpage, read_bytes) != (int) read_bytes)
 379         {
 380           palloc_free_page (kpage);
 381           return false;
 382         }
 383       memset (kpage + read_bytes, 0, zero_bytes);
 384       filesz_left -= read_bytes;
 385
 386       /* Add the page to the process's address space. */
 387       if (!install_page (upage, kpage))
 388         {
 389           palloc_free_page (kpage);
 390           return false;
 391         }
 392     }
 393
 394   return true;
 395 }
 396
 397 /* Create a minimal stack by mapping a zeroed page at the top of
 398    user virtual memory. */
 399 static bool
 400 setup_stack (void **esp)
 401 {
 402   uint8_t *kpage;
 403   bool success = false;
 404
 405   kpage = palloc_get_page (PAL_USER | PAL_ZERO);
 406   if (kpage != NULL)
 407     {
 408       success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage);
 409       if (success)
 410         *esp = PHYS_BASE;
 411       else
 412         palloc_free_page (kpage);
 413     }
 414   else
 415     printf ("failed to allocate process stack\n");
 416
 417   return success;
 418 }
 419
 420 /* Adds a mapping from user virtual address UPAGE to kernel
 421    virtual address KPAGE to the page table.  Fails if UPAGE is
 422    already mapped or if memory allocation fails. */
 423 static bool
 424 install_page (void *upage, void *kpage)
 425 {
 426   struct thread *t = thread_current ();
 427
 428   /* Verify that there's not already a page at that virtual
 429      address, then map our page there. */
 430   return (pagedir_get_page (t->pagedir, upage) == NULL
 431           && pagedir_set_page (t->pagedir, upage, kpage, true));
 432 }