自分自身のメモリ割り当て器を作成する

この記事では、自分自身のメモリアロケータを実装する方法を紹介します。このメモリアロケータは 非常にシンプル で、オペレーティングシステム内部のメモリ割り当てプロセスについてより深く理解するのに役立ちます。そのため、効率的ではありません。簡単に言えば、このメモリアロケータは ただ動作する (Just works) だけです。

主に C 言語を使用してプログラミングを行います。しかし、プログラミングの前に、私たちのオペレーティングシステムのメモリストレージ方法について一定の理解が必要です。

オペレーティングシステムのメモリストレージ#

私たちのオペレーティングシステムのメモリには、主に 5 つの部分があります。これらの 5 つの部分はそれぞれ次の通りです：

Different partitions in the RAM

kernel: オペレーティングシステムのカーネルを格納します。
stack: プログラムの変数を格納します。
heap: プログラムが動的に要求したメモリを格納します。
data: 静的変数を格納します。
text: プログラムのコードセクションを格納します。

その中で、相対的に動的な heap と stack のサイズは固定されていません。heap は上方向（高いメモリアドレス）に成長し、stack は下方向（低いメモリアドレス）に成長します。したがって、C で malloc などのコマンドを使用すると、実際には heap 領域が少し上に成長することになります。図からもわかるように、heap の上部には brk ポインタがあり、このポインタは heap の領域範囲を制限しています。したがって、新しいメモリを malloc する際には、brk ポインタを上に移動させることになります。brk を移動させるプロセスは、Unix/Linux システムでは sbrk という専用の関数があります。この関数には 3 つの使い方があります：

sbrk(0) は現在の brk アドレスを返します。
sbrk(n) は brk を n バイト上に拡張します。ここで n は正の数です。
sbrk(-n) は brk を n バイト下に拡張します。ここで n は正の数です。

sbrk() が成功すると、割り当てられた領域の開始アドレスを返します。もし sbrk() のメモリ割り当てが失敗した場合、(void *) -1 （つまり 0xFFFFFFFF）を返します。

sbrk() は実際には現代のオペレーティングシステムでは廃止されていますが、より良いメモリ割り当て方法（例えば mmap()）があるためです。しかし、sbrk() はシンプルで直感的であるため、ここではメモリ割り当てのために sbrk() を使用します。

`malloc(size_t size)` の実装#

malloc(size_t size) は、割り当てるメモリのサイズを表す引数を受け取ります。私たちは直感的に sbrk(size) を直接呼び出せばいいのではないかと思うかもしれません。

確かに、直接呼び出すことで新しいメモリを割り当てることができますが、このメモリを使用した後に free() で解放しようとすると問題が発生します。なぜなら、解放する必要があるメモリのサイズがわからないため、解放することができないからです。

さらに、brk ポインタは常に heap の上部を指しており、私たちは brk の位置を調整することでメモリをオペレーティングシステムに返します。したがって、実際には 本当に解放する （オペレーティングシステムに返す）ことができるのは heap の上部にあるメモリ割り当てのみであり、中間のメモリは本当に解放することが難しいのです（全体を移動することはできますが、そうすると消費が大きくなります）。中間のメモリを本当に解放することはできませんが、それらを効果的に利用することができます。つまり、解放されたメモリをマークして、そのメモリを別のプログラムに「割り当てる」ことができるようにします。したがって、malloc の際には、実際にはすべての割り当てられたメモリをループして、解放されているかどうか、サイズが要求を満たすかどうかを確認するプロセスが含まれます。

最後に、sbrk() コマンドは私たちだけが呼び出せるものではなく、どのプログラムでも呼び出すことができます。言い換えれば、私たちが割り当てたメモリが物理アドレス上で連続していることを保証することはできません。 これにより、前述の「ループ」プロセスを実行できなくなります。したがって、私たちは リンクリスト の方法を使用して、割り当てた各メモリをリンクさせる必要があります。

したがって、malloc の際には、この割り当てに関するいくつかの必要な情報を一緒に書き込む必要があります。正確には、割り当てられたメモリの前に書き込むことになります。これらの必要な情報には、割り当てられたメモリのサイズ、解放されているかどうか、および 次のメモリ割り当てのアドレス が含まれます。

struct header_t {
    size_t size;
    unsigned is_free;   /* shorthand for unsigned int */
    union header *next; /* linked list for our heap */
}

次に、処理を簡単にするために、すべての割り当てられたメモリのヘッダー情報のサイズが同じであることを望みます。したがって、すべてのヘッダー情報のサイズを 16 ビットに揃える必要があります。

typedef char ALIGH[16]; /* ALIGH is 16 bits */

union header {
    struct {
        size_t size;
        unsigned is_free;   /* shorthand for unsigned int */
        union header *next; /* linked list for our heap */
    } s;
    ALIGH stub;
};

typedef union header header_t;  /* so header_t will have a fixed 16 bytes size */

ループリンクリストと解放を容易にするために、リストのヘッドとテイルを指す 2 つのポインタも必要です。

/* a head and tail pointer to track our heap */
header_t *head, *tail;

最後に、競合を避けるために ミューテックス を導入する必要があります。

/* set a mutex lock to prevent concurrently accessing memory */
pthread_mutex_t global_malloc_lock;

これで、私たちはついに malloc() 関数を完成させることができます。

header_t *get_free_block(size_t size);

/* sbrk(0) => return the current address of program break
 * sbrk(x) => increase brk by x bytes
 * sbrk(-x) => decrease brk by x bytes
 * if sbrk() fails, it will return (void *) -1 / 0xFFFFFFFF
 * */
void *malloc(size_t size) {
    if (!size)  /* if the requested size is zero, return */
        return NULL;
    size_t total_size;  /* header size + block size */
    void *block;
    header_t *header;

    pthread_mutex_lock(&global_malloc_lock);    /* acquire the lock */
    header = get_free_block(size);  /* check if there have available free block that has a size of bigger than ‘size’ */
    if (header) {   /* exists */
        header -> s.is_free = 0;    /* this block is not free */
        pthread_mutex_unlock(&global_malloc_lock);  /* release the lock */
        return (void *)(header + 1);    /* return the address of the block instead of the header */
    }

    total_size = sizeof(header_t) + size;   /* not exists, we have to create one */
    block = sbrk(total_size);
    if (block == (void *) -1) { /* malloc failed */
        pthread_mutex_unlock(&global_malloc_lock);  /* release the lock */
        return NULL;
    }

    header = block;
    header -> s.size = size;
    header -> s.is_free = 0;
    header -> s.next = NULL;

    if (!head)  /* if the head pointer of the heap not exists, make header be the head */
        head = header;
    if (tail)   /* if the tail pointer of the heap exists, */
        tail -> s.next = header;
    tail = header; /* make this header be the tail (or the new tail) */
    pthread_mutex_unlock(&global_malloc_lock);  /* release the lock */
    return (void *)(header + 1);    /* return the address of the block instead of the header */
}

header_t *get_free_block(size_t size) {
    header_t *curr = head;
    while (curr) {
        if (curr -> s.is_free == 1 && curr -> s.size >= size)
            return curr;
        curr = curr -> s.next;
    }
    return NULL;
}

malloc() のフローは次の通りです：まず、引数 size が合法かどうかを検証します。合法であれば、ミューテックスを取得しようとします。ロックを取得できたら🔒、get_free_block() を通じてメモリ割り当てリンクリストの中から解放された十分なサイズのメモリブロックを探します。見つかった場合、そのブロックを未解放としてマークし、ミューテックスを解放してこのメモリのアドレスを返します。ここで注意すべきは、(void *)(header + 1) の意味は割り当てられた メモリブロック のアドレスを返すことであり、header はヘッダー情報のアドレスで、ヘッダー情報は 16 ビットを占めます。一方、割り当てられたメモリの中に適切なメモリブロックが見つからなかった場合、sbrk を使用して新しいメモリブロックを割り当てる必要があります。ここで割り当てるサイズは、ヘッダー情報のサイズとメモリブロックのサイズの合計です。割り当てが成功すれば、それをリンクリストに追加し、メモリブロックのアドレスを返します。

`free(void *block)` の実装#

free(void *block) はメモリブロックのアドレスを受け取り、それを解放します。解放の戦略は次の通りです：もしこのメモリがちょうどリンクリストの末尾、つまり brk にある場合、sbrk() を呼び出してこのメモリをオペレーティングシステムに返すことができます。もしこのメモリがリンクリストの中間にある場合、単純に「解放」とマークします。

/* if the block-to-be-freed is at the end of the heap, then we return it to the OS.
 * otherwise we simply mark it as ‘free’
 * */
void free(void *block){
    header_t *header, *tmp;
    void *programbreak;

    if (!block) /* if this block not exists */
        return;

    pthread_mutex_lock(&global_malloc_lock);
    header = (header_t *)block - 1; /* header address */

    programbreak = sbrk(0); /* get current brk location */

    if ((char *)block + header -> s.size == programbreak) { /* this is the end of the heap */
        if (head == tail) { /* currently there is only one block in the heap, we will erase it */
            head = tail = NULL;
        } else {    /* otherwise we will remove the tail */
            tmp = head;
            while (tmp) {
                if (tmp -> s.next == tail) {
                    tmp -> s.next = NULL;
                    tail = tmp;
                }
                tmp = tmp -> s.next;
            }
        }
        /* release the space */
        sbrk(0 - sizeof(header_t) - header -> s.size);
        pthread_mutex_unlock(&global_malloc_lock);
        return;
    }

    /* if this block is in the middle of our heap, we mark it as ‘free’ */
    header -> s.is_free = 1;
    pthread_mutex_unlock(&global_malloc_lock);
}

このコードでは、(header_t *)block - 1 の意味はメモリブロックのアドレスを header * にマッピングし、-1 でヘッダー情報のアドレスを取得することです。 (char *)block はメモリブロックの初期アドレスで、初期アドレスにメモリブロックのサイズを加えたものが終了アドレスです。終了アドレスが brk に指されている場合、このメモリはオペレーティングシステムに返すことができます。解放時には、リンクリストも更新することに注意してください。

これで、メモリ割り当てのコアとなる 2 つの関数が実装されました。次に、非常に便利な 2 つの関数、calloc と realloc を実装します。

`calloc(size_t num, size_t nsize)` の実装#

calloc(size_t num, size_t nsize) は、数量パラメータ num とサイズパラメータ nsize を受け取り、num 個の nsize サイズのメモリブロックを割り当て、すべての割り当てられたメモリを 0 に設定し、初期アドレスを返します。

/* calloc allocates ‘num’ elements with size of ‘nsize’.
 * */
void *calloc(size_t num, size_t nsize) {
    if (!num || !nsize)
        return NULL;    /* num and nsize must be valid */

    size_t size;
    void *block;
    size = num * nsize;
    if (nsize != size / num)
        return NULL;    /* multiply overflow */
    block = malloc(size);
    if (!block)
        return NULL;    /* malloc failed */
    memset(block, 0, size); /* reset all value in this block */
    return block;
}

中間に溢れを判断するプロセスがあることに注意が必要です。他の部分には問題はないはずです。

`realloc(void *block, size_t size)` の実装#

realloc(void *block, size_t size) は、メモリブロックのサイズを再割り当てします。実際には、再割り当てのサイズが 元のメモリブロックのサイズ以下 であれば、関数は元のメモリブロックのアドレスをそのまま返します。再割り当てのサイズが 元のメモリブロックのサイズより大きい 場合、malloc を呼び出して新しいメモリブロックを割り当て、元のメモリブロックの内容をコピーして新しいメモリブロックのアドレスを返します。

/* change the given block’s size
 * */
void *realloc(void *block, size_t size){
    if (!block || !size)    /* block and size must be valid */
        return NULL;

    header_t *header;
    void *ret;
    header = (header_t *)block - 1;
    if (header -> s.size >= size)   /* if the original block already has enough space for the data */
        return block;
    ret = malloc(size); /* allocate a new space */
    if (ret) {
        memcpy(ret, block, header -> s.size);   /* move data in block to ret */
        free(block);    /* free original block */
    }
    return ret;
}