Skip to content

Instantly share code, notes, and snippets.

@zurawiki

zurawiki/a3-design.md

Last active August 29, 2015 14:17
Show Gist options
  • Save zurawiki/bf1971848d7552caa031 to your computer and use it in GitHub Desktop.
Save zurawiki/bf1971848d7552caa031 to your computer and use it in GitHub Desktop.
Download ZIP
A3 Design Doc
Raw
a3-design.md

A3 Design Doc

Rottweiler OS161

Stella Pantella - Roger Zurawicki

Data Structures

Coremap

// max_pid is 64 = 2^6
struct cm_elt_t {
    uint32_t tlb_hi; 
    // = TLB_HI[1/2]    32 bits
    // |-- VPN          20 bits
    // |-- pid          12 bits  
    // unsigned lockbit;   (used for multipage allocation)
}

Page Table

We assume one level constant size pagetable

// 64-bit struct
struct pt_elt_t {
    uint32_t tlb_lo;
    // = TLB_LO[1/2]    32 bits
    // |-- PPN             20 bits
    // |-= mode             4 bits
    // | |-- nocache          1 bit
    // | |-- dirty            1 bit
    // | |-- valid            1 bit
    // | |-- global (kernel)  1 bit
    // |-= TLB reserved     8 bits
    // | |-- swapped          1 bit
    // | |-- (unused)         3 bit
    // | |-- cpu_id           4 bits
    
    ppn_t ppn;  // 32 bits
}

Process-dependent structures

struct pagetable_t {
    // dynamic array, start at size USERPRAM_SZ/PAGE_SZ 
    pt_elt_tarray pt_elts;
    struct lock *pt_lk;
}

struct addrspace {
    // TODO handle the stack boundary?
    vaddr_t stack_min;
    vaddr_t heap_max;    
    struct pagetable_t pt;
}

## Kernel-dependent structures
```c
// Corepage size is fixed at boot-time = USERRAM_SZ/PAGE_SZ 
// sizeof(struct coremap) 
// 512 KB RAM -> 512+  B coremap
// 512 MB RAM -> 512+ KB coremap 
struct coremap_t {
    struct cm_elt_t *cm_elts; 
    size_t cm_sz;
    
    // we have a total of k buckets with cm_sz/k elts each
    struct lock *cm_lks[COREMAP_LKS];
    // lets use the clock LFU approximation algorithm
    // points to the index of the map that will be a candidate for eviction
    // if used we evict it and update the clock_hand
    int clock_hand;
}

Swapdisk Bitmap

// Bitmap size is dynamic and increases at run-time
// sizeof(struct swapdisk_bitmap_t)
// 1 MB disk -> 128+ b = 16+ B bitmap max size
// 4 GB disk -> 1+ Mb = 128+ KB bitmap max size
struct swapdisk_bitmap_t {
    struct bitmap bm; 
    struct lock *bm_lk;
    struct vnode *bm_vn;
}

Macros and Interface prototypes

Note: MACROS use the actual struct, NOT a pointer.

Note: All functions are thread-unsafe, less noted otherwise.

#define CME_PPN(cme)            ((ppn_t)(&cme - &CME[0]))
#define CME_VPN(cme)            ((vpn_t)((cme).tlb_hi >> 12))
#define CME_PID(cme)            ((cme).tlb_hi & 0xfff)

#define PTE_PPN(pte)            ((ppn_t)((pte).tlb_lo >> 12))
#define PTE_ISNOCACHE(pte)      ((pte).tlb_lo >> 11 & 1)
#define PTE_ISDIRTY(pte)        ((pte).tlb_lo >> 10 & 1)
#define PTE_ISVALID(pte)        ((pte).tlb_lo >> 9 & 1)
#define PTE_ISKERNEL(pte)       ((pte).tlb_lo >> 8 & 1)
#define PTE_ISSWAPPED(pte)      ((pte).tlb_lo >> 7 & 1)
#define PTE_CPU(pte)            ((pte).tlb_lo & 0xf)

typedef uint64_t tlb_t;   // tlb_t should be 64 bits
typedef uint32_t ppn_t;   // Physcial page number type
typedef uint32_t vpn_t;   // Virtual Page Number tyle
typedef uint32_t spn_t;   // Swap Page Number Type


#define OFFSET_BITS 20
#define PN_OF_ADDR(ptr)         ((ptr) >> OFFSET_BITS)
#define ADDR_OF_PN(pn)          ((pn) << OFFSET_BITS)

#define CME(ppn)                (coremap->cm_elts[(ppn)])

/*
 * Helper functions
 */

/** Gets the pagetable entry for a given process and virtual address
 *
 */
inline struct pt_elt_t *pte_proc_vaddr(struct proc *p, vaddr_t ptr) {
	return &p->p_as.pt.pt_elts[PN(ptr)];
}

/** Looks up pagetable entry from coremap entry
 * @param cme[in] coremap entry to lookup
 * @return pagetable entry of page
 * @pre page is mapped in RAM by an active process
 */
inline struct pt_elt_t *cme_to_pte(struct cm_elt_t *cme) {
    struct proc *p = procvector->procs[cme->owner];
    struct pagetable_t *pt = p->p_as.pt;
    return pt.pt_elts[CME_VPN(cme)]; 
}

/** Looks up coremap entry from pagetable entry
 * @param[in] pte pagetable entry to lookup
 * @return coremap entry of page
 * @pre page is mapped in RAM by an active process 
 */
inline struct cm_elt_t *pte_to_cme(struct pt_elt_t *pte) {
    return CME(PTE_PPN(*pte));
}

/** Convert page mapping to TLB entry
 * @param[in] cme coremap entry of page
 * @param[in] pte pagetable entry of page
 * @return TLB entry from @pte and @cme
 * @pre the page is active and mapped by @pte to @cme
 */
tlb_t tlb_entry(struct cm_elt_t *cme, struct pt_elt_t *pte) {
    tlb_t retval;
    uint32_t tlb_lo = pte->tlb_lo & ~(0xff);  // clears the reserve bits
    uint32_t tlb_hi = cme->tlb_hi & ~(0x3f);  // clears the reserve bits

	// TODO we might want to handle the ASID

    join32to64(&tlb_hi, &tlb_lo, &retval);
    return retval;
}

/*
 * VM mapping functions
 */
 
/** Gets an open coremap page, evicitng if necessary
 * @return coremap entry of available page or NULL
 * 
 * Will evict page as necessary
 * May block on I/O
 */
struct cm_elt_t *alloc_cme() {
	// TODO lock coremap
  // TODO use clock to find nearest free page
  
  // TODO if clock wraps around and cannot find free page
  
  // else manually evict
  page_deactivate(cme, pte);
  
  // TODO update coremap and return cme
}


/** Updates coremap to map physical page entry to virtual page
 * @param[in,out] coremap entry to update
 * @param[in] ptr virtual address of page to map
 * @param[in] owner written to coremap entry
 * @return physical address that @ptr maps to
 * @pre @ptr is not mapped in RAM
 * @pre @cme is inactive
 * @post coremap refects new mapping
 */
inline paddr_t cm_map(struct cm_elt_t *cme, vaddr_t ptr, pid_t owner) {
    cme->tlb_hi = PN_OF_ADDR(ptr);
    cme->tlb_hi <<= 12;
    cme->tlb_hi |= (owner & 0xfff);
    
    return CME_PPN(cme) | (ptr & 0xfff);
}

/** Grabs physical memory to map virtual page
 * @param[in] pid user process id, 0 means kernel
 * @param[in] ptr virtual address of page to map
 * @param[in] writeable false if page is readonly
 * @return physical address that @ptr maps to
 * @pre @ptr is not mapped in RAM
 * @pre @ptr is not swapped to disk
 * @pre Process @pid is active or equals 0
 * @post coremap refects new mapping
 * @post Process @pid's pagetable reflect new mapping 
 *
 * Will evict page as necessary
 * May block on I/O
 */
paddr_t page_create(pid_t pid, vaddr_t ptr, int writable) {
    struct pt_elt_t *pte = pte_proc_vaddr(PROC(pid), ptr);
    struct cm_elt_t *cme = alloc_cme(); 
    
    ppn_t ppn = CM_PPN(cme);
    pte->tlb_lo = ppn << 12
   	
    // set valid bit
    pte->tlb_lo |= (1 << 9);
    
    if (writeable) {
    	pte->tlb_lo |= (1 << 10);
    }
    
	if (pid == 0) {
    	// set global bit
    	pte->tlb_lo |= (1 << 8);
    }
    
    // no need to save CPU, that info is in the proccess's kthread
    
	pte->owner = pid;
    
    return cm_map(cme, ptr, pid);
}

/** Sets up coremap to map virtual page
 * @param[in] pid user process id, 0 means kernel
 * @param[in] ptr virtual address of page to map
 * @return physical address that @ptr maps to
 * @pre @ptr is not mapped to RAM
 * @pre @ptr is swapped to disk
 * @pre Process @pid is active or equals 0
 * @post coremap refects new mapping
 * @post Process @pid's pagetable reflect new mapping in RAM
 *
 * Will evict page as necessary
 * May block on I/O
 */
paddr_t page_reactivate(pid_t pid, vaddr_t ptr) {    
    return cm_map(alloc_cme(), ptr, pid);
}


/** Removes a page from memory, writing to swap as neccessary
 * @param[in,out] cme coremap entry of page to deactivate
 * @param[in,out] pte coremap entry of page to deactivate
 * @pre @pte belongs to active process
 * @pre @cme's page is active and mapped by owner's pagetable
 * @post physical page is filled with deadbeef
 *
 * May block on I/O
 */
void page_deactivate(struct cm_elt_t *cme, struct pt_elt_t *pte) {
	if (PTE_ISDIRTY(pte)) {
    	KASSERT(PTE_ISSWAPPED(pte));
        swapout(CME_PPN(&cme), pte->spn);
    }

    pte->tlb_lo = 0;
    pte->spn = 0;
    
    
    cme->tlb_hi = 0;
    ppn_t ppn = CME_PPN(cme);
    fill_deadbeef(cme, PAGE_SZ);
    
}

Synchronization Policy

Lock ordering

We interact wth synchonization primitvies by the following order. We order by increasing acquisition pressure so that the critical section for high pressure synchronization primitives have smaller critical sections.

  • Locks (sorted by ascending acquisiton pressure)
    • I/O locks (TBD, this might be too impractical to enforce)
    • Pagetable Locks
    • Coremap locks ...
    • Big Locks
    • In case of tie, ascending address in memory
  • Spinlocks
    • Ordered by ascending address in memory
  • Atomic CAS, TAS, and other instructions

We can only acquire lock in ascending order (top-down). We free locks as necessary to enforce this invariant.

Coremap

If we use a lock for the coremap, it is necessary to acquire the lock for writes. It is sufficient to acquire the lock for reads, but is it necessary?

We might explore how CAS might help us avoid allocating an entire lock.

Pagetable

Because each process has its own pagetable, this is not quite the smae synchonization problem as airballons.

Roger: We could have a biglock for all pagetables. I just don't know if that is preferable or not.

A race condition we need to watch out for is the following:

Scenario

Assume TLB and memory are full

Page X and Y have the same VPN.

Process A has a TLB miss for an active, valid page (Page X) (in coremap and pagetable)

Process B has a TLB miss for an inactive, valid page (Page Y) swapped to disk.

The Race

Process B evicts page X from memory to swap disk (write to A's pagetable & coremap).

Process B installs page Y in memory (write to B's pagetable & coremap).

Process B installs the TLB entry for page Y (read B's pagetable).

Process A sets the TLB to map page X (read A's pagetable). (Is page X active?)

Process B now issues a read to page X when it should have read page Y.

Process A

Process

Following from A2, we use p->p_lk to protect process sturcutres (excluding) VM.

Swaptable

We lock our vnode I/O with st_lk.

TLB Management

Context Switch

On context switch we call the function vm_tlbshootdown_all (defined in "vm.h") '''c /** Invalidates all tlb entries in the current cpu.

  • @post all tlb entries are invalidated for the current cpu

  • Atomic at Machine level */ void vm_tlbshootdown_all(void) { // TODO inter-CPU shootdown - Is it necessary? int spl = splhigh(0);

    for (int i = 0; i < NUM_TLB; i++) tlb_write(TLBHI_INVALID, TLBLO_INVALID, i); splx(spl); }


## TLB Fault
```c
/** Handles TLB fault
  * @pre page is not in TLB
  * @param[in] faulttype type of fault
  * @param[in] ptr pointer to virtual address
  * @return 0 on success, errno descriptor on failure
   *
  * Atomic at thread level
  */ 
int vm_fault(int faulttype, vaddr_t ptr) {	
    int err = 0;
    switch (faulttype) {
	    case VM_FAULT_READONLY:
	    case VM_FAULT_READ:
	    case VM_FAULT_WRITE:
        	struct pt_elt_t *pte = pte_proc_vaddr(curproc, ptr);
    		if (pte_to_cme(pte) == NULL) 
    			// bring page to memory
    			err = page_handler(pte);
 
                
            KASSERT(pte_to_cme(pte) != NULL);
             
    		if TLB does not have empty slot
    			evict random page from TLB 
               
    		insert new page into that slot with tlb_write
    
		break;
	    default:
			err = EINVAL; 
	}
    return print_err(err);  // TODO standardize error handling
}

Pagetable Management

/** Handles Page fault
  * @param[in] pte page table entry
  * @pre page is not in TLB
  * @return 0 on success, errno descriptor on failure
  *
  * Atomic at thread level
  */ 
int page_handler(struct pt_elt_t *pte) {
  	int err;
	// grab coremap lock
	// search coremap for empty slot
    // if no empty slot, run paging daemon
    // reserve the slot
    // release core map lock
    
    err = swapcopyin(cm_slot, sidx);
    // update VPN -> PPN in Page Table
    return print_err(err);
}

Dynamic Pagetable management

We are using a dynamically allocated page table array for every address space. The odd indexes of the array correspond to heap v. addresses and the even indexes of the array correspond to stack v. addresses. That way we do not need to use 2-level page tables.

vpn_to_pt_idx(x) = if even then (x/2) else (n-(x/2 + 1)
pt_idx_to_vpn(x) = if x < HALF then (2x) else (2(x+n)-1)


(  0  ,  1  ,  2  , ... , n-2 , n-1 )
maps =>
(  0  , n-1 ,  1  , n-2 ,  2  , ... )

Swap Management

Errors

The main data structure used for swap management is the "swapdisk_bitmap_t". It has a global lock and use the "lhdraw0:" disk.

/** Swapout updates the contents of the swap page on disk
 *  @pre assumes the page is dirty
 *  @pre assumes the page has spn @sidx
 *
 * thread-safe with respect to swapdisk
 */
void
swapcopyout(ppn_t *ppn, spn_t sidx) {  
  struct uio u;
  struct iovec iov;

  iov.iov_ubase = ADDR_OF_PN(ppn);
  iov.iov_len = PAGE_SZ;
  u.uio_iov = &iov;
  u.uio_iovcnt = 1;
  u.uio_resid = PAGE_SZ;  // amount to read from the file
  u.uio_segflg = UIO_USERSPACE;
  u.uio_rw = UIO_WRITE;
  u.uio_space = curproc->p_addrspace;
  
  // set the position to write to based on the idx
  u.uio_offset = sidx * PAGE_SZ;

  lock_acquire(swapdisk_bitmap->bm_lk);
  VOP_WRITE(swapdisk->bm_vn, uio);
  lock_release(swapdisk_bitmap->bm_lk0;
}

/** set memory contents to that of swap space
 * @pre assumes there is a page to cpy from swap space to @ppn
 * @pre @ppn belongs to the process and is already alloced in the coremap
 *
 * thread-safe with respect to swapdisk
 */
void
swapcopyin(ppn_t *ppn, spn_t sidx) {
    struct uio u;
    struct iovec iov;
  
    iov.iov_ubase = ADDR_OF_PN(ppn);
    iov.iov_len = PAGE_SZ;
    u.uio_iov = &iov;
    u.uio_iovcnt = 1;
    u.uio_resid = PAGE_SZ;  // amount to read from the file
    u.uio_segflg = UIO_USERSPACE;
    u.uio_rw = UIO_WRITE;
    u.uio_space = curproc->p_addrspace;
    
    // set the position to write to based on the idx
    u.uio_offset = sidx * PAGE_SZ;
  
    lock_acquire(swapdisk_bitmap->bm_lk);
    VOP_READ(swapdisk->bm_vn, uio);
    lock_release(swapdisk_bitmap->bm_lk0;
}

/** Finds free n contiguous swap pages in disk
 *  @return -1 for no space, starting index for most pages
 *  @post updates swap bitmap to reflect new relationship 
 */
spn_t 
swapalloc(int npages) {

}

/** Frees npages of swap starting at sidx
 *  @param[in] sidx starting idx
 *  @param[in] npages number of pages to free
 *  @return Does not fail
 */
void 
swapdealloc(spn_t sidx, int npages) {
	// lock swap space
    // free pages and set them

}

Daemon

This is a thread forked on startup and specified in vm_daemon_thread.

void

File IO

Bootstrapping

On vm_bootstrap we need to create a coremap that will keep track of the empty and allocated physical pages for us. The coremap will be allocated at the first few spaces of our vm space which will not be virtually mapped.

In order to find the size of the coremap, we need to check how big our physical space is and get the last physical address by calling

lastpaddr = ram_getsize().

Our VM starts at address 0, so the total number of pages we have is: NPAGES = lastpaddr/PAGE_SIZE // integer division

Our coremap will occupy the first sizeof(struct coremap_elt) * NPAGES bytes.

// vm.h
// flag to check whether vm has been initialined, our implementation of kmalloc depends on this
static bool vm_initialized;


/** bootstraps ram
  *
  */
  
static
ram_bootstrap() {
	+ vm_initialized = false;

}



// vm.h
/** called after ram_bootstrap
 *  initializes the coremap
 *  excludes itself from the mapped pages
 *  @pre firstpaddr and lastpaddr have not been invalidated
 *  @post firstpaddr and lastpaddr are invalidated
 */
void vm_bootstrap() {
    
    paddr_t lastpaddr = ram_getsize();
	paddr_t firstpaddr = ram_getfirstfree();
    unsigned total_pages = (firstpaddr - lastpaddr)/PAGE_SZ;
    unsigned coremap->cm_sz = total_pages * PAGE_SZ/(PAGE_SZ + sizeof(cm_elt_t))
    
    // initialize corem
    coremap->cm_elts = (cm_elt_t *)(firstaddr); 
    
    for (i = 0; i < coremap->cm_sz; ++i)
        coremap->cm_elts[i] = {};
    
    vm_initalized = true;
    // kmalllc uses the core map from this point 
    for (int i = 0; i < COREMAP_LKS; ++i)
        coremap->cm_lks[i] = lock_create(“cm lock”);
        if (coremap->cm_lks[i] == NULL)
            panic(“could not create coremap lock”);
}

void swapdisk_bootstrap() {
    swapdisk_bitmap_t *swapdisk_bitmap;

    // use lhdraw0 disk as the swap space
    err = vfs_open(“lhdraw0:”, flags, 0644, &swapdisk_bitmap.vn);
    if (err)
        panic(“swapdisk_bootstrap failed”);
    
    // get the size of the disk
    struct stat s;
    VOP_STAT(swapdisk_bitmap->bm_vn, &s);
    off_t nbits = s.st_size;

    // allocate nbits for the bitmap
    swapdisk_bitmap->bm = bitmap_create(nbits);
    swapdisk_bitmap->bm_lk = lock_create(“bitmap lock”);
    if (“swapdisk_bitmap->bm_lk” == NULL)
    panic(“swapdisk_bootstrap failed: cannot create bm lock”);
}

// Helper functions for the swapspace found in swap.c?
set_swaping_idx(unsigned pa_idx, unsigned swaping_idx, struct addrspace as);
unsigned get_swaping_idx(unsigned pa_idx, struct addrspace as);
bool has_swaping_idx(unsigned pa_idx, struct addrspace as);

vm_daemon_thread() {
    // updates the daemon idx field in coremap struct
    next_daemon_idx(coremap);
    
    lock_acquire(swapdisk_bitmap->bm_lk)
    pid_t owner = CME(coremap.daemon_idx).owner
    
    unsigned swaping_idx;
    
    if (!has_swaping_idx(coremap.daemon_idx, procvector->procs[owner]->p_addrspace))
        bswaping_idx = swapdisk_find_freeidx();
    lock_acquire(procvector->procs[owner]->p_addrspace->pt->pt_lk);
    // update swaping idx in addrspace and swaping bit in coremap elt
    set_swaping_idx(coremap.daemon_idx, sing_idx, procvector->procs[owner]->p_addrspace);
    
    lock_release(procvector->procs[owner]->p_addrspace->pt->pt_lk);
    else
        swaping_idx =
    get_swaping_idx(coremap.daemon_idx,procvector->procs[owner]->p_addrspace)
        
    
    // TODO: do proper write with uio objects
    VOP_WRITE(swapdisk_bitmap->bm_vn, idx * PAGE_SZ);
    lock_release(swapdisk_bitmap->bm_lk)
}

sys_sbrk

int sys_sbreak(intptr_t amount, int *retval) {
	if (amount == 0) {
    	// simple value return
        //*retval =  curproc->p_as->break
        return 0;
    }
    //TODO
    // get npages we need to add to our heap
    
    // Free or create pages as needed
    // if we cant find a new page, ENOMEM (retval gets 1)
	// if amount + current val < 0, EINVAL
}

Address Space API

/** Initializes addrspace
 */
struct addrspace *as_create(void) {
  // initialize pt_elets array at size USERPRAM_SZ/PAGE_SZ
  // create the pt_lk
}


/** Copies addrspaces
 *  @param[in] src
 *  @param[in] dst
 *  @return error
 */
int
as_copy(struct addrspace *src, struct addrspace **ret) {

    // grap the addrspace lock of the src
    // foreach multipage allocation in the page table of src
    // create a page in swapdisk for the new proc
    // if failure at any point
      // release src lock
        as_destroy(ret);
}

/** Invalidates all TLB entries
 *  @param[in] src
 *  @param[in] dst
 *  @return error
 */
void as_activate(void) {
    vm_tlbshootdown_all();

}

/** Deactivates current TLB entries
 *
 */
void  as_deactivate(void) {
}

/** Destroys addrspace
 *  We should free all proces pages that have not been
 *  freed in swap bitmap and the coremap.

 *  @param[in] src
 *  @param[in] dst
 *  @return void
 */
void as_destroy(struct addrspace *) {
    // for each element in the page table, destroy the element
    // free the corresponding swap space
    // free the core map
}

/** Set up a segment at virtual address VADDR of size MEMSIZE.
 *  The segment in memory extends from VADDR up to (but not
 *  including) VADDR+MEMSIZE.
 *
 *  The READABLE, WRITEABLE, and EXECUTABLE flags are set if
 *  read write, or execute permission should be set on the
 *  segment.
 *  @param[in] as addrespace
 *  @param[in] vaddr
 *  @param[in] sz
 *  @param[in] readable permissions
 *  @param[in] writeable permissions
 *  @param[in] executable permissions
 */
int as_define_region(struct addrspace *as,
                      vaddr_t vaddr, size_t sz,
                      int readable,
                      int writeable,
                      int executable) {
     // for every entry in the pagetable, set the write bits
     // do not set the

}

/** set the permissions of the addrspace table as read and write to prepare for load
 *  as_complete_load will restore permissions to whatever they were before
 *  @param[in] as addrespace
 *  @return error
 */
int as_prepare_load(struct addrspace *as) {

}

/** restore permissions to whatever they were before as_prepare_load
 *  @param[in] as addrespace
 *  @return error
 */
int as_complete_load(struct addrspace *as) {


}

/** Sets the top of the stack
 *  @param[in] as addrespace
 *  @param[in,out] initstackptr stack ptr to set
 *  @return error
 */
int as_define_stack(struct addrspace *as, vaddr_t *initstackptr) {

    *initstackptr = USERSTACK;
    return 0;
}

Kernel allocation

Coremap representation

Kernel allocations over multiple pages are labeled such that the first page has the big set, and subsequent pages of an allocation have the bit unset.

Consider the following kmalloc calls

...
kmalloc(3*4096);
kmalloc(1*4096);
kmalloc(2*4096);
kmalloc(1*4096);
...

Here are the multipage_start bits of the following contiguous physical pages from cm_elts[i].tlb_hi:multipage_start

... | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | ...

kmalloc

Do we alloc pages before setting up the VM? We shouldn’t!!!

  • What if we have space in an existing page?
    • Let’s setup a ref count of objects for each page, we can free when its zero
    • we should stuff pages when we can
  • Do we start a new page?
    • Hopefully not, we want to save space
/** Gets npages from virtual memory
  * Never shifts pages around. If there are not n contiguous pages in memory we just return null.
  * @return Null
  */
static
paddr_t
getppages(unsigned long npages)
{
	paddr_t addr;
	
    if (!vm_initialized) {
      spinlock_acquire(&stealmem_lock);
  
      addr = ram_stealmem(npages);
  
      spinlock_release(&stealmem_lock);
    } else {
    	// linear greedy search for contiguous free pages
        int pages_left = npages;
        int start_idx = 0;
        
        //TOOD: locking, which depends on our coremap implementation
        
        
        for (int i = 0; i < MAX_PPN; i++ && pages_left > 0; i++) 		 {
             if ( CME_ISFREE(CME(i)) ) {
                    pages_left--;
                    CME_RESERVE(CME(i));
            }
            else {
                pages_left = npages;
                start_idx = i;
            }
          }
        
        // we did not find enough pages
        if (pages_left > 0) {
	        // ENOMEM?
            return NULL;
        }
        
        // setup page structure
        kalloc_startpage(start_idx);
        for (int i = start_idx+1; i < start_idx + npages; i++) {
        kalloc_multipage(i);
        }
    
        return ADDR_OF_PN(start_idx);
    
    }
	return addr;
}

kfree

  • How do we free multiple pages? Do we keep track of next in our core map?
    • we know a multipage allocation is contiguous in virtual memory, we can therefore find out all the pages we need to free
  • Mark the page as free
    • USE THIS: as_zero_region coremap_elt->address_space = NULL
  • do TLB shootdown

kfree is called on a page with the multipage flag unset, return error

Otherwise, kfree will free the current page and all following pages until the multipage flag is set again

void kfree(void *ptr) {
    if (ptr == NULL) {
            return;
    }
    unsigned int ppn = PN_OF_ADDR(ptr);
    cm_elt_t cme = CME(ppn);
    
    if (!CME_ISMULTIPAGE(cme)) {
        return EINVAL;
    }
    
    do {
        free_kpages(ppn);
    cme_deactivate(cme);
    ppn++;
    cme = CME(ppn);
    } while (CME_ISMULTIPAGE(cme) && ppn <= PPN_MAX);

}

Statistics and Performance Analysis

  • TLB Hit Rate = # TLB Hits / # TLB Accessses (should be ~98%)

"Let's page to the cloud"

https://www.dropbox.com/developers/core/docs#files_put

Other TODOs

error handling page after sbrk should be marked as invalid daemon only writes a page to disk if it’s already there if it’s not there just wait for forced eviction to put it there

when destroying the address space, we should delete from swap when we free we should delete from swap

A3 Design Document: Virtual Memory

Questions

TLB Questions

Problem 1 (5 points)

Assuming that a user program just accessed a piece of data at (virtual) address X, describe the conditions under which each of the following can arise. If the situation cannot happen, answer "impossible" and explain why it cannot occur.

TLB miss, page fault

  • user/kernel proc is running and the page requested is not in the TLB and the page is not in memory TLB miss, no page fault
  • user/kernel proc is running and the page is still in memory but not in the tlb TLB hit, page fault
  • impossible
  • if the valid bit is not set then it is not a hit TLB hit, no page fault
  • this is the best case, the page is in memory and mapped in the TLB

Problem 2 (2 points)

A friend of yours who foolishly decided not to take 161, but who likes OS/161, implemented a TLB that has room for only one entry, and experienced a bug that caused a user-level instruction to generate a TLB fault infinitely—the instruction never completed executing! Explain how this could happen. (Note that after OS/161 handles an exception, it restarts the instruction that caused the exception.)

  • We need to have a page in TLB
  • instruction pointer memory needs TLB too
la ($a0), $a1 // int a = *0x8000000;

Does kernel needs a TLB entry?

  • No all kernel memory is unmapped in our implmentation

Problem 3 (3 points)

How many memory-related exceptions (i.e., hardware exceptions and other software exceptional conditions) can the following MIPS-like instruction raise? Explain the cause of each exception.

load word from $0 (zero register), offset 0x120, into register $3

lw  $3, 0x0120($0)

Exceptions at the MIPS level

  • #define EX_TLBL 2 /* TLB miss on load */ (permissions)
  • #define EX_ADEL 4 /* Address error on load */

Exceptions at the OS161 level: segfault (accesses illegal memory)

Malloc Questions

Question 1. Consider the following (useless) program:

/* This is bad code: it doesn't do any error-checking */
#include <stdio.h>
int main (int argc, char **argv) {
    int i;
    void *start, *finish;
    void *res[10];
    start = sbrk(0);
    for (i = 0; i < 10; i++) {
        res[i] = malloc(10);
    }
    finish = sbrk(0);
    /* TWO */
    return 0;
}

How many times does the system call sbrk() get called from within malloc()?

Once, the first malloc gets the initial page, then other malloc calls all use the memory allocated by the first page

On the i386 platform, what is the numeric value of (finish - start)? 4 KB (0x1000)

Question 2. Suppose that we now insert the following code at location /* TWO */:

{
    void *x;
    free(res[8]); free(res[7]); free(res[6]);
    free(res[1]); free(res[3]); free(res[2]);
    x = malloc(60);  /* MARK */
}

Again on the i386, would malloc() call sbrk() when doing that last allocation at the marked line above? What can you say about x?

No, a page is 4KB, and we are using less than 100 bytes. We know that res[9] < x < sbrk(0)

Question 3. It is conventional for libc internal functions and variables to be prefaced with "__". Why do you think this is so?

If we use the "__" prefix we can directly access protected variables and write code that requires more privilege. It should be helpful to the programmer.

Question 4. The man page for malloc requires that "the pointer returned must be suitably aligned for use with any data type." How does our implementation of malloc guarantee this?

Currently, we assign a new page each time we call malloc, even to malloc 1 byte. Each malloc therefore therefore is 4KB aligned.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment