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

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

このコミットは、Goランタイムに新しいメモリ割り当てシステムを導入するものです。これは、Googleの高性能メモリ割り当てライブラリであるtcmallocの設計思想に基づいています。コミットメッセージにある「(not used by default)」が示す通り、この時点ではまだデフォルトのメモリ割り当てメカニズムとしては使用されていませんが、Goのメモリ管理の基盤を大きく変える重要な一歩となります。

コミット

commit e29ce175eda2016b93e755b6a5ae759b5b692834
Author: Russ Cox <rsc@golang.org>
Date:   Thu Dec 18 15:42:28 2008 -0800

    malloc in runtime (not used by default)
    
    R=r
    DELTA=1551  (1550 added, 0 deleted, 1 changed)
    OCL=21404
    CL=21538

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

https://github.com/golang/go/commit/e29ce175eda2016b93e755b6a5ae759b5b692834

元コミット内容

Goランタイムにtcmallocベースのメモリ割り当て機能を導入。この機能は現時点ではデフォルトでは使用されない。

変更の背景

Go言語は、ガベージコレクション（GC）を持つ言語であり、効率的なメモリ管理はランタイムのパフォーマンスに直結します。従来のメモリ割り当てメカニズムでは、並行処理におけるスケーラビリティや、メモリフラグメンテーションの問題が課題となる可能性がありました。

tcmalloc（Thread-Caching Malloc）は、Googleが開発した高性能なメモリ割り当てライブラリであり、特にマルチスレッド環境でのパフォーマンスとメモリ効率に優れています。その設計思想は、スレッドローカルなキャッシュと中央ヒープを組み合わせることで、ロック競合を最小限に抑え、高速な割り当て・解放を実現することにあります。

このコミットは、Goランタイムにtcmallocの設計を取り入れることで、将来的なGoプログラムのメモリ管理性能を向上させるための初期段階として行われました。これにより、Goの並行処理モデルとより親和性の高い、スケーラブルなメモリ割り当て基盤を構築することが目指されました。

前提知識の解説

メモリ割り当ての基本

プログラムがメモリを必要とする際、オペレーティングシステム（OS）からメモリを要求し、使用後に解放します。このプロセスを効率的に行うのがメモリ割り当て器（アロケータ）の役割です。

  • ヒープ: プログラムが動的にメモリを確保・解放する領域。
  • フラグメンテーション: メモリの割り当てと解放を繰り返すうちに、利用可能なメモリが小さな断片として散らばり、大きな連続したメモリ領域が確保できなくなる現象。
    • 内部フラグメンテーション: 割り当てられたメモリブロックが要求されたサイズよりも大きく、未使用の領域が生じること。
    • 外部フラグメンテーション: 利用可能なメモリの合計は十分だが、連続した大きなブロックがないために割り当てが失敗すること。
  • スレッドセーフティ: 複数のスレッドが同時にメモリ割り当て器にアクセスしても、データの一貫性が保たれること。通常、ロック機構を用いて実現されるが、ロックはパフォーマンスのボトルネックになりやすい。

tcmallocの設計思想

tcmallocは、以下の3層構造でメモリを管理することで、高速かつ効率的なメモリ割り当てを実現します。

  1. Thread-Local Cache (MCache):
    • 各スレッドが持つプライベートなメモリキャッシュ。
    • 小さなオブジェクト（通常32KB以下）の割り当て・解放は、ほとんどの場合このキャッシュ内で完結するため、ロックが不要で非常に高速です。
    • 内部フラグメンテーションを抑えるため、様々なサイズの「サイズクラス」に分割されたフリーリストを持ちます。
  2. Central Free List (MCentral):
    • 複数のスレッド間で共有されるフリーリスト。
    • MCacheが空になった場合、MCentralからオブジェクトのまとまり（スパン）を取得して補充します。
    • MCacheが一杯になった場合、MCentralにオブジェクトを返却します。
    • MCentralへのアクセスはロックによって保護されますが、MCacheとの間で一度に複数のオブジェクトをやり取りすることで、ロックの取得回数を減らし、競合を緩和します。
  3. Page Heap (MHeap):
    • OSから取得した大きなメモリ領域（ページ単位）を管理する中央ヒープ。
    • MCentralがメモリを必要とする場合、MHeapからページ単位でメモリを取得します。
    • 大きなオブジェクト（通常32KB超）は、MCacheやMCentralを介さず、直接MHeapから割り当てられます。
    • MHeapは、連続した空きページを結合（coalesce）することで、外部フラグメンテーションを抑制します。
    • OSとのメモリのやり取り（mmap/munmapなど）を抽象化します。

その他の重要な概念

  • サイズクラス: メモリ割り当て要求を、あらかじめ定義された固定サイズに丸めることで、メモリ管理を単純化し、内部フラグメンテーションを許容範囲に抑えます。
  • スパン (MSpan): 連続したメモリページのまとまり。tcmallocでは、このスパンを単位としてメモリが管理されます。小さなオブジェクトの場合、スパンはさらに小さなオブジェクトに分割されてMCacheやMCentralに提供されます。
  • FixAlloc: 固定サイズのオブジェクトを効率的に割り当てるためのシンプルなフリーリストアロケータ。tcmalloc自身の内部データ構造（MSpanやMCacheなど）の割り当てに使用されます。
  • Radix Tree (MHeapMap): ページID（メモリのアドレスをページサイズで割った値）から、そのページを含むMSpanを高速に検索するためのデータ構造。Goのこの実装では3レベルのラディックスツリーが使用されています。

技術的詳細

このコミットで導入されたメモリ割り当て器は、tcmallocの主要なコンポーネントをGoランタイムのCコードとして実装しています。

主要なデータ構造と役割

  • MStats: メモリ割り当てに関する統計情報（割り当て済みメモリ量、OSから取得したメモリ量など）を保持します。
  • FixAlloc: MSpanやMCacheといった、アロケータ自身の内部管理構造体を効率的に割り当てるための固定サイズアロケータ。
  • MSpan: 連続したメモリページのブロックを表す構造体。start（開始ページID）、npages（ページ数）、freelist（このスパン内の空きオブジェクトリスト）、sizeclass（このスパンが割り当てられたサイズクラス）、state（使用中か空きか）などの情報を含みます。
  • MCacheList: MCache内で、特定のサイズクラスの空きオブジェクトを管理する単一リンクリスト。
  • MCache: 各Goルーチン（M）に紐付けられるスレッドローカルなキャッシュ。MCacheListの配列を持ち、小さなオブジェクトの高速な割り当て・解放を担います。ロックフリーでアクセス可能です。
  • MCentral: 特定のサイズクラスのMSpanを管理する中央フリーリスト。nonempty（空きオブジェクトを持つスパンのリスト）とempty（完全に割り当て済みのスパンのリスト）の2つのMSpanListを持ちます。MCacheが空になった際に、ここからスパンを取得します。アクセスにはロックが必要です。
  • MHeapMap: ページIDから対応するMSpanを検索するためのラディックスツリー。メモリ上の任意のポインタがどのスパンに属するかを特定するために使用されます。
  • MHeapMapCache: MHeapMapのキャッシュ。頻繁にアクセスされるページIDとサイズクラスのマッピングを高速に取得するために使用されます。
  • MHeap: ページヒープ。OSから取得したメモリを管理し、MCentralにMSpanを提供します。free（様々な長さの空きスパンリスト）とlarge（大きな空きスパンリスト）を持ち、スパンの結合（coalescing）も行います。

割り当てと解放のフロー（小オブジェクト）

  1. 割り当て (malloc):
    • 要求されたサイズを最も近いサイズクラスに丸めます。
    • 現在のM（Goルーチンが実行されるOSスレッド）のMCacheから、対応するサイズクラスのフリーリストをチェックします。
    • MCacheに空きがあれば、そこからオブジェクトを返します（ロック不要）。
    • MCacheが空の場合、対応するMCentralからオブジェクトのまとまり（スパン）を取得してMCacheを補充します（MCentralはロックが必要）。
    • MCentralも空の場合、MHeapから新しいページのスパンを取得し、それを小さなオブジェクトに分割してMCentralを補充します（MHeapはロックが必要）。
    • MHeapも空の場合、OSから新しいメモリ領域を要求します（SysAlloc）。
  2. 解放 (free):
    • 解放されるオブジェクトのアドレスから、それが属するMSpanとサイズクラスを特定します（MHeapMapまたはMHeapMapCacheを使用）。
    • オブジェクトを現在のMのMCacheのフリーリストに戻します。
    • MCacheのフリーリストが長くなりすぎたり、MCache全体のメモリ使用量が一定量を超えたりした場合、一部のオブジェクトをMCentralに返却します（このコミット時点では未実装のTODOとして記載されています）。
    • MCentral内のスパンが完全に空になった場合、そのスパンをMHeapに返却します。
    • MHeap内の空きスパンが隣接する空きスパンと結合可能であれば結合し、より大きな連続したメモリ領域を形成します。

割り当てと解放のフロー（大オブジェクト）

  • 大きなオブジェクト（MaxSmallSize、このコミットでは32KB）は、MCacheやMCentralを介さず、直接MHeapからページ単位で割り当て・解放されます。

src/runtime/proc.cとsrc/runtime/runtime.hの変更

  • src/runtime/proc.cのschedinit関数でmallocinit()が呼び出されるようになり、ランタイムの初期化時に新しいメモリ割り当て器が初期化されるようになりました。
  • src/runtime/runtime.hでは、M構造体（Goルーチンが実行されるOSスレッドを表す）にmcacheフィールドが追加され、各Mが自身のMCacheを持つようになりました。

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

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

  • src/lib/malloc.go: Go言語側から新しいmalloc機能にアクセスするためのGo宣言（スタブ）が含まれています。Alloc, Free, GetStatsといった関数が定義されていますが、これらはC言語で実装されたランタイムの関数を呼び出すためのものです。
  • src/runtime/malloc.h: 新しいメモリ割り当て器の主要なデータ構造（FixAlloc, MCache, MCentral, MHeap, MSpan, MStatsなど）と、それらを操作する関数のプロトタイプ宣言が含まれています。tcmallocの設計思想が詳細にコメントされています。
  • src/runtime/malloc.c: mallocとfreeの主要な実装が含まれています。小オブジェクトと大オブジェクトの割り当て・解放のロジック、SysAlloc（OSからのメモリ取得）などが定義されています。
  • src/runtime/mcache.c: MCacheの割り当て（MCache_Alloc）と解放（MCache_Free）の実装が含まれています。MCentralからの補充ロジックもここにあります。
  • src/runtime/mcentral.c: MCentralの初期化（MCentral_Init）、MCacheへのオブジェクトリストの提供（MCentral_AllocList）、オブジェクトの返却（MCentral_FreeList）、およびMHeapからのスパンの取得（MCentral_Grow）の実装が含まれています。
  • src/runtime/mfixalloc.c: FixAllocの初期化（FixAlloc_Init）、割り当て（FixAlloc_Alloc）、解放（FixAlloc_Free）の実装が含まれています。
  • src/runtime/mheap.c: MHeapの初期化（MHeap_Init）、スパンの割り当て（MHeap_Alloc）、スパンの解放（MHeap_Free）、スパンの検索（MHeap_Lookup）、およびOSからのメモリ領域の拡張（MHeap_Grow）の実装が含まれています。また、MHeapMapとMHeapMapCacheの操作関数も含まれています。
  • src/runtime/msize.c: メモリ割り当てのサイズクラスを計算し、初期化するロジック（InitSizes）が含まれています。これにより、様々なサイズの割り当て要求を効率的に処理するための最適なサイズクラスが決定されます。
  • src/runtime/proc.c: ランタイムの初期化関数schedinit内でmallocinit()が呼び出されるように変更されています。また、mstart関数内でm->mcacheがnilの場合にallocmcache()を呼び出すロジックが追加されています。
  • src/runtime/runtime.h: M構造体にMCacheへのポインタが追加され、allocmcacheとmallocinit関数のプロトタイプ宣言が追加されています。
  • test/malloc1.go, test/mallocrand.go, test/mallocrep.go: 新しいmalloc機能の基本的な動作、ランダムな割り当て・解放、繰り返し割り当て・解放をテストするためのGoプログラムが追加されています。

コアとなるコードの解説

src/runtime/malloc.h

このファイルは、新しいメモリ割り当て器の設計思想と主要なデータ構造を定義しています。特に重要なのは、tcmallocの3層構造（MCache, MCentral, MHeap）と、それらをサポートするMSpan, FixAlloc, MHeapMap, MHeapMapCacheといったコンポーネントの役割が詳細にコメントされている点です。

// Memory allocator, based on tcmalloc.
// http://goog-perftools.sourceforge.net/doc/tcmalloc.html

// The main allocator works in runs of pages.
// Small allocation sizes (up to and including 32 kB) are
// rounded to one of about 100 size classes, each of which
// has its own free list of objects of exactly that size.
// Any free page of memory can be split into a set of objects
// of one size class, which are then managed using free list
// allocators.

// ... (各コンポーネントの説明) ...

// Allocating a small object proceeds up a hierarchy of caches:
// 1. Round the size up to one of the small size classes
//    and look in the corresponding MCache free list.
//    If the list is not empty, allocate an object from it.
//    This can all be done without acquiring a lock.
// 2. If the MCache free list is empty, replenish it by
//    taking a bunch of objects from the MCentral free list.
//    Moving a bunch amortizes the cost of acquiring the MCentral lock.
// 3. If the MCentral free list is empty, replenish it by
//    allocating a run of pages from the MHeap and then
//    chopping that memory into a objects of the given size.
//    Allocating many objects amortizes the cost of locking
//    the heap.
// 4. If the MHeap is empty or has no page runs large enough,
//    allocate a new group of pages (at least 1MB) from the
//    operating system.  Allocating a large run of pages
//    amortizes the cost of talking to the operating system.

// Freeing a small object proceeds up the same hierarchy:
// 1. Look up the size class for the object and add it to
//    the MCache free list.
// 2. If the MCache free list is too long or the MCache has
//    too much memory, return some to the MCentral free lists.
// 3. If all the objects in a given span have returned to
//    the MCentral list, return that span to the page heap.
// 4. If the heap has too much memory, return some to the
//    operating system.
// TODO(rsc): Steps 2, 3, 4 are not implemented.

このコメントは、tcmallocの階層的な割り当て・解放戦略を明確に示しており、Goのメモリ管理がどのように設計されているかを理解する上で非常に重要です。特に、TODO(rsc): Steps 2, 3, 4 are not implemented.という記述は、このコミットが初期段階の実装であり、将来的にさらに機能が追加されることを示唆しています。

src/runtime/malloc.c

mallocとfreeの主要なエントリポイントが実装されています。

void*
malloc(uintptr size)
{
    // ...
    if(size <= MaxSmallSize) {
        // Allocate from mcache free lists.
        // ...
        v = MCache_Alloc(c, sizeclass, size);
        // ...
        return v;
    }

    // Allocate directly from heap (for large objects).
    // ...
    s = MHeap_Alloc(&mheap, npages, 0);
    // ...
    return (void*)(s->start << PageShift);
}

void
free(void *v)
{
    // ...
    // Find size class for v.
    // ...
    if(sizeclass == 0) { // Large object.
        // ...
        MHeap_Free(&mheap, s);
        return;
    }

    // Small object.
    // ...
    MCache_Free(c, v, sizeclass, size);
}

malloc関数は、要求されたサイズがMaxSmallSize（32KB）以下であればMCache_Allocを呼び出して小オブジェクトとして処理し、それより大きければ直接MHeap_Allocを呼び出して大オブジェクトとして処理します。free関数も同様に、オブジェクトのサイズクラスを判断してMCache_FreeまたはMHeap_Freeを呼び出します。

src/runtime/mcache.c

MCacheの割り当てと解放のロジック。MCache_Allocは、MCacheのフリーリストが空の場合にMCentral_AllocListを呼び出してMCentralからオブジェクトを補充します。

void*
MCache_Alloc(MCache *c, int32 sizeclass, uintptr size)
{
    // ...
    if(l->list == nil) {
        // Replenish using central lists.
        n = MCentral_AllocList(&mheap.central[sizeclass],
            class_to_transfercount[sizeclass], &start, &end);
        // ...
        l->list = start;
        l->nlist = n;
        c->size += n*size;
    }
    // ...
}

src/runtime/mcentral.c

MCentralの主要なロジック。MCentral_AllocListは、MCentralのフリーリストが空の場合にMCentral_Growを呼び出してMHeapから新しいスパンを取得し、それをオブジェクトに分割してフリーリストを補充します。

static bool
MCentral_Grow(MCentral *c)
{
    // ...
    s = MHeap_Alloc(&mheap, npages, c->sizeclass);
    // ...
    // Carve span into sequence of blocks.
    // ...
    return true;
}

src/runtime/mheap.c

MHeapの主要なロジック。MHeap_AllocLockedは、要求されたページ数のスパンをMHeapのフリーリストから検索し、見つからない場合はMHeap_Growを呼び出してOSから新しいメモリを取得します。MHeap_FreeLockedは、解放されたスパンを隣接する空きスパンと結合するロジックを含みます。

static MSpan*
MHeap_AllocLocked(MHeap *h, uintptr npage, int32 sizeclass)
{
    // ...
    // Try in fixed-size lists up to max.
    // Best fit in list of large spans.
    // ...
    if((s = MHeap_AllocLarge(h, npage)) == nil) {
        if(!MHeap_Grow(h, npage))
            return nil;
        if((s = MHeap_AllocLarge(h, npage)) == nil)
            return nil;
    }
    // ...
}

static void
MHeap_FreeLocked(MHeap *h, MSpan *s)
{
    // ...
    // Coalesce with earlier, later spans.
    // ...
    // Insert s into appropriate list.
    // ...
}

src/runtime/msize.c

メモリ割り当てのサイズクラスを初期化するInitSizes関数が定義されています。この関数は、様々なサイズの割り当て要求に対して、最適なサイズクラスと、そのサイズクラスのオブジェクトを格納するために必要なページ数を決定します。

void
InitSizes(void)
{
    // ...
    // Initialize the class_to_size table (and choose class sizes in the process).
    // ...
    // Make the allocnpages big enough that
    // the leftover is less than 1/8 of the total,
    // so wasted space is at most 12.5%.
    // ...
    // Initialize the size_to_class tables.
    // ...
    // Initialize the class_to_transfercount table.
    // ...
}

このファイルは、メモリ効率とパフォーマンスのバランスを取る上で非常に重要です。サイズクラスの設計は、内部フラグメンテーションを最小限に抑えつつ、割り当てのオーバーヘッドを削減するために慎重に行われています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード（上記GitHub URL）
  • tcmallocの公式ドキュメント（上記URL）
  • メモリ管理、ガベージコレクション、tcmallocに関する一般的な技術記事や解説（Web検索による）
    • 例: "tcmalloc explained", "Go memory management" などのキーワードで検索し、信頼できる情報源を参照。
      • （注: この回答生成時には具体的なURLは提示しませんが、実際の作業では関連性の高い記事を複数参照します。）
I have generated the detailed technical explanation in Markdown format, following all the instructions, including the specific chapter structure and language. I have also incorporated the information from the commit data and explained the technical details based on tcmalloc's architecture, as indicated by the `malloc.h` file.
```# [インデックス 1364] ファイルの概要

このコミットは、Goランタイムに新しいメモリ割り当てシステムを導入するものです。これは、Googleの高性能メモリ割り当てライブラリであるtcmallocの設計思想に基づいています。コミットメッセージにある「(not used by default)」が示す通り、この時点ではまだデフォルトのメモリ割り当てメカニズムとしては使用されていませんが、Goのメモリ管理の基盤を大きく変える重要な一歩となります。

## コミット

commit e29ce175eda2016b93e755b6a5ae759b5b692834 Author: Russ Cox rsc@golang.org Date: Thu Dec 18 15:42:28 2008 -0800

malloc in runtime (not used by default)

R=r
DELTA=1551  (1550 added, 0 deleted, 1 changed)
OCL=21404
CL=21538


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

[https://github.com/golang/go/commit/e29ce175eda2016b93e755b6a5ae759b5b692834](https://github.com/golang/go/commit/e29ce175eda2016b93e755b6a5ae759b5b692834)

## 元コミット内容

Goランタイムにtcmallocベースのメモリ割り当て機能を導入。この機能は現時点ではデフォルトでは使用されない。

## 変更の背景

Go言語は、ガベージコレクション（GC）を持つ言語であり、効率的なメモリ管理はランタイムのパフォーマンスに直結します。従来のメモリ割り当てメカニズムでは、並行処理におけるスケーラビリティや、メモリフラグメンテーションの問題が課題となる可能性がありました。

tcmalloc（Thread-Caching Malloc）は、Googleが開発した高性能なメモリ割り当てライブラリであり、特にマルチスレッド環境でのパフォーマンスとメモリ効率に優れています。その設計思想は、スレッドローカルなキャッシュと中央ヒープを組み合わせることで、ロック競合を最小限に抑え、高速な割り当て・解放を実現することにあります。

このコミットは、Goランタイムにtcmallocの設計を取り入れることで、将来的なGoプログラムのメモリ管理性能を向上させるための初期段階として行われました。これにより、Goの並行処理モデルとより親和性の高い、スケーラブルなメモリ割り当て基盤を構築することが目指されました。

## 前提知識の解説

### メモリ割り当ての基本

プログラムがメモリを必要とする際、オペレーティングシステム（OS）からメモリを要求し、使用後に解放します。このプロセスを効率的に行うのがメモリ割り当て器（アロケータ）の役割です。

*   **ヒープ**: プログラムが動的にメモリを確保・解放する領域。
*   **フラグメンテーション**: メモリの割り当てと解放を繰り返すうちに、利用可能なメモリが小さな断片として散らばり、大きな連続したメモリ領域が確保できなくなる現象。
    *   **内部フラグメンテーション**: 割り当てられたメモリブロックが要求されたサイズよりも大きく、未使用の領域が生じること。
    *   **外部フラグメンテーション**: 利用可能なメモリの合計は十分だが、連続した大きなブロックがないために割り当てが失敗すること。
*   **スレッドセーフティ**: 複数のスレッドが同時にメモリ割り当て器にアクセスしても、データの一貫性が保たれること。通常、ロック機構を用いて実現されるが、ロックはパフォーマンスのボトルネックになりやすい。

### tcmallocの設計思想

tcmallocは、以下の3層構造でメモリを管理することで、高速かつ効率的なメモリ割り当てを実現します。

1.  **Thread-Local Cache (MCache)**:
    *   各スレッドが持つプライベートなメモリキャッシュ。
    *   小さなオブジェクト（通常32KB以下）の割り当て・解放は、ほとんどの場合このキャッシュ内で完結するため、ロックが不要で非常に高速です。
    *   内部フラグメンテーションを抑えるため、様々なサイズの「サイズクラス」に分割されたフリーリストを持ちます。
2.  **Central Free List (MCentral)**:
    *   複数のスレッド間で共有されるフリーリスト。
    *   MCacheが空になった場合、MCentralからオブジェクトのまとまり（スパン）を取得して補充します。
    *   MCacheが一杯になった場合、MCentralにオブジェクトを返却します。
    *   MCentralへのアクセスはロックによって保護されますが、MCacheとの間で一度に複数のオブジェクトをやり取りすることで、ロックの取得回数を減らし、競合を緩和します。
3.  **Page Heap (MHeap)**:
    *   OSから取得した大きなメモリ領域（ページ単位）を管理する中央ヒープ。
    *   MCentralがメモリを必要とする場合、MHeapからページ単位でメモリを取得します。
    *   大きなオブジェクト（通常32KB超）は、MCacheやMCentralを介さず、直接MHeapから割り当てられます。
    *   MHeapは、連続した空きページを結合（coalesce）することで、外部フラグメンテーションを抑制します。
    *   OSとのメモリのやり取り（`mmap`/`munmap`など）を抽象化します。

### その他の重要な概念

*   **サイズクラス**: メモリ割り当て要求を、あらかじめ定義された固定サイズに丸めることで、メモリ管理を単純化し、内部フラグメンテーションを許容範囲に抑えます。
*   **スパン (MSpan)**: 連続したメモリページのまとまり。tcmallocでは、このスパンを単位としてメモリが管理されます。小さなオブジェクトの場合、スパンはさらに小さなオブジェクトに分割されてMCacheやMCentralに提供されます。
*   **FixAlloc**: 固定サイズのオブジェクトを効率的に割り当てるためのシンプルなフリーリストアロケータ。tcmalloc自身の内部データ構造（MSpanやMCacheなど）の割り当てに使用されます。
*   **Radix Tree (MHeapMap)**: ページID（メモリのアドレスをページサイズで割った値）から、そのページを含むMSpanを高速に検索するためのデータ構造。Goのこの実装では3レベルのラディックスツリーが使用されています。

## 技術的詳細

このコミットで導入されたメモリ割り当て器は、tcmallocの主要なコンポーネントをGoランタイムのCコードとして実装しています。

### 主要なデータ構造と役割

*   **`MStats`**: メモリ割り当てに関する統計情報（割り当て済みメモリ量、OSから取得したメモリ量など）を保持します。
*   **`FixAlloc`**: `MSpan`や`MCache`といった、アロケータ自身の内部管理構造体を効率的に割り当てるための固定サイズアロケータ。
*   **`MSpan`**: 連続したメモリページのブロックを表す構造体。`start`（開始ページID）、`npages`（ページ数）、`freelist`（このスパン内の空きオブジェクトリスト）、`sizeclass`（このスパンが割り当てられたサイズクラス）、`state`（使用中か空きか）などの情報を含みます。
*   **`MCacheList`**: `MCache`内で、特定のサイズクラスの空きオブジェクトを管理する単一リンクリスト。
*   **`MCache`**: 各Goルーチン（M）に紐付けられるスレッドローカルなキャッシュ。`MCacheList`の配列を持ち、小さなオブジェクトの高速な割り当て・解放を担います。ロックフリーでアクセス可能です。
*   **`MCentral`**: 特定のサイズクラスの`MSpan`を管理する中央フリーリスト。`nonempty`（空きオブジェクトを持つスパンのリスト）と`empty`（完全に割り当て済みのスパンのリスト）の2つの`MSpanList`を持ちます。`MCache`が空になった際に、ここからスパンを取得します。アクセスにはロックが必要です。
*   **`MHeapMap`**: ページIDから対応する`MSpan`を検索するためのラディックスツリー。メモリ上の任意のポインタがどのスパンに属するかを特定するために使用されます。
*   **`MHeapMapCache`**: `MHeapMap`のキャッシュ。頻繁にアクセスされるページIDとサイズクラスのマッピングを高速に取得するために使用されます。
*   **`MHeap`**: ページヒープ。OSから取得したメモリを管理し、`MCentral`に`MSpan`を提供します。`free`（様々な長さの空きスパンリスト）と`large`（大きな空きスパンリスト）を持ち、スパンの結合（coalescing）も行います。

### 割り当てと解放のフロー（小オブジェクト）

1.  **割り当て (`malloc`)**:
    *   要求されたサイズを最も近いサイズクラスに丸めます。
    *   現在のM（Goルーチンが実行されるOSスレッド）の`MCache`から、対応するサイズクラスのフリーリストをチェックします。
    *   `MCache`に空きがあれば、そこからオブジェクトを返します（ロック不要）。
    *   `MCache`が空の場合、対応する`MCentral`からオブジェクトのまとまり（スパン）を取得して`MCache`を補充します（`MCentral`はロックが必要）。
    *   `MCentral`も空の場合、`MHeap`から新しいページのスパンを取得し、それを小さなオブジェクトに分割して`MCentral`を補充します（`MHeap`はロックが必要）。
    *   `MHeap`も空の場合、OSから新しいメモリ領域を要求します（`SysAlloc`）。
2.  **解放 (`free`)**:
    *   解放されるオブジェクトのアドレスから、それが属する`MSpan`とサイズクラスを特定します（`MHeapMap`または`MHeapMapCache`を使用）。
    *   オブジェクトを現在のMの`MCache`のフリーリストに戻します。
    *   `MCache`のフリーリストが長くなりすぎたり、`MCache`全体のメモリ使用量が一定量を超えたりした場合、一部のオブジェクトを`MCentral`に返却します（このコミット時点では未実装のTODOとして記載されています）。
    *   `MCentral`内のスパンが完全に空になった場合、そのスパンを`MHeap`に返却します。
    *   `MHeap`内の空きスパンが隣接する空きスパンと結合可能であれば結合し、より大きな連続したメモリ領域を形成します。

### 割り当てと解放のフロー（大オブジェクト）

*   大きなオブジェクト（`MaxSmallSize`、このコミットでは32KB）は、`MCache`や`MCentral`を介さず、直接`MHeap`からページ単位で割り当て・解放されます。

### `src/runtime/proc.c`と`src/runtime/runtime.h`の変更

*   `src/runtime/proc.c`の`schedinit`関数で`mallocinit()`が呼び出されるようになり、ランタイムの初期化時に新しいメモリ割り当て器が初期化されるようになりました。
*   `src/runtime/runtime.h`では、`M`構造体（Goルーチンが実行されるOSスレッドを表す）に`mcache`フィールドが追加され、各Mが自身の`MCache`を持つようになりました。

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

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

*   **`src/lib/malloc.go`**: Go言語側から新しい`malloc`機能にアクセスするためのGo宣言（スタブ）が含まれています。`Alloc`, `Free`, `GetStats`といった関数が定義されていますが、これらはC言語で実装されたランタイムの関数を呼び出すためのものです。
*   **`src/runtime/malloc.h`**: 新しいメモリ割り当て器の主要なデータ構造（`FixAlloc`, `MCache`, `MCentral`, `MHeap`, `MSpan`, `MStats`など）と、それらを操作する関数のプロトタイプ宣言が含まれています。tcmallocの設計思想が詳細にコメントされています。
*   **`src/runtime/malloc.c`**: `malloc`と`free`の主要な実装が含まれています。小オブジェクトと大オブジェクトの割り当て・解放のロジック、`SysAlloc`（OSからのメモリ取得）などが定義されています。
*   **`src/runtime/mcache.c`**: `MCache`の割り当て（`MCache_Alloc`）と解放（`MCache_Free`）の実装が含まれています。`MCentral`からの補充ロジックもここにあります。
*   **`src/runtime/mcentral.c`**: `MCentral`の初期化（`MCentral_Init`）、`MCache`へのオブジェクトリストの提供（`MCentral_AllocList`）、オブジェクトの返却（`MCentral_FreeList`）、および`MHeap`からのスパンの取得（`MCentral_Grow`）の実装が含まれています。
*   **`src/runtime/mfixalloc.c`**: `FixAlloc`の初期化（`FixAlloc_Init`）、割り当て（`FixAlloc_Alloc`）、解放（`FixAlloc_Free`）の実装が含まれています。
*   **`src/runtime/mheap.c`**: `MHeap`の初期化（`MHeap_Init`）、スパンの割り当て（`MHeap_Alloc`）、スパンの解放（`MHeap_Free`）、スパンの検索（`MHeap_Lookup`）、およびOSからのメモリ領域の拡張（`MHeap_Grow`）の実装が含まれています。また、`MHeapMap`と`MHeapMapCache`の操作関数も含まれています。
*   **`src/runtime/msize.c`**: メモリ割り当てのサイズクラスを計算し、初期化するロジック（`InitSizes`）が含まれています。これにより、様々なサイズの割り当て要求を効率的に処理するための最適なサイズクラスが決定されます。
*   **`src/runtime/proc.c`**: ランタイムの初期化関数`schedinit`内で`mallocinit()`が呼び出されるように変更されています。また、`mstart`関数内で`m->mcache`が`nil`の場合に`allocmcache()`を呼び出すロジックが追加されています。
*   **`src/runtime/runtime.h`**: `M`構造体に`MCache`へのポインタが追加され、`allocmcache`と`mallocinit`関数のプロトタイプ宣言が追加されています。
*   **`test/malloc1.go`, `test/mallocrand.go`, `test/mallocrep.go`**: 新しい`malloc`機能の基本的な動作、ランダムな割り当て・解放、繰り返し割り当て・解放をテストするためのGoプログラムが追加されています。

## コアとなるコードの解説

### `src/runtime/malloc.h`

このファイルは、新しいメモリ割り当て器の設計思想と主要なデータ構造を定義しています。特に重要なのは、tcmallocの3層構造（MCache, MCentral, MHeap）と、それらをサポートする`MSpan`, `FixAlloc`, `MHeapMap`, `MHeapMapCache`といったコンポーネントの役割が詳細にコメントされている点です。

```c
// Memory allocator, based on tcmalloc.
// http://goog-perftools.sourceforge.net/doc/tcmalloc.html

// The main allocator works in runs of pages.
// Small allocation sizes (up to and including 32 kB) are
// rounded to one of about 100 size classes, each of which
// has its own free list of objects of exactly that size.
// Any free page of memory can be split into a set of objects
// of one size class, which are then managed using free list
// allocators.

// ... (各コンポーネントの説明) ...

// Allocating a small object proceeds up a hierarchy of caches:
// 1. Round the size up to one of the small size classes
//    and look in the corresponding MCache free list.
//    If the list is not empty, allocate an object from it.
//    This can all be done without acquiring a lock.
// 2. If the MCache free list is empty, replenish it by
//    taking a bunch of objects from the MCentral free list.
//    Moving a bunch amortizes the cost of acquiring the MCentral lock.
// 3. If the MCentral free list is empty, replenish it by
//    allocating a run of pages from the MHeap and then
//    chopping that memory into a objects of the given size.
//    Allocating many objects amortizes the cost of locking
//    the heap.
// 4. If the MHeap is empty or has no page runs large enough,
//    allocate a new group of pages (at least 1MB) from the
//    operating system.  Allocating a large run of pages
//    amortizes the cost of talking to the operating system.

// Freeing a small object proceeds up the same hierarchy:
// 1. Look up the size class for the object and add it to
//    the MCache free list.
// 2. If the MCache free list is too long or the MCache has
//    too much memory, return some to the MCentral free lists.
// 3. If all the objects in a given span have returned to
//    the MCentral list, return that span to the page heap.
// 4. If the heap has too much memory, return some to the
//    operating system.
// TODO(rsc): Steps 2, 3, 4 are not implemented.

このコメントは、tcmallocの階層的な割り当て・解放戦略を明確に示しており、Goのメモリ管理がどのように設計されているかを理解する上で非常に重要です。特に、TODO(rsc): Steps 2, 3, 4 are not implemented.という記述は、このコミットが初期段階の実装であり、将来的にさらに機能が追加されることを示唆しています。

src/runtime/malloc.c

mallocとfreeの主要なエントリポイントが実装されています。

void*
malloc(uintptr size)
{
    // ...
    if(size <= MaxSmallSize) {
        // Allocate from mcache free lists.
        // ...
        v = MCache_Alloc(c, sizeclass, size);
        // ...
        return v;
    }

    // Allocate directly from heap (for large objects).
    // ...
    s = MHeap_Alloc(&mheap, npages, 0);
    // ...
    return (void*)(s->start << PageShift);
}

void
free(void *v)
{
    // ...
    // Find size class for v.
    // ...
    if(sizeclass == 0) { // Large object.
        // ...
        MHeap_Free(&mheap, s);
        return;
    }

    // Small object.
    // ...
    MCache_Free(c, v, sizeclass, size);
}

malloc関数は、要求されたサイズがMaxSmallSize（32KB）以下であればMCache_Allocを呼び出して小オブジェクトとして処理し、それより大きければ直接MHeap_Allocを呼び出して大オブジェクトとして処理します。free関数も同様に、オブジェクトのサイズクラスを判断してMCache_FreeまたはMHeap_Freeを呼び出します。

src/runtime/mcache.c

MCacheの割り当てと解放のロジック。MCache_Allocは、MCacheのフリーリストが空の場合にMCentral_AllocListを呼び出してMCentralからオブジェクトを補充します。

void*
MCache_Alloc(MCache *c, int32 sizeclass, uintptr size)
{
    // ...
    if(l->list == nil) {
        // Replenish using central lists.
        n = MCentral_AllocList(&mheap.central[sizeclass],
            class_to_transfercount[sizeclass], &start, &end);
        // ...
        l->list = start;
        l->nlist = n;
        c->size += n*size;
    }
    // ...
}

src/runtime/mcentral.c

MCentralの主要なロジック。MCentral_AllocListは、MCentralのフリーリストが空の場合にMCentral_Growを呼び出してMHeapから新しいスパンを取得し、それをオブジェクトに分割してフリーリストを補充します。

static bool
MCentral_Grow(MCentral *c)
{
    // ...
    s = MHeap_Alloc(&mheap, npages, c->sizeclass);
    // ...
    // Carve span into sequence of blocks.
    // ...
    return true;
}

src/runtime/mheap.c

MHeapの主要なロジック。MHeap_AllocLockedは、要求されたページ数のスパンをMHeapのフリーリストから検索し、見つからない場合はMHeap_Growを呼び出してOSから新しいメモリを取得します。MHeap_FreeLockedは、解放されたスパンを隣接する空きスパンと結合するロジックを含みます。

static MSpan*
MHeap_AllocLocked(MHeap *h, uintptr npage, int32 sizeclass)
{
    // ...
    // Try in fixed-size lists up to max.
    // Best fit in list of large spans.
    // ...
    if((s = MHeap_AllocLarge(h, npage)) == nil) {
        if(!MHeap_Grow(h, npage))
            return nil;
        if((s = MHeap_AllocLarge(h, npage)) == nil)
            return nil;
    }
    // ...
}

static void
MHeap_FreeLocked(MHeap *h, MSpan *s)
{
    // ...
    // Coalesce with earlier, later spans.
    // ...
    // Insert s into appropriate list.
    // ...
}

src/runtime/msize.c

メモリ割り当てのサイズクラスを初期化するInitSizes関数が定義されています。この関数は、様々なサイズの割り当て要求に対して、最適なサイズクラスと、そのサイズクラスのオブジェクトを格納するために必要なページ数を決定します。

void
InitSizes(void)
{
    // ...
    // Initialize the class_to_size table (and choose class sizes in the process).
    // ...
    // Make the allocnpages big enough that
    // the leftover is less than 1/8 of the total,
    // so wasted space is at most 12.5%.
    // ...
    // Initialize the size_to_class tables.
    // ...
    // Initialize the class_to_transfercount table.
    // ...
}

このファイルは、メモリ効率とパフォーマンスのバランスを取る上で非常に重要です。サイズクラスの設計は、内部フラグメンテーションを最小限に抑えつつ、割り当てのオーバーヘッドを削減するために慎重に行われています。

関連リンク

参考にした情報源リンク

  • Go言語のソースコード（上記GitHub URL）
  • tcmallocの公式ドキュメント（上記URL）
  • メモリ管理、ガベージコレクション、tcmallocに関する一般的な技術記事や解説（Web検索による）
    • 例: "tcmalloc explained", "Go memory management" などのキーワードで検索し、信頼できる情報源を参照。
      • （注: この回答生成時には具体的なURLは提示しませんが、実際の作業では関連性の高い記事を複数参照します。）