diff options
Diffstat (limited to 'web/l4.html')
| -rw-r--r-- | web/l4.html | 518 |
1 files changed, 0 insertions, 518 deletions
diff --git a/web/l4.html b/web/l4.html deleted file mode 100644 index 342af32..0000000 --- a/web/l4.html +++ /dev/null @@ -1,518 +0,0 @@ -<title>L4</title> -<html> -<head> -</head> -<body> - -<h1>Address translation and sharing using segments</h1> - -<p>This lecture is about virtual memory, focusing on address -spaces. It is the first lecture out of series of lectures that uses -xv6 as a case study. - -<h2>Address spaces</h2> - -<ul> - -<li>OS: kernel program and user-level programs. For fault isolation -each program runs in a separate address space. The kernel address -spaces is like user address spaces, expect it runs in kernel mode. -The program in kernel mode can execute priviledge instructions (e.g., -writing the kernel's code segment registers). - -<li>One job of kernel is to manage address spaces (creating, growing, -deleting, and switching between them) - -<ul> - -<li>Each address space (including kernel) consists of the binary - representation for the text of the program, the data part - part of the program, and the stack area. - -<li>The kernel address space runs the kernel program. In a monolithic - organization the kernel manages all hardware and provides an API - to user programs. - -<li>Each user address space contains a program. A user progam may ask - to shrink or grow its address space. - -</ul> - -<li>The main operations: -<ul> -<li>Creation. Allocate physical memory to storage program. Load -program into physical memory. Fill address spaces with references to -physical memory. -<li>Growing. Allocate physical memory and add it to address space. -<li>Shrinking. Free some of the memory in an address space. -<li>Deletion. Free all memory in an address space. -<li>Switching. Switch the processor to use another address space. -<li>Sharing. Share a part of an address space with another program. -</ul> -</ul> - -<p>Two main approaches to implementing address spaces: using segments - and using page tables. Often when one uses segments, one also uses - page tables. But not the other way around; i.e., paging without - segmentation is common. - -<h2>Example support for address spaces: x86</h2> - -<p>For an operating system to provide address spaces and address -translation typically requires support from hardware. The translation -and checking of permissions typically must happen on each address used -by a program, and it would be too slow to check that in software (if -even possible). The division of labor is operating system manages -address spaces, and hardware translates addresses and checks -permissions. - -<p>PC block diagram without virtual memory support: -<ul> -<li>physical address -<li>base, IO hole, extended memory -<li>Physical address == what is on CPU's address pins -</ul> - -<p>The x86 starts out in real mode and translation is as follows: - <ul> - <li>segment*16+offset ==> physical address - <li>no protection: program can load anything into seg reg - </ul> - -<p>The operating system can switch the x86 to protected mode, which -allows the operating system to create address spaces. Translation in -protected mode is as follows: - <ul> - <li>selector:offset (logical addr) <br> - ==SEGMENTATION==> - <li>linear address <br> - ==PAGING ==> - <li>physical address - </ul> - -<p>Next lecture covers paging; now we focus on segmentation. - -<p>Protected-mode segmentation works as follows: -<ul> -<li>protected-mode segments add 32-bit addresses and protection -<ul> -<li>wait: what's the point? the point of segments in real mode was - bigger addresses, but 32-bit mode fixes that! -</ul> -<li>segment register holds segment selector -<li>selector indexes into global descriptor table (GDT) -<li>segment descriptor holds 32-bit base, limit, type, protection -<li>la = va + base ; assert(va < limit); -<li>seg register usually implicit in instruction - <ul> - <li>DS:REG - <ul> - <li><tt>movl $0x1, _flag</tt> - </ul> - <li>SS:ESP, SS:EBP - <ul> - <li><tt>pushl %ecx, pushl $_i</tt> - <li><tt>popl %ecx</tt> - <li><tt>movl 4(%ebp),%eax</tt> - </ul> - <li>CS:EIP - <ul> - <li>instruction fetch - </ul> - <li>String instructions: read from DS:ESI, write to ES:EDI - <ul> - <li><tt>rep movsb</tt> - </ul> - <li>Exception: far addresses - <ul> - <li><tt>ljmp $selector, $offset</tt> - </ul> - </ul> -<li>LGDT instruction loads CPU's GDT register -<li>you turn on protected mode by setting PE bit in CR0 register -<li>what happens with the next instruction? CS now has different - meaning... - -<li>How to transfer from segment to another, perhaps with different -priveleges. -<ul> -<li>Current privilege level (CPL) is in the low 2 bits of CS -<li>CPL=0 is privileged O/S, CPL=3 is user -<li>Within in the same privelege level: ljmp. -<li>Transfer to a segment with more privilege: call gates. -<ul> -<li>a way for app to jump into a segment and acquire privs -<li>CPL must be <= descriptor's DPL in order to read or write segment -<li>call gates can change privelege <b>and</b> switch CS and SS - segment -<li>call gates are implemented using a special type segment descriptor - in the GDT. -<li>interrupts are conceptually the same as call gates, but their - descriptor is stored in the IDT. We will use interrupts to transfer - control between user and kernel mode, both in JOS and xv6. We will - return to this in the lecture about interrupts and exceptions. -</ul> -</ul> - -<li>What about protection? -<ul> - <li>can o/s limit what memory an application can read or write? - <li>app can load any selector into a seg reg... - <li>but can only mention indices into GDT - <li>app can't change GDT register (requires privilege) - <li>why can't app write the descriptors in the GDT? - <li>what about system calls? how to they transfer to kernel? - <li>app cannot <b>just</b> lower the CPL -</ul> -</ul> - -<h2>Case study (xv6)</h2> - -<p>xv6 is a reimplementation of <a href="../v6.html">Unix 6th edition</a>. -<ul> -<li>v6 is a version of the orginal Unix operating system for <a href="http://www.pdp11.org/">DEC PDP11</a> -<ul> - <li>PDP-11 (1972): - <li>16-bit processor, 18-bit physical (40) - <li>UNIBUS - <li>memory-mapped I/O - <li>performance: less than 1MIPS - <li>register-to-register transfer: 0.9 usec - <li>56k-228k (40) - <li>no paging, but some segmentation support - <li>interrupts, traps - <li>about $10K - <li>rk disk with 2MByte of storage - <li>with cabinet 11/40 is 400lbs -</ul> - <li>Unix v6 -<ul> - <li><a href="../reference.html">Unix papers</a>. - <li>1976; first widely available Unix outside Bell labs - <li>Thompson and Ritchie - <li>Influenced by Multics but simpler. - <li>complete (used for real work) - <li>Multi-user, time-sharing - <li>small (43 system calls) - <li>modular (composition through pipes; one had to split programs!!) - <li>compactly written (2 programmers, 9,000 lines of code) - <li>advanced UI (shell) - <li>introduced C (derived from B) - <li>distributed with source - <li>V7 was sold by Microsoft for a couple years under the name Xenix -</ul> - <li>Lion's commentary -<ul> - <li>surpressed because of copyright issue - <li>resurfaced in 1996 -</ul> - -<li>xv6 written for 6.828: -<ul> - <li>v6 reimplementation for x86 - <li>does't include all features of v6 (e.g., xv6 has 20 of 43 - system calls). - <li>runs on symmetric multiprocessing PCs (SMPs). -</ul> -</ul> - -<p>Newer Unixs have inherited many of the conceptual ideas even though -they added paging, networking, graphics, improve performance, etc. - -<p>You will need to read most of the source code multiple times. Your -goal is to explain every line to yourself. - -<h3>Overview of address spaces in xv6</h3> - -<p>In today's lecture we see how xv6 creates the kernel address - spaces, first user address spaces, and switches to it. To understand - how this happens, we need to understand in detail the state on the - stack too---this may be surprising, but a thread of control and - address space are tightly bundled in xv6, in a concept - called <i>process</i>. The kernel address space is the only address - space with multiple threads of control. We will study context - switching and process management in detail next weeks; creation of - the first user process (init) will get you a first flavor. - -<p>xv6 uses only the segmentation hardware on xv6, but in a limited - way. (In JOS you will use page-table hardware too, which we cover in - next lecture.) The adddress space layouts are as follows: -<ul> -<li>In kernel address space is set up as follows: - <pre> - the code segment runs from 0 to 2^32 and is mapped X and R - the data segment runs from 0 to 2^32 but is mapped W (read and write). - </pre> -<li>For each process, the layout is as follows: -<pre> - text - original data and bss - fixed-size stack - expandable heap -</pre> -The text of a process is stored in its own segment and the rest in a -data segment. -</ul> - -<p>xv6 makes minimal use of the segmentation hardware available on the -x86. What other plans could you envision? - -<p>In xv6, each each program has a user and a kernel stack; when the -user program switches to the kernel, it switches to its kernel stack. -Its kernel stack is stored in process's proc structure. (This is -arranged through the descriptors in the IDT, which is covered later.) - -<p>xv6 assumes that there is a lot of physical memory. It assumes that - segments can be stored contiguously in physical memory and has - therefore no need for page tables. - -<h3>xv6 kernel address space</h3> - -<p>Let's see how xv6 creates the kernel address space by tracing xv6 - from when it boots, focussing on address space management: -<ul> -<li>Where does xv6 start after the PC is power on: start (which is - loaded at physical address 0x7c00; see lab 1). -<li>1025-1033: are we in real mode? -<ul> -<li>how big are logical addresses? -<li>how big are physical addresses? -<li>how are addresses physical calculated? -<li>what segment is being used in subsequent code? -<li>what values are in that segment? -</ul> -<li>1068: what values are loaded in the GDT? -<ul> -<li>1097: gdtr points to gdt -<li>1094: entry 0 unused -<li>1095: entry 1 (X + R, base = 0, limit = 0xffffffff, DPL = 0) -<li>1096: entry 2 (W, base = 0, limit = 0xffffffff, DPL = 0) -<li>are we using segments in a sophisticated way? (i.e., controled sharing) -<li>are P and S set? -<li>are addresses translated as in protected mode when lgdt completes? -</ul> -<li>1071: no, and not even here. -<li>1075: far jump, load 8 in CS. from now on we use segment-based translation. -<li>1081-1086: set up other segment registers -<li>1087: where is the stack which is used for procedure calls? -<li>1087: cmain in the bootloader (see lab 1), which calls main0 -<li>1222: main0. -<ul> -<li>job of main0 is to set everthing up so that all xv6 convtions works -<li>where is the stack? (sp = 0x7bec) -<li>what is on it? -<pre> - 00007bec [00007bec] 7cda // return address in cmain - 00007bf0 [00007bf0] 0080 // callee-saved ebx - 00007bf4 [00007bf4] 7369 // callee-saved esi - 00007bf8 [00007bf8] 0000 // callee-saved ebp - 00007bfc [00007bfc] 7c49 // return address for cmain: spin - 00007c00 [00007c00] c031fcfa // the instructions from 7c00 (start) -</pre> -</ul> -<li>1239-1240: switch to cpu stack (important for scheduler) -<ul> -<li>why -32? -<li>what values are in ebp and esp? -<pre> -esp: 0x108d30 1084720 -ebp: 0x108d5c 1084764 -</pre> -<li>what is on the stack? -<pre> - 00108d30 [00108d30] 0000 - 00108d34 [00108d34] 0000 - 00108d38 [00108d38] 0000 - 00108d3c [00108d3c] 0000 - 00108d40 [00108d40] 0000 - 00108d44 [00108d44] 0000 - 00108d48 [00108d48] 0000 - 00108d4c [00108d4c] 0000 - 00108d50 [00108d50] 0000 - 00108d54 [00108d54] 0000 - 00108d58 [00108d58] 0000 - 00108d5c [00108d5c] 0000 - 00108d60 [00108d60] 0001 - 00108d64 [00108d64] 0001 - 00108d68 [00108d68] 0000 - 00108d6c [00108d6c] 0000 -</pre> - -<li>what is 1 in 0x108d60? is it on the stack? - -</ul> - -<li>1242: is it save to reference bcpu? where is it allocated? - -<li>1260-1270: set up proc[0] - -<ul> -<li>each process has its own stack (see struct proc). - -<li>where is its stack? (see the section below on physical memory - management below). - -<li>what is the jmpbuf? (will discuss in detail later) - -<li>1267: why -4? - -</ul> - -<li>1270: necessar to be able to take interrupts (will discuss in - detail later) - -<li>1292: what process do you think scheduler() will run? we will - study later how that happens, but let's assume it runs process0 on - process0's stack. -</ul> - -<h3>xv6 user address spaces</h3> - -<ul> -<li>1327: process0 -<ul> -<li>process 0 sets up everything to make process conventions work out - -<li>which stack is process0 running? see 1260. - -<li>1334: is the convention to release the proc_table_lock after being - scheduled? (we will discuss locks later; assume there are no other - processors for now.) - -<li>1336: cwd is current working directory. - -<li>1348: first step in initializing a template tram frame: set - everything to zero. we are setting up process 0 as if it just - entered the kernel from user space and wants to go back to user - space. (see x86.h to see what field have the value 0.) - -<li>1349: why "|3"? instead of 0? - -<li>1351: why set interrupt flag in template trapframe? - -<li>1352: where will the user stack be in proc[0]'s address space? - -<li>1353: makes a copy of proc0. fork() calls copyproc() to implement - forking a process. This statement in essense is calling fork inside - proc0, making a proc[1] a duplicate of proc[0]. proc[0], however, - has not much in its address space of one page (see 1341). -<ul> -<li>2221: grab a lock on the proc table so that we are the only one - updating it. -<li>2116: allocate next pid. -<li>2228: we got our entry; release the lock. from now we are only - modifying our entry. -<li>2120-2127: copy proc[0]'s memory. proc[1]'s memory will be identical - to proc[0]'s. -<li>2130-2136: allocate a kernel stack. this stack is different from - the stack that proc[1] uses when running in user mode. -<li>2139-2140: copy the template trapframe that xv6 had set up in - proc[0]. -<li>2147: where will proc[1] start running when the scheduler selects - it? -<li>2151-2155: Unix semantics: child inherits open file descriptors - from parent. -<li>2158: same for cwd. -</ul> - -<li>1356: load a program in proc[1]'s address space. the program - loaded is the binary version of init.c (sheet 16). - -<li>1374: where will proc[1] start? - -<li>1377-1388: copy the binary into proc[1]'s address space. (you - will learn about the ELF format in the labs.) -<ul> -<li>can the binary for init be any size for proc[1] to work correctly? - -<li>what is the layout of proc[1]'s address space? is it consistent - with the layout described on line 1950-1954? - -</ul> - -<li>1357: make proc[1] runnable so that the scheduler will select it - to run. everything is set up now for proc[1] to run, "return" to - user space, and execute init. - -<li>1359: proc[0] gives up the processor, which calls sleep, which - calls sched, which setjmps back to scheduler. let's peak a bit in - scheduler to see what happens next. (we will return to the - scheduler in more detail later.) -</ul> -<li>2219: this test will fail for proc[1] -<li>2226: setupsegs(p) sets up the segments for proc[1]. this call is - more interesting than the previous, so let's see what happens: -<ul> -<li>2032-37: this is for traps and interrupts, which we will cover later. -<li>2039-49: set up new gdt. -<li>2040: why 0x100000 + 64*1024? -<li>2045: why 3? why is base p->mem? is p->mem physical or logical? -<li>2045-2046: how much the program for proc[1] be compiled if proc[1] - will run successfully in user space? -<li>2052: we are still running in the kernel, but we are loading gdt. - is this ok? -<li>why have so few user-level segments? why not separate out code, - data, stack, bss, etc.? -</ul> -<li>2227: record that proc[1] is running on the cpu -<li>2228: record it is running instead of just runnable -<li>2229: setjmp to fork_ret. -<li>2282: which stack is proc[1] running on? -<li>2284: when scheduled, first release the proc_table_lock. -<li>2287: back into assembly. -<li>2782: where is the stack pointer pointing to? -<pre> - 0020dfbc [0020dfbc] 0000 - 0020dfc0 [0020dfc0] 0000 - 0020dfc4 [0020dfc4] 0000 - 0020dfc8 [0020dfc8] 0000 - 0020dfcc [0020dfcc] 0000 - 0020dfd0 [0020dfd0] 0000 - 0020dfd4 [0020dfd4] 0000 - 0020dfd8 [0020dfd8] 0000 - 0020dfdc [0020dfdc] 0023 - 0020dfe0 [0020dfe0] 0023 - 0020dfe4 [0020dfe4] 0000 - 0020dfe8 [0020dfe8] 0000 - 0020dfec [0020dfec] 0000 - 0020dff0 [0020dff0] 001b - 0020dff4 [0020dff4] 0200 - 0020dff8 [0020dff8] 1000 -</pre> -<li>2783: why jmp instead of call? -<li>what will iret put in eip? -<li>what is 0x1b? what will iret put in cs? -<li>after iret, what will the processor being executing? -</ul> - -<h3>Managing physical memory</h3> - -<p>To create an address space we must allocate physical memory, which - will be freed when an address space is deleted (e.g., when a user - program terminates). xv6 implements a first-fit memory allocater - (see kalloc.c). - -<p>It maintains a list of ranges of free memory. The allocator finds - the first range that is larger than the amount of requested memory. - It splits that range in two: one range of the size requested and one - of the remainder. It returns the first range. When memory is - freed, kfree will merge ranges that are adjacent in memory. - -<p>Under what scenarios is a first-fit memory allocator undesirable? - -<h3>Growing an address space</h3> - -<p>How can a user process grow its address space? growproc. -<ul> -<li>2064: allocate a new segment of old size plus n -<li>2067: copy the old segment into the new (ouch!) -<li>2068: and zero the rest. -<li>2071: free the old physical memory -</ul> -<p>We could do a lot better if segments didn't have to contiguous in - physical memory. How could we arrange that? Using page tables, which - is our next topic. This is one place where page tables would be - useful, but there are others too (e.g., in fork). -</body> - - |