Buddy memory allocationの実装
30年ほど前こいつを8086アセンブラで書きました。C/C++で実装されたものがないか探してみたらばGitHubに見つけましたよ。ここにあったC実装、C99でサポートされたinlineを使っているためコンパイルエラーとなる処理系もありますが、inlineを潰してしまうかC++としてコンパイルすれば無問題です。C++用にほんの少し修正を加えたもの（buddy.h, buddy.cpp）をサンプルに同梱しておきました。
インターフェースを軽く説明しておきます：
struct buddy* buddy_new(int lebel)
buddyを生成します。引数levelはbuddyが管理するblockの初期orderで、例えば buddy_new(10) で2^10=1024個のblockを管理します。
void buddy_delete(struct buddy*)
buddyの廃棄。生成時に作業領域をmallocしているので、用が済んだらbuddy_deleteをお忘れなく。
int buddy_alloc(struct buddy*. int size)
少なくともsize個の連続blockを確保し、確保された連続blockの先頭block番号を（0起点で）返します。確保できなかったら-1です。
int buddy_free(struct buddy*. int offset)
buddy_allocで確保されたblockを解放します。
int buddy_size(struct buddy*, int offset)
buddy_allocで確保された実際のblock数を返します。
buddy_dump(struct buddy*)
blockの使用状況をstdoutに出力します。block番号bとその大きさsが、未使用なら(b:s)確保済なら[b:s]と表現されます。
前述のダンドリ説明（1～9）を実装／実行したのがコチラ：
#include <stdio.h>
#include "buddy.h"
int test_alloc(struct buddy* b, int sz) {
int r = buddy_alloc(b, sz);
printf("alloc %d (sz= %d)\n",r,sz);
buddy_dump(b);
return r;
}
void test_free(struct buddy* b, int addr) {
printf("free %d\n",addr);
buddy_free(b, addr);
buddy_dump(b);
}
int main() {
struct buddy* b = buddy_new(4);
printf("--- 1. initial ----------------:\n");
buddy_dump(b);
printf("--- 2. A allocates 1 block ----: ");
int mA = test_alloc(b, 1);
printf("--- 3. B allocates 2 blocks ---: ");
int mB = test_alloc(b, 2);
printf("--- 4. C allocates 1 block ----: ");
int mC = test_alloc(b, 1);
printf("--- 5. D allocates 2 blocks ---: ");
int mD = test_alloc(b, 2);
printf("--- 6. B frees ----------------: ");
test_free(b,mB);
printf("--- 7. D frees ----------------: ");
test_free(b,mD);
printf("--- 8. A frees ----------------: ");
test_free(b,mA);
printf("--- 9. C frees ----------------: ");
test_free(b,mC);
printf("\n");
buddy_delete(b);
}
……ちょい待ち、このコード、メモリの確保も解放もやってないやん？ そのとおり、buddyそれ自体は連続する2^L個のblockそれぞれの使用／未使用状態を管理するだけなんです。
これは実用にはならんので、確保時にはポインタを返し解放時にはポインタを渡すよう、簡単なwrapper：buddy_poolを用意しました。
#ifndef BUDDY_POOL_H_
#define BUDDY_POOL_H_
#include "buddy.h"
#include <mutex>
#include <cstdint>
#include <cstddef>
class buddy_pool {
private:
std::mutex mutex_; // mutex
buddy* buddy_; // Buddy
std::uint8_t* buffer_; // memory pool
std::size_t block_; // bytes per block
public:
buddy_pool(int level, std::size_t block, void* pool)
: buffer_(static_cast<uint8_t*>(pool)), block_(block) {
buddy_ = buddy_new(level);
}
~buddy_pool() {
buddy_delete(buddy_);
}
void* allocate(std::size_t n) {
std::lock_guard<std::mutex> guard(mutex_);
int nblock = static_cast<int>((n + block_ -1U)/block_);
int offset = buddy_alloc(buddy_, nblock);
return offset < 0 ? nullptr : buffer_ + offset * block_;
}
void deallocate(void* ptr) {
std::lock_guard<std::mutex> guard(mutex_);
int offset = static_cast<int>((static_cast<uint8_t*>(ptr) - buffer_)/block_);
buddy_free(buddy_, offset);
}
void dump(void (*func)(const char*)) const {
buddy_dump_f(buddy_, func);
}
void dump() const {
buddy_dump(buddy_);
}
static std::size_t required(int level, std::size_t block) {
return block << level;
}
static buddy_pool* make(int level, std::size_t block, void* pool) {
return new buddy_pool(level, block, pool);
}
};
#endif
buddy_poolのコンストラクタにはlevel、blockあたりのbyte数、そしてあらかじめ確保された（少なくともblock*(2^level)byteの大きさを持つ）領域を与えます。buddy_poolはこの領域を小分けにして確保します。使い方はmalloc／freeとおんなじですね。
#include "buddy_pool.h"
#include <cstring>
#include <cstdio>
int main() {
char buffer[1024];
buddy_pool pool(4, 8, buffer);
char* hello = (char*)pool.allocate(6);
char* world = (char*)pool.allocate(6);
pool.dump();
strcpy(hello, "Hello");
strcpy(world, "world");
printf("%s, %s\n", hello, world);
pool.deallocate(hello);
pool.deallocate(world);
}
おまけにもうひとひねり、std::vectorやstd::listなど標準C++コンテナへのメモリ供給源としてbuddy_poolを利用するallocator：buddy_allocatorを実装します。
#ifndef BUDDY_POOL_H_
#define BUDDY_POOL_H_
#include "buddy.h"
#include <mutex>
#include <cstdint>
#include <cstddef>
class buddy_pool {
private:
std::mutex mutex_; // mutex
buddy* buddy_; // Buddy
std::uint8_t* buffer_; // memory pool
std::size_t block_; // bytes per block
public:
buddy_pool(int level, std::size_t block, void* pool)
: buffer_(static_cast<uint8_t*>(pool)), block_(block) {
buddy_ = buddy_new(level);
}
~buddy_pool() {
buddy_delete(buddy_);
}
void* allocate(std::size_t n) {
std::lock_guard<std::mutex> guard(mutex_);
int nblock = static_cast<int>((n + block_ -1U)/block_);
int offset = buddy_alloc(buddy_, nblock);
return offset < 0 ? nullptr : buffer_ + offset * block_;
}
void deallocate(void* ptr) {
std::lock_guard<std::mutex> guard(mutex_);
int offset = static_cast<int>((static_cast<uint8_t*>(ptr) - buffer_)/block_);
buddy_free(buddy_, offset);
}
void dump(void (*func)(const char*)) const {
buddy_dump_f(buddy_, func);
}
void dump() const {
buddy_dump(buddy_);
}
static std::size_t required(int level, std::size_t block) {
return block << level;
}
static buddy_pool* make(int level, std::size_t block, void* pool) {
return new buddy_pool(level, block, pool);
}
};
#endif
おためしはコチラ。
#include "buddy_allocator.h"
#include <cstdio>
#include <vector>
#include <list>
int main() {
const size_t block = sizeof(int);
const int level = 8;
char buffer[block << level];
buddy_pool pool(level, block, &buffer);
buddy_allocator<int> alloc(&pool);
{
std::vector<int,buddy_allocator<int>> v(alloc);
std::list<int,buddy_allocator<int>> l(alloc);
for ( int i = 0; i < 10; ++i ) {
v.push_back(i);
l.push_back(i);
pool.dump();
printf("\n");
}
for ( int i = 0; i < 5; ++i ) {
l.pop_front();
pool.dump();
printf("\n");
}
printf("\n vector : ");
for ( int item : v ) printf("%3d", item);
printf("\n list : ");
for ( int item : l ) printf("%3d", item);
}
printf("\n");
pool.dump();
}
30年前の黄ばんだノートから、Buddy memory allocationのご紹介でした。IoTが賑やかになってきたので、芸の肥やしにと遅まきながらRaspberry Piを手に入れたんですよ。組み込み向けの小さなボードでメモリを高速にやりくりするのに使えるんじゃないかと、古ぼけたコードを引っ張り出してホコリを払ってみた次第です。
