🐥

神話のプログラム言語 Odin 集中型メモリ管理システム編

2024/10/16に公開

まず初めに、前回の記事神話のプログラム言語 Odin(これであなたも厨二病)を見て頂いて、ありがとうございます。私の記事が日に1000閲覧以上も見て貰えたのは初めてです。いつも毎日10閲覧未満でした。(笑)
※タイトルがネタ的なのが、うけたのかな?(笑)

今回はOdinの集中型メモリ管理システムについて、説明していきます。

【集中型メモリ管理システムについて、神からのお告げがありました】

神はおっしゃいました!!、現代のコンピュータシステムには、ヒープもスタックも関係ないんだよ!、最新のオペレーティングシステムは、プロセスごとにメモリを仮想化しているから、こんな二元管理は不要なんだよ!と言っています。
gingerBill氏のメモリ戦略
全てのメモリは一つの線形リストで管理すべきなんだよ!と、神のお告げを賜りました。

OdinのCMM:(集中メモリ管理システム)は、この言葉からきている物です。
これを実現したのが、アリーナアロケータと言うメモリ管理です。Zigのメモリ管理も基本的に同じです。
従来の言語は、いくつものメモリを確保した場合、チマチマと一つ一つのメモリを解放しなければいけなかったのですが、Odinでは、アリーナバッファを最初にドーンと確保し、一括でメモリを解放すると言う仕組みです。メモリを一元管理する事で、プログラム内のメモリの追跡や、使用メモリ数を制限できると言う利点があります。

その為にも、Odinでは下記のような暗黙のContextと言う管理用グローバルエリアを設けています。
暗黙のContextに一度設定すれば、後は、全ての関数で同じメモリエリアが使われます。
Zigには、暗黙のContextと言うような管理用エリアが無いため、使用する時に呼び出さないといけないらしい。(Zigを詳しく知らないですが、そう誰かが言ってました。)

暗黙のContext(自動的に付与されるグローバルstaticエリア)
Context :: struct {
	allocator:              Allocator,
	temp_allocator:         Allocator,
	assertion_failure_proc: Assertion_Failure_Proc,
	logger:                 Logger,
	random_generator:       Random_Generator,

	user_ptr:   rawptr,
	user_index: int,

	// Internal use only
	_internal: rawptr,
}

暗黙のContext内のメモリの管理では、永続的なメモリ管理と一時的なテンポラリのメモリ管理の二つが存在します。それ以外にログの管理とユーザ管理(thread時の自身の管理かな?だと思います)も存在します。

メモリ管理

Odinではメモリを管理する構造体として、以下の4つが存在します。(まだ後2つあるんですけど、私自身、使用用途がイマイチわかっていません。)

  • mem.Allocator (構造体名称)
    通常、odinプログラムが起動時は、暗黙のContextに使われる。これはバッファの管理は行わないので、サイズ制限はない。その代わり、freeとdeleteを使って、一つ一つメモリ解放を行わないといけない。
  • mem.Tracking_Allocator (構造体名称)
    メモリ追跡時に使われる。
  • mem.Arena (構造体名称)
    アリーナアロケータ:アリーナバッファを設置して利用される。
  • virtual.Arena (構造体名称)
    仮想メモリアロケータは上記のアリーナアロケータと較べて柔軟性が高いです。以下の3つの利用方法を行う事が出来ます。
    • arena_init_buffer:アリーナアロケータと同様でユーザがバッファを設定し、利用する方法
    • arena_init_growing:システムが仮想バッファを自動で用意し、利用する方法
    • arena_init_static:システムが1Gバイトのスタックエリアを用意し、利用する方法

Odinでは、メモリ確保にはnewとmakeの関数が存在します。どちらも同じなのですが、newとfreeは対で、且つ、makeとdeleteは対で使用しなければ、実行時にエラーになります。

newとmakeの説明
int_ptr := new([10]int)  // newで確保したら、free関数で解放する
defer free(int_ptr)

int_ptr := make([dynamic]int, 10)  // makeで確保したら、delete関数で解放する
defer delete(int_ptr)

1.トラッキングアロケータ

Odinでメモリ追跡処理のトラッキングアロケータを作成します。
プロジェクト直下に、「tracking_alloccator」ディレクトリを作成し、以下の様にmain.odinファイルを作成します。

tracking_alloccator/main.nim
/* ===========================
    Odinプログラム トラッキングアロケータ
   =========================== */
package main

import "core:fmt"
import "core:mem"

main :: proc() {
  // トラッキングアロケータの設定(以下の3行を追記するだけ)
  track: mem.Tracking_Allocator
  mem.tracking_allocator_init(&track, context.allocator)
  context.allocator = mem.tracking_allocator(&track)  // contextに設定する事で、全ての処理のアロケートを追跡可能

  defer { // 処理終了時に、メモリの未開放と2度解放したメモリを抽出
    if len(track.allocation_map) > 0 {
      fmt.eprintf("=== total alloc size %v byte\n", track.total_memory_allocated)
      fmt.eprintf("=== %v allocations not freed: ===\n", len(track.allocation_map))
      for _, entry in track.allocation_map {
        fmt.eprintf("- %v bytes @ %v\n", entry.size, entry.location)
      }
    }
    if len(track.bad_free_array) > 0 {
      fmt.eprintf("=== total free size %v byte\n", track.total_memory_freed)
      fmt.eprintf("=== %v incorrect frees: ===\n", len(track.bad_free_array))
      for entry in track.bad_free_array {
        fmt.eprintf("- %p @ %v\n", entry.memory, entry.location)
      }
    }
    mem.tracking_allocator_destroy(&track)
  }

  malloc_test()   // 下位の関数でメモリ取得処理
}

// 下位の関数でメモリ取得チェック処理
malloc_test :: proc() {
  int_ptr := new(int)        // 8byte   メモリの解放をした
  long_ptr := new(i128)      // 16byte  メモリ解放していない
  int_ptr2 := new([10]int)   // 80byte  メモリ解放していない
  long_ptr2 := new([10]i128) // 160byte メモリの解放をした
                             // メモリ確保のトータル数:264byte取得
  free(int_ptr)              // 8byte
  free(int_ptr)              // 0byte 同一のメモリを解放失敗した
  free(long_ptr2)            // 160byte 
                             // メモリ解放のトータル数:168byte解放
}

context.allocatorに、mem.Tracking_Allocatorを設定する事で、プログラム内の全ての関数で使用したメモリの未開放行と二重解放して失敗した行を追跡できる。
上記プログラムは、ソース自体複雑に見えますが、上記3行だけで、トラッキングアロケータの設定を行って、処理終了時のdeferで、追跡結果を表示してるだけ。(つまりは、コピペすれば、どこでも使えます)
ちなみに、context.allocatorに設定できるアロケータの種類は4つ以上ありますが、context.allocatorは一つなので、併用する事は出来ません。
なので、トラッキングアロケータはデバック時のみ使われる物だと思ってください。

$ odin run .\tracking_alloccator\
=== total alloc size 264 byte    ← メモリを確保したサイズ
=== 2 allocations not freed: ===
- 80 bytes @ E:/your_project/tracking_alloccator/main.odin(40:15)
- 16 bytes @ E:/your_project/tracking_alloccator/main.odin(39:15)
=== total free size 168 byte     ← メモリを解放したサイズ
=== 1 incorrect frees: ===
- 0x21E131ECE08 @ E:/your_project/tracking_alloccator/main.odin(44:3)

実行結果は、alloc数が264バイト、free数が168バイトと結果が出ています。(本来ならfree数も264バイトになるところが、一致していません)
39行目のlong_ptr変数をfreeし忘れているので、エラーが発生、40行目のint_ptr2変数をfreeし忘れているので、エラーが発生、44行目のint_ptr変数を二度解放しているので、エラーが発生と言う情報が出力されました。ここでは、long_ptr2変数だけ正常にメモリを確保解放されている事がわかります。

2.アリーナアロケータ

Odinでアリーナアロケータによるメモリ生成処理を説明します。
プロジェクト直下に、「arena_alloccator」ディレクトリを作成し、以下の様にmain.odinファイルを作成します。

arena_alloccator/main.nim
/* ===========================
    Odinプログラム アリーナアロケータ
   =========================== */
package main

import "core:fmt"
import "core:mem"

main :: proc() {
  default_context_allocator := context.allocator // 一時保存

  arena_buffer := make([dynamic]byte, 2_000)    // ヒープのアリーナバッファーを作成 2kByte
  arena: mem.Arena                              // アリーナアロケータを指定
  mem.arena_init(&arena, arena_buffer[:])       // アリーナアロケータにバッファーを設定
  arena_allocator := mem.arena_allocator(&arena)

  context.allocator = arena_allocator           // 暗黙のcontext一度設定すれば、下位に呼ばれる全ての関数はアリーナアロケータで制御される
  defer {
    free_all(arena_allocator)                   // メイン処理が終わった後に、メモリを一括解放出来る
    fmt.println("memory clear end.")            // 確保時にエラーが発生した時、panicで終了している為、メモリクリアはされない
  }

  malloc_test1(250)   // 250byteのメモリを5回取得
  // context.allocator = default_context_allocator  // アリーナアロケータからデフォルトに戻すと正常に終了する
  malloc_test2(250)   // 250byteのメモリを5回取得
}

// 下位の関数でメモリ取得処理
malloc_test1 :: proc(alloc_size: int) {
  arr: [5][dynamic]byte   // メモリを取得するエリア 二次元配列
  total: int              // メモリの取得トータルサイズ
  for i in 0 ..< 5 {
    // 上位で暗黙のcontextを設定しているため、アリーナアロケータでメモリを取得
    // makeは、メモリ取得エラーの場合、第二戻り値でエラーを返すため、or_elseでエラーを対処する
    arr[i] = make([dynamic]byte, alloc_size) or_else fmt.panicf("error: out of memory count=%v\n", i)
    total += cap(arr[i])   // キャパシティ数で動的獲得数が取得可能
    fmt.printf("malloc_test1 count=%v alloc total = %v\n", i, total)
  }
}

// 下位の関数でメモリ取得処理
malloc_test2 :: proc(alloc_size: int) {
  arr: [5][dynamic]byte   // メモリを取得するエリア 二次元配列
  total: int              // メモリの取得トータルサイズ
  for i in 0 ..< 5 {
    arr[i] = make([dynamic]byte, alloc_size) or_else fmt.panicf("error: out of memory count=%v\n", i)
    total += cap(arr[i])   // キャパシティ数で動的獲得数が取得可能
    fmt.printf("malloc_test2 count=%v alloc total = %v\n", i, total)
  }
}

ここでは、下位の関数(malloc_test1,malloc_test2)でメモリを確保しています。2つの関数はやってる事は同じで、全てbyte単位でメモリを確保しています。
メモリの解放は、メイン側でfree_all関数を使って一括でメモリを解放します。
ここでは、メモリ確保関数に、newではなく、makeを利用しています。この関数は戻り値に2つの値を返します。(一つ目は確保したバッファアドレス、二つ目は確保出来なかったエラー情報)。そのため、or_elseでエラー時の処理を行っています。

$ odin run .\arena_alloccator\
malloc_test1 count=0 alloc total = 250
malloc_test1 count=1 alloc total = 500
malloc_test1 count=2 alloc total = 750
malloc_test1 count=3 alloc total = 1000
malloc_test1 count=4 alloc total = 1250
malloc_test2 count=0 alloc total = 250
malloc_test2 count=1 alloc total = 500
malloc_test2 count=2 alloc total = 750
E:/your_project/arena_allocator/main.odin(48:54) Panic: error: out of memory count=3

アリーナバッファを2kバイト確保しているのですが、250バイトのメモリを合計10回確保するとエラーになります。当たり前ですが、2.5kバイトのメモリを確保しにいってるからです。

arena_alloccator/main.nimの部分修正
main :: proc() {
  ・・・main関数の最後3行から抜粋・・・
  malloc_test1(250)   // 250byteのメモリを5回取得
  context.allocator = default_context_allocator  // アリーナアロケータからデフォルトに戻すと正常に終了する
  malloc_test2(250)   // 250byteのメモリを5回取得
}

上記のようにmalloc_test2関数を呼び出す前に、暗黙のcontextをデフォルトに戻してやると、エラーは発生しません。但し、この場合、malloc_test1の関数だけしか、アリーナアロケータは制御していないと言う事になります。

または、malloc_test2関数にtemp_allocatorを使う

arena_alloccator/main.nimの部分修正
malloc_test2 :: proc(alloc_size: int) {
・・・malloc_test2関数のmake行から抜粋・・・

  defer free_all(context.temp_allocator)  // malloc_test2を抜ける時にtemp_allocatorのメモリを解放
  for i in 0 ..< 5 {
    arr[i] = make([dynamic]byte, alloc_size, context.temp_allocator) or_else fmt.panicf("error: out of memory count=%v\n", i)

・・・malloc_test2関数のmake行から抜粋・・・
  }
}

Odin内の標準関数では、バッファエリアを取得する関数は、大体がアロケータを引数に渡す事が出来ます。make関数もその一つで、temp_allocatorを渡す事で、今メインで使用しているアロケータと異なるバッファエリアを使います。temp_allocatorは一時的なメモリですので、関数内だけでメモリを確保する場合に利用します。
また、temp_allocatorはサイズ制限がありませんが、使い過ぎると、ガベージコレクションと何ら変わりが無くなってしまいますので、使い過ぎには注意が必要。
下位の関数内で処理が終了した時に、free_all(context.temp_allocator)をすれば、問題ありません。
基本、temp_allocatorは、ファイル読み込みで一時的にデータを確保しなければいけない時とか、関数内だけで一時的にバッファが必要な時のみに使われます。

3.仮想アリーナアロケータ

Odinで仮想アリーナアロケータによるメモリ生成処理を説明します。
プロジェクト直下に、「virtual_alloccator」ディレクトリを作成し、以下の様にmain.odinファイルを作成します。

virtual_alloccator/main.nim
/* ===========================
    Odinプログラム 仮想メモリ アリーナ アロケータ
   =========================== */
package main

import "core:fmt"
import "core:mem/virtual"     // 仮想メモリはcore:mem/virtualをimport

main :: proc() {
  default_context_allocator := context.allocator	// 一時保存

  arena_buffer := make([dynamic]byte, 2_000) // ヒープの仮想アリーナバッファーを作成 2kByte
  arena: virtual.Arena                       // 仮想メモリ アリーナを指定
  _ = virtual.arena_init_buffer(&arena, arena_buffer[:])  // 戻り値のエラー情報は無視する
  arena_allocator := virtual.arena_allocator(&arena)

  context.allocator = arena_allocator
  defer virtual.arena_free_all(&arena)      // 処理後に、一括でメモリー解放

  malloc_test1(250)   // 250byteのメモリを5回取得
  // context.allocator = default_context_allocator  // 仮想アリーナからデフォルトに戻すと正常に終了する
  malloc_test2(250)   // 250byteのメモリを5回取得
}

// 下位の関数でメモリ取得処理
malloc_test1 :: proc(alloc_size: int) {
  arr: [5][dynamic]byte   // メモリを取得するエリア 二次元配列
  total: int              // メモリの取得トータルサイズ
  for i in 0 ..< 5 {
    // 上位で暗黙のcontextを設定しているため、仮想メモリアリーナでメモリを取得
    // makeは、メモリ取得エラーの場合、第二戻り値でエラーを返すため、or_elseでエラーを対処する
    arr[i] = make([dynamic]byte, alloc_size) or_else fmt.panicf("error: out of memory count=%v\n", i)
    total += cap(arr[i])   // キャパシティ数で動的獲得数が取得可能
    fmt.printf("malloc_test1 count=%v alloc total = %v\n", i, total)
  }
}

// 下位の関数でメモリ取得処理
malloc_test2 :: proc(alloc_size: int) {
  arr: [5][dynamic]byte   // メモリを取得するエリア 二次元配列
  total: int              // メモリの取得トータルサイズ
  for i in 0 ..< 5 {
    arr[i] = make([dynamic]byte, alloc_size) or_else fmt.panicf("error: out of memory count=%v\n", i)
    total += cap(arr[i])   // キャパシティ数で動的獲得数が取得可能
    fmt.printf("malloc_test2 count=%v alloc total = %v\n", i, total)
  }
}

仮想アリーナアロケータは、3つの設定を行う事が出来ます。上記のソースは、アリーナアロケータと同様でユーザがバッファを設けて動作させています。それ以外に、無尽蔵にメモリを増やせる設定とシステムが1Gバイトのスタックバッファを設定して動作させるやり方が存在します。
また、通常のアリーナアロケータは、free_all関数でメモリを解放しますが、仮想アリーナアロケータは、virtual.arena_free_allでメモリを一括解放します。

$ odin run .\virtual_alloccator\
malloc_test1 count=0 alloc total = 250
malloc_test1 count=1 alloc total = 500
malloc_test1 count=2 alloc total = 750
malloc_test1 count=3 alloc total = 1000
malloc_test1 count=4 alloc total = 1250
malloc_test2 count=0 alloc total = 250
malloc_test2 count=1 alloc total = 500
E:/your_project/virtual_allocator/main.odin(53:54) Panic: error: out of memory count=2

allocする回数がアリーナアロケータに較べて、1つ少なくない?って思われると思います。
実は、仮想アリーナアロケータは、初期化した時に、40バイトバッファを使用するため、アリーナアロケータとallocする回数が異なるのです。本来なら、バッファサイズは2kバイトじゃなく2040バイト取るべきだったのでしょうね。

■arena_init_growingに変更(システムが自動で仮想エリアを増やす設定)

virtual_alloccator/main.nimの部分修正
・・・main関数のvirtual.Arena設定から抜粋・・・
  arena: virtual.Arena                       // 仮想メモリ アリーナを指定
  _ = virtual.arena_init_growing(&arena)     // システムが自動で仮想バッファを設定
  arena_allocator := virtual.arena_allocator(&arena)
・・・main関数のvirtual.Arena設定から抜粋・・・

自動で無尽蔵にバッファを増やせるため、Out of Memoryにはならない。

■arena_init_staticに変更(システムが自動で1Gバイトのスタックに設定)

virtual_alloccator/main.nimの部分修正
・・・main関数のvirtual.Arena設定から抜粋・・・
  arena: virtual.Arena                       // 仮想メモリ アリーナを指定
  _ = virtual.arena_init_static(&arena)      // システムが自動で1Gバイトのスタックを設定
  arena_allocator := virtual.arena_allocator(&arena)
・・・main関数のvirtual.Arena設定から抜粋・・・

malloc_test1とmalloc_test2のallocサイズを150Mバイトに変更しましょう。
malloc_test1(150_000_000)に変更すると、malloc_test2でOut of Memoryが発生します。
システムが用意した1Gバイトのスタックバッファを使い切ったためです。

4.カスタムアロケータ

Odinでカスタムアロケータによるメモリ生成処理を説明します。
プロジェクト直下に、「custum_allocator」ディレクトリを作成し、以下の様にmain.odinファイルを作成します。
アロケータを独自に作成するやり方です。
トラッキングアロケータじゃなく、常時プログラムが動作している時の、メモリー状況を見たいよね?って言う、奇特な方向けです。

custum_allocator/main.nim
/* ===========================
    Odinプログラム カスタムアロケータ
   =========================== */
package main

import "core:fmt"
import "core:mem"
import "core:mem/virtual"
import "core:os"

Allocator :: mem.Allocator
Allocator_Mode :: mem.Allocator_Mode
Allocator_Error :: mem.Allocator_Error

MyAllocatorData :: struct {
  allocator : Allocator,
}

my_allocator :: proc(my_allocator_data: ^MyAllocatorData) -> Allocator {
  return Allocator {
    procedure = my_allocator_proc,  // メモリ操作時に呼び出す関数を指定
    data = my_allocator_data,       // メモリ操作時のバッファー指定
  }
}

my_allocator_proc :: proc(allocator_data: rawptr, mode: Allocator_Mode, size, alignment: int,
                          old_memory: rawptr, old_size: int,
                          location := #caller_location) -> ([]byte, Allocator_Error) {

  allocator := (cast(^MyAllocatorData)allocator_data).allocator
  #partial switch mode {  // #partialはenum値の場合だけ使用可
    case .Alloc:          // メモリを取得した場合
      fmt.printf("Alloc size=%v (%v:%v)\n", size, location.procedure, location.line)
      return mem.alloc_bytes(size, alignment, allocator, location)
    case .Free:           // メモリを解放した場合
      fmt.printf("Free size=%v (%v:%v)\n", old_size, location.procedure, location.line)
      return nil, mem.free(cast(rawptr)old_memory, allocator, location)
  }
  os.exit(1)
}

main :: proc() {
  default_context_allocator := context.allocator	// 一時保存

  // カスタム アロケータ
  my_data := MyAllocatorData {allocator = context.allocator}	// 現在のcontextアロケータバッファー設定
  allocator := my_allocator(&my_data)
  context.allocator = allocator

  a := make([dynamic]byte, 320) or_else fmt.panicf("error: out of memory")
  defer delete(a)

  b := make([dynamic]byte, 1_000) or_else fmt.panicf("error: out of memory")
  defer delete(b)
}

独自にAllocatorを作成しなければいけないので、大概ややこしい処理になります。

$ odin run .\custum_allocator\
Alloc size=320 (main:49)
Alloc size=1000 (main:52)
Free size=1000 (main:53)
Free size=320 (main:50)

これなら常時動作している時のメモリ状況を見れますが、デバック用です。こういう事も出来ますよって言うサンプルです。

結論

トラッキング・アリーナ・仮想アリーナ・カスタムアロケータと色々説明してきましたが、柔軟性を考えるなら、仮想メモリアリーナを使うのが一番良いのかもしれません。
最初に仮想メモリアリーナでユーザがバッファサイズを設定し、メモリ問題が発生したら、サイズを増やして、メモリのサイズ要件が満たしたら、最後にarena_init_growingに変更(システムが自動で仮想エリアを設定)にすれば良いのかもしれません。

おわりに

今回は、Odinの集中型メモリ管理システムについて説明しました。アロケータについては、プログラム全体をアロケータで管理する場合もあれば、部分的に(例えばスレッド間で使用とか、メモリを多く確保しているモジュールだけ使用とか)使用する場合もあるかと思います。
難しく思われるかもしれませんが、メモリを一元管理していると言う意味では単純です。
今後のプログラム言語は、Raylib開発者がCentralized Memory Management言うように、集中型メモリ管理システムが主流になるのかもしれません。

Discussion