Demand Paging with 2-level Hierarchical Page Table.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <limits.h>

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)

struct list_head {
	struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_reverse - iterate backwards over list of given type.
 * @pos:	the type * to use as a loop counter.
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_reverse(pos, head, member)			\
	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
	     &pos->member != (head); 	\
	     pos = list_entry(pos->member.prev, typeof(*pos), member))

/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @pos:	the type * to use as a loop counter.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_entry((head)->next, typeof(*pos), member),	\
		n = list_entry(pos->member.next, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_for_each_entry_safe_continue -	iterate over list of given type
 *			continuing after existing point safe against removal of list entry
 * @pos:	the type * to use as a loop counter.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe_continue(pos, n, head, member) 		\
	for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
		n = list_entry(pos->member.next, typeof(*pos), member);		\
	     &pos->member != (head);						\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 *				      removal of list entry
 * @pos:	the type * to use as a loop counter.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
		n = list_entry(pos->member.prev, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))

/**
 * list_prepare_entry - prepare a pos entry for use as a start point in
 *			list_for_each_entry_continue
 * @pos:	the type * to use as a start point
 * @head:	the head of the list
 * @member:	the name of the list_struct within the struct.
 */

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next) {
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head) {
	__list_add(new, head, head->next);
}

static inline void list_add_tail(struct list_head *new, struct list_head *head) {
	__list_add(new, head->prev, head);
}

static inline void __list_del(struct list_head * prev, struct list_head * next) {
	next->prev = prev;
	prev->next = next;
}

static inline void list_del(struct list_head *entry) {
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

static inline void list_del_init(struct list_head *entry) {
	__list_del(entry->prev, entry->next);
	INIT_LIST_HEAD(entry);
}

static inline void list_move(struct list_head *list, struct list_head *head) {
        __list_del(list->prev, list->next);
        list_add(list, head);
}

static inline void list_move_tail(struct list_head *list,
				  struct list_head *head) {
        __list_del(list->prev, list->next);
        list_add_tail(list, head);
}

static inline int list_empty(const struct list_head *head) {
	return head->next == head;
}

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define list_for_each(pos, head) \
  for (pos = (head)->next; pos != (head);	\
       pos = pos->next)

#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
        	pos = pos->prev)

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

#define list_for_each_entry_reverse(pos, head, member)			\
	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
	     &pos->member != (head); 	\
	     pos = list_entry(pos->member.prev, typeof(*pos), member))

#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_entry((head)->next, typeof(*pos), member),	\
		n = list_entry(pos->member.next, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
		n = list_entry(pos->member.prev, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))


#if 0    //DEBUG
#define debug(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define debug(fmt, args...)
#endif

#define PAGESIZE (32)
#define PAS_FRAMES (256) //fit for unsigned char frame in PTE
#define PAS_SIZE (PAGESIZE*PAS_FRAMES) //32*256 = 8192 B
#define VAS_PAGES (64)
#define VAS_SIZE (PAGESIZE*VAS_PAGES) //32*64 = 2048 B
#define PTE_SIZE (4) //sizeof(pte)
#define PAGETABLE_FRAMES (VAS_PAGES*PTE_SIZE/PAGESIZE) //64*4/32 = 8 consecutive frames
#define PAGE_INVALID (0)
#define PAGE_VALID (1)
#define MAX_REFERENCES (256)
typedef struct{
    unsigned char frame; //allocated frame
    unsigned char vflag; //valid-invalid bit
    unsigned char ref; //reference bit
    unsigned char pad; //padding
} pte; // Page Table Entry (total 4 Bytes, always)

 
typedef struct{
    int pid;
    int ref_len; //Less than 255
    unsigned char *references;
	int process_page_faults;
	int process_references;
	int alloc_frame;
    struct list_head job, ready;
	
} process_raw;

typedef struct {
    unsigned char b[PAGESIZE];
} frame;

    process_raw *cur, *next;	//연결리스트를 돌며 특정 list를 지정하기 위한 변수
	pte *pte_ptr, *pte_ptr2;	//pte 찾기 위한 포인터
	frame *pas;

    LIST_HEAD(job_q);	//list_head job_q 선언 및 초기화
	LIST_HEAD(ready_q);	//list_head ready_q 선언 및 초기화

    int process_count = 0; //이진 파일로부터 읽어들인 process수를 세기 위한 변수
	int base_res = 0; // base register를 저장하기 위한 변수
	int ref_count = 0; //simulator 구현시 각 프로세스별로 순차적으로 reference를 한번씩 돌아가며 실행해주게 구현하였음.이 때 현재 실행해야할 reference를 찾기위한 변수. 과제 1, 2의 clock역할.
	int frame_count = -1; //frame_count - 할당 해야할 프레임 위치를 찾기 위한 변수
	int total_page_faults = 0; //전체 page faults를 저장하기 위한 변수. total_ 변수는 total값을 구할 때 따로 다시 queue를 돌며 합산하여 시간이 걸리지 않도록 하기위하여 따로 변수를 만들어놈.
	int total_references = 0; //전체 references를 저장하기 위한 변수.
	int num = 0; //pas 상세 frame를 찾기위한 변수

void IO_task(){	//binary형태의 파일을 읽어들여 job_q에 저장
	while(fread(cur = malloc(sizeof(process_raw)), sizeof(int), 2, stdin) == 2){    //pocess구조체의 크기를 동적할당 받아 int형 변수 3개에 값을 차래대로 대입
		cur->process_page_faults = 0;
		cur->process_references = 0;
		INIT_LIST_HEAD(&cur->job);
		list_add_tail(&cur->job, &job_q);
		cur->references = malloc(sizeof(unsigned char) * cur->ref_len);	//code_bytes에 저장된 정보를 operaations크기만큼 동적 할당받아 저장.
		for(int i = 0; i < cur->ref_len; i++){ 
			fread(&cur->references[i], sizeof(unsigned char), 1, stdin);
        }
    }
}
void IO_task_print(){	//job_q에 저장된 파일을 출력
		list_for_each_entry_safe(cur, next, &job_q, job){
		printf("%d %d\n",cur->pid, cur->ref_len);
		for(int i = 0; i < cur->ref_len; i++){
			printf("%d ",cur->references[i]);
		}
        printf("\n");
	}
}
void load_process(){ //ready_q에 job_q를 순서대로 삽입.
	list_for_each_entry_safe(cur, next, &job_q, job){	
		INIT_LIST_HEAD(&cur->ready);
		list_add_tail(&cur->ready, &ready_q);
		cur->alloc_frame = 1;   //  level 1프레임 할당
		process_count++;
		frame_count += 1; //프로세스별로 level 1 Pagetabel 할당
	}
}

void Init_PTE(){    //1L PT 초기화 
	pas = (frame*) malloc(PAS_SIZE); //(unsigned char형 32칸 배열) * 256개
	for(int i = 0; i < process_count; i++){
		pte_ptr = (pte*) &pas[i];
		for(int j = 0; j < 8; j++){
			pte_ptr[j].vflag = PAGE_INVALID;
		}
	}
}

void end_simulator(){	//시뮬레이터가 종료 될때 PT 정보를 출력해주는 함수
	list_for_each_entry_safe(cur, next, &job_q, job){
		printf("** Process %03d: Allocated Frames=%03d PageFaults/References=%03d/%03d\n", cur->pid, cur->alloc_frame, cur->process_page_faults, cur->process_references);
		base_res = cur->pid;
		pte_ptr = (pte*) &pas[base_res];
		for(int i = 0; i < 8; i++){
			if(pte_ptr[i].vflag == PAGE_VALID){ //1LPT에서 valid인 것만 출력
				printf("(L1PT) %03d -> %03d\n", i, pte_ptr[i].frame);
				pte_ptr2 = (pte*) &pas[pte_ptr[i].frame];
				for(int j = 0; j < 8; j++){
					if(pte_ptr2[j].vflag == PAGE_VALID){ //2LPT에서 valid인 것만 출력
						printf("(L2PT) %03d -> %03d REF=%03d\n", (i * 8) + j, pte_ptr2[j].frame, pte_ptr2[j].ref);
					}
				}
			}
		}
	}
	printf("Total: Allocated Frames=%03d Page Faults/References=%03d/%03d\n", frame_count + 1, total_page_faults, total_references);
}
void up_count_pf(){//page fault시 각 변수들의 count를 올려주는 함수
	cur->process_page_faults++;
	cur->alloc_frame++;
	total_page_faults++;
}
void up_count_rf(){//refence시 각변수들의 count를 올려주는 함수
	cur->process_references++;
	total_references++;
}
void make_valid(){	//invaild 상황시 vaild로 변경해주고 할당 된 frame의 정보를 넣어주는 함수
	pte_ptr[num].frame = frame_count;
    pte_ptr[num].vflag = PAGE_VALID;
}
void simulator(){

	load_process();
	Init_PTE();
	int ref;	//수행 해야 할 reference
	while(1){
		list_for_each_entry_safe(cur, next, &ready_q, ready){
            //L1 page table
            pte_ptr = (pte*) &pas[cur->pid];
			ref = cur->references[ref_count];
            num = ref / 8;

			//1L PT에서 확인한 2L페이지 테이블이 INVALID인 경우
            if(pte_ptr[num].vflag == PAGE_INVALID){ 
                frame_count++;
                if(frame_count > 255){	//OOM
                    break;
                }
                make_valid();	//invaild 상황시 vaild로 변경해주고
				up_count_pf();

                pte_ptr = (pte*) &pas[frame_count]; 
				for(int i = 0; i < 8; i ++){	//새로 할당 받은 L2 frame 초기화
					pte_ptr[i].vflag = PAGE_INVALID;	
				}
				//L2 page table의 page에게 frame 할당.
                frame_count++;
                if(frame_count > 255){	//OOM
                    break;
                }
                num = ref % 8;
              	//L2의 page주소에 값 대입
                make_valid();
				pte_ptr[num].ref = 1;

                up_count_pf();
				up_count_rf();
				//1L PT에서 확인한 2L페이지 테이블이 VALID인 경우
            } else if(pte_ptr[num].vflag == PAGE_VALID){   
                num = pte_ptr[num].frame;   //1L pte를 읽어들여 2L PT로 이동
                pte_ptr = (pte*) &pas[num];

                num = ref % 8;  // L2 page table이 INVALID면 frame 할당 아니면 기존값 사용
                if(pte_ptr[num].vflag == PAGE_INVALID){
                    frame_count++;   //새 frame 할당
                    if(frame_count > 255){//OOM
                        break;
                    }
					make_valid();
					pte_ptr[num].ref = 1;
					
                    up_count_pf();
					up_count_rf();
                }else if(pte_ptr[num].vflag == PAGE_VALID){
                    pte_ptr[num].ref++;
                    up_count_rf();
                }

            }

			if(cur->ref_len - 1 == ref_count){	//모든 reference에 대해서 pas할당이 끝난 process는 ready_q에서 제거
				list_del(&cur->ready);
			}
		}
		if(frame_count > 255){//OOM
			frame_count--;
			printf("Out of memory!!\n");
			end_simulator();
			break;
		}
		if(list_empty(&ready_q) == 1){
			end_simulator();
			break;
		}
		ref_count++;
	}
}
void free_malloc(){
	free(pas);
	list_for_each_entry_safe_reverse(cur, next, &job_q, job){	//job_q를 돌며 할당 받았던 메모리들을 반환한다
		free(cur->references);
		free(cur);	
	}
}
int main(){

    IO_task();
    //IO_task_print();
	simulator();
    free_malloc();

    return 0;
}