学んだ C 言語の学生は必ずmalloc、calloc、realloc、freeを使ったことがあるでしょう。自分でメモリを管理することを学ぶことで、プログラムの性能を向上させることができます。しかし、その内部原理を理解せずにそれらを使用すると、メモリオーバーフローやダングリングポインタなどの問題を引き起こす可能性があります。
この記事を通じて、メモリや仮想メモリなどの概念を理解し、自分でメモリ管理器（Memory Allocator）を手書きすることができます。
メモリ（RAM）とハードディスク（DRIVER）#
一部の人々はメモリとハードディスクの概念を混同します。通常、メモリはプログラムのバイナリ命令や関連する変数を保存するためのハードウェアであり、ハードディスクは大量のデータを保存するためのハードウェアです。
実際には、メモリとハードディスクには本質的な違いはなく、どちらもコンピュータストレージ(memory) であり、一定のデータを保存するために使用されます。メモリのアクセス速度は速いですが、単位コストが高いため、プログラムのコンテキストを保存するなど、頻繁に読み書きが必要な場所で使用されます。ハードディスクは、メモリに比べて読み書き速度が遅いですが、容量が大きく、頻繁に読み書きする必要のないファイルの長期保存に適しています。
メモリはハードディスクのキャッシュとして見ることができ、データを取得する必要があるとき、ハードディスクのデータを一時的にメモリにコピーすることができます。コンピュータがこれらのデータを必要とするとき、非常に速い読み書き速度のメモリから直接取得できます。
このようなキャッシュメカニズムはコンピュータ内で至る所に見られ、CPU の中には ALU（算術論理ユニット）以外にも、register（レジスタ）と呼ばれる重要な部分があります。レジスタも一種のコンピュータストレージであり、メモリのキャッシュと見なすことができます。この言い方は実際には少し片面であり、CPU にはキャッシュの階層構造と呼ばれるメカニズムもあり、ここでは詳しく述べません。興味のある読者は自分で調べてみてください。
仮想メモリ#
仮想メモリは、コンピュータシステム（OS）がメモリの一部を抽象化したものです。アプリケーションプログラムの視点から見ると、自分がコンピュータの全メモリ（連続したアドレス空間）を占有しているように見えます。しかし実際には、このメモリはコンピュータシステムがアプリケーションプログラムに提供するメモリの断片です。それは物理メモリの一部だけでなく、ハードディスクのスペースも含む可能性があります。
仮想メモリがなければ、プロセス間でメモリリソースを奪い合い、さらには境界を越えてアクセスすることが容易になり、メモリリークを引き起こす可能性があります。また、プロセスのメモリはブロック単位で保存されているため、小さな未割り当てのメモリはより大きなプロセスによって要求されることができず、一定のリソースの無駄が生じます。
仮想メモリを使用して物理メモリを管理することで、物理メモリを人工的にブロック（chunk）に分割し、複数のブロックを ** ページ（page）** として構成し、ページとその占有状況をページテーブルに書き込むことができます。これにより、プロセスが必要とするメモリをブロック形式で保存でき、これらのメモリを集中して保存する必要はなく、逆に任意の位置に配置することができます。仮想メモリと物理メモリの間のマッピング関係（index）を記録し、そのマッピング関係をページテーブルに保存することで、これらの情報に基づいて物理メモリアドレスを見つけることができます。 これらの操作はすべてハードウェアによって行われ、非常に高速で、メモリの可用性と効率を大幅に向上させます。
CPU は最初に操作命令を受け取り、仮想アドレスを MMU（メモリ管理ユニット）に送信します。MMU は物理メモリにアクセスし（実際には物理メモリのキャッシュである TLB にアクセス）、ページテーブルを取得し、その後マッピング関係を見つけて物理アドレスを計算し、CPU に渡します。CPU は物理メモリにアクセスしてデータを取得します。
メモリの構造#
メモリを操作する前に、メモリの構造について理解しておきましょう。
- テキストセクション
- データセクション
- BSS
- ヒープ
- スタック
mallocを使用する際に操作するメモリ構造はヒープ（Heap）です。その末尾にはbrkという名前のポインタがあり、ヒープの頂点を指しています。
これは動的に割り当て可能なメモリ構造であり、必要に応じて動的に一定量のメモリを要求でき、同時に削除操作もサポートしています。一般的に、ポインタを介して要求されたアドレスにデータ操作を行います。
メモリを操作する際に、ハードウェアを直接操作する必要はなく、システムが封装した APIsbrk()を直接使用できます。
sbrk(0)は現在のプログラム実行位置のメモリアドレスを返します。
sbrk(x)はbrkを正の方向に x バイト（bytes）増加させます。
sbrk(-x)はbrkを負の方向に x バイト（bytes）増加させます。
sbrk()が何らかの理由で操作を完了できなかった場合、(void*) -1を返します。
malloc()#
さて、ここまで来て、簡単なmalloc()を実装することができます:
void* malloc( size_t size )
{
void* block;
block = sbrk(size);
if ( block == (void*) -1 )
return NULL;
return block;
}
見た目は良さそうですが、完璧ではありません。
free()関数を書く際に、ポインタを受け取ってそれに関連するメモリを解放しますが、解放するメモリのサイズをどうやって知るのでしょうか？
各アドレスの初めにHeaderを定義することができます:
struct header_t {
size_t size;
unsigned is_free;
};
sizeはHeaderが指すメモリのサイズを保存するために使用されます。
is_freeはこのメモリが占有されているかどうかを示すために使用されます。
現在、私たちのメモリはこのように見えます:
未使用のメモリを見つけるために、このメモリを遍歴する方法が必要です。リンクリストは良い解決策です:
struct header_t {
size_t size;
unsigned is_free;
struct header_t* next;
};
現在はこのようになっています:
メモリをブロック単位で管理しているため、アライメント操作が必要です:
typedef char ALIGN[16];
union header {
struct {
size_t size;
unsigned is_free;
union header *next;
} s;
ALIGN stub;
};
typedef union header header_t;
また、ヘッドとテイルノードを定義する必要があります:
header_t *head, *tail;
マルチスレッドが同時にメモリを呼び出すのを避けるために、グローバルロックを追加し、アドレスを要求した後に解放します:
pthread_mutex_t global_malloc_lock;
現在のバージョンは次のようになります:
void* malloc(size_t size) {
size_t total_size;
header_t* header;
void* block;
if ( size <= 0 ) {
return NULL;
};
pthread_mutex_lock(&global_malloc_lock);
header = get_header_t(size);
if (header)
{
header->s.isFree = 0;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
total_size = size + sizeof(header_t);
block = sbrk(total_size);
if (block == (void*) -1) {
pthread_mutex_unlock(&global_malloc_lock);
return NULL;
} else {
header = block;
};
header->s.isFree = 0;
header->s.size = size;
header->s.next = NULL;
if (head == NULL)
head = header;
if (tail)
tail->s.next = header;
tail = header;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
};
header_t* get_header_t( size_t size ) {
header_t* curr = head;
while (curr)
{
if ( curr->s.isFree && curr->s.size >= size) {
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(head);
};
curr = curr->s.next;
}
return NULL;
}
まず、要求されたメモリが合法かどうかを判断し、次に最低アドレスのノードポインタ（get_header_t()）を探します。
見つかった場合はisFreeとしてマークし、ロックを解除して仮想アドレスの先頭ポインタを返します。
見つからなかった場合は、sbrkを呼び出してメモリを要求し、headerを初期化してtailノードとして設定し、その後ロックを解除してアドレスを返します。
total_sizeはヘッダーと実際に必要なメモリサイズの 2 つの部分を含みます。
free()#
free()関数を設計する際に注意すべき詳細があります：解放するアドレスがヒープの末尾にあるかどうかを最初に判断します。
末尾にある場合は、直接オペレーティングシステムに解放を任せます。そうでない場合は、isFreeとしてマークし、後で再利用します。
void free(void* block) {
if (!block)
{
return NULL;
}
header_t* header = (header_t*)block - 1;
void* programbreak = sbrk(0);
pthread_mutex_lock(&global_malloc_lock);
if ((char*)block + header->s.size == programbreak)
{
size_t total_size = header->s.size + sizeof(header_t);
//release
if (head == tail)
{
head = tail = NULL;
} else {
header_t* curr = head;
//change tail
while (curr->s.next == tail)
{
curr->s.next = NULL;
tail = curr;
}
}
sbrk(-total_size);
pthread_mutex_unlock(&global_malloc_lock);
return;
};
header->s.isFree = 1;
pthread_mutex_unlock(&global_malloc_lock);
}
まずbrkの位置を見つけてprogrambreakに割り当て、その後解放するオブジェクトがヒープの頂点にあるかどうかを判断します。
char*とsize_t、void*は同じバイト数を持っています:
//test.c
#include <stddef.h>
int main(int argc, char const *argv[])
{
printf("char* is:%d, char is:%d, void* is:%d, size_t is:%d", sizeof(char*), sizeof(char), sizeof(void*), sizeof(size_t));
return 0;
}
//char* is:8, char is:1, void* is:8, size_t is:8
ヒープの頂点にある場合、(char*)block + header->s.size == programbreakとなります。
その後、最後のメモリを遍歴して解放し、倒数第二のメモリをtailとして設定します。
ヒープの頂点にない場合は、一時的にisFreeとしてマークし、後で再利用を待ちます。
calloc()#
void* calloc( size_t nsize, size_t num)
{
size_t size;
void* block;
if (!num || !nsize)
return NULL;
size = nsize * num;
//overflow check
if (size != nsize * num)
return NULL;
block = malloc(size);
if (!block)
return NULL;
memset(block, 0, size);
return block;
}
calloc()は、返されるアドレスが指すメモリブロックがすべてNullであることを要求します。memsetを使用して 0 に設定できます。
realloc()#
void* realloc(void* block, size_t size)
{
header_t* header;
void* ret;
if (!block || !size)
return NULL;
header = (header_t*)block - 1;
if (header->s.size >= size)
return block;
ret = malloc(size);
if (ret)
{
memcpy(ret, block, header->s.size);
free(block);
}
return ret;
}
realloc()は特別であり、使用する際には返されるポインタが指すアドレスが必ずしも元のアドレスであるとは限らないことに注意する必要があります。
realloc()を使用すると、次の 2 つの状況が発生する可能性があります:
- ヒープメモリが高位に成長し、上方の空いているメモリのサイズが増加分を収容できる場合。元のアドレスを返し、
headerのsizeを変更します。 - ヒープメモリの上方に空いているメモリが不足している場合、
mallocを呼び出して新しいアドレスを再度要求し、元のアドレスの内容を新しく要求したアドレスにコピーします。
コンパイル#
$ gcc -o memalloc.so -fPIC -shared memalloc.c
$ export LD_PRELOAD=$PWD/memalloc.so
$ ls
memalloc.c memalloc.so
拡張#
C/C++ はその優れた性能で知られていますが、これは常に批判の対象でもあります。これを使用する人がコンピュータシステムについて深く理解していない場合、誤操作を引き起こす可能性があります。
他の高級言語はメモリ管理を自動化し、そのメカニズムをガーベジコレクション（OC）と呼び、その原理は大まかに次のように要約できます：あるオブジェクトが到達不可能であれば、ガーベジコレクタによって回収されます。
参考文献#
おすすめの読書: