notepad

[FROM THE ASST3 DESCRIPTION: https://www.ops-class.org/asst/3/]

We might want to heed these warnings. We definitely felt this a bit in ASST2 and especially now during our cleanup process:

"As a final piece of advice, ASST2 and ASST3 begin to produce code bases that are large, complex, and potentially very difficult to debug. You do not want to introduce bugs into your kernel because they will be very hard to remove. Our advice—​slow down, design, think, design again, discuss with your partner, and slow down again. Then write some code."

"Note that because you are designing a much larger and more independent OS module, a good design is ever more important for ASST3 than it was for ASST2-"


Be able to answer:
    What will your page tables look like?

    What should you put in each page table entry (PTE)?

    What will your coremap (or reverse page table) look like?

    In what order can TLB faults and page faults occur? For example, can a page fault occur without causing a TLB fault?

    What is your strategy for splitting the assignment into smaller pieces that can be developed and tested separately? You are strongly encouraged to add new user and kernel tests as needed.


Important website material for getting started on ASST3.1: 	
	5.1. Setup	
	5.2. Tracking Kernel Page Allocations
	6.1. Coremap	
	

MORE CLARIFICATION IN CARL'S MASTER FORUM POST: 
https://discourse.ops-class.org/t/on-to-asst3-1/468


[ASST 3 RECITATION 1 NOTES]

Slides: https://drive.google.com/file/d/0B2KANO6SyBWlaFY3M2hwTEhCVkE/view
Video: https://www.youtube.com/watch?v=tNzwSD-smiM

ASST3 Overview
	ASST3 is divided into three incremental parts
		3.1 - Physical Memory Management (Coremap)				DUE 4/7
			Scroll down to 'ASST3.1 OVERVIEW' for more info
		3.2 - Address Space and TLB Management (User Paging)	DUE 4/21
		3.3 - Swapping											DUE 5/5

VM Interfaces
	Virtual Memory Management (RELEVANT TO ASST3.1)
		Defined in: kern/include/vm.h
		Dumb implementations of these functions in DUMBVM. They are intentionally bad.
		Interfaces:
			vm_bootstrap(): 
				Function to initialize VM Subsystem data structures.
				Problem: Dependency issues in subsystem boot order. 
				"This isn't actually a bootstrap." - Carl
			
			alloc_kpages(): NEED TO WRITE FOR ASST3.1
				Allocates n coniguous physical pages (Called by kmalloc)
				"Your implementation should call a working getppages routine that checks your coremap for the status of free pages and returns appropriately" - Carl

			free_kpages(): NEED TO WRITE FOR ASST3.1
				Free pages starting at a physical address argument (Called by kfree)
				Problem: Need to know how many pages to free

			vm_tlbshootdown(): 
				Remove an entry from another CPU's TLB address mapping.
				"Forget about this until you get to swapping" - Carl

			vm_fault(): 
				Routing to handle pagefaults.
				"Very important. Gets called every time there is a page fault. You need to do a lot of implementation and optimization in this"
				"If the user refers to a virtual address, the TLB checks to see if there's an entry, if there is not, it does a page fault and this routine is immediately called"
				"Says 'memory manager, there's a page fault what do you want to do?', and you need to tell it what to do. That's the essence of ASST3.2"

	Address Space Management (RELEVANT TO 3.2)
		Defined in: kern/include/addrspace.h
		"You don't have to grasp all this right now. These are more applicable to ASST3.2" - Carl
		Interfaces:
			as_create(): 
				Create a new empty address space
			as_destroy(): 
				Destroy an existing address space
			as_copy(): 
				Create a copy of an address space
			as_activate(): 
				Make current process's address space the one currently seen by the processor
			as_deactivate(): 
				Remove the current process's address space so it isn't seen by the processor
				"activate and deactivate update the TLB for a context switch" - Carl
			as_define_stack(): 
				setup the stack segment in the address space and return the initial stack pointer for the new process
			as_define_region(): 
				setup a memory segment within the address space
			as_prepare_load(): 
				called before loading a segement from disk into the address space
			as_complete_load(): 
				called after loading a segement from disk into the address space
		Usage example: kern/syscall/loadelf.c

	User Memory Management
		void * sbrk(intptr_t amount)
			A syscall to set process break (allocate memory)
			The "break" is the end address of a process's heap region
			In OS/161, the initial "break" must be page-aligned, and sbrk only need support values of 'amount' that result in page-aligned "break" addresses. Other values of 'amount' may be rejected.
			Check OS/161 man pages for more details: man/syscall/sbrk.html

DumbVM
	Implemented in: kern/arch/mips/vm/dumbvm.c
	Some notes on DumbVM:
		Don't copy dumbvm.c and try to improve it.
		DumbVM is not a good design reference.
		However, you can compare DumbVM to what a VM system is supposed to do.

	Physical Memory Management in DumbVM (RELEVANT TO 3.1)
		alloc_kpages() / free_kpages()
		Also check: kern/arch/mips/vm/ram.c
			ram_bootstrap()
			ram_stealmem()
				"Steals memory by just pushing the 'firstpaddr' pointer until you hit the end of memory and crash"
				"This is why dumbvm sucks" - Carl
		"The kernel is located in physical address 0 and up, which is mapped to virtual addresses 80000000 and up." - Carl

		Limitations of Physical Memory Management in DumbVM:
			Doesnt free allocated pages
			No reclaiming/recycling of pages
			Keepes stealing RAM until it runs out of pages

		What a VM Subsystem is SUPPOSED to provide:
			Coremap: A data structure that keeps track of information on all physiical pages frames
			The ability to reclaim/recycle physical pages
			"Your page table tracks information on virtual pages, your coremap tracks information on physcial pages (reverse page table!)" - Carl

	User Address Space in DumbVM
		DumbVM uses the "base and bound" approach to memory segmentation

		Limitations of the User Address Space in DumbVM:
			Fixed (3) number of segments, including the stack
				If the other two segements are used for test and data then there is no room for a heap
			Fixed size of stack: Under dumbvm, user stack is always 72k

		What a VM Subsystem is SUPPOSED to provide:
			Variable number of segements
				"5 or 6 should keep you safe" - Carl
			Variable sized segments (ie stack and heap)

	Address Translation in DumbVM
		Check vm_fault() function in DumbVM
			paddr = (faultaddress - vbase) + pbase

		Limitations of Address Translation in DumbVM:
			Each segment of contiguous virtual memory maps to a corresponding block of continiguous physical memory
				However, it is easy to implement: physical addresses ca be calculated quickly and there is no need to track individual pages

		What a VM Subsystem is SUPPOSED to provide:
			Flexible memory remapping: Scattered physical page frames can be mapped into contiguous virtual memory blocks
				However, need to track individual pages and locate metadata about them (ie PTEs) quickly

	Page Allocation in DumbVM
		Limitations of Page Allocation in DumbVM:
			Static allocation: All physical memory is allocated and fixed at program launch
				Suffers from internal fragementation

		What a VM Subsystem is SUPPOSED to provide:
			Dynamic allocation: Physical page frames are allocated on demand
				Allows dynamic growth of stack
				Supports sparse memory segments and data structures
				"Don't allocate your memory until you actually need it" -  Carl
	
	Swapping in DumbVM
		DumbVM doesn't support swapping
			Panic when running out of memory

		What a VM Subsystem is SUPPOSED to provide:
			Swap out pages when no free physical pages are availible

Design Document
	What will your data structures look like?
		Coremap and physical memory metadata
		Address space and virtual memory metadeta
		Page table and PTEs
	What information should each of your data structures have?
	How will you handle TLB faults and page faults?
	Do you need to provide synchronization? Where?
	If yes, then what synchronization primitives do you need to use?

ASST3.1 REVIEW
	Virtual Memory (VM) Subsystem
		Memory management technique that maps virtual addresses used by a user process into physical addresses in computer memory.
		User process sees the memory as contiguous address space.
		The operating system manages address spaces and the assignemnt of real memory to virtual memory.
		Memory Management Unit (MMU) uses the Translation Lookaside Buffer (TLB) to translate virtual addresses to physical addresses

ASST3.1 OVERVIEW
	1) Reconfigure os161 for ASST3 -- remove DumbVM
		"Your kernel wont boot. There is going to be some arithmetic involved in getting it up and running. Talk to course staff. They have shortcuts." - Carl

	2) Design one data structure, the coremap
		The first step in implementing physical memory management for your VM
		A coremap is a data structure that keeps track of the state of all physical page frames
		Number of entries in the coremap is going to be fixed, and must be accessed quickly
			"Just a simple array should be fine, possibly in combination with something else" - Carl
			How much physical memory will we have? That is defined in our sys161.conf file. Tests will be configuring your kernel with varying amounts.
			
		All you need to keep track of now is whether a particular physical frame is allocated and the size of each allocation request

	3) Write code to initialize data structure
		When to initialize the coremap data structure:
			Study the order of initialization functions (bootstrap functions) in kern/main/main.c
		Scenario 1: in vm_bootstrap() function
			Seems intuitive. But... "that won't work. Look in main.c. There will be a dependency issue with proc_bootstrap() because it needs kmalloc. Put it somewhere before proc_bootstrap(), either in ram_bootstrap() or make your own function" - Carl
		Scenario 2: Before the first kmalloc() call
			It's very early on, but THIS IS THE ONLY WAY. Talk to staff. They have shortcuts.
		"We can't just declare a global array. We also can't use kmalloc. We will have to manually create this data structure ourselves"

	4) (Re)write two functions: alloc_kpages() and free_kpages()
		These functions are called by kmalloc() and kfree() respectively

	5) Pass five tests: km1-km5
		These tests are run from the kernel menu

"That's assignment 3.1. Design the data strcuture that represents physical memrory, initialize the coremap, write a couple function to support kmalloc and kfree. Look at DumbVM to see how its done right now but its not a good design going forward."


[ASST 3 RECITATION 2 NOTES: ASST3.2 BOOTSTRAP]

Slides: https://drive.google.com/file/d/0B2KANO6SyBWlc3p6bDVXejZCQ2c/view
Video: https://youtu.be/1GB1VupDU5Q

VM Interfaces for 3.2
	Physical Memory Management: kern/include/vm.h
		vm_bootstrap
			Use this to set up the rest (post-coremap) part of your memory system

		vm_fault
			Handles all TLB faults

	Address Space Management: kern/include/addrspace.h 
		as_create()
			create a new empty address space.

		as_destroy()
			dispose an existing address space.

		as_copy() 
			create an exact copy of the passed address space.

		as_activate() 
			make current process's address space the one currently seen by the processor.

		as_deactivate() 
			unload current process's address space so it isn't seen by the processor.

		as_define_stack() 
			setup the stack region and return the initial stack pointer.

		as_define_region()
			setup a (non-stack) region of memory.

		as_prepare_load()
			called before loading from an executable into the address space.

		as_complete_load()
			called when loading from an executable is complete.

		Usage example: kern/syscall/loadelf.c

	User Memory Management: void* sbrk(intptr_t amount)
		A syscall to set process break (allocate memory).

		The "break" is the end address of a process's heap region.

		In OS/161, the initial "break" must be page-aligned, and sbrk only need support values of amount that result in page-aligned "break" addresses. Other values of amount may be rejected.

		As with other syscalls, check OS/161 man pages for more details: man/syscall/sbrk.html

MIPs interpretation of Virtual Memory
	Every vaddr under 80000000 is mapped to a paddr via tlb
	Every vaddr from 80000000 to bfffffff maps directly to paddr = vaddr - 80000000 
	Every vaddr over c0000000 is mapped to a paddr via tlb
	
"Let's talk about assignment 3.2"
	The address_space struct should contain at minimum:
		Segement (AKA region) information
			Should have room for multiple possible segements

		Need to track the start and size of each segment

	A Page Table structure (the state of virtual memory)
		Typically, implemeted as either a linked list or a MLPT
			Note that a 2-level array creates significant memory pressure.

		The Page Table contains Page Table Entries (PTEs)
			Each PTE contains the state of a virtual page

			Each PTE maps a virtual page to a physical page (or disk block)

	In general, KISS. Add additional fields as needed.
		Note: through 3.2, address spaces are private per process

"Start simple. Start with a reference to a physical address then add stuff as you go along"

"You don't have to worry about synchronization in terms of page tables...until 3.3"

Statically Sized Segments
	Text(code), Data(initialized local variables), and BSS (uninitialized static variables)
		These are set up at load time in os161, in load_elf() -> as_define_region()

	Stack -- set up in as_define_stack() (Thanks carl)

	These segements never change in size once set up
		Not the same as allocating underlying physical pages

	Additionally, DumbVM also *allocates* physical memory statically: as_prepare_load()
		Need to change this approach to dynamic allocation

	Heap
		No support for this in os161 out of the box

		This can change in size while the program is runnning

		Additionally, memory in the segment can be both dynamically allocated and reclaimed

Virtual memory Decision Tree
	Is the vaddr in an existing TLB translation entry?
		If yes, no fault (handled in hardware transparently)

	If not, is the vaddr in a segment (region)?
		If not, segmentation fault
	
	If so, is the vaddr also in a PTE?
		Need to search Page Table structure

		If so, is the virtual page in memory?
			If so, update the TLB and resume execution
			
			If not (Page fault), swap in page from disk
		
		If not, create a new PTE and allocate a new physical page (dynamic allocation)

vm_fault 
	Current Behavior:
		faultaddress is the vaddr of the TLB fault

		First 1/3 of code perforsm basic setup and safety checks
			DumbVM does not use subpermissions
		
		Second 1/3 tries to locate the phyiscal page corresponding to the virtual page of the fault
			Uses base and bounds method of translation
		
			Returns EFAULT if unsuccessful
		
		Last 1/3 takes the virtual page - physical page translation and updates the TLB
			Uses TLB access routines in machine/include/tlb.h
			Never evicts TLB translation entries => will eventually crash.
	
	What to do:
		Need to rewrite: handling of Virtual/Physical Data
	
		Given a virtual fault address, determine if it is a potentially valid address
			Look at memory segment information in your data structures
	
		If it is a valid address, locate the virtual page in which it occurs
			Search page table for PTE
	
			May need to allocate a new PTE
	
		The PTE should map the virtual page to a physical page
			May need to allocate a new physical page

			(for ASST3.3) May need to page-in data from disk

		Need to rewrite: updating of TLB entries
			Should never panic on running out of free entry slots
			
			May need to evict a TLB mapping (not the same as evicting a physical
			memory page)

GETTING STARTED
	Write your data structures:	
		struct addrspace, struct PTE, and pagetable
	
	Get a single process working -- eq a simple Hello World program
		Need: as_create(), as_define_region(), as_define_stack(), vm_fault()
	
		Reuse: as_activate()
	
	Add support for fork() and memory reclamation -- pass forktest
		Need: as_copy(), as_destroy()
	
		Clean up ALL memory leaks, tested by khu in test161
	
	Add support for dynamic memory management AKA heap
		Need: sbrk()
	
	Need to support dynamic memory allocation
		as_prepare_load() and as_complete_load() are used in DumbVM but may not be needed at all -- used for static allocation

Does the process page table abstract out the contiguousness of the coremap?
Clock LRU? 
	Brijesh used this. Took him to the finish line.
Speed of linkedlist
	Brijesh highly recommends the 4LPT
Will user processes be starting other user processes?
	That's what fork does you dummy
Do we need to worry about orphans now?

Do we decide where the static regions start and end? 
	as_define_region
Do we decide where the heap starts and ends? 
	as_define_region
Does everything need to be page aligned? 
	this is kindof implicitly taken care of
Static stack. No dynamic stack. Brijesh won't tell us how large it needs to be becuase he wants us to suffer

Dont need to deal with offset at all. Just chop it off. VPN is all you need.

If we do 4LPT

PTE[]       : stores PTE
PTE[][]     : stores PTE[]
PTE[][][]   : stores PTE[][]
PTE[][][][] : stores PTE[][][]

0xFFFFFFFF gets chopped down to 0xFFFFF, which is the same as 

11111 11111 11111 11111 in base 2

Each 5-bit chunk of that number is an index in each successive PT.

==EXPERIMENTAL BULLSHIT BELOW. POSSIBLY WRONG==
I think we might have to write something like this for allocing inside addrspace:

	curVaddr //Where the allocation is starting in the address space. How to get this?
	pages = needed_pages(alloc_size);
	blockStart = alloc_kpages(pages);
	for(int i = 0; i < pages; i++){
		struct pte curpte;
		curpte->vpn = (top 20 bits of curVaddr) + i;
		curpte->ppn = paddr_to_ppn((blockStart - 0x80000000) + (PAGE_SIZE * i));

[ASST3.3 RECITATION 1: ASST3.3 BOOTSTRAP]

Expand vm_fault to do the swapping-in algorithm

Eviction
	Use the virtual memory system to give the user process the illusion that it has more physical memory than it does
		The amount of allocated virtual memory in the addres space can be greater than the amount of allocated physical memory

		The remainder of allocated virtual memory resides on the backing storge (disk)

	The process of moving data between memory and disk is called swapping
		Moving data from a physical page to disk to make room is called eviction.

Swapping -- Implementation
	Changes to existing data structures
		Additional state info for physical page frames
		
		Additional state information for virtual pages
	
	Additional data structures
		Swapdisk, allocation bitmap

	Changes to existing routines
		Add support for page-in to fault handler -- vm_fault or equivalent
		
		Add support for page-out eviction to physical page allocator -- getppages() or equivalent

	Additional new routines
		Swapdisk blockread(), blockwrite()

		"A block refers to a 4096 block that resides on disk"

	Optimizations as needed
		ASST3.3 has time and space performance requirements -- logical correctness is not enough

	"Should never have to deal with the problem of swapdisk running out of space"

Swapping -- Additions
	Physical Page Frames (in coremap)
		Need some way of backtracking to the PTE of the process that currently owns this frame

		Now need to track whether a frame is part of a kernel data allocation

		Possibly other information for use in, say, an eviction algorithm or TLB shootdown code

	Virtual Page Table Entry (PTE)
		Now need to track location of data: in memory or on disk

		Need sychnronization information (lock etc.)

"Coremap size doesn't matter anymore, don't worry about it. Just add what you need."

Swapping In
	Need to swap in whenever we try to access a page whose data is on disk
		This happens in vm_fault and as_copy

	Allocate a physical page in memory as usual
		Underneath, however, this may trigger swapping "out" (evicting another virtual page to free up a physical page for use) if the coremap is full

	Copy the page data from disk to memory: blockread()

	Change the state of the page table entry (PTE) to indicate that the data of the virtual page is now in_memory
		The PTE is shared data in ASST3.3 -- yet another process may be trying to evict *this* page and change its state back to on_disk

"One design thing: We recommend, once you start doing something, let it go to completion. Once you begin the eviction process, let it run through to completion before you have to undo something"

Swapping Out
	Need to swap out whenever we try to allocate a page and the coremap is full
	
	Select a victim page to evict from the coremap
		Several eviction strategies to use -- complexity/performace tradeoff
		
		Good page frames not to evict: those holding kernel structures, or frames already in eviction
		
	Update the state of both the victim page frame and victim PTE
		The page frame has a new owner, the state of the victim PTE is now on_disk
		
		Both the coremap and PTE are shared data. Can need to hold *both* locks at the same time.
			Lock type and acquisition order matters (deadlock issues)
			
			The state of data may change if a lock is dropped and reacquired (sometimes necessary)
	
	The kernel can swap out user processes and user processes can swap out each other
		USER PROCESSES CANNOT SWAP OUT KERNEL STUFF	

	"Go for a clock or a LRU algorithm"

	"Eviction is not a ton of code -- about 300 lines to getppages. It's just very tricky."

	May need to remove the translation entry corresponding to the victim virtual page from another CPU's TLB
		Code to send a message to anohter CPU in tlb_shootdown()

		Only necessary if the victim thread state is currently RUN

	"Whenever you evict a page, flush the CPU/TLB. Inefficient but will work."

	Copy the page data from memory to disk: blockwrite()
		(optional) If maintaining page clean/dirty state, only necessary if state is dirty.


[GETTING STARTED]

Write/expand data structures
	Add additional fields to page frame struct, PTE struct
		Design swapdisk data and allocation bitmap
			Use bitmap to track 4k blocks on swapdisk
				Note that the bitmap is a shared structure

Write swapdisk access routines
	Initialization -- set up in vm_bootstrap()
		If device is absent, disable swapping (will be tested)

	Can us the initialization and access routines in bitmap.h

	Write read block and write block routines
		VOP_READ/WRITE diretly to/from kernel space

	Test swapdisk -- need to write your own

	"lhd0raw:" -- device name (recall "con:")

	Use VOP_STAT to figure out how large the swapdisk is since it's just a file

Write pagein/pageout routines
	Expand vm_fault() and getppages() or equivalent

	Use shorter eviction victim selection strategy for now -- random, roundrobin
		Likely not good enough to pass tests later -- use clock or LRU strategy

	Modify as_copy() and as_destroy() to support virtual page state, data can now be on disk
		Source data from copy may be on disk => pagein

		Target data for destroy may be on disk => deallocate

	Test: get the single-process tests passing (sort, matmult) before continuing
		Launch from kernel menu to avoid shell shit

		SUBMIT: Get 40 points now.

Add support for multiple processes
	Need to sync access to multiple shared data: PTEs, coremap

	Lock type and acquisition ordering matters -- prevent dealocks

	Test: get multiprocess tests passing with 1 CPU

Add support for multiple CPUs
	Add TLB shootdown
		Simplest approach to start: clear TLB

	Test: get multiprocess tests passing with multiple CPUs from kernel shell

Add optimizations
	Definitely: better page eviction strategy

	Likely: Better TLB shootdown method (only need if victim process state is RUN)

	Possible: cleaning service. Copy on write.
		Need to track page clean/dirty state