slab malloc / ücretsiz uygulama
Bu öğreticinin rehberliğinde bellek ayırıcıyı yerleştirmeye çalışıyorum . Next-fit arama ve Ayrılmış liste aramasının bir karışımını kullandım.
Farklı boyutlarda birden fazla levha vardır (bir levha, aynı boyutta bulaşıcı bellek blokları ve ayrıca bir başlıktır). Bir döşemede serbest blok kalmamışsa, aynı boyutta yeni bir levha tahsis eder ve onu mevcut döşemeye bağlar. ücretsiz bloklar, her bir levhanın başlığındaki bir bitmap kullanılarak izlenir.
Tasarımım bellek ve hız açısından nasıl?
Boyutu bilmeden bir bloğu hangi levhanın serbest bırakacağını belirlemenin bir yolu var mı? mevcut yaklaşım, tüm plakalardan bloğu serbest bırakmalarını istemektir, bu bloğun sahibi onu serbest bırakacaktır.
Büyük boyutlarda bellekle başa çıkmanın en iyi yolu nedir (plakalardan daha büyük)
Buna nasıl bazı birim testleri yazabilirim? Döndürülen adresin geçerli olup olmadığını anlamak zor.
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 (gerçekten önemli değil)
#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);
}
Yanıtlar
Sorularınıza cevaplar
Tasarımım bellek ve hız açısından nasıl?
Bu kolay: ölçün! Belleği ayırıp serbest bırakan ve ne kadar süreceğini zamanlayan bir miktar iş yükü oluşturun. Örneğin getrusage()Linux'ta programınızın ne kadar bellek kullandığını size söyleyebilen işletim sistemi işlevleri de vardır . İki sürümü, kimse döşeme ayırıcısı kullanarak ve başka kullanılarak düzenli mı malloc()/free(), new/deleteya da ne şekilde olursa olsun işletim sisteminden bellek almak ve performans farkını kontrol etmek gerekir.
Boyutu bilmeden bir bloğu hangi levhanın serbest bırakacağını belirlemenin bir yolu var mı? mevcut yaklaşım, tüm plakalardan bloğu serbest bırakmalarını istemektir, bu bloğun sahibi onu serbest bırakacaktır.
Bunun bir yolu, geri dönen bellek bölgesinden hemen önce küçük bir başlığın ayrılması alloc()ve döşeme ayırıcı nesnesinin kendisinin göstericisi gibi bazı meta verileri bu başlıkta depolamaktır. Diğer bir seçenek de, döşemelerin her zaman bellekte doğal olarak hizalanmasını sağlamaktır, böylece döşemenin nereden geldiğine bakılmaksızın, döşemenin başlangıcına hızlı bir şekilde bir işaretçi alabilirsiniz.
Ancak çoğu kez arayan kişi custom_free(), serbest bıraktığı nesnenin boyutunu gerçekten bilir. Bu nedenle, bir boyut parametresi eklemek mantıklıdır custom_free(), böylece custom_malloc()kurtulmak için doğru levha nesnesini bulmak için yaptığınız aynı şeyi yapabilir .
Büyük boyutlarda bellekle başa çıkmanın en iyi yolu nedir (plakalardan daha büyük)
Sonra normal bir malloc()veya new.
Buna nasıl bazı birim testleri yazabilirim? Döndürülen adresin geçerli olup olmadığını anlamak zor.
Bir olasılık, sadece birim testinde tahsis edilen belleğe yazmak ve ardından AddressSanitizer etkinken birim testlerini derlemektir . Alternatif olarak, geçersiz adreslere yazılanları yakalamak için Valgrind içinde birim testini çalıştırın .
uint64_tBitmap dizisi için kullanın
Bu kodu özellikle 8 bitlik bir mikro denetleyicide çalıştırmak için yazmıyorsanız uint64_t, bitmap dizisi için kullanmanızı öneririm . Bunun nedeni, günümüzde bilgisayarların 64-bit yazmaçlara sahip olması ve bir seferde 64-bit üzerindeki işlemlerin, bir seferde 8-bit kadar hızlı veya hatta bazen daha hızlı olmasıdır.
Bir bitmapte ilk set bitini bulmak için donanım talimatlarını kullanın
Çoğu işlemcinin tam sayıdaki ilk biti bulma talimatları vardır. Bu, kullanım için mükemmeldir Bitmap::find_used(). C ++ 20'de, std::countl_zero()bu işlevselliğe erişmek için ilgili işlevleri kullanabileceksiniz, ancak henüz C ++ 20'yi kullanamıyorsanız, o zaman ffs()GCC'ler gibi platforma özgü işlevlere veya __builtin_clz()bunu yapmak için GCC'ler gibi derleyici yerleşiklerine sahip olabilirsiniz. aynı.
Sınıflarınız için uygun kurucular yazın
init()Sınıflarınızda bir işleve sahip olmamalı , ancak başlatmayı gerçekleştiren uygun bir kurucuya sahip olmalısınız . Bu, yanlışlıkla başlatıcıyı aramayı veya iki kez aramayı unutmanız olasılığını ortadan kaldırır.
Yıkıcı yaz class Slab
Bir levha tarafından kullanılmakta olan tüm bellekleri yok edildiğinde temizleyen bir yıkıcı yazmalısınız.