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 execute_thread 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, execute_thread, 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 execute_thread (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 void
 122 process_activate (void)
 123 {
 124   struct thread *t = thread_current ();
 125
 126   /* Activate thread's page tables. */
 127   pagedir_activate (t->pagedir);
 128
 129   /* Set thread's kernel stack for use in processing
 130      interrupts. */
 131   tss_set_esp0 ((uint8_t *) t + PGSIZE);
 132 }
 133 \f
 134 /* We load ELF binaries.  The following definitions are taken
 135    from the ELF specification, [ELF1], more-or-less verbatim.  */
 136
 137 /* ELF types.  See [ELF1] 1-2. */
 138 typedef uint32_t Elf32_Word, Elf32_Addr, Elf32_Off;
 139 typedef uint16_t Elf32_Half;
 140
 141 /* For use with ELF types in printf(). */
 142 #define PE32Wx PRIx32   /* Print Elf32_Word in hexadecimal. */
 143 #define PE32Ax PRIx32   /* Print Elf32_Addr in hexadecimal. */
 144 #define PE32Ox PRIx32   /* Print Elf32_Off in hexadecimal. */
 145 #define PE32Hx PRIx16   /* Print Elf32_Half in hexadecimal. */
 146
 147 /* Executable header.  See [ELF1] 1-4 to 1-8.
 148    This appears at the very beginning of an ELF binary. */
 149 struct Elf32_Ehdr
 150   {
 151     unsigned char e_ident[16];
 152     Elf32_Half    e_type;
 153     Elf32_Half    e_machine;
 154     Elf32_Word    e_version;
 155     Elf32_Addr    e_entry;
 156     Elf32_Off     e_phoff;
 157     Elf32_Off     e_shoff;
 158     Elf32_Word    e_flags;
 159     Elf32_Half    e_ehsize;
 160     Elf32_Half    e_phentsize;
 161     Elf32_Half    e_phnum;
 162     Elf32_Half    e_shentsize;
 163     Elf32_Half    e_shnum;
 164     Elf32_Half    e_shstrndx;
 165   };
 166
 167 /* Program header.  See [ELF1] 2-2 to 2-4.
 168    There are e_phnum of these, starting at file offset e_phoff
 169    (see [ELF1] 1-6). */
 170 struct Elf32_Phdr
 171   {
 172     Elf32_Word p_type;
 173     Elf32_Off  p_offset;
 174     Elf32_Addr p_vaddr;
 175     Elf32_Addr p_paddr;
 176     Elf32_Word p_filesz;
 177     Elf32_Word p_memsz;
 178     Elf32_Word p_flags;
 179     Elf32_Word p_align;
 180   };
 181
 182 /* Values for p_type.  See [ELF1] 2-3. */
 183 #define PT_NULL    0            /* Ignore. */
 184 #define PT_LOAD    1            /* Loadable segment. */
 185 #define PT_DYNAMIC 2            /* Dynamic linking info. */
 186 #define PT_INTERP  3            /* Name of dynamic loader. */
 187 #define PT_NOTE    4            /* Auxiliary info. */
 188 #define PT_SHLIB   5            /* Reserved. */
 189 #define PT_PHDR    6            /* Program header table. */
 190 #define PT_STACK   0x6474e551   /* Stack segment. */
 191
 192 /* Flags for p_flags.  See [ELF3] 2-3 and 2-4. */
 193 #define PF_X 1          /* Executable. */
 194 #define PF_W 2          /* Writable. */
 195 #define PF_R 4          /* Readable. */
 196
 197 static bool setup_stack (void **esp);
 198 static bool validate_segment (const struct Elf32_Phdr *, struct file *);
 199 static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
 200                           uint32_t read_bytes, uint32_t zero_bytes,
 201                           bool writable);
 202
 203 /* Loads an ELF executable from FILE_NAME into the current thread.
 204    Stores the executable's entry point into *EIP
 205    and its initial stack pointer into *ESP.
 206    Returns true if successful, false otherwise. */
 207 bool
 208 load (const char *file_name, void (**eip) (void), void **esp)
 209 {
 210   struct thread *t = thread_current ();
 211   struct Elf32_Ehdr ehdr;
 212   struct file *file = NULL;
 213   off_t file_ofs;
 214   bool success = false;
 215   int i;
 216
 217   /* Allocate and activate page directory. */
 218   t->pagedir = pagedir_create ();
 219   if (t->pagedir == NULL)
 220     goto done;
 221   process_activate ();
 222
 223   /* Open executable file. */
 224   file = filesys_open (file_name);
 225   if (file == NULL)
 226     {
 227       printf ("load: %s: open failed\n", file_name);
 228       goto done;
 229     }
 230
 231   /* Read and verify executable header. */
 232   if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
 233       || memcmp (ehdr.e_ident, "\177ELF\1\1\1", 7)
 234       || ehdr.e_type != 2
 235       || ehdr.e_machine != 3
 236       || ehdr.e_version != 1
 237       || ehdr.e_phentsize != sizeof (struct Elf32_Phdr)
 238       || ehdr.e_phnum > 1024)
 239     {
 240       printf ("load: %s: error loading executable\n", file_name);
 241       goto done;
 242     }
 243
 244   /* Read program headers. */
 245   file_ofs = ehdr.e_phoff;
 246   for (i = 0; i < ehdr.e_phnum; i++)
 247     {
 248       struct Elf32_Phdr phdr;
 249
 250       if (file_ofs < 0 || file_ofs > file_length (file))
 251         goto done;
 252       file_seek (file, file_ofs);
 253
 254       if (file_read (file, &phdr, sizeof phdr) != sizeof phdr)
 255         goto done;
 256       file_ofs += sizeof phdr;
 257       switch (phdr.p_type)
 258         {
 259         case PT_NULL:
 260         case PT_NOTE:
 261         case PT_PHDR:
 262         case PT_STACK:
 263         default:
 264           /* Ignore this segment. */
 265           break;
 266         case PT_DYNAMIC:
 267         case PT_INTERP:
 268         case PT_SHLIB:
 269           goto done;
 270         case PT_LOAD:
 271           if (validate_segment (&phdr, file))
 272             {
 273               bool writable = (phdr.p_flags & PF_W) != 0;
 274               uint32_t file_page = phdr.p_offset & ~PGMASK;
 275               uint32_t mem_page = phdr.p_vaddr & ~PGMASK;
 276               uint32_t page_offset = phdr.p_vaddr & PGMASK;
 277               uint32_t read_bytes, zero_bytes;
 278               if (phdr.p_filesz > 0)
 279                 {
 280                   /* Normal segment.
 281                      Read initial part from disk and zero the rest. */
 282                   read_bytes = page_offset + phdr.p_filesz;
 283                   zero_bytes = (ROUND_UP (page_offset + phdr.p_memsz, PGSIZE)
 284                                 - read_bytes);
 285                 }
 286               else
 287                 {
 288                   /* Entirely zero.
 289                      Don't read anything from disk. */
 290                   read_bytes = 0;
 291                   zero_bytes = ROUND_UP (page_offset + phdr.p_memsz, PGSIZE);
 292                 }
 293               if (!load_segment (file, file_page, (void *) mem_page,
 294                                  read_bytes, zero_bytes, writable))
 295                 goto done;
 296             }
 297           else
 298             goto done;
 299           break;
 300         }
 301     }
 302
 303   /* Set up stack. */
 304   if (!setup_stack (esp))
 305     goto done;
 306
 307   /* Start address. */
 308   *eip = (void (*) (void)) ehdr.e_entry;
 309
 310   success = true;
 311
 312  done:
 313   /* We arrive here whether the load is successful or not. */
 314   file_close (file);
 315   return success;
 316 }
 317 \f
 318 /* load() helpers. */
 319
 320 static bool install_page (void *upage, void *kpage, bool writable);
 321
 322 /* Checks whether PHDR describes a valid, loadable segment in
 323    FILE and returns true if so, false otherwise. */
 324 static bool
 325 validate_segment (const struct Elf32_Phdr *phdr, struct file *file)
 326 {
 327   /* p_offset and p_vaddr must have the same page offset. */
 328   if ((phdr->p_offset & PGMASK) != (phdr->p_vaddr & PGMASK))
 329     return false;
 330
 331   /* p_offset must point within FILE. */
 332   if (phdr->p_offset > (Elf32_Off) file_length (file))
 333     return false;
 334
 335   /* p_memsz must be at least as big as p_filesz. */
 336   if (phdr->p_memsz < phdr->p_filesz)
 337     return false;
 338
 339   /* The segment must not be empty. */
 340   if (phdr->p_memsz == 0)
 341     return false;
 342
 343   /* The virtual memory region must both start and end within the
 344      user address space range. */
 345   if (!is_user_vaddr ((void *) phdr->p_vaddr))
 346     return false;
 347   if (!is_user_vaddr ((void *) (phdr->p_vaddr + phdr->p_memsz)))
 348     return false;
 349
 350   /* The region cannot "wrap around" across the kernel virtual
 351      address space. */
 352   if (phdr->p_vaddr + phdr->p_memsz < phdr->p_vaddr)
 353     return false;
 354
 355   /* Disallow mapping page 0.
 356      Not only is it a bad idea to map page 0, but if we allowed
 357      it then user code that passed a null pointer to system calls
 358      could quite likely panic the kernel by way of null pointer
 359      assertions in memcpy(), etc. */
 360   if (phdr->p_vaddr < PGSIZE)
 361     return false;
 362
 363   /* It's okay. */
 364   return true;
 365 }
 366
 367 /* Loads a segment starting at offset OFS in FILE at address
 368    UPAGE.  In total, READ_BYTES + ZERO_BYTES bytes of virtual
 369    memory are initialized, as follows:
 370
 371         - READ_BYTES bytes at UPAGE must be read from FILE
 372           starting at offset OFS.
 373
 374         - ZERO_BYTES bytes at UPAGE + READ_BYTES must be zeroed.
 375
 376    The pages initialized by this function must be writable by the
 377    user process if WRITABLE is true, read-only otherwise.
 378
 379    Return true if successful, false if a memory allocation error
 380    or disk read error occurs. */
 381 static bool
 382 load_segment (struct file *file, off_t ofs, uint8_t *upage,
 383               uint32_t read_bytes, uint32_t zero_bytes, bool writable)
 384 {
 385   ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);
 386   ASSERT (pg_ofs (upage) == 0);
 387   ASSERT (ofs % PGSIZE == 0);
 388
 389   file_seek (file, ofs);
 390   while (read_bytes > 0 || zero_bytes > 0)
 391     {
 392       /* Calculate how to fill this page.
 393          We will read PAGE_READ_BYTES bytes from FILE
 394          and zero the final PAGE_ZERO_BYTES bytes. */
 395       size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
 396       size_t page_zero_bytes = PGSIZE - page_read_bytes;
 397
 398       /* Get a page of memory. */
 399       uint8_t *kpage = palloc_get_page (PAL_USER);
 400       if (kpage == NULL)
 401         return false;
 402
 403       /* Load this page. */
 404       if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
 405         {
 406           palloc_free_page (kpage);
 407           return false;
 408         }
 409       memset (kpage + page_read_bytes, 0, page_zero_bytes);
 410
 411       /* Add the page to the process's address space. */
 412       if (!install_page (upage, kpage, writable))
 413         {
 414           palloc_free_page (kpage);
 415           return false;
 416         }
 417
 418       /* Advance. */
 419       read_bytes -= page_read_bytes;
 420       zero_bytes -= page_zero_bytes;
 421       upage += PGSIZE;
 422     }
 423   return true;
 424 }
 425
 426 /* Create a minimal stack by mapping a zeroed page at the top of
 427    user virtual memory. */
 428 static bool
 429 setup_stack (void **esp)
 430 {
 431   uint8_t *kpage;
 432   bool success = false;
 433
 434   kpage = palloc_get_page (PAL_USER | PAL_ZERO);
 435   if (kpage != NULL)
 436     {
 437       success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true);
 438       if (success)
 439         *esp = PHYS_BASE;
 440       else
 441         palloc_free_page (kpage);
 442     }
 443   return success;
 444 }
 445
 446 /* Adds a mapping from user virtual address UPAGE to kernel
 447    virtual address KPAGE to the page table.
 448    If WRITABLE is true, the user process may modify the page;
 449    otherwise, it is read-only.
 450    UPAGE must not already be mapped.
 451    KPAGE should probably be a page obtained from the user pool
 452    with palloc_get_page().
 453    Returns true on success, false if UPAGE is already mapped or
 454    if memory allocation fails. */
 455 static bool
 456 install_page (void *upage, void *kpage, bool writable)
 457 {
 458   struct thread *t = thread_current ();
 459
 460   /* Verify that there's not already a page at that virtual
 461      address, then map our page there. */
 462   return (pagedir_get_page (t->pagedir, upage) == NULL
 463           && pagedir_set_page (t->pagedir, upage, kpage, writable));
 464 }