slab malloc / implementación libre
Estoy tratando de implementar un asignador de memoria guiado por este tutorial . Usé una combinación de búsqueda Next-fit y búsqueda de lista segregada.
Existen múltiples losas de diferentes tamaños (una losa son bloques contagiosos de memoria del mismo tamaño, más un encabezado). Si una losa se queda sin bloques libres, asigna una nueva losa del mismo tamaño y la vincula a la losa actual. los bloques libres se rastrean utilizando un mapa de bits en el encabezado de cada losa.
¿Cómo es mi diseño en términos de memoria y velocidad?
¿Hay alguna forma de determinar de qué losa liberar un bloque, sin conocer el tamaño? el planteamiento actual es pedir a todas las losas que liberen el bloque, el dueño de ese bloque lo liberará.
¿Cuál es la mejor manera de lidiar con grandes tamaños de memoria (más grandes que los de losas)?
¿Cómo puedo escribir algunas pruebas unitarias para esto? es difícil saber si la dirección devuelta es válida o no.
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 (no es realmente 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);
}
Respuestas
Respuestas a tus preguntas
¿Cómo es mi diseño en términos de memoria y velocidad?
Eso es fácil: ¡mídelo! Cree una carga de trabajo que asigne y libere memoria, y calcule cuánto tiempo lleva. También hay funciones del sistema operativo que pueden indicarle cuánta memoria está usando su programa, por ejemplo, getrusage()en Linux. Tenga dos versiones, una que use su asignador de bloques y otra que use regular malloc()/free(), new/deleteo cualquier forma que tenga para obtener memoria del sistema operativo, y verifique la diferencia en el rendimiento.
¿Hay alguna forma de determinar de qué losa liberar un bloque, sin conocer el tamaño? el planteamiento actual es pedir a todas las losas que liberen el bloque, el dueño de ese bloque lo liberará.
Una forma es tener un pequeño encabezado asignado justo antes de la región de memoria devuelta por alloc()y almacenar algunos metadatos en ese encabezado, como el puntero al objeto asignador de losa en sí. Otra opción es asegurarse de que las losas siempre estén alineadas de forma natural en la memoria, de modo que pueda obtener rápidamente un puntero al inicio de la losa, independientemente de dónde provenga la asignación en la losa.
Pero a menudo, la persona que llama custom_free()sabrá realmente el tamaño del objeto que está liberando. Por lo tanto, tiene sentido agregar un parámetro de tamaño a custom_free(), para que pueda hacer lo mismo que usted custom_malloc()para encontrar el objeto de losa correcto para liberarse.
¿Cuál es la mejor manera de lidiar con grandes tamaños de memoria (más grandes que los de losas)?
Entonces simplemente vuelves a un estándar malloc()o new.
¿Cómo puedo escribir algunas pruebas unitarias para esto? es difícil saber si la dirección devuelta es válida o no.
Una posibilidad es simplemente escribir en la memoria asignada en la prueba unitaria y luego compilar las pruebas unitarias con AddressSanitizer habilitado. Alternativamente, ejecute la prueba unitaria dentro de Valgrind para detectar escrituras en direcciones no válidas.
Usar uint64_tpara la matriz de mapa de bits
A menos que esté escribiendo específicamente este código para ejecutarlo en un microcontrolador de 8 bits, le sugiero que lo use uint64_tpara la matriz de mapa de bits. La razón es que las computadoras hoy en día tienen registros de 64 bits, y las operaciones en 64 bits a la vez son tan rápidas o incluso a veces más rápidas que en 8 bits a la vez.
Utilice las instrucciones de hardware para encontrar el primer bit establecido en un mapa de bits
La mayoría de los procesadores tienen instrucciones para encontrar el primer bit establecido en un entero. Esto es perfecto para usar en Bitmap::find_used(). En C ++ 20, podrá usar std::countl_zero()y las funciones relacionadas para acceder a esa funcionalidad, pero si aún no puede usar C ++ 20, entonces puede tener funciones específicas de la plataforma, tales como ffs()compiladores integrados como GCC __builtin_clz()para hacer el mismo.
Escribe constructores adecuados para tus clases.
No debería tener una init()función en sus clases, sino un constructor adecuado que realice la inicialización. Eso evita la posibilidad de que accidentalmente olvide llamar al inicializador o lo llame dos veces.
Escribe un destructor para class Slab
Debe escribir un destructor que limpie cualquier memoria restante que esté en uso por una losa cuando se destruye.