slab malloc / การใช้งานฟรี
ฉันกำลังพยายามฝังตัวจัดสรรหน่วยความจำที่แนะนำโดยบทช่วยสอนนี้ ฉันใช้การค้นหาแบบ Next-fit และการค้นหารายการที่แยกจากกัน
มีแผ่นพื้นหลายขนาดที่แตกต่างกัน (แผ่นพื้นเป็นบล็อกหน่วยความจำที่มีขนาดเท่ากันรวมทั้งส่วนหัว) หากแผ่นพื้นหมดบล็อกว่างจะจัดสรรแผ่นพื้นใหม่ที่มีขนาดเท่ากันและเชื่อมโยงกับแผ่นพื้นปัจจุบัน บล็อกฟรีจะถูกติดตามโดยใช้บิตแมปในส่วนหัวของแต่ละแผ่น
การออกแบบของฉันเป็นอย่างไรในแง่ของหน่วยความจำและความเร็ว?
มีวิธีใดในการพิจารณาว่าแผ่นพื้นใดที่จะทำให้บล็อกว่างโดยไม่ทราบขนาดได้หรือไม่? แนวทางปัจจุบันคือขอให้แผ่นคอนกรีตทั้งหมดเป็นอิสระผู้ที่เป็นเจ้าของบล็อกนั้นจะเป็นอิสระ
อะไรคือวิธีที่ดีที่สุดในการจัดการกับหน่วยความจำขนาดใหญ่ (ใหญ่กว่าแผ่นพื้น)
ฉันจะเขียนแบบทดสอบหน่วยการเรียนรู้นี้ได้อย่างไร ยากที่จะทราบว่าที่อยู่ที่ส่งกลับถูกต้องหรือไม่
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 (ไม่สำคัญจริงๆ)
#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);
}
คำตอบ
คำตอบสำหรับคำถามของคุณ
การออกแบบของฉันเป็นอย่างไรในแง่ของหน่วยความจำและความเร็ว?
ง่ายมาก: วัดได้! สร้างภาระงานบางส่วนที่จัดสรรและปลดปล่อยหน่วยความจำและระยะเวลาที่ใช้ นอกจากนี้ยังมีฟังก์ชั่นระบบปฏิบัติการที่สามารถบอกคุณได้ว่าโปรแกรมของคุณใช้หน่วยความจำเท่าใดตัวอย่างเช่นgetrusage()บน Linux มีสองรุ่นหนึ่งโดยใช้แผ่นจัดสรรของคุณและอื่นโดยใช้ปกติmalloc()/free(), new/deleteหรืออะไรก็ตามที่คุณจะต้องได้รับหน่วยความจำจากระบบปฏิบัติการและตรวจสอบความแตกต่างในการทำงาน
มีวิธีใดในการพิจารณาว่าแผ่นพื้นใดที่จะทำให้บล็อกว่างโดยไม่ทราบขนาดได้หรือไม่? แนวทางปัจจุบันคือขอให้แผ่นคอนกรีตทั้งหมดเป็นอิสระผู้ที่เป็นเจ้าของบล็อกนั้นจะเป็นอิสระ
วิธีหนึ่งคือการจัดสรรส่วนหัวเล็กน้อยก่อนที่พื้นที่หน่วยความจำจะส่งคืนalloc()และจัดเก็บข้อมูลเมตาบางส่วนในส่วนหัวนั้นเช่นตัวชี้ไปยังวัตถุตัวจัดสรรพื้น อีกทางเลือกหนึ่งคือตรวจสอบให้แน่ใจว่าแผ่นคอนกรีตอยู่ในแนวเดียวกันในหน่วยความจำเสมอดังนั้นคุณจึงสามารถนำตัวชี้ไปที่จุดเริ่มต้นของแผ่นพื้นได้อย่างรวดเร็วไม่ว่าการจัดสรรจะมาจากที่ใดในแผ่นพื้นก็ตาม
แต่บ่อยครั้งผู้เรียกcustom_free()จะรู้ขนาดของวัตถุที่กำลังหลุดพ้น ดังนั้นจึงเป็นเรื่องที่สมเหตุสมผลที่จะเพิ่มพารามิเตอร์ขนาดเข้าไปcustom_free()ดังนั้นจึงสามารถทำสิ่งเดียวกันกับที่คุณทำcustom_malloc()เพื่อค้นหาวัตถุแผ่นพื้นที่เหมาะสมที่จะว่างได้
อะไรคือวิธีที่ดีที่สุดในการจัดการกับหน่วยความจำขนาดใหญ่ (ใหญ่กว่าแผ่นพื้น)
แล้วคุณก็ถอยกลับไปเป็นประจำหรือmalloc()new
ฉันจะเขียนแบบทดสอบหน่วยการเรียนรู้นี้ได้อย่างไร ยากที่จะทราบว่าที่อยู่ที่ส่งกลับถูกต้องหรือไม่
ความเป็นไปได้อย่างหนึ่งคือเพียงแค่เขียนไปยังหน่วยความจำที่จัดสรรในการทดสอบหน่วยจากนั้นรวบรวมการทดสอบหน่วยโดยเปิดใช้งานAddressSanitizer หรือเรียกใช้การทดสอบหน่วยภายในValgrindเพื่อจับการเขียนไปยังที่อยู่ที่ไม่ถูกต้อง
ใช้uint64_tสำหรับอาร์เรย์บิตแมป
เว้นแต่คุณจะเขียนโค้ดนี้โดยเฉพาะเพื่อรันบนไมโครคอนโทรลเลอร์ 8 บิตฉันขอแนะนำให้คุณใช้uint64_tสำหรับอาร์เรย์บิตแมป เหตุผลก็คือคอมพิวเตอร์ในปัจจุบันมีการลงทะเบียน 64 บิตและการทำงานบน 64 บิตในแต่ละครั้งนั้นเร็วหรือเร็วกว่า 8 บิตในบางครั้ง
ใช้คำแนะนำฮาร์ดแวร์เพื่อค้นหาบิตชุดแรกในบิตแมป
โปรเซสเซอร์ส่วนใหญ่มีคำสั่งในการค้นหาบิตชุดแรกเป็นจำนวนเต็ม เหมาะสำหรับใช้ในBitmap::find_used(). ใน C ++ 20 คุณจะสามารถใช้std::countl_zero()และฟังก์ชันที่เกี่ยวข้องเพื่อเข้าถึงฟังก์ชันนั้นได้ แต่ถ้าคุณยังไม่สามารถใช้ C ++ 20 ได้คุณอาจมีฟังก์ชันเฉพาะแพลตฟอร์มเช่นffs()หรือคอมไพเลอร์ในตัวเช่น GCC __builtin_clz()เพื่อทำ เหมือนกัน.
เขียนตัวสร้างที่เหมาะสมสำหรับชั้นเรียนของคุณ
คุณไม่ควรมีinit()ฟังก์ชันในคลาสของคุณ แต่เป็นตัวสร้างที่เหมาะสมที่ดำเนินการเริ่มต้น เพื่อหลีกเลี่ยงความเป็นไปได้ที่คุณจะลืมโทรไปที่ initializer โดยไม่ได้ตั้งใจหรือเรียกซ้ำสองครั้ง
เขียนตัวทำลายสำหรับ class Slab
คุณควรเขียนตัวทำลายล้างหน่วยความจำที่เหลืออยู่ที่แผ่นพื้นใช้เมื่อมันถูกทำลาย