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 a
dan b
, tetapi itu berarti OS / CPU (?) Harus keluar d
dan c
pertama kembali ke a
dan b
. Tapi kemudian ia akan menembak dirinya sendiri di kaki, karena ia membutuhkan c
dan d
di 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 doSomething
pada dasarnya menunjuk ke alamat memori yang sama seperti a
dan b
di foo
. Tetapi sekali lagi ini berarti bahwa tidak ada munculan tumpukan sampai kita sampai a
danb
terjadi.
Kedua kasus itu membuat saya berpikir bahwa saya belum sepenuhnya memahami bagaimana tepatnya tumpukan bekerja dan bagaimana itu secara ketat mengikuti aturan LIFO .
LIFO
artinya Anda dapat menambah atau menghapus elemen hanya di akhir tumpukan, dan Anda selalu dapat membaca / mengubah elemen apa pun.Jawaban:
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 :
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
gcc.godbolt.org memberi kita
.. untuk
main
. Saya membagi kode menjadi tiga subbagian. Prolog fungsi terdiri dari tiga operasi pertama:Kemudian
cin
dipindahkan ke EDI register 2 danget
dipanggil; 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 berikutnyac
di EAX: EAX dipindahkan ke ESI,cout
dipindahkan ke EDI dan kemudian operator penyisipan dipanggil dengancout
danc
menjadi argumennya.Akhirnya,
main
disimpan dalam EAX: 0. Itu karenareturn
pernyataan implisit . Anda mungkin juga melihat,xorl rax rax
bukanmovl
.leave
menyingkat epilog ini dan secara implisitSetelah operasi ini dan
ret
dilakukan, 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 keret
.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-pointer
GCC dan-Oy
Clang; 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.
sumber
rbp
untuk melakukan pekerjaan lain.Pendeknya:
Tidak perlu melontarkan argumen. Argumen yang diteruskan oleh pemanggil
foo
ke fungsidoSomething
dan variabel lokal didoSomething
semua dapat direferensikan sebagai offset dari penunjuk dasar .Begitu,
Secara terperinci:
Aturannya adalah bahwa setiap panggilan fungsi menghasilkan pembuatan bingkai tumpukan (dengan alamat minimum yang akan dikembalikan). Jadi, jika
funcA
panggilanfuncB
danfuncB
panggilanfuncC
, 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).Tumpukan dalam pertanyaan Anda disiapkan oleh pemanggil
foo
. KetikadoSomething
dandoAnotherThing
dipanggil, maka mereka mengatur tumpukan mereka sendiri. Angka tersebut dapat membantu Anda untuk memahami ini: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.
Lihatlah kode C berikut untuk pembentukan bingkai tumpukan fungsi:
Saat penelepon menyebutnya
kode berikut akan dibuat
dan kode perakitan untuk fungsi tersebut akan (diatur oleh callee sebelum kembali)
Referensi:
sumber
EBP
danESP
?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:
Poin-poin dalam waktu
T1, T2, etc
. ditandai dalam kode dan status memori pada saat itu ditunjukkan pada gambar:sumber
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,4
setelah setiap panggilan, gunakan satuADD SP,16
setelah 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.
sumber
(g==4)
kemudianint d = 3
dang
saya mengambil input menggunakanscanf
setelah itu saya mendefinisikan variabel lainint h = 5
. Sekarang, bagaimana kompilator sekarang memberid = 3
ruang di tumpukan. Bagaimana offset dilakukan karena jikag
tidak4
, maka tidak akan ada memori untuk d di stack dan offset akan diberikan keh
dan jikag == 4
offset akan menjadi yang pertama untuk g dan kemudian untukh
. Bagaimana kompilator melakukannya pada waktu kompilasi, ia tidak mengetahui masukan kita untukg
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.
sumber
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:
http://en.wikipedia.org/wiki/Random-access_machine
sumber
Berikut adalah diagram yang saya buat untuk tumpukan panggilan C. Ini lebih akurat dan kontemporer daripada versi gambar google
Dan sesuai dengan struktur yang tepat dari diagram di atas, berikut adalah debug dari notepad.exe x64 di windows 7.
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.
sumber
register
belakang 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?call
register
danconst
pengoptimalan hanya membuat perbedaan pada -O0.