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

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