heap_allocator
1.0.0
これは、私が取り組んでいる趣味の OS 用に書いた単純なヒープ アロケーターです。このアロケーターはほとんど調査せずに作成しており、できるだけ理解しやすいように作成されています。このリポジトリは、(私のように) OS 開発が初めての人、または malloc や free などの関数の簡略化されたバージョンに興味がある人にとって役立つと思います。
ヒープとリンク リストを定義する 2 つのヘッダー ファイルがあります。このリポジトリをコンパイルするには:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
これにより、アロケーターのデモが実行され、いくつかの情報が出力されます。
このヒープを初期化するには、メモリのセクションを提供する必要があります。このリポジトリでは、そのメモリはmallocによって提供されます (はい、ヒープを介してヒープを割り当てます)。 OS 設定では、一部のページをマップしてヒープに提供する必要があります (1 つのシナリオ)。 heap_t構造体のビンにもメモリを割り当てる必要があることに注意してください。
関数 init_heap が呼び出されるときは、空のヒープ構造体のアドレス (割り当てられた bin ポインターを含む) を指定する必要があります。 init_heap 関数は、ヘッダー ( node_t struct) とフッター ( footer_t struct) を含む 1 つの大きなチャンクを作成します。このチャンクのサイズを決定するために、関数は定数HEAP_INIT_SIZEを使用します。ヒープの終了場所を決定するために、これをstart引数に追加します。
メモリの各チャンクには、先頭にノード構造体があり、最後にフッター構造体があります。ノードは、チャンクが空いているかどうかに関係なく、サイズと、二重リンク リストで使用される 2 つのポインター (次と前) を保持します。フッター構造体は、ヘッダーへのポインターを保持するだけです (隣接するチャンクを解放するときに使用されます)。ヒープの最後にあるチャンクは、「荒野」チャンクと呼ばれます。これは最大のチャンクであり、その最小サイズと最大サイズは heap.h で定義されます。ヒープの縮小と拡張は、この荒野のチャンクのサイズを変更するのと同じくらい簡単です。メモリの空きチャンクは「ビン」に格納されます。各ビンは実際には、同様のサイズを持つノードの二重リンク リストにすぎません。ヒープ構造には、定義された数のビン ( heap.h のBIN_COUNT ) が保持されます。どのビンにチャンクを配置するかを決定するには、関数get_bin_indexによってチャンクのサイズがビン インデックスにマップされます。この一貫したビニング機能により、定義された方法でチャンクにアクセスし、保存できることが保証されます。チャンクはビンに挿入されるときにソートされるため、チャンクの挿入は O(1) ではありませんが、これにより、最も適合するチャンクを見つけることがはるかに簡単になります。ビニング関数は、このヒープのユーザーが適切と感じるように定義できることに注意してください。チャンクの迅速な取得を支援するために、より洗練されたビニング関数を決定すると有益な場合があります。
関数heap_alloc割り当て元のヒープ構造体のアドレスとサイズを受け取ります。この関数は単にget_bin_index使用して、このサイズのチャンクがどこにあるべきかを決定します。もちろん、そのサイズのチャンクが存在しない可能性もあります。対応するビンでチャンクが見つからない場合は、次のビンがチェックされます。これは、チャンクが見つかるか、最後のビンに到達するまで続きます。最後のビンに到達すると、メモリの一部が荒野のチャンクから取得されます。見つかったチャンクが十分に大きい場合は、分割されます。チャンクを分割する必要があるかどうかを判断するために、現在の割り当てで使用されていないメタデータの量 (オーバーヘッド) が差し引かれます。残っているものがMIN_ALLOC_SZ以上である場合は、このチャンクを分割し、残りを正しいビンに配置する必要があることを意味します。見つかったチャンクを返す準備ができたら、 nextフィールドのアドレスを取得してそれを返します。これは、チャンクが割り当てられている間はnextフィールドとprevフィールドが使用されないため、チャンクのユーザーはヒープの内部動作に影響を与えることなくこれらのフィールドにデータを書き込むことができるために行われます。
関数heap_free heap_allocによって返されたポインターを受け取ります。ノード構造体のアドレスを取得するために、正しいオフセットが減算されます。単にチャンクを正しいビンに配置するのではなく、提供されたチャンクの周囲のチャンクがチェックされます。これらのチャンクのいずれかが空いている場合は、チャンクを結合して、より大きなチャンクを作成できます。チャンクを結合するには、フッターを使用して前のチャンクのノード構造体と次のチャンクのノード構造体を取得します。たとえば、 to_freeというチャンクがあるとします。このチャンクの前のチャンクを取得するには、 sizeof(footer_t)を減算して、前のチャンクのフッターを取得します。フッターには、前のチャンクの先頭へのポインターが保持されます。次のチャンクを取得するには、単にto_freeのフッターを取得し、次のチャンクを取得するためにsizeof(footer_t)を追加します。これらすべてが完了し、サイズが再計算されると、チャンクはビンに戻されます。
注: このコードはもともと 32 ビット マシン用にコンパイルされました。これは、このコードが使用されたとき、両方のサイズが同じであるため、int をポインターにキャストすることが許容されることを意味します。 64 ビット システムでは、コンパイラはサイズの違いについて警告します。これらの警告を消すために、unsigned int からポインターにキャストするときにuintptr_t使用しました。これにより、可読性が少し損なわれ、キャストやポインター演算の一部が冗長になるため、コードを読むときはその点に留意してください。
