元は こちら
CPUコア数の少ない環境向けのSTMシステムです。 動作には 64bit の Linux 環境の上で clang を使ってビルドする必要があります。
これは、 __attribute__((address_space(256))) を使用した構造体のハックです。
このハックを使うと、 clang はアセンブラレベルで、すべてのポインタの参照剥がしを "%gs" プリフィクスを使うようにします。
すべてのメモリアクセスのアドレスを特殊レジスタ %gs の値分ずらして処理させるという時たま使われる機能です。
%gs の値はスレッドごとに保持されます。
Note
pthread ライブラリでは、スレッドローカル変数のアドレスに対してオフセットを指定するために %fs レジスタを使っています。
私達が必要としているものは、スレッドローカル変数と同じようなものですが、それを大量に必要としています。
私達は %gs プリフィクスを使うことで速度低下するという事例を一つも見つけられませんでした。
そのため、実際のパフォーマンスへの影響が小さいものであると期待しています。
(この期待は一つ一つの load/store 命令に付加されるデータによる余分なストレスによる影響に対するものです)
Linux にだけ存在するシステムコール remap_file_pages() は、 メモリ上の mmap() 領域への操作を許可します。
この remap_file_pages() システムコールによって、CPUによるメモリマップの管理に一つのレイヤを追加します。
ここで、ファイルにマッピングされない mmap を見てみましょう。
mmap() を呼び出すと、ゼロで初期化された物理的なページを4096バイトごとに割り当てます。
(実際は一度にすべてを確保するわけではなく、プロセスが本当に必要とする時まで領域の確保は遅延されます。)
現在のプロセスにおける仮想アドレスの確保もまた、物理ページに対応する形で行われます。
しかし rmap_file_pages() を使うことでアドレスと物理ページのマッピングを変更できます。
物理ページと仮想メモリのそれぞれの総量は同一で不変ですが、ページサイズの範囲がどこにあるのかを取得でき、異なる物理ページにマッピングされているかどうかを調べられます。 おそらく変更が終わるまではオーバーヘッドとカーネル上の追加メモリ領域は存在しないものと思われます。 ここでのトリックは、異なる範囲のアドレスをメモリ上の同じ物理ページにマッピングできるということです。これはコストをかけずに別のアドレスとデータをシェアする方法です。
Note
この機能は Linux でのみ有効ですが、別の OS 上でも実現できる可能性があるアイデアです。 Windows 上では OS のページテーブルを操作するようなデバイスドライバを着くなどすれば可能になるでしょう。 しかし、もしそれが不可能であればさらに詳しく調査をする必要があります。
N * M バイトの領域を保持するために十分な大きさの mmap を割り当てます。 この時の N はスレッド数、 M は全オブジェクトの合計サイズです。
そして remap_file_pages() を使ってすべての領域を同じ物理メモリにマッピングした N 個のマップを作ります。
それぞれのスレッドにおいて %gs は対応する領域の開始アドレスを指します。
これが意味するところは、スレッドごとに %gs を使って相対的な別のアドレスにアクセスしに行くということです。
しかし、それぞれのアドレスは(最初は)同じ物理メモリ上にマッピングされています。
そのため、 %gs と rmap_file_pages() を使わない場合と同じ結果が得られます。
例外は、既にコミットされたオブジェクトを含むページで、かつ現在のトランザクションで変更されるであろうページです。
このような変更は現在のトランザクションがコミットされるまでは他のスレッドからは見えません。
これは、さらに rmap_file_pages() を使ってページを「非共有化」することで行われます。
すなわち、 %gs を使っての対応付けを止め、スレッドローカルページを他のスレッドと同じ物理ページにマッピングすることをやめるということです。
そのためには新しく物理ページを割り当て、マッピング変更前の内容を複製します。
フォークした後のメモリ領域に対して変更が行われた時のような挙動です。
訳注: Copy on Write の説明っぽい
さらなる詳細:
スレッドローカル領域ごとの最初のページのアドレス (4096バイト) は NULL ポインタでのアクセスのエラーを検知するためにアクセス不可能になっています。
二番目のページはスレッドローカルデータのために予約されています。
それ以降の 1/16 はローカルな読み込みマーカーのために、続く 15/16 は実際にオブジェクトを保持するために使われます。
最初に remap_file_pages() を使うのはこの 15/16 の範囲です。
それぞれのトランザクションでは変更のあったオブジェクトを記録します。 その記録は共有されていないページのなかで行われます。 他のスレッドがコミットを行うときは、最初に変更のあったオブジェクトをそれぞれのバージョンのページにコピーします。 ここでのポイントは、別のスレッドから見るとメモリ上の変更が見えず、別のスレッドでは変更をコピーすることが明示されているという事です。
どのオブジェクトが読み込まれているかを追跡するために、それぞれのトランザクションでは(プライベートな)読み込みマーカーを使います。 スレッドがいくつかのオブジェクトに加えられた変更を「取り込む」場合、それらのオブジェクトが現在のトランザクションで読み込まれているかをすぐにチェックできます。 そして、変更の衝突を検知できるのです。
Note
訳注
ココらへんから訳が怪しい
ここでは、STM の研究において、STM がうまく働くとされている条件での仕組みを説明します。 トランザクションは「開始時」から「コミット時」の間張られていますが、開始からコミットまでの時間はは明示的に数値として表現されるわけではありません。 トランザクションの開始時に、現在のスレッドにおける「オブジェクトの初期状態」を定義します。 現在張っているトランザクションの開始時間を規則正しくバンプする(増やす?)ために「拡張可能なタイムスタンプ(extendable timestamps)」と呼ばれる手法を用いています。 (潜在的な衝突が検知された時だけでなく、もう少し頻繁です)
スレッドごとに、読み込んだオブジェクト(バイトマップを使って)をプライベートな領域に、書き込んだオブジェクトを(オブジェクトのグローバルフラグと同様にポインタの配列を使って)公開領域に記録しています。 Read-write コンフリクトは開始時のバンプにおいて検知されます。 Write-write コンフリクトはもう少し厳密に検出されます。 すなわち、あるオブジェクトに対する変更を一度に実行できるトランザクションはひとつだけです。 (write-write コンフリクトのケースでは、いくつかの競合状態を管理するためのポリシーの候補があります。今は、オブジェクトに変更を加えようとした時点より後のトランザクションは常に取り消されます)
現在のトランザクションで新しく作られたオブジェクトについては、別に考慮してあげる必要があります。 それらのオブジェクトは変更されたオブジェクトの大半であり、すぐに使われなくなることを期待しています。
「undo log」アプローチに似た手法をを使っています。 オブジェクトはインプレイスに変更され、どこかから書き戻すことで中止されます。 しかし、これは明示的な undo log を使わずに実装されています。書き戻しは複数スレッドのローカルコピー間でのコピーによって行われます。 メモリページに含まれる変更されたオブジェクトは重複しています。またコピーされたいくつかのオブジェクトは既に別のバージョンである可能性があります、
(この章の残りの部分は「リーダー」の定義です。 「リーダー」はトランザクションが中止された時に書き戻すオブジェクトを常に確認するための確実な方法です。 まず、core.c で実装されているように、2つのスレッドが最新版になるまでの間、必要であれば単に待ちます。 その後、それぞれのスレッドは他のスレッドのオリジナルオブジェクトを使えるようになります。)
一つのスレッドは「リーダー」と呼ばれます。(「リーダー」は私の知る範囲では新しい用語です) リーダーは
- その時トランザクションを張っているスレッド (as opposed to being in some blocking syscall between two transactions, for example);
- 一つではない 並行してトランザクションを張っている他のスレッドが存在する (一つのスレッドのみが動いているときは、それはリーダーではありません)
- 最後にそのスレッドのトランザクション開始時刻が、他に張っているどのトランザクションの開始時間よりも厳密に高い (いくつかのスレッドが同じ最大の開始時刻を持つとき、リーダーはいません)
Note
高いとは?
リーダーシップは一時的な状態です。 トランザクションがコミットされ、次のトランザクションが開始することによって、リーダーシップがスレッドによって(通常)獲得されます。 しかし、他のスレッドがトランザクションの開始時間を更新した後すぐにリーダーシップは再び失われます。
リーダーシップという概念のポイントは、リーダーがオブジェクトを変更しようとするとき、まずオリジナルバージョンが他にも存在するかどうかを確認する必要があります。 もしオリジナルバージョンが存在している場合は、リーダースレッドのみがそれについて配慮する必要があります。
古いオブジェクトのオリジナルバージョンは覚えておく必要がありません。 トランザクションを中断する必要があるときすべてのオブジェクトを最新版に更新することがあるためです。 そして、一番高い同じ開始時刻を持ついくつかのスレッドがあるとき、オリジナルオブジェクトがそれらのスレッドのどこかにあることを確認します。 これが Write-Write 競合をすぐに検出するためのポイントです。 最後に、一つのスレッドのみが走っているときは直ちにに更新され、トランザクションが中止されることはありません。 すべてのオブジェクトの古いバージョンを記録する必要がないのです。
The only remaining case is the one in which there is a leader thread, this leader thread has the only latest version of an object, and it tries to further modify this object. To handle this precise case, for now, we simply wait until another thread updates and we are no longer the leader.
一つ残ったケースは、リーダースレッドがひとつの場合です。 このリーダースレッドは、最新のオブジェクトのみを持ちます。 そして、さらにオブジェクトの更新を試みることができます。 この正確なケースを処理するには 現在は他のスレッドが更新し、リーダーが存在しなくなるまで単純に待っています。
Note
the code in core.c contains, or contained, or will again contain, an explicit undo log that would be filled in this case only.
これらのコードは core.c には含まれる・含まれていた・再び含まれる可能性があります。 明示的な undo log
ドラフト:
- 変更され、既にコミットされたオブジェクトを含むページは非共有状態にする必要があります.
- ページのメモリ空間の一部(もしくはすべて)が以前使われていなかった場合、ページは共有して残せます。 しかし、ページが新しいオブジェクトの割り当てに使われた場合、そのトランザクションの間に行われる新しいオブジェクトに対するどのような変更も非共有状態にする必要は ありません 。そのため、一般的なケースにおいて、大半のページは非共有になることはありません。
- いつでも定期的にトランザクションの終了時点で発生するマイナーコレクションにおいて、マークすることで新しいオブジェクトが生き残ることがあります。("mark-and-don't-sweep" GC において)マークされていないオブジェクトは次の割り当てリクエストまで遅延されてスワップされます。(ここではマイナーコレクションのみです) 古いオブジェクトが新しいオブジェクトを参照していることを検出するために write barrier が必要です。(古いオブジェクトは、同じ実行中のトランザクションよりフレッシュな可能性があります。もしくは既にコミットされています。)
- オブジェクトに格納されている数値とフラグは上記ゴールを考慮して設計する必要があります。
- まだ不明: マイナーコレクションは空きメモリが存在しないか、数メガバイトのメモリが確保されるたびにのみ引き起こされる可能性があります。これは、数メガバイトを確保する程度の小〜中規模のトランザクションでは重要ではありません。しかし、実行時間の長いトランザクションでは気にする必要があります。
- major collection は すべて のオブジェクトを走査します。 そのためにはすべてのスレッドの同期がおそらく必要となるでしょう。 理想的にはスレッドが並列してGCを実行する必要があります。 しかし、最初のステップではすべてのスレッドをブロックし、ひとつのスレッドを走らせます。
major collection は実際に使っているメモリ量によって引き起こされる必要があります。 その意味するところは、非共有状態のページを N ページとしてカウントするという事です。 major collection は、すべてのスレッドのタイムスタンプが更新されていることを確認したら、可能な限りページを再共有しようとします。 大きく、古く、長い間更新されていないオブジェクトを、最終的にメモリ上の一つだけ残してまとめるということを保証する本質的な部分です。
一方、同じ時間の境界で
remap_file_pages()が呼ばれる回数は major collection サイクルごとに一ページにつき二回です。
Use __builtin_setjmp() and __builtin_longjmp() rather than setjmp() and longjmp().