slab malloc / implementasi gratis
Saya mencoba untuk mengimplementasikan pengalokasi memori yang dipandu oleh tutorial ini . Saya menggunakan campuran pencarian Next-fit dan pencarian daftar-terpisah.
Ada beberapa lempengan dengan ukuran berbeda (lempengan adalah blok memori yang menular dengan ukuran yang sama, ditambah tajuk). Jika slab kehabisan blok bebas, slab tersebut mengalokasikan slab baru dengan ukuran yang sama dan menautkannya ke slab saat ini. blok gratis dilacak menggunakan bitmap di header setiap slab.
Bagaimana desain saya dalam hal memori & kecepatan?
Adakah cara untuk menentukan pelat mana yang akan membebaskan satu blok, tanpa mengetahui ukurannya? pendekatan saat ini adalah meminta semua lempengan untuk membebaskan blok, orang yang memiliki blok itu akan membebaskannya.
Apa cara terbaik untuk menangani ukuran memori yang besar (lebih besar dari slab)
Bagaimana saya bisa menulis beberapa tes unit untuk ini? sulit untuk mengetahui apakah alamat yang dikembalikan valid atau tidak.
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 (tidak terlalu penting)
#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);
}
Jawaban
Jawaban atas pertanyaan Anda
Bagaimana desain saya dalam hal memori & kecepatan?
Itu mudah: ukurlah! Buat beberapa beban kerja yang mengalokasikan dan membebaskan memori, dan menghitung berapa lama waktu yang dibutuhkan. Ada juga fungsi sistem operasi yang dapat memberi tahu Anda berapa banyak memori yang digunakan program Anda, misalnya getrusage()di Linux. Memiliki dua versi, satu menggunakan pengalokasi slab Anda, dan lain menggunakan reguler malloc()/free(), new/deleteatau cara apa pun yang Anda harus mendapatkan memori dari sistem operasi, dan memeriksa perbedaan dalam kinerja.
Adakah cara untuk menentukan pelat mana yang akan membebaskan satu blok, tanpa mengetahui ukurannya? pendekatan saat ini adalah meminta semua lempengan untuk membebaskan blok, orang yang memiliki blok itu akan membebaskannya.
Salah satu caranya adalah dengan memiliki sedikit header yang dialokasikan tepat sebelum wilayah memori dikembalikan oleh alloc(), dan menyimpan beberapa metadata di header itu, seperti penunjuk ke objek pengalokasi slab itu sendiri. Pilihan lainnya adalah memastikan slab selalu sejajar secara alami dalam memori, sehingga Anda bisa dengan cepat mendapatkan penunjuk ke awal slab, terlepas dari dari mana asal alokasi slab.
Namun seringkali, penelepon custom_free()benar-benar mengetahui ukuran objek yang dikosongkan. Jadi masuk akal untuk menambahkan parameter ukuran ke custom_free(), sehingga dapat melakukan hal yang sama seperti yang Anda lakukan custom_malloc()untuk menemukan objek slab yang tepat untuk dibebaskan.
Apa cara terbaik untuk menangani ukuran memori yang besar (lebih besar dari slab)
Kemudian Anda hanya kembali ke biasa malloc()atau new.
Bagaimana saya bisa menulis beberapa tes unit untuk ini? sulit untuk mengetahui apakah alamat yang dikembalikan valid atau tidak.
Salah satu kemungkinannya adalah dengan hanya menulis ke memori yang dialokasikan dalam pengujian unit, dan kemudian mengkompilasi pengujian unit dengan AddressSanitizer diaktifkan. Atau, jalankan pengujian unit di dalam Valgrind untuk menangkap penulisan ke alamat yang tidak valid.
Gunakan uint64_tuntuk larik bitmap
Kecuali Anda secara khusus menulis kode ini untuk dijalankan pada mikrokontroler 8-bit, saya sarankan Anda menggunakan uint64_tuntuk array bitmap. Alasannya adalah bahwa komputer saat ini memiliki register 64-bit, dan operasi pada 64-bit pada suatu waktu sama cepatnya atau terkadang bahkan lebih cepat daripada pada 8-bit sekaligus.
Gunakan petunjuk perangkat keras untuk menemukan bit set pertama dalam bitmap
Kebanyakan prosesor memiliki instruksi untuk menemukan bit set pertama dalam sebuah integer. Ini sempurna untuk digunakan dalam Bitmap::find_used(). Di C ++ 20, Anda akan dapat menggunakan std::countl_zero()dan fungsi terkait untuk mengakses fungsionalitas itu, tetapi jika Anda belum dapat menggunakan C ++ 20, Anda mungkin memiliki fungsi khusus platform seperti ffs()atau kompiler bawaan seperti GCC __builtin_clz()untuk melakukan sama.
Tulis konstruktor yang tepat untuk kelas Anda
Anda seharusnya tidak memiliki init()fungsi di kelas Anda, tetapi konstruktor tepat yang melakukan inisialisasi. Itu menghindari kemungkinan bahwa Anda secara tidak sengaja lupa memanggil penginisialisasi, atau memanggilnya dua kali.
Tulis destruktor untuk class Slab
Anda harus menulis sebuah destruktor yang membersihkan sisa memori yang digunakan oleh lempengan saat dimusnahkan.