From 01a6c054d548d9fff8bbdfac4d3f3de4ae8677a1 Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Wed, 7 Sep 2011 11:49:14 -0400 Subject: Remove web directory; all cruft or moved to 6.828 repo --- web/l4.html | 518 ------------------------------------------------------------ 1 file changed, 518 deletions(-) delete mode 100644 web/l4.html (limited to 'web/l4.html') 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 @@ -L4 - - - - - -

Address translation and sharing using segments

- -

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. - -

Address spaces

- -

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). - -
One job of kernel is to manage address spaces (creating, growing, -deleting, and switching between them) - -
- 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. - -
- The kernel address space runs the kernel program. In a monolithic - organization the kernel manages all hardware and provides an API - to user programs. - -
- Each user address space contains a program. A user progam may ask - to shrink or grow its address space. - -
- -
The main operations: -
- Creation. Allocate physical memory to storage program. Load -program into physical memory. Fill address spaces with references to -physical memory. -
- Growing. Allocate physical memory and add it to address space. -
- Shrinking. Free some of the memory in an address space. -
- Deletion. Free all memory in an address space. -
- Switching. Switch the processor to use another address space. -
- Sharing. Share a part of an address space with another program. -
-

- -

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. - -

Example support for address spaces: x86

- -

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. - -

PC block diagram without virtual memory support: -

physical address -
base, IO hole, extended memory -
Physical address == what is on CPU's address pins -

- -

The x86 starts out in real mode and translation is as follows: -

segment*16+offset ==> physical address -
no protection: program can load anything into seg reg -

- -

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: -

selector:offset (logical addr)
- ==SEGMENTATION==> -
linear address
- ==PAGING ==> -
physical address -

- -

Next lecture covers paging; now we focus on segmentation. - -

Protected-mode segmentation works as follows: -

protected-mode segments add 32-bit addresses and protection -
- wait: what's the point? the point of segments in real mode was - bigger addresses, but 32-bit mode fixes that! -
-
segment register holds segment selector -
selector indexes into global descriptor table (GDT) -
segment descriptor holds 32-bit base, limit, type, protection -
la = va + base ; assert(va < limit); -
seg register usually implicit in instruction -
- DS:REG -
  - movl $0x1, _flag -
  -
- SS:ESP, SS:EBP -
  - pushl %ecx, pushl $_i -
  - popl %ecx -
  - movl 4(%ebp),%eax -
  -
- CS:EIP -
  - instruction fetch -
  -
- String instructions: read from DS:ESI, write to ES:EDI -
  - rep movsb -
  -
- Exception: far addresses -
  - ljmp $selector, $offset -
  -
-
LGDT instruction loads CPU's GDT register -
you turn on protected mode by setting PE bit in CR0 register -
what happens with the next instruction? CS now has different - meaning... - -
How to transfer from segment to another, perhaps with different -priveleges. -
- Current privilege level (CPL) is in the low 2 bits of CS -
- CPL=0 is privileged O/S, CPL=3 is user -
- Within in the same privelege level: ljmp. -
- Transfer to a segment with more privilege: call gates. -
  - a way for app to jump into a segment and acquire privs -
  - CPL must be <= descriptor's DPL in order to read or write segment -
  - call gates can change privelege and switch CS and SS - segment -
  - call gates are implemented using a special type segment descriptor - in the GDT. -
  - 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. -
  -
- -
What about protection? -
- can o/s limit what memory an application can read or write? -
- app can load any selector into a seg reg... -
- but can only mention indices into GDT -
- app can't change GDT register (requires privilege) -
- why can't app write the descriptors in the GDT? -
- what about system calls? how to they transfer to kernel? -
- app cannot just lower the CPL -
-

- -

Case study (xv6)

- -

xv6 is a reimplementation of Unix 6th edition. -

v6 is a version of the orginal Unix operating system for DEC PDP11 -
- PDP-11 (1972): -
- 16-bit processor, 18-bit physical (40) -
- UNIBUS -
- memory-mapped I/O -
- performance: less than 1MIPS -
- register-to-register transfer: 0.9 usec -
- 56k-228k (40) -
- no paging, but some segmentation support -
- interrupts, traps -
- about $10K -
- rk disk with 2MByte of storage -
- with cabinet 11/40 is 400lbs -
-
Unix v6 -
- Unix papers. -
- 1976; first widely available Unix outside Bell labs -
- Thompson and Ritchie -
- Influenced by Multics but simpler. -
- complete (used for real work) -
- Multi-user, time-sharing -
- small (43 system calls) -
- modular (composition through pipes; one had to split programs!!) -
- compactly written (2 programmers, 9,000 lines of code) -
- advanced UI (shell) -
- introduced C (derived from B) -
- distributed with source -
- V7 was sold by Microsoft for a couple years under the name Xenix -
-
Lion's commentary -
- surpressed because of copyright issue -
- resurfaced in 1996 -
- -
xv6 written for 6.828: -
- v6 reimplementation for x86 -
- does't include all features of v6 (e.g., xv6 has 20 of 43 - system calls). -
- runs on symmetric multiprocessing PCs (SMPs). -
-

- -

Newer Unixs have inherited many of the conceptual ideas even though -they added paging, networking, graphics, improve performance, etc. - -

You will need to read most of the source code multiple times. Your -goal is to explain every line to yourself. - -

Overview of address spaces in xv6

- -

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 process. 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. - -

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: -

In kernel address space is set up as follows: -

-  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).
-

For each process, the layout is as follows: -
```
-  text
-  original data and bss
-  fixed-size stack
-  expandable heap
-
```
-The text of a process is stored in its own segment and the rest in a -data segment. -

- -

xv6 makes minimal use of the segmentation hardware available on the -x86. What other plans could you envision? - -

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.) - -

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. - -

xv6 kernel address space

- -

Let's see how xv6 creates the kernel address space by tracing xv6 - from when it boots, focussing on address space management: -

Where does xv6 start after the PC is power on: start (which is - loaded at physical address 0x7c00; see lab 1). -
1025-1033: are we in real mode? -
- how big are logical addresses? -
- how big are physical addresses? -
- how are addresses physical calculated? -
- what segment is being used in subsequent code? -
- what values are in that segment? -
-
1068: what values are loaded in the GDT? -
- 1097: gdtr points to gdt -
- 1094: entry 0 unused -
- 1095: entry 1 (X + R, base = 0, limit = 0xffffffff, DPL = 0) -
- 1096: entry 2 (W, base = 0, limit = 0xffffffff, DPL = 0) -
- are we using segments in a sophisticated way? (i.e., controled sharing) -
- are P and S set? -
- are addresses translated as in protected mode when lgdt completes? -
-
1071: no, and not even here. -
1075: far jump, load 8 in CS. from now on we use segment-based translation. -
1081-1086: set up other segment registers -
1087: where is the stack which is used for procedure calls? -
1087: cmain in the bootloader (see lab 1), which calls main0 -

1222: main0. -

job of main0 is to set everthing up so that all xv6 convtions works -
where is the stack? (sp = 0x7bec) -

what is on it? -

-   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)
-

1239-1240: switch to cpu stack (important for scheduler) -

why -32? -

what values are in ebp and esp? -

-esp: 0x108d30   1084720
-ebp: 0x108d5c   1084764
-

what is on the stack? -

-   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
-

- -

what is 1 in 0x108d60? is it on the stack? - -

- -

1242: is it save to reference bcpu? where is it allocated? - -
1260-1270: set up proc[0] - -
- each process has its own stack (see struct proc). - -
- where is its stack? (see the section below on physical memory - management below). - -
- what is the jmpbuf? (will discuss in detail later) - -
- 1267: why -4? - -
- -
1270: necessar to be able to take interrupts (will discuss in - detail later) - -
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. -

- -

xv6 user address spaces

- -

1327: process0 -
- process 0 sets up everything to make process conventions work out - -
- which stack is process0 running? see 1260. - -
- 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.) - -
- 1336: cwd is current working directory. - -
- 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.) - -
- 1349: why "|3"? instead of 0? - -
- 1351: why set interrupt flag in template trapframe? - -
- 1352: where will the user stack be in proc[0]'s address space? - -
- 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). -
  - 2221: grab a lock on the proc table so that we are the only one - updating it. -
  - 2116: allocate next pid. -
  - 2228: we got our entry; release the lock. from now we are only - modifying our entry. -
  - 2120-2127: copy proc[0]'s memory. proc[1]'s memory will be identical - to proc[0]'s. -
  - 2130-2136: allocate a kernel stack. this stack is different from - the stack that proc[1] uses when running in user mode. -
  - 2139-2140: copy the template trapframe that xv6 had set up in - proc[0]. -
  - 2147: where will proc[1] start running when the scheduler selects - it? -
  - 2151-2155: Unix semantics: child inherits open file descriptors - from parent. -
  - 2158: same for cwd. -
  - -
- 1356: load a program in proc[1]'s address space. the program - loaded is the binary version of init.c (sheet 16). - -
- 1374: where will proc[1] start? - -
- 1377-1388: copy the binary into proc[1]'s address space. (you - will learn about the ELF format in the labs.) -
  - can the binary for init be any size for proc[1] to work correctly? - -
  - what is the layout of proc[1]'s address space? is it consistent - with the layout described on line 1950-1954? - -
  - -
- 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. - -
- 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.) -
-
2219: this test will fail for proc[1] -
2226: setupsegs(p) sets up the segments for proc[1]. this call is - more interesting than the previous, so let's see what happens: -
- 2032-37: this is for traps and interrupts, which we will cover later. -
- 2039-49: set up new gdt. -
- 2040: why 0x100000 + 64*1024? -
- 2045: why 3? why is base p->mem? is p->mem physical or logical? -
- 2045-2046: how much the program for proc[1] be compiled if proc[1] - will run successfully in user space? -
- 2052: we are still running in the kernel, but we are loading gdt. - is this ok? -
- why have so few user-level segments? why not separate out code, - data, stack, bss, etc.? -
-
2227: record that proc[1] is running on the cpu -
2228: record it is running instead of just runnable -
2229: setjmp to fork_ret. -
2282: which stack is proc[1] running on? -
2284: when scheduled, first release the proc_table_lock. -
2287: back into assembly. -

2782: where is the stack pointer pointing to? -

-   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
-

2783: why jmp instead of call? -
what will iret put in eip? -
what is 0x1b? what will iret put in cs? -
after iret, what will the processor being executing? -

- -

Managing physical memory

- -

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). - -

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. - -

Under what scenarios is a first-fit memory allocator undesirable? - -

Growing an address space

- -

How can a user process grow its address space? growproc. -

2064: allocate a new segment of old size plus n -
2067: copy the old segment into the new (ouch!) -
2068: and zero the rest. -
2071: free the old physical memory -

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). - - - -- cgit v1.2.3