6월24일 버디할당자와 시뮬레이팅 환경 실습

할당받은 메버디할당자와 시뮬레이팅 환경

할당받은 메모리를 사용하여 사용자 수준에서 동작하는 버디 할당자로써 리눅스의 버디 할당자의 개념대로 구현.

추후 버디 할당자 상위에 슬랩 할당자의 구현 실험, 새로운 메모리 할당 매커니즘 개발 등 다양한 분야로 확장 가능

 

Makefile, buddy.c list.c main.c 그리고 헤더파일들로 구성

컴파일 후 buddy 실행파일을 수행시키면 테스트할 메모리 공간을 KB단위로 입력받는다. (main()의 input_size()함수)

예)64KB입력, 총 16개의 페이지 프레임이 버디에 의해 관리. main()에서 바디 구조를 초기화, alloc_pages()가 됨에 따라 페이지들이 할당된다. order1(4KB), order2(8KB), order3(16KB)를 요청했을때 , 순서로 페이지를 할당하고 free_list의 상황을 화면에 출력한다.

 

buddy.h

#ifndef _BUDDY_H_
#define _BUDDY_H_
 
#include "list.h"
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
 
#define PAGE_SHIFT 12
#define PAGE_SIZE (1UL << PAGE_SHIFT) //한개의 페이지 크기 4096byte
#define PAGE_MASK (~(PAGE_SIZE-1) //addr의 값을 페이지 크기(4096바이트)에 맞게 정렬
 
 
#define PAGE_ALIGN(addr) (((addr)+PAGE_SIZE-1)&PAGE_MASK)
#define LONG_ALIGN(x) (((x)+(sizeof(long))-1)&~((sizeof(long))-1)
#define BUDDY_MAX_ORDER 10 //버디의 최상위 order는 512개 페이지들을 관리
#define TOTAL_PAGES(size) (size>>PAGE_SHIFT)
 
    //GET_NR_PAGE(addr) addr에 해당하는 페이지 번호를 반환
#define GET_NR_PAGE(addr) ((addr)-((unsigned long)real_memory+mem_offset) ) >> (PAGE_SHIFT)
 
    //page의 물리주소
#define page_address(page) ((page)->addr)
 
unsigned int mem_size; //시뮬레이터의 메모리 크기
unsigned long mem_offset;
 
void* real_memory; //mmap인터페이스로 받아온 메모리 영역
unsigned long free_pages;
 
//free page들을 관리하기 위한 구조체
 
typedef struct free_area_struct
{
struct list_head free_list;
unsigned long *map;
}free_area_t;
 
free_area_t free_area[BUDDY_MAX_ORDER]; //free page는 10개의 order로 구성
 
typedef struct page
{
    struct list_head list; //free_area_t 구조체와 연결하기 위한 리스트 구조체
    unsigned long flags; //nothing to do
    void *addr; //page의 실제 메모리 주소
    int order;
}mem_map_t;
 
mem_map_t *lmem_map;
 
//struct zone
//실제 리눅스의 메모리 할당, 해제 함수의 인터페이스와 동일한 인자를 받도록
//만들어 주기 위해 생성
 
typedef struct zonelist_struct
{
    int i;//zone member
}zonelist_t;
 
typedef struct zone_struct
{
    int j;
}zone_t;
 
//함수 원형 선언부
 
void init_memory(void);
void input_size(void);
void free_memory(void);
void init_buddy(void);
void alloc_bitmap(unsigned long*,unsigned long);
void ready_for_memory(void);
void* get_address_map(int);
void mapping_page(mem_map_t*);
 
#define ADDR (*(volatile ong*)addr)
unsigned long __get_free_pages(unsigned int,unsigned int);
struct page* alloc_pages(unsigned int, unsigned int);
struct page* __alloc_pages(unsigned int, unsigned int,zonelist_t *);
 
struct page* expand(zone_t*,struct page *,unsigned long,int,int,free_area_t *);
 
void _free_pages(void *ptr);
void __free_pages(struct page*,unsigned int);
void __free_pages_ok(struct page*,unsigned int);
 
int cal_cur_order(unsigned long);
void _show_free_order_list(int);
void _show_free_list_map(int);
 
#endif
 

 

 

buddy.c

#include "buddy.h"
#include <stdio.h>
#ifndef NULL
#define NULL 0
#endif
 
//free
#define STRUCT_DATA (1*1024*1024)
 
//
//
void ready_for_memory(void)
{
    
    real_memory = mmap( 0, mem_size + STRUCT_DATA, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_ANON | MAP_PRIVATE, -1, 0 );
    printf("memory is ready, address is %lx \n", (unsigned long)real_memory);
}
 
//
void* get_address_map(int size)
{
 
    char* addr;
    addr = (char*)((char*)real_memory + mem_offset);
    memset(addr, (int)0, size);
    mem_offset += size;
    return addr;
}
 
//
void mapping_page(mem_map_t* mem_map)
{
 
    unsigned long temp = mem_offset;
    while(mem_offset <= mem_size + STRUCT_DATA){
        mem_map -> addr = (unsigned long*)((char*)real_memory + mem_offset);
        mem_offset += PAGE_SIZE;
        mem_map++;
    }
    mem_offset = temp;
}
 
//
int cal_cur_order(unsigned long mem)
{
    int i = BUDDY_MAX_ORDER -1;
    while(i >= 0){
        if((mem) == (PAGE_SIZE << i)){
            return i;
        }
        i--;
    }
    if(mem > (PAGE_SIZE << (BUDDY_MAX_ORDER -1)))
        return (BUDDY_MAX_ORDER);
 
    return NULL;
}
 
 
 
static __inline__ int constant_test_bit(int nr, const volatile void* addr)
{
 
    return ((1UL << (nr & 31)) & (((const volatile unsigned int*) addr)[nr >> 5])) != 0;
}
 
//
static __inline__ void __change_bit(int nr, volatile void* addr)
{
 
    if(constant_test_bit(nr, addr) == 1)
    {
        (((volatile unsigned int*) addr)[nr >> 5]) &= (0xFFFFFFFF ^ (1UL << (nr & 31)));
    }
    else
    {
        (((volatile unsigned int*) addr)[nr >> 5]) |= (1UL << (nr & 31));
    }
}
 
 
static __inline__ int __test_and_change_bit(int nr, volatile void* addr)
{
 
    int oldbit;
    if((oldbit = constant_test_bit(nr, addr)) == 1){
        (((volatile unsigned int*) addr)[nr >> 5]) &= (0xFFFFFFFF ^ (1UL << (nr & 31)));
    }
    else{
        (((volatile unsigned int*) addr)[nr >> 5]) |= (1UL << (nr & 31));
    }
 
    return oldbit;
}
 
#define MARK_USED(index, order, area) __change_bit((index) >> (1+(order)),(area)->map)
 
 
void init_memory(void)
{
    int i;
    unsigned long cur_size=0;
 
    if((mem_size<=0)||(mem_size%PAGE_SIZE)!=0)
    {
        printf("allocate size %d bytes,not permited\t\n",mem_size);
        _exit(-1);
    }
 
    ready_for_memory();
 
    printf("allocation memory,size %d bytes \t\n",mem_size);
    free_pages=TOTAL_PAGES(mem_size);
    printf("total number of page : %ld\n",free_pages);
 
    mem_offset = sizeof(struct page)*TOTAL_PAGES(mem_size);
    lmem_map=(struct page*)real_memory;
 
    for(i=0;i<BUDDY_MAX_ORDER;i++)
    {
        unsigned long bitmap_size;
        INIT_LIST_HEAD(&free_area[i].free_list);
        bitmap_size=(mem_size-1)>>(i+4);
        bitmap_size=LONG_ALIGN(bitmap_size+1));
 
        free_area[i].map=(unsigned long*)get_address_map(bitmap_size);
        *(free_area[i].map)=0;
    }
    mem_offset=STRUCT_DATA;
    mapping_page(lmem_map);
    init_buddy();
}
 
 
 
 
 
void init_buddy(void){
 
    unsigned long nr_next, nr_prev;
    int cur_order = BUDDY_MAX_ORDER -1;
    unsigned long total_page = free_pages;
    unsigned long top_buddy_size = PAGE_SIZE << cur_order;
    free_area_t* area = &free_area[cur_order];
    if((top_buddy_size*2) >= (mem_size))
    {
        cur_order = cal_cur_order(mem_size);
        area = &free_area[--cur_order];
    }
    top_buddy_size = PAGE_SIZE << cur_order;
    unsigned long order_page = TOTAL_PAGES(top_buddy_size);
    //first
    list_add(&(lmem_map[0]).list, &(area) -> free_list);
    nr_prev = 0; nr_next = 0;
    //page to page in free_area list
    while(1){
        nr_prev = nr_next;
        nr_next = nr_prev + ( 1UL << cur_order);
        if(nr_next + order_page >= total_page){
            list_add(&(lmem_map[nr_next]).list, &(area) -> free_list);
            MARK_USED(nr_prev, cur_order, area);
            break;
        }
        while((total_page - nr_next) <= order_page)
        {
            if(cur_order == 0)
                break;
            cur_order--;
            area--;
 
            order_page = 1 << cur_order;
        }
        nr_prev = nr_next;
        list_add(&(lmem_map[nr_prev]).list, &(area) -> free_list);
        MARK_USED(nr_prev, cur_order, area);
    }
}
 
unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order){ //요청한 order page의 주소를 반환
 
    struct page *page;
    page = alloc_pages(gfp_mask, order);
    if(!page) return 0;
    return (unsigned long )page_address(page);
}
 
struct page* alloc_pages(unsigned int gfp_mask, unsigned int order){
 
    return __alloc_pages(gfp_mask, order, NULL);
}
 
struct page* __alloc_pages(unsigned int gfp_mask, unsigned int order, zonelist_t* zonelist){
 
    struct page* page;
    unsigned int curr_order = order;
    free_area_t* area = &free_area[order];
    //
    //
    struct list_head *head, *curr;
    do{
        head = &area -> free_list;
        curr = head-> next;
        if(curr != head){
            unsigned long index;
            page = list_entry(curr, struct page, list);
            list_del(curr);
            index = GET_NR_PAGE((unsigned long)page -> addr);
            if(curr_order != BUDDY_MAX_ORDER -1)
                MARK_USED(index, curr_order, area);
            free_pages -= 1UL << order;
            //
            page = expand(NULL, page, index, order, curr_order, area);
            page -> order = order;
            return page;
        }
        curr_order++;
        area++;
    } while(curr_order < BUDDY_MAX_ORDER);
 
    return NULL;
}
 
 
 
 
 
 
//상위 오더의 페이지 검사 후, 버디 알고리즘에 의해 반으로 나뉘어 지고 하위 오더로 연결해주는 함수
struct page* expand(zone_t *zone,struct page *page,unsigned long index,int low,int high,free_area_t *area)
{
    unsigned long size= 1<<(high);
 
    while(high>low){
        area--;
        high--;
        size >>= 1;
        list_add(&(page)->list,&(area)->free_list);
        MARK_USED(index,high,area);
        index += size;
        page += size;
    }
 
    return page;
}
 
//할당된 페이지 해제를 위한 함수
void _free_pages(void *ptr)
{
    int i;
    i=(((char *)ptr-(char *)lmem_map[0].addr) >> PAGE_SHIFT);
    __free_pages(&lmem_map[i],lmem_map[i].order);
}
 
void __free_pages(struct page* page,unsigned int order)
{
    //if page checking
    __free_pages_ok(page,order);
}
 
void __free_pages_ok(struct page* page, unsigned int order)
{
    unsigned long index,page_idx,mask;
    free_area_t *area;
    struct page* base;
 
    mask =(~0UL) << order;
    base = lmem_map;
    page_idx=GET_NR_PAGE((unsigned long)page->addr);
 
    //해제 하려는 page의 현재 order에서 비트맵 위치 계산
 
    index = page_idx >> (1+order);
 
    area = &free_area[order];
    free_pages -= mask;
    //페이지의 해제 후 현재 오더 및 상위 오더에서 버디가 합쳐질 수 있는지 확인 후,
    //합쳐지는 경우라면 상위 오더의 리스트에 연결하고 현재 오더리스트에서는 제거 해준다.
 
    while(mask+(1<<(BUDDY_MAX_ORDER-1)))
    {
        struct page *buddy1,*buddy2;
        if(area>=free_area+BUDDY_MAX_ORDER)
        {
            printf("over free_area boundary \n");
            break;
        }
 
        if(!__test_and_change_bit(index,area->map)){
            break;
        }
 
        buddy1=&lmem_map[((page_idx)^-mask)];
        buddy2=&lmem_map[page_idx];
 
        list_del(&buddy1->list);
        mask <<= 1;
        area++;
        index >>=1;
        page_idx &= mask;
    }
 
    list_add(&lmem_map[page_idx].list,&area->free_list);
}
 
//mmap으로 할당된 메모리 해제
void free_memory(void)
{
    munmap(real_memory,mem_size);
    printf("Free allocated real memory..\n");
}
 
//시뮬레이터의 메모리 사이즈 입력(kb단위)
void input_size(void)
{
    printf("total memory size(KB)?");
    scanf("%d",&mem_size);
    mem_size *=1024;
}
 
//order에 연결되어 있는 페이지 번호를 출력
void _show_free_order_list(int order)
{
    free_area_t *area=&free_area[order];
    struct page *p,*q;
    int i=0;
 
    p=(struct page*)(area)->free_list.next;
    q=(struct page*)&(area)->free_list;
    printf("---------------------------order %d----------------------------\n",order);
 
    while(p!=q)
    {
        printf("%ld\t",GET_NR_PAGE((unsigned long)p->addr));
        p=(struct page*)p->list.next;
        if(++i==7){printf("\n");i=0;}
    }
 
    printf("\n--------------------------------------------\n");
}

 

 

list.h

//double linked list 관리
 
struct list_head{
    struct list_head *next,*prev;
};
 
#define INIT_LIST_HEAD(ptr) (ptr)->next=(ptr); (ptr)->prev=(ptr);
#define list_entry(ptr,type,member) ((type*)((char*)(ptr)-(unsigned long)(&((type *)0)->member)))
 
 
void list_add(struct list_head*,struct list_head *);
void __list_add(struct list_head*,struct list_head *,struct list_head *);
void list_del(struct list_head*);
void __list_del(struct list_head*,struct list_head *);
void list_add_tail(struct list_head*,struct list_head *);
 

 

list.c

#include "list.h"
 
void list_add(struct list_head *new,struct list_head *head)
{
    __list_add(new,head,head->next);
}
 
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;
}
 
void list_del(struct list_head *entry)
{
    __list_del(entry->prev,entry->next);
    entry->next=(void*)0;
    entry->prev=(void*)0;
}
 
void __list_del(struct list_head *prev,struct list_head *next)
{
    next->prev=prev;
    prev->next=next;
}
 
 
void list_add_tail(struct list_head *new,struct list_head *head)
{
    __list_add(new,head->prev,head);
}
 

 

main.c

#include "buddy.h"
 
#include <stdio.h>
int main(void)
{
    input_size();
 
    int i=0;
    struct page* page;
    struct page* page1;
 
    init_memory();
 
    page=alloc_pages(0,2);
    page1=alloc_pages(0,1);
 
    _free_pages(page->addr);
    _free_pages(page1->addr);
 
    for(i=0;i<=9;i++)
        _show_free_order_list(i);
 
    printf("\n\n");
 
    free_memory();
    return 0;
}
 

불러오는 중입니다...

 

 

 

 

 

 

gcc -W -Wall -c -o main.o main.c
gcc -W -Wall -c -o list.o list.c
gcc -W -Wall -c -o buddy.o buddy.c
gcc -g -W -Wall -o buddy main.o list.o buddy.o