Buddy memory allocation by bitmap

# はじめに
組み込みやゲームなど特殊な環境では, 独自のメモリ割り当てが必要になることがあります. ひとつの選択肢として, "Buddy memory allocation"を考えてみます.

良いメモリ割り当ての理想は次になります. 特殊環境で自前に実装する理由は, 3つ目を捨てて, その環境で1と2を追求するということです.

- 確保・解放が高速に動作する
- 内部・外部断片化が最小である
- 環境に応じて最適に動作する

記載するコードは一部を抜き出しています.

# Buddy system
オブジェクトの相方（buddy)を決めて, 処理の効率化を測るシステムになります. "Buddy memory allocation"では, メモリブロックを2分木で管理して, 兄弟の節を相方と考えます. 実装が2分木であるかではなく, 考え方が2分木です. メモリ割り当ての効率化とは, コンパクションの効率化になります.

![buddy00.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/f9391190-a15a-fcbd-d6c8-b9085aca0c46.jpeg)

前の図の例で, 8KB以下のメモリを2つ確保すると次のようになります. 

![buddy01.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/4bb9d193-d8af-62b2-a1df-490cd2fa9459.jpeg)

それから, 確保順に解放したとすると, 次のようになります. 相方が空きなら親を遡って空きにすることで, コンパクションを実現します.

![buddy02.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/27065/b01ee622-128f-a996-3536-a8444774813d.jpeg)

欠点は, 2分木ですので割り当てサイズの自由度が狭く, 内部断片化が大きくなることです.

# Bitmap表現による"Buddy system"の実装
N分木は配列で表現できるため, "Buddy system"も配列で表現可能です.
前項を見ると"Buddy system"を実現するために, "空き", "割り当て済", "一部割り当て済"の3値が必要になります. ここでは単純に, 一部割り当て済かを表す`fill`と, そのブロックが割り当て済かを表す`use`を使用します.

```cpp
template<class T=u64>
class BitTree
{
    typedef T value_type;

    value_type fill_;
    value_type use_;
};
```

## 割り当て
入力は割り当てたい木のレベルです. 64KBのブロックから32KBが欲しいなら, レベル1を要求してください. 出力は, 割り当ての成否と木の配列インデックスです. APIの設計の話ですので, お好きにしていただきたいです.
未使用の節の子供を探索して, 該当のレベルの節が空なら割り当て成功です. 割り当てに成功した場合, 親を遡って一部割り当て済（fill）のフラグをセットします.
余談ですが, スタックが8固定なのは64bitのbitmapまでしか考えていないからです.

```cpp
template<class T>
bool BitTree<T>::set(u8& index, u32 level)
{
    assert(level <= MaxLevel);
    Node stack[8];
    u8 top = 1;
    stack[top] = {0, 0};
    while(0 < top) {
        Node node = stack[top];
        --top;
        value_type flag = One << node.index_;
        if(level <= node.level_) {
            bool empty = 0 == (fill_ & flag);
            if(empty) {
                use_ |= flag;
                fill_ |= flag;
                backtrackSet(node.index_);
                index = node.index_;
                return true;
            }
        } else if(0 == (use_ & flag)){
            assert(node.level_<=MaxLevel);
            u8 nextLevel = node.level_ + 1;
            u8 child0 = (node.index_ << 1) + 1;
            u8 child1 = child0 + 1;
            ++top;
            stack[top] = {child1, nextLevel};
            ++top;
            stack[top] = {child0, nextLevel};
        }
    }
    return false;
}
```

親を遡って一部割り当て済のフラグをセットします.

```cpp
template<class T>
void BitTree<T>::backtrackSet(u8 index)
{
    while(0 < index) {
        index = (index-1) >> 1;
        fill_ |= (One << index);
    }
}
```

# 解放
入力は, 木の配列インデックスです, 管理は外側に任せる方針です.

```cpp
template<class T>
void BitTree<T>::reset(u8 index)
{
    assert(0 != (use_ & (One << index)));
    assert(0 != (fill_ & (One << index)));

    value_type flag = ~(One << index);
    use_ &= flag;
    fill_ &= flag;
    backtrackReset(index);
}
```

親に遡りながら相方が空きなら, その親を空きにセットします. コンパクションがこのように単純なことが, このシステムの利点です.

```cpp
template<class T>
void BitTree<T>::backtrackReset(u8 index)
{
    while(0 < index) {
        u8 sibling = 0 == (index & 0x01U) ? index - 1 : index + 1;
        value_type flag = One << sibling;
        if(0 != (fill_ & flag)) {
            return;
        }
        index = (index - 1) >> 1;
        fill_ &= ~(One << index);
    }
}
```

# テスト

```cpp
BitTree<> bitTree;
u8 index[3];

bitTree.set(index[1], BitTree<>::MaxLevel);
bitTree.set(index[0], 3);
bitTree.print();

bitTree.set(index[2], BitTree<>::MaxLevel);
bitTree.print();

bitTree.reset(index[0]);
bitTree.print();

bitTree.reset(index[1]);
bitTree.print();

bitTree.reset(index[2]);
bitTree.print();
```

結果は次のようになります, 'f'は一部割り当て済, 'u'は割り当て済, '-'は空きになります. 正しい（おそらく）.

```
f
f-
f---
fu------
f---------------
u-------------------------------

f
f-
f---
fu------
f---------------
uu------------------------------

f
f-
f---
f-------
f---------------
uu------------------------------

f
f-
f---
f-------
f---------------
-u------------------------------

-
--
----
--------
----------------
--------------------------------
```

#まとめ
何に使うの？というのは後日書くかもしれません.