malloc() と free() の実装 - 大きなブロックの分割

このシリーズの前回の投稿では、再利用するメモリ ブロックを選択する順序によってメモリ消費量が増減する可能性があり、これを回避するために関数を変更しました。無駄。しかし、さらに深刻な別の問題を解決する必要があります。場合によっては、非常に大きなメモリ ブロックが、いくつかの小さなブロックが使用できるスペースを占有する可能性があるということです。以下のケースを考えてみましょう。ここでは、大きなメモリ チャンクを割り当て、割り当てを解除してから、2 つのはるかに小さなブロックを割り当てます。

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

ここでは、128 バイトの空きメモリ ブロックがあり、わずか 8 バイトのブロックを割り当てると、128 バイトすべてが使用できなくなります。さらに 8 バイトのブロックを割り当てると、ヒープが再び大きくなる必要があります。これはメモリの効率的な使用法ではありません。

このケースには少なくとも 2 つの一般的な解決策があります。 1 つは、より効率的ですが、bins を使用することです。ブロックをサイズごとにグループ化するリストです。これはより洗練され効率的なアプローチですが、より複雑です。より簡単なもう 1 つのオプションは、大きなブロックを見つけて、それを小さなブロックに分割することです。このアプローチに従います。

ただし、覚えておいてください: シンプルであるということは、必ずしもシンプルであるという意味ではありません ;-)

初期リファクタリング

始める前に、小さなリファクタリングを行ってみましょう。現在、header_new() 関数は 2 つのことを実行します。新しいブロックにより多くのメモリを割り当て、そのヘッダーを初期化してメタデータと前のブロックへのポインタを設定します。ヘッダーの初期化の部分が役立つかもしれないので、抽出してみましょう。読みやすさを向上させるために 2 つの新しい関数を作成します。

• header_plug() 関数。初期化されたブロックを前後のブロックに「接続」します。
• header_init() 関数。ブロックのメタデータ (サイズと可用性) の初期値を設定します。

外観は次のとおりです:

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

ここで、次の新しい関数を使用するように header_new() を変更する必要があります。

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

(さらに、header_plug() がそれを処理するため、abmalloc() 関数から行 last->previous->next = last; を削除できます。)

ブロックの分割

これらのツールを用意して、header_split() 関数を作成しましょう。ヘッダーと必要な最小サイズを指定すると、元のブロックが

• 必要なサイズ、
• 新しいブロックの新しいヘッダー、および
• メモリが少し追加されました。

まず、ブロックが十分な大きさであるかどうかを確認します。

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

この条件が満たされる場合、ブロックを分割します。まず、ヘッダーのサイズと abmalloc によって要求されたスペースを減算して、現在のブロックのサイズを減らします。

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

これにより、現在のブロックの後にメモリ空間が残り、それを使用して新しいブロックを作成します。この新しいブロックのポインターを計算します:

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

新しいブロックへのポインターを取得したので、header_init():
でそのヘッダーを初期化します。

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

そして、header_plug():
を使用して、新しいブロックを前後のブロックに接続します。

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

元のブロックが最後のブロックだった場合、新しいブロックが最後になるため、最後のポインターを更新します。

header->size = original_size - size - sizeof(Header);

最後に、新しいブロックを返します:

Header *new_header = header + sizeof(Header) + header->size;

元のブロックが十分に大きくない場合は、単純に元のブロックを返します。

header_init(new_header, size, true);

abmalloc() を更新しています

ここで、abmalloc() 関数に戻り、使用可能なブロックを見つけた場所で header_split() を呼び出して分割を試みます。

header_plug(new_header, header, header->next);

ブロックが分割できる場合は、新しいブロックが返されます。それ以外の場合は、元のブロックが保持され、以前と同様に返されます。

ブロック分割に関する注意事項

元のブロックの最後に新しいブロックを作成したことに注目してください。最初に作成することもできましたが、最後に新しい使用済みブロックを作成することで、新しい空きブロックが古いブロックの近くに留まります。こうすることで、次回 abmalloc() が呼び出されたときに最初に見つかります。

大きなメモリ ブロックを分割することは前進ですが、逆の問題があります。小さなメモリ ブロックは断片化を引き起こし、より大きなリクエストを行うとヒープが増大する可能性があります。これを解決する方法については、次の投稿で説明します。

以上がmalloc() と free() の実装 - 大きなブロックの分割の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。