Стек растет вверх или вниз?

У меня есть этот фрагмент кода в 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);

Результат:

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

Итак, я вижу, что от aдо a[2]адреса памяти увеличиваются на 4 байта каждый. Но от qдо sадреса памяти уменьшаются на 4 байта.

Интересно 2 вещи:

1. Стек растет или опускается? (В этом случае мне кажется, что оба)
2. Что происходит между адресами памяти a[2]и q? Почему там большая разница памяти? (20 байт).

Примечание: это не вопрос домашнего задания. Мне любопытно, как работает стек. Спасибо за любую помощь.

Поведение стека (рост или уменьшение) зависит от двоичного интерфейса приложения (ABI) и того, как организован стек вызовов (также известный как запись активации).

На протяжении всей своей жизни программа обязана взаимодействовать с другими программами, такими как ОС. ABI определяет, как программа может взаимодействовать с другой программой.

Стек для разных архитектур может расти в любом случае, но для архитектуры он будет согласованным. Пожалуйста, проверьте эту ссылку в вики. Но рост стека определяется ABI этой архитектуры.

Например, если вы возьмете MIPS ABI, стек вызовов определяется следующим образом.

Давайте рассмотрим, что функция «fn1» вызывает «fn2». Теперь кадр стека, который видит 'fn2', выглядит следующим образом:

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

Теперь вы можете видеть, что стек растет вниз. Таким образом, если переменные размещены в локальном фрейме функции, адреса переменных фактически растут вниз. Компилятор может выбрать порядок переменных для выделения памяти. (В вашем случае это может быть либо 'q', либо 's', которое является первой выделенной памятью стека. Но, как правило, компилятор выделяет память стека в соответствии с порядком объявления переменных).

Но в случае массивов выделение имеет только один указатель, и память, которую необходимо выделить, будет фактически указана одним указателем. Для массива память должна быть непрерывной. Итак, хотя стек растет вниз, для массивов стек растет вверх.

На самом деле это два вопроса. Один касается того, как растет стек, когда одна функция вызывает другую (когда выделяется новый фрейм), а другой касается того, как переменные размещаются в кадре конкретной функции.

Ни то, ни другое не указано в стандарте C, но ответы немного отличаются:

• В каком направлении увеличивается стек при выделении нового кадра - если функция f () вызывает функцию g (), будет ли fуказатель кадра больше или меньше gуказателя кадра? Это может происходить любым путем - это зависит от конкретного компилятора и архитектуры (см. «Соглашение о вызовах»), но всегда согласовано в рамках данной платформы (за некоторыми причудливыми исключениями, см. Комментарии). Вниз встречается чаще; это относится к x86, PowerPC, MIPS, SPARC, EE и Cell SPU.
• Как локальные переменные функции располагаются внутри ее кадра стека? Это не указано и совершенно непредсказуемо; компилятор может упорядочивать свои локальные переменные, однако ему нравится получать наиболее эффективный результат.

Направление роста стеков зависит от архитектуры. Тем не менее, насколько я понимаю, только очень немногие аппаратные архитектуры имеют растущие стеки.

Направление роста стека не зависит от компоновки отдельного объекта. Таким образом, хотя стек может увеличиваться, массивы - нет (т.е. & array [n] всегда будет <& array [n + 1]);

В стандарте нет ничего, что определяло бы, как вещи вообще организованы в стеке. Фактически, вы могли бы создать соответствующий компилятор, который вообще не хранил бы элементы массива в смежных элементах в стеке, при условии, что у него был ум, чтобы по-прежнему правильно выполнять арифметические операции с элементами массива (чтобы он знал, например, что 1 было 1K от [0] и можно было бы отрегулировать для этого).

Причина, по которой вы можете получать разные результаты, заключается в том, что, хотя стек может увеличиваться вниз для добавления к нему «объектов», массив является одним «объектом», и он может иметь восходящие элементы массива в противоположном порядке. Но полагаться на такое поведение небезопасно, поскольку направление может меняться, а переменные можно менять местами по разным причинам, включая, помимо прочего:

• оптимизация.
• выравнивание.
• капризы человека - часть компилятора, управляющая стеком.

Смотрите здесь мой отличный трактат о направлении стека :-)

В ответ на ваши конкретные вопросы:

1. Стек растет или опускается?
   Это вообще не имеет значения (с точки зрения стандарта), но, поскольку вы спросили, он может увеличиваться или уменьшаться в памяти, в зависимости от реализации.
2. Что происходит между адресами памяти a [2] и q? Почему там большая разница памяти? (20 байт)?
   Совсем не важно (с точки зрения стандарта). См. Возможные причины выше.

На x86 «выделение» памяти для кадра стека состоит просто из вычитания необходимого количества байтов из указателя стека (я считаю, что другие архитектуры похожи). В этом смысле, я предполагаю, что стек растет «вниз», поскольку адреса становятся все меньше по мере того, как вы вызываете более глубоко в стек (но я всегда представляю, что память начинается с 0 в верхнем левом углу и получает большие адреса при перемещении вправо и завернуть вниз, так что в моем мысленном образе стек растет ...). Порядок объявляемых переменных может не иметь никакого отношения к их адресам - я считаю, что стандарт позволяет компилятору переупорядочивать их, если это не вызывает побочных эффектов (кто-нибудь, пожалуйста, поправьте меня, если я ошибаюсь) . Oни'

Зазор вокруг массива может быть чем-то вроде прокладки, но для меня это загадочно.

Прежде всего, это 8 байтов неиспользуемого пространства в памяти (его не 12, помните, что стек растет вниз, поэтому пространство, которое не выделяется, составляет от 604 до 597). и почему?. Потому что каждый тип данных занимает место в памяти, начиная с адреса, кратного его размеру. В нашем случае массив из 3 целых чисел занимает 12 байтов в памяти, а 604 не делится на 12. Таким образом, он оставляет пустые места, пока не встретит адрес памяти, который делится на 12, это 596.

Таким образом, объем памяти, выделенный для массива, составляет от 596 до 584. Но поскольку выделение массива продолжается, первый элемент массива начинается с адреса 584, а не с 596.

Компилятор может размещать локальные (автоматические) переменные в любом месте фрейма локального стека, вы не можете достоверно вывести направление роста стека только на основании этого. Вы можете определить направление роста стека, сравнивая адреса вложенных фреймов стека, то есть сравнивая адрес локальной переменной внутри фрейма стека функции с вызываемой:

#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;
}

Я не думаю, что это так детерминировано. Кажется, что массив a "растет", потому что эта память должна выделяться непрерывно. Однако, поскольку q и s вообще не связаны друг с другом, компилятор просто вставляет каждый из них в произвольную свободную ячейку памяти в стеке, возможно, ту, которая лучше всего подходит к целочисленному размеру.

Между a [2] и q произошло то, что пространство вокруг местоположения q было недостаточно большим (т.е. не превышало 12 байт) для размещения массива из трех целых чисел.

Кажется, что мой стек расширяется в сторону адресов с меньшими номерами.

Это может быть иначе на другом компьютере или даже на моем компьютере, если я использую другой вызов компилятора. ... или компилятор может вообще не использовать стек (встроить все (функции и переменные, если я не взял их адрес)).

$ 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
уровень 4: x находится на 0x7fff7781190c
уровень 3: x находится на 0x7fff778118ec
уровень 2: x находится на 0x7fff778118cc
уровень 1: x находится на 0x7fff778118ac
уровень 0: x находится на 0x7fff7781188c

Стек растет вниз (на x86). Однако при загрузке функции стек выделяется в одном блоке, и у вас нет гарантии, в каком порядке элементы будут располагаться в стеке.

В этом случае он выделил место для двух целых чисел и массива из трех целых чисел в стеке. Он также выделил дополнительные 12 байтов после массива, поэтому он выглядит так:

a [12 байтов]
заполнение (?) [12 байтов]
s [4 байта]
q [4 байта]

По какой-то причине ваш компилятор решил, что для этой функции необходимо выделить 32 байта, а возможно и больше. Это непонятно для вас, как программиста на C, вы не знаете почему.

Если вы хотите знать, почему, скомпилируйте код на язык ассемблера, я считаю, что это -S в gcc и / S в компиляторе C. Если вы посмотрите на инструкции по открытию этой функции, вы увидите, что старый указатель стека сохраняется, а затем из него вычитается 32 (или что-то еще!). Отсюда вы можете увидеть, как код обращается к этому 32-байтовому блоку памяти, и выяснить, что делает ваш компилятор. В конце функции вы можете увидеть восстанавливаемый указатель стека.

Это зависит от вашей операционной системы и вашего компилятора.

Стек действительно растет. Итак, f (g (h ())), стек, выделенный для h, будет начинаться с меньшего адреса, тогда g и g будут ниже, чем f. Но переменные в стеке должны соответствовать спецификации C,

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

1206 Если указанные объекты являются членами одного и того же агрегатного объекта, указатели на члены структуры, объявленные позже, сравниваются больше, чем указатели на члены, объявленные ранее в структуре, а указатели на элементы массива с большими значениями нижних индексов сравниваются больше, чем указатели на элементы того же массив с нижними значениями индекса.

& a [0] <& a [1], всегда должно быть истинным, независимо от того, как 'a' назначен

растет вниз, и это происходит из-за стандарта порядка байтов с обратным порядком байтов, когда речь идет о наборе данных в памяти.

Один из способов, которым вы могли бы это увидеть, - это то, что стек ДЕЙСТВИТЕЛЬНО растет вверх, если вы посмотрите на память от 0 сверху и max снизу.

Причина увеличения стека вниз заключается в возможности разыменования с точки зрения стека или базового указателя.

Помните, что разыменование любого типа увеличивается от наименьшего к наибольшему адресу. Поскольку стек растет вниз (от самого высокого до самого низкого адреса), это позволяет вам рассматривать стек как динамическую память.

Это одна из причин, почему так много языков программирования и сценариев используют виртуальную машину на основе стека, а не на основе регистров.

Это зависит от архитектуры. Чтобы проверить свою систему, используйте этот код от 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; 
}