Bagaimana tepatnya cara kerja callstack?

103

Saya mencoba untuk mendapatkan pemahaman yang lebih dalam tentang bagaimana operasi bahasa pemrograman tingkat rendah bekerja dan terutama bagaimana mereka berinteraksi dengan OS / CPU. Saya mungkin telah membaca setiap jawaban di setiap utas terkait tumpukan / tumpukan di sini di Stack Overflow, dan semuanya brilian. Tapi masih ada satu hal yang belum saya mengerti sepenuhnya.

Pertimbangkan fungsi ini dalam kode semu yang cenderung merupakan kode Rust yang valid ;-)

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

    // line X

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

Beginilah cara saya mengasumsikan tumpukan terlihat pada baris X:

Stack

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

Sekarang, semua yang saya baca tentang cara kerja tumpukan adalah bahwa ia secara ketat mematuhi aturan LIFO (terakhir masuk, keluar pertama). Sama seperti tipe data tumpukan di .NET, Java atau bahasa pemrograman lainnya.

Tetapi jika itu masalahnya, lalu apa yang terjadi setelah baris X? Karena jelas, hal berikutnya yang kita perlukan adalah bekerja dengan adan b, tetapi itu berarti OS / CPU (?) Harus keluar ddan cpertama kembali ke adan b. Tapi kemudian ia akan menembak dirinya sendiri di kaki, karena ia membutuhkan cdan ddi baris berikutnya.

Jadi, saya bertanya-tanya apa sebenarnya yang terjadi di balik layar?

Pertanyaan terkait lainnya. Pertimbangkan kami meneruskan referensi ke salah satu fungsi lain seperti ini:

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

    // line X

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

Dari cara saya memahami berbagai hal, ini berarti bahwa parameter di doSomethingpada dasarnya menunjuk ke alamat memori yang sama seperti adan bdi foo. Tetapi sekali lagi ini berarti bahwa tidak ada munculan tumpukan sampai kita sampai adanb terjadi.

Kedua kasus itu membuat saya berpikir bahwa saya belum sepenuhnya memahami bagaimana tepatnya tumpukan bekerja dan bagaimana itu secara ketat mengikuti aturan LIFO .

Christoph
sumber
14
LIFO hanya penting untuk menyediakan ruang pada tumpukan. Anda selalu dapat mengakses variabel apa pun yang setidaknya ada di bingkai tumpukan Anda (dideklarasikan di dalam fungsi) meskipun berada di bawah banyak variabel lain
VoidStar
2
Dengan kata lain, LIFOartinya Anda dapat menambah atau menghapus elemen hanya di akhir tumpukan, dan Anda selalu dapat membaca / mengubah elemen apa pun.
HolyBlackCat
12
Mengapa Anda tidak membongkar fungsi sederhana setelah mengkompilasi dengan -O0 dan melihat instruksi yang dihasilkan? Cukup, baik, instruktif ;-). Anda akan menemukan bahwa kode tersebut memanfaatkan bagian R RAM dengan baik; itu mengakses alamat secara langsung sesuka hati. Anda dapat menganggap nama variabel sebagai offset ke register alamat (penunjuk tumpukan). Seperti yang dikatakan orang lain, tumpukan hanya LIFO sehubungan dengan penumpukan (baik untuk rekursi, dll.). Ini bukan LIFO sehubungan dengan mengaksesnya. Akses sepenuhnya acak.
Peter - Reinstate Monica
6
Anda dapat membuat struktur data tumpukan Anda sendiri menggunakan larik, dan hanya menyimpan indeks elemen teratas, menambahkannya saat Anda mendorong, menurunkannya saat Anda muncul. Jika Anda melakukan ini, Anda masih dapat mengakses setiap elemen dalam larik kapan saja tanpa mendorong atau memunculkannya, seperti yang selalu dapat Anda lakukan dengan larik. Kira-kira hal yang sama terjadi di sini.
Crowman
3
Pada dasarnya, penamaan stack / heap sangat disayangkan. Mereka memiliki sedikit kemiripan dengan stack dan heap dalam terminologi struktur data, jadi menyebutnya sama akan sangat membingungkan.
Siyuan Ren

Jawaban:

117

Tumpukan panggilan juga bisa disebut tumpukan bingkai.
Hal-hal yang ditumpuk setelah prinsip LIFO bukanlah variabel lokal tetapi seluruh frame stack ("panggilan") dari fungsi yang dipanggil . Variabel lokal didorong dan muncul bersama dengan frame-frame tersebut dalam apa yang disebut prolog dan epilog fungsi .

Di dalam bingkai, urutan variabel sama sekali tidak ditentukan; Penyusun "menyusun ulang" posisi variabel lokal di dalam bingkai dengan tepat untuk mengoptimalkan penyelarasannya sehingga prosesor dapat mengambilnya secepat mungkin. Fakta krusialnya adalah bahwa offset variabel relatif terhadap beberapa alamat tetap adalah konstan selama masa pakai frame - jadi cukup untuk mengambil alamat anchor, katakanlah, alamat frame itu sendiri, dan bekerja dengan offset dari alamat tersebut ke variabel. Alamat jangkar seperti itu sebenarnya terkandung dalam apa yang disebut penunjuk dasar atau bingkaiyang disimpan dalam register EBP. Sebaliknya, offset diketahui dengan jelas pada waktu kompilasi dan oleh karena itu di-hardcode ke dalam kode mesin.

Grafik dari Wikipedia ini menunjukkan seperti apa susunan panggilan tipikal seperti 1 :

Gambar tumpukan

Tambahkan offset variabel yang ingin kita akses ke alamat yang terdapat dalam penunjuk bingkai dan kita mendapatkan alamat variabel kita. Jadi singkatnya, kode hanya mengaksesnya secara langsung melalui offset waktu kompilasi konstan dari penunjuk dasar; Ini aritmatika penunjuk sederhana.

Contoh

#include <iostream>

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

gcc.godbolt.org memberi kita

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

.. untuk main. Saya membagi kode menjadi tiga subbagian. Prolog fungsi terdiri dari tiga operasi pertama:

  • Penunjuk dasar didorong ke tumpukan.
  • Penunjuk tumpukan disimpan di penunjuk dasar
  • Penunjuk tumpukan dikurangi untuk memberikan ruang bagi variabel lokal.

Kemudian cindipindahkan ke EDI register 2 dan getdipanggil; Nilai kembali dalam EAX.

Sejauh ini baik. Sekarang hal yang menarik terjadi:

Byte orde rendah EAX, yang ditunjuk oleh register 8-bit AL, diambil dan disimpan dalam byte tepat setelah pointer dasar : Artinya -1(%rbp), offset dari pointer dasar adalah -1. Byte ini adalah variabel kitac . Offsetnya negatif karena tumpukan tumbuh ke bawah pada x86. Penyimpanan operasi berikutnya cdi EAX: EAX dipindahkan ke ESI, coutdipindahkan ke EDI dan kemudian operator penyisipan dipanggil dengan coutdan cmenjadi argumennya.

Akhirnya,

  • Nilai kembali maindisimpan dalam EAX: 0. Itu karena returnpernyataan implisit . Anda mungkin juga melihat, xorl rax raxbukan movl.
  • pergi dan kembali ke situs panggilan. leavemenyingkat epilog ini dan secara implisit
    • Mengganti penunjuk tumpukan dengan penunjuk dasar dan
    • Munculkan penunjuk dasar.

Setelah operasi ini dan retdilakukan, frame telah secara efektif muncul, meskipun pemanggil masih harus membersihkan argumen karena kita menggunakan konvensi pemanggilan cdecl. Konvensi lain, misalnya stdcall, mengharuskan callee untuk merapikan, misalnya dengan meneruskan jumlah byte ke ret.

Penghilangan Pointer Bingkai

Dimungkinkan juga untuk tidak menggunakan offset dari penunjuk basis / bingkai tetapi dari penunjuk tumpukan (ESB) sebagai gantinya. Hal ini membuat register EBP yang seharusnya berisi nilai penunjuk bingkai tersedia untuk penggunaan sewenang-wenang - tetapi hal ini dapat membuat debugging tidak mungkin dilakukan pada beberapa mesin , dan akan secara implisit dimatikan untuk beberapa fungsi . Ini sangat berguna ketika mengkompilasi prosesor dengan hanya sedikit register, termasuk x86.

Pengoptimalan ini dikenal sebagai FPO (penghilangan penunjuk bingkai) dan ditetapkan oleh -fomit-frame-pointerGCC dan -OyClang; perhatikan bahwa ini secara implisit dipicu oleh setiap level pengoptimalan> 0 jika dan hanya jika debugging masih memungkinkan, karena tidak ada biaya selain itu. Untuk informasi lebih lanjut lihat di sini dan di sini .


1 Seperti yang ditunjukkan dalam komentar, penunjuk bingkai mungkin dimaksudkan untuk menunjuk ke alamat setelah alamat pengirim.

2 Perhatikan bahwa register yang dimulai dengan R adalah register 64-bit dari register yang dimulai dengan E. EAX menunjuk empat byte orde rendah RAX. Saya menggunakan nama register 32-bit untuk kejelasan.

Columbo
sumber
1
Jawaban yang bagus. Masalah dengan menangani data dengan offset adalah bagian yang hilang bagi saya :)
Christoph
1
Saya pikir ada kesalahan kecil dalam gambar. Penunjuk bingkai harus berada di sisi lain dari alamat pengirim. Meninggalkan suatu fungsi biasanya dilakukan sebagai berikut: pindahkan penunjuk tumpukan ke penunjuk bingkai, lepaskan penunjuk bingkai pemanggil dari tumpukan, kembali (yaitu
lepaskan
kasperd benar sekali. Anda juga tidak menggunakan penunjuk bingkai sama sekali (pengoptimalan yang valid dan khususnya untuk arsitektur yang kekurangan register seperti x86 sangat berguna) atau Anda menggunakannya dan menyimpan yang sebelumnya di tumpukan - biasanya tepat setelah alamat pengirim. Bagaimana frame disiapkan dan dihapus sangat bergantung pada arsitektur dan ABI. Ada beberapa arsitektur (halo Itanium) di mana semuanya .. lebih menarik (dan ada hal-hal seperti daftar argumen berukuran variabel!)
Voo
3
@Christoph Saya pikir Anda mendekati ini dari sudut pandang konseptual. Berikut adalah komentar yang diharapkan dapat menyelesaikan masalah ini - RTS, atau RunTime Stack, sedikit berbeda dari tumpukan lain, karena ini adalah "tumpukan kotor" - sebenarnya tidak ada yang mencegah Anda untuk melihat nilai yang tidak ' t di atas. Perhatikan bahwa dalam diagram, "Alamat Pengembalian" untuk metode hijau - yang dibutuhkan oleh metode biru! adalah setelah parameter. Bagaimana metode biru mendapatkan nilai kembali, setelah bingkai sebelumnya muncul? Yah, ini adalah tumpukan kotor, jadi dia bisa masuk dan mengambilnya.
Bersepeda pada
1
Frame pointer sebenarnya tidak diperlukan karena seseorang selalu dapat menggunakan offset dari stack pointer. GCC yang menargetkan arsitektur x64 secara default menggunakan penunjuk tumpukan, dan membebaskan rbpuntuk melakukan pekerjaan lain.
Siyuan Ren
27

Karena jelas, hal berikutnya yang kita butuhkan adalah bekerja dengan a dan b tetapi itu berarti OS / CPU (?) Harus mengeluarkan d dan c terlebih dahulu untuk kembali ke a dan b. Tapi kemudian ia akan menembak dirinya sendiri di kaki karena ia membutuhkan c dan d di baris berikutnya.

Pendeknya:

Tidak perlu melontarkan argumen. Argumen yang diteruskan oleh pemanggil fooke fungsi doSomethingdan variabel lokal di doSomething semua dapat direferensikan sebagai offset dari penunjuk dasar .
Begitu,

  • Saat pemanggilan fungsi dilakukan, argumen fungsi PUSH di stack. Argumen ini selanjutnya direferensikan oleh penunjuk dasar.
  • Saat fungsi kembali ke pemanggilnya, argumen dari fungsi yang kembali akan POP dari tumpukan menggunakan metode LIFO.

Secara terperinci:

Aturannya adalah bahwa setiap panggilan fungsi menghasilkan pembuatan bingkai tumpukan (dengan alamat minimum yang akan dikembalikan). Jadi, jika funcApanggilan funcBdan funcBpanggilan funcC, tiga bingkai tumpukan diatur satu di atas yang lain. Ketika suatu fungsi kembali, bingkainya menjadi tidak valid . Fungsi yang berperilaku baik hanya bertindak pada bingkai tumpukannya sendiri dan tidak melanggar bingkai lain. Dengan kata lain POPing dilakukan ke stack frame di atas (saat kembali dari fungsi).

masukkan deskripsi gambar di sini

Tumpukan dalam pertanyaan Anda disiapkan oleh pemanggil foo. Ketika doSomethingdan doAnotherThingdipanggil, maka mereka mengatur tumpukan mereka sendiri. Angka tersebut dapat membantu Anda untuk memahami ini:

masukkan deskripsi gambar di sini

Perhatikan bahwa, untuk mengakses argumen, badan fungsi harus melintasi (alamat yang lebih tinggi) dari lokasi di mana alamat yang dikembalikan disimpan, dan untuk mengakses variabel lokal, badan fungsi harus melintasi tumpukan (alamat yang lebih rendah) ) relatif terhadap lokasi penyimpanan alamat pengirim. Faktanya, kode yang dihasilkan kompilator tipikal untuk fungsi tersebut akan melakukan hal ini dengan tepat. Kompiler mendedikasikan register yang disebut EBP untuk ini (Base Pointer). Nama lain untuk hal yang sama adalah penunjuk bingkai. Kompiler biasanya, sebagai hal pertama untuk badan fungsi, mendorong nilai EBP saat ini ke stack dan menyetel EBP ke ESP saat ini. Ini berarti, setelah ini selesai, di bagian mana pun dari kode fungsi, argumen 1 berjarak EBP + 8 (4 byte untuk masing-masing EBP pemanggil dan alamat pengirim), argumen 2 adalah EBP + 12 (desimal), variabel lokal adalah EBP-4n.

.
.
.
[ebp - 4]  (1st local variable)
[ebp]      (old ebp value)
[ebp + 4]  (return address)
[ebp + 8]  (1st argument)
[ebp + 12] (2nd argument)
[ebp + 16] (3rd function argument) 

Lihatlah kode C berikut untuk pembentukan bingkai tumpukan fungsi:

void MyFunction(int x, int y, int z)
{
     int a, int b, int c;
     ...
}

Saat penelepon menyebutnya

MyFunction(10, 5, 2);  

kode berikut akan dibuat

^
| call _MyFunction  ; Equivalent to: 
|                   ; push eip + 2
|                   ; jmp _MyFunction
| push 2            ; Push first argument  
| push 5            ; Push second argument  
| push 10           ; Push third argument  

dan kode perakitan untuk fungsi tersebut akan (diatur oleh callee sebelum kembali)

^
| _MyFunction:
|  sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c)
|  ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16]
|  ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] =   [esp]
|  mov ebp, esp
|  push ebp
 

Referensi:

haccks
sumber
1
Terima kasih atas jawaban Anda. Juga tautannya sangat keren dan membantu saya menjelaskan lebih banyak pertanyaan yang tidak pernah berakhir tentang bagaimana sebenarnya komputer bekerja :)
Christoph
Apa yang Anda maksud dengan "mendorong nilai EBP saat ini ke tumpukan" dan juga apakah penunjuk tumpukan disimpan dalam register atau yang juga menempati posisi di tumpukan ... saya sedikit bingung
Suraj Jain
Dan Bukankah seharusnya itu * [ebp + 8] bukan [ebp + 8].?
Suraj Jain
@Tokopedia Tahukah kamu apa itu EBPdan ESP?
haccks
esp adalah penunjuk tumpukan dan ebp adalah penunjuk dasar. Jika saya memiliki pengetahuan yang salah, mohon dikoreksi.
Suraj Jain
19

Seperti yang dicatat orang lain, tidak perlu parameter pop, sampai keluar dari ruang lingkup.

Saya akan menempelkan beberapa contoh dari "Pointer dan Memori" oleh Nick Parlante. Saya pikir situasinya sedikit lebih sederhana dari yang Anda bayangkan.

Ini kodenya:

void X() 
{
  int a = 1;
  int b = 2;

  // T1
  Y(a);

  // T3
  Y(b);

  // T5
}

void Y(int p) 
{
  int q;
  q = p + 2;
  // T2 (first time through), T4 (second time through)
}

Poin-poin dalam waktu T1, T2, etc. ditandai dalam kode dan status memori pada saat itu ditunjukkan pada gambar:

masukkan deskripsi gambar di sini


sumber
2
Penjelasan visual yang bagus. Saya mencari di Google dan menemukan kertasnya di sini: cslibrary.stanford.edu/102/PointersAndMemory.pdf Makalah yang sangat membantu!
Christoph
7

Prosesor dan bahasa yang berbeda menggunakan beberapa desain tumpukan yang berbeda. Dua pola tradisional pada 8x86 dan 68000 disebut konvensi pemanggilan Pascal dan konvensi pemanggilan C; setiap konvensi ditangani dengan cara yang sama di kedua prosesor, kecuali untuk nama register. Masing-masing menggunakan dua register untuk mengelola tumpukan dan variabel terkait, yang disebut penunjuk tumpukan (SP atau A7) dan penunjuk bingkai (BP atau A6).

Saat memanggil subrutin menggunakan salah satu konvensi, parameter apa pun akan didorong pada stack sebelum memanggil rutin. Kode rutin kemudian mendorong nilai saat ini dari penunjuk bingkai ke tumpukan, menyalin nilai saat ini dari penunjuk tumpukan ke penunjuk bingkai, dan mengurangi jumlah byte yang digunakan oleh variabel lokal [jika ada] dari penunjuk tumpukan. Setelah itu selesai, bahkan jika data tambahan didorong ke tumpukan, semua variabel lokal akan disimpan di variabel dengan perpindahan negatif konstan dari penunjuk tumpukan, dan semua parameter yang didorong pada tumpukan oleh pemanggil dapat diakses di perpindahan positif konstan dari penunjuk bingkai.

Perbedaan antara kedua konvensi tersebut terletak pada cara mereka menangani keluar dari subrutin. Dalam konvensi C, fungsi yang dikembalikan menyalin penunjuk bingkai ke penunjuk tumpukan [memulihkannya ke nilai yang dimilikinya tepat setelah penunjuk bingkai lama didorong], memunculkan nilai penunjuk bingkai yang lama, dan melakukan pengembalian. Parameter apa pun yang didorong oleh penelepon ke tumpukan sebelum panggilan akan tetap ada. Dalam konvensi Pascal, setelah memunculkan penunjuk bingkai lama, prosesor memunculkan alamat pengembalian fungsi, menambahkan ke penunjuk tumpukan jumlah byte parameter yang didorong oleh pemanggil, dan kemudian pergi ke alamat pengembalian yang muncul. Pada asli 68000 itu perlu untuk menggunakan urutan 3 instruksi untuk menghapus parameter pemanggil; prosesor 8x86 dan semua 680x0 setelah aslinya menyertakan "ret N"

Konvensi Pascal memiliki keuntungan dalam menyimpan sedikit kode di sisi pemanggil, karena pemanggil tidak perlu memperbarui penunjuk tumpukan setelah pemanggilan fungsi. Namun, ia memerlukan bahwa fungsi yang dipanggil tahu persis berapa banyak byte yang bernilai parameter yang akan diletakkan pemanggil di tumpukan. Gagal mendorong jumlah parameter yang tepat ke tumpukan sebelum memanggil fungsi yang menggunakan konvensi Pascal hampir dijamin akan menyebabkan crash. Ini diimbangi, bagaimanapun, oleh fakta bahwa sedikit kode tambahan dalam setiap metode yang dipanggil akan menyimpan kode di tempat-tempat di mana metode tersebut dipanggil. Oleh karena itu, sebagian besar rutinitas kotak alat Macintosh asli menggunakan konvensi pemanggilan Pascal.

Konvensi pemanggilan C memiliki keuntungan karena memungkinkan rutinitas menerima sejumlah variabel parameter, dan menjadi kuat bahkan jika sebuah rutin tidak menggunakan semua parameter yang diteruskan (pemanggil akan mengetahui berapa nilai byte parameter yang didorongnya, dan dengan demikian akan bisa membersihkannya). Lebih lanjut, tidak perlu melakukan pembersihan tumpukan setelah setiap panggilan fungsi. Jika sebuah rutin memanggil empat fungsi secara berurutan, yang masing-masing menggunakan parameter senilai empat byte, ia mungkin - alih-alih menggunakan ADD SP,4setelah setiap panggilan, gunakan satu ADD SP,16setelah panggilan terakhir untuk membersihkan parameter dari keempat panggilan.

Saat ini konvensi panggilan yang dijelaskan dianggap agak kuno. Karena kompiler menjadi lebih efisien dalam penggunaan register, biasanya metode menerima beberapa parameter di register daripada mengharuskan semua parameter didorong pada stack; jika suatu metode dapat menggunakan register untuk menampung semua parameter dan variabel lokal, tidak perlu menggunakan penunjuk bingkai, sehingga tidak perlu menyimpan dan memulihkan yang lama. Namun, terkadang perlu menggunakan konvensi pemanggilan yang lebih lama saat memanggil perpustakaan yang ditautkan untuk menggunakannya.

supercat
sumber
1
Wow! Bisakah saya meminjam otak Anda selama seminggu atau lebih. Perlu mengekstrak beberapa hal penting! Jawaban yang bagus!
Christoph
Di manakah penunjuk bingkai dan tumpukan disimpan dalam tumpukan itu sendiri atau di mana pun?
Suraj Jain
@SurajJain: Biasanya, setiap salinan penunjuk bingkai yang disimpan akan disimpan pada perpindahan tetap relatif terhadap nilai penunjuk bingkai yang baru.
supercat
Pak, saya mengalami keraguan ini untuk waktu yang lama. Jika dalam fungsi saya, saya menulis jika (g==4)kemudian int d = 3dan gsaya mengambil input menggunakan scanfsetelah itu saya mendefinisikan variabel lain int h = 5. Sekarang, bagaimana kompilator sekarang memberi d = 3ruang di tumpukan. Bagaimana offset dilakukan karena jika gtidak 4, maka tidak akan ada memori untuk d di stack dan offset akan diberikan ke hdan jika g == 4offset akan menjadi yang pertama untuk g dan kemudian untuk h. Bagaimana kompilator melakukannya pada waktu kompilasi, ia tidak mengetahui masukan kita untukg
Suraj Jain
@SurajJain: Versi awal C mengharuskan semua variabel otomatis dalam fungsi harus muncul sebelum pernyataan yang dapat dieksekusi. Sedikit melonggarkan kompilasi yang rumit, tetapi salah satu pendekatannya adalah menghasilkan kode di awal fungsi yang mengurangi nilai label yang dideklarasikan ke depan dari SP. Di dalam fungsinya, kompilator dapat di setiap titik dalam kode melacak berapa banyak byte bernilai lokal yang masih dalam cakupan, dan juga melacak jumlah maksimum byte bernilai lokal yang pernah ada dalam cakupan. Di akhir fungsi, ini dapat memberikan nilai untuk sebelumnya ...
supercat
5

Sudah ada jawaban yang sangat bagus di sini. Namun, jika Anda masih khawatir tentang perilaku LIFO dari tumpukan, anggaplah itu sebagai tumpukan bingkai, bukan tumpukan variabel. Yang ingin saya sarankan adalah, meskipun suatu fungsi dapat mengakses variabel yang tidak berada di bagian atas tumpukan, ia masih hanya beroperasi pada item di bagian atas tumpukan: satu bingkai tumpukan.

Tentu saja, ada pengecualian untuk ini. Variabel lokal dari seluruh rantai panggilan masih dialokasikan dan tersedia. Tapi mereka tidak bisa diakses secara langsung. Sebaliknya, mereka diteruskan oleh referensi (atau oleh pointer, yang sebenarnya hanya berbeda secara semantik). Dalam hal ini variabel lokal dari frame stack yang lebih jauh ke bawah dapat diakses. Tetapi bahkan dalam kasus ini, fungsi yang saat ini dijalankan masih hanya beroperasi pada data lokalnya sendiri. Ini mengakses referensi yang disimpan dalam bingkai tumpukannya sendiri, yang mungkin merupakan referensi ke sesuatu di heap, dalam memori statis, atau lebih jauh di tumpukan.

Ini adalah bagian dari tumpukan abstraksi yang membuat fungsi dapat dipanggil dalam urutan apa pun, dan memungkinkan rekursi. Bingkai tumpukan atas adalah satu-satunya objek yang langsung diakses oleh kode. Yang lainnya diakses secara tidak langsung (melalui penunjuk yang berada di bingkai tumpukan atas).

Mungkin bermanfaat untuk melihat perakitan program kecil Anda, terutama jika Anda mengkompilasi tanpa pengoptimalan. Saya pikir Anda akan melihat bahwa semua akses memori dalam fungsi Anda terjadi melalui offset dari penunjuk bingkai tumpukan, yang merupakan cara kode untuk fungsi tersebut akan ditulis oleh kompiler. Dalam kasus lewat referensi, Anda akan melihat instruksi akses memori tidak langsung melalui penunjuk yang disimpan di beberapa offset dari penunjuk bingkai tumpukan.

Jeremy West
sumber
4

Tumpukan panggilan sebenarnya bukan struktur data tumpukan. Di balik layar, komputer yang kami gunakan adalah implementasi dari arsitektur mesin akses acak. Jadi, a dan b bisa langsung diakses.

Di balik layar, mesin melakukan:

  • get "a" sama dengan membaca nilai elemen keempat di bawah stack top.
  • get "b" sama dengan membaca nilai elemen ketiga di bawah tumpukan atas.

http://en.wikipedia.org/wiki/Random-access_machine

hdante
sumber
1

Berikut adalah diagram yang saya buat untuk tumpukan panggilan C. Ini lebih akurat dan kontemporer daripada versi gambar google

masukkan deskripsi gambar di sini

Dan sesuai dengan struktur yang tepat dari diagram di atas, berikut adalah debug dari notepad.exe x64 di windows 7.

masukkan deskripsi gambar di sini

Alamat rendah dan alamat tinggi ditukar sehingga tumpukan naik ke atas dalam diagram ini. Merah menunjukkan bingkai persis seperti pada diagram pertama (yang dulunya berwarna merah dan hitam, tetapi warna hitam sekarang telah digunakan ulang); hitam adalah ruang rumah; biru adalah alamat pengirim, yang merupakan offset ke fungsi pemanggil ke instruksi setelah panggilan; oranye adalah penyelarasan dan merah muda adalah tempat penunjuk instruksi mengarah tepat setelah panggilan dan sebelum instruksi pertama. Nilai homespace + kembali adalah bingkai terkecil yang diizinkan pada windows dan karena penyelarasan 16 byte rsp tepat di awal fungsi yang dipanggil harus dipertahankan, ini selalu menyertakan penyelarasan 8 byte juga.BaseThreadInitThunk dan seterusnya.

Bingkai fungsi berwarna merah menguraikan apa yang secara logis 'dimiliki' oleh fungsi callee + reads / modify (dapat memodifikasi parameter yang diteruskan pada stack yang terlalu besar untuk diteruskan dalam register pada -Ofast). Garis hijau membatasi ruang yang dialokasikan oleh fungsi itu sendiri dari awal hingga akhir fungsi.

Lewis Kelsey
sumber
RDI dan argumen register lainnya hanya akan tumpah ke stack jika Anda mengompilasi dalam mode debug, dan tidak ada jaminan bahwa kompilasi mengambil urutan tersebut. Juga, mengapa stack args tidak ditampilkan di bagian atas diagram untuk pemanggilan fungsi terlama? Tidak ada batasan yang jelas dalam diagram Anda antara frame mana yang "memiliki" data mana. (Callee memiliki stack args-nya). Menghilangkan argumen tumpukan dari bagian atas diagram membuatnya semakin sulit untuk melihat bahwa "parameter yang tidak dapat dilewatkan dalam register" selalu tepat di atas alamat pengirim dari setiap fungsi.
Peter Cordes
Output asm @PeterCordes goldbolt menunjukkan clang dan gcc callees mendorong parameter yang diteruskan dalam register ke stack sebagai perilaku default, sehingga memiliki alamat. Pada gcc menggunakan di registerbelakang parameter mengoptimalkan ini, tetapi Anda akan berpikir bahwa itu akan dioptimalkan tetap karena alamat tidak pernah diambil dalam fungsi. Saya akan memperbaiki bingkai atas; memang saya harus meletakkan elipsis dalam bingkai kosong terpisah. 'a callee memiliki stack argsnya', apa termasuk yang didorong oleh pemanggil jika tidak dapat diteruskan dalam register?
Lewis Kelsey
Ya, jika Anda mengkompilasi dengan pengoptimalan dinonaktifkan, callee akan menumpahkannya di suatu tempat. Tetapi tidak seperti posisi stack args (dan bisa dibilang disimpan-RBP), tidak ada yang distandarisasi tentang di mana. Re: callee memiliki stack args-nya: ya, fungsi diizinkan untuk mengubah arg yang masuk. Reg berpendapat bahwa tumpahan itu sendiri bukanlah argumen tumpukan. Kompiler terkadang melakukan ini, tetapi IIRC sering membuang ruang tumpukan dengan menggunakan spasi di bawah alamat pengirim meskipun mereka tidak pernah membaca ulang arg. Jika penelepon ingin melakukan panggilan lain dengan argumen yang sama, untuk amannya mereka harus menyimpan salinan lain sebelum mengulangicall
Peter Cordes
@PeterCordes Baiklah, saya membuat argumen sebagai bagian dari tumpukan pemanggil karena saya membatasi bingkai tumpukan berdasarkan di mana rbp poin. Beberapa diagram menunjukkan ini sebagai bagian dari tumpukan callee (seperti yang dilakukan diagram pertama pada pertanyaan ini) dan beberapa menampilkannya sebagai bagian dari tumpukan pemanggil, tapi mungkin masuk akal untuk menjadikannya bagian dari tumpukan callee melihat sebagai cakupan parameter tidak dapat diakses oleh penelepon di kode tingkat yang lebih tinggi. Ya, tampaknya registerdan constpengoptimalan hanya membuat perbedaan pada -O0.
Lewis Kelsey
@PeterCordes Saya mengubahnya. Saya mungkin mengubahnya lagi
Lewis Kelsey