laje malloc / implementação livre
Estou tentando implementar o alocador de memória guiado por este tutorial . Usei uma combinação de pesquisa de ajuste seguinte e pesquisa de lista segregada.
Existem várias placas de tamanhos diferentes (uma placa é contagiante blocos de memória do mesmo tamanho, mais um cabeçalho). Se uma laje ficar sem blocos livres, ele aloca uma nova laje do mesmo tamanho e a liga à laje atual. blocos livres são rastreados usando um bitmap no cabeçalho de cada placa.
Como está o meu design em termos de memória e velocidade?
Existe alguma maneira de determinar de qual laje liberar um bloco, sem saber o tamanho? a abordagem atual é pedir a todas as lajes para liberar o bloco, aquele que possui esse bloco irá liberá-lo.
Qual é a melhor maneira de lidar com grandes tamanhos de memória (maiores do que placas)
Como posso escrever alguns testes de unidade para isso? é difícil descobrir se o endereço retornado é válido ou não.
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 (não é muito 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);
}
Respostas
Respostas às suas perguntas
Como está o meu design em termos de memória e velocidade?
É fácil: meça! Crie alguma carga de trabalho que aloque e libere memória e calcule o tempo necessário. Também existem funções do sistema operacional que podem informar a quantidade de memória que seu programa está usando, por exemplo, getrusage()no Linux. Tenha duas versões, uma usando seu alocador slab e outra usando regular malloc()/free(), new/deleteou qualquer outra forma de obter memória do sistema operacional e verificar a diferença no desempenho.
Existe alguma maneira de determinar de qual laje liberar um bloco, sem saber o tamanho? a abordagem atual é pedir a todas as lajes para liberar o bloco, aquele que possui esse bloco irá liberá-lo.
Uma maneira é ter um pequeno cabeçalho alocado antes da região de memória retornada por alloc()e armazenar alguns metadados nesse cabeçalho, como o ponteiro para o próprio objeto alocador de bloco. Outra opção é garantir que as lajes estejam sempre alinhadas naturalmente na memória, para que você possa obter rapidamente um ponteiro para o início da laje, independentemente de onde a alocação veio na laje.
Mas frequentemente, o chamador de custom_free()saberá realmente o tamanho do objeto que está liberando. Portanto, faz sentido adicionar um parâmetro de tamanho a custom_free(), para que ele possa fazer a mesma coisa que você faz custom_malloc()para encontrar o objeto de laje certo para se livrar.
Qual é a melhor maneira de lidar com grandes tamanhos de memória (maiores do que placas)
Então você volta para um normal malloc()ou new.
Como posso escrever alguns testes de unidade para isso? é difícil descobrir se o endereço retornado é válido ou não.
Uma possibilidade é apenas gravar na memória alocada no teste de unidade e, em seguida, compilar os testes de unidade com o AddressSanitizer ativado. Como alternativa, execute o teste de unidade dentro do Valgrind para capturar gravações em endereços inválidos.
Use uint64_tpara a matriz de bitmap
A menos que você esteja escrevendo especificamente este código para ser executado em um microcontrolador de 8 bits, sugiro que você use uint64_tpara a matriz de bitmap. A razão é que os computadores hoje em dia têm registradores de 64 bits, e as operações em 64 bits por vez são tão rápidas ou às vezes até mais rápidas do que em 8 bits por vez.
Use as instruções de hardware para encontrar o primeiro conjunto de bits em um bitmap
A maioria dos processadores tem instruções para encontrar o primeiro bit definido em um inteiro. Isso é perfeito para uso em Bitmap::find_used(). Em C ++ 20, você será capaz de usar std::countl_zero()e funções relacionadas para acessar essa funcionalidade, mas se você não pode usar C ++ 20 ainda, então você pode ter funções específicas da plataforma, como ffs()ou compiladores embutidos, como GCCs __builtin_clz()para fazer o mesmo.
Escreva construtores adequados para suas classes
Você não deve ter uma init()função em suas classes, mas um construtor adequado que executa a inicialização. Isso evita a possibilidade de você se esquecer acidentalmente de chamar o inicializador ou chamá-lo duas vezes.
Escreva um destruidor para class Slab
Você deve escrever um destruidor que limpe qualquer memória restante que esteja em uso por uma placa quando ela é destruída.