슬랩 malloc / 무료 구현
이 튜토리얼에서 안내하는 메모리 할당자를 구현하려고합니다 . 저는 Next-fit 검색과 Segregated-list 검색을 혼합하여 사용했습니다.
크기가 다른 여러 개의 슬래브가 있습니다 (슬래브는 동일한 크기의 전염성이있는 메모리 블록과 헤더입니다). 슬래브에 여유 블록이 부족하면 동일한 크기의 새 슬래브를 할당하고 현재 슬래브에 연결합니다. 여유 블록은 각 슬래브의 헤더에있는 비트 맵을 사용하여 추적됩니다.
메모리 및 속도 측면에서 내 디자인은 어떻습니까?
크기를 모르고 블록을 해제 할 슬래브를 결정하는 방법이 있습니까? 현재 접근 방식은 모든 슬래브에 블록을 해제하도록 요청하는 것입니다. 해당 블록을 소유 한 사람이 블록을 해제합니다.
큰 크기의 메모리를 처리하는 가장 좋은 방법은 무엇입니까 (슬래브보다 큼)
여기에 몇 가지 단위 테스트를 어떻게 작성할 수 있습니까? 반환 된 주소가 유효한지 여부를 파악하기가 어렵습니다.
malloc.cpp#include "slab_allocator.h" const size_t PAGE_SIZE = 0x1000; static Slab<0x010, PAGE_SIZE> slab_0x10; static Slab<0x020, PAGE_SIZE> slab_0x20; static Slab<0x040, PAGE_SIZE> slab_0x40; static Slab<0x060, PAGE_SIZE> slab_0x60; static Slab<0x100, PAGE_SIZE> slab_0x100; static Slab<0x200, PAGE_SIZE> slab_0x200; static Slab<0x300, PAGE_SIZE> slab_0x300; void init() { slab_0x10.init(); slab_0x20.init(); slab_0x40.init(); slab_0x60.init(); slab_0x100.init(); slab_0x200.init(); slab_0x300.init(); } void* custom_malloc(size_t size) { if (size < 0x10) { return slab_0x10.alloc(); } else if (size < 0x20) { return slab_0x10.alloc(); } else if (size < 0x40) { return slab_0x40.alloc(); } else if (size < 0x60) { return slab_0x60.alloc(); } else if (size < 0x100) { return slab_0x100.alloc(); } else if (size < 0x200) { return slab_0x200.alloc(); } else if (size < 0x500) { return slab_0x300.alloc(); } else { return nullptr; } } void custom_free(void* address) { slab_0x10.free(address); slab_0x20.free(address); slab_0x40.free(address); slab_0x60.free(address); slab_0x100.free(address); slab_0x200.free(address); slab_0x300.free(address); }
slab_allocator.h :
#pragma once
#include "bitmap.h"
#include <cstdint>
#include <Windows.h>
template<size_t slab_size, size_t memory_size> class Slab;
template<size_t slab_size, size_t memory_size, size_t max_blocks = memory_size / slab_size> struct SlabHeader {
Slab<slab_size, memory_size>* prev, * next;
Bitmap<max_blocks> mem_map;
size_t free_blocks;
size_t next_fit_block;
};
template<size_t slab_size, size_t memory_size> class Slab {
private:
const static size_t MAX_HEADER_SIZE = sizeof(SlabHeader<slab_size, memory_size>);
const static size_t MAX_BLOCKS = (memory_size - MAX_HEADER_SIZE) / slab_size;
static_assert(memory_size > MAX_HEADER_SIZE);
static_assert((slab_size + MAX_HEADER_SIZE) <= memory_size);
SlabHeader<slab_size, memory_size, MAX_BLOCKS> header;
char blocks[MAX_BLOCKS][slab_size];
bool is_address_in_slab(void* address);
void* alloc_in_current_slab(size_t block_index);
void* alloc_in_new_slab();
void free_from_current_slab(size_t block_index);
void free_from_next_slab(void* address);
void* request_memory_from_os(size_t size);
void free_memory_to_os(void* addrss, size_t size);
public:
void init(Slab* prev = nullptr);
void* alloc();
void free(void* address);
};
template<size_t slab_size, size_t memory_size>
void Slab<slab_size, memory_size>::init(Slab* prev) {
header.prev = prev;
header.next = nullptr;
header.free_blocks = MAX_BLOCKS;
header.next_fit_block = 0;
header.mem_map.init();
}
template<size_t slab_size, size_t memory_size>
void* Slab<slab_size, memory_size>::alloc() {
size_t block_index = -1;
if (header.free_blocks &&
((block_index = header.mem_map.find_unused(header.next_fit_block)) != BITMAP_NO_BITS_LEFT)) {
return alloc_in_current_slab(block_index);
} else {
return alloc_in_new_slab();
}
}
template<size_t slab_size, size_t memory_size>
void Slab<slab_size, memory_size>::free(void* address) {
if (is_address_in_slab(address) == false) {
return free_from_next_slab(address);
}
size_t block_index = (uintptr_t(address) - uintptr_t(blocks)) / slab_size;
assert(header.mem_map.check_used(block_index));
free_from_current_slab(block_index);
}
template<size_t slab_size, size_t memory_size>
bool Slab<slab_size, memory_size>::is_address_in_slab(void* address) {
if ((address >= blocks) && (address <= &blocks[MAX_BLOCKS - 1][slab_size - 1])) {
return true;
} else {
return false;
}
}
template<size_t slab_size, size_t memory_size>
void* Slab<slab_size, memory_size>::alloc_in_new_slab() {
Slab* new_slab = static_cast<Slab*>(request_memory_from_os(sizeof(Slab)));
if (!new_slab) {
return nullptr;
}
new_slab->init(this);
header.next = new_slab;
return new_slab->alloc();
}
template<size_t slab_size, size_t memory_size>
void* Slab<slab_size, memory_size>::alloc_in_current_slab(size_t block_index) {
header.mem_map.set_used(block_index);
header.next_fit_block = (block_index + 1) % MAX_BLOCKS;
header.free_blocks--;
return static_cast<void*>(blocks[block_index]);
}
template<size_t slab_size, size_t memory_size>
void Slab<slab_size, memory_size>::free_from_current_slab(size_t block_index) {
header.mem_map.set_unused(block_index);
header.next_fit_block = block_index;
header.free_blocks++;
if ((header.free_blocks == 0) && (header.prev)) {
//slab is empty, and it's not the first;
header.prev->header.next = nullptr;
free_memory_to_os(this, sizeof(Slab));
//The slab committed suicide, don't ever use it again!
}
}
template<size_t slab_size, size_t memory_size>
void Slab<slab_size, memory_size>::free_from_next_slab(void* address) {
if (header.next) {//if there is another slab in the list check on it too.
header.next->free(address);
return;
} else {
//address doesn't belong any slab.
return;
}
}
template<size_t slab_size, size_t memory_size>
void* Slab<slab_size, memory_size>::request_memory_from_os(size_t size) {
//system dependent function, returns aligned memory region.
return VirtualAlloc(0, size, MEM_COMMIT, PAGE_READWRITE);
}
template<size_t slab_size, size_t memory_size>
void Slab<slab_size, memory_size>::free_memory_to_os(void* addrss, size_t size) {
//system dependent function, returns aligned memory region.
VirtualFree(addrss, size, MEM_FREE);
}
Bitmap.h (정말 중요하지 않음)
#pragma once
#include <cstdint>
#include <assert.h>
#include <cstring>
#define CHECK_BIT(value, bit) ((value >> bit) & 1)
#define BITMAP_NO_BITS_LEFT 0xFFFFFFFF
template <size_t SIZE> class Bitmap {
private:
uint8_t m_bitmap_data[SIZE];
public:
void init();
void set_used(unsigned position);
void set_unused(unsigned position);
unsigned find_unused(unsigned search_start = 0);
unsigned find_used(unsigned search_start = 0);
bool check_used(unsigned position);
bool check_unused(unsigned position);
};
template <size_t SIZE> void Bitmap<SIZE>::init() {
memset(m_bitmap_data, 0, sizeof(m_bitmap_data));
}
template <size_t SIZE> void Bitmap<SIZE>::set_used(unsigned position) {
assert(position < SIZE);
m_bitmap_data[position / 8] |= (1 << (position % 8));
}
template <size_t SIZE> void Bitmap<SIZE>::set_unused(unsigned position) {
assert(position < SIZE);
m_bitmap_data[position / 8] &= ~(1 << (position % 8));
}
template <size_t SIZE> unsigned Bitmap<SIZE>::find_unused(unsigned search_start) {
assert(search_start < SIZE);
size_t bit_index = search_start;
while (bit_index < SIZE) {
if (m_bitmap_data[bit_index / 8] == 0xFF) {
bit_index += 8;
continue;
}
if (!CHECK_BIT(m_bitmap_data[bit_index / 8], bit_index % 8))
return bit_index;
bit_index++;
}
return BITMAP_NO_BITS_LEFT;
}
template <size_t SIZE> unsigned Bitmap<SIZE>::find_used(unsigned search_start) {
assert(search_start < SIZE);
size_t bit_index = search_start;
while (bit_index < SIZE) {
if (m_bitmap_data[bit_index / 8] == 0) {
bit_index += 8;
continue;
}
if (CHECK_BIT(m_bitmap_data[bit_index / 8], bit_index % 8))
return bit_index;
bit_index++;
}
return BITMAP_NO_BITS_LEFT;
}
template <size_t SIZE> bool Bitmap<SIZE>::check_used(unsigned position) {
return CHECK_BIT(m_bitmap_data[position / 8], position % 8);
}
template <size_t SIZE> bool Bitmap<SIZE>::check_unused(unsigned position) {
return !CHECK_BIT(m_bitmap_data[position / 8], position % 8);
}
답변
질문에 대한 답변
메모리 및 속도 측면에서 내 디자인은 어떻습니까?
간단합니다. 측정하세요! 메모리를 할당하고 해제하는 워크로드를 생성하고 시간이 얼마나 걸리는지 확인하십시오. 예를 들어 getrusage()Linux에서 프로그램이 사용중인 메모리 양을 알려줄 수있는 운영 체제 기능도 있습니다 . 두 가지 버전, 하나 귀하의 슬랩 할당을 사용하고, 다른 사용 규칙이 malloc()/free(), new/delete또는 어떤 방법으로 운영 체제에서 메모리를 얻을 수 및 성능의 차이를 확인해야합니다.
크기를 모르고 블록을 해제 할 슬래브를 결정하는 방법이 있습니까? 현재 접근 방식은 모든 슬래브에 블록을 해제하도록 요청하는 것입니다. 해당 블록을 소유 한 사람이 블록을 해제합니다.
한 가지 방법은에서 반환 한 메모리 영역 바로 앞에 약간의 헤더를 할당 alloc()하고 해당 헤더에 슬랩 할당 자 객체 자체에 대한 포인터와 같은 일부 메타 데이터를 저장하는 것입니다. 또 다른 옵션은 슬래브가 항상 메모리에서 자연스럽게 정렬되도록하는 것이므로, 슬래브에서 할당이 발생한 위치에 관계없이 슬래브의 시작에 대한 포인터를 빠르게 얻을 수 있습니다.
그러나 종종의 호출자 custom_free()는 실제로 해제되는 개체의 크기를 알고 있습니다. 따라서에 크기 매개 변수를 추가하는 것이 합리적 custom_free()이므로에서 제거 custom_malloc()할 올바른 슬래브 객체를 찾기 위해 수행하는 것과 동일한 작업을 수행 할 수 있습니다.
큰 크기의 메모리를 처리하는 가장 좋은 방법은 무엇입니까 (슬래브보다 큼)
그런 다음 일반 malloc()또는 new.
여기에 몇 가지 단위 테스트를 어떻게 작성할 수 있습니까? 반환 된 주소가 유효한지 여부를 파악하기가 어렵습니다.
한 가지 가능성은 단위 테스트에서 할당 된 메모리에 기록한 다음 AddressSanitizer가 활성화 된 상태 에서 단위 테스트를 컴파일하는 것 입니다. 또는 Valgrind 내에서 단위 테스트를 실행하여 유효하지 않은 주소에 대한 쓰기를 포착하십시오.
사용 uint64_t비트 맵 배열
8 비트 마이크로 컨트롤러에서 실행되도록 특별히이 코드를 작성하지 않는 한 uint64_t비트 맵 배열 을 사용 하는 것이 좋습니다 . 그 이유는 오늘날 컴퓨터에는 64 비트 레지스터가 있고 한 번에 64 비트 작업이 한 번에 8 비트보다 빠르거나 때로는 더 빠르기 때문입니다.
하드웨어 지침을 사용하여 비트 맵에서 첫 번째 세트 비트 찾기
대부분의 프로세서에는 정수에서 첫 번째 세트 비트를 찾는 명령이 있습니다. 에서 사용하기에 적합 Bitmap::find_used()합니다. C ++ 20에서는 std::countl_zero()및 관련 함수 를 사용 하여 해당 기능에 액세스 할 수 있지만 아직 C ++ 20을 사용할 수없는 경우 ffs()GCC와 같은 플랫폼 별 함수 또는 컴파일러 내장 기능이있을 수 있습니다 __builtin_clz(). 같은.
클래스에 대한 적절한 생성자 작성
init()클래스에 함수 가 없어야 하지만 초기화를 수행하는 적절한 생성자가 있어야합니다. 그러면 실수로 초기화 프로그램을 호출하는 것을 잊거나 두 번 호출 할 가능성을 피할 수 있습니다.
소멸자 작성 class Slab
슬래브가 소멸 될 때 사용중인 나머지 메모리를 정리하는 소멸자를 작성해야합니다.