CS 111 - Lecture 14 Scribe Notes (3/4/13)

Scribe: Wesley Situ

Unreliable Processes with Bad Memory References

An unavoidable problem that arises is the unreliability of programs making bad memory references. They may be making subscript errors or dereferencing null, uninitialized, and freed pointers, leading to the corruption of memory. So, what are the possible solutions to prevent this from happening?

1. Fire the programmers!

   Well... getting rid of bad programmers would fix the problem, but not everyone writes flawless code. This approach would not scale well.

2. Add runtime subscript checking

   During compilation, all accesses to memory can be checked. For example, Java does this and throws an exception when there is an out-of-bounds access to an array. However there is the downside of performance for having to do these checks. Also, subscript checking is voluntary, so there is a trust issue between the process and the OS. A solution for this is that the OS will have its own compiler, and it will only run programs built with that compiler. Some OSes that do this are the B5500 and its successors.

3. Ask the hardware for help to do subscript checking

   The simple approach to check whether or not a process is making a valid access to memory is to specify a region in memory with a base register and a bounds register. If there is an attempt to make an access outside of that region, the system will trap.

   

Problems with Base-Bounds Pairs

If processes change their base or bounds they could give themselves more memory. We can easily avoid this problem by making the registers privileged.

Suppose we have two processes that contain a copy of sort. When the programs instruction pointers reach the jump to the sort code's absolute address, it is possible that they will jump to a region in which the processes do not have access. How might we fix this problem?

• We can change the hardware to add the processes' base to every address. This way, the addresses of sort are at the same offsets.
• We can mutate the program as we load it into RAM and change the absolute addresses.
• We can prohibit absolute addresses altogether. gcc can build these Position Independent Codes (PIC) with the options -fpic or -fPIC.

With this approach of base-bounds pairs, each process is given its own region in memory. What if we want them to share memory?

We just need to give the processes more base-bounds pairs! But how can we keep track of which processes have access to which base-bounds pairs?

• Domains

  We can add a system call to create a domain.

  • map_domain(size, permissions)

    The permissions are also stored in registers like the base and bounds. They specify the actions a process can do with the domain. Namely, rwx (read, write, execute). Traditionally, x86 only had read and write permissions as execute is just a specific form of reading. However, buffer overflow attacks were easy.

    Some possible uses for domains

    • Text of a program (r)
    • Data of a program (w)
    • Heap (rw)
    • Stack (1/thread)
    • I/O buffers
    • Shared memory
    • Segmented memory

Segmentation

The idea of segmentation is to parcel out memory to processes, recording them in a segment table. It will verify if the process has access to a segment by checking if the offset is within the bounds and if it has the permissions to do what it wants to do. Like base-bounds registers, privileges are needed to change the segment table.

A layout of RAM using this method is as follows:

Notice that it is expensive to grow files. i.e. new x(), malloc(N). This problem is similar to the file system problem. A solution for this is page-based memory management.

Virtual Memory

• Page-based Memory Management

  

  An advantage for using this technique is that all the pages are the same size(say 8KiB). Accesses to pages are done by specifying a virtual page number and an offset into that page. The virtual page number will then be magically converted into a physical page in memory. This "magic box" is a page table which maps a virtual page to a physical page

  Linear Page Table

  

  int pmap(int v){
  	return PAGE_TABLE[v];
  }

  If each page table entry is 4 bytes, and there are 2²⁰ entries, then each process is given up to 4 MB of mapping. However, for processes that do not need that much, it becomes a waste of space.

  2-Level Page Table

  

  int pmap(int v){
  	int hi = v >> 10;
  	int lo = v & (1 << 10)-1;
  	pt *p = PAGE_TABLE[hi];
  	if (!p)
  	  return 0;
  	return p[lo];
  }

  In order to reduce the waste from a linear page table, a 2-level page table can be used. There are 10 bits to represent the top-level page number, and 10 bits to represent the second level pages. This is similar to indirect blocking in file systems. This method would use 3 page tables * 4 bytes per PTE * 2¹⁰ byte entries, which is 12 KB per process.

As the OS kernel, we might want to "lie" to hardware, tell it current process is smaller than it really is. The program would think it has 3.5 GiB of memory when it only has 100 MiB.

This takes advantage of the fact that most of the space is unused (0). When the program does actually need that page, we can do a page fault (trapping, then inspecting the fault address) to bring the page from the swap space to main memory. Main memory is, in a sense, a cache for the swap space.

Page Faulting

Although it is nice that we can run programs that require more memory than we actually have, there is a catch. It is very slow to do a page fault. Here's the code to implement a page fault:

p - process holding victim page
va - virtual address of victim
pa - physical address of victim

void pfault(int v, int access, ...){
	if (swapmap(v, current_process) == FAIL)
		kill(current_process);
	else{
		(p, va) = removal_policy(); /*pick a victim physical page*/
		pa = p->pmap(va);
		p->pmap(va) = FAULT; /*move here in case of interrupt*/
		write(pa, swapmap(p, va)); /*still valid if interrupted here*/
		p->pmap(va) = FAULT;
		read(pa, swapmap(current_process, v));
		current_process->pmap(v) = pa;
	}
}

Note: Memory manager pages themselves are "wired down"; they're never selected as victims to swap out. Also, first level pages shouldn't be victimized, or else we would lose track of second level pages and data.

Virtual Memory Tuning

The process of page faulting is slow, but there are some ways that we can speed it up.

1. Demand Paging

   When we start up the program, we'll just load the first page, then do page faults when the program needs it. The advantage of doing this is that there is a quick response time for the programs, but after that startup, it's slow. This is due to the need of the disk arm to move around constantly as it is serving other processes.

2. The Dirty Bit

   In the page table entries, we can designate a bit to be 0 for unmodified and 1 for modified. Every now and then, we'll reset all the bits to 0. Whenever the page is changed, the bit will be changed to a 1. This will let us know whether or not we actually need to write the page back to the swap space. If the bit is 0 when the page is victimized, it is a win for us because we only need to replace it; we can eliminate the time for doing a store for that page.