C Academy · レッスン

アラインメントと分割

Q: 「アラインメントと分割」で何を学びますか？

ブロックを利用可能な状態に整えます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

ブロックを利用可能な状態に整えます。

「アラインメントと分割」はCoddyKit上の無料C Academyレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。

アラインメントが重要な理由

すべての型にはアラインメント要件があります。アドレスが、ある2の累乗の倍数でなければなりません。通常、doubleには8バイトのアラインメントが必要です。

mallocは何を格納するか把握していないため、最も厳しい型に合わせたポインタを返す必要があります。64ビットシステムでは通常16バイトです。

#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t);   /* often 16 */

align_upのテクニック

サイズを2の累乗のアラインメントの次の倍数まで切り上げる処理には、古典的なビット演算のテクニックがあります。a - 1を加えてから、下位ビットをマスクします。

これは a が2の累乗の場合にのみ機能しますが、実際のアラインメントはすべてそうなっています。

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);
}
/* align_up(13, 8) == 16, align_up(16, 8) == 16 */

計算の動作を検証する

実行可能なプログラムで align_up を検証しましょう。複数のサイズを8バイトおよび16バイトの境界まで切り上げ、結果を表示します。

#include <stdio.h>
#include <stddef.h>

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);
}

int main(void) {
    printf("%zu\n", align_up(13, 8));   /* 16 */
    printf("%zu\n", align_up(16, 8));   /* 16 */
    printf("%zu\n", align_up(1, 16));   /* 16 */
    printf("%zu\n", align_up(33, 16));  /* 48 */
    return 0;
}

要求サイズのアラインメント

アロケータでは、すべての要求について、最初に要求されたサイズをアラインメント境界まで切り上げます。これにより、次のブロックもアラインメントされた位置から始まります。

パディングバイトは内部フラグメンテーションであり、あらゆるアラインメントに対応するためのコストです。

#define ALIGN 16
void *my_alloc(size_t size) {
    size = align_up(size, ALIGN);
    /* now find a block of this aligned size */
    /* ... */
    return NULL;
}

ブロック全体を再利用する問題

前のレッスンでは、小さな要求に対しても空きブロック全体を返していました。4000バイトの空きブロックを16バイトの要求に渡すと、残りが無駄になります。

分割によってブロックを、使用する部分と空きのまま残す余りに分けます。

ブロックの分割

選んだブロックが必要なサイズより大幅に大きい場合、要求領域の末尾に新しいヘッダーを配置します。残りは、リスト内の小さな空きブロックになります。

余りにヘッダーとある程度のペイロードを格納できる十分な大きさがある場合にのみ分割します。そうでなければ、その断片は役に立ちません。

void split(block_t *b, size_t size) {
    size_t rem = b->size - size;
    if (rem < sizeof(block_t) + ALIGN) return; /* too small */
    block_t *nb = (block_t *)((char *)(b + 1) + size);
    nb->size = rem - sizeof(block_t);
    nb->free = 1;
    nb->next = b->next;
    b->size = size;
    b->next = nb;
}

アロケーション、アラインメント、分割

これでアロケーション処理全体は、サイズをアラインメントし、適合するブロックを探し、大きな余りを分割してから、ブロックを使用中としてマークするようになりました。

これによりブロックのサイズが適切に保たれ、使用可能な空き領域が後に残ります。

void *my_alloc(size_t size) {
    size = align_up(size, ALIGN);
    block_t *b = first_fit(size);
    if (!b) return NULL;
    split(b, size);
    b->free = 0;
    return (void *)(b + 1);
}

プール自体のアラインメントを保つ

正しく動作させるには、プールの開始アドレスとヘッダーのサイズもアラインメントに合わせる必要があります。これにより、すべてのペイロードが境界上に配置されます。

静的バッファに alignas を使うと、仕組み全体がアラインメントされた状態で始まることが保証されます。

#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */

実行可能なアラインメント対応アロケーション

このプログラムはアラインメントされたプールからメモリを割り当て、返されたアドレスを16で割った余りを表示します。余りが常にゼロになるため、正しくアラインメントされていることが分かります。

#include <stdio.h>
#include <stddef.h>
#include <stdalign.h>

static size_t align_up(size_t n, size_t a){ return (n+a-1)&~(a-1); }
alignas(16) static unsigned char pool[1024];
static size_t off = 0;

void *alloc16(size_t s){ off=align_up(off,16); if(off+s>sizeof(pool)) return NULL; void*p=&pool[off]; off+=s; return p; }

int main(void){
    void *a = alloc16(1);
    void *b = alloc16(20);
    printf("a %% 16 = %lu\n", (unsigned long)((size_t)a % 16));
    printf("b %% 16 = %lu\n", (unsigned long)((size_t)b % 16));
    return 0;
}

分割と結合

分割と結合は互いに反対の操作で、バランスを取ります。アロケーションでは大きなブロックを分割し、解放時には小さなブロックを再び結合します。

この2つにより、同じプールで要求サイズの変化に対応しながら、領域を無駄にしたり恒久的にフラグメント化したりせずに済みます。

おもちゃから実用的なアロケータへ

これで4つの柱がそろいました。メモリソース、アラインメントされたヘッダー、結合を伴うフリーリスト再利用、そして分割です。実際のアロケータでは、速度と規模への対応のために、サイズクラスのビン、スレッドキャッシュ、OSとの統合などを追加します。

しかし、ここで構築した基本概念が、あらゆる malloc 実装を支えています。

クイックチェック

アロケーション中にブロックを分割する理由を考えてみましょう。

まとめ

アラインメントでは、ビット演算のテクニック (n + a - 1) & ~(a - 1) を使ってサイズを切り上げ、あらゆる型に適したペイロードを実現します。分割では大きすぎる空きブロックを、使用部分と空きの余りに切り分け、結合では解放時にその逆を行います。

この4つの柱によって、完全で正しいメモリアロケータが形成されます。

よくある質問

「アラインメントと分割」レッスンは無料ですか？

はい。「アラインメントと分割」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。

「アラインメントと分割」で何を学びますか？

ブロックを利用可能な状態に整えます。ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン4/4です。

「アラインメントと分割」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC Academyレッスンでコードを書いて実行できますか？

はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← C Academyに戻る