Lecture 15 Scribes Notes - Computer Science 111, Winter 2012

Justin Taylor Manners: 603-933-566
Xiao Huang: 303-941-308
Youran Weng: 803-741-241

Lecture by Paul Eggert on March 7, 2012

Table of Contents

1. I. Page Faults
2. II. Paging Example
3. III. Improving Performance
4. IV. Return Oriented Programming
5. V. Fork Speed Increase
6. VI. Distributed Systems and RPC

---

I. Page Faults

Page Fault: When you Try to access memory thats not there in RAM!

Ram is a cache for a much larger disk


Map virtual address to real address with pmap

pmap(virtual address)

pmap(va) returns a page table entry
each process gets its own page table necessary for isolation

threads are not this way because they are supposed to have shared memory
decreases context switching cost

each process hass its own pmap function used like p->pmap(va)

In order to do pagefaults, we need a new function that tells us where virtual addresses live on disk

p->swapmap(va)
{return p->origin+virtual address;}
returns FAULT if va > virtual address limit

With these two functions we see what a page fault function does

pfault(faultedVA, Process, ) //2 cases, bad address, valid address we need to swap
{ if (p->swapmap(va)==FAULT) kill(p);
else
{ //page isnt in RAM, need to put in RAM; find unused RAM and swap page in, and pick a victim and send it down to disk
    (op,ova)=removal_policy(); //finds the correct victim
    pa=op->pmap(ova); //booting can be faster if you keep track of the initial pages of previous boots and prefetch
    write pa block to disk @ op->swapmap(ova);
    read pa block from disk @ p->swapmap(va);
    update BOTH page tables to reflect the newly changed RAM
}

         most imporant problem what policy is our removal_policy();

Q. which page should be the victim?
A0. pick a victim at random
A1. FIFO, choose page that has been in RAM longest
A2. Oracles policy, replace the page that won't be needed for the longest time *tell the future*
A3. LRU- least recently used - "nicest in practice"

II. Paging Example

III. Improving Performance

A. Demand paging
read just the main page & then execute, start right away //the point is to start faster. Important in interactive applications to put splash screen and then read more pages
+start faster
-more page-fault code executed
-more disk-arm movement, non-contiguous reads in a multiprocess application
targetted towards consumer processes, that want instant response

B. Skip uneeded Writes to Disk
Don't write victim page to disk if you know that the victim page has not been written to //dirty bit tells if you the page needs to be saved
dirty bit not supported in hardware mostly, so mark the page as invalid to give kernel control, and in the first write to the page, krenel marks page as dirty

This skips half of the writes when possible


                                what a dirty bit would look like in Hardware

IV. *Black hats on*

for security reasons, the 'x' bit (execute permissions) was added to block buffer overflow

Goal: how to get buffer overflow attack to execute arbritrary instructions when:
1) the application is r-x (no write permissions to executable code)
2) the stack is rw- (no execute permissions to the writable code)

Answer: RoP- return oriented programming
1) Uses pattern analysis of the executed code looking for a few, simple instructions followed by a return
2) Using these sets of instructions, build your program out of this with a turing machine?
3) Set proper return addresses on the stack to make the system run these sets of instructions in the order we want

V. LETS MAKE FORK FAST

fork() copies all of processess's virtual memory //problem is that its slow

Speed it up by abusing these facts:
1) Read Only pages don't need to be copied as they cant ever by inconsistent between processes
2) Don't necessarily need to copy writable pages either; use copy-on-write
           Copy-On-Write: only copy when actually written to copy-on-write: fork :: demand paging : exec
3) It is possible in some cases to even use the same page table,
           vfork(); from users point of view, parent + child share memory, therefore, share page tables
           *Required: parent is frozen until child exits or execs*

p = vfork();
if (!p){
fiddle a bit //should not stomp on globably visibile data structures (anything parent can see)
exec(); exit();
}



VI. Distributed Systems and & RPC - Remote Procedure Call

We want to call some function that transfers money from account A to account B

Our Machine calls transfer(10,a,b);
However,body of function runs on a seperate machine

RPCs differ from ordinary function calls & kernel syscalls

Positives

1)caller and callee have SUPER HARD MODULARITY //no shared address space

Negatives

1)slowest of the 3, high latency
2)speed of light problems
3)no call by reference, always by value

Both

1) Caller and Callee dont need to agree about architecture eg. sparc and intel

To solve this, both sides arrange for messages sent in a known format
The Caller has to convert arguments to external form which is called Marshalling
Callee then unMarshals the data and converts it to internal format that the system then uses