Effective Techniques in Swift Runtime Library

Swift言語のランタイムライブラリで使われているテクニックについて解説します。

ランタイムライブラリと実行可能ファイル

Swiftを実行するためにはswiftCoreというランタイムライブラリが必要です。意識することはあまりありませんが、静的もしくは動的に実行可能ファイルにリンクされています。

Swift 5.0からABI安定が達成されたことで、macOS 10.14.4以降は/usr/lib/swift/libswiftCore.dylibにランタイムライブラリがインストールされています。

SwiftのランタイムライブラリにはSwiftの動的な言語仕様をサポートするための関数が含まれています。

言語仕様の2つの側面

プログラミング言語の言語仕様を考えるとき、以下のような2つに分類できます。

静的な言語仕様
- 文法
- 型システム
動的な言語仕様
- 実行時型システム
- 例外ハンドリング
- バイナリ互換性

ここでは、動的な言語仕様というのは実行時に使われる言語仕様のことを指します。Swiftの言語機能の中では以下のようなものが例として挙げられます。

メモリ確保
ARC
実行時の型システム
動的キャスト

これらの言語機能は素朴なコンパイル時のコード生成ではコードサイズが肥大化してしまうため、ランタイムライブラリとして切り出されています。

メモリ確保

ランタイムライブラリの提供する言語機能の例としてメモリ確保の動きを見てみましょう。

Swiftの構造体のように、静的に型のサイズが決定できる場合、コンパイラはそのサイズを確保するようなコードを出力します。

この場合、pet変数はコンパイル時にPet型からインスタンスサイズを24byteに決定できます。

// 24 byte
struct Pet {
  let name: String // 16 byte
  let age: Int     // 8 byte
}

let pet = Pet(name: ..., age: ...) // malloc 24 byte

一方で型から静的にサイズを決定できないケースもあります。例えばSwiftのクラス継承による動的な型の決定を想像してみましょう。

// 8 byte
class View {
  var point: (x: Float, y: Float) // 8 byte
  required init(...) { }

  func copy() -> Self {
    return Self(...) // malloc n byte
  } 
}

// 24 byte
class TextView: View {
  var text: String // 16 byte
  required init(...) { }
}

let view: View = TextView(...)

// この時点でviewがTextViewであることを保証できない。
let anotherView: View = view.copy()

この例ではView型はcopyメソッドを実装しており、 Self型からインスタンスを生成します。 Self型はView型またはTextView型になり得ますが、コンパイラはどちらの型が実行時に使われるか静的に決定できません。

このような Selfを使ったコードを正しく実行するためには、実行時にインスタンスの本来の型情報をインスタンス自身が取り回さなければなりません。

Metadata

実行時に取り回される型情報をSwiftではType Metadataと呼びます。基本的にSwiftユーザーからは見えないようになっており、直接使うこともありません。

Type Metadataは型のサイズや動的なメソッド呼び出しのための関数テーブル、ジェネリック型パラメータのメタデータ、後述するType Descriptorへのポインタなどを保持しています。

ランタイムライブラリは主にMetadataを操作することで動的な言語機能を実装しています。メモリ確保の例では、インスタンスに埋め込まれたType Metadataを取り出してランタイム関数に引数として渡すことで、動的にインスタンスのサイズを決定できるようになっています。

Type Descriptorはジェネリックな型パラメータなどに影響されない、特定の型インスタンスから独立した情報のみを保持しています。また、リフレクションのための情報もここに含まれています。

ジェネリックな型のType Metadataは実際にその型が使われた実行時のタイミングで、型パラメータ毎それぞれ動的に作られるケースがあります。しかしType MetadataとType Descriptorの二段の構造を取ることで、常に同一のType Descriptorデータを使い回すことができ、メモリを節約しています。

テクニックの背景

データ構造について見ていく前に前提となる背景を軽く話します。

TEXTセグメント

まず、メタデータがどのようにバイナリに格納されているかについてです。

ここではmacOSで使われているMach-O形式について書きます。他のバイナリファイルフォーマットでもさほど変わりません。

基本的に実行可能ファイルは機械語を含むTEXTセグメントとグローバル変数を保持するDATAセグメントに分かれます。

これらのセグメントの大きな違いとして書き込み権限の有無が挙げられます。TEXTセグメントは実行中読み出し専用で書き込み不可ですが、DATAセグメントは実行中に書き込みが可能です。

TEXTセグメントの読み出し専用の性質は動的ライブラリを使う際やプロセスをforkする際に大きく役立ちます。同じ動的ライブラリを2つのプロセスでロードする時、素朴な発想では同じ動的ライブラリを2つメモリ空間に展開します。が、TEXTセグメントが読み出し専用であれば読み書き可能なDATAセグメントのみを重複して展開し、TEXTセグメントは同一のメモリ空間を共有できます。

つまり、ライブラリの占めるTEXTセグメントの割合が多いほどメモリ空間の利用効率が向上します。

SwiftはTEXTセグメントにできるだけメタデータを配置するために一工夫しています。

再配置

再配置は主にリンカがオブジェクトファイルをリンクするタイミングと、プログラムローダが実行可能ファイルをロードするタイミングの2回行われます。

リンク時の再配置ではシンボル同士のアドレスの差や、セクションの先頭からのオフセットなど、実行前にわかる情報を反映します。

また、ロード時の再配置ではプログラムの各部分で使われている絶対アドレスを実際のメモリ空間のアドレスに置換します。基本的に、プログラムが展開されるメモリ空間の先頭アドレスを各アドレスに足し合わせるだけです。

データ構造のテクニック

Relative Pointer

Relative Pointerはポインタ自身のアドレスから対象のアドレスまでのオフセットを保持するポインタ形式です。Swiftのメタデータに含まれるポインタは全てこのRelative Pointer形式になっています。

struct RelativePointer<Pointee> {
    var offset: Int32

    mutating func pointee() -> Pointee {
        return withUnsafePointer(to: &self) { [offset] pointer -> UnsafePointer<Pointee> in
            let rawPointer = UnsafeRawPointer(pointer)
            let advanced = rawPointer.advanced(by: Int(offset))
            return advanced.assumingMemoryBound(to: Pointee.self)
        }.pointee
    }
}

通常のポインタの代わりにRelativePointerを使うメリットはいくつかあります。

バイナリサイズの節約
ロード時再配置を減らせる
メタデータをTEXTセグメントに含められるようにできる

上から1つづつ見ていきます。

まず、Relative Pointerは二点間のアドレスの差を計算するリンカの再配置の仕組みを使っています。この再配置の結果は符号付き32bit整数におさまる、という前提で作られているため、通常のポインタが64bit消費するのに対し、Relative Pointerはその半分の32bitで表現できます。

ロード時の再配置についてですが、前述したとおり、通常のポインタはロード時に再配置が発生するため、プログラムの起動までにオーバーヘッドが発生します。一方、二点間のアドレスの差の計算はリンク時に完了する再配置なので、ロード時のオーバーヘッドがありません。

またロード時の再配置を無くすことによって、メタデータはロード時のデータの書き換えを抑制し、位置独立なデータとして扱うことができます。つまり、実行プログラム本体と同じようにTEXTセグメントに配置して、ほかのプロセスとメモリ空間を共有できるようになります。

もちろんデリファレンス時にオフセットを足し合わせるオーバーヘッドが発生しますが、Swiftでは以上のメリットよりこのような手法を採用しています。

Indirect Pointer

ランタイムライブラリが扱うポインタにはRelative Pointerと組み合わせて、いくつかのテクニックが使われています。その1つの例がIndirect Pointerです。

Indirect Pointerはアライメントによるアドレスの使われないbitを利用してGOT経由のポインタと通常のポインタを同一の型で表現するテクニックです。

アライメントはプロセッサが効率的にデータを扱うために用いられるメモリ空間上のデータ配置規則です。例えば32bitの数値型はアドレスが4の倍数になるように配置されます。

つまり、Int32が配置されるアドレスの下位2bitは必ず0になるわけです。また、Relative Pointer自身も32bit符号付き整数なので、差の数値の下位2bitも0で固定されます。そのため、ポインタの型さえ分かっていればこの下位数ビットは無駄になってしまいます。

Swiftのランタイムライブラリはこの下位数ビットを使っていくつかの状態をポインタに保持しています。

Indirect Pointerは下位1bitをGOTを経由するか否かを表現するために使っています。

GOTを経由する場合はデリファレンスの際に2回デリファレンスします。

struct RelativeIndirectablePointer<Pointee> /*  where alignof(Pointee) => 2 */ {
    let offsetWithIndirectFlag: Int32

    mutating func pointee() -> Pointee {
        let offset: Int32
        if isIndirect {
            offset = offsetWithIndirectFlag & ~isIndirectMask
        } else {
            offset = offsetWithIndirectFlag
        }
        return withUnsafePointer(to: &self) { pointer -> UnsafePointer<Pointee> in
            let rawPointer = UnsafeRawPointer(pointer)
            let advanced = rawPointer.advanced(by: Int(offset))
            if isIndirect {
                let got = advanced.assuimgMemoryBound(to: UnsafePointer<Pointee>.self)
                return got.assumingMemoryBound(to: Pointee.self)
            } else {
                return advanced.assumingMemoryBound(to: Pointee.self)
            }
        }.pointee
    }

    var isIndirect: Bool {
        offsetWithIndirectFlag & isIndirectMask != 0
    }

    var isIndirectMask: Int32 { 0x01 }
}

Int Paired Pointer

また、使われない下位ビットをそのまま数値として取り出すポインタもあります。

struct RelativeDirectPointerIntPair<Pointee, IntTy: BinaryInteger>
    /*  where alignof(Pointee) => 2 */
{
    let offsetWithInt: Int32

    mutating func pointee() -> Pointee {
        let offset = offsetWithInt & ~intMask
        return withUnsafePointer(to: &self) { pointer -> UnsafePointer<Pointee> in
            let rawPointer = UnsafeRawPointer(pointer)
            let advanced = rawPointer.advanced(by: Int(offset))
            return advanced.assumingMemoryBound(to: Pointee.self)
        }.pointee
    }

    var value: IntTy {
        IntTy(offsetWithInt & intMask)
    }

    var intMask: Int32 {
        Int32(
            min(
                MemoryLayout<Pointee>.alignment,
                MemoryLayout<Int32>.alignment
            ) - 1
        )
    }
}

IndirectableとInt Pairedを組み合わせた型もあり、この場合、Indirectか否かを1bit、もう1bitを値として取り出せるようになっています。

Symbolic Reference

Symbolic Referenceはマングリングの種類の1つとして使われています。

通常、型名からメタデータを取得する場合、マングルされた文字列をデマングルしてメタデータを探索します。しかし、対象のオブジェクトがモジュール内に存在する場合、マングルされた名前を介することなく直接参照した方が効率的です。

通常のマングリングは対象のオブジェクトを一意に示す文字列表現ですが、Symbolic Referenceは文字列の一部に対象オブジェクトのアドレスを直接埋め込みます。

Symbolic Referenceは通常のマングルされた文字列と区別するために先頭が制御文字で始まっており、0x01~0x0CまではSymbolic Referenceのために確保されています。

制御文字のあとには4byteのRelative Pointerが埋め込まれており、ランタイムライブラリでデコードされます。

この仕組みにより、モジュール内に定義されたメタデータの参照はほぼコスト無しに行えます。

__swift_instantiateConcreteTypeFromMangledName

この関数は型名からメタデータを取得するために使われます。引数にはこの関数の結果をキャッシュするための { i32, i32 }の構造が渡ってきます。

擬似C++で表現するとこんな感じです。

union Input {
  struct {
    RelativePointer<CChar> typeName;               // 4byte
    int32_t                negativeTypeNameLength; // 4byte
  } nonCached;
  
  TypeMetadata *cached; // 8 byte
}

キャッシュオブジェクトの状態はキャッシュなしとキャッシュ済みの2つあり、それぞれ64bitの使い方が変わってきます。エンディアンによってレイアウトが変わるので、ひとまずリトルエンディアンを仮定して話を進めます。

キャッシュなしの状態では、最初の32bitには型名へのRelative Pointer、後ろの32bitには型名の長さが負号をつけて配置されます。型名はSymbolic Referenceになりうるため、アドレスの一部としてnull文字が入り込む場合があります。そのためnull文字をターミネータとして使えないため、型名の長さが必要になります。

キャッシュありの状態では、64bit全体をキャッシュしたメタデータへの絶対ポインタがそのまま入っています。

この2つの状態はキャッシュオブジェクトを符号付き64bit整数として見た時、負数であればキャッシュなし、正数であればキャッシュあり、として区別できます。これはキャッシュなしの状態で後方32bitに型名の長さを負号をつけて保存したために、64bit全体を符号付き整数として見ると必ず負数になることを利用しています。また、単純に後方32bitの符号を比較するより64bit全体を見るほうが効率的な命令数になります。

まとめ

この様にランタイムライブラリではメモリ空間を最大限に活用するためのテクニックが多く詰まっています。一方でRelative Pointerを前提に組まれた構造がほとんどなので、32bit以上のポインタサイズをサポートしようとすると、ランタイム構造体の調整が必要になってきます。この調整をする場合、コンパイラが出力するメタデータのレイアウトとランタイムライブラリの想定するレイアウトを同期する必要がありますが、現状の実装では特に同期のための仕組みがあるわけではなく、全てのレイアウトを手動で調整する必要があります。

これはSwiftの移植性に大きく関わってくるため、メタデータのレイアウトを一元的に管理する何かしらの仕組みが必要です。例えば、コンパイラが出力したLLVM IRからランタイムライブラリ用のCの構造体を生成するようなコードジェネレータがあれば解決できるかもしれません。（SwiftのメタデータはTrailingObjectsによって可変長なレイアウトを持つため難しいかもしれませんが。）

LLVMはコンパイラ実装の基盤として大きな役割を果たしていますが、ランタイムライブラリとコンパイラの間のインターフェイス定義をサポートするようなライブラリはあまり見たことがありません。そのようなレイヤーの技術が充実してくればもっと多くの言語がABI安定を達成できるような世界になるかもしれませんね。

kateinoigakukunのブログ

思考垂れ流しObserver