VPATH := $(VPATH):$(TOP_SRCDIR)/devices
VPATH := $(VPATH):$(TOP_SRCDIR)/lib
VPATH := $(VPATH):$(TOP_SRCDIR)/filesys
+VPATH := $(VPATH):$(TOP_SRCDIR)/userprog
-include *.d
THREADS_SRC += interrupt.c # Interrupt core.
THREADS_SRC += intr-stubs.S # Interrupt stubs.
THREADS_SRC += synch.c # Synchronization.
+THREADS_SRC += paging.c # Page tables.
THREADS_SRC += palloc.c # Page allocator.
THREADS_SRC += malloc.c # Subpage allocator.
FILESYS_SRC += file.c # Individual files.
FILESYS_SRC += filesys-stub.c # Stub helper code.
+# User process code.
+USERPROG_SRC = addrspace.c # Address spaces.
+
# Objects.
OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES)))
+#include "init.h"
#include <stdint.h>
#include <stddef.h>
#include <limits.h>
#include "lib.h"
#include "malloc.h"
#include "mmu.h"
+#include "paging.h"
#include "palloc.h"
#include "random.h"
#include "serial.h"
/* Amount of physical memory, in 4 kB pages. */
size_t ram_pages;
-static void init_page_table (void);
-static void setup_gdt (void);
+static void gdt_init (void);
void power_off (void);
-struct thread *a, *b;
-
static void
-tfunc (void *aux UNUSED)
+main_thread (void *aux UNUSED)
{
- for (;;)
- {
- size_t count, i;
- if (random_ulong () % 5 == 0)
- {
- printk ("%s exiting\n", thread_current ()->name);
- break;
- }
- count = random_ulong () % 25 * 10000;
- printk ("%s waiting %zu: ", thread_current ()->name, count);
- for (i = 0; i < count; i++);
- printk ("%s\n", thread_current ()->name);
- }
+ thread_execute ("a.out");
}
int
main (void)
{
extern char _text, _end, __bss_start;
+ struct thread *t;
/* Clear out the BSS segment. */
memset (&__bss_start, 0, &_end - &__bss_start);
is free. Give it to the page allocator. */
palloc_init ((void *) (KERN_BASE + kernel_pages * NBPG),
(void *) (PHYS_BASE + ram_pages * NBPG));
-
- init_page_table ();
- setup_gdt ();
+ paging_init ();
+ gdt_init ();
malloc_init ();
random_init ();
#ifdef FILESYS
filesys_init (false);
+ filesys_self_test ();
#endif
thread_init ();
- {
- struct thread *t;
- int i;
-
- for (i = 0; i < 4; i++)
- {
- char name[2];
- name[0] = 'a' + i;
- name[1] = 0;
- t = thread_create (name, tfunc, NULL);
- }
- thread_start (t);
- }
+ t = thread_create ("main", main_thread, NULL);
+ thread_start (t);
printk ("Done!\n");
return 0;
}
-/* Populates the page directory and page table with the kernel
- virtual mapping. */
-static void
-init_page_table (void)
-{
- uint32_t *pd, *pt;
- uint32_t paddr;
-
- pd = palloc_get (PAL_ASSERT | PAL_ZERO);
- pt = NULL;
- for (paddr = 0; paddr < NBPG * ram_pages; paddr += NBPG)
- {
- uint32_t vaddr = paddr + PHYS_BASE;
- size_t pde_idx = PDENO(vaddr);
- size_t pte_idx = PTENO(vaddr);
-
- if (pd[pde_idx] == 0)
- {
- pt = palloc_get (PAL_ASSERT | PAL_ZERO);
- pd[pde_idx] = (uint32_t) vtop (pt) | PG_U | PG_W | PG_P;
- }
-
- pt[pte_idx] = paddr | PG_U | PG_W | PG_P;
- }
-
- /* Set the page table. */
- asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd)));
-}
-
static uint64_t
make_seg_desc (uint32_t base,
uint32_t limit,
/* Sets up a proper GDT. The bootstrap loader's GDT didn't
include user-mode selectors or a TSS. */
static void
-setup_gdt (void)
+gdt_init (void)
{
uint64_t gdtr_operand;
few fields of it are ever referenced, and those are the only
ones we initialize. */
tss = palloc_get (PAL_ASSERT | PAL_ZERO);
- tss->esp0 = (uint32_t) ptov(0xc0020000);
+ tss->esp0 = (uint32_t) ptov(0x20000);
tss->ss0 = SEL_KDSEG;
tss->bitmap = 0xdfff;
--- /dev/null
+#include "paging.h"
+#include <stdbool.h>
+#include <stddef.h>
+#include "init.h"
+#include "lib.h"
+#include "mmu.h"
+#include "palloc.h"
+
+static uint32_t *base_page_dir;
+
+static uint32_t
+make_pde (uint32_t *pagetab)
+{
+ ASSERT (PGOFS ((uintptr_t) pagetab) == 0);
+
+ return vtop (pagetab) | PG_U | PG_P | PG_W;
+}
+
+static uint32_t
+make_pte (uint32_t *page, bool writable)
+{
+ uint32_t entry;
+
+ ASSERT (PGOFS ((uintptr_t) page) == 0);
+
+ entry = vtop (page) | PG_U | PG_P;
+ if (writable)
+ entry |= PG_W;
+ return entry;
+}
+
+static uint32_t *
+pde_get_pagetab (uint32_t pde)
+{
+ ASSERT (pde & PG_P);
+
+ return ptov (PGROUNDDOWN (pde));
+}
+
+static void *
+pte_get_page (uint32_t pte)
+{
+ ASSERT (pte & PG_P);
+
+ return ptov (PGROUNDDOWN (pte));
+}
+
+/* Populates the base page directory and page table with the
+ kernel virtual mapping, and then sets up the CPU to use the
+ new page directory.
+
+ At the time this function is called, the active page table
+ only maps the first 4 MB of RAM, so it should not try to use
+ extravagant amounts of memory. Fortunately, there is no need
+ to do so. */
+void
+paging_init (void)
+{
+ uint32_t *pd, *pt;
+ size_t page;
+
+ pd = base_page_dir = palloc_get (PAL_ASSERT | PAL_ZERO);
+ pt = NULL;
+ for (page = 0; page < ram_pages; page++)
+ {
+ uintptr_t paddr = page * NBPG;
+ void *vaddr = ptov (paddr);
+ size_t pde_idx = PDENO ((uintptr_t) vaddr);
+ size_t pte_idx = PTENO ((uintptr_t) vaddr);
+
+ if (pd[pde_idx] == 0)
+ {
+ pt = palloc_get (PAL_ASSERT | PAL_ZERO);
+ pd[pde_idx] = make_pde (pt);
+ }
+
+ pt[pte_idx] = make_pte (vaddr, true);
+ }
+
+ /* Set the page table. */
+ asm volatile ("movl %0,%%cr3" :: "r" (vtop (pd)));
+}
+
+uint32_t *
+pagedir_create (void)
+{
+ uint32_t *pd = palloc_get (0);
+ memcpy (pd, base_page_dir, NBPG);
+ return pd;
+}
+
+void
+pagedir_destroy (uint32_t *pd)
+{
+ void *kpage, *upage;
+
+ for (kpage = pagedir_first (pd, &upage); kpage != NULL;
+ kpage = pagedir_next (pd, &upage))
+ palloc_free (kpage);
+ palloc_free (pd);
+}
+
+static uint32_t *
+lookup_page (uint32_t *pagedir, void *upage, bool create)
+{
+ uint32_t *pagetab;
+ uint32_t *pde;
+
+ ASSERT (pagedir != NULL);
+ ASSERT (PGOFS ((uintptr_t) upage) == 0);
+ ASSERT ((uintptr_t) upage < PHYS_BASE);
+
+ /* Check for a page table for UPAGE.
+ If one is missing, create one if requested. */
+ pde = pagedir + PDENO ((uint32_t) upage);
+ if (*pde == 0)
+ {
+ if (create)
+ {
+ pagetab = palloc_get (PAL_ZERO);
+ if (pagetab == NULL)
+ return NULL;
+
+ *pde = make_pde (pagetab);
+ }
+ else
+ return NULL;
+ }
+
+ /* Return the page table entry. */
+ pagetab = pde_get_pagetab (*pde);
+ return &pagetab[PTENO ((uintptr_t) upage)];
+}
+
+bool
+pagedir_set_page (uint32_t *pagedir, void *upage, void *kpage,
+ bool writable)
+{
+ uint32_t *pte;
+
+ ASSERT (PGOFS ((uintptr_t) kpage) == 0);
+
+ pte = lookup_page (pagedir, upage, true);
+ if (pte != NULL)
+ {
+ *pte = make_pte (kpage, writable);
+ return true;
+ }
+ else
+ return false;
+}
+
+void *
+pagedir_get_page (uint32_t *pagedir, void *upage)
+{
+ uint32_t *pte = lookup_page (pagedir, upage, false);
+ return pte != NULL && *pte != 0 ? pte_get_page (*pte) : NULL;
+}
+
+void
+pagedir_clear_page (uint32_t *pagedir, void *upage)
+{
+ uint32_t *pte = lookup_page (pagedir, upage, false);
+ if (pte != NULL)
+ *pte = 0;
+}
+
+static uint32_t *
+scan_pt (uint32_t *pt, unsigned pde_idx, unsigned pte_idx, void **upage)
+{
+ for (; pte_idx < NBPG / sizeof *pt; pte_idx++)
+ {
+ uint32_t pte = pt[pte_idx];
+
+ if (pte != 0)
+ {
+ void *kpage = pte_get_page (pte);
+ if (kpage != NULL)
+ {
+ *upage = (void *) ((pde_idx << PDSHIFT)
+ | (pte_idx << PGSHIFT));
+ return kpage;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+static void *
+scan_pd (uint32_t *pd, unsigned pde_idx, void **upage)
+{
+ for (; pde_idx < PDENO (PHYS_BASE); pde_idx++)
+ {
+ uint32_t pde = pd[pde_idx];
+
+ if (pde != 0)
+ {
+ void *kpage = scan_pt (pde_get_pagetab (pde), pde_idx, 0, upage);
+ if (kpage != NULL)
+ return kpage;
+ }
+ }
+
+ return NULL;
+}
+
+void *
+pagedir_first (uint32_t *pagedir, void **upage)
+{
+ return scan_pd (pagedir, 0, upage);
+}
+
+void *
+pagedir_next (uint32_t *pd, void **upage)
+{
+ unsigned pde_idx, pte_idx;
+ void *kpage;
+
+ pde_idx = PDENO (*upage);
+ pte_idx = PTENO (*upage);
+ kpage = scan_pt (pde_get_pagetab (pd[pde_idx]),
+ pde_idx, pte_idx + 1, upage);
+ if (kpage == NULL)
+ kpage = scan_pd (pd, pde_idx + 1, upage);
+ return kpage;
+}
+
+void pagedir_activate (uint32_t *pagedir);
--- /dev/null
+#ifndef HEADER_PAGING_H
+#define HEADER_PAGING_H 1
+
+#include <stdbool.h>
+#include <stdint.h>
+
+void paging_init (void);
+
+uint32_t *pagedir_create (void);
+void pagedir_destroy (uint32_t *);
+bool pagedir_set_page (uint32_t *pagedir, void *upage, void *kpage,
+ bool writable);
+void *pagedir_get_page (uint32_t *pagedir, void *upage);
+void pagedir_clear_page (uint32_t *pagedir, void *upage);
+
+void *pagedir_first (uint32_t *pagedir, void **upage);
+void *pagedir_next (uint32_t *pagedir, void **upage);
+
+void pagedir_activate (uint32_t *pagedir);
+
+#endif /* paging.h */
#include "lib.h"
#include "mmu.h"
#include "palloc.h"
+#include "random.h"
uint32_t thread_stack_ofs = offsetof (struct thread, stack);
return stack_to_thread (esp);
}
+#ifdef USERPROG
+void
+thread_execute (const char *filename)
+{
+ struct thread *t = thread_current ();
+
+ if (!addrspace_load (&t->addrspace, filename))
+ panic ("%s: program load failed", filename);
+ panic ("%s: loaded", filename);
+}
+#endif
+
void
thread_ready (struct thread *t)
{
thread_current ()->status = THREAD_BLOCKED;
thread_schedule ();
}
+
+static void
+tfunc (void *aux UNUSED)
+{
+ for (;;)
+ {
+ size_t count, i;
+ if (random_ulong () % 5 == 0)
+ {
+ printk ("%s exiting\n", thread_current ()->name);
+ break;
+ }
+ count = random_ulong () % 25 * 10000;
+ printk ("%s waiting %zu: ", thread_current ()->name, count);
+ for (i = 0; i < count; i++);
+ printk ("%s\n", thread_current ()->name);
+ }
+}
+
+void
+thread_self_test (void)
+{
+ struct thread *t;
+ int i;
+
+ for (i = 0; i < 4; i++)
+ {
+ char name[2];
+ name[0] = 'a' + i;
+ name[1] = 0;
+ t = thread_create (name, tfunc, NULL);
+ }
+ thread_start (t);
+}
#include <stdint.h>
#include "list.h"
+#ifdef USERPROG
+#include "addrspace.h"
+#endif
+
enum thread_status
{
THREAD_RUNNING,
enum thread_status status;
char name[16];
uint32_t *stack;
- struct list_elem rq_elem;
+ list_elem rq_elem;
+#ifdef USERPROG
+ struct addrspace addrspace;
+#endif
};
void thread_init (void);
void thread_destroy (struct thread *);
struct thread *thread_current (void);
+#ifdef USERPROG
+void thread_execute (const char *filename);
+#endif
+
void thread_start (struct thread *);
void thread_ready (struct thread *);
void thread_exit (void);
void thread_sleep (void);
void thread_schedule (void);
+void thread_self_test (void);
+
#endif /* thread.h */
--- /dev/null
+all:
+%:
+ $(MAKE) -C build $@
#include "addrspace.h"
+#include <inttypes.h>
+#include "debug.h"
+#include "file.h"
+#include "filesys.h"
+#include "lib.h"
+#include "mmu.h"
+#include "malloc.h"
+#include "paging.h"
+#include "palloc.h"
/* We load ELF binaries. The following definitions are taken
- from the ELF specification more-or-less literally. */
+ from the ELF specification more-or-less verbatim. */
/* ELF types. */
typedef uint32_t Elf32_Word, Elf32_Addr, Elf32_Off;
typedef uint16_t Elf32_Half;
+#define PE32Wx PRIx32
+#define PE32Ax PRIx32
+#define PE32Ox PRIx32
+#define PE32Hx PRIx16
+
/* Executable header.
This appears at the very beginning of an ELF binary. */
struct Elf32_Ehdr
Elf32_Word p_align;
};
-/* Values for p_type in struct Elf32_Phdr. */
-#define PT_NULL 0 /* Ignore this program header. */
-#define PT_LOAD 1 /* Loadable segment. */
-#define PT_DYNAMIC 2 /* Dynamic linking info. */
-#define PT_INTERP 3 /* Name of dynamic loader. */
-#define PT_NOTE 4 /* Auxiliary info. */
-#define PT_SHLIB 5 /* Reserved. */
-#define PT_PHDR 6 /* Program header table. */
+/* Values for p_type. */
+#define PT_NULL 0 /* Ignore. */
+#define PT_LOAD 1 /* Loadable segment. */
+#define PT_DYNAMIC 2 /* Dynamic linking info. */
+#define PT_INTERP 3 /* Name of dynamic loader. */
+#define PT_NOTE 4 /* Auxiliary info. */
+#define PT_SHLIB 5 /* Reserved. */
+#define PT_PHDR 6 /* Program header table. */
+#define PT_STACK 0x6474e551 /* Stack segment. */
+
+/* Flags for p_flags. */
+#define PF_X 1 /* Executable. */
+#define PF_W 2 /* Writable. */
+#define PF_R 4 /* Readable. */
#define LOAD_ERROR(MSG) \
do { \
goto error; \
} while (0)
+static bool
+load_segment (struct addrspace *as, struct file *file,
+ const struct Elf32_Phdr *phdr)
+{
+ uintptr_t start, end;
+ uint8_t *upage;
+ off_t filesz_left;
+
+ ASSERT (as != NULL);
+ ASSERT (file != NULL);
+ ASSERT (phdr != NULL);
+ ASSERT (phdr->p_type == PT_LOAD);
+
+ /* p_offset and p_vaddr must be congruent modulo NBPG. */
+ if (phdr->p_offset % NBPG != phdr->p_vaddr % NBPG)
+ {
+ printk ("%#08"PE32Ox" and %#08"PE32Ax" not congruent modulo %#x\n",
+ phdr->p_offset, phdr->p_vaddr, (unsigned) NBPG);
+ return false;
+ }
+
+ /* p_memsz must be at least as big as p_filesz. */
+ if (phdr->p_memsz < phdr->p_filesz)
+ {
+ printk ("p_memsz (%08"PE32Wx") < p_filesz (%08"PE32Wx")\n",
+ phdr->p_memsz, phdr->p_filesz);
+ return false;
+ }
+
+ /* Validate virtual memory region to be mapped. */
+ start = PGROUNDDOWN (phdr->p_vaddr);
+ end = PGROUNDUP (phdr->p_vaddr + phdr->p_memsz);
+ if (start >= PHYS_BASE || end >= PHYS_BASE || end < start)
+ {
+ printk ("bad virtual region %08lx...%08lx\n",
+ (unsigned long) start, (unsigned long) end);
+ return false;
+ }
+
+ filesz_left = phdr->p_filesz + (phdr->p_vaddr - start);
+ file_seek (file, ROUND_DOWN (phdr->p_offset, NBPG));
+ for (upage = (uint8_t *) start; upage < (uint8_t *) end; upage += NBPG)
+ {
+ size_t read_bytes = filesz_left >= NBPG ? NBPG : filesz_left;
+ size_t zero_bytes = NBPG - read_bytes;
+ uint8_t *kpage = palloc_get (0);
+ if (kpage == NULL)
+ return false;
+
+ if (file_read (file, kpage, read_bytes) != (int) read_bytes)
+ return false;
+ memset (kpage + read_bytes, 0, zero_bytes);
+ filesz_left -= read_bytes;
+
+ if (pagedir_get_page (as->pagedir, upage))
+ {
+ palloc_free (kpage);
+ return false;
+ }
+ pagedir_set_page (as->pagedir, upage, kpage, true);
+ }
+
+ return true;
+}
+
bool
addrspace_load (struct addrspace *as, const char *filename)
{
- Elf32_Ehdr ehdr;
- struct file *file;
+ struct Elf32_Ehdr ehdr;
+ struct file *file = NULL;
+ off_t file_ofs;
+ bool success = false;
+ int i;
+
+ as->pagedir = pagedir_create ();
file = filesys_open (filename);
if (file == NULL)
/* Read and verify executable header. */
if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr)
LOAD_ERROR (("error reading executable header"));
- if (memcmp (ehdr.e_ident, "\x7fELF\1\1\1", 7) != 0)
- LOAD_ERROR (("not an ELF file"));
+ if (memcmp (ehdr.e_ident, "\177ELF\1\1\1", 7) != 0)
+ LOAD_ERROR (("file is not ELF"));
if (ehdr.e_type != 2)
- LOAD_ERROR (("not an executable"));
+ LOAD_ERROR (("ELF file is not an executable"));
if (ehdr.e_machine != 3)
- LOAD_ERROR (("not an x86 binary"));
+ LOAD_ERROR (("ELF executable is not x86"));
if (ehdr.e_version != 1)
- LOAD_ERROR (("unknown ELF version %d", (int) ehdr.e_version));
+ LOAD_ERROR (("ELF executable hasunknown version %d",
+ (int) ehdr.e_version));
if (ehdr.e_phentsize != sizeof (struct Elf32_Phdr))
- LOAD_ERROR (("bad program header size", (int) ehdr.e_phentsize));
+ LOAD_ERROR (("bad ELF program header size"));
if (ehdr.e_phnum > 1024)
- LOAD_ERROR (("too many program headers"));
+ LOAD_ERROR (("too many ELF program headers"));
/* Read program headers. */
+ file_ofs = ehdr.e_phoff;
+ printk ("e_phnum=%d\n", ehdr.e_phnum);
+ for (i = 0; i < ehdr.e_phnum; i++)
+ {
+ struct Elf32_Phdr phdr;
- as->page_dir = create_page_dir ();
- list_init (&as->vmas);
+ file_seek (file, file_ofs);
+ if (file_read (file, &phdr, sizeof phdr) != sizeof phdr)
+ LOAD_ERROR (("error reading program header"));
+ printk ("%x: %08x, %08x %08x %08x %05x %05x\n",
+ file_tell (file),
+ phdr.p_type,
+ phdr.p_offset, phdr.p_vaddr, phdr.p_paddr,
+ phdr.p_filesz, phdr.p_memsz);
+ file_ofs += sizeof phdr;
+ switch (phdr.p_type)
+ {
+ case PT_NULL:
+ case PT_NOTE:
+ case PT_PHDR:
+ case PT_STACK: /* Stack segment. */
+ /* Ignore this segment. */
+ break;
+ case PT_DYNAMIC:
+ case PT_INTERP:
+ case PT_SHLIB:
+ /* Reject the executable. */
+ LOAD_ERROR (("unsupported ELF segment type %d\n", phdr.p_type));
+ break;
+ default:
+ printk ("unknown ELF segment type %08x\n", phdr.p_type);
+ break;
+ case PT_LOAD:
+ if (!load_segment (as, file, &phdr))
+ goto error;
+ break;
+ }
+ }
+ success = true;
-
-
+ error:
+ if (file != NULL)
+ file_close (file);
+ if (!success)
+ addrspace_destroy (as);
+ return success;
+}
+void
+addrspace_destroy (struct addrspace *as)
+{
+ if (as != NULL && as->pagedir != NULL)
+ pagedir_destroy (as->pagedir);
}
#ifndef HEADER_ADDRSPACE_H
#define HEADER_ADDRSPACE_H 1
-#include "list.h"
-
-struct vma
- {
- struct list_elem elem;
- uint32_t start, end;
- void **pages;
- };
+#include <stdint.h>
+#include "hash.h"
struct addrspace
{
- uint32_t *page_dir;
- struct list vmas;
+ uint32_t *pagedir;
};
-void addrspace_load (struct addrspace *, const char *);
+bool addrspace_load (struct addrspace *, const char *);
+void addrspace_destroy (struct addrspace *);
#endif /* addrspace.h */
projects / pintos-anon / commitdiff