Lab2 initial changes
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 23 Jan 2009 20:46:41 +0000 (12:46 -0800)
committerBarret Rhoden <brho@cs.berkeley.edu>
Fri, 23 Jan 2009 20:46:41 +0000 (12:46 -0800)
13 files changed:
inc/env.h [new file with mode: 0644]
inc/trap.h [new file with mode: 0644]
kern/env.c [new file with mode: 0644]
kern/env.h [new file with mode: 0644]
kern/init.c
kern/kclock.c [new file with mode: 0644]
kern/kclock.h [new file with mode: 0644]
kern/kdebug.c [new file with mode: 0644]
kern/kdebug.h [new file with mode: 0644]
kern/monitor.c
kern/pmap.c [new file with mode: 0644]
kern/pmap.h [new file with mode: 0644]
kern/trap.h [new file with mode: 0644]

diff --git a/inc/env.h b/inc/env.h
new file mode 100644 (file)
index 0000000..51f1c47
--- /dev/null
+++ b/inc/env.h
@@ -0,0 +1,52 @@
+/* See COPYRIGHT for copyright information. */
+
+#ifndef JOS_INC_ENV_H
+#define JOS_INC_ENV_H
+
+#include <inc/types.h>
+#include <inc/queue.h>
+#include <inc/trap.h>
+#include <inc/memlayout.h>
+
+typedef int32_t envid_t;
+
+// An environment ID 'envid_t' has three parts:
+//
+// +1+---------------21-----------------+--------10--------+
+// |0|          Uniqueifier             |   Environment    |
+// | |                                  |      Index       |
+// +------------------------------------+------------------+
+//                                       \--- ENVX(eid) --/
+//
+// The environment index ENVX(eid) equals the environment's offset in the
+// 'envs[]' array.  The uniqueifier distinguishes environments that were
+// created at different times, but share the same environment index.
+//
+// All real environments are greater than 0 (so the sign bit is zero).
+// envid_ts less than 0 signify errors.  The envid_t == 0 is special, and
+// stands for the current environment.
+
+#define LOG2NENV               10
+#define NENV                   (1 << LOG2NENV)
+#define ENVX(envid)            ((envid) & (NENV - 1))
+
+// Values of env_status in struct Env
+#define ENV_FREE               0
+#define ENV_RUNNABLE           1
+#define ENV_NOT_RUNNABLE       2
+
+struct Env {
+       struct Trapframe env_tf;        // Saved registers
+       LIST_ENTRY(Env) env_link;       // Free list link pointers
+       envid_t env_id;                 // Unique environment identifier
+       envid_t env_parent_id;          // env_id of this env's parent
+       unsigned env_status;            // Status of the environment
+       uint32_t env_runs;              // Number of times environment has run
+
+       // Address space
+       pde_t *env_pgdir;               // Kernel virtual address of page dir
+       physaddr_t env_cr3;             // Physical address of page dir
+
+};
+
+#endif // !JOS_INC_ENV_H
diff --git a/inc/trap.h b/inc/trap.h
new file mode 100644 (file)
index 0000000..2ff289b
--- /dev/null
@@ -0,0 +1,74 @@
+#ifndef JOS_INC_TRAP_H
+#define JOS_INC_TRAP_H
+
+// Trap numbers
+// These are processor defined:
+#define T_DIVIDE     0         // divide error
+#define T_DEBUG      1         // debug exception
+#define T_NMI        2         // non-maskable interrupt
+#define T_BRKPT      3         // breakpoint
+#define T_OFLOW      4         // overflow
+#define T_BOUND      5         // bounds check
+#define T_ILLOP      6         // illegal opcode
+#define T_DEVICE     7         // device not available 
+#define T_DBLFLT     8         // double fault
+/* #define T_COPROC  9 */      // reserved (not generated by recent processors)
+#define T_TSS       10         // invalid task switch segment
+#define T_SEGNP     11         // segment not present
+#define T_STACK     12         // stack exception
+#define T_GPFLT     13         // genernal protection fault
+#define T_PGFLT     14         // page fault
+/* #define T_RES    15 */      // reserved
+#define T_FPERR     16         // floating point error
+#define T_ALIGN     17         // aligment check
+#define T_MCHK      18         // machine check
+#define T_SIMDERR   19         // SIMD floating point error
+
+// These are arbitrarily chosen, but with care not to overlap
+// processor defined exceptions or interrupt vectors.
+#define T_SYSCALL   48         // system call
+#define T_DEFAULT   500                // catchall
+
+#ifndef __ASSEMBLER__
+
+#include <inc/types.h>
+
+struct PushRegs {
+       /* registers as pushed by pusha */
+       uint32_t reg_edi;
+       uint32_t reg_esi;
+       uint32_t reg_ebp;
+       uint32_t reg_oesp;              /* Useless */
+       uint32_t reg_ebx;
+       uint32_t reg_edx;
+       uint32_t reg_ecx;
+       uint32_t reg_eax;
+};
+
+struct Trapframe {
+       struct PushRegs tf_regs;
+       uint16_t tf_es;
+       uint16_t tf_padding1;
+       uint16_t tf_ds;
+       uint16_t tf_padding2;
+       uint32_t tf_trapno;
+       /* below here defined by x86 hardware */
+       uint32_t tf_err;
+       uintptr_t tf_eip;
+       uint16_t tf_cs;
+       uint16_t tf_padding3;
+       uint32_t tf_eflags;
+       /* below here only when crossing rings, such as from user to kernel */
+       uintptr_t tf_esp;
+       uint16_t tf_ss;
+       uint16_t tf_padding4;
+};
+
+
+#endif /* !__ASSEMBLER__ */
+
+// Must equal 'sizeof(struct Trapframe)'.
+// A static_assert in kern/trap.c checks this.
+#define SIZEOF_STRUCT_TRAPFRAME        0x44
+
+#endif /* !JOS_INC_TRAP_H */
diff --git a/kern/env.c b/kern/env.c
new file mode 100644 (file)
index 0000000..d33b25b
--- /dev/null
@@ -0,0 +1,383 @@
+/* See COPYRIGHT for copyright information. */
+
+#include <inc/x86.h>
+#include <inc/mmu.h>
+#include <inc/error.h>
+#include <inc/string.h>
+#include <inc/assert.h>
+#include <inc/elf.h>
+
+#include <kern/env.h>
+#include <kern/pmap.h>
+#include <kern/trap.h>
+#include <kern/monitor.h>
+
+struct Env *envs = NULL;               // All environments
+struct Env *curenv = NULL;             // The current env
+static struct Env_list env_free_list;  // Free list
+
+#define ENVGENSHIFT    12              // >= LOGNENV
+
+//
+// Converts an envid to an env pointer.
+//
+// RETURNS
+//   0 on success, -E_BAD_ENV on error.
+//   On success, sets *penv to the environment.
+//   On error, sets *penv to NULL.
+//
+int
+envid2env(envid_t envid, struct Env **env_store, bool checkperm)
+{
+       struct Env *e;
+
+       // If envid is zero, return the current environment.
+       if (envid == 0) {
+               *env_store = curenv;
+               return 0;
+       }
+
+       // Look up the Env structure via the index part of the envid,
+       // then check the env_id field in that struct Env
+       // to ensure that the envid is not stale
+       // (i.e., does not refer to a _previous_ environment
+       // that used the same slot in the envs[] array).
+       e = &envs[ENVX(envid)];
+       if (e->env_status == ENV_FREE || e->env_id != envid) {
+               *env_store = 0;
+               return -E_BAD_ENV;
+       }
+
+       // Check that the calling environment has legitimate permission
+       // to manipulate the specified environment.
+       // If checkperm is set, the specified environment
+       // must be either the current environment
+       // or an immediate child of the current environment.
+       if (checkperm && e != curenv && e->env_parent_id != curenv->env_id) {
+               *env_store = 0;
+               return -E_BAD_ENV;
+       }
+
+       *env_store = e;
+       return 0;
+}
+
+//
+// Mark all environments in 'envs' as free, set their env_ids to 0,
+// and insert them into the env_free_list.
+// Insert in reverse order, so that the first call to env_alloc()
+// returns envs[0].
+//
+void
+env_init(void)
+{
+       // LAB 3: Your code here.
+}
+
+//
+// Initialize the kernel virtual memory layout for environment e.
+// Allocate a page directory, set e->env_pgdir and e->env_cr3 accordingly,
+// and initialize the kernel portion of the new environment's address space.
+// Do NOT (yet) map anything into the user portion
+// of the environment's virtual address space.
+//
+// Returns 0 on success, < 0 on error.  Errors include:
+//     -E_NO_MEM if page directory or table could not be allocated.
+//
+static int
+env_setup_vm(struct Env *e)
+{
+       int i, r;
+       struct Page *p = NULL;
+
+       // Allocate a page for the page directory
+       if ((r = page_alloc(&p)) < 0)
+               return r;
+
+       // Now, set e->env_pgdir and e->env_cr3,
+       // and initialize the page directory.
+       //
+       // Hint:
+       //    - The VA space of all envs is identical above UTOP
+       //      (except at VPT and UVPT, which we've set below).
+       //      See inc/memlayout.h for permissions and layout.
+       //      Can you use boot_pgdir as a template?  Hint: Yes.
+       //      (Make sure you got the permissions right in Lab 2.)
+       //    - The initial VA below UTOP is empty.
+       //    - You do not need to make any more calls to page_alloc.
+       //    - Note: pp_ref is not maintained for most physical pages
+       //      mapped above UTOP -- but you do need to increment
+       //      env_pgdir's pp_ref!
+
+       // LAB 3: Your code here.
+
+       // VPT and UVPT map the env's own page table, with
+       // different permissions.
+       e->env_pgdir[PDX(VPT)]  = e->env_cr3 | PTE_P | PTE_W;
+       e->env_pgdir[PDX(UVPT)] = e->env_cr3 | PTE_P | PTE_U;
+
+       return 0;
+}
+
+//
+// Allocates and initializes a new environment.
+// On success, the new environment is stored in *newenv_store.
+//
+// Returns 0 on success, < 0 on failure.  Errors include:
+//     -E_NO_FREE_ENV if all NENVS environments are allocated
+//     -E_NO_MEM on memory exhaustion
+//
+int
+env_alloc(struct Env **newenv_store, envid_t parent_id)
+{
+       int32_t generation;
+       int r;
+       struct Env *e;
+
+       if (!(e = LIST_FIRST(&env_free_list)))
+               return -E_NO_FREE_ENV;
+
+       // Allocate and set up the page directory for this environment.
+       if ((r = env_setup_vm(e)) < 0)
+               return r;
+
+       // Generate an env_id for this environment.
+       generation = (e->env_id + (1 << ENVGENSHIFT)) & ~(NENV - 1);
+       if (generation <= 0)    // Don't create a negative env_id.
+               generation = 1 << ENVGENSHIFT;
+       e->env_id = generation | (e - envs);
+       
+       // Set the basic status variables.
+       e->env_parent_id = parent_id;
+       e->env_status = ENV_RUNNABLE;
+       e->env_runs = 0;
+
+       // Clear out all the saved register state,
+       // to prevent the register values
+       // of a prior environment inhabiting this Env structure
+       // from "leaking" into our new environment.
+       memset(&e->env_tf, 0, sizeof(e->env_tf));
+
+       // Set up appropriate initial values for the segment registers.
+       // GD_UD is the user data segment selector in the GDT, and 
+       // GD_UT is the user text segment selector (see inc/memlayout.h).
+       // The low 2 bits of each segment register contains the
+       // Requestor Privilege Level (RPL); 3 means user mode.
+       e->env_tf.tf_ds = GD_UD | 3;
+       e->env_tf.tf_es = GD_UD | 3;
+       e->env_tf.tf_ss = GD_UD | 3;
+       e->env_tf.tf_esp = USTACKTOP;
+       e->env_tf.tf_cs = GD_UT | 3;
+       // You will set e->env_tf.tf_eip later.
+
+       // commit the allocation
+       LIST_REMOVE(e, env_link);
+       *newenv_store = e;
+
+       cprintf("[%08x] new env %08x\n", curenv ? curenv->env_id : 0, e->env_id);
+       return 0;
+}
+
+//
+// Allocate len bytes of physical memory for environment env,
+// and map it at virtual address va in the environment's address space.
+// Does not zero or otherwise initialize the mapped pages in any way.
+// Pages should be writable by user and kernel.
+// Panic if any allocation attempt fails.
+//
+static void
+segment_alloc(struct Env *e, void *va, size_t len)
+{
+       // LAB 3: Your code here.
+       // (But only if you need it for load_icode.)
+       //
+       // Hint: It is easier to use segment_alloc if the caller can pass
+       //   'va' and 'len' values that are not page-aligned.
+       //   You should round va down, and round len up.
+}
+
+//
+// Set up the initial program binary, stack, and processor flags
+// for a user process.
+// This function is ONLY called during kernel initialization,
+// before running the first user-mode environment.
+//
+// This function loads all loadable segments from the ELF binary image
+// into the environment's user memory, starting at the appropriate
+// virtual addresses indicated in the ELF program header.
+// At the same time it clears to zero any portions of these segments
+// that are marked in the program header as being mapped
+// but not actually present in the ELF file - i.e., the program's bss section.
+//
+// All this is very similar to what our boot loader does, except the boot
+// loader also needs to read the code from disk.  Take a look at
+// boot/main.c to get ideas.
+//
+// Finally, this function maps one page for the program's initial stack.
+//
+// load_icode panics if it encounters problems.
+//  - How might load_icode fail?  What might be wrong with the given input?
+//
+static void
+load_icode(struct Env *e, uint8_t *binary, size_t size)
+{
+       // Hints: 
+       //  Load each program segment into virtual memory
+       //  at the address specified in the ELF section header.
+       //  You should only load segments with ph->p_type == ELF_PROG_LOAD.
+       //  Each segment's virtual address can be found in ph->p_va
+       //  and its size in memory can be found in ph->p_memsz.
+       //  The ph->p_filesz bytes from the ELF binary, starting at
+       //  'binary + ph->p_offset', should be copied to virtual address
+       //  ph->p_va.  Any remaining memory bytes should be cleared to zero.
+       //  (The ELF header should have ph->p_filesz <= ph->p_memsz.)
+       //  Use functions from the previous lab to allocate and map pages.
+       //
+       //  All page protection bits should be user read/write for now.
+       //  ELF segments are not necessarily page-aligned, but you can
+       //  assume for this function that no two segments will touch
+       //  the same virtual page.
+       //
+       //  You may find a function like segment_alloc useful.
+       //
+       //  Loading the segments is much simpler if you can move data
+       //  directly into the virtual addresses stored in the ELF binary.
+       //  So which page directory should be in force during
+       //  this function?
+       //
+       // Hint:
+       //  You must also do something with the program's entry point,
+       //  to make sure that the environment starts executing there.
+       //  What?  (See env_run() and env_pop_tf() below.)
+
+       // LAB 3: Your code here.
+
+       // Now map one page for the program's initial stack
+       // at virtual address USTACKTOP - PGSIZE.
+
+       // LAB 3: Your code here.
+}
+
+//
+// Allocates a new env and loads the named elf binary into it.
+// This function is ONLY called during kernel initialization,
+// before running the first user-mode environment.
+// The new env's parent ID is set to 0.
+//
+// Where does the result go? 
+// By convention, envs[0] is the first environment allocated, so
+// whoever calls env_create simply looks for the newly created
+// environment there. 
+void
+env_create(uint8_t *binary, size_t size)
+{
+       // LAB 3: Your code here.
+}
+
+//
+// Frees env e and all memory it uses.
+// 
+void
+env_free(struct Env *e)
+{
+       pte_t *pt;
+       uint32_t pdeno, pteno;
+       physaddr_t pa;
+
+       // Note the environment's demise.
+       cprintf("[%08x] free env %08x\n", curenv ? curenv->env_id : 0, e->env_id);
+
+       // Flush all mapped pages in the user portion of the address space
+       static_assert(UTOP % PTSIZE == 0);
+       for (pdeno = 0; pdeno < PDX(UTOP); pdeno++) {
+
+               // only look at mapped page tables
+               if (!(e->env_pgdir[pdeno] & PTE_P))
+                       continue;
+
+               // find the pa and va of the page table
+               pa = PTE_ADDR(e->env_pgdir[pdeno]);
+               pt = (pte_t*) KADDR(pa);
+
+               // unmap all PTEs in this page table
+               for (pteno = 0; pteno <= PTX(~0); pteno++) {
+                       if (pt[pteno] & PTE_P)
+                               page_remove(e->env_pgdir, PGADDR(pdeno, pteno, 0));
+               }
+
+               // free the page table itself
+               e->env_pgdir[pdeno] = 0;
+               page_decref(pa2page(pa));
+       }
+
+       // free the page directory
+       pa = e->env_cr3;
+       e->env_pgdir = 0;
+       e->env_cr3 = 0;
+       page_decref(pa2page(pa));
+
+       // return the environment to the free list
+       e->env_status = ENV_FREE;
+       LIST_INSERT_HEAD(&env_free_list, e, env_link);
+}
+
+//
+// Frees environment e.
+// If e was the current env, then runs a new environment (and does not return
+// to the caller).
+//
+void
+env_destroy(struct Env *e) 
+{
+       env_free(e);
+
+       cprintf("Destroyed the only environment - nothing more to do!\n");
+       while (1)
+               monitor(NULL);
+}
+
+
+//
+// Restores the register values in the Trapframe with the 'iret' instruction.
+// This exits the kernel and starts executing some environment's code.
+// This function does not return.
+//
+void
+env_pop_tf(struct Trapframe *tf)
+{
+       __asm __volatile("movl %0,%%esp\n"
+               "\tpopal\n"
+               "\tpopl %%es\n"
+               "\tpopl %%ds\n"
+               "\taddl $0x8,%%esp\n" /* skip tf_trapno and tf_errcode */
+               "\tiret"
+               : : "g" (tf) : "memory");
+       panic("iret failed");  /* mostly to placate the compiler */
+}
+
+//
+// Context switch from curenv to env e.
+// Note: if this is the first call to env_run, curenv is NULL.
+//  (This function does not return.)
+//
+void
+env_run(struct Env *e)
+{
+       // Step 1: If this is a context switch (a new environment is running),
+       //         then set 'curenv' to the new environment,
+       //         update its 'env_runs' counter, and
+       //         and use lcr3() to switch to its address space.
+       // Step 2: Use env_pop_tf() to restore the environment's
+       //         registers and drop into user mode in the
+       //         environment.
+
+       // Hint: This function loads the new environment's state from
+       //      e->env_tf.  Go back through the code you wrote above
+       //      and make sure you have set the relevant parts of
+       //      e->env_tf to sensible values.
+       
+       // LAB 3: Your code here.
+
+        panic("env_run not yet implemented");
+}
+
diff --git a/kern/env.h b/kern/env.h
new file mode 100644 (file)
index 0000000..0508f86
--- /dev/null
@@ -0,0 +1,43 @@
+/* See COPYRIGHT for copyright information. */
+
+#ifndef JOS_KERN_ENV_H
+#define JOS_KERN_ENV_H
+
+#include <inc/env.h>
+
+#ifndef JOS_MULTIENV
+// Change this value to 1 once you're allowing multiple environments
+// (for UCLA: Lab 3, Part 3; for MIT: Lab 4).
+#define JOS_MULTIENV 0
+#endif
+
+extern struct Env *envs;               // All environments
+extern struct Env *curenv;             // Current environment
+
+LIST_HEAD(Env_list, Env);              // Declares 'struct Env_list'
+
+void   env_init(void);
+int    env_alloc(struct Env **e, envid_t parent_id);
+void   env_free(struct Env *e);
+void   env_create(uint8_t *binary, size_t size);
+void   env_destroy(struct Env *e);     // Does not return if e == curenv
+
+int    envid2env(envid_t envid, struct Env **env_store, bool checkperm);
+// The following two functions do not return
+void   env_run(struct Env *e) __attribute__((noreturn));
+void   env_pop_tf(struct Trapframe *tf) __attribute__((noreturn));
+
+// For the grading script
+#define ENV_CREATE2(start, size)       {               \
+       extern uint8_t start[], size[];                 \
+       env_create(start, (int)size);                   \
+}
+
+#define ENV_CREATE(x)                  {               \
+       extern uint8_t _binary_obj_##x##_start[],       \
+               _binary_obj_##x##_size[];               \
+       env_create(_binary_obj_##x##_start,             \
+               (int)_binary_obj_##x##_size);           \
+}
+
+#endif // !JOS_KERN_ENV_H
index adb49fd..465dd4f 100644 (file)
@@ -8,18 +8,8 @@
 
 #include <kern/monitor.h>
 #include <kern/console.h>
-
-// Test the stack backtrace function (lab 1 only)
-void
-test_backtrace(int x)
-{
-       cprintf("entering test_backtrace %d\n", x);
-       if (x > 0)
-               test_backtrace(x-1);
-       else
-               mon_backtrace(0, 0, 0);
-       cprintf("leaving test_backtrace %d\n", x);
-}
+#include <kern/pmap.h>
+#include <kern/kclock.h>
 
 void
 kernel_init(multiboot_info_t *mboot_info)
@@ -35,24 +25,11 @@ kernel_init(multiboot_info_t *mboot_info)
        // Can't call cprintf until after we do this!
        cons_init();
 
-       /*
-       extern stab_t stab[], estab[];
-       extern char stabstr[];
-       stab_t* symtab;
-       // Spits out the stabs for functions
-       for (symtab = stab; symtab < estab; symtab++) {
-               // gives us only functions.  not really needed if we scan by address
-               if (symtab->n_type != 36)
-                       continue;
-               cprintf("Symbol name = %s\n", stabstr + symtab->n_strx);
-               cprintf("Symbol type = %d\n", symtab->n_type);
-               cprintf("Symbol value = 0x%x\n", symtab->n_value);
-               cprintf("\n");
-       }
-       */
-
-       // Test the stack backtrace function (lab 1 only)
-       test_backtrace(5);
+       // Lab 2 memory management initialization functions
+       i386_detect_memory();
+       i386_vm_init();
+       page_init();
+       page_check();
 
        // Drop into the kernel monitor.
        while (1)
@@ -134,3 +111,20 @@ _warn(const char *file, int line, const char *fmt,...)
                cprintf("Symbol vale = 0x%x\n", symtab->st_value);
        }
        */
+       /*
+       extern stab_t stab[], estab[];
+       extern char stabstr[];
+       stab_t* symtab;
+       // Spits out the stabs for functions
+       for (symtab = stab; symtab < estab; symtab++) {
+               // gives us only functions.  not really needed if we scan by address
+               if (symtab->n_type != 36)
+                       continue;
+               cprintf("Symbol name = %s\n", stabstr + symtab->n_strx);
+               cprintf("Symbol type = %d\n", symtab->n_type);
+               cprintf("Symbol value = 0x%x\n", symtab->n_value);
+               cprintf("\n");
+       }
+       */
+
+
diff --git a/kern/kclock.c b/kern/kclock.c
new file mode 100644 (file)
index 0000000..d52f8f7
--- /dev/null
@@ -0,0 +1,28 @@
+/* See COPYRIGHT for copyright information. */
+
+/* Support for two time-related hardware gadgets: 1) the run time
+ * clock with its NVRAM access functions; 2) the 8253 timer, which
+ * generates interrupts on IRQ 0.
+ */
+
+#include <inc/x86.h>
+
+#include <kern/kclock.h>
+
+
+unsigned
+mc146818_read(unsigned reg)
+{
+       outb(IO_RTC, reg);
+       return inb(IO_RTC+1);
+}
+
+void
+mc146818_write(unsigned reg, unsigned datum)
+{
+       outb(IO_RTC, reg);
+       outb(IO_RTC+1, datum);
+}
+
+
+
diff --git a/kern/kclock.h b/kern/kclock.h
new file mode 100644 (file)
index 0000000..ecea06e
--- /dev/null
@@ -0,0 +1,33 @@
+/* See COPYRIGHT for copyright information. */
+
+#ifndef JOS_KERN_KCLOCK_H
+#define JOS_KERN_KCLOCK_H
+#ifndef JOS_KERNEL
+# error "This is a JOS kernel header; user programs should not #include it"
+#endif
+
+#define        IO_RTC          0x070           /* RTC port */
+
+#define        MC_NVRAM_START  0xe     /* start of NVRAM: offset 14 */
+#define        MC_NVRAM_SIZE   50      /* 50 bytes of NVRAM */
+
+/* NVRAM bytes 7 & 8: base memory size */
+#define NVRAM_BASELO   (MC_NVRAM_START + 7)    /* low byte; RTC off. 0x15 */
+#define NVRAM_BASEHI   (MC_NVRAM_START + 8)    /* high byte; RTC off. 0x16 */
+
+/* NVRAM bytes 9 & 10: extended memory size */
+#define NVRAM_EXTLO    (MC_NVRAM_START + 9)    /* low byte; RTC off. 0x17 */
+#define NVRAM_EXTHI    (MC_NVRAM_START + 10)   /* high byte; RTC off. 0x18 */
+
+/* NVRAM bytes 34 and 35: extended memory POSTed size */
+#define NVRAM_PEXTLO   (MC_NVRAM_START + 34)   /* low byte; RTC off. 0x30 */
+#define NVRAM_PEXTHI   (MC_NVRAM_START + 35)   /* high byte; RTC off. 0x31 */
+
+/* NVRAM byte 36: current century.  (please increment in Dec99!) */
+#define NVRAM_CENTURY  (MC_NVRAM_START + 36)   /* RTC offset 0x32 */
+
+unsigned mc146818_read(unsigned reg);
+void mc146818_write(unsigned reg, unsigned datum);
+void kclock_init(void);
+
+#endif // !JOS_KERN_KCLOCK_H
diff --git a/kern/kdebug.c b/kern/kdebug.c
new file mode 100644 (file)
index 0000000..89833db
--- /dev/null
@@ -0,0 +1,205 @@
+#include <inc/stab.h>
+#include <inc/string.h>
+#include <inc/memlayout.h>
+#include <inc/assert.h>
+
+#include <kern/kdebug.h>
+#include <kern/pmap.h>
+#include <kern/env.h>
+
+extern const struct Stab __STAB_BEGIN__[];     // Beginning of stabs table
+extern const struct Stab __STAB_END__[];       // End of stabs table
+extern const char __STABSTR_BEGIN__[];         // Beginning of string table
+extern const char __STABSTR_END__[];           // End of string table
+
+
+// stab_binsearch(stabs, region_left, region_right, type, addr)
+//
+//     Some stab types are arranged in increasing order by instruction
+//     address.  For example, N_FUN stabs (stab entries with n_type ==
+//     N_FUN), which mark functions, and N_SO stabs, which mark source files.
+//
+//     Given an instruction address, this function finds the single stab
+//     entry of type 'type' that contains that address.
+//
+//     The search takes place within the range [*region_left, *region_right].
+//     Thus, to search an entire set of N stabs, you might do:
+//
+//             left = 0;
+//             right = N - 1;     /* rightmost stab */
+//             stab_binsearch(stabs, &left, &right, type, addr);
+//
+//     The search modifies *region_left and *region_right to bracket the
+//     'addr'.  *region_left points to the matching stab that contains
+//     'addr', and *region_right points just before the next stab.  If
+//     *region_left > *region_right, then 'addr' is not contained in any
+//     matching stab.
+//
+//     For example, given these N_SO stabs:
+//             Index  Type   Address
+//             0      SO     f0100000
+//             13     SO     f0100040
+//             117    SO     f0100176
+//             118    SO     f0100178
+//             555    SO     f0100652
+//             556    SO     f0100654
+//             657    SO     f0100849
+//     this code:
+//             left = 0, right = 657;
+//             stab_binsearch(stabs, &left, &right, N_SO, 0xf0100184);
+//     will exit setting left = 118, right = 554.
+//
+static void
+stab_binsearch(const struct Stab *stabs, int *region_left, int *region_right,
+              int type, uintptr_t addr)
+{
+       int l = *region_left, r = *region_right, any_matches = 0;
+       
+       while (l <= r) {
+               int true_m = (l + r) / 2, m = true_m;
+               
+               // search for earliest stab with right type
+               while (m >= l && stabs[m].n_type != type)
+                       m--;
+               if (m < l) {    // no match in [l, m]
+                       l = true_m + 1;
+                       continue;
+               }
+
+               // actual binary search
+               any_matches = 1;
+               if (stabs[m].n_value < addr) {
+                       *region_left = m;
+                       l = true_m + 1;
+               } else if (stabs[m].n_value > addr) {
+                       *region_right = m - 1;
+                       r = m - 1;
+               } else {
+                       // exact match for 'addr', but continue loop to find
+                       // *region_right
+                       *region_left = m;
+                       l = m;
+                       addr++;
+               }
+       }
+
+       if (!any_matches)
+               *region_right = *region_left - 1;
+       else {
+               // find rightmost region containing 'addr'
+               for (l = *region_right;
+                    l > *region_left && stabs[l].n_type != type;
+                    l--)
+                       /* do nothing */;
+               *region_left = l;
+       }
+}
+
+
+// debuginfo_eip(addr, info)
+//
+//     Fill in the 'info' structure with information about the specified
+//     instruction address, 'addr'.  Returns 0 if information was found, and
+//     negative if not.  But even if it returns negative it has stored some
+//     information into '*info'.
+//
+int
+debuginfo_eip(uintptr_t addr, struct Eipdebuginfo *info)
+{
+       const struct Stab *stabs, *stab_end;
+       const char *stabstr, *stabstr_end;
+       int lfile, rfile, lfun, rfun, lline, rline;
+
+       // Initialize *info
+       info->eip_file = "<unknown>";
+       info->eip_line = 0;
+       info->eip_fn_name = "<unknown>";
+       info->eip_fn_namelen = 9;
+       info->eip_fn_addr = addr;
+       info->eip_fn_narg = 0;
+
+       // Find the relevant set of stabs
+       if (addr >= ULIM) {
+               stabs = __STAB_BEGIN__;
+               stab_end = __STAB_END__;
+               stabstr = __STABSTR_BEGIN__;
+               stabstr_end = __STABSTR_END__;
+       } else {
+               // Can't search for user-level addresses yet!
+               panic("User address");
+       }
+
+       // String table validity checks
+       if (stabstr_end <= stabstr || stabstr_end[-1] != 0)
+               return -1;
+
+       // Now we find the right stabs that define the function containing
+       // 'eip'.  First, we find the basic source file containing 'eip'.
+       // Then, we look in that source file for the function.  Then we look
+       // for the line number.
+       
+       // Search the entire set of stabs for the source file (type N_SO).
+       lfile = 0;
+       rfile = (stab_end - stabs) - 1;
+       stab_binsearch(stabs, &lfile, &rfile, N_SO, addr);
+       if (lfile == 0)
+               return -1;
+
+       // Search within that file's stabs for the function definition
+       // (N_FUN).
+       lfun = lfile;
+       rfun = rfile;
+       stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr);
+
+       if (lfun <= rfun) {
+               // stabs[lfun] points to the function name
+               // in the string table, but check bounds just in case.
+               if (stabs[lfun].n_strx < stabstr_end - stabstr)
+                       info->eip_fn_name = stabstr + stabs[lfun].n_strx;
+               info->eip_fn_addr = stabs[lfun].n_value;
+               addr -= info->eip_fn_addr;
+               // Search within the function definition for the line number.
+               lline = lfun;
+               rline = rfun;
+       } else {
+               // Couldn't find function stab!  Maybe we're in an assembly
+               // file.  Search the whole file for the line number.
+               info->eip_fn_addr = addr;
+               lline = lfile;
+               rline = rfile;
+       }
+       // Ignore stuff after the colon.
+       info->eip_fn_namelen = strfind(info->eip_fn_name, ':') - info->eip_fn_name;
+
+       
+       // Search within [lline, rline] for the line number stab.
+       // If found, set info->eip_line to the right line number.
+       // If not found, return -1.
+       //
+       // Hint:
+       //      There's a particular stabs type used for line numbers.
+       //      Look at the STABS documentation and <inc/stab.h> to find
+       //      which one.
+       // Your code here.
+
+       
+       // Search backwards from the line number for the relevant filename
+       // stab.
+       // We can't just use the "lfile" stab because inlined functions
+       // can interpolate code from a different file!
+       // Such included source files use the N_SOL stab type.
+       while (lline >= lfile
+              && stabs[lline].n_type != N_SOL
+              && (stabs[lline].n_type != N_SO || !stabs[lline].n_value))
+               lline--;
+       if (lline >= lfile && stabs[lline].n_strx < stabstr_end - stabstr)
+               info->eip_file = stabstr + stabs[lline].n_strx;
+
+
+       // Set eip_fn_narg to the number of arguments taken by the function,
+       // or 0 if there was no containing function.
+       // Your code here.
+
+       
+       return 0;
+}
diff --git a/kern/kdebug.h b/kern/kdebug.h
new file mode 100644 (file)
index 0000000..236af39
--- /dev/null
@@ -0,0 +1,20 @@
+#ifndef JOS_KERN_KDEBUG_H
+#define JOS_KERN_KDEBUG_H
+
+#include <inc/types.h>
+
+// Debug information about a particular instruction pointer
+struct Eipdebuginfo {
+       const char *eip_file;           // Source code filename for EIP
+       int eip_line;                   // Source code linenumber for EIP
+
+       const char *eip_fn_name;        // Name of function containing EIP
+                                       //  - Note: not null terminated!
+       int eip_fn_namelen;             // Length of function name
+       uintptr_t eip_fn_addr;          // Address of start of function
+       int eip_fn_narg;                // Number of function arguments
+};
+
+int debuginfo_eip(uintptr_t eip, struct Eipdebuginfo *info);
+
+#endif
index 21ecc4a..ec50f11 100644 (file)
@@ -10,6 +10,7 @@
 
 #include <kern/console.h>
 #include <kern/monitor.h>
+#include <kern/kdebug.h>
 
 #define CMDBUF_SIZE    80      // enough for one VGA text line
 
diff --git a/kern/pmap.c b/kern/pmap.c
new file mode 100644 (file)
index 0000000..8e33a94
--- /dev/null
@@ -0,0 +1,655 @@
+/* See COPYRIGHT for copyright information. */
+
+#include <inc/x86.h>
+#include <inc/mmu.h>
+#include <inc/error.h>
+#include <inc/string.h>
+#include <inc/assert.h>
+
+#include <kern/pmap.h>
+#include <kern/kclock.h>
+
+// These variables are set by i386_detect_memory()
+static physaddr_t maxpa;       // Maximum physical address
+size_t npage;                  // Amount of physical memory (in pages)
+static size_t basemem;         // Amount of base memory (in bytes)
+static size_t extmem;          // Amount of extended memory (in bytes)
+
+// These variables are set in i386_vm_init()
+pde_t* boot_pgdir;             // Virtual address of boot time page directory
+physaddr_t boot_cr3;           // Physical address of boot time page directory
+static char* boot_freemem;     // Pointer to next byte of free mem
+
+struct Page* pages;            // Virtual address of physical page array
+static struct Page_list page_free_list;        // Free list of physical pages
+
+// Global descriptor table.
+//
+// The kernel and user segments are identical (except for the DPL).
+// To load the SS register, the CPL must equal the DPL.  Thus,
+// we must duplicate the segments for the user and the kernel.
+//
+struct Segdesc gdt[] =
+{
+       // 0x0 - unused (always faults -- for trapping NULL far pointers)
+       SEG_NULL,
+
+       // 0x8 - kernel code segment
+       [GD_KT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 0),
+
+       // 0x10 - kernel data segment
+       [GD_KD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 0),
+
+       // 0x18 - user code segment
+       [GD_UT >> 3] = SEG(STA_X | STA_R, 0x0, 0xffffffff, 3),
+
+       // 0x20 - user data segment
+       [GD_UD >> 3] = SEG(STA_W, 0x0, 0xffffffff, 3),
+
+       // 0x28 - tss, initialized in idt_init()
+       [GD_TSS >> 3] = SEG_NULL
+};
+
+struct Pseudodesc gdt_pd = {
+       sizeof(gdt) - 1, (unsigned long) gdt
+};
+
+static int
+nvram_read(int r)
+{
+       return mc146818_read(r) | (mc146818_read(r + 1) << 8);
+}
+
+void
+i386_detect_memory(void)
+{
+       // CMOS tells us how many kilobytes there are
+       basemem = ROUNDDOWN(nvram_read(NVRAM_BASELO)*1024, PGSIZE);
+       extmem = ROUNDDOWN(nvram_read(NVRAM_EXTLO)*1024, PGSIZE);
+
+       // Calculate the maximum physical address based on whether
+       // or not there is any extended memory.  See comment in <inc/mmu.h>.
+       if (extmem)
+               maxpa = EXTPHYSMEM + extmem;
+       else
+               maxpa = basemem;
+
+       npage = maxpa / PGSIZE;
+
+       cprintf("Physical memory: %dK available, ", (int)(maxpa/1024));
+       cprintf("base = %dK, extended = %dK\n", (int)(basemem/1024), (int)(extmem/1024));
+}
+
+// --------------------------------------------------------------
+// Set up initial memory mappings and turn on MMU.
+// --------------------------------------------------------------
+
+static void check_boot_pgdir(void);
+
+//
+// Allocate n bytes of physical memory aligned on an 
+// align-byte boundary.  Align must be a power of two.
+// Return kernel virtual address.  Returned memory is uninitialized.
+//
+// If we're out of memory, boot_alloc should panic.
+// This function may ONLY be used during initialization,
+// before the page_free_list has been set up.
+// 
+static void*
+boot_alloc(uint32_t n, uint32_t align)
+{
+       extern char end[];
+       void *v;
+
+       // Initialize boot_freemem if this is the first time.
+       // 'end' is a magic symbol automatically generated by the linker,
+       // which points to the end of the kernel's bss segment -
+       // i.e., the first virtual address that the linker
+       // did _not_ assign to any kernel code or global variables.
+       if (boot_freemem == 0)
+               boot_freemem = end;
+
+       // LAB 2: Your code here:
+       //      Step 1: round boot_freemem up to be aligned properly
+       //      Step 2: save current value of boot_freemem as allocated chunk
+       //      Step 3: increase boot_freemem to record allocation
+       //      Step 4: return allocated chunk
+
+       return NULL;
+}
+
+//
+// Given pgdir, a pointer to a page directory,
+// walk the 2-level page table structure to find
+// the page table entry (PTE) for linear address la.
+// Return a pointer to this PTE.
+//
+// If the relevant page table doesn't exist in the page directory:
+//     - If create == 0, return 0.
+//     - Otherwise allocate a new page table, install it into pgdir,
+//       and return a pointer into it.
+//        (Questions: What data should the new page table contain?
+//       And what permissions should the new pgdir entry have?
+//       Note that we use the 486-only "WP" feature of %cr0, which
+//       affects the way supervisor-mode writes are checked.)
+//
+// This function abstracts away the 2-level nature of
+// the page directory by allocating new page tables
+// as needed.
+// 
+// boot_pgdir_walk may ONLY be used during initialization,
+// before the page_free_list has been set up.
+// It should panic on failure.  (Note that boot_alloc already panics
+// on failure.)
+//
+static pte_t*
+boot_pgdir_walk(pde_t *pgdir, uintptr_t la, int create)
+{
+       return 0;
+}
+
+//
+// Map [la, la+size) of linear address space to physical [pa, pa+size)
+// in the page table rooted at pgdir.  Size is a multiple of PGSIZE.
+// Use permission bits perm|PTE_P for the entries.
+//
+// This function may ONLY be used during initialization,
+// before the page_free_list has been set up.
+//
+static void
+boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm)
+{
+}
+
+// Set up a two-level page table:
+//    boot_pgdir is its linear (virtual) address of the root
+//    boot_cr3 is the physical adresss of the root
+// Then turn on paging.  Then effectively turn off segmentation.
+// (i.e., the segment base addrs are set to zero).
+// 
+// This function only sets up the kernel part of the address space
+// (ie. addresses >= UTOP).  The user part of the address space
+// will be setup later.
+//
+// From UTOP to ULIM, the user is allowed to read but not write.
+// Above ULIM the user cannot read (or write). 
+void
+i386_vm_init(void)
+{
+       pde_t* pgdir;
+       uint32_t cr0;
+       size_t n;
+
+       // Remove this line when you're ready to test this function.
+       panic("i386_vm_init: This function is not finished\n");
+
+       //////////////////////////////////////////////////////////////////////
+       // create initial page directory.
+       pgdir = boot_alloc(PGSIZE, PGSIZE);
+       memset(pgdir, 0, PGSIZE);
+       boot_pgdir = pgdir;
+       boot_cr3 = PADDR(pgdir);
+
+       //////////////////////////////////////////////////////////////////////
+       // Recursively insert PD in itself as a page table, to form
+       // a virtual page table at virtual address VPT.
+       // (For now, you don't have understand the greater purpose of the
+       // following two lines.)
+
+       // Permissions: kernel RW, user NONE
+       pgdir[PDX(VPT)] = PADDR(pgdir)|PTE_W|PTE_P;
+
+       // same for UVPT
+       // Permissions: kernel R, user R 
+       pgdir[PDX(UVPT)] = PADDR(pgdir)|PTE_U|PTE_P;
+
+       //////////////////////////////////////////////////////////////////////
+       // Map the kernel stack (symbol name "bootstack").  The complete VA
+       // range of the stack, [KSTACKTOP-PTSIZE, KSTACKTOP), breaks into two
+       // pieces:
+       //     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
+       //     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed => faults
+       //     Permissions: kernel RW, user NONE
+       // Your code goes here:
+
+       //////////////////////////////////////////////////////////////////////
+       // Map all of physical memory at KERNBASE. 
+       // Ie.  the VA range [KERNBASE, 2^32) should map to
+       //      the PA range [0, 2^32 - KERNBASE)
+       // We might not have 2^32 - KERNBASE bytes of physical memory, but
+       // we just set up the mapping anyway.
+       // Permissions: kernel RW, user NONE
+       // Your code goes here: 
+
+       //////////////////////////////////////////////////////////////////////
+       // Make 'pages' point to an array of size 'npage' of 'struct Page'.
+       // The kernel uses this structure to keep track of physical pages;
+       // 'npage' equals the number of physical pages in memory.  User-level
+       // programs get read-only access to the array as well.
+       // You must allocate the array yourself.
+       // Map this array read-only by the user at linear address UPAGES
+       // (ie. perm = PTE_U | PTE_P)
+       // Permissions:
+       //    - pages -- kernel RW, user NONE
+       //    - the read-only version mapped at UPAGES -- kernel R, user R
+       // Your code goes here: 
+
+       // Check that the initial page directory has been set up correctly.
+       check_boot_pgdir();
+
+       //////////////////////////////////////////////////////////////////////
+       // On x86, segmentation maps a VA to a LA (linear addr) and
+       // paging maps the LA to a PA.  I.e. VA => LA => PA.  If paging is
+       // turned off the LA is used as the PA.  Note: there is no way to
+       // turn off segmentation.  The closest thing is to set the base
+       // address to 0, so the VA => LA mapping is the identity.
+
+       // Current mapping: VA KERNBASE+x => PA x.
+       //     (segmentation base=-KERNBASE and paging is off)
+
+       // From here on down we must maintain this VA KERNBASE + x => PA x
+       // mapping, even though we are turning on paging and reconfiguring
+       // segmentation.
+
+       // Map VA 0:4MB same as VA KERNBASE, i.e. to PA 0:4MB.
+       // (Limits our kernel to <4MB)
+       pgdir[0] = pgdir[PDX(KERNBASE)];
+
+       // Install page table.
+       lcr3(boot_cr3);
+
+       // Turn on paging.
+       cr0 = rcr0();
+       cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_TS|CR0_EM|CR0_MP;
+       cr0 &= ~(CR0_TS|CR0_EM);
+       lcr0(cr0);
+
+       // Current mapping: KERNBASE+x => x => x.
+       // (x < 4MB so uses paging pgdir[0])
+
+       // Reload all segment registers.
+       asm volatile("lgdt gdt_pd");
+       asm volatile("movw %%ax,%%gs" :: "a" (GD_UD|3));
+       asm volatile("movw %%ax,%%fs" :: "a" (GD_UD|3));
+       asm volatile("movw %%ax,%%es" :: "a" (GD_KD));
+       asm volatile("movw %%ax,%%ds" :: "a" (GD_KD));
+       asm volatile("movw %%ax,%%ss" :: "a" (GD_KD));
+       asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (GD_KT));  // reload cs
+       asm volatile("lldt %%ax" :: "a" (0));
+
+       // Final mapping: KERNBASE+x => KERNBASE+x => x.
+
+       // This mapping was only used after paging was turned on but
+       // before the segment registers were reloaded.
+       pgdir[0] = 0;
+
+       // Flush the TLB for good measure, to kill the pgdir[0] mapping.
+       lcr3(boot_cr3);
+}
+
+//
+// Checks that the kernel part of virtual address space
+// has been setup roughly correctly(by i386_vm_init()).
+//
+// This function doesn't test every corner case,
+// in fact it doesn't test the permission bits at all,
+// but it is a pretty good sanity check. 
+//
+static physaddr_t check_va2pa(pde_t *pgdir, uintptr_t va);
+
+static void
+check_boot_pgdir(void)
+{
+       uint32_t i, n;
+       pde_t *pgdir;
+
+       pgdir = boot_pgdir;
+
+       // check pages array
+       n = ROUNDUP(npage*sizeof(struct Page), PGSIZE);
+       for (i = 0; i < n; i += PGSIZE)
+               assert(check_va2pa(pgdir, UPAGES + i) == PADDR(pages) + i);
+       
+
+       // check phys mem
+       for (i = 0; KERNBASE + i != 0; i += PGSIZE)
+               assert(check_va2pa(pgdir, KERNBASE + i) == i);
+
+       // check kernel stack
+       for (i = 0; i < KSTKSIZE; i += PGSIZE)
+               assert(check_va2pa(pgdir, KSTACKTOP - KSTKSIZE + i) == PADDR(bootstack) + i);
+
+       // check for zero/non-zero in PDEs
+       for (i = 0; i < NPDENTRIES; i++) {
+               switch (i) {
+               case PDX(VPT):
+               case PDX(UVPT):
+               case PDX(KSTACKTOP-1):
+               case PDX(UPAGES):
+                       assert(pgdir[i]);
+                       break;
+               default:
+                       if (i >= PDX(KERNBASE))
+                               assert(pgdir[i]);
+                       else
+                               assert(pgdir[i] == 0);
+                       break;
+               }
+       }
+       cprintf("check_boot_pgdir() succeeded!\n");
+}
+
+// This function returns the physical address of the page containing 'va',
+// defined by the page directory 'pgdir'.  The hardware normally performs
+// this functionality for us!  We define our own version to help check
+// the check_boot_pgdir() function; it shouldn't be used elsewhere.
+
+static physaddr_t
+check_va2pa(pde_t *pgdir, uintptr_t va)
+{
+       pte_t *p;
+
+       pgdir = &pgdir[PDX(va)];
+       if (!(*pgdir & PTE_P))
+               return ~0;
+       p = (pte_t*) KADDR(PTE_ADDR(*pgdir));
+       if (!(p[PTX(va)] & PTE_P))
+               return ~0;
+       return PTE_ADDR(p[PTX(va)]);
+}
+               
+// --------------------------------------------------------------
+// Tracking of physical pages.
+// The 'pages' array has one 'struct Page' entry per physical page.
+// Pages are reference counted, and free pages are kept on a linked list.
+// --------------------------------------------------------------
+
+//  
+// Initialize page structure and memory free list.
+// After this point, ONLY use the functions below
+// to allocate and deallocate physical memory via the page_free_list,
+// and NEVER use boot_alloc() or the related boot-time functions above.
+//
+void
+page_init(void)
+{
+       // The example code here marks all pages as free.
+       // However this is not truly the case.  What memory is free?
+       //  1) Mark page 0 as in use.
+       //     This way we preserve the real-mode IDT and BIOS structures
+       //     in case we ever need them.  (Currently we don't, but...)
+       //  2) Mark the rest of base memory as free.
+       //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM).
+       //     Mark it as in use so that it can never be allocated.      
+       //  4) Then extended memory [EXTPHYSMEM, ...).
+       //     Some of it is in use, some is free. Where is the kernel?
+       //     Which pages are used for page tables and other data structures?
+       //
+       // Change the code to reflect this.
+       int i;
+       LIST_INIT(&page_free_list);
+       for (i = 0; i < npage; i++) {
+               pages[i].pp_ref = 0;
+               LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
+       }
+}
+
+//
+// Initialize a Page structure.
+// The result has null links and 0 refcount.
+// Note that the corresponding physical page is NOT initialized!
+//
+static void
+page_initpp(struct Page *pp)
+{
+       memset(pp, 0, sizeof(*pp));
+}
+
+//
+// Allocates a physical page.
+// Does NOT set the contents of the physical page to zero -
+// the caller must do that if necessary.
+//
+// *pp_store -- is set to point to the Page struct of the newly allocated
+// page
+//
+// RETURNS 
+//   0 -- on success
+//   -E_NO_MEM -- otherwise 
+//
+// Hint: use LIST_FIRST, LIST_REMOVE, and page_initpp
+// Hint: pp_ref should not be incremented 
+int
+page_alloc(struct Page **pp_store)
+{
+       // Fill this function in
+       return -E_NO_MEM;
+}
+
+//
+// Return a page to the free list.
+// (This function should only be called when pp->pp_ref reaches 0.)
+//
+void
+page_free(struct Page *pp)
+{
+       // Fill this function in
+}
+
+//
+// Decrement the reference count on a page,
+// freeing it if there are no more refs.
+//
+void
+page_decref(struct Page* pp)
+{
+       if (--pp->pp_ref == 0)
+               page_free(pp);
+}
+
+// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
+// a pointer to the page table entry (PTE) for linear address 'va'.
+// This requires walking the two-level page table structure.
+//
+// If the relevant page table doesn't exist in the page directory, then:
+//    - If create == 0, pgdir_walk returns NULL.
+//    - Otherwise, pgdir_walk tries to allocate a new page table
+//     with page_alloc.  If this fails, pgdir_walk returns NULL.
+//    - Otherwise, pgdir_walk returns a pointer into the new page table.
+//
+// This is boot_pgdir_walk, but using page_alloc() instead of boot_alloc().
+// Unlike boot_pgdir_walk, pgdir_walk can fail.
+//
+// Hint: you can turn a Page * into the physical address of the
+// page it refers to with page2pa() from kern/pmap.h.
+pte_t *
+pgdir_walk(pde_t *pgdir, const void *va, int create)
+{
+       // Fill this function in
+       return NULL;
+}
+
+//
+// Map the physical page 'pp' at virtual address 'va'.
+// The permissions (the low 12 bits) of the page table
+//  entry should be set to 'perm|PTE_P'.
+//
+// Details
+//   - If there is already a page mapped at 'va', it is page_remove()d.
+//   - If necessary, on demand, allocates a page table and inserts it into
+//     'pgdir'.
+//   - pp->pp_ref should be incremented if the insertion succeeds.
+//   - The TLB must be invalidated if a page was formerly present at 'va'.
+//
+// RETURNS: 
+//   0 on success
+//   -E_NO_MEM, if page table couldn't be allocated
+//
+// Hint: The TA solution is implemented using pgdir_walk, page_remove,
+// and page2pa.
+//
+int
+page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm) 
+{
+       // Fill this function in
+       return 0;
+}
+
+//
+// Return the page mapped at virtual address 'va'.
+// If pte_store is not zero, then we store in it the address
+// of the pte for this page.  This is used by page_remove
+// but should not be used by other callers.
+//
+// Return 0 if there is no page mapped at va.
+//
+// Hint: the TA solution uses pgdir_walk and pa2page.
+//
+struct Page *
+page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
+{
+       // Fill this function in
+       return NULL;
+}
+
+//
+// Unmaps the physical page at virtual address 'va'.
+// If there is no physical page at that address, silently does nothing.
+//
+// Details:
+//   - The ref count on the physical page should decrement.
+//   - The physical page should be freed if the refcount reaches 0.
+//   - The pg table entry corresponding to 'va' should be set to 0.
+//     (if such a PTE exists)
+//   - The TLB must be invalidated if you remove an entry from
+//     the pg dir/pg table.
+//
+// Hint: The TA solution is implemented using page_lookup,
+//     tlb_invalidate, and page_decref.
+//
+void
+page_remove(pde_t *pgdir, void *va)
+{
+       // Fill this function in
+}
+
+//
+// Invalidate a TLB entry, but only if the page tables being
+// edited are the ones currently in use by the processor.
+//
+void
+tlb_invalidate(pde_t *pgdir, void *va)
+{
+       // Flush the entry only if we're modifying the current address space.
+       // For now, there is only one address space, so always invalidate.
+       invlpg(va);
+}
+
+void
+page_check(void)
+{
+       struct Page *pp, *pp0, *pp1, *pp2;
+       struct Page_list fl;
+       pte_t *ptep;
+
+       // should be able to allocate three pages
+       pp0 = pp1 = pp2 = 0;
+       assert(page_alloc(&pp0) == 0);
+       assert(page_alloc(&pp1) == 0);
+       assert(page_alloc(&pp2) == 0);
+
+       assert(pp0);
+       assert(pp1 && pp1 != pp0);
+       assert(pp2 && pp2 != pp1 && pp2 != pp0);
+
+       // temporarily steal the rest of the free pages
+       fl = page_free_list;
+       LIST_INIT(&page_free_list);
+
+       // should be no free memory
+       assert(page_alloc(&pp) == -E_NO_MEM);
+
+       // there is no page allocated at address 0
+       assert(page_lookup(boot_pgdir, (void *) 0x0, &ptep) == NULL);
+
+       // there is no free memory, so we can't allocate a page table 
+       assert(page_insert(boot_pgdir, pp1, 0x0, 0) < 0);
+
+       // free pp0 and try again: pp0 should be used for page table
+       page_free(pp0);
+       assert(page_insert(boot_pgdir, pp1, 0x0, 0) == 0);
+       assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
+       assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
+       assert(pp1->pp_ref == 1);
+       assert(pp0->pp_ref == 1);
+
+       // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
+       assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, 0) == 0);
+       assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
+       assert(pp2->pp_ref == 1);
+
+       // should be no free memory
+       assert(page_alloc(&pp) == -E_NO_MEM);
+
+       // should be able to map pp2 at PGSIZE because it's already there
+       assert(page_insert(boot_pgdir, pp2, (void*) PGSIZE, 0) == 0);
+       assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
+       assert(pp2->pp_ref == 1);
+
+       // pp2 should NOT be on the free list
+       // could happen in ref counts are handled sloppily in page_insert
+       assert(page_alloc(&pp) == -E_NO_MEM);
+
+       // should not be able to map at PTSIZE because need free page for page table
+       assert(page_insert(boot_pgdir, pp0, (void*) PTSIZE, 0) < 0);
+
+       // insert pp1 at PGSIZE (replacing pp2)
+       assert(page_insert(boot_pgdir, pp1, (void*) PGSIZE, 0) == 0);
+
+       // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
+       assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
+       assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
+       // ... and ref counts should reflect this
+       assert(pp1->pp_ref == 2);
+       assert(pp2->pp_ref == 0);
+
+       // pp2 should be returned by page_alloc
+       assert(page_alloc(&pp) == 0 && pp == pp2);
+
+       // unmapping pp1 at 0 should keep pp1 at PGSIZE
+       page_remove(boot_pgdir, 0x0);
+       assert(check_va2pa(boot_pgdir, 0x0) == ~0);
+       assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
+       assert(pp1->pp_ref == 1);
+       assert(pp2->pp_ref == 0);
+
+       // unmapping pp1 at PGSIZE should free it
+       page_remove(boot_pgdir, (void*) PGSIZE);
+       assert(check_va2pa(boot_pgdir, 0x0) == ~0);
+       assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
+       assert(pp1->pp_ref == 0);
+       assert(pp2->pp_ref == 0);
+
+       // so it should be returned by page_alloc
+       assert(page_alloc(&pp) == 0 && pp == pp1);
+
+       // should be no free memory
+       assert(page_alloc(&pp) == -E_NO_MEM);
+
+       // forcibly take pp0 back
+       assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
+       boot_pgdir[0] = 0;
+       assert(pp0->pp_ref == 1);
+       pp0->pp_ref = 0;
+
+       // give free list back
+       page_free_list = fl;
+
+       // free the pages we took
+       page_free(pp0);
+       page_free(pp1);
+       page_free(pp2);
+
+       cprintf("page_check() succeeded!\n");
+}
+
diff --git a/kern/pmap.h b/kern/pmap.h
new file mode 100644 (file)
index 0000000..734dd97
--- /dev/null
@@ -0,0 +1,92 @@
+/* See COPYRIGHT for copyright information. */
+
+#ifndef JOS_KERN_PMAP_H
+#define JOS_KERN_PMAP_H
+#ifndef JOS_KERNEL
+# error "This is a JOS kernel header; user programs should not #include it"
+#endif
+
+#include <inc/memlayout.h>
+#include <inc/assert.h>
+
+
+/* This macro takes a kernel virtual address -- an address that points above
+ * KERNBASE, where the machine's maximum 256MB of physical memory is mapped --
+ * and returns the corresponding physical address.  It panics if you pass it a
+ * non-kernel virtual address.
+ */
+#define PADDR(kva)                                             \
+({                                                             \
+       physaddr_t __m_kva = (physaddr_t) (kva);                \
+       if (__m_kva < KERNBASE)                                 \
+               panic("PADDR called with invalid kva %08lx", __m_kva);\
+       __m_kva - KERNBASE;                                     \
+})
+
+/* This macro takes a physical address and returns the corresponding kernel
+ * virtual address.  It panics if you pass an invalid physical address. */
+#define KADDR(pa)                                              \
+({                                                             \
+       physaddr_t __m_pa = (pa);                               \
+       uint32_t __m_ppn = PPN(__m_pa);                         \
+       if (__m_ppn >= npage)                                   \
+               panic("KADDR called with invalid pa %08lx", __m_pa);\
+       (void*) (__m_pa + KERNBASE);                            \
+})
+
+
+
+extern char bootstacktop[], bootstack[];
+
+extern struct Page *pages;
+extern size_t npage;
+
+extern physaddr_t boot_cr3;
+extern pde_t *boot_pgdir;
+
+extern struct Segdesc gdt[];
+extern struct Pseudodesc gdt_pd;
+
+void   i386_vm_init();
+void   i386_detect_memory();
+
+void   page_init(void);
+void   page_check(void);
+int    page_alloc(struct Page **pp_store);
+void   page_free(struct Page *pp);
+int    page_insert(pde_t *pgdir, struct Page *pp, void *va, int perm);
+void   page_remove(pde_t *pgdir, void *va);
+struct Page *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store);
+void   page_decref(struct Page *pp);
+
+void   tlb_invalidate(pde_t *pgdir, void *va);
+
+static inline ppn_t
+page2ppn(struct Page *pp)
+{
+       return pp - pages;
+}
+
+static inline physaddr_t
+page2pa(struct Page *pp)
+{
+       return page2ppn(pp) << PGSHIFT;
+}
+
+static inline struct Page*
+pa2page(physaddr_t pa)
+{
+       if (PPN(pa) >= npage)
+               panic("pa2page called with invalid pa");
+       return &pages[PPN(pa)];
+}
+
+static inline void*
+page2kva(struct Page *pp)
+{
+       return KADDR(page2pa(pp));
+}
+
+pte_t *pgdir_walk(pde_t *pgdir, const void *va, int create);
+
+#endif /* !JOS_KERN_PMAP_H */
diff --git a/kern/trap.h b/kern/trap.h
new file mode 100644 (file)
index 0000000..8aa7648
--- /dev/null
@@ -0,0 +1,21 @@
+/* See COPYRIGHT for copyright information. */
+
+#ifndef JOS_KERN_TRAP_H
+#define JOS_KERN_TRAP_H
+#ifndef JOS_KERNEL
+# error "This is a JOS kernel header; user programs should not #include it"
+#endif
+
+#include <inc/trap.h>
+#include <inc/mmu.h>
+
+/* The kernel's interrupt descriptor table */
+extern struct Gatedesc idt[];
+
+void idt_init(void);
+void print_regs(struct PushRegs *regs);
+void print_trapframe(struct Trapframe *tf);
+void page_fault_handler(struct Trapframe *);
+void backtrace(struct Trapframe *);
+
+#endif /* JOS_KERN_TRAP_H */