Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 1138] ファイルの概要

このコミットは、Go言語のランタイムにおける初期のメモリ管理システム、特にmalloc（メモリ確保）機能の最初の部分を導入するものです。Go言語の設計思想において、効率的なメモリ管理は重要な要素であり、このコミットはその基盤を築くものです。

コミット

commit 75647d202475edd41e811e936760e834cafc8594
Author: Russ Cox <rsc@golang.org>
Date:   Mon Nov 17 12:32:35 2008 -0800

    First pieces of malloc.
    
    R=r
    DELTA=756  (754 added, 0 deleted, 2 changed)
    OCL=19266
    CL=19378

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/75647d202475edd41e811e936760e834cafc8594

元コミット内容

First pieces of malloc.

R=r
DELTA=756  (754 added, 0 deleted, 2 changed)
OCL=19266
CL=19378

変更の背景

このコミットは、Go言語の初期開発段階において、プログラムが動的にメモリを確保・解放するための基本的なメカニズムを導入するものです。Go言語はガベージコレクション（GC）を持つ言語ですが、GCが効率的に動作するためには、その下層にあるメモリ確保（アロケーション）の仕組みが非常に重要です。このコミットは、そのアロケーションの「最初のピース」を提供し、後のGoランタイムのメモリ管理の基礎となります。特に、コメントにtcmallocへの言及があることから、Google内部で開発された高性能なメモリ管理ライブラリであるtcmallocの設計思想をGoのランタイムに持ち込もうとしていることが伺えます。

前提知識の解説

メモリ管理とアロケータ

コンピュータプログラムは実行時にメモリを必要とします。このメモリを動的に確保（mallocなど）し、不要になったら解放（freeなど）する仕組みがメモリ管理です。メモリ管理システムは、プログラムのパフォーマンス、安定性、メモリ使用効率に大きく影響します。

tcmalloc (Thread-Caching Malloc)

tcmallocは、Googleが開発した高性能なメモリ管理ライブラリです。その主な特徴は以下の通りです。

  • スレッドローカルキャッシュ (Thread-Local Cache): 各スレッドが独自の小さなメモリキャッシュを持つことで、ロック競合を減らし、並行処理性能を向上させます。これにより、頻繁な小さなアロケーション/デアロケーションが高速になります。
  • 中央ヒープ (Central Heap): スレッドローカルキャッシュで処理できない大きなアロケーションや、スレッドローカルキャッシュから溢れたメモリは、中央ヒープで管理されます。
  • ページベースの管理: メモリを固定サイズのページ（通常4KB）単位で管理し、これらのページを「スパン (Span)」と呼ばれる連続したページの塊として扱います。
  • サイズクラス (Size Class): 小さなオブジェクトのアロケーションを効率化するため、あらかじめ定義されたいくつかのサイズクラスにメモリを分割します。これにより、アロケーション時の計算コストを削減し、メモリの断片化を抑制します。

Go言語のランタイムにおけるメモリ管理は、このtcmallocの設計思想に強く影響を受けています。

ページマップ (PageMap)

ページマップは、仮想メモリのアドレス空間を物理メモリにマッピングするためのデータ構造です。このコミットでは、pagemap.cで実装されているように、ページ番号（仮想アドレスをページサイズで割ったもの）から、そのページが属するSpan構造体へのマッピングを管理するために使用されます。これは、free関数が与えられたポインタがどのメモリブロックに属するかを効率的に特定するために不可欠です。

技術的詳細

このコミットで導入されるメモリ管理の初期実装は、tcmallocの主要な概念をGoランタイムに適用しています。

  1. Span (スパン): malloc.cで定義されるSpan構造体は、連続したメモリページ（baseとlengthで表現）の塊を表します。SpanInUseとSpanFreeの2つの状態を持ち、メモリが使用中か解放済みかを管理します。
  2. Central (中央キャッシュ): malloc.cで定義されるCentral構造体は、中央のフリーリストを管理します。free[256]配列は、異なるサイズクラスの小さなオブジェクトに対応するフリーリストを保持し、largeは大きなスパンのフリーリストを管理します。
  3. PageMap (ページマップ): pagemap.cで実装されるPageMapは、ページ番号からSpanへのマッピングを提供します。これは、pmlookup（ルックアップ）とpminsert（挿入）関数を通じて操作され、メモリポインタから対応するスパンを効率的に見つけるために使用されます。実装は4レベルのラディックスツリー（基数木）を使用しており、64ビットアドレス空間と4KBページを効率的に扱うように設計されています。
  4. サイズクラス (Size Class): malloc.cのclasstosize配列とsizetoclass関数は、オブジェクトのサイズを対応するサイズクラスにマッピングします。これにより、異なるサイズのオブジェクトを効率的に管理し、メモリの断片化を減らします。
  5. アロケーションと解放のロジック:
    • allocsmall: 小さなオブジェクト（SmallFreeClassesで定義されたサイズクラス内）をアロケートします。将来的にはスレッドローカルキャッシュ（m->freelist[cl]）から取得し、なければ中央キャッシュ（centralgrab）から取得する設計になっています。
    • alloclarge: 大きなオブジェクト（LargeSize以上）をアロケートします。これは中央キャッシュから適切なスパンを取得します。
    • alloc: nバイトのメモリをアロケートするメイン関数で、サイズに応じてallocsmallまたはalloclargeを呼び出します。
    • free: メモリを解放する関数で、与えられたポインタからspanofptrを使って対応するスパンを見つけ、そのスパンの状態とサイズクラスに基づいて解放処理を行います。大きなオブジェクトは直接中央キャッシュに返され、小さなオブジェクトはスレッドローカルのフリーリストに返されます。
  6. Trivial Allocator (triv.c): triv.cは、Span構造体やPageMapのノードなど、メモリ管理システム自体が使用する小さな内部オブジェクトや、より大きなメモリブロックをOSから直接取得するための「自明な」ベースアロケータを提供します。これはsys·mmapを呼び出してOSからメモリを確保します。

コアとなるコードの変更箇所

このコミットでは、主に以下のファイルが新規作成または変更されています。

  • src/runtime/runtime.c: MAP_ANONのコメント修正。
  • src/runtime/runtime.h:
    • uintptr型の追加（uint64のtypedef）。
    • SmallFreeClasses定数（mallocにおける小さなフリーリストの数）の追加。
    • M構造体（GoのM（Machine）構造体、OSスレッドを表す）にfreelist[SmallFreeClasses]（スレッドローカルなフリーリスト）の追加。
  • usr/rsc/mem/Makefile: 新しいメモリ管理関連のC言語およびGo言語ファイルのコンパイルとリンクを定義するMakefile。testrandom, testrepeat, testsizetoclassといったテストターゲットが含まれます。
  • usr/rsc/mem/allocator.go: Go言語からC言語で実装されたアロケータの関数（free, malloc, memsetなど）を呼び出すためのエクスポート定義。
  • usr/rsc/mem/malloc.c:
    • Goランタイムの主要なメモリ確保・解放ロジックをC言語で実装。
    • Span、Central構造体の定義。
    • insertspan, shrinkspan, spanofptr, allocspan, freespanといったスパン管理関数。
    • classtosize配列とsizetoclass関数によるサイズクラスの定義とマッピング。
    • centralgrab, allocsmall, alloclarge, alloc, freeといったアロケーション/デアロケーションのコアロジック。
    • memsetやスタックアロケーション/解放のプレースホルダ関数。
  • usr/rsc/mem/malloc.h: malloc.cで使用される型定義（PageMap）や定数（PageShift, PageMaskなど）、外部関数宣言。
  • usr/rsc/mem/pagemap.c: ページ番号からスパンへのマッピングを管理するPageMapの実装。pmlookupとpminsert関数が含まれます。
  • usr/rsc/mem/testrandom.go: ランダムなサイズでメモリを確保・解放し、メモリフットプリントをテストするGoプログラム。
  • usr/rsc/mem/testrepeat.go: 特定のサイズで繰り返しメモリを確保・解放し、アロケータの安定性とフットプリントをテストするGoプログラム。
  • usr/rsc/mem/testsizetoclass.go: sizetoclass関数の正確性をテストするGoプログラム。
  • usr/rsc/mem/triv.c: メモリ管理システム自体が使用する小さなオブジェクトや、OSから直接メモリを取得するための「自明な」ベースアロケータ。trivalloc関数が含まれます。

コアとなるコードの解説

このコミットの核心は、usr/rsc/mem/malloc.cに実装されたメモリ管理ロジックです。

malloc.cの主要な概念と関数:

  • Span構造体:

    typedef struct Span Span;
struct Span
{
    Span *next;     // in free lists
    byte *base;     // first byte in span
    uintptr length; // number of pages in span
    int32 cl;       // size class
    int32 state;    // state (SpanInUse, SpanFree)
};

    これは、連続したメモリページ（baseから始まりlengthページ分）の塊を表します。clは、このスパンがどのサイズクラスのオブジェクトを保持しているかを示します。

  • Central構造体:

    typedef struct Central Central;
struct Central
{
    Lock;
    Span *free[256]; // free lists for small objects
    Span *large;     // free spans >= MaxPage pages
};
static Central central; // Global central cache

    これは、Goランタイム全体で共有される中央のメモリキャッシュです。free配列は、特定のサイズクラスに属する小さなオブジェクトのためのフリーリストを管理し、largeは大きなスパンのフリーリストを管理します。

  • PageMap (spanmap):

    static PageMap spanmap;

    これは、仮想アドレスのページ番号から、そのページを含むSpan構造体へのマッピングを管理します。これにより、任意のメモリポインタがどのスパンに属するかを効率的に特定できます。

  • allocspan(int32 npage): npageで指定されたページ数以上の空きスパンを中央キャッシュから探し、見つからなければtrivallocを使ってOSから新しいメモリを確保し、新しいスパンを作成します。スパンが要求されたサイズよりも大きい場合、残りの部分を新しいスパンとして分割し、フリーリストに戻します。

  • freespan(Span *s): 使用済みのスパンsを中央キャッシュの適切なフリーリスト（サイズに応じてcentral.freeまたはcentral.large）に戻します。

  • sizetoclass(int32 siz): 与えられたサイズsizがどのサイズクラスに属するかを計算します。これは、classtosize配列で定義された固定サイズの範囲に基づいて行われます。

  • allocsmall(int32 cl): 指定されたサイズクラスclの小さなオブジェクトをアロケートします。最初はスレッドローカルなフリーリスト（m->freelist[cl]）を試み、空であればcentralgrabを呼び出して中央キャッシュからブロックを取得します。

  • alloclarge(int32 np): npページ分の大きなオブジェクトをアロケートします。これはallocspanを呼び出して新しいスパンを取得します。

  • alloc(int32 n): nバイトのメモリをアロケートするメインのエントリポイントです。nがLargeSize（32KB）未満であればallocsmallを、それ以上であればalloclargeを呼び出します。

  • free(void *v): ポインタvが指すメモリを解放します。spanofptr(v)を使って対応するスパンを見つけ、そのスパンのサイズクラスに基づいて、大きなオブジェクトであればfreespanで中央キャッシュに返し、小さなオブジェクトであればスレッドローカルなフリーリストに連結します。解放されたメモリはゼロクリアされます。

これらの関数とデータ構造が連携して、Goランタイムの初期のメモリ管理システムを構成しています。特に、tcmallocの設計思想を取り入れることで、並行処理環境下での効率的なメモリ管理を目指していることがわかります。

関連リンク

参考にした情報源リンク

  • コミットデータ: ./commit_data/1138.txt
  • Go言語のソースコード (GitHub): https://github.com/golang/go
  • tcmallocに関する一般的な情報源 (例: Wikipedia, Google Developersドキュメントなど)
  • Go言語のメモリ管理に関する初期の設計ドキュメントや議論 (Goのメーリングリストやデザインドキュメントなど、当時の情報源を想定)