Почему стопки обычно растут вниз?

96

Я знаю, что в архитектурах, с которыми я лично знаком (x86, 6502 и т.д.), стек обычно растет вниз (т.е. каждый элемент, помещенный в стек, приводит к уменьшению SP, а не к увеличению).

Мне интересно историческое обоснование этого. Я знаю, что в унифицированном адресном пространстве удобно начинать стек на противоположном конце сегмента данных (скажем), поэтому проблема возникает только в том случае, если две стороны сталкиваются посередине. Но почему стек традиционно получает верхнюю часть? Особенно с учетом того, насколько это противоположность «концептуальной» модели?

(И обратите внимание, что в архитектуре 6502 стек также растет вниз, даже если он ограничен одной 256-байтовой страницей, и этот выбор направления кажется произвольным.)

Бен Зотто
источник

Ответы:

52

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

В стороне, обратите внимание, что установка счетчика программ на 0 при сбросе не относится ко всем ранним процессорам. Например, Motorola 6809 будет получать счетчик программ с адресов, 0xfffe/fчтобы вы могли начать работу в произвольном месте, в зависимости от того, что было поставлено по этому адресу (обычно, но не ограничиваясь этим, ROM).

Одним из первых действий некоторых исторических систем будет сканирование памяти сверху, пока не будет найдено место, которое будет считывать то же записанное значение, чтобы узнать фактическую установленную оперативную память (например, z80 с адресным пространством 64 КБ не обязательно иметь 64 КБ или ОЗУ, на самом деле 64 КБ были бы огромными в мои первые дни). Как только он найдет верхний фактический адрес, он соответствующим образом установит указатель стека и сможет начать вызывать подпрограммы. Это сканирование обычно выполняется программным кодом ЦП в ПЗУ как часть запуска.

Что касается роста стеков, не все они растут вниз, подробности см. В этом ответе .

Paxdiablo
источник
1
Мне нравится история стратегии обнаружения RAM Z80. Имеет некоторый смысл в том, что текстовые сегменты расположены растущими вверх - в прошлом программисты имели более непосредственный контакт с последствиями этого, чем стек. Спасибо paxdiablo. Указатель на множество альтернативных форм реализации стека также очень интересен.
Бен Зотто
Разве у ранней памяти нет способа сообщить ее размер, и мы должны рассчитать его вручную?
phuclv
1
@ LưuVĩnhPhúc, полагаю, ты на поколение (или два) позади меня. Я до сих пор помню метод TRS-80 model 3 для получения даты и времени, когда нужно спрашивать об этом у пользователя во время загрузки. Когда-то считалось, что наличие сканера памяти для установки верхнего предела памяти - это настоящее искусство :-) Можете ли вы представить, что произойдет, если Windows будет запрашивать время или сколько памяти у вас каждый раз при загрузке?
paxdiablo
1
Действительно, в документации Zilog Z80 сказано, что часть запускается с установки регистра ПК на 0000h и выполнения. Он устанавливает режим прерывания на 0, отключает прерывания и также устанавливает регистры I и R на 0. После этого он начинает выполняться. В 0000h запускается код. Этот код должен инициализировать указатель стека, прежде чем он сможет вызвать подпрограмму или разрешить прерывания. Какой поставщик продает Z80, который ведет себя так, как вы описываете?
MikeB
1
Майк, извини, я должен был быть яснее. Когда я сказал, что ЦП сканирует память, я не имел в виду, что это была особенность самого ЦП. Фактически он управлялся программой в ПЗУ. Я уточню.
paxdiablo
21

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

Anq
источник
8

Стэнли Мазор (архитектор 4004 и 8080) объясняет, как было выбрано направление роста стека для 8080 (и, в конечном итоге, для 8086) в статье «Микропроцессоры Intel: от 8008 до 8086» :

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

рулебо
источник
6

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

Jalf
источник
1
Компьютеры не вычитают; они добавляют 2 комплимента. Все, что делается путем вычитания, на самом деле делается путем добавления. Учтите, что в компьютерах есть сумматоры, а не вычитатели.
jww
1
@jww - это различие без разницы. Я мог бы сказать, что компьютеры не прибавляют, а только вычитают! Для целей этого ответа это не имеет особого значения, но большинство ALU будут использовать схему, которая поддерживает как сложение, так и вычитание с одинаковой производительностью. То есть, хотя A - Bконцептуально может быть реализовано как A + (-B)(т. Е. Как отдельный шаг отрицания для B), на практике это не так.
BeeOnRope
@jww Ваша придирка не подходит для ранних компьютеров - потребовалось некоторое время для победы над дополнением до двух, а пока это не произошло, были компьютеры, использующие дополнение, знак и величину и, возможно, другие вещи. В этих реализациях могло быть преимущество сложения перед вычитанием. Таким образом, в отсутствие дополнительной информации неправильно исключать это как возможный фактор, влияющий на выбор схемы адресации, такой как направление стека.
mtraceur
4

IIRC стек растет вниз, потому что куча растет вверх. Все могло быть наоборот.

Кристиан V
источник
5
Восходящая куча позволяет в некоторых случаях эффективно перераспределять память, но нисходящая куча практически никогда не делает этого.
Питер Кордес
@PeterCordes, почему?
Яшас
3
@Yashas: потому что realloc(3)нужно больше места после объекта, чтобы просто расширить отображение без копирования. Повторное перераспределение одного и того же объекта возможно, если за ним следует произвольное количество неиспользуемого пространства.
Питер Кордес
2

Я считаю, что это чисто дизайнерское решение. Не все из них растут вниз - см. Эту ветку SO, где подробно обсуждается направление роста стека на разных архитектурах.

Калеб Брази
источник
1

Я считаю, что соглашение началось с IBM 704 и его печально известного «регистра декремента». В современной речи это поле смещения инструкции, но дело в том, что они пошли вниз , а не вверх .

Люзер Дрог
источник
1

Еще 2с:

Помимо всех упомянутых исторических причин, я совершенно уверен, что для современных процессоров нет никаких оснований. Все процессоры могут принимать смещения со знаком, и максимизация расстояния кучи / стека довольно спорна с тех пор, как мы начали иметь дело с несколькими потоками.

Я лично считаю это недостатком системы безопасности. Если бы, скажем, разработчики архитектуры x64 изменили направление роста стека на противоположное, большинство переполнений буфера стека было бы устранено, что в некотором роде имеет большое значение. (поскольку струны растут вверх).

Офек Шилон
источник
0

Я не уверен, но в свое время я занимался программированием для VAX / VMS. Кажется, я помню, как одна часть памяти (куча ??) поднималась вверх, а стек опускался. Когда эти двое встретились, вы были вне памяти.

Мартин
источник
1
Это правда, но тогда почему куча растет вверх, а не наоборот?
Чиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
0

Одним из преимуществ нисходящего роста стека в минимальной встроенной системе является то, что один фрагмент ОЗУ может быть избыточно отображен как на страницу O, так и на страницу 1, что позволяет назначать нулевые переменные страницы, начиная с 0x000, а стек растет вниз от 0x1FF, максимально увеличивая количество, которое оно должно было бы увеличиться перед перезаписью переменных.

Одна из первоначальных целей дизайна 6502 заключалась в том, чтобы его можно было объединить, например, с 6530, в результате чего получилась двухчиповая микроконтроллерная система с 1 КБ программной ПЗУ, таймером, вводом-выводом и 64 байтами общей оперативной памяти между переменными стека и нулевой страницы. Для сравнения, минимальная встраиваемая система того времени на базе 8080 или 6800 состояла бы из четырех или пяти микросхем.

Милан
источник