Apakah tumpukan tumbuh ke atas atau ke bawah?

Saya memiliki potongan kode ini di c:

int q = 10;
int s = 5;
int a[3];

printf("Address of a: %d\n",    (int)a);
printf("Address of a[1]: %d\n", (int)&a[1]);
printf("Address of a[2]: %d\n", (int)&a[2]);
printf("Address of q: %d\n",    (int)&q);
printf("Address of s: %d\n",    (int)&s);

Outputnya adalah:

Address of a: 2293584
Address of a[1]: 2293588
Address of a[2]: 2293592
Address of q: 2293612
Address of s: 2293608

Jadi, saya melihat bahwa dari ake a[2], alamat memori masing-masing bertambah 4 byte. Tapi dari qke s, alamat memori berkurang 4 byte.

Saya bertanya-tanya 2 hal:

1. Apakah tumpukan tumbuh ke atas atau ke bawah? (Sepertinya keduanya bagi saya dalam kasus ini)
2. Apa yang terjadi antara a[2]dan qalamat memori? Mengapa ada perbedaan memori yang besar di sana? (20 byte).

Catatan: Ini bukan pertanyaan pekerjaan rumah. Saya ingin tahu tentang cara kerja tumpukan. Terima kasih atas bantuannya.

Perilaku tumpukan (tumbuh atau berkembang ke bawah) bergantung pada antarmuka biner aplikasi (ABI) dan bagaimana tumpukan panggilan (alias catatan aktivasi) diatur.

Sepanjang masa hidupnya program terikat untuk berkomunikasi dengan program lain seperti OS. ABI menentukan bagaimana suatu program dapat berkomunikasi dengan program lain.

Tumpukan untuk arsitektur yang berbeda dapat berkembang dengan cara apa pun, tetapi untuk arsitektur akan konsisten. Silakan periksa tautan wiki ini . Namun, pertumbuhan tumpukan ditentukan oleh ABI arsitektur tersebut.

Misalnya, jika Anda menggunakan MIPS ABI, tumpukan panggilan ditentukan seperti di bawah ini.

Mari kita pertimbangkan bahwa fungsi 'fn1' memanggil 'fn2'. Sekarang bingkai tumpukan seperti yang terlihat oleh 'fn2' adalah sebagai berikut:

direction of     |                                 |
  growth of      +---------------------------------+ 
   stack         | Parameters passed by fn1(caller)|
from higher addr.|                                 |
to lower addr.   | Direction of growth is opposite |
      |          |   to direction of stack growth  |
      |          +---------------------------------+ <-- SP on entry to fn2
      |          | Return address from fn2(callee) | 
      V          +---------------------------------+ 
                 | Callee saved registers being    | 
                 |   used in the callee function   | 
                 +---------------------------------+
                 | Local variables of fn2          |
                 |(Direction of growth of frame is |
                 | same as direction of growth of  |
                 |            stack)               |
                 +---------------------------------+ 
                 | Arguments to functions called   |
                 | by fn2                          |
                 +---------------------------------+ <- Current SP after stack 
                                                        frame is allocated

Sekarang Anda dapat melihat tumpukan tumbuh ke bawah. Jadi, jika variabel dialokasikan ke kerangka lokal fungsi, alamat variabel sebenarnya tumbuh ke bawah. Kompilator dapat memutuskan urutan variabel untuk alokasi memori. (Dalam kasus Anda, ini bisa berupa 'q' atau 's' yang pertama kali dialokasikan memori tumpukan. Tetapi, umumnya kompilator melakukan alokasi memori tumpukan sesuai urutan deklarasi variabel).

Tetapi dalam kasus array, alokasi hanya memiliki satu pointer dan memori yang perlu dialokasikan akan diarahkan oleh satu pointer. Memori harus bersebelahan untuk sebuah array. Jadi, meskipun tumpukan tumbuh ke bawah, untuk array, tumpukan tumbuh.

Ini sebenarnya dua pertanyaan. Pertama tentang cara tumpukan tumbuh ketika satu fungsi memanggil yang lain (ketika bingkai baru dialokasikan), dan yang lainnya adalah tentang bagaimana variabel ditata dalam bingkai fungsi tertentu.

Tidak ada yang ditentukan oleh standar C, tetapi jawabannya sedikit berbeda:

• Dengan cara manakah tumpukan bertambah ketika bingkai baru dialokasikan - jika fungsi f () memanggil fungsi g (), apakah fpenunjuk bingkai akan lebih besar atau lebih kecil dari gpenunjuk bingkai? Ini bisa dilakukan dengan cara apa pun - tergantung pada kompiler dan arsitektur tertentu (cari "konvensi pemanggil"), tetapi selalu konsisten dalam platform tertentu (dengan beberapa pengecualian aneh, lihat komentar). Ke bawah lebih umum; itu kasus di x86, PowerPC, MIPS, SPARC, EE, dan Cell SPU.
• Bagaimana variabel lokal suatu fungsi diletakkan di dalam bingkai tumpukannya? Ini tidak ditentukan dan sama sekali tidak dapat diprediksi; kompilator bebas mengatur variabel lokalnya, bagaimanapun ia ingin mendapatkan hasil yang paling efisien.

Arah pertumbuhan tumpukan adalah spesifik arsitektur. Yang mengatakan, pemahaman saya adalah bahwa hanya sedikit arsitektur perangkat keras yang memiliki tumpukan yang tumbuh.

Arah pertumbuhan tumpukan tidak bergantung pada tata letak objek individu. Jadi, meskipun tumpukan mungkin bertambah kecil, array tidak akan (yaitu & array [n] akan selalu menjadi <& array [n + 1]);

Tidak ada dalam standar yang mengamanatkan bagaimana hal-hal diatur di tumpukan sama sekali. Faktanya, Anda dapat membuat kompiler yang sesuai yang tidak menyimpan elemen array pada elemen yang berdekatan di stack sama sekali, asalkan ia memiliki kecerdasan untuk tetap melakukan aritmatika elemen array dengan benar (sehingga ia tahu, misalnya, bahwa 1 adalah 1K dari [0] dan bisa menyesuaikan untuk itu).

Alasan Anda mungkin mendapatkan hasil yang berbeda adalah karena, meskipun tumpukan mungkin bertambah ke bawah untuk menambahkan "objek" ke dalamnya, array adalah "objek" tunggal dan mungkin memiliki elemen array naik dalam urutan yang berlawanan. Tetapi tidak aman untuk mengandalkan perilaku itu karena arah dapat berubah dan variabel dapat ditukar karena berbagai alasan termasuk, tetapi tidak terbatas pada:

• optimasi.
• penjajaran.
• keinginan orang bagian manajemen tumpukan dari kompilator.

Lihat di sini untuk risalah saya yang sangat baik tentang arah tumpukan :-)

Sebagai jawaban atas pertanyaan spesifik Anda:

1. Apakah tumpukan tumbuh ke atas atau ke bawah?
   Tidak masalah sama sekali (dalam hal standar) tetapi, karena Anda bertanya, itu bisa naik atau turun dalam memori, tergantung pada implementasinya.
2. Apa yang terjadi antara alamat memori [2] dan q? Mengapa ada perbedaan memori yang besar di sana? (20 byte)?
   Tidak masalah sama sekali (dalam hal standar). Lihat di atas untuk kemungkinan alasan.

Pada x86, "alokasi" memori dari bingkai tumpukan terdiri dari pengurangan jumlah byte yang diperlukan dari penunjuk tumpukan (saya yakin arsitektur lain serupa). Dalam hal ini, saya kira tumpukan bertambah "turun", di mana alamat menjadi semakin kecil saat Anda memanggil lebih dalam ke tumpukan (tapi saya selalu membayangkan memori dimulai dengan 0 di kiri atas dan mendapatkan alamat yang lebih besar saat Anda bergerak ke kanan dan membungkus, jadi dalam bayangan mental saya tumpukan tumbuh ...). Urutan variabel yang dideklarasikan mungkin tidak ada hubungannya dengan alamat mereka - Saya percaya standar memungkinkan compiler untuk menyusunnya kembali, selama tidak menimbulkan efek samping (seseorang tolong perbaiki saya jika saya salah) . Mereka'

Celah di sekitar array mungkin semacam padding, tapi itu misterius bagi saya.

Pertama-tama, 8 byte ruang yang tidak terpakai dalam memori (bukan 12, ingat tumpukan tumbuh ke bawah, Jadi ruang yang tidak dialokasikan dari 604 menjadi 597). dan mengapa?. Karena setiap tipe data membutuhkan ruang dalam memori mulai dari alamat yang habis dibagi ukurannya. Dalam kasus kita, array 3 bilangan bulat mengambil 12 byte ruang memori dan 604 tidak habis dibagi 12. Jadi meninggalkan ruang kosong sampai menemukan alamat memori yang habis dibagi 12, yaitu 596.

Jadi ruang memori yang dialokasikan untuk array adalah dari 596 sampai 584. Tetapi karena alokasi array dalam kelanjutan, maka elemen pertama dari array dimulai dari alamat 584 dan bukan dari 596.

Compiler bebas mengalokasikan variabel lokal (otomatis) di sembarang tempat pada frame stack lokal, Anda tidak dapat secara andal menyimpulkan arah pertumbuhan stack hanya dari situ. Anda dapat menyimpulkan arah pertumbuhan tumpukan dari membandingkan alamat bingkai tumpukan bersarang, yaitu membandingkan alamat variabel lokal di dalam bingkai tumpukan suatu fungsi dibandingkan dengan kalendernya:

#include <stdio.h>
int f(int *x)
{
  int a;
  return x == NULL ? f(&a) : &a - x;
}

int main(void)
{
  printf("stack grows %s!\n", f(NULL) < 0 ? "down" : "up");
  return 0;
}

Saya tidak berpikir itu deterministik seperti itu. Array tampaknya "tumbuh" karena memori itu harus dialokasikan secara berdekatan. Namun, karena q dan s sama sekali tidak terkait satu sama lain, compiler hanya menempelkan masing-masingnya di lokasi memori bebas sembarang dalam tumpukan, mungkin yang paling cocok dengan ukuran integer.

Apa yang terjadi antara a [2] dan q adalah bahwa ruang di sekitar lokasi q tidak cukup besar (yaitu, tidak lebih besar dari 12 byte) untuk mengalokasikan array bilangan bulat 3.

Tumpukan saya tampaknya meluas ke alamat bernomor lebih rendah.

Ini mungkin berbeda di komputer lain, atau bahkan di komputer saya sendiri jika saya menggunakan pemanggilan kompiler yang berbeda. ... atau kompilator muigt memilih untuk tidak menggunakan tumpukan sama sekali (semua sebaris (fungsi dan variabel jika saya tidak mengambil alamatnya)).

$ cat stack.c
#include <stdio.h>

int stack(int x) {
  printf("level %d: x is at %p\n", x, (void*)&x);
  if (x == 0) return 0;
  return stack(x - 1);
}

int main(void) {
  stack(4);
  return 0;
}

$ / usr / bin / gcc -Wall -Wextra -std = c89 -pedantic stack.c

$ ./a.out
level 4: x berada di 0x7fff7781190c
level 3: x berada di 0x7fff778118ec
level 2: x berada di 0x7fff778118cc
level 1: x berada di 0x7fff778118ac
level 0: x berada di 0x7fff7781188c

Tumpukan tumbuh ke bawah (pada x86). Namun, tumpukan dialokasikan dalam satu blok saat fungsi dimuat, dan Anda tidak memiliki jaminan urutan item apa yang akan ada di tumpukan.

Dalam kasus ini, ini mengalokasikan ruang untuk dua int dan array tiga int pada stack. Itu juga mengalokasikan tambahan 12 byte setelah array, sehingga terlihat seperti ini:

a [12 byte]
padding (?) [12 byte]
s [4 byte]
q [4 byte]

Untuk alasan apa pun, kompilator Anda memutuskan bahwa ia perlu mengalokasikan 32 byte untuk fungsi ini, dan mungkin lebih. Itu tidak jelas bagi Anda sebagai programmer C, Anda tidak tahu alasannya.

Jika Anda ingin tahu alasannya, kompilasi kode ke bahasa assembly, saya yakin -S ada di gcc dan / S di kompiler C MS. Jika Anda melihat petunjuk pembukaan untuk fungsi itu, Anda akan melihat penunjuk tumpukan lama disimpan dan kemudian 32 (atau yang lainnya!) Dikurangkan darinya. Dari sana, Anda dapat melihat bagaimana kode mengakses blok memori 32-byte itu dan mencari tahu apa yang dilakukan kompiler Anda. Di akhir fungsi, Anda dapat melihat penunjuk tumpukan dipulihkan.

Itu tergantung pada sistem operasi dan kompiler Anda.

Tumpukan tumbuh turun. Jadi f (g (h ())), stack yang dialokasikan untuk h akan mulai dari alamat yang lebih rendah kemudian g dan g akan lebih rendah dari f. Tetapi variabel dalam tumpukan harus mengikuti spesifikasi C,

http://c0x.coding-guidelines.com/6.5.8.html

1206 Jika objek yang ditunjuk adalah anggota dari objek agregat yang sama, pointer ke anggota struktur dideklarasikan kemudian bandingkan lebih besar dari pointer ke anggota yang dideklarasikan sebelumnya dalam struktur, dan pointer ke elemen array dengan nilai subskrip yang lebih besar membandingkan lebih besar dari pointer ke elemen yang sama array dengan nilai subskrip yang lebih rendah.

& a [0] <& a [1], harus selalu benar, terlepas dari bagaimana 'a' dialokasikan

tumbuh ke bawah dan ini karena standar urutan byte endian kecil ketika datang ke kumpulan data dalam memori.

Salah satu cara untuk melihatnya adalah bahwa tumpukan TIDAK tumbuh ke atas jika Anda melihat memori dari 0 dari atas dan maks dari bawah.

Alasan tumpukan tumbuh ke bawah adalah untuk dapat membedakan dari perspektif tumpukan atau penunjuk dasar.

Ingatlah bahwa dereferensi jenis apa pun meningkat dari alamat terendah ke tertinggi. Karena Stack tumbuh ke bawah (alamat tertinggi ke terendah), ini memungkinkan Anda memperlakukan stack seperti memori dinamis.

Inilah salah satu alasan mengapa begitu banyak bahasa pemrograman dan skrip menggunakan mesin virtual berbasis stack daripada berbasis register.

Itu tergantung pada arsitekturnya. Untuk memeriksa sistem Anda sendiri, gunakan kode ini dari GeeksForGeeks :

// C program to check whether stack grows 
// downward or upward. 
#include<stdio.h> 

void fun(int *main_local_addr) 
{ 
    int fun_local; 
    if (main_local_addr < &fun_local) 
        printf("Stack grows upward\n"); 
    else
        printf("Stack grows downward\n"); 
} 

int main() 
{ 
    // fun's local variable 
    int main_local; 

    fun(&main_local); 
    return 0; 
}