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