Platte malloc / freie Implementierung
Ich versuche, einen Speicherzuweiser zu implementieren, der von diesem Tutorial geleitet wird . Ich habe eine Mischung aus Next-Fit-Suche und Segregated-List-Suche verwendet.
Es gibt mehrere Platten unterschiedlicher Größe (eine Platte besteht aus ansteckenden Speicherblöcken derselben Größe plus einer Kopfzeile). Wenn einer Platte die freien Blöcke ausgehen, weist sie eine neue Platte derselben Größe zu und verknüpft sie mit der aktuellen Platte. Freie Blöcke werden mithilfe einer Bitmap in der Kopfzeile jeder Platte verfolgt.
Wie ist mein Design in Bezug auf Speicher und Geschwindigkeit?
Gibt es eine Möglichkeit zu bestimmen, von welcher Platte ein Block befreit werden soll, ohne die Größe zu kennen? Der derzeitige Ansatz besteht darin, alle Platten zu bitten, den Block freizugeben. Derjenige, dem dieser Block gehört, wird ihn freigeben.
Was ist der beste Weg, um mit großen Speichergrößen umzugehen (größer als Platten)?
Wie kann ich dazu einige Unit-Tests schreiben? Es ist schwer herauszufinden, ob die zurückgegebene Adresse gültig ist oder nicht.
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 (nicht wirklich wichtig)
#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);
}
Antworten
Antworten auf Ihre Fragen
Wie ist mein Design in Bezug auf Speicher und Geschwindigkeit?
Das ist ganz einfach: Messen Sie es! Erstellen Sie eine Arbeitslast, die Speicher zuweist und freigibt, und legen Sie fest, wie lange es dauert. Es gibt auch Betriebssystemfunktionen, mit denen Sie feststellen können, wie viel Speicher Ihr Programm verwendet, beispielsweise getrusage()unter Linux. Habe zwei Versionen, eine mit Ihrer Platte allocator, und eine andere mit regulärer malloc()/free(), new/deleteoder was auch immer Art und Weise haben Sie Speicher aus dem Betriebssystem zu bekommen, und prüfen Sie den Unterschied in der Leistung.
Gibt es eine Möglichkeit zu bestimmen, von welcher Platte ein Block befreit werden soll, ohne die Größe zu kennen? Der derzeitige Ansatz besteht darin, alle Platten zu bitten, den Block freizugeben. Derjenige, dem dieser Block gehört, wird ihn freigeben.
Eine Möglichkeit besteht darin, einen kleinen Header direkt vor dem von zurückgegebenen Speicherbereich zuzuweisen alloc()und einige Metadaten in diesem Header zu speichern, z. B. den Zeiger auf das Plattenzuweisungsobjekt selbst. Eine andere Möglichkeit besteht darin, sicherzustellen, dass die Platten im Speicher immer auf natürliche Weise ausgerichtet sind, sodass Sie schnell einen Zeiger auf den Beginn der Platte erhalten, unabhängig davon, woher die Zuordnung in der Platte stammt.
Aber oft custom_free()kennt der Aufrufer von tatsächlich die Größe des Objekts, das er freigibt. Es ist also sinnvoll, einen Größenparameter hinzuzufügen custom_free(), damit er das Gleiche tun kann custom_malloc(), um das richtige Plattenobjekt zu finden, von dem er befreit werden soll.
Was ist der beste Weg, um mit großen Speichergrößen umzugehen (größer als Platten)?
Dann fällt man einfach auf ein normales malloc()oder zurück new.
Wie kann ich dazu einige Unit-Tests schreiben? Es ist schwer herauszufinden, ob die zurückgegebene Adresse gültig ist oder nicht.
Eine Möglichkeit besteht darin, im Komponententest einfach in den zugewiesenen Speicher zu schreiben und dann die Komponententests mit aktiviertem AddressSanitizer zu kompilieren . Alternativ können Sie den Komponententest in Valgrind ausführen , um Schreibvorgänge an ungültige Adressen abzufangen .
Verwenden Sie uint64_tfür das Bitmap-Array
Sofern Sie diesen Code nicht speziell für die Ausführung auf einem 8-Bit-Mikrocontroller schreiben, empfehle ich die Verwendung uint64_tfür das Bitmap-Array. Der Grund dafür ist, dass Computer heutzutage 64-Bit-Register haben und Operationen mit jeweils 64-Bit genauso schnell oder manchmal sogar schneller sind als mit jeweils 8-Bit.
Verwenden Sie die Hardwareanweisungen, um das erste gesetzte Bit in einer Bitmap zu finden
Die meisten Prozessoren haben Anweisungen, um das erste gesetzte Bit in einer Ganzzahl zu finden. Dies ist perfekt für den Einsatz in Bitmap::find_used(). In C ++ 20, werden Sie in der Lage zu nutzen std::countl_zero()und die damit verbundenen Funktionen zuzugreifen , die Funktionalität, aber wenn Sie nicht C ++ 20 noch verwenden können, dann könnten Sie plattformspezifische Funktionen wie haben ffs()oder Compiler builtins wie GCC __builtin_clz()das zu tun gleich.
Schreiben Sie die richtigen Konstruktoren für Ihre Klassen
Sie sollten keine init()Funktion in Ihren Klassen haben, sondern einen geeigneten Konstruktor, der die Initialisierung durchführt. Dadurch wird vermieden, dass Sie versehentlich vergessen, den Initialisierer aufzurufen, oder ihn zweimal aufrufen.
Schreiben Sie einen Destruktor für class Slab
Sie sollten einen Destruktor schreiben, der den verbleibenden Speicher bereinigt, der von einer Platte verwendet wird, wenn diese zerstört wird.