[解決済み] コールスタックはどのように機能するのか？

質問

プログラミング言語の低レベルの動作、特に OS/CPU とどのように相互作用するかについて深く理解しようとしています。おそらく、Stack Overflow のスタック/ヒープ関連のスレッドですべての回答を読みましたが、それらはすべて素晴らしいものでした。しかし、まだ完全に理解できていないことが1つあります。

有効な Rust コードになりがちな疑似コードで、この関数を考えてみましょう ;-)

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(a, b);
    doAnotherThing(c, d);
}

X行目のスタックはこのように想定しています。

Stack

a +-------------+
  | 1           | 
b +-------------+     
  | 2           |  
c +-------------+
  | 3           | 
d +-------------+     
  | 4           | 
  +-------------+ 

さて、スタックがどのように動作するかについて私が読んだことすべては、それが厳密にLIFOルール（last in, first out）に従うということです。.NET、Java、またはその他のプログラミング言語におけるスタック データ型のようにです。

しかし、もしそうだとすると、X行目の後はどうなるのでしょうか。なぜなら、明らかに、次に必要なのは a と b というように、OS/CPU(?)が飛び出すことになります。 d と c に戻るには、まず a と b . しかし、そうすると足元をすくわれることになります。 c と d を次の行に追加します。

で、どうなんだろう はいったい はどうなっているのでしょうか？

もうひとつの関連する質問です。このように他の関数の1つに参照を渡すことを考えます。

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(&a, &b);
    doAnotherThing(c, d);
}

私の理解では、この場合 doSomething は基本的に同じメモリアドレスを指していて a と b で foo . しかし、これはつまり に到達するまでスタックにポップアップする a と b が起こる。

この2つのケースを見ると、私はまだどのように まさに がどのように機能し、どのように厳密に LIFO のルールに厳密に従うことです。

どのように解決するのですか？

コールスタックはフレームスタックとも呼ばれることがあります。

というものは スタック は、ローカル変数ではなく、呼び出される関数のスタックフレーム全体です。 . ローカル変数はこれらのフレームと一緒に、いわゆる 関数プロローグ と エピローグ のように、それぞれ

フレーム内では変数の順序は全く指定されていません。コンパイラ "reorder"フレーム内のローカル変数の位置を指定します。 は、プロセッサができるだけ早く変数を取得できるように、その配置を最適化するために、フレーム内のローカル変数の位置を適切に並べ替えます。重要なのは ある固定アドレスに対する変数のオフセットがフレームの寿命を通じて一定であることです。 - ですから、アンカーアドレス、例えばフレーム自体のアドレスを取り、変数へのそのアドレスのオフセットで作業すれば十分なのです。このようなアンカーアドレスは、実際にはいわゆる ベース または フレームポインタ であり、EBP レジスタに格納されます。一方、オフセットはコンパイル時に明確にわかるため、マシン コードにハードコードされます。

このグラフィックは ウィキペディア は、典型的なコールスタックがどのような構造になっているかを示しています。 ¹ :

フレームポインタに含まれるアドレスに、アクセスしたい変数のオフセットを追加すると、変数のアドレスが得られます。つまり、コードではベース ポインタから一定のコンパイル時オフセットを介して直接アクセスするだけで、単純なポインタ演算が行われます。

例

#include <iostream>

int main()
{
    char c = std::cin.get();
    std::cout << c;
}

gcc.godbolt.org は私たちに

main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

    movl    std::cin, %edi
    call    std::basic_istream<char, std::char_traits<char> >::get()
    movb    %al, -1(%rbp)
    movsbl  -1(%rbp), %eax
    movl    %eax, %esi
    movl    std::cout, %edi
    call    [... the insertion operator for char, long thing... ]

    movl    $0, %eax
    leave
    ret

... for main . 私はコードを3つのサブセクションに分けました。 関数プロローグは最初の3つの操作で構成されています。

• ベースポインタはスタックにプッシュされます。
• スタックポインタがベースポインタに保存される
• スタックポインタを減算して、ローカル変数のためのスペースを確保します。

次に cin はEDIレジスタに移動されます ² と get が呼び出される。戻り値はEAXである。

ここまでは順調です。さて、面白いことが起こります。

8ビットレジスタALで指定されたEAXの下位バイトが取り出され ベースポインタの直後のバイトに格納されます。 : つまり -1(%rbp) の場合、ベースポインタのオフセットは -1 . このバイトは私たちの変数 c . x86ではスタックが下に伸びていくので、オフセットは負になります。次の操作では c を EAX に格納する。EAX は ESI に移動される。 cout は EDI に移動し、挿入演算子は cout と c が引数です。

最後に

• の戻り値は main の戻り値は EAX: 0 に格納されます。 return ステートメントがあるためです。 また xorl rax rax の代わりに movl .
• を出て、コールサイトに戻る。 leave はこのエピローグを省略し、暗黙のうちに
  • スタックポインタをベースポインタに置き換えて
  • ベースポインタをポップします。

この操作と ret が実行された後、フレームは効果的にポップされますが、cdecl 呼び出し規約を使っているので、呼び出し側はまだ引数をクリーンアップしなければなりません。他の規約、例えば stdcall では、呼び出し側が片付けをする必要があります。 ret .

フレームポインタの省略

ベース/フレーム ポインターからのオフセットを使用せず、代わりにスタック ポインター (ESB) からオフセットを使用することも可能です。これにより、フレーム ポインタの値を含む EBP レジスタを任意の用途に使用できるようになります - しかし、これにより デバッグが不可能になるマシンもあります。 となり、また 暗黙のうちにいくつかの関数でオフにされます。 . これは、x86を含む少数のレジスタしか持たないプロセッサ用にコンパイルするときに特に有用です。

この最適化はFPO (frame pointer omission) として知られ、以下のように設定されます。 -fomit-frame-pointer で設定され、GCC の -Oy これは、デバッグがまだ可能な場合のみ、すべての最適化レベル > 0 で暗黙的にトリガーされることに注意してください。 詳細については を参照してください。 および はこちら .

¹ コメントで指摘されているように、フレームポインタはリターンアドレスの後のアドレスを指すと思われます。

² Rで始まるレジスタは、Eで始まるレジスタの64ビット版であることに注意してください。EAXはRAXの下位4バイトを表します。わかりやすくするために、32 ビットのレジスタの名前を使用しました。