main.c

Home   »   main.c

#include 
#include 
#include 
#include 

#include "testcases.h"

/*
* syscall() and signal 
* specific headers
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

void *buff;
unsigned long nr_signals = 0;

#define PAGE_SIZE (4096)

/*
 * 			placeholder-3
 * implement your page replacement policy here
 */

// Helper Macros
#define GetVpnFromVpa(vpa) ((vpa) >> 12)
#define GetPfnFromPte(pte) ((pte)&0x7FFFFFFFFFFFFFL)
#define IsSwappedOut(pte) ((pte >> 62) & 1)
#define GetNormalizedAddress(vpn) (vpn-start_vpn)
#define GetUnNormalizedAddress(vpn) (vpn+start_vpn)

// heap macros
#define LeftChild(x) ((x<<1) | 1)
#define RightChild(x) (LeftChild(x) + 1)
#define Parent(x) ((x-1)>>1)

// constants
#define LRU_LIST_UPDATE_FREQUENCY_IN_SEC 5
#define FREE_MEM_THRESHOLD (1 << 20)
#define PAGE_COUNT (TOTAL_MEMORY_SIZE / PAGE_SIZE + (TOTAL_MEMORY_SIZE % PAGE_SIZE == 0 ? 0 : 1))
#define SIGBALLOON 40

// definitions of shared data-structures

sig_atomic_t entry_flag;
unsigned long start_vpn;

/**
 * @brief 
 * This array holds vpn to pfn mapping 
 * which will reduce the number of syscalls
 * needed to translate vpn to pfn
 * need to invalidate this entry when we 
 * swap a page
 */
typedef struct pte_cache_entry
{
	unsigned long pte;
	short valid;
} pte_cache_entry_t;

pte_cache_entry_t pte_cache[PAGE_COUNT];

/**
 * @brief 
 * contains entry for each page
 * higher the score more the chances
 * that page will be accessed in the 
 * near future
 */
typedef struct {
	unsigned int score;
	// unnormalized vpn
	unsigned long vpn;
} lru_list_entry_t;

lru_list_entry_t lru_list[PAGE_COUNT];

/**
 * @brief ith entry stores the index at which 
 * the heap_node for ith page can be found in 
 * the lru_list.
 */
size_t lru_list_lookup[PAGE_COUNT];


// function definations

/**
 * @brief
 * A helper function to maintain a min_heap
 * 
 * @returns
 * -1 on error
 * 0 otherwise
 */
int min_heapify(size_t pos){
	if(pos<0 || PAGE_COUNT<=pos)
		return -1;
	size_t minn = pos;
	if(LeftChild(minn) < PAGE_COUNT && lru_list[minn].score > lru_list[LeftChild(minn)].score)
		minn = LeftChild(minn);
	
	if(RightChild(minn) < PAGE_COUNT && lru_list[minn].score > lru_list[RightChild(minn)].score)
		minn = RightChild(minn);
	
	if(minn!=pos){
		lru_list_entry_t temp = lru_list[pos];
		lru_list[pos] = lru_list[minn];
		lru_list[minn] = temp;
		//also, update lru_list_lookup
		lru_list_lookup[GetNormalizedAddress(lru_list[minn].vpn)] = minn;
		lru_list_lookup[GetNormalizedAddress(lru_list[pos].vpn)] = pos;
		return min_heapify(minn);
	}

	return 0;
}

/**
 * @brief
 * organize the content of lru_list in 
 * min_heap. It also, updates lru_list_lookup
 * accordingly.
 * 
 * This function expects that lru_list has been
 * initialized with ith location containing heap_node
 * of ith page. It also expects that lru_list_lookup 
 * is consistent with lru_list.
 * 
 * @returns
 * -1 on error
 *  0 otherwise
 */
int build_min_heap(){
	int ret;
	for(size_t i = (PAGE_COUNT>>1) - 1; i>=0; i--)
		if(ret = min_heapify(i))
			return ret;
	return 0;
}

/**
 * @brief
 * increases the score of the lru_list entry
 * and then enforce the min_heap invariant.
 * 
 * @param
 * vpn: unnormalized vpn for which the score is to be increased
 * new_score: the score which is to be assigned
 **/
int increase_score(unsigned long vpn, unsigned int new_score){
	vpn = GetNormalizedAddress(vpn);
	if(vpn<0 || PAGE_COUNT<=vpn)
		return -1;

	unsigned int old_score = lru_list[lru_list_lookup[vpn]].score;
	if(new_scoreold_score)
		return -1;

	size_t cur = lru_list_lookup[vpn];
	lru_list_entry_t temp = lru_list[cur];
	temp.score = new_score;
	while(cur>0 && lru_list[Parent(cur)].score > new_score){
		lru_list[cur] = lru_list[Parent(cur)];
		lru_list_lookup[GetNormalizedAddress(lru_list[cur].vpn)] = cur;
		cur = Parent(cur);
	}

	lru_list[cur] = temp;
	lru_list_lookup[GetNormalizedAddress(lru_list[cur].vpn)] = cur;

	return 0;
}


/**
 * @brief
 * updates the score of the lru_list entry
 * and then enforce the min_heap invariant.
 * 
 * @param
 * vpn: unnormalized vpn for which the score is to be increased
 * new_score: the score which is to be assigned
 **/
int update_score(unsigned long vpn, unsigned int new_score){
	unsigned long nvpn = GetNormalizedAddress(vpn);
	if(nvpn<0 || PAGE_COUNT<=nvpn)
		return -1;

	unsigned int old_score = lru_list[lru_list_lookup[nvpn]].score;
	
	if(old_score < new_score)
		return increase_score(vpn, new_score);
	else if(old_score > new_score)
		return decrease_score(vpn, new_score);

	return 0;
}

/**
 * @brief
 * returns the amount of available 
 * free memory in KB
 */
unsigned long calc_free_mem()
{
	struct sysinfo info;
	if (sysinfo(&info))
	{
		perror("[calc_free_mem] sysinfo returned nonzero code: ");
		exit(1);
	}
	return info.freeram >> 10;
}

/**
 * @brief 
 * This function translates unnormalized vpn to pte and 
 * stores the resule into pte_cache
 * 
 * @return
 * -1 on error
 *  0 otherwise
 */
int get_pte(unsigned long vpn, unsigned long *pte)
{
	unsigned long _pte = 0;
	static int pagemap_fd;

	if (vpn < start_vpn || vpn >= start_vpn + PAGE_COUNT)
	{
		printf("[get_pte] Invalid vpn\n");
		return -1;
	}

	if (pte == NULL)
	{
		printf("[get_pte] Invalid pfn\n");
		return -1;
	}

	if (pte_cache[vpn - start_vpn].valid)
	{
		*pte = pte_cache[vpn - start_vpn].pte;
		return 0;
	}

	if (!pagemap_fd)
		pagemap_fd = open("/proc/self/pagemap", O_RDONLY);

	if (pagemap_fd < 0)
	{
		perror("[get_pte] Unable to open pagemap file: ");
		return -1;
	}

	unsigned long seek_offset = vpn * 8;
	if (pread(pagemap_fd, &_pte, sizeof(_pte), seek_offset) != sizeof(_pte))
	{
		perror("[get_pte] Failed to read pfn: ");
		return -1;
	}

	pte_cache[vpn - start_vpn].pte = _pte;
	pte_cache[vpn - start_vpn].valid = 1;

	*pte = _pte;

	return 0;
}

/**
 * @brief 
 * this function reads the idle bit from 
 * "/sys/kernel/mm/page_idle/bitmap" and
 * return it
 * @returns -1 on error
 */
int is_idle(unsigned long vpn)
{
	unsigned long pfn;
	unsigned long pte;
	if(get_pte(vpn, &pte)){
		printf("[is_idle] Error in get_pte.\n");
		return -1;
	}
	pfn = GetPfnFromPte(pte);
	
	static int idle_fd;
	if (!idle_fd)
		idle_fd = open("/sys/kernel/mm/page_idle/bitmap", O_RDONLY);

	if (idle_fd < 0)
	{
		perror("[is_idle] Unable to open page_idle file: ");
		return -1;
	}

	unsigned long seek_offset = (pfn >> 6) << 3;
	unsigned long entry;
	if (pread(idle_fd, &entry, sizeof(entry), seek_offset) != sizeof(entry))
	{
		perror("[is_idle] Unable to read the entry from the page_idle file: ");
		return -1;
	}

	return (entry >> (pfn & 63)) & 1;
}

/**
 * @brief 
 * this function sets the idle bit in
 * "/sys/kernel/mm/page_idle/bitmap"
 */
int set_page_idle(unsigned long vpn)
{
	unsigned long pfn;
	unsigned long pte;
	if(get_pte(vpn, &pte)){
		printf("[is_idle] Error in get_pte.\n");
		return -1;
	}
	pfn = GetPfnFromPte(pte);

	static int idle_fd;
	if (!idle_fd)
		idle_fd = open("/sys/kernel/mm/page_idle/bitmap", O_RDWR);

	if (idle_fd < 0)
	{
		perror("[set_page_idle] Unable to open page_idle file: ");
		return -1;
	}

	unsigned long seek_offset = (pfn >> 6) << 3;
	unsigned long entry;
	if (pread(idle_fd, &entry, sizeof(entry), seek_offset) != sizeof(entry))
	{
		perror("[set_page_idle] Unable to read the entry from the page_idle file: ");
		return -1;
	}

	unsigned long old_entry = entry;

	if ((entry >> (pfn & 63)) & 1)
		return 0;

	entry |= 1ULL << (pfn & 63);

	assert(entry!=old_entry);

	if (pwrite(idle_fd, &entry, sizeof(entry), seek_offset) != sizeof(entry))
	{
		perror("[set_page_idle] Unable to read the entry from the page_idle file: ");
		return -1;
	}

	return 0;
}


/**
 * @brief 
 * \return
 * 1 if vpn is swapped out
 * 0 if not
 * -1 in error
 */
int is_swapped_out(unsigned long vpn)
{
	unsigned long pte;
	if(get_pte(vpn, &pte)){
		printf("[is_idle] Error in get_pte.\n");
		return -1;
	}
	return IsSwappedOut(pte);
}

/**
 * @brief 
 * This function need to be invoked at 
 * some regular interval
 */
void update_lru_score()
{
	// disable the timer
	struct itimerval it_val;
	it_val.it_value.tv_sec = 0;
	it_val.it_value.tv_usec = 0;
	it_val.it_interval = it_val.it_value;

	if (setitimer(ITIMER_REAL, &it_val, NULL))
	{
		perror("[update_lru_score] Failed to disable the timer...");
		exit(1);
	}

	if(!entry_flag)
		/**
		 * sigballon_handler is under execution. 
		 * So, just return. Otherwise we risk 
		 * corrupting the shared state.
		 */
		return;
	/** 
	 * If SIGBALLOON is received 
	 * at this point it's handler will
	 * execute fully.
	 */
	entry_flag = 0;

	/** 
	 * But, if SIGBALLOON is received 
	 * at this point it's handler will
	 * return just from beginning.
	 */
	
	printf("[update_lru_score] starting to update lru score...\n");
	for(int i=0; i>1;
		// clear first 2 MSBs
		new_score &= 0x3fffffff;
		// set MSB if page is swapped out
		new_score |= swapped_out << 31;
		/** set 2nd MSB if page is not accessed 
		 *  after last score update
		 */
		new_score |= active << 30;
		
		if(update_score(vpn, new_score))
			printf("[update_lru_score] Failed to update_score.\n");
		
		if(!swapped_out && set_page_idle(vpn))
			printf("[update_lru_score] Failed to set_page_idle.\n");
	}
	
	printf("[update_lru_score] done updating lru score...\n");
	
	//release lock
	entry_flag = 1;

	// enable the timer
	it_val.it_value.tv_sec = LRU_LIST_UPDATE_FREQUENCY_IN_SEC;
	it_val.it_value.tv_usec = 0;
	it_val.it_interval = it_val.it_value;

	if (setitimer(ITIMER_REAL, &it_val, NULL))
	{
		perror("[update_lru_score] Failed to disable the timer...");
		exit(1);
	}

	//if free memory is below the threshold then invoke sigballoon_handler.
	if(calc_free_mem()>2;
	unsigned long free_page_threshold = FREE_MEM_THRESHOLD>>2;
	
	if(free_page_threshold <= free_pages){
		printf("[sigballoon_handler] Returning without freeing any memory because free_page_threshold=%lu, free_pages=%lu...\n", free_page_threshold, free_pages);	
		entry_flag = 1;
		return;
	}

	unsigned long nr_pages = free_page_threshold - free_pages;

	printf("[sigballoon_handler] Trying to free %lu memory pages...\n", nr_pages);	

	int ret = swapout_pages(nr_pages);

	if (ret==-1)
	{
		printf("[sigballoon_handler] Error in swapout_pages.\n");
	}else{
		printf("[sigballoon_handler] %d pages swapped out.\n", ret);
	}

	entry_flag = 1;
}

/**
 * @brief 
 * initialize the data structures and 
 * register the signal handlers.
 */
void sigballoon_init(int *ptr)
{
	start_vpn = GetVpnFromVpa((unsigned long)ptr);
	memset(pte_cache, 0, sizeof(pte_cache));

	entry_flag = 1;

	// initialize lru_list
	for(size_t i=0; i

Leave a Reply

Your email address will not be published. Required fields are marked *