Ashish has a tree consisting of n nodes numbered 1 to n rooted at node 1. The i-th node in the tree has a cost ai, and binary digit bi is written in it. He wants to have binary digit ci written in the i-th node in the end.
To achieve this, he can perform the following operation any number of times:
Select any k nodes from the subtree of any node u, and shuffle the digits in these nodes as he wishes, incurring a cost of k⋅au. Here, he can choose k ranging from 1 to the size of the subtree of u.
He wants to perform the operations in such a way that every node finally has the digit corresponding to its target.
Help him find the minimum total cost he needs to spend so that after all the operations, every node u has digit cu written in it, or determine that it is impossible.
Input
First line contains a single integer n(1≤n≤2⋅105) denoting the number of nodes in the tree.
i-th line of the next n lines contains 3 space-separated integers ai, bi, ci(1≤ai≤109,0≤bi,ci≤1) — the cost of the i-th node, its initial digit and its goal digit.
Each of the next n−1 lines contain two integers u, v(1≤u,v≤n,u≠v), meaning that there is an edge between nodes u and v in the tree.
Output
Print the minimum total cost to make every node reach its target digit, and −1 if it is impossible.
In sample 1, we can choose node 1 and k=4 for a cost of 4⋅1=4 and select nodes 1,2,3,5, shuffle their digits and get the desired digits in every node.
In sample 2, we can choose node 1 and k=2 for a cost of 10000⋅2, select nodes 1,5 and exchange their digits, and similarly, choose node 2 and k=2 for a cost of 2000⋅2, select nodes 2,3 and exchange their digits to get the desired digits in every node.
In sample 3, it is impossible to get the desired digits, because there is no node with digit 1 initially.
// If this is the file server (type == ENV_TYPE_FS) give it I/O privileges. // LAB 5: Your code here. if(type == ENV_TYPE_FS) e->env_tf.tf_eflags |= FL_IOPL_MASK;
// Allocate a page in the disk map region, read the contents // of the block from the disk into that page. // Hint: first round addr to page boundary. fs/ide.c has code to read // the disk. // // LAB 5: you code here: addr = ROUNDDOWN(addr, BLKSIZE); if((r = sys_page_alloc(0, addr, PTE_U | PTE_P | PTE_W)) < 0) panic("in bc_pgfault, sys_page_alloc: %e", r); if((r = ide_read(blockno << 3, addr, 8)) < 0) panic("in_bc_pgfault, ide_read: %e", r);
// Mark a block free in the bitmap void free_block(uint32_t blockno) { // Blockno zero is the null pointer of block numbers. if (blockno == 0) panic("attempt to free zero block"); bitmap[blockno/32] |= 1<<(blockno%32); }
// Search the bitmap for a free block and allocate it. When you // allocate a block, immediately flush the changed bitmap block // to disk. // // Return block number allocated on success, // -E_NO_DISK if we are out of blocks. // // Hint: use free_block as an example for manipulating the bitmap. int alloc_block(void) { // The bitmap consists of one or more blocks. A single bitmap block // contains the in-use bits for BLKBITSIZE blocks. There are // super->s_nblocks blocks in the disk altogether.
// Find the disk block number slot for the 'filebno'th block in file 'f'. // Set '*ppdiskbno' to point to that slot. // The slot will be one of the f->f_direct[] entries, // or an entry in the indirect block. // When 'alloc' is set, this function will allocate an indirect block // if necessary. // // Returns: // 0 on success (but note that *ppdiskbno might equal 0). // -E_NOT_FOUND if the function needed to allocate an indirect block, but // alloc was 0. // -E_NO_DISK if there's no space on the disk for an indirect block. // -E_INVAL if filebno is out of range (it's >= NDIRECT + NINDIRECT). // // Analogy: This is like pgdir_walk for files. // Hint: Don't forget to clear any block you allocate. staticint file_block_walk(struct File *f, uint32_t filebno, uint32_t **ppdiskbno, bool alloc) { // LAB 5: Your code here. int r;
// Set *blk to the address in memory where the filebno'th // block of file 'f' would be mapped. // // Returns 0 on success, < 0 on error. Errors are: // -E_NO_DISK if a block needed to be allocated but the disk is full. // -E_INVAL if filebno is out of range. // // Hint: Use file_block_walk and alloc_block. int file_get_block(struct File *f, uint32_t filebno, char **blk) { // LAB 5: Your code here. uint32_t * pdiskbno; int r; if((r = file_block_walk(f, filebno, &pdiskbno, true)) < 0) return r; if(*pdiskbno == 0){ if((r = alloc_block()) < 0) return r; *pdiskbno = r; } *blk = (char *)diskaddr(*pdiskbno); flush_block(*blk); return0; }
// Read at most ipc->read.req_n bytes from the current seek position // in ipc->read.req_fileid. Return the bytes read from the file to // the caller in ipc->readRet, then update the seek position. Returns // the number of bytes successfully read, or < 0 on error. int serve_read(envid_t envid, union Fsipc *ipc) { structFsreq_read *req = &ipc->read; structFsret_read *ret = &ipc->readRet;
if (debug) cprintf("serve_read %08x %08x %08x\n", envid, req->req_fileid, req->req_n);
// Write req->req_n bytes from req->req_buf to req_fileid, starting at // the current seek position, and update the seek position // accordingly. Extend the file if necessary. Returns the number of // bytes written, or < 0 on error. int serve_write(envid_t envid, struct Fsreq_write *req) { if (debug) cprintf("serve_write %08x %08x %08x\n", envid, req->req_fileid, req->req_n);
// Write at most 'n' bytes from 'buf' to 'fd' at the current seek position. // // Returns: // The number of bytes successfully written. // < 0 on error. staticssize_t devfile_write(struct Fd *fd, constvoid *buf, size_t n) { // Make an FSREQ_WRITE request to the file system server. Be // careful: fsipcbuf.write.req_buf is only so large, but // remember that write is always allowed to write *fewer* // bytes than requested. // LAB 5: Your code here int r; fsipcbuf.write.req_fileid = fd->fd_file.id; fsipcbuf.write.req_n = n; memmove(fsipcbuf.write.req_buf, buf, n); if((r = fsipc(FSREQ_WRITE, NULL)) < 0) return r; assert(r <= n); assert(r <= PGSIZE); return r; }
// Set envid's trap frame to 'tf'. // tf is modified to make sure that user environments always run at code // protection level 3 (CPL 3), interrupts enabled, and IOPL of 0. // // Returns 0 on success, < 0 on error. Errors are: // -E_BAD_ENV if environment envid doesn't currently exist, // or the caller doesn't have permission to change envid. staticint sys_env_set_trapframe(envid_t envid, struct Trapframe *tf) { // LAB 5: Your code here. // Remember to check whether the user has supplied us with a good // address! structEnv* env; if(envid2env(envid, &env, 1)) return -E_BAD_ENV; env->env_tf = *tf; env->env_tf.tf_eflags |= FL_IF; env->env_tf.tf_eflags &= ~FL_IOPL_MASK; env->env_tf.tf_cs |= 3; return0; panic("sys_env_set_trapframe not implemented"); }
case'>': // Output redirection // Grab the filename from the argument list if (gettoken(0, &t) != 'w') { cprintf("syntax error: > not followed by word\n"); exit(); } if ((fd = open(t, O_WRONLY|O_CREAT|O_TRUNC)) < 0) { cprintf("open %s for write: %e", t, fd); exit(); } if (fd != 1) { dup(fd, 1); close(fd); } break;
internal FS tests [fs/test.c]: OK (1.0s) fs i/o: OK check_bc: OK check_super: OK check_bitmap: OK alloc_block: OK file_open: OK file_get_block: OK file_flush/file_truncate/file rewrite: OK testfile: OK (1.6s) serve_open/file_stat/file_close: OK file_read: OK file_write: OK file_read after file_write: OK open: OK large file: OK spawn via spawnhello: OK (1.8s) Protection I/O space: OK (1.6s) PTE_SHARE [testpteshare]: OK (0.9s) PTE_SHARE [testfdsharing]: OK (1.4s) start the shell [icode]: Timeout! OK (31.5s) testshell: OK (2.4s) (Old jos.out.testshell failure log removed) primespipe: OK (7.2s) Score: 150/150
A monopole magnet is a magnet that only has one pole, either north or south. They don’t actually exist since real magnets have two poles, but this is a programming contest problem, so we don’t care.
There is an n×m grid. Initially, you may place some north magnets and some south magnets into the cells. You are allowed to place as many magnets as you like, even multiple in the same cell.
An operation is performed as follows. Choose a north magnet and a south magnet to activate. If they are in the same row or the same column and they occupy different cells, then the north magnet moves one unit closer to the south magnet. Otherwise, if they occupy the same cell or do not share a row or column, then nothing changes. Note that the south magnets are immovable.
Each cell of the grid is colored black or white. Let’s consider ways to place magnets in the cells so that the following conditions are met.
There is at least one south magnet in every row and every column.
If a cell is colored black, then it is possible for a north magnet to occupy this cell after some sequence of operations from the initial placement.
If a cell is colored white, then it is impossible for a north magnet to occupy this cell after some sequence of operations from the initial placement.
Determine if it is possible to place magnets such that these conditions are met. If it is possible, find the minimum number of north magnets required (there are no requirements on the number of south magnets).
Input
The first line contains two integers n and m (1≤n,m≤1000) — the number of rows and the number of columns, respectively.
The next n lines describe the coloring. The i-th of these lines contains a string of length m, where the j-th character denotes the color of the cell in row i and column j. The characters “#” and “.” represent black and white, respectively. It is guaranteed, that the string will not contain any other characters.
Output
Output a single integer, the minimum possible number of north magnets required.
If there is no placement of magnets that satisfies all conditions, print a single integer −1.
Examples
input
1 2 3 4
3 3 .#. ### ##.
output
1
1
input
1 2 3 4 5
4 2 ## .# .# ##
output
1
-1
input
1 2 3 4 5
4 5 ....# ####. .###. .#...
output
1
2
input
1 2 3
2 1 . #
output
1
-1
input
1 2 3 4
3 5 ..... ..... .....
output
1
0
Note
In the first test, here is an example placement of magnets:
In the second test, we can show that no required placement of magnets exists. Here are three example placements that fail to meet the requirements. The first example violates rule 3 since we can move the north magnet down onto a white square. The second example violates rule 2 since we cannot move the north magnet to the bottom-left black square by any sequence of operations. The third example violates rule 1 since there is no south magnet in the first column.
In the third test, here is an example placement of magnets. We can show that there is no required placement of magnets with fewer north magnets.
In the fourth test, we can show that no required placement of magnets exists. Here are two example placements that fail to meet the requirements. The first example violates rule 1 since there is no south magnet in the first row. The second example violates rules 1 and 3 since there is no south magnet in the second row and we can move the north magnet up one unit onto a white square.
In the fifth test, we can put the south magnet in each cell and no north magnets. Because there are no black cells, it will be a correct placement.
Calculate the number of ways to place n rooks on n×n chessboard so that both following conditions are met:
each empty cell is under attack;
exactly k pairs of rooks attack each other.
An empty cell is under attack if there is at least one rook in the same row or at least one rook in the same column. Two rooks attack each other if they share the same row or column, and there are no other rooks between them. For example, there are only two pairs of rooks that attack each other in the following picture:
One of the ways to place the rooks for n=3 and k=2
Two ways to place the rooks are considered different if there exists at least one cell which is empty in one of the ways but contains a rook in another way.
The answer might be large, so print it modulo 998244353.
Input
The only line of the input contains two integers n and k (1≤n≤200000; 0≤k≤2n(n−1)).
Output
Print one integer — the number of ways to place the rooks, taken modulo 998244353.
// // Reserve size bytes in the MMIO region and map [pa,pa+size) at this // location. Return the base of the reserved region. size does *not* // have to be multiple of PGSIZE. // void * mmio_map_region(physaddr_t pa, size_t size) { // Where to start the next region. Initially, this is the // beginning of the MMIO region. Because this is static, its // value will be preserved between calls to mmio_map_region // (just like nextfree in boot_alloc). staticuintptr_t base = MMIOBASE;
uintptr_t result;
// Reserve size bytes of virtual memory starting at base and // map physical pages [pa,pa+size) to virtual addresses // [base,base+size). Since this is device memory and not // regular DRAM, you'll have to tell the CPU that it isn't // safe to cache access to this memory. Luckily, the page // tables provide bits for this purpose; simply create the // mapping with PTE_PCD|PTE_PWT (cache-disable and // write-through) in addition to PTE_W. (If you're interested // in more details on this, see section 10.5 of IA32 volume // 3A.) // // Be sure to round size up to a multiple of PGSIZE and to // handle if this reservation would overflow MMIOLIM (it's // okay to simply panic if this happens). // // Hint: The staff solution uses boot_map_region. // // Your code here: if(base + ROUNDUP(size, PGSIZE) >= MMIOLIM) panic("mmio_map_region: out of memory\n"); boot_map_region(kern_pgdir, base, size, pa, PTE_PCD | PTE_PWT | PTE_W); result = base; base += ROUNDUP(size, PGSIZE); return (void *)result; }
Exercise 2
修改page_init()的内容如下，只是增加一个特殊处理：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// case 1: pages[0].pp_ref = 1; pages[0].pp_link = NULL; // case 2, 3, 4: for (i = 1; i < npages; i++) { if((IOPHYSMEM <= i * PGSIZE && i * PGSIZE < pa_free_start) || page2pa(pages + i) == MPENTRY_PADDR) { pages[i].pp_ref = 1; pages[i].pp_link = NULL; } else { pages[i].pp_ref = 0; pages[i].pp_link = page_free_list; page_free_list = &pages[i]; } }
// Modify mappings in kern_pgdir to support SMP // - Map the per-CPU stacks in the region [KSTACKTOP-PTSIZE, KSTACKTOP) // staticvoid mem_init_mp(void) { // Map per-CPU stacks starting at KSTACKTOP, for up to 'NCPU' CPUs. // // For CPU i, use the physical memory that 'percpu_kstacks[i]' refers // to as its kernel stack. CPU i's kernel stack grows down from virtual // address kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP), and is // divided into two pieces, just like the single stack you set up in // mem_init: // * [kstacktop_i - KSTKSIZE, kstacktop_i) // -- backed by physical memory // * [kstacktop_i - (KSTKSIZE + KSTKGAP), kstacktop_i - KSTKSIZE) // -- not backed; so if the kernel overflows its stack, // it will fault rather than overwrite another CPU's stack. // Known as a "guard page". // Permissions: kernel RW, user NONE // // LAB 4: Your code here: uint32_t i, kstacktop_i; for(i=0, kstacktop_i=KSTACKTOP;i < NCPU; ++i, kstacktop_i -= KSTKSIZE + KSTKGAP) boot_map_region(kern_pgdir, kstacktop_i - KSTKSIZE, KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_W); }
// Initialize and load the per-CPU TSS and IDT void trap_init_percpu(void) { // The example code here sets up the Task State Segment (TSS) and // the TSS descriptor for CPU 0. But it is incorrect if we are // running on other CPUs because each CPU has its own kernel stack. // Fix the code so that it works for all CPUs. // // Hints: // - The macro "thiscpu" always refers to the current CPU's // struct CpuInfo; // - The ID of the current CPU is given by cpunum() or // thiscpu->cpu_id; // - Use "thiscpu->cpu_ts" as the TSS for the current CPU, // rather than the global "ts" variable; // - Use gdt[(GD_TSS0 >> 3) + i] for CPU i's TSS descriptor; // - You mapped the per-CPU kernel stacks in mem_init_mp() // - Initialize cpu_ts.ts_iomb to prevent unauthorized environments // from doing IO (0 is not the correct value!) // // ltr sets a 'busy' flag in the TSS selector, so if you // accidentally load the same TSS on more than one CPU, you'll // get a triple fault. If you set up an individual CPU's TSS // wrong, you may not get a fault until you try to return from // user space on that CPU. // // LAB 4: Your code here:
// Setup a TSS so that we get the right stack // when we trap to the kernel. thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - cpunum() * (KSTKSIZE + KSTKGAP); thiscpu->cpu_ts.ts_ss0 = GD_KD; thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);
// Initialize the TSS slot of the gdt. gdt[(GD_TSS0 >> 3) + cpunum()] = SEG16(STS_T32A, (uint32_t) (&(thiscpu->cpu_ts)), sizeof(struct Taskstate) - 1, 0); gdt[(GD_TSS0 >> 3) + cpunum()].sd_s = 0;
// Load the TSS selector (like other segment selectors, the // bottom three bits are special; we leave them 0) ltr(GD_TSS0 + (cpunum() << 3));
In i386_init(), acquire the lock before the BSP wakes up the other CPUs.
1 2 3 4 5 6
// Acquire the big kernel lock before waking up APs // Your code here: lock_kernel(); // Starting non-boot CPUs boot_aps();
In mp_main(), acquire the lock after initializing the AP, and then call sched_yield() to start running environments on this AP.
1 2 3 4 5 6 7
// Now that we have finished some basic setup, call sched_yield() // to start running processes on this CPU. But make sure that // only one CPU can enter the scheduler at a time! // // Your code here: lock_kernel(); sched_yield();
In trap(), acquire the lock when trapped from user mode. To determine whether a trap happened in user mode or in kernel mode, check the low bits of the tf_cs.
1 2 3 4 5 6
// Trapped from user mode. // Acquire the big kernel lock before doing any // serious kernel work. // LAB 4: Your code here. lock_kernel(); assert(curenv);
In env_run(), release the lock right before switching to user mode. Do not do that too early or too late, otherwise you will experience races or deadlocks.
// Choose a user environment to run and run it. void sched_yield(void) { structEnv *idle;
// Implement simple round-robin scheduling. // // Search through 'envs' for an ENV_RUNNABLE environment in // circular fashion starting just after the env this CPU was // last running. Switch to the first such environment found. // // If no envs are runnable, but the environment previously // running on this CPU is still ENV_RUNNING, it's okay to // choose that environment. // // Never choose an environment that's currently running on // another CPU (env_status == ENV_RUNNING). If there are // no runnable environments, simply drop through to the code // below to halt the cpu.
// Setup code for APs void mp_main(void) { // We are in high EIP now, safe to switch to kern_pgdir lcr3(PADDR(kern_pgdir)); cprintf("SMP: CPU %d starting\n", cpunum());
lapic_init(); env_init_percpu(); trap_init_percpu(); xchg(&thiscpu->cpu_status, CPU_STARTED); // tell boot_aps() we're up
// Now that we have finished some basic setup, call sched_yield() // to start running processes on this CPU. But make sure that // only one CPU can enter the scheduler at a time! // // Your code here: lock_kernel(); sched_yield();
// Remove this after you finish Exercise 6 for (;;); }
// Allocate a new environment. // Returns envid of new environment, or < 0 on error. Errors are: // -E_NO_FREE_ENV if no free environment is available. // -E_NO_MEM on memory exhaustion. staticenvid_t sys_exofork(void) { // Create the new environment with env_alloc(), from kern/env.c. // It should be left as env_alloc created it, except that // status is set to ENV_NOT_RUNNABLE, and the register set is copied // from the current environment -- but tweaked so sys_exofork // will appear to return 0.
// Set envid's env_status to status, which must be ENV_RUNNABLE // or ENV_NOT_RUNNABLE. // // Returns 0 on success, < 0 on error. Errors are: // -E_BAD_ENV if environment envid doesn't currently exist, // or the caller doesn't have permission to change envid. // -E_INVAL if status is not a valid status for an environment. staticint sys_env_set_status(envid_t envid, int status) { // Hint: Use the 'envid2env' function from kern/env.c to translate an // envid to a struct Env. // You should set envid2env's third argument to 1, which will // check whether the current environment has permission to set // envid's status.
// Allocate a page of memory and map it at 'va' with permission // 'perm' in the address space of 'envid'. // The page's contents are set to 0. // If a page is already mapped at 'va', that page is unmapped as a // side effect. // // perm -- PTE_U | PTE_P must be set, PTE_AVAIL | PTE_W may or may not be set, // but no other bits may be set. See PTE_SYSCALL in inc/mmu.h. // // Return 0 on success, < 0 on error. Errors are: // -E_BAD_ENV if environment envid doesn't currently exist, // or the caller doesn't have permission to change envid. // -E_INVAL if va >= UTOP, or va is not page-aligned. // -E_INVAL if perm is inappropriate (see above). // -E_NO_MEM if there's no memory to allocate the new page, // or to allocate any necessary page tables. staticint sys_page_alloc(envid_t envid, void *va, int perm) { // Hint: This function is a wrapper around page_alloc() and // page_insert() from kern/pmap.c. // Most of the new code you write should be to check the // parameters for correctness. // If page_insert() fails, remember to free the page you // allocated!
// Map the page of memory at 'srcva' in srcenvid's address space // at 'dstva' in dstenvid's address space with permission 'perm'. // Perm has the same restrictions as in sys_page_alloc, except // that it also must not grant write access to a read-only // page. // // Return 0 on success, < 0 on error. Errors are: // -E_BAD_ENV if srcenvid and/or dstenvid doesn't currently exist, // or the caller doesn't have permission to change one of them. // -E_INVAL if srcva >= UTOP or srcva is not page-aligned, // or dstva >= UTOP or dstva is not page-aligned. // -E_INVAL is srcva is not mapped in srcenvid's address space. // -E_INVAL if perm is inappropriate (see sys_page_alloc). // -E_INVAL if (perm & PTE_W), but srcva is read-only in srcenvid's // address space. // -E_NO_MEM if there's no memory to allocate any necessary page tables. staticint sys_page_map(envid_t srcenvid, void *srcva, envid_t dstenvid, void *dstva, int perm) { // Hint: This function is a wrapper around page_lookup() and // page_insert() from kern/pmap.c. // Again, most of the new code you write should be to check the // parameters for correctness. // Use the third argument to page_lookup() to // check the current permissions on the page.
// Unmap the page of memory at 'va' in the address space of 'envid'. // If no page is mapped, the function silently succeeds. // // Return 0 on success, < 0 on error. Errors are: // -E_BAD_ENV if environment envid doesn't currently exist, // or the caller doesn't have permission to change envid. // -E_INVAL if va >= UTOP, or va is not page-aligned. staticint sys_page_unmap(envid_t envid, void *va) { // Hint: This function is a wrapper around page_remove().
// Set the page fault upcall for 'envid' by modifying the corresponding struct // Env's 'env_pgfault_upcall' field. When 'envid' causes a page fault, the // kernel will push a fault record onto the exception stack, then branch to // 'func'. // // Returns 0 on success, < 0 on error. Errors are: // -E_BAD_ENV if environment envid doesn't currently exist, // or the caller doesn't have permission to change envid. staticint sys_env_set_pgfault_upcall(envid_t envid, void *func) { // LAB 4: Your code here. structEnv* env; if(envid2env(envid, &env, 1)) return -E_BAD_ENV; env->env_pgfault_upcall = func; return0; //panic("sys_env_set_pgfault_upcall not implemented"); }
// Restore the trap-time registers. After you do this, you // can no longer modify any general-purpose registers. // LAB 4: Your code here. addl $8, %esp popal
// Restore eflags from the stack. After you do this, you can // no longer use arithmetic operations or anything else that // modifies eflags. // LAB 4: Your code here. addl $4, %esp popfl
// Switch back to the adjusted trap-time stack. // LAB 4: Your code here. popl %esp
// Return to re-execute the instruction that faulted. // LAB 4: Your code here. ret
// // Set the page fault handler function. // If there isn't one yet, _pgfault_handler will be 0. // The first time we register a handler, we need to // allocate an exception stack (one page of memory with its top // at UXSTACKTOP), and tell the kernel to call the assembly-language // _pgfault_upcall routine when a page fault occurs. // void set_pgfault_handler(void (*handler)(struct UTrapframe *utf)) { int r;
if (_pgfault_handler == 0) { // First time through! // LAB 4: Your code here. if(sys_page_alloc(0, (void *)(UXSTACKTOP - PGSIZE), PTE_U | PTE_P | PTE_W)) panic("set_pgfault_handler: page alloc fault!"); if(sys_env_set_pgfault_upcall(0, (void *)_pgfault_upcall)) panic("set_pgfault handler: set pgfault upcall failed!"); } // Save handler pointer for assembly to call. _pgfault_handler = handler; }
// // Custom page fault handler - if faulting page is copy-on-write, // map in our own private writable copy. // staticvoid pgfault(struct UTrapframe *utf) { void *addr = (void *) utf->utf_fault_va; uint32_t err = utf->utf_err; int r;
// Check that the faulting access was (1) a write, and (2) to a // copy-on-write page. If not, panic. // Hint: // Use the read-only page table mappings at uvpt // (see <inc/memlayout.h>).
// LAB 4: Your code here. if(!((err & FEC_WR) && (uvpt[PGNUM(addr)] & PTE_COW))) panic("pgfault: 0x%08x the fault page is not writable or copy-on-write page!", addr);
// Allocate a new page, map it at a temporary location (PFTEMP), // copy the data from the old page to the new page, then move the new // page to the old page's address. // Hint: // You should make three system calls.
// // Map our virtual page pn (address pn*PGSIZE) into the target envid // at the same virtual address. If the page is writable or copy-on-write, // the new mapping must be created copy-on-write, and then our mapping must be // marked copy-on-write as well. (Exercise: Why do we need to mark ours // copy-on-write again if it was already copy-on-write at the beginning of // this function?) // // Returns: 0 on success, < 0 on error. // It is also OK to panic on error. // staticint duppage(envid_t envid, unsigned pn) { int r;
// // User-level fork with copy-on-write. // Set up our page fault handler appropriately. // Create a child. // Copy our address space and page fault handler setup to the child. // Then mark the child as runnable and return. // // Returns: child's envid to the parent, 0 to the child, < 0 on error. // It is also OK to panic on error. // // Hint: // Use uvpd, uvpt, and duppage. // Remember to fix "thisenv" in the child process. // Neither user exception stack should ever be marked copy-on-write, // so you must allocate a new page for the child's user exception stack. // envid_t fork(void) { // LAB 4: Your code here. int r; envid_t envid; uint8_t * addr; set_pgfault_handler(pgfault); envid = sys_exofork(); if(envid < 0) panic("fork: sys_exofork failed!"); if(envid == 0){ thisenv = &envs[ENVX(sys_getenvid())]; return0; }
// Block until a value is ready. Record that you want to receive // using the env_ipc_recving and env_ipc_dstva fields of struct Env, // mark yourself not runnable, and then give up the CPU. // // If 'dstva' is < UTOP, then you are willing to receive a page of data. // 'dstva' is the virtual address at which the sent page should be mapped. // // This function only returns on error, but the system call will eventually // return 0 on success. // Return < 0 on error. Errors are: // -E_INVAL if dstva < UTOP but dstva is not page-aligned. staticint sys_ipc_recv(void *dstva) { // LAB 4: Your code here. structEnv * env; if(envid2env(0, &env, 0)) return -E_BAD_ENV; if((uint32_t)dstva < UTOP && (dstva != ROUNDDOWN(dstva, PGSIZE))) return -E_INVAL;
// Try to send 'value' to the target env 'envid'. // If srcva < UTOP, then also send page currently mapped at 'srcva', // so that receiver gets a duplicate mapping of the same page. // // The send fails with a return value of -E_IPC_NOT_RECV if the // target is not blocked, waiting for an IPC. // // The send also can fail for the other reasons listed below. // // Otherwise, the send succeeds, and the target's ipc fields are // updated as follows: // env_ipc_recving is set to 0 to block future sends; // env_ipc_from is set to the sending envid; // env_ipc_value is set to the 'value' parameter; // env_ipc_perm is set to 'perm' if a page was transferred, 0 otherwise. // The target environment is marked runnable again, returning 0 // from the paused sys_ipc_recv system call. (Hint: does the // sys_ipc_recv function ever actually return?) // // If the sender wants to send a page but the receiver isn't asking for one, // then no page mapping is transferred, but no error occurs. // The ipc only happens when no errors occur. // // Returns 0 on success, < 0 on error. // Errors are: // -E_BAD_ENV if environment envid doesn't currently exist. // (No need to check permissions.) // -E_IPC_NOT_RECV if envid is not currently blocked in sys_ipc_recv, // or another environment managed to send first. // -E_INVAL if srcva < UTOP but srcva is not page-aligned. // -E_INVAL if srcva < UTOP and perm is inappropriate // (see sys_page_alloc). // -E_INVAL if srcva < UTOP but srcva is not mapped in the caller's // address space. // -E_INVAL if (perm & PTE_W), but srcva is read-only in the // current environment's address space. // -E_NO_MEM if there's not enough memory to map srcva in envid's // address space. staticint sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm) { // LAB 4: Your code here. structEnv* dstenv, * srcenv; if(envid2env(envid, &dstenv, 0) || envid2env(0, &srcenv, 0)) return -E_BAD_ENV; if(!dstenv->env_ipc_recving) return -E_IPC_NOT_RECV;
// Receive a value via IPC and return it. // If 'pg' is nonnull, then any page sent by the sender will be mapped at // that address. // If 'from_env_store' is nonnull, then store the IPC sender's envid in // *from_env_store. // If 'perm_store' is nonnull, then store the IPC sender's page permission // in *perm_store (this is nonzero iff a page was successfully // transferred to 'pg'). // If the system call fails, then store 0 in *fromenv and *perm (if // they're nonnull) and return the error. // Otherwise, return the value sent by the sender // // Hint: // Use 'thisenv' to discover the value and who sent it. // If 'pg' is null, pass sys_ipc_recv a value that it will understand // as meaning "no page". (Zero is not the right value, since that's // a perfectly valid place to map a page.) int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store) { // LAB 4: Your code here. int r;
// Send 'val' (and 'pg' with 'perm', if 'pg' is nonnull) to 'toenv'. // This function keeps trying until it succeeds. // It should panic() on any error other than -E_IPC_NOT_RECV. // // Hint: // Use sys_yield() to be CPU-friendly. // If 'pg' is null, pass sys_ipc_try_send a value that it will understand // as meaning "no page". (Zero is not the right value.) void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm) { // LAB 4: Your code here. int r; do{ sys_yield(); r = sys_ipc_try_send(to_env, val, pg ? pg : (void *)UTOP, perm); if(r != 0 && r != -E_IPC_NOT_RECV) panic("ipc_send: faild, %e", r); }while(r); }
实现完了之后lab4的基础内容就已经结束了，执行make grade可以得到如下的输出：
1 2 3 4 5 6 7 8 9 10 11
spin: OK (1.8s) stresssched: OK (3.2s) sendpage: OK (0.9s) (Old jos.out.sendpage failure log removed) pingpong: OK (1.9s) (Old jos.out.pingpong failure log removed) primes: OK (9.1s) (Old jos.out.primes failure log removed) Part C score: 25/25
enabled interrupts: 1 2 [00000000] new env 00001000 [00001000] new env 00001001 i am 00001000; thisenv is 0xeec00000 send 0 from 1000 to 1001 1001 got 0 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 1 from 1001 (thisenv is 0xeec00000 1000) 1001 got 2 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 3 from 1001 (thisenv is 0xeec00000 1000) 1001 got 4 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 5 from 1001 (thisenv is 0xeec00000 1000) 1001 got 6 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 7 from 1001 (thisenv is 0xeec00000 1000) 1001 got 8 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 9 from 1001 (thisenv is 0xeec00000 1000) [00001000] exiting gracefully [00001000] free env 00001000 1001 got 10 from 1000 (thisenv is 0xeec0007c 1001) [00001001] exiting gracefully [00001001] free env 00001001
可以发现实际上两个进程确实是共享了地址空间，并且thisenv能够正确的指向进程自身了。
如果将其中的sfork()修改成fork()的话，得到的输出如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
enabled interrupts: 1 2 [00000000] new env 00001000 [00001000] new env 00001001 i am 00001000; thisenv is 0xeec00000 send 0 from 1000 to 1001 1001 got 0 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 0 from 1001 (thisenv is 0xeec00000 1000) 1001 got 1 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 1 from 1001 (thisenv is 0xeec00000 1000) 1001 got 2 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 2 from 1001 (thisenv is 0xeec00000 1000) 1001 got 3 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 3 from 1001 (thisenv is 0xeec00000 1000) 1001 got 4 from 1000 (thisenv is 0xeec0007c 1001) 1000 got 4 from 1001 (thisenv is 0xeec00000 1000) ...
Denis came to Nastya and discovered that she was not happy to see him… There is only one chance that she can become happy. Denis wants to buy all things that Nastya likes so she will certainly agree to talk to him.
The map of the city where they live has a lot of squares, some of which are connected by roads. There is exactly one way between each pair of squares which does not visit any vertex twice. It turns out that the graph of the city is a tree.
Denis is located at vertex 1 at the time 0. He wants to visit every vertex at least once and get back as soon as possible.
Denis can walk one road in 1 time. Unfortunately, the city is so large that it will take a very long time to visit all squares. Therefore, Denis took a desperate step. He pulled out his pocket time machine, which he constructed in his basement. With its help, Denis can change the time to any non-negative time, which is less than the current time.
But the time machine has one feature. If the hero finds himself in the same place and at the same time twice, there will be an explosion of universal proportions and Nastya will stay unhappy. Therefore, Denis asks you to find him a route using a time machine that he will get around all squares and will return to the first and at the same time the maximum time in which he visited any square will be minimal.
Formally, Denis’s route can be represented as a sequence of pairs:{v1,t1},{v2,t2},{v3,t3},…,{vk,tk}, where vi is number of square, and ti is time in which the boy is now.
The following conditions must be met:
The route starts on square 1 at time 0, i.e. v1=1,t1=0 and ends on the square 1, i.e. vk=1.
All transitions are divided into two types:
Being in the square change the time: {vi,ti}→{vi+1,ti+1}:vi+1=vi,0≤ti+1<ti.
Walk along one of the roads: {vi,ti}→{vi+1,ti+1}. Herewith, vi and vi+1 are connected by road, and ti+1=ti+1
All pairs {vi,ti} must be different.
All squares are among v1,v2,…,vk.
You need to find a route such that the maximum time in any square will be minimal, that is, the route for which max(t1,t2,…,tk) will be the minimum possible.
Input
The first line contains a single integer n(1≤n≤105) — the number of squares in the city.
The next n−1 lines contain two integers u and v(1≤v,u≤n,u≠v) - the numbers of the squares connected by the road.
It is guaranteed that the given graph is a tree.
Output
In the first line output the integer k(1≤k≤106) — the length of the path of Denis.
In the next k lines output pairs vi,ti — pairs that describe Denis’s route (as in the statement).
All route requirements described in the statements must be met.
It is guaranteed that under given restrictions there is at least one route and an answer whose length does not exceed 106. If there are several possible answers, print any.
If the girl doesn’t go to Denis, then Denis will go to the girl. Using this rule, the young man left home, bought flowers and went to Nastya.
On the way from Denis’s house to the girl’s house is a road of n lines. This road can’t be always crossed in one green light. Foreseeing this, the good mayor decided to place safety islands in some parts of the road. Each safety island is located after a line, as well as at the beginning and at the end of the road. Pedestrians can relax on them, gain strength and wait for a green light.
Denis came to the edge of the road exactly at the moment when the green light turned on. The boy knows that the traffic light first lights up g seconds green, and then r seconds red, then again g seconds green and so on.
Formally, the road can be represented as a segment [0,n]. Initially, Denis is at point 0. His task is to get to point n in the shortest possible time.
He knows many different integers d1,d2,…,dm, where 0≤di≤n — are the coordinates of points, in which the safety islands are located. Only at one of these points, the boy can be at a time when the red light is on.
Unfortunately, Denis isn’t always able to control himself because of the excitement, so some restrictions are imposed:
He must always move while the green light is on because it’s difficult to stand when so beautiful girl is waiting for you. Denis can change his position by ±1 in 11 second. While doing so, he must always stay inside the segment [0,n]
He can change his direction only on the safety islands (because it is safe). This means that if in the previous second the boy changed his position by +1 and he walked on a safety island, then he can change his position by ±1. Otherwise, he can change his position only by +1. Similarly, if in the previous second he changed his position by −1, on a safety island he can change position by ±1, and at any other point by −1.
At the moment when the red light is on, the boy must be on one of the safety islands. He can continue moving in any direction when the green light is on.
Denis has crossed the road as soon as his coordinate becomes equal to n.
This task was not so simple, because it’s possible that it is impossible to cross the road. Since Denis has all thoughts about his love, he couldn’t solve this problem and asked us to help him. Find the minimal possible time for which he can cross the road according to these rules, or find that it is impossible to do.
Input
The first line contains two integers n and m, (1≤n≤106,2≤m≤min(n+1,104)) — road width and the number of safety islands.
The second line contains m distinct integers d1,d2,…,dm(0≤di≤n) — the points where the safety islands are located. It is guaranteed that there are 0 and n among them.
The third line contains two integers g,r(1≤g,r≤1000) — the time that the green light stays on and the time that the red light stays on.
Output
Output a single integer — the minimum time for which Denis can cross the road with obeying all the rules.
If it is impossible to cross the road output −1.
Examples
input
1 2 3
15 5 0 3 7 14 15 11 11
output
1
45
input
1 2 3
13 4 0 3 7 13 9 9
output
1
-1
Note
In the first test, the optimal route is:
for the first green light, go to 7 and return to 3. In this case, we will change the direction of movement at the point 7, which is allowed, since there is a safety island at this point. In the end, we will be at the point of 3, where there is also a safety island. The next 11 seconds we have to wait for the red light.
for the second green light reaches 14. Wait for the red light again.
for 11 second go to 15. As a result, Denis is at the end of the road.
In total, 45 seconds are obtained.
In the second test, it is impossible to cross the road according to all the rules.
// Make 'envs' point to an array of size 'NENV' of 'struct Env'. // LAB 3: Your code here. envs = (struct Env *) boot_alloc(sizeof(struct Env) * NENV);
同时采用相似的方法将其map到UENVS处：
1 2 3 4 5 6 7 8 9
// Map the 'envs' array read-only by the user at linear address UENVS // (ie. perm = PTE_U | PTE_P). // Permissions: // - the new image at UENVS -- kernel R, user R // - envs itself -- kernel RW, user NONE // LAB 3: Your code here. n = ROUNDUP(NENV*sizeof(struct Env), PGSIZE); for (i = 0; i < n; i+=PGSIZE) page_insert(kern_pgdir, pa2page(PADDR(envs) + i), (void *)(UENVS + i), PTE_U | PTE_P);
// Mark all environments in 'envs' as free, set their env_ids to 0, // and insert them into the env_free_list. // Make sure the environments are in the free list in the same order // they are in the envs array (i.e., so that the first call to // env_alloc() returns envs[0]). // void env_init(void) { // Set up envs array // LAB 3: Your code here. memset(envs, 0, sizeof(struct Env) * NENV); int i; env_free_list = envs; for(i = 1; i < NENV; ++i) envs[i-1].env_link = envs + i;
// Per-CPU part of the initialization env_init_percpu(); }
// // Initialize the kernel virtual memory layout for environment e. // Allocate a page directory, set e->env_pgdir 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. // staticint env_setup_vm(struct Env *e) { int i; structPageInfo *p =NULL;
// Allocate a page for the page directory if (!(p = page_alloc(ALLOC_ZERO))) return -E_NO_MEM;
// Now, set e->env_pgdir and initialize the page directory. // // Hint: // - The VA space of all envs is identical above UTOP // (except at UVPT, which we've set below). // See inc/memlayout.h for permissions and layout. // Can you use kern_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: In general, pp_ref is not maintained for // physical pages mapped only above UTOP, but env_pgdir // is an exception -- you need to increment env_pgdir's // pp_ref for env_free to work correctly. // - The functions in kern/pmap.h are handy.
// // 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. // staticvoid region_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 region_alloc if the caller can pass // 'va' and 'len' values that are not page-aligned. // You should round va down, and round (va + len) up. // (Watch out for corner-cases!) void *start_va = ROUNDDOWN(va, PGSIZE); void *end_va = ROUNDUP(va + len, PGSIZE); void *cur_va; for(cur_va = start_va; cur_va < end_va; cur_va += PGSIZE) { structPageInfo * pp = page_alloc(0); if(!pp) panic("region_alloc: Out of memory!\n"); page_insert(e->env_pgdir, pp, (void *)cur_va, PTE_U | PTE_W); } }
// read 1st page off disk readseg((uint32_t) ELFHDR, SECTSIZE*8, 0);
// is this a valid ELF? if (ELFHDR->e_magic != ELF_MAGIC) goto bad;
// load each program segment (ignores ph flags) ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff); eph = ph + ELFHDR->e_phnum; for (; ph < eph; ph++) // p_pa is the load address of this segment (as well // as the physical address) readseg(ph->p_pa, ph->p_memsz, ph->p_offset);
// call the entry point from the ELF header // note: does not return! ((void (*)(void)) (ELFHDR->e_entry))();
bad: outw(0x8A00, 0x8A00); outw(0x8A00, 0x8E00); while (1) /* do nothing */; }
// // 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? // staticvoid load_icode(struct Env *e, uint8_t *binary) { // Hints: // Load each program segment into virtual memory // at the address specified in the ELF segment 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 region_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? // // 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.)
// // Allocates a new env with env_alloc, loads the named elf // binary into it with load_icode, and sets its env_type. // 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. // void env_create(uint8_t *binary, enum EnvType type) { // LAB 3: Your code here. structEnv * e; if(env_alloc(&e, 0)) panic("env_create: env alloc failed!\n"); load_icode(e, binary); e->env_type = type; }
// // 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): // 1. Set the current environment (if any) back to // ENV_RUNNABLE if it is ENV_RUNNING (think about // what other states it can be in), // 2. Set 'curenv' to the new environment, // 3. Set its status to ENV_RUNNING, // 4. Update its 'env_runs' counter, // 5. 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.
(gdb) b *0x800a33 Breakpoint 2 at 0x800a33 (gdb) c Continuing. => 0x800a33: int $0x30
Breakpoint 2, 0x00800a33 in ?? ()
发现确实执行到了这一条指令，以上的实现应该是没有问题。
Exercise 3
内容为阅读Chapter 9，是关于Exceptions和Interrupts的内容。
Exercise 4
从inc/trap.h当中可以发现，TrapFrame有着如下的结构：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
structTrapframe { structPushRegstf_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; } __attribute__((packed));
Divide error 0 No Debug exceptions 1 No Breakpoint 3 No Overflow 4 No Bounds check 5 No Invalid opcode 6 No Coprocessor not available 7 No System error 8 Yes (always 0) Coprocessor Segment Overrun 9 No Invalid TSS 10 Yes Segment not present 11 Yes Stack exception 12 Yes General protection fault 13 Yes Page fault 14 Yes Coprocessor error 16 No Two-byte SW interrupt 0-255 No
// Set up a normal interrupt/trap gate descriptor. // - istrap: 1 for a trap (= exception) gate, 0 for an interrupt gate. // see section 9.6.1.3 of the i386 reference: "The difference between // an interrupt gate and a trap gate is in the effect on IF (the // interrupt-enable flag). An interrupt that vectors through an // interrupt gate resets IF, thereby preventing other interrupts from // interfering with the current interrupt handler. A subsequent IRET // instruction restores IF to the value in the EFLAGS image on the // stack. An interrupt through a trap gate does not change IF." // - sel: Code segment selector for interrupt/trap handler // - off: Offset in code segment for interrupt/trap handler // - dpl: Descriptor Privilege Level - // the privilege level required for software to invoke // this interrupt/trap gate explicitly using an int instruction. #define SETGATE(gate, istrap, sel, off, dpl) \ { \ (gate).gd_off_15_0 = (uint32_t) (off) & 0xffff; \ (gate).gd_sel = (sel); \ (gate).gd_args = 0; \ (gate).gd_rsv1 = 0; \ (gate).gd_type = (istrap) ? STS_TG32 : STS_IG32; \ (gate).gd_s = 0; \ (gate).gd_dpl = (dpl); \ (gate).gd_p = 1; \ (gate).gd_off_31_16 = (uint32_t) (off) >> 16; \ }
// Dispatches to the correct kernel function, passing the arguments. int32_t syscall(uint32_t syscallno, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5) { // Call the function corresponding to the 'syscallno' parameter. // Return any appropriate return value. // LAB 3: Your code here.
//panic("syscall not implemented");
switch (syscallno) { case SYS_cputs: sys_cputs((constchar *)a1, (size_t)a2); return0;
case SYS_cgetc: return sys_cgetc();
case SYS_getenvid: return sys_getenvid();
case SYS_env_destroy: return sys_env_destroy((envid_t)a1);
case NSYSCALLS: return0;
default: return -E_INVAL; } }
Exercise 8
在lib/libmain.c当中，进行env_id的指定：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
void libmain(int argc, char **argv) { // set thisenv to point at our Env structure in envs[]. // LAB 3: Your code here. envid_t envid = sys_getenvid(); thisenv = &envs[ENVX(envid)];
// save the name of the program so that panic() can use it if (argc > 0) binaryname = argv[0];
// // Check that an environment is allowed to access the range of memory // [va, va+len) with permissions 'perm | PTE_P'. // Normally 'perm' will contain PTE_U at least, but this is not required. // 'va' and 'len' need not be page-aligned; you must test every page that // contains any of that range. You will test either 'len/PGSIZE', // 'len/PGSIZE + 1', or 'len/PGSIZE + 2' pages. // // A user program can access a virtual address if (1) the address is below // ULIM, and (2) the page table gives it permission. These are exactly // the tests you should implement here. // // If there is an error, set the 'user_mem_check_addr' variable to the first // erroneous virtual address. // // Returns 0 if the user program can access this range of addresses, // and -E_FAULT otherwise. // int user_mem_check(struct Env *env, constvoid *va, size_t len, int perm) { // LAB 3: Your code here. int newperm = perm | PTE_P; uint32_t cur_addr; pte_t * pte; for(cur_addr = (uint32_t)va; cur_addr < (uint32_t)(va + len); cur_addr = ROUNDDOWN((cur_addr+PGSIZE),PGSIZE)) { if(cur_addr >= ULIM) { user_mem_check_addr = cur_addr; return -E_FAULT; } pte = pgdir_walk(env->env_pgdir, (void *)cur_addr, 0); if((!pte) || ((*pte) & newperm) != newperm){ user_mem_check_addr = cur_addr; return -E_FAULT; } } return0; }
需要注意的是要在kern/syscall.c当中需要填充上有关检查的部分！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// Print a string to the system console. // The string is exactly 'len' characters long. // Destroys the environment on memory errors. staticvoid sys_cputs(constchar *s, size_t len) { // Check that the user has permission to read memory [s, s+len). // Destroy the environment if not.
// LAB 3: Your code here. user_mem_assert(curenv, s, len, PTE_W);
// Print the string supplied by the user. cprintf("%.*s", len, s); }
else { // The user-application linker script, user/user.ld, // puts information about the application's stabs (equivalent // to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and // __STABSTR_END__) in a structure located at virtual address // USTABDATA. conststruct UserStabData *usd = (conststruct UserStabData *) USTABDATA;
// Make sure this memory is valid. // Return -1 if it is not. Hint: Call user_mem_check. // LAB 3: Your code here. if(user_mem_check(curenv, (void *)usd, sizeof(struct UserStabData), PTE_U)) return-1;
[00000000] new env 00001000 Incoming TRAP frame at 0xefffffbc Incoming TRAP frame at 0xefffffbc [00001000] user_mem_check assertion failure for va f010000c [00001000] free env 00001000 Destroyed the only environment - nothing more to do! Welcome to the JOS kernel monitor!
用户环境被销毁了，并且kernel没有panic，说明行为符合预期。
使用make grade命令可以得到如下结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
divzero: OK (1.4s) softint: OK (1.4s) badsegment: OK (2.0s) Part A score: 30/30
faultread: OK (1.9s) faultreadkernel: OK (1.6s) faultwrite: OK (0.9s) faultwritekernel: OK (1.6s) breakpoint: OK (2.0s) testbss: OK (2.1s) hello: OK (1.8s) buggyhello: OK (1.7s) buggyhello2: OK (0.8s) evilhello: OK (1.6s) Part B score: 50/50
divzero: OK (1.4s) softint: OK (1.4s) badsegment: OK (1.6s) Part A score: 30/30
faultread: OK (0.9s) faultreadkernel: OK (1.5s) faultwrite: OK (2.0s) faultwritekernel: OK (1.6s) breakpoint: OK (0.9s) (Old jos.out.breakpoint failure log removed) testbss: OK (1.5s) hello: OK (1.6s) buggyhello: OK (1.0s) buggyhello2: OK (1.4s) evilhello: OK (1.6s) Part B score: 50/50
Score: 80/80
Challenge 2
Intel手册中12.3.1.4节为关于单步调试的相关内容：
This debug condition occurs at the end of an instruction if the trap flag (TF) of the flags register held the value one at the beginning of that instruction. Note that the exception does not occur at the end of an instruction that sets TF. For example, if POPF is used to set TF, a single-step trap does not occur until after the instruction that follows POPF.
[00000000] new env 00001000 Incoming TRAP frame at 0xefffffbc Incoming TRAP frame at 0xefffffbc Welcome to the JOS kernel monitor! Type 'help' for a list of commands. TRAP frame at 0xf0228000 edi 0x00000000 esi 0x00000000 ebp 0xeebfdfd0 oesp 0xefffffdc ebx 0x00000000 edx 0x00000000 ecx 0x00000000 eax 0xeec00000 es 0x----0023 ds 0x----0023 trap 0x00000003 Breakpoint err 0x00000000 eip 0x00800038 cs 0x----001b flag 0x00000046 esp 0xeebfdfd0 ss 0x----0023 K> continue Incoming TRAP frame at 0xefffffbc [00001000] exiting gracefully [00001000] free env 00001000 Destroyed the only environment - nothing more to do! Welcome to the JOS kernel monitor! Type 'help' for a list of commands. K>
#define wrmsr(msr,val1,val2) \ __asm__ __volatile__("wrmsr" \ : /* no outputs */ \ : "c" (msr), "a" (val1), "d" (val2))
从IA32的手册当中可以找到在使用SYSENTER之前所需要设置的相关内容：
IA32_SYSENTER_CS (MSR address 174H) — The lower 16 bits of this MSR are the segment selector for the privilege level 0 code segment. This value is also used to determine the segment selector of the privilege level 0 stack segment (see the Operation section). This value cannot indicate a null selector.
IA32_SYSENTER_EIP (MSR address 176H) — The value of this MSR is loaded into RIP (thus, this value references the first instruction of the selected operating procedure or routine). In protected mode, only bits 31:0 are loaded.
IA32_SYSENTER_ESP (MSR address 175H) — The value of this MSR is loaded into RSP (thus, this value contains the stack pointer for the privilege level 0 stack). This value cannot represent a non-canonical address. In protected mode, only bits 31:0 are loaded.
[00000000] new env 00001000 Incoming TRAP frame at 0xefffffbc hello, world i am environment 00001000 Incoming TRAP frame at 0xefffffbc [00001000] exiting gracefully [00001000] free env 00001000 Destroyed the only environment - nothing more to do!
对比原来的输出：
1 2 3 4 5 6 7 8 9 10
[00000000] new env 00001000 Incoming TRAP frame at 0xefffffbc Incoming TRAP frame at 0xefffffbc hello, world Incoming TRAP frame at 0xefffffbc i am environment 00001000 Incoming TRAP frame at 0xefffffbc [00001000] exiting gracefully [00001000] free env 00001000 Destroyed the only environment - nothing more to do!
可以发现由于在进行系统调用的时候没有采用int 0x30，所以这里在每次输出前并没有都进入trap()函数，使得少去了两行Incoming TRAP frame at ....的输出。
// A linear address 'la' has a three-part structure as follows: // // +--------10------+-------10-------+---------12----------+ // | Page Directory | Page Table | Offset within Page | // | Index | Index | | // +----------------+----------------+---------------------+ // \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/ // \---------- PGNUM(la) ----------/
在inc/memlayout.h中可以看到PageInfo的结构如下：
1 2 3 4 5 6 7 8 9 10 11 12
structPageInfo { // Next page on the free list. structPageInfo *pp_link;
// pp_ref is the count of pointers (usually in page table entries) // to this page, for pages allocated using page_alloc. // Pages allocated at boot time using pmap.c's // boot_alloc do not have valid reference count fields.
// This simple physical memory allocator is used only while JOS is setting // up its virtual memory system. page_alloc() is the real allocator. // // If n>0, allocates enough pages of contiguous physical memory to hold 'n' // bytes. Doesn't initialize the memory. Returns a kernel virtual address. // // If n==0, returns the address of the next free page without allocating // anything. // // If we're out of memory, boot_alloc should panic. // This function may ONLY be used during initialization, // before the page_free_list list has been set up. staticvoid * boot_alloc(uint32_t n) { staticchar *nextfree; // virtual address of next byte of free memory char *result;
// Initialize nextfree 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: // the first virtual address that the linker did *not* assign // to any kernel code or global variables. if (!nextfree) { externchar end[]; nextfree = ROUNDUP((char *) end, PGSIZE); }
// Allocate a chunk large enough to hold 'n' bytes, then update // nextfree. Make sure nextfree is kept aligned // to a multiple of PGSIZE. // // LAB 2: Your code here. if(npages * PGSIZE < (uint32_t)(nextfree + n - KERNBASE)) // out of memory panic("boot_alloc: We are out of memory.\n"); result = nextfree; nextfree = ROUNDUP(nextfree + n, PGSIZE);
由于在注释中要求要对于对于out of memory的情况需要触发panic，所以这里在34行进行了一个分配内容是否超过物理内存限制的检查。如果一切正常的话就进行分配，采用已经定义好的ROUNDUP宏来进行页面对齐。
如果n为0的时候，37行代码不会产生任何改变，符合注释中所描述的代码逻辑。
mem_init
1 2 3 4 5 6 7 8 9
// Allocate an array of npages 'struct PageInfo's and store it in 'pages'. // The kernel uses this array to keep track of physical pages: for // each physical page, there is a corresponding struct PageInfo in this // array. 'npages' is the number of physical pages in memory. Use memset // to initialize all fields of each struct PageInfo to 0. // Your code goes here:
// At IOPHYSMEM (640K) there is a 384K hole for I/O. From the kernel, // IOPHYSMEM can be addressed at KERNBASE + IOPHYSMEM. The hole ends // at physical address EXTPHYSMEM. #define IOPHYSMEM 0x0A0000 #define EXTPHYSMEM 0x100000
/* 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) _kaddr(__FILE__, __LINE__, pa)
staticinlinevoid* _kaddr(constchar *file, int line, physaddr_t pa) { if (PGNUM(pa) >= npages) _panic(file, line, "KADDR called with invalid pa %08lx", pa); return (void *)(pa + KERNBASE); }
// // Initialize page structure and memory free list. // After this is done, NEVER use boot_alloc again. ONLY use the page // allocator functions below to allocate and deallocate physical // memory via the page_free_list. // void page_init(void) { // The example code here marks all physical pages as free. // However this is not truly the case. What memory is free? // 1) Mark physical 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) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE) // is free. // 3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must // never be allocated. // 4) Then extended memory [EXTPHYSMEM, ...). // Some of it is in use, some is free. Where is the kernel // in physical memory? Which pages are already in use for // page tables and other data structures? // // Change the code to reflect this. // NB: DO NOT actually touch the physical memory corresponding to // free pages! size_t i; uint32_t pa_free_start = (uint32_t)((char *)boot_alloc(0) - KERNBASE); // case 1: pages[0].pp_ref = 1; pages[0].pp_link = NULL; // case 2, 3, 4: for (i = 1; i < npages; i++) { if(IOPHYSMEM <= i * PGSIZE && i * PGSIZE < pa_free_start) { pages[i].pp_ref = 1; pages[i].pp_link = NULL; } else { pages[i].pp_ref = 0; pages[i].pp_link = page_free_list; page_free_list = &pages[i]; } } }
// // Allocates a physical page. If (alloc_flags & ALLOC_ZERO), fills the entire // returned physical page with '\0' bytes. Does NOT increment the reference // count of the page - the caller must do these if necessary (either explicitly // or via page_insert). // // Be sure to set the pp_link field of the allocated page to NULL so // page_free can check for double-free bugs. // // Returns NULL if out of free memory. // // Hint: use page2kva and memset struct PageInfo * page_alloc(int alloc_flags) { // Fill this function in structPageInfo* alloc_page = page_free_list; if(alloc_page == NULL) returnNULL; page_free_list = alloc_page->pp_link; alloc_page->pp_link = NULL; if(alloc_flags && ALLOC_ZERO) memset(page2kva(alloc_page), 0, PGSIZE); return alloc_page; }
// // Return a page to the free list. // (This function should only be called when pp->pp_ref reaches 0.) // void page_free(struct PageInfo *pp) { // Fill this function in // Hint: You may want to panic if pp->pp_ref is nonzero or // pp->pp_link is not NULL. if(pp->pp_ref != 0 || pp->pp_link != NULL) panic("page_free: pp_ref or pp_link is not zero!\n"); pp->pp_link = page_free_list; page_free_list = pp; return; }
// 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. // // The relevant page table page might not exist yet. // If this is true, and create == false, then pgdir_walk returns NULL. // Otherwise, pgdir_walk allocates a new page table page with page_alloc. // - If the allocation fails, pgdir_walk returns NULL. // - Otherwise, the new page's reference count is incremented, // the page is cleared, // and pgdir_walk returns a pointer into the new page table page. // // Hint 1: you can turn a PageInfo * into the physical address of the // page it refers to with page2pa() from kern/pmap.h. // // Hint 2: the x86 MMU checks permission bits in both the page directory // and the page table, so it's safe to leave permissions in the page // directory more permissive than strictly necessary. // // Hint 3: look at inc/mmu.h for useful macros that manipulate page // table and page directory entries. // pte_t * pgdir_walk(pde_t *pgdir, constvoid *va, int create) { // Fill this function in uint32_t pdx = PDX(va); uint32_t ptx = PTX(va); if(pgdir[pdx] == 0) { if(create) { structPageInfo* newpte = page_alloc(1); if(newpte == NULL) returnNULL; ++(newpte->pp_ref); pgdir[pdx] = page2pa(newpte) | PTE_P | PTE_W | PTE_U; } else returnNULL; } physaddr_t pte = PTE_ADDR(pgdir[pdx]) | (ptx << 2); return KADDR(pte); }
// // Map [va, va+size) of virtual address space to physical [pa, pa+size) // in the page table rooted at pgdir. Size is a multiple of PGSIZE, and // va and pa are both page-aligned. // Use permission bits perm|PTE_P for the entries. // // This function is only intended to set up the ``static'' mappings // above UTOP. As such, it should *not* change the pp_ref field on the // mapped pages. // // Hint: the TA solution uses pgdir_walk staticvoid boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm) { // Fill this function in while(size > 0) { pte_t* pte = pgdir_walk(pgdir, (void *)va, 1); if(pte == NULL) panic("boot_map_region: Fail to alloc new page, run out of memory!\n"); *pte = pa | perm | PTE_P; size -= PGSIZE; va += PGSIZE, pa += PGSIZE; } }
// // 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 and // can be used to verify page permissions for syscall arguments, // but should not be used by most callers. // // Return NULL if there is no page mapped at va. // // Hint: the TA solution uses pgdir_walk and pa2page. // struct PageInfo * page_lookup(pde_t *pgdir, void *va, pte_t **pte_store) { // Fill this function in pte_t* pte = pgdir_walk(pgdir, va, 0); if(pte == NULL) returnNULL; physaddr_t pa = PTE_ADDR(*pte); if(pte_store) *pte_store = pte; return pa2page(pa); }
// // 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 page 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 pte_t* pte_store; structPageInfo* pp = page_lookup(pgdir, va, &pte_store); if(pp == NULL) return; *pte_store = 0; page_decref(pp); tlb_invalidate(pgdir, va); }
// // 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'. // // Requirements // - If there is already a page mapped at 'va', it should be page_remove()d. // - If necessary, on demand, a page table should be allocated and inserted // 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'. // // Corner-case hint: Make sure to consider what happens when the same // pp is re-inserted at the same virtual address in the same pgdir. // However, try not to distinguish this case in your code, as this // frequently leads to subtle bugs; there's an elegant way to handle // everything in one code path. // // 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 PageInfo *pp, void *va, int perm) { // Fill this function in pte_t* pte = pgdir_walk(pgdir, va, 1); if(pte == NULL) return -E_NO_MEM; physaddr_t pa = page2pa(pp); ++(pp->pp_ref); if(*pte) page_remove(pgdir, va); *pte = pa | perm | PTE_P; return0; }
// Map 'pages' read-only by the user at linear address UPAGES // Permissions: // - the new image at UPAGES -- kernel R, user R // (ie. perm = PTE_U | PTE_P) // - pages itself -- kernel RW, user NONE // Your code goes here: n = ROUNDUP(npages*sizeof(struct PageInfo), PGSIZE); for (i = 0; i < n; i += PGSIZE) page_insert(kern_pgdir, pa2page(PADDR(pages) + i), (void *)(UPAGES + i), PTE_U | PTE_P);
// Use the physical memory that 'bootstack' refers to as the kernel // stack. The kernel stack grows down from virtual address KSTACKTOP. // We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP) // to be the kernel stack, but break this into two pieces: // * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory // * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if // the kernel overflows its stack, it will fault rather than // overwrite memory. Known as a "guard page". // Permissions: kernel RW, user NONE // Your code goes here: boot_map_region(kern_pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
// 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: //cprintf("kernbase: %x 2^32-kernbase: %x", KERNBASE, (~KERNBASE)+1); boot_map_region(kern_pgdir, KERNBASE, (~KERNBASE) + 1, 0, PTE_W);
We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel’s memory? What specific mechanisms protect the kernel memory?
Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?
# We haven't set up virtual memory yet, so we're running from # the physical address the boot loader loaded the kernel at: 1MB # (plus a few bytes). However, the C code is linked to run at # KERNBASE+1MB. Hence, we set up a trivial page directory that # translates virtual addresses [KERNBASE, KERNBASE+4MB) to # physical addresses [0, 4MB). This 4MB region will be # sufficient until we set up our real page table in mem_init # in lab 2.
# Load the physical address of entry_pgdir into cr3. entry_pgdir # is defined in entrypgdir.c. movl $(RELOC(entry_pgdir)), %eax movl %eax, %cr3 # Turn on paging. movl %cr0, %eax orl $(CR0_PE|CR0_PG|CR0_WP), %eax movl %eax, %cr0
# Now paging is enabled, but we're still running at a low EIP # (why is this okay?). Jump up above KERNBASE before entering # C code. mov $relocated, %eax jmp *%eax relocated:
# Clear the frame pointer register(EBP) # so that once we get into debugging C code, # stack backtraces will be terminated properly. movl $0x0,%ebp # nuke frame pointer
staticvoid boot_map_region_normal(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm) { // Fill this function in while(size > 0) { pte_t* pte = pgdir_walk(pgdir, (void *)va, 1); if(pte == NULL) panic("boot_map_region: Fail to alloc new page, run out of memory!\n"); *pte = pa | perm | PTE_P; size -= PGSIZE; va += PGSIZE, pa += PGSIZE; } }
staticvoid boot_map_region_ex(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm) { while(size > 0) { pte_t* pte = pgdir_walk_ex(pgdir, (void *)va, 2); if(pte == NULL) panic("boot_map_region: Fail to alloc new page, run out of memory!\n"); *pte = pa | perm | PTE_P | PTE_PS; size -= PTSIZE; va += PTSIZE, pa+= PTSIZE; } }
check_page_free_list() succeeded! check_page_alloc() succeeded! check_page() succeeded! check_kern_pgdir() succeeded! check_page_installed_pgdir() succeeded! Welcome to the JOS kernel monitor! Type 'help' for a list of commands. K>
题面中所说的"power-of-two allocation unit sizes from 4KB up to some reasonable maximum of your choice."应该就是伙伴系统了。感觉要完全实现除去修改自己写的函数之外需要修改check_page_free_list()以及kern/pmap.h当中的宏以及辅助函数，不知道会不会引发什么其他地方未知的错误，没有进行代码实现。
