implementazione slab malloc / free
Sto cercando di implementare l'allocatore di memoria guidato da questo tutorial . Ho usato un mix di ricerca Next-fit e ricerca in elenco segregato.
Esistono più lastre di dimensioni diverse (una lastra è costituita da blocchi di memoria contagiosi della stessa dimensione, più un'intestazione). Se una lastra esaurisce i blocchi liberi, alloca una nuova lastra della stessa dimensione e la collega alla lastra corrente. i blocchi liberi vengono tracciati utilizzando una bitmap nell'intestazione di ogni lastra.
Com'è il mio design in termini di memoria e velocità?
C'è un modo per determinare da quale lastra liberare un blocco, senza conoscerne le dimensioni? l'approccio attuale è chiedere a tutte le lastre di liberare il blocco, chi possiede quel blocco lo libererà.
Qual è il modo migliore per gestire grandi formati di memoria (più grandi di quelli delle lastre)
Come posso scrivere alcuni unit test su questo? è difficile capire se l'indirizzo restituito è valido o meno.
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 (non molto importante)
#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);
}
Risposte
Risposte alle tue domande
Com'è il mio design in termini di memoria e velocità?
È facile: misuralo! Crea un carico di lavoro che alloca e libera la memoria e il tempo necessario. Ci sono anche funzioni del sistema operativo che possono dirti quanta memoria sta usando il tuo programma, ad esempio getrusage()su Linux. Avere due versioni, una con il tuo allocatore slab, e un altro utilizzando normali malloc()/free(), new/deleteo qualunque modo si deve ottenere memoria dal sistema operativo, e verificare la differenza in termini di prestazioni.
C'è un modo per determinare da quale lastra liberare un blocco, senza conoscerne le dimensioni? l'approccio attuale è chiedere a tutte le lastre di liberare il blocco, chi possiede quel blocco lo libererà.
Un modo è avere una piccola intestazione allocata subito prima della regione di memoria restituita da alloc()e memorizzare alcuni metadati in quell'intestazione, come il puntatore all'oggetto allocatore slab stesso. Un'altra opzione è garantire che le lastre siano sempre allineate naturalmente in memoria, in modo da poter ottenere rapidamente un puntatore all'inizio della lastra, indipendentemente da dove proviene l'allocazione.
Ma spesso, il chiamante custom_free()conoscerà effettivamente la dimensione dell'oggetto che sta liberando. Quindi ha senso aggiungere un parametro di dimensione custom_free(), in modo che possa fare la stessa cosa che fai custom_malloc()per trovare l'oggetto lastra giusto da cui liberarti.
Qual è il modo migliore per gestire grandi formati di memoria (più grandi di quelli delle lastre)
Quindi torni a un normale malloc()o new.
Come posso scrivere alcuni unit test su questo? è difficile capire se l'indirizzo restituito è valido o meno.
Una possibilità è scrivere nella memoria allocata nello unit test e quindi compilare gli unit test con AddressSanitizer abilitato. In alternativa, eseguire lo unit test all'interno di Valgrind per rilevare le scritture su indirizzi non validi.
Utilizzare uint64_tper la matrice bitmap
A meno che tu non stia scrivendo specificamente questo codice per funzionare su un microcontrollore a 8 bit, ti suggerisco di usarlo uint64_tper l'array bitmap. Il motivo è che i computer oggigiorno hanno registri a 64 bit e le operazioni su 64 bit alla volta sono altrettanto veloci o talvolta anche più veloci di quelle su 8 bit alla volta.
Utilizzare le istruzioni hardware per trovare il primo bit impostato in una bitmap
La maggior parte dei processori ha istruzioni per trovare il primo bit impostato in un numero intero. Questo è perfetto per l'uso in Bitmap::find_used(). In C ++ 20, sarai in grado di utilizzare std::countl_zero()e le funzioni correlate per accedere a tale funzionalità, ma se non puoi ancora utilizzare C ++ 20, potresti avere funzioni specifiche della piattaforma come ffs()o incorporati del compilatore come GCC __builtin_clz()per eseguire il stesso.
Scrivi i costruttori appropriati per le tue classi
Non dovresti avere una init()funzione nelle tue classi, ma un costruttore appropriato che esegue l'inizializzazione. Ciò evita la possibilità che ti dimentichi accidentalmente di chiamare l'inizializzatore o lo chiami due volte.
Scrivi un distruttore per class Slab
Dovresti scrivere un distruttore che pulisca tutta la memoria rimanente che è in uso da una lastra quando viene distrutta.