리눅스 커널 내부구조 10장 #3 buddy allocator
Linux Kernel 의 buddy allocator 를 구현한 코드이다. 책에서 나온 코드를 바닥부터 뜯어 고쳐서 원본 코드랑 완전히 달라졌으나 그 기저의 동작 방식은 그대로 녹여냈다.
1. 코드
- 소스코드
bitmap.c
#include "bitmap.h"
#include <stdio.h> // fputc()
#include <stdlib.h> // malloc(), free()
#include <limits.h> // CHAR_BIT
#include <string.h> // memset()
#include "exstdlib.h"
typedef char byte;
#define TYPE_ALIGN(TYPE, X) ( ((X) + ((TYPE) - 1)) / (TYPE) )
#define BITMAP_SIZE (sizeof(btype) * CHAR_BIT)
#define BITS_TO_BYTE(BITS) TYPE_ALIGN(CHAR_BIT, BITS)
#define BITMAP_INDEX_ALIGN(BITSIZE) TYPE_ALIGN( \
sizeof(btype), \
BITS_TO_BYTE(BITSIZE) \
)
#define BITMAP_INDEX(BITSIZE) ((BITSIZE) / (CHAR_BIT * sizeof(btype)))
#define BYTE_BIT CHAR_BIT
#define COMP(X, Y) (((X) > (Y)) ? 1 : -1)
enum bitmap_alloc {
BITMAP_ALLOC_BY_MALLOC,
BITMAP_ALLOC_ADDR_ONLY,
BITMAP_ALLOC_FULL_STRUCT,
BITMAP_ALLOC_INVAL
};
typedef unsigned int btype;
struct bitmap {
int bitsize;
int memsize;
btype *map;
enum bitmap_alloc type;
};
// static void __bitmap_show(btype *map, int index, int shift, bool high_first);
enum bitmap_alloc bitmap_get_type(int size, void *addr, int addr_size)
{
enum bitmap_alloc type;
if (addr != NULL) {
int addr_only = BITMAP_INDEX_ALIGN(size) * sizeof(btype);
int full_struct = addr_only + sizeof(struct bitmap);
if (addr_size >= full_struct)
type = BITMAP_ALLOC_FULL_STRUCT;
else if (addr_size >= addr_only)
type = BITMAP_ALLOC_ADDR_ONLY;
else
type = BITMAP_ALLOC_INVAL;
} else type = BITMAP_ALLOC_BY_MALLOC;
return type;
}
uint64_t bitmap_to_int(Bitmap map)
{
uint64_t value = 0;
return value;
}
Bitmap __bitmap_create(uint64_t size, void *addr, int addr_size)
{
Bitmap bitmap = NULL;
btype *map_addr = NULL;
enum bitmap_alloc type;
type = bitmap_get_type(size, addr, addr_size);
switch (size) {
case BITMAP_ALLOC_FULL_STRUCT: bitmap = addr;
PTR_ADD(addr, sizeof(struct bitmap));
case BITMAP_ALLOC_ADDR_ONLY: map_addr = addr;
case BITMAP_ALLOC_BY_MALLOC: break;
case BITMAP_ALLOC_INVAL: return NULL;
}
if (bitmap == NULL) {
bitmap = malloc(sizeof(struct bitmap));
if (bitmap == NULL)
return NULL;
}
if (map_addr == NULL) {
map_addr = malloc(BITMAP_INDEX_ALIGN(size) * sizeof(btype));
if (map_addr == NULL) {
if (type == BITMAP_ALLOC_BY_MALLOC) free(bitmap);
return NULL;
}
}
bitmap->map = map_addr;
bitmap->type = type;
bitmap->memsize = BITMAP_INDEX_ALIGN(size) * sizeof(btype);
bitmap->bitsize = size;
return bitmap;
}
Bitmap bitmap_create(uint64_t size)
{
return __bitmap_create(size, NULL, 0);
}
int __bitmap_calc_alloc_size(bool is_full_struct, uint64_t size)
{
int addr_only = BITS_TO_BYTE(size);
int full_struct = addr_only + sizeof(struct bitmap);
return (is_full_struct ? full_struct : addr_only);
}
void bitmap_clear(Bitmap bitmap, bool value)
{
memset(bitmap->map, value, bitmap->memsize);
}
bool bitmap_get(Bitmap bitmap, uint64_t pos)
{
uint64_t idx = BITMAP_INDEX(pos);
return (bitmap->map[idx]) & (((btype) 1) << (pos & (BITMAP_SIZE - 1)));
}
bool bitmap_switch(Bitmap bitmap, uint64_t pos)
{
bool prev = bitmap_get(bitmap, pos);
bitmap_set(bitmap, pos, !prev);
return prev;
}
void bitmap_set(Bitmap bitmap, uint64_t pos, bool set)
{
int idx = BITMAP_INDEX(pos);
int shift = pos % BITMAP_SIZE;
if (set)
bitmap->map[idx] |= ((btype) 1) << shift;
else
bitmap->map[idx] &= ((~((btype) 0)) ^ (((btype) 1) << shift));
}
uint64_t bitmap_size(Bitmap bitmap)
{
return bitmap->bitsize;
}
uint64_t bitmap_msize(Bitmap bitmap)
{
return bitmap->memsize;
}
void bitmap_show(Bitmap bitmap, bool high_start)
{
uint64_t start, end;
if (high_start) start = bitmap_size(bitmap) - 1, end = 0;
else start = 0, end = bitmap_size(bitmap) - 1;
bitmap_show_area(bitmap, start, end);
}
void bitmap_show_all(Bitmap bitmap, bool high_start)
{
uint64_t start, end;
if (high_start) start = (bitmap_msize(bitmap) * BYTE_BIT) - 1, end = 0;
else start = 0, end = (bitmap_msize(bitmap) * BYTE_BIT) - 1;
bitmap_show_area(bitmap, start, end);
}
void bitmap_show_area(Bitmap bitmap, uint64_t start, uint64_t end)
{
int nr;
for (nr = start; nr != end; nr += COMP(end, start)) {
fputc(bitmap_get(bitmap, nr) ? '1' : '0', stdout);
if (nr != 0) {
if (nr % BYTE_BIT == 0)
fputc(' ', stdout);
}
}
fputc(bitmap_get(bitmap, nr) ? '1' : '0', stdout);
}
void bitmap_destroy(Bitmap bitmap)
{
switch (bitmap->type) {
case BITMAP_ALLOC_BY_MALLOC:
free(bitmap->map);
case BITMAP_ALLOC_ADDR_ONLY:
free(bitmap);
case BITMAP_ALLOC_FULL_STRUCT:
case BITMAP_ALLOC_INVAL:
/* do nothing */ ;
}
}
int bitmap_bytebit(void)
{
return BYTE_BIT;
}
buddy.c
#include "buddy.h"
#include "exstdlib.h"
// STRUCT_DATA: buddy_allocator, free_area struct, bitmap, page memory
// 자료구조를 위한 메모리, 이후 init_memory() 에서 사용됨
#define STRUCT_DATA (1 * 1024 * 1024) // 1 MiB
// GET_PAGE_IDX(BUDDY, ADDR): ADDR 에 해당하는 페이지 번호(index)를 반환
#define GET_PAGE_IDX(BUDDY, ADDR) ( \
(((byte *) (ADDR)) - ((byte *) (BUDDY)->lmem_map[0].addr)) / PAGE_SIZE \
)
// 현재 PTR 의 값을 반환하고, PTR 에 SIZE 를 더한다.
#define ALLOC_FROM_PTR(PTR, SIZE) (((PTR) += (SIZE)), (void *) ((PTR) - (SIZE)))
// MARK_USED(INDEX, ORDER, AREA):
// INDEX 와 ORDER 를 참조하여 bitmap 에 page 사용 정보를 매핑한다.
// - INDEX: page 의 실제 index 값
// - ORDER: 현재 order
// - AREA: free_area_t 구조체
//
// - INDEX >> (1 + (ORDER)) 를 통해 해당 ORDER 에서의 bitmap 위치를 알아낸다.
// -----------------------------------------------------------------
// USED(*) | * * * * * - * * - - - * - - - - |
// PAGE | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
// -----------------------------------------------------------------
// ORDER(0) | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
// -----------------------------------------------------------------
// ORDER(1) | 0 | 0 | 1 -> 0 | 0 |
// -----------------------------------------------------------------
// ORDER(2) | 0 | 1 |
// -----------------------------------------------------------------
// ORDER(3) | 0 |
// -----------------------------------------------------------------
// A 상단의 아스키 아트는 free_area[ORDER].map 을 도식화한 것이고,
// V 하단의 아스키 아트는 free_area[ORDER].free_list 를 도식화한 것이다.
// | 9 |
// |...|
// |...|
// |...|
// | 4 |
// | 3 |
// | 2 | <--> C
// | 1 | <--> 8 (will remove)
// | 0 | <--> 5 <--> A
//
// 위와 같은 상황에서 alloc_pages 를 통해 order 1 의 페이지 할당을 요청하면
// 이를 free_list[1] 에서 찾게 된다. 사용 가능한 free page 를 찾으면
// 해당 page 를 반환하고 bitmap 수정을 위해 아래와 같이 매크로를 호출하게 된다.
// MARK_USED(buddy->free_area[1], 8, 1);
// 위 매크로를 호출하게 되면 아래와 같이 치환된다:
// bitmap_set(buddy->free_area[1].map, 8 >> (1 + 1), false);
// bitmap_set(buddy->free_area[1].map, 2, false);
#define MARK_USED(AREA, INDEX, ORDER) \
bitmap_switch((AREA)->map, (INDEX) >> (1 + (ORDER)))
#include <stdbool.h> // true, false
#include <limits.h>
#include <stdint.h>
#include <sys/mman.h>
#include "bitmap.h"
extern Bitmap __bitmap_create(uint64_t size, void *addr, int addr_size);
extern int __bitmap_calc_alloc_size(bool is_full_struct, uint64_t size);
typedef char byte;
// free page 를 관리하기 위한 구조체
struct free_area_t {
struct list_head free_list; // 사용 가능한 page 를 연결한 리스트
Bitmap map; /* 사용 가능한 page 를 알려주는 bitmap
이후 메모리 병합에 사용됨. */
};
struct buddy_allocator {
// 할당된 메모리 크기
unsigned int mem_size;
// page 구조체의 시작 주소
struct page *lmem_map;
// free_pages: 할당 가능한 페이지의 최대 개수
// max_order: 요청 가능 order 의 최댓값
unsigned int free_pages;
unsigned int max_order;
// free page 를 관리하기 위한 구조체
struct free_area_t *free_area;
};
//------------------------------------------------------------------------------
// Local function prototype
//------------------------------------------------------------------------------
static int find_fitness_order(int memsize);
static struct page *expand(
struct page *page,
int index, int low, int high,
struct free_area_t *area
);
static struct buddy_allocator *init_memory(int memsize);
static int calc_gap(int order);
static void buddy_show_order_status(struct buddy_allocator *buddy, int order);
//------------------------------------------------------------------------------
// Global function
//------------------------------------------------------------------------------
struct buddy_allocator *buddy_create(int memsize)
{
unsigned int order_page, total_page, cur_order;
struct buddy_allocator *buddy;
struct free_area_t *area;
// buddy 구조체 완성
buddy = init_memory(memsize);
if (buddy == NULL)
return NULL;
// 현재 order - 1 을 cur_order 로 잡아 페이지를 할당
cur_order = buddy->max_order - 1;
// total: 전체 페이지의 크기
// order: 현재 order 에서 만들 수 있는 페이지의 크기
// 가령 order 가 3 이고 페이지 하나의 크기가 4 KiB 라면
// order_page 는 8 이 된다.
total_page = buddy->free_pages;
order_page = TOTAL_PAGES(PAGE_SIZE << cur_order);
// 일반적으로 order_page 가 total_page 의 절반이 되나,
// 전체 메모리가 너무 커서 최대 order (max_order) 로 표현 가능한
// 페이지의 수가 2 배를 넘는 경우엔 아래의 반복문에서 처리가 이뤄진다.
// free_area list 에 최초의 page 등록
area = &buddy->free_area[cur_order];
list_add(&area->free_list, &buddy->lmem_map[0].list);
// 남은 페이지를 등록, 일반적으로 한번 돌고 끝나지만
// 전체 메모리가 너무 큰 경우 max_order 페이지가 여러 개
// 등록될 수 있기 때문에 반복을 통해 페이지를 추가한다.
for (int nr = 0; nr < total_page - order_page; nr += (1UL << cur_order))
{
int nr_next = nr + (1UL << cur_order);
list_add(&area->free_list, &buddy->lmem_map[nr_next].list);
MARK_USED(area, nr, cur_order);
}
return buddy;
}
// buddy allocator 를 제거한다.
// buddy 는 mmap 을 통해 할당받은 메모리를 적절히 쪼개 할당했으므로 munmap
// 함수를 호출하는 것만으로 모든 buddy 시스템 데이터를 제거하는 것이 가능하다.
void buddy_destroy(struct buddy_allocator *buddy)
{
munmap(buddy, buddy->mem_size + STRUCT_DATA);
printf("free allocated real memory..
");
}
struct page *buddy_page_alloc(struct buddy_allocator *buddy, unsigned int order)
{
struct page *page;
unsigned int cur_order;
struct free_area_t *area;
struct list_head *head, *next;
// 할당하려는 order 가 max_order 다 크다면 NULL 반환
if (buddy->max_order <= order)
return NULL;
// free_area 가져오기
cur_order = order;
area = &buddy->free_area[cur_order];
do {
head = &area->free_list;
next = head->next;
// head 가 next 와 같지 않다? => 할당 가능한 페이지가 존재한다.
if (next != head) {
int index;
/*
* 1. list 에 연결되어 있는 페이지를 가져온다.
* 2. 해당 페이지를 연결 리스트에서 제거한다.
* 3. 페이지의 주소를 통해 페이지 인덱스를 가져온다.
*/
page = LIST_ENTRY(next, struct page, list);
list_del(next);
index = GET_PAGE_IDX(buddy, page->addr);
// max_order 인 경우를 제외한 모든 경우에 MARK 한다.
//if (cur_order != buddy->max_order - 1)
MARK_USED(area, index, cur_order);
// free_pages 를 할당한 크기만큼 줄인다.
buddy->free_pages -= (1UL << order);
// 만일 현재 page 의 order 가 요청한 order 보다 크다면
// page 를 쪼개고 남은 페이지를 할당한다.
page = expand(
/* page, index */
page, index,
/* low, high */
order, cur_order,
/* free area */
area
);
page->order = order;
return page;
}
// cur_order 에서 페이지를 찾지 못하면 여기로 떨어져 내려온다.
// cur_order 에 page 가 없다는 것은 아래를 뜻한다.
// => free_area list 에 그 어떠한 페이지도 없다.
// 따라서 다음 order 로 넘어간다.
cur_order++;
area++;
// order 가 만약 max_order 보다 크다면?
// => 이건 더 이상 할당할 페이지가 없다는 뜻
} while (cur_order < buddy->max_order);
// 그 어디에도 할당 가능한 데이터가 없다면 NULL 반환
return NULL;
}
void buddy_page_free(struct buddy_allocator *buddy, struct page *page)
{
struct free_area_t *area;
unsigned page_idx, bitmap_idx;
int order;
// 반환을 요청한 page 주소를 통해 page 의 index 를 계산
order = page->order;
page_idx = GET_PAGE_IDX(buddy, (unsigned long) page->addr);
bitmap_idx = page_idx >> (1 + order);
area = &buddy->free_area[order];
buddy->free_pages += (1 << order);
while (area < &buddy->free_area[buddy->max_order - 1]) {
// 할당 가능한 page 가 있다면 bitmap 의 값은 1 이다.
// 그런데 bitmap_switch 결과가 0 이다? 이는 buddy page 가
// 옆에 있다는 뜻이므로 merge 해서 상위 order page 로
// 올려 보내야 함을 의미한다.
if ( !bitmap_switch(area->map, bitmap_idx) )
break;
// 제거할 buddy page 의 index 를 구한다.
page_idx = page_idx ^ (1 << order);
list_del(&buddy->lmem_map[page_idx].list);
// 상위 order 로 올라간다.
area++;
order++;
bitmap_idx >>= 1;
// page_idx 를 상위 order 주소에 맞게 align 한다.
page_idx &= (~0 << order);
}
list_add(&area->free_list, &buddy->lmem_map[page_idx].list);
}
// 현재 buddy allocator 의 bitmap 및 free_area list 의 정보를 상세히 출력한다.
void buddy_show_status(struct buddy_allocator *buddy,
enum buddy_show_type type)
{
struct free_area_t *area;
int total_page;
int padd_bitmap, padd_freelist, padd_order;
for (int i = 0; i < buddy->max_order; i++) {
area = &buddy->free_area[i];
total_page = TOTAL_PAGES(PAGE_SIZE << buddy->max_order);
padd_bitmap = bitmap_size(area->map) / bitmap_bytebit() + 2
+ bitmap_size(area->map);
padd_freelist = total_page * (3 + 1) + 1;
padd_order = 12;
// 상단부, 구역별 명칭
putchar('-'); cprintf(" [order] ", '-', padd_order);
cprintf(" [free list] ", '-', padd_freelist);
cprintf(" [bitmap] ", '-', padd_bitmap); NEWLINE;
// 중단부, order, free area list, bitmap 순서대로 출력
putchar('|'); cprintf("%d", ' ', padd_order, i); putchar('|');
buddy_show_order_status(buddy, i);
putchar(' '); bitmap_show(area->map, false); puts(" |");
// 하단부
cprintf("", '-', padd_bitmap + padd_freelist + padd_order + 1);
NEWLINE;
}
}
//------------------------------------------------------------------------------
// Local function
//------------------------------------------------------------------------------
static int find_fitness_order(int memsize)
{
// - 요청한 메모리가 단일 page 크기에 딱 맞아 떨어지는지 확인
// - 최소 할당 단위가 PAGE_SIZE 이므로 당연히 PAGE_SIZE 로 정확하게
// 나누어 떨어져야 한다. 그렇지 않다면 -1 반환.
if ((memsize <= 0) || (memsize % PAGE_SIZE) != 0)
return -1;
// 메모리 크기에 딱 맞는 max order 를 구한다.
if (memsize <= (PAGE_SIZE << (BUDDY_MAX_ORDER - 1))) {
for (int i = 0; i < BUDDY_MAX_ORDER; i++) {
// mem_size 와 동일한 크기의 단일 page order 라면
// 해당 값을 max_order 로 사용한다.
if (memsize == (PAGE_SIZE << i))
return i;
}
return -1;
}
// mem_size 가 max_order 로 할당 가능한 최대 memory 크기보다 크다면
// 당연히 max order 역시 BUDDY SYSTEM 의 MAX ORDER 로 잡는다.
return BUDDY_MAX_ORDER;
}
static struct buddy_allocator *init_memory(int memsize)
{
struct buddy_allocator *buddy;
byte *real_memory;
int max_order;
// memsize 에 적합한 max_order 를 구한다.
max_order = find_fitness_order(memsize);
if (max_order < 0)
return NULL;
// 메모리 동적 할당
real_memory = mmap(
0, memsize + STRUCT_DATA,
PROT_READ | PROT_WRITE | PROT_EXEC,
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0
);
if (real_memory == NULL) {
printf("failed to allocate %d size memory",
memsize + STRUCT_DATA);
return NULL;
} else printf("memory is ready, address is %p
", (void *) real_memory);
/*******************************************************************************
* - buddy system 을 위한 메모리를 할당, 메모리는 아래와 같이 사용된다: *
* r-------T-----------T-------------T--------T----T-----T-----T----T-----7 *
* | buddy | free area | page struct | bitmap | .. | pg0 | pg1 | .. | pgN | *
* L-------^-----------^-------------^--------^----^-----^-----^----^-----J *
******************************************************************************/
// buddy 구조체 기본 데이터 초기화
buddy = ALLOC_FROM_PTR(real_memory, sizeof(struct buddy_allocator));
buddy->mem_size = memsize;
buddy->max_order = max_order;
// free_area 구조체를 위한 공간 할당
buddy->free_area = ALLOC_FROM_PTR(real_memory,
sizeof(struct free_area_t) * buddy->max_order
);
// free_pages 계산, page 구조체를 위한 공간 마련
buddy->lmem_map = ALLOC_FROM_PTR(real_memory,
(sizeof(struct page) * TOTAL_PAGES(buddy->mem_size))
);
buddy->free_pages = TOTAL_PAGES(buddy->mem_size);
printf("allocate memory, size %d bytes
", buddy->mem_size);
printf("total number of page: %u
", buddy->free_pages);
// buddy 구조체 내의 free_area 자료구조의 초기화를 진행한다.
// 각 order 의 list 초기화 및 bitmap 의 생성 및 초기화를 수행한다.
for (int i = 0; i < buddy->max_order; i++) {
unsigned int map_size, struct_size;
list_init(&buddy->free_area[i].free_list);
map_size = (buddy->free_pages / 2) >> i;
struct_size = __bitmap_calc_alloc_size(true, map_size);
printf("order(%d). map_size: %u struct_size: %u
",
i, map_size, struct_size);
buddy->free_area[i].map = __bitmap_create(
map_size,
ALLOC_FROM_PTR(real_memory, struct_size),
struct_size
);
bitmap_clear(buddy->free_area[i].map, 0);
}
// page 구조체의 addr 멤버 변수가 실제 빈 메모리를 가르키도록 한다.
real_memory = (byte *) buddy + STRUCT_DATA;
for (int i = 0; i < buddy->free_pages; i++)
buddy->lmem_map[i].addr = ALLOC_FROM_PTR(
real_memory, PAGE_SIZE
);
return buddy;
}
// buddy_page_free 에 의해 호출되는 함수로 현재 order 에서 할당 가능한 page 가
// 없는 경우 상위 free_area list 에서 할당 가능한 page 를 쪼개어 할당.
static struct page *expand(
struct page *page,
int index, int low, int high,
struct free_area_t *area
)
{
unsigned long size = (1 << high);
// high 는 현재 발견한 상위 free_area list 의 order 이고
// low 는 현재 할당을 요청한 page 의 order 이다.
// index 는 high order 에 존재하는 page 의 index 를 의미한다);
while (high > low) {
// 1. (area - 1) 은 하위 order 로 하강함을 의미한다.
// 2. (high - 1) 역시 상위 order 를 하강함을 의미한다.
// 3. size 역시 2 의 high order 승이므로 같이 맞춰 내린다.
area--;
high--;
size >>= 1;
// 여기에서 기존 page 를 하강한 free_area list 에 등록하는데
// 이렇게 되면 page 의 크기만 반으로 줄어든다. 재미있는 점은
// page 의 index 에는 아무런 변화가 일어나지 않는다는 것이다.
list_add(&area->free_list, &page->list);
// 하위 order 에 사용 가능한 page 두 개가 생겼고 (상위 order 의
// page 를 한 단계 내렸기 때문에) 그 중 하나는 할당 혹은 다시
// 재귀적으로 쪼갤 것이기에 사용 중으로 표시한다.
MARK_USED(area, index, high);
// index 의 크기를 size 만큼 증가
index += size;
// 페이지의 역시 size index 만큼 뛰어 넘는다.
page += size;
}
// 최종적으로 요청한 order 에 해당하는 page 를 반환한다.
return page;
// - 처음에는 위 코드의 동작 방식이 정확하게 이해되지 않을 수 있다.
// 따라서, main 코드를 실행시켜 그 동작을 이해하는 것이 좋다.
// - 최초 page 할당 시 어떠한 방식으로 page 가 쪼개지는지 주목하라.
}
// buddy_show_order_status() 에서 free_area list 간극을 계산하는 함수
static int calc_gap(int order)
{
if (order <= 0)
return 3;
return calc_gap(order - 1) * 2 + 1;
}
// 현재 order 의 free area list 정보를 양식에 맞춰 출력한다.
static void buddy_show_order_status(struct buddy_allocator *buddy, int order)
{
struct free_area_t *area;
int total_page, find;
if (buddy->max_order <= order)
return ;
area = &buddy->free_area[order];
total_page = TOTAL_PAGES(PAGE_SIZE << buddy->max_order);
for (int i = 0; i < total_page; i += ((1 << order)))
{
find = -1;
for (struct page *p = (struct page *) area->free_list.next,
*q = (struct page *) &area->free_list;
p != q;
p = (struct page *) p->list.next)
{
if (GET_PAGE_IDX(buddy, p->addr) == i) {
find = i;
break;
}
}
if (find == -1) cprintf("-", ' ', calc_gap(order));
else cprintf("%d", ' ', calc_gap(order), find);
putchar('|');
}
}
exstdlib.c
#include "exstdlib.h"
#include <stdio.h> // for printf() series
#include <stdlib.h> // for malloc()
#include <stdarg.h> // for va_*** series
#include <stdbool.h> // true, false
int cprintf(const char *fmt, char chr, int width, ...)
{
static bool rem_dir = true;
char *fmtstr, *alignstr, *trackstr;
int fmtlen, padlen, rem;
va_list ap_for_len, ap_for_read;
if (fmt == NULL)
return (rem_dir = !rem_dir);
va_start(ap_for_len, width);
va_copy(ap_for_read, ap_for_len);
fmtlen = vsnprintf(NULL, 0, fmt, ap_for_len);
fmtstr = malloc(fmtlen + 1);
if(fmtstr == NULL)
goto RETURN_ERR;
vsprintf(fmtstr, fmt, ap_for_read);
va_end(ap_for_read);
va_end(ap_for_len);
padlen = (fmtlen >= width) ? 0 : width - fmtlen;
rem = padlen % 2;
alignstr = malloc(fmtlen + padlen + 1);
if (alignstr == NULL)
goto FREE_FMT_STR;
trackstr = alignstr;
memset_mv(trackstr, chr, padlen / 2 + (rem * (rem_dir == true)));
memcpy_mv(trackstr, fmtstr, fmtlen);
memset_mv(trackstr, chr, padlen / 2 + (rem * (rem_dir == false)));
*trackstr = '
list.c
#include "list.h"
void list_init(struct list_head *head)
{
head->next = head;
head->prev = head;
}
void list_add(struct list_head *head, struct list_head *new)
{
// link with (new) <=> (head->next)
head->next->prev = new;
new->next = head->next;
// link with (head) <=> (new)
new->prev = head;
head->next = new;
}
void list_del(struct list_head *entry)
{
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
entry->next = entry->prev = NULL;
}
void list_add_tail(struct list_head *head, struct list_head *new)
{
head->prev->next = new;
new->prev = head->prev;
head->prev = new;
new->next = head;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include "buddy.h"
#include "bitmap.h"
#include "list.h"
#define BITMAP_SHOW(BITMAP) bitmap_show_all(BITMAP, true)
struct page_list {
struct page *page;
struct list_head head;
};
int free_page(struct buddy_allocator *buddy, struct list_head **main)
{
int index, order, cnt = 0;
if (main == NULL) goto RETURN_ERR;
printf("index(1 ~ +) or order(- ~ 0): ");
scanf("%d", &index);
if (index <= 0) order = -index;
else order = -1;
LIST_ITERATOR_WITH_ENTRY(*main, entry, struct page_list, head)
if (++cnt == index || entry->page->order == order) {
buddy_page_free(buddy, entry->page);
if (&entry->head == *main) {
if (entry->head.next == &entry->head)
*main = NULL;
else
*main = entry->head.next;
}
LIST_ITERATOR_DELETE_ENTRY;
free(entry);
return 0;
}
LIST_ITERATOR_END
RETURN_ERR: return -1;
}
int alloc_page(struct buddy_allocator *buddy, struct list_head **main)
{
struct page_list *new_plist;
int order;
printf("order: "); scanf("%d", &order);
if (order < 0) goto RETURN_ERR;
new_plist = malloc(sizeof(struct page_list));
if ( !new_plist )
goto RETURN_ERR;
list_init(&new_plist->head);
new_plist->page = buddy_page_alloc(buddy, order);
if ( !new_plist->page )
goto FREE_PLIST;
if ( !*main ) *main = &new_plist->head;
else list_add((*main)->next, &new_plist->head);
return 0;
FREE_PLIST: free(new_plist);
RETURN_ERR: return -1;
}
int show_page(struct list_head *main)
{
int index = 0;
if ( !main )
return -1;
LIST_ITERATOR_WITH_ENTRY(main, entry, struct page_list, head)
printf("index: %d ", ++index);
printf("order: %d
", entry->page->order);
LIST_ITERATOR_END
return 0;
}
int main(void)
{
struct buddy_allocator *buddy;
struct list_head *main_list = NULL;
int memsize, menu;
printf("total memory size(KiB)? ");
scanf("%d", &memsize); memsize *= 1024;
buddy = buddy_create(memsize);
if ( !buddy )
exit(EXIT_FAILURE);
while (true) {
printf("1. allocate, 2. free, "
"3. show alloc list, 4. show free list, "
"5. quit
");
printf("Choose menu: "); scanf("%d", &menu);
switch (menu) {
case 1: if (alloc_page(buddy, &main_list) < 0)
printf("failed to allocate page!
");
break;
case 2: if (free_page(buddy, &main_list) < 0)
printf("failed to free page!
");
break;
case 3: if (show_page(main_list) < 0)
printf("failed to show page!
");
break;
case 4: buddy_show_status(buddy, BUDDY_SHOW_ALL);
break;
case 5: goto WHILE_LOOP_BREAK;
break;
default: printf("invalid menu number
");
break;
}
putchar('
');
} WHILE_LOOP_BREAK:
buddy_destroy(buddy);
return 0;
}
- 헤더파일
bitmap.h
#ifndef BITMAP_H__
#define BITMAP_H__
#include <stdint.h> // uint64_t
#include <stdbool.h> // bool
typedef struct bitmap *Bitmap;
// 비트맵 생성과 제거 함수
Bitmap bitmap_create(uint64_t bitsize);
/* extern Bitmap __bitmap_create(uint64_t size, void *addr, int addr_size); */
// 비트맵 제거 함수
void bitmap_destroy(Bitmap map);
// 비트맵 단항 연산
void bitmap_clear(Bitmap map, bool value);
bool bitmap_get(Bitmap map, uint64_t pos);
void bitmap_set(Bitmap map, uint64_t pos, bool set);
bool bitmap_switch(Bitmap map, uint64_t pos);
uint64_t bitmap_to_int(Bitmap map);
// 비트맵 정보 출력 및 반환 함수
void bitmap_show(Bitmap map, bool high_start);
void bitmap_show_all(Bitmap map, bool high_start);
void bitmap_show_area(Bitmap map, uint64_t start, uint64_t end);
uint64_t bitmap_asize(Bitmap map);
uint64_t bitmap_size(Bitmap map);
int bitmap_bytebit(void);
/* extern int __bitmap_calc_alloc_size(bool is_full_struct, uint64_t size); */
#endif
buddy.h
#ifndef BUDDY_H__
#define BUDDY_H__
// for the MAP_ANONYMOUS macro
#define _GNU_SOURCE
#include "list.h"
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
// PAGE_SHIFT: 페이지가 2 의 몇 승인지를 나타내는 매크로
// PAGE_SIZE: 실제 페이지의 크기
// - 현재 페이지 크기 = 2 ^ 12 byte = 4096 byte = 4 KiB
#define PAGE_SHIFT 12
#define PAGE_SIZE (1UL << PAGE_SHIFT)
// BUDDY_MAX_ORDER: 최대 ORDER 의 크기
// - 현재 BUDDY_MAX_ORDER 는 10 이므로, 한번에 할당 가능한
// 최대 메모리는 4 MiB (2^10 x 4 KiB) 이다.
// BUDDY_MAX_PAGESIZE: 한번에 할당 가능한 연속된 페이지의 최대 크기
#define BUDDY_MAX_ORDER 10
#define BUDDY_MAX_PAGESIZE (PAGE_SIZE << BUDDY_MAX_ORDER)
// TOTAL_PAGES(MEMSIZE): MEMSIZE 에서 할당 가능한 페이지의 개수
// - MEMSIZE 를 PAGE_SHIFT 만큼 right shift 한다는 것은...
// => MEMSIZE 를 2 ^ PAGE_SHIFT 만큼 나누는 것고 동일
// => MEMSIZE 를 PAGE 의 크기로 나누는 것과 동일
// => 그러므로 이는 MEMSIZE 를 기준으로 할당 가능한 PAGE 의 개수를 의미
#define TOTAL_PAGES(MEMSIZE) ((MEMSIZE) >> PAGE_SHIFT)
struct page {
struct list_head list; // free_area_t 구조체와 연결하기 위한 리스트
unsigned long flags; // nothing to do for now
void *addr; // page 의 실제 메모리 주소
int order; // 해당 페이지의 order
};
enum buddy_show_type {
BUDDY_SHOW_BITMAP = 0x01,
BUDDY_SHOW_FREELIST = 0x02,
BUDDY_SHOW_ALL = BUDDY_SHOW_BITMAP & BUDDY_SHOW_FREELIST
};
struct buddy_allocator;
// buddy allocator 생성 & 초기화, 해제 & 제거 함수
struct buddy_allocator *buddy_create(int memsize);
void buddy_destroy(struct buddy_allocator *buddy);
// 페이지 할당, 해제 함수
struct page *buddy_page_alloc(struct buddy_allocator *buddy,
unsigned int order);
void buddy_page_free(struct buddy_allocator *buddy, struct page *page);
// 현재 buddy system 의 상태를 출력하는 함수
void buddy_show_status(struct buddy_allocator *buddy,
enum buddy_show_type type);
#endif
exstdlib.h
#ifndef EX_STDLIB_H__
#define EX_STDLIB_H__
#include <string.h> // for memset()
#include <stdbool.h> // for bool type
#include <stdint.h>
#define memset_mv(DEST, VALUE, SIZE) memset(DEST, VALUE, SIZE), \
DEST = (char *) (DEST) + (SIZE)
#define memcpy_mv(DEST, VALUE, SIZE) memcpy(DEST, VALUE, SIZE), \
DEST = (char *) (DEST) + (SIZE)
#define container_of(PTR, TYPE, MEMBER) \
((TYPE *) ((char *) (PTR) - offsetof(TYPE, MEMBER)))
#define NEWLINE putchar('
')
#define PTR_ADD(PTR, VALUE) *((intptr_t *) &(PTR)) += VALUE
int cprintf(const char *fmt, char chr, int width, ...);
#endif
list.h
#ifndef LIST_H__
#define LIST_H__
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "exstdlib.h"
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(HEAD) { .next = &(HEAD), .prev = &(HEAD) }
#define LIST_ENTRY container_of
#define LIST_ITERATOR_WITH_ENTRY(HEAD, ENTRY, TYPE, MEMBER) \
do { if (HEAD == NULL) \
break; \
\
struct list_head *__LIST_START = HEAD, \
*__LIST_END = HEAD; \
do { \
TYPE *ENTRY = container_of(__LIST_START, TYPE, MEMBER);
/*
* ...
*/
#define LIST_ITERATOR_END \
} while ( __LIST_START = __LIST_START->next, \
__LIST_START != __LIST_END ) ; \
} while (false);
#define LIST_ITERATOR_DELETE_ENTRY list_del(__LIST_START)
#define LIST_ITERATOR_BREAK break
#define LIST_ITERATOR_CONTINUE continue
void list_init(struct list_head *head);
void list_add(struct list_head *head, struct list_head *new);
void list_del(struct list_head *head);
void list_add_tail(struct list_head *, struct list_head *);
#endif
2. 코드 해설
bitmap.c#include "bitmap.h"
#include <stdio.h> // fputc()
#include <stdlib.h> // malloc(), free()
#include <limits.h> // CHAR_BIT
#include <string.h> // memset()
#include "exstdlib.h"
typedef char byte;
#define TYPE_ALIGN(TYPE, X) ( ((X) + ((TYPE) - 1)) / (TYPE) )
#define BITMAP_SIZE (sizeof(btype) * CHAR_BIT)
#define BITS_TO_BYTE(BITS) TYPE_ALIGN(CHAR_BIT, BITS)
#define BITMAP_INDEX_ALIGN(BITSIZE) TYPE_ALIGN( \
sizeof(btype), \
BITS_TO_BYTE(BITSIZE) \
)
#define BITMAP_INDEX(BITSIZE) ((BITSIZE) / (CHAR_BIT * sizeof(btype)))
#define BYTE_BIT CHAR_BIT
#define COMP(X, Y) (((X) > (Y)) ? 1 : -1)
enum bitmap_alloc {
BITMAP_ALLOC_BY_MALLOC,
BITMAP_ALLOC_ADDR_ONLY,
BITMAP_ALLOC_FULL_STRUCT,
BITMAP_ALLOC_INVAL
};
typedef unsigned int btype;
struct bitmap {
int bitsize;
int memsize;
btype *map;
enum bitmap_alloc type;
};
// static void __bitmap_show(btype *map, int index, int shift, bool high_first);
enum bitmap_alloc bitmap_get_type(int size, void *addr, int addr_size)
{
enum bitmap_alloc type;
if (addr != NULL) {
int addr_only = BITMAP_INDEX_ALIGN(size) * sizeof(btype);
int full_struct = addr_only + sizeof(struct bitmap);
if (addr_size >= full_struct)
type = BITMAP_ALLOC_FULL_STRUCT;
else if (addr_size >= addr_only)
type = BITMAP_ALLOC_ADDR_ONLY;
else
type = BITMAP_ALLOC_INVAL;
} else type = BITMAP_ALLOC_BY_MALLOC;
return type;
}
uint64_t bitmap_to_int(Bitmap map)
{
uint64_t value = 0;
return value;
}
Bitmap __bitmap_create(uint64_t size, void *addr, int addr_size)
{
Bitmap bitmap = NULL;
btype *map_addr = NULL;
enum bitmap_alloc type;
type = bitmap_get_type(size, addr, addr_size);
switch (size) {
case BITMAP_ALLOC_FULL_STRUCT: bitmap = addr;
PTR_ADD(addr, sizeof(struct bitmap));
case BITMAP_ALLOC_ADDR_ONLY: map_addr = addr;
case BITMAP_ALLOC_BY_MALLOC: break;
case BITMAP_ALLOC_INVAL: return NULL;
}
if (bitmap == NULL) {
bitmap = malloc(sizeof(struct bitmap));
if (bitmap == NULL)
return NULL;
}
if (map_addr == NULL) {
map_addr = malloc(BITMAP_INDEX_ALIGN(size) * sizeof(btype));
if (map_addr == NULL) {
if (type == BITMAP_ALLOC_BY_MALLOC) free(bitmap);
return NULL;
}
}
bitmap->map = map_addr;
bitmap->type = type;
bitmap->memsize = BITMAP_INDEX_ALIGN(size) * sizeof(btype);
bitmap->bitsize = size;
return bitmap;
}
Bitmap bitmap_create(uint64_t size)
{
return __bitmap_create(size, NULL, 0);
}
int __bitmap_calc_alloc_size(bool is_full_struct, uint64_t size)
{
int addr_only = BITS_TO_BYTE(size);
int full_struct = addr_only + sizeof(struct bitmap);
return (is_full_struct ? full_struct : addr_only);
}
void bitmap_clear(Bitmap bitmap, bool value)
{
memset(bitmap->map, value, bitmap->memsize);
}
bool bitmap_get(Bitmap bitmap, uint64_t pos)
{
uint64_t idx = BITMAP_INDEX(pos);
return (bitmap->map[idx]) & (((btype) 1) << (pos & (BITMAP_SIZE - 1)));
}
bool bitmap_switch(Bitmap bitmap, uint64_t pos)
{
bool prev = bitmap_get(bitmap, pos);
bitmap_set(bitmap, pos, !prev);
return prev;
}
void bitmap_set(Bitmap bitmap, uint64_t pos, bool set)
{
int idx = BITMAP_INDEX(pos);
int shift = pos % BITMAP_SIZE;
if (set)
bitmap->map[idx] |= ((btype) 1) << shift;
else
bitmap->map[idx] &= ((~((btype) 0)) ^ (((btype) 1) << shift));
}
uint64_t bitmap_size(Bitmap bitmap)
{
return bitmap->bitsize;
}
uint64_t bitmap_msize(Bitmap bitmap)
{
return bitmap->memsize;
}
void bitmap_show(Bitmap bitmap, bool high_start)
{
uint64_t start, end;
if (high_start) start = bitmap_size(bitmap) - 1, end = 0;
else start = 0, end = bitmap_size(bitmap) - 1;
bitmap_show_area(bitmap, start, end);
}
void bitmap_show_all(Bitmap bitmap, bool high_start)
{
uint64_t start, end;
if (high_start) start = (bitmap_msize(bitmap) * BYTE_BIT) - 1, end = 0;
else start = 0, end = (bitmap_msize(bitmap) * BYTE_BIT) - 1;
bitmap_show_area(bitmap, start, end);
}
void bitmap_show_area(Bitmap bitmap, uint64_t start, uint64_t end)
{
int nr;
for (nr = start; nr != end; nr += COMP(end, start)) {
fputc(bitmap_get(bitmap, nr) ? '1' : '0', stdout);
if (nr != 0) {
if (nr % BYTE_BIT == 0)
fputc(' ', stdout);
}
}
fputc(bitmap_get(bitmap, nr) ? '1' : '0', stdout);
}
void bitmap_destroy(Bitmap bitmap)
{
switch (bitmap->type) {
case BITMAP_ALLOC_BY_MALLOC:
free(bitmap->map);
case BITMAP_ALLOC_ADDR_ONLY:
free(bitmap);
case BITMAP_ALLOC_FULL_STRUCT:
case BITMAP_ALLOC_INVAL:
/* do nothing */ ;
}
}
int bitmap_bytebit(void)
{
return BYTE_BIT;
}buddy.c#include "buddy.h"
#include "exstdlib.h"
// STRUCT_DATA: buddy_allocator, free_area struct, bitmap, page memory
// 자료구조를 위한 메모리, 이후 init_memory() 에서 사용됨
#define STRUCT_DATA (1 * 1024 * 1024) // 1 MiB
// GET_PAGE_IDX(BUDDY, ADDR): ADDR 에 해당하는 페이지 번호(index)를 반환
#define GET_PAGE_IDX(BUDDY, ADDR) ( \
(((byte *) (ADDR)) - ((byte *) (BUDDY)->lmem_map[0].addr)) / PAGE_SIZE \
)
// 현재 PTR 의 값을 반환하고, PTR 에 SIZE 를 더한다.
#define ALLOC_FROM_PTR(PTR, SIZE) (((PTR) += (SIZE)), (void *) ((PTR) - (SIZE)))
// MARK_USED(INDEX, ORDER, AREA):
// INDEX 와 ORDER 를 참조하여 bitmap 에 page 사용 정보를 매핑한다.
// - INDEX: page 의 실제 index 값
// - ORDER: 현재 order
// - AREA: free_area_t 구조체
//
// - INDEX >> (1 + (ORDER)) 를 통해 해당 ORDER 에서의 bitmap 위치를 알아낸다.
// -----------------------------------------------------------------
// USED(*) | * * * * * - * * - - - * - - - - |
// PAGE | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
// -----------------------------------------------------------------
// ORDER(0) | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
// -----------------------------------------------------------------
// ORDER(1) | 0 | 0 | 1 -> 0 | 0 |
// -----------------------------------------------------------------
// ORDER(2) | 0 | 1 |
// -----------------------------------------------------------------
// ORDER(3) | 0 |
// -----------------------------------------------------------------
// A 상단의 아스키 아트는 free_area[ORDER].map 을 도식화한 것이고,
// V 하단의 아스키 아트는 free_area[ORDER].free_list 를 도식화한 것이다.
// | 9 |
// |...|
// |...|
// |...|
// | 4 |
// | 3 |
// | 2 | <--> C
// | 1 | <--> 8 (will remove)
// | 0 | <--> 5 <--> A
//
// 위와 같은 상황에서 alloc_pages 를 통해 order 1 의 페이지 할당을 요청하면
// 이를 free_list[1] 에서 찾게 된다. 사용 가능한 free page 를 찾으면
// 해당 page 를 반환하고 bitmap 수정을 위해 아래와 같이 매크로를 호출하게 된다.
// MARK_USED(buddy->free_area[1], 8, 1);
// 위 매크로를 호출하게 되면 아래와 같이 치환된다:
// bitmap_set(buddy->free_area[1].map, 8 >> (1 + 1), false);
// bitmap_set(buddy->free_area[1].map, 2, false);
#define MARK_USED(AREA, INDEX, ORDER) \
bitmap_switch((AREA)->map, (INDEX) >> (1 + (ORDER)))
#include <stdbool.h> // true, false
#include <limits.h>
#include <stdint.h>
#include <sys/mman.h>
#include "bitmap.h"
extern Bitmap __bitmap_create(uint64_t size, void *addr, int addr_size);
extern int __bitmap_calc_alloc_size(bool is_full_struct, uint64_t size);
typedef char byte;
// free page 를 관리하기 위한 구조체
struct free_area_t {
struct list_head free_list; // 사용 가능한 page 를 연결한 리스트
Bitmap map; /* 사용 가능한 page 를 알려주는 bitmap
이후 메모리 병합에 사용됨. */
};
struct buddy_allocator {
// 할당된 메모리 크기
unsigned int mem_size;
// page 구조체의 시작 주소
struct page *lmem_map;
// free_pages: 할당 가능한 페이지의 최대 개수
// max_order: 요청 가능 order 의 최댓값
unsigned int free_pages;
unsigned int max_order;
// free page 를 관리하기 위한 구조체
struct free_area_t *free_area;
};
//------------------------------------------------------------------------------
// Local function prototype
//------------------------------------------------------------------------------
static int find_fitness_order(int memsize);
static struct page *expand(
struct page *page,
int index, int low, int high,
struct free_area_t *area
);
static struct buddy_allocator *init_memory(int memsize);
static int calc_gap(int order);
static void buddy_show_order_status(struct buddy_allocator *buddy, int order);
//------------------------------------------------------------------------------
// Global function
//------------------------------------------------------------------------------
struct buddy_allocator *buddy_create(int memsize)
{
unsigned int order_page, total_page, cur_order;
struct buddy_allocator *buddy;
struct free_area_t *area;
// buddy 구조체 완성
buddy = init_memory(memsize);
if (buddy == NULL)
return NULL;
// 현재 order - 1 을 cur_order 로 잡아 페이지를 할당
cur_order = buddy->max_order - 1;
// total: 전체 페이지의 크기
// order: 현재 order 에서 만들 수 있는 페이지의 크기
// 가령 order 가 3 이고 페이지 하나의 크기가 4 KiB 라면
// order_page 는 8 이 된다.
total_page = buddy->free_pages;
order_page = TOTAL_PAGES(PAGE_SIZE << cur_order);
// 일반적으로 order_page 가 total_page 의 절반이 되나,
// 전체 메모리가 너무 커서 최대 order (max_order) 로 표현 가능한
// 페이지의 수가 2 배를 넘는 경우엔 아래의 반복문에서 처리가 이뤄진다.
// free_area list 에 최초의 page 등록
area = &buddy->free_area[cur_order];
list_add(&area->free_list, &buddy->lmem_map[0].list);
// 남은 페이지를 등록, 일반적으로 한번 돌고 끝나지만
// 전체 메모리가 너무 큰 경우 max_order 페이지가 여러 개
// 등록될 수 있기 때문에 반복을 통해 페이지를 추가한다.
for (int nr = 0; nr < total_page - order_page; nr += (1UL << cur_order))
{
int nr_next = nr + (1UL << cur_order);
list_add(&area->free_list, &buddy->lmem_map[nr_next].list);
MARK_USED(area, nr, cur_order);
}
return buddy;
}
// buddy allocator 를 제거한다.
// buddy 는 mmap 을 통해 할당받은 메모리를 적절히 쪼개 할당했으므로 munmap
// 함수를 호출하는 것만으로 모든 buddy 시스템 데이터를 제거하는 것이 가능하다.
void buddy_destroy(struct buddy_allocator *buddy)
{
munmap(buddy, buddy->mem_size + STRUCT_DATA);
printf("free allocated real memory..
");
}
struct page *buddy_page_alloc(struct buddy_allocator *buddy, unsigned int order)
{
struct page *page;
unsigned int cur_order;
struct free_area_t *area;
struct list_head *head, *next;
// 할당하려는 order 가 max_order 다 크다면 NULL 반환
if (buddy->max_order <= order)
return NULL;
// free_area 가져오기
cur_order = order;
area = &buddy->free_area[cur_order];
do {
head = &area->free_list;
next = head->next;
// head 가 next 와 같지 않다? => 할당 가능한 페이지가 존재한다.
if (next != head) {
int index;
/*
* 1. list 에 연결되어 있는 페이지를 가져온다.
* 2. 해당 페이지를 연결 리스트에서 제거한다.
* 3. 페이지의 주소를 통해 페이지 인덱스를 가져온다.
*/
page = LIST_ENTRY(next, struct page, list);
list_del(next);
index = GET_PAGE_IDX(buddy, page->addr);
// max_order 인 경우를 제외한 모든 경우에 MARK 한다.
//if (cur_order != buddy->max_order - 1)
MARK_USED(area, index, cur_order);
// free_pages 를 할당한 크기만큼 줄인다.
buddy->free_pages -= (1UL << order);
// 만일 현재 page 의 order 가 요청한 order 보다 크다면
// page 를 쪼개고 남은 페이지를 할당한다.
page = expand(
/* page, index */
page, index,
/* low, high */
order, cur_order,
/* free area */
area
);
page->order = order;
return page;
}
// cur_order 에서 페이지를 찾지 못하면 여기로 떨어져 내려온다.
// cur_order 에 page 가 없다는 것은 아래를 뜻한다.
// => free_area list 에 그 어떠한 페이지도 없다.
// 따라서 다음 order 로 넘어간다.
cur_order++;
area++;
// order 가 만약 max_order 보다 크다면?
// => 이건 더 이상 할당할 페이지가 없다는 뜻
} while (cur_order < buddy->max_order);
// 그 어디에도 할당 가능한 데이터가 없다면 NULL 반환
return NULL;
}
void buddy_page_free(struct buddy_allocator *buddy, struct page *page)
{
struct free_area_t *area;
unsigned page_idx, bitmap_idx;
int order;
// 반환을 요청한 page 주소를 통해 page 의 index 를 계산
order = page->order;
page_idx = GET_PAGE_IDX(buddy, (unsigned long) page->addr);
bitmap_idx = page_idx >> (1 + order);
area = &buddy->free_area[order];
buddy->free_pages += (1 << order);
while (area < &buddy->free_area[buddy->max_order - 1]) {
// 할당 가능한 page 가 있다면 bitmap 의 값은 1 이다.
// 그런데 bitmap_switch 결과가 0 이다? 이는 buddy page 가
// 옆에 있다는 뜻이므로 merge 해서 상위 order page 로
// 올려 보내야 함을 의미한다.
if ( !bitmap_switch(area->map, bitmap_idx) )
break;
// 제거할 buddy page 의 index 를 구한다.
page_idx = page_idx ^ (1 << order);
list_del(&buddy->lmem_map[page_idx].list);
// 상위 order 로 올라간다.
area++;
order++;
bitmap_idx >>= 1;
// page_idx 를 상위 order 주소에 맞게 align 한다.
page_idx &= (~0 << order);
}
list_add(&area->free_list, &buddy->lmem_map[page_idx].list);
}
// 현재 buddy allocator 의 bitmap 및 free_area list 의 정보를 상세히 출력한다.
void buddy_show_status(struct buddy_allocator *buddy,
enum buddy_show_type type)
{
struct free_area_t *area;
int total_page;
int padd_bitmap, padd_freelist, padd_order;
for (int i = 0; i < buddy->max_order; i++) {
area = &buddy->free_area[i];
total_page = TOTAL_PAGES(PAGE_SIZE << buddy->max_order);
padd_bitmap = bitmap_size(area->map) / bitmap_bytebit() + 2
+ bitmap_size(area->map);
padd_freelist = total_page * (3 + 1) + 1;
padd_order = 12;
// 상단부, 구역별 명칭
putchar('-'); cprintf(" [order] ", '-', padd_order);
cprintf(" [free list] ", '-', padd_freelist);
cprintf(" [bitmap] ", '-', padd_bitmap); NEWLINE;
// 중단부, order, free area list, bitmap 순서대로 출력
putchar('|'); cprintf("%d", ' ', padd_order, i); putchar('|');
buddy_show_order_status(buddy, i);
putchar(' '); bitmap_show(area->map, false); puts(" |");
// 하단부
cprintf("", '-', padd_bitmap + padd_freelist + padd_order + 1);
NEWLINE;
}
}
//------------------------------------------------------------------------------
// Local function
//------------------------------------------------------------------------------
static int find_fitness_order(int memsize)
{
// - 요청한 메모리가 단일 page 크기에 딱 맞아 떨어지는지 확인
// - 최소 할당 단위가 PAGE_SIZE 이므로 당연히 PAGE_SIZE 로 정확하게
// 나누어 떨어져야 한다. 그렇지 않다면 -1 반환.
if ((memsize <= 0) || (memsize % PAGE_SIZE) != 0)
return -1;
// 메모리 크기에 딱 맞는 max order 를 구한다.
if (memsize <= (PAGE_SIZE << (BUDDY_MAX_ORDER - 1))) {
for (int i = 0; i < BUDDY_MAX_ORDER; i++) {
// mem_size 와 동일한 크기의 단일 page order 라면
// 해당 값을 max_order 로 사용한다.
if (memsize == (PAGE_SIZE << i))
return i;
}
return -1;
}
// mem_size 가 max_order 로 할당 가능한 최대 memory 크기보다 크다면
// 당연히 max order 역시 BUDDY SYSTEM 의 MAX ORDER 로 잡는다.
return BUDDY_MAX_ORDER;
}
static struct buddy_allocator *init_memory(int memsize)
{
struct buddy_allocator *buddy;
byte *real_memory;
int max_order;
// memsize 에 적합한 max_order 를 구한다.
max_order = find_fitness_order(memsize);
if (max_order < 0)
return NULL;
// 메모리 동적 할당
real_memory = mmap(
0, memsize + STRUCT_DATA,
PROT_READ | PROT_WRITE | PROT_EXEC,
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0
);
if (real_memory == NULL) {
printf("failed to allocate %d size memory",
memsize + STRUCT_DATA);
return NULL;
} else printf("memory is ready, address is %p
", (void *) real_memory);
/*******************************************************************************
* - buddy system 을 위한 메모리를 할당, 메모리는 아래와 같이 사용된다: *
* r-------T-----------T-------------T--------T----T-----T-----T----T-----7 *
* | buddy | free area | page struct | bitmap | .. | pg0 | pg1 | .. | pgN | *
* L-------^-----------^-------------^--------^----^-----^-----^----^-----J *
******************************************************************************/
// buddy 구조체 기본 데이터 초기화
buddy = ALLOC_FROM_PTR(real_memory, sizeof(struct buddy_allocator));
buddy->mem_size = memsize;
buddy->max_order = max_order;
// free_area 구조체를 위한 공간 할당
buddy->free_area = ALLOC_FROM_PTR(real_memory,
sizeof(struct free_area_t) * buddy->max_order
);
// free_pages 계산, page 구조체를 위한 공간 마련
buddy->lmem_map = ALLOC_FROM_PTR(real_memory,
(sizeof(struct page) * TOTAL_PAGES(buddy->mem_size))
);
buddy->free_pages = TOTAL_PAGES(buddy->mem_size);
printf("allocate memory, size %d bytes
", buddy->mem_size);
printf("total number of page: %u
", buddy->free_pages);
// buddy 구조체 내의 free_area 자료구조의 초기화를 진행한다.
// 각 order 의 list 초기화 및 bitmap 의 생성 및 초기화를 수행한다.
for (int i = 0; i < buddy->max_order; i++) {
unsigned int map_size, struct_size;
list_init(&buddy->free_area[i].free_list);
map_size = (buddy->free_pages / 2) >> i;
struct_size = __bitmap_calc_alloc_size(true, map_size);
printf("order(%d). map_size: %u struct_size: %u
",
i, map_size, struct_size);
buddy->free_area[i].map = __bitmap_create(
map_size,
ALLOC_FROM_PTR(real_memory, struct_size),
struct_size
);
bitmap_clear(buddy->free_area[i].map, 0);
}
// page 구조체의 addr 멤버 변수가 실제 빈 메모리를 가르키도록 한다.
real_memory = (byte *) buddy + STRUCT_DATA;
for (int i = 0; i < buddy->free_pages; i++)
buddy->lmem_map[i].addr = ALLOC_FROM_PTR(
real_memory, PAGE_SIZE
);
return buddy;
}
// buddy_page_free 에 의해 호출되는 함수로 현재 order 에서 할당 가능한 page 가
// 없는 경우 상위 free_area list 에서 할당 가능한 page 를 쪼개어 할당.
static struct page *expand(
struct page *page,
int index, int low, int high,
struct free_area_t *area
)
{
unsigned long size = (1 << high);
// high 는 현재 발견한 상위 free_area list 의 order 이고
// low 는 현재 할당을 요청한 page 의 order 이다.
// index 는 high order 에 존재하는 page 의 index 를 의미한다);
while (high > low) {
// 1. (area - 1) 은 하위 order 로 하강함을 의미한다.
// 2. (high - 1) 역시 상위 order 를 하강함을 의미한다.
// 3. size 역시 2 의 high order 승이므로 같이 맞춰 내린다.
area--;
high--;
size >>= 1;
// 여기에서 기존 page 를 하강한 free_area list 에 등록하는데
// 이렇게 되면 page 의 크기만 반으로 줄어든다. 재미있는 점은
// page 의 index 에는 아무런 변화가 일어나지 않는다는 것이다.
list_add(&area->free_list, &page->list);
// 하위 order 에 사용 가능한 page 두 개가 생겼고 (상위 order 의
// page 를 한 단계 내렸기 때문에) 그 중 하나는 할당 혹은 다시
// 재귀적으로 쪼갤 것이기에 사용 중으로 표시한다.
MARK_USED(area, index, high);
// index 의 크기를 size 만큼 증가
index += size;
// 페이지의 역시 size index 만큼 뛰어 넘는다.
page += size;
}
// 최종적으로 요청한 order 에 해당하는 page 를 반환한다.
return page;
// - 처음에는 위 코드의 동작 방식이 정확하게 이해되지 않을 수 있다.
// 따라서, main 코드를 실행시켜 그 동작을 이해하는 것이 좋다.
// - 최초 page 할당 시 어떠한 방식으로 page 가 쪼개지는지 주목하라.
}
// buddy_show_order_status() 에서 free_area list 간극을 계산하는 함수
static int calc_gap(int order)
{
if (order <= 0)
return 3;
return calc_gap(order - 1) * 2 + 1;
}
// 현재 order 의 free area list 정보를 양식에 맞춰 출력한다.
static void buddy_show_order_status(struct buddy_allocator *buddy, int order)
{
struct free_area_t *area;
int total_page, find;
if (buddy->max_order <= order)
return ;
area = &buddy->free_area[order];
total_page = TOTAL_PAGES(PAGE_SIZE << buddy->max_order);
for (int i = 0; i < total_page; i += ((1 << order)))
{
find = -1;
for (struct page *p = (struct page *) area->free_list.next,
*q = (struct page *) &area->free_list;
p != q;
p = (struct page *) p->list.next)
{
if (GET_PAGE_IDX(buddy, p->addr) == i) {
find = i;
break;
}
}
if (find == -1) cprintf("-", ' ', calc_gap(order));
else cprintf("%d", ' ', calc_gap(order), find);
putchar('|');
}
}exstdlib.c#include "exstdlib.h"
#include <stdio.h> // for printf() series
#include <stdlib.h> // for malloc()
#include <stdarg.h> // for va_*** series
#include <stdbool.h> // true, false
int cprintf(const char *fmt, char chr, int width, ...)
{
static bool rem_dir = true;
char *fmtstr, *alignstr, *trackstr;
int fmtlen, padlen, rem;
va_list ap_for_len, ap_for_read;
if (fmt == NULL)
return (rem_dir = !rem_dir);
va_start(ap_for_len, width);
va_copy(ap_for_read, ap_for_len);
fmtlen = vsnprintf(NULL, 0, fmt, ap_for_len);
fmtstr = malloc(fmtlen + 1);
if(fmtstr == NULL)
goto RETURN_ERR;
vsprintf(fmtstr, fmt, ap_for_read);
va_end(ap_for_read);
va_end(ap_for_len);
padlen = (fmtlen >= width) ? 0 : width - fmtlen;
rem = padlen % 2;
alignstr = malloc(fmtlen + padlen + 1);
if (alignstr == NULL)
goto FREE_FMT_STR;
trackstr = alignstr;
memset_mv(trackstr, chr, padlen / 2 + (rem * (rem_dir == true)));
memcpy_mv(trackstr, fmtstr, fmtlen);
memset_mv(trackstr, chr, padlen / 2 + (rem * (rem_dir == false)));
*trackstr = 'list.c#include "list.h"
void list_init(struct list_head *head)
{
head->next = head;
head->prev = head;
}
void list_add(struct list_head *head, struct list_head *new)
{
// link with (new) <=> (head->next)
head->next->prev = new;
new->next = head->next;
// link with (head) <=> (new)
new->prev = head;
head->next = new;
}
void list_del(struct list_head *entry)
{
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
entry->next = entry->prev = NULL;
}
void list_add_tail(struct list_head *head, struct list_head *new)
{
head->prev->next = new;
new->prev = head->prev;
head->prev = new;
new->next = head;
}main.c#include <stdio.h>
#include <stdlib.h>
#include "buddy.h"
#include "bitmap.h"
#include "list.h"
#define BITMAP_SHOW(BITMAP) bitmap_show_all(BITMAP, true)
struct page_list {
struct page *page;
struct list_head head;
};
int free_page(struct buddy_allocator *buddy, struct list_head **main)
{
int index, order, cnt = 0;
if (main == NULL) goto RETURN_ERR;
printf("index(1 ~ +) or order(- ~ 0): ");
scanf("%d", &index);
if (index <= 0) order = -index;
else order = -1;
LIST_ITERATOR_WITH_ENTRY(*main, entry, struct page_list, head)
if (++cnt == index || entry->page->order == order) {
buddy_page_free(buddy, entry->page);
if (&entry->head == *main) {
if (entry->head.next == &entry->head)
*main = NULL;
else
*main = entry->head.next;
}
LIST_ITERATOR_DELETE_ENTRY;
free(entry);
return 0;
}
LIST_ITERATOR_END
RETURN_ERR: return -1;
}
int alloc_page(struct buddy_allocator *buddy, struct list_head **main)
{
struct page_list *new_plist;
int order;
printf("order: "); scanf("%d", &order);
if (order < 0) goto RETURN_ERR;
new_plist = malloc(sizeof(struct page_list));
if ( !new_plist )
goto RETURN_ERR;
list_init(&new_plist->head);
new_plist->page = buddy_page_alloc(buddy, order);
if ( !new_plist->page )
goto FREE_PLIST;
if ( !*main ) *main = &new_plist->head;
else list_add((*main)->next, &new_plist->head);
return 0;
FREE_PLIST: free(new_plist);
RETURN_ERR: return -1;
}
int show_page(struct list_head *main)
{
int index = 0;
if ( !main )
return -1;
LIST_ITERATOR_WITH_ENTRY(main, entry, struct page_list, head)
printf("index: %d ", ++index);
printf("order: %d
", entry->page->order);
LIST_ITERATOR_END
return 0;
}
int main(void)
{
struct buddy_allocator *buddy;
struct list_head *main_list = NULL;
int memsize, menu;
printf("total memory size(KiB)? ");
scanf("%d", &memsize); memsize *= 1024;
buddy = buddy_create(memsize);
if ( !buddy )
exit(EXIT_FAILURE);
while (true) {
printf("1. allocate, 2. free, "
"3. show alloc list, 4. show free list, "
"5. quit
");
printf("Choose menu: "); scanf("%d", &menu);
switch (menu) {
case 1: if (alloc_page(buddy, &main_list) < 0)
printf("failed to allocate page!
");
break;
case 2: if (free_page(buddy, &main_list) < 0)
printf("failed to free page!
");
break;
case 3: if (show_page(main_list) < 0)
printf("failed to show page!
");
break;
case 4: buddy_show_status(buddy, BUDDY_SHOW_ALL);
break;
case 5: goto WHILE_LOOP_BREAK;
break;
default: printf("invalid menu number
");
break;
}
putchar('
');
} WHILE_LOOP_BREAK:
buddy_destroy(buddy);
return 0;
}bitmap.h#ifndef BITMAP_H__
#define BITMAP_H__
#include <stdint.h> // uint64_t
#include <stdbool.h> // bool
typedef struct bitmap *Bitmap;
// 비트맵 생성과 제거 함수
Bitmap bitmap_create(uint64_t bitsize);
/* extern Bitmap __bitmap_create(uint64_t size, void *addr, int addr_size); */
// 비트맵 제거 함수
void bitmap_destroy(Bitmap map);
// 비트맵 단항 연산
void bitmap_clear(Bitmap map, bool value);
bool bitmap_get(Bitmap map, uint64_t pos);
void bitmap_set(Bitmap map, uint64_t pos, bool set);
bool bitmap_switch(Bitmap map, uint64_t pos);
uint64_t bitmap_to_int(Bitmap map);
// 비트맵 정보 출력 및 반환 함수
void bitmap_show(Bitmap map, bool high_start);
void bitmap_show_all(Bitmap map, bool high_start);
void bitmap_show_area(Bitmap map, uint64_t start, uint64_t end);
uint64_t bitmap_asize(Bitmap map);
uint64_t bitmap_size(Bitmap map);
int bitmap_bytebit(void);
/* extern int __bitmap_calc_alloc_size(bool is_full_struct, uint64_t size); */
#endifbuddy.h#ifndef BUDDY_H__
#define BUDDY_H__
// for the MAP_ANONYMOUS macro
#define _GNU_SOURCE
#include "list.h"
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
// PAGE_SHIFT: 페이지가 2 의 몇 승인지를 나타내는 매크로
// PAGE_SIZE: 실제 페이지의 크기
// - 현재 페이지 크기 = 2 ^ 12 byte = 4096 byte = 4 KiB
#define PAGE_SHIFT 12
#define PAGE_SIZE (1UL << PAGE_SHIFT)
// BUDDY_MAX_ORDER: 최대 ORDER 의 크기
// - 현재 BUDDY_MAX_ORDER 는 10 이므로, 한번에 할당 가능한
// 최대 메모리는 4 MiB (2^10 x 4 KiB) 이다.
// BUDDY_MAX_PAGESIZE: 한번에 할당 가능한 연속된 페이지의 최대 크기
#define BUDDY_MAX_ORDER 10
#define BUDDY_MAX_PAGESIZE (PAGE_SIZE << BUDDY_MAX_ORDER)
// TOTAL_PAGES(MEMSIZE): MEMSIZE 에서 할당 가능한 페이지의 개수
// - MEMSIZE 를 PAGE_SHIFT 만큼 right shift 한다는 것은...
// => MEMSIZE 를 2 ^ PAGE_SHIFT 만큼 나누는 것고 동일
// => MEMSIZE 를 PAGE 의 크기로 나누는 것과 동일
// => 그러므로 이는 MEMSIZE 를 기준으로 할당 가능한 PAGE 의 개수를 의미
#define TOTAL_PAGES(MEMSIZE) ((MEMSIZE) >> PAGE_SHIFT)
struct page {
struct list_head list; // free_area_t 구조체와 연결하기 위한 리스트
unsigned long flags; // nothing to do for now
void *addr; // page 의 실제 메모리 주소
int order; // 해당 페이지의 order
};
enum buddy_show_type {
BUDDY_SHOW_BITMAP = 0x01,
BUDDY_SHOW_FREELIST = 0x02,
BUDDY_SHOW_ALL = BUDDY_SHOW_BITMAP & BUDDY_SHOW_FREELIST
};
struct buddy_allocator;
// buddy allocator 생성 & 초기화, 해제 & 제거 함수
struct buddy_allocator *buddy_create(int memsize);
void buddy_destroy(struct buddy_allocator *buddy);
// 페이지 할당, 해제 함수
struct page *buddy_page_alloc(struct buddy_allocator *buddy,
unsigned int order);
void buddy_page_free(struct buddy_allocator *buddy, struct page *page);
// 현재 buddy system 의 상태를 출력하는 함수
void buddy_show_status(struct buddy_allocator *buddy,
enum buddy_show_type type);
#endifexstdlib.h#ifndef EX_STDLIB_H__
#define EX_STDLIB_H__
#include <string.h> // for memset()
#include <stdbool.h> // for bool type
#include <stdint.h>
#define memset_mv(DEST, VALUE, SIZE) memset(DEST, VALUE, SIZE), \
DEST = (char *) (DEST) + (SIZE)
#define memcpy_mv(DEST, VALUE, SIZE) memcpy(DEST, VALUE, SIZE), \
DEST = (char *) (DEST) + (SIZE)
#define container_of(PTR, TYPE, MEMBER) \
((TYPE *) ((char *) (PTR) - offsetof(TYPE, MEMBER)))
#define NEWLINE putchar('
')
#define PTR_ADD(PTR, VALUE) *((intptr_t *) &(PTR)) += VALUE
int cprintf(const char *fmt, char chr, int width, ...);
#endiflist.h#ifndef LIST_H__
#define LIST_H__
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "exstdlib.h"
struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(HEAD) { .next = &(HEAD), .prev = &(HEAD) }
#define LIST_ENTRY container_of
#define LIST_ITERATOR_WITH_ENTRY(HEAD, ENTRY, TYPE, MEMBER) \
do { if (HEAD == NULL) \
break; \
\
struct list_head *__LIST_START = HEAD, \
*__LIST_END = HEAD; \
do { \
TYPE *ENTRY = container_of(__LIST_START, TYPE, MEMBER);
/*
* ...
*/
#define LIST_ITERATOR_END \
} while ( __LIST_START = __LIST_START->next, \
__LIST_START != __LIST_END ) ; \
} while (false);
#define LIST_ITERATOR_DELETE_ENTRY list_del(__LIST_START)
#define LIST_ITERATOR_BREAK break
#define LIST_ITERATOR_CONTINUE continue
void list_init(struct list_head *head);
void list_add(struct list_head *head, struct list_head *new);
void list_del(struct list_head *head);
void list_add_tail(struct list_head *, struct list_head *);
#endif코드 해설은 소스 코드 내의 주석으로 달아 놓았기에 생략하겠다.
3. 실행 결과
출처
[책] 리눅스 커널 내부구조 (백승제, 최종무 저)
Author And Source
이 문제에 관하여(리눅스 커널 내부구조 10장 #3 buddy allocator), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mythos/리눅스-커널-내부구조-10장-3-buddy-allocator저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
