Стек

Для динамического хранения локальных переменных и адресов возврата нам нужен стек.

Абстракция «стек»

Хранилище «объектов»

• Основные операции — положить на стек, снять со стека
• Основной доступ — последовательный, к верхнему элементу стека
  • Иногда разрешается относительный доступ к N-му элементу стека от вершины
• ⇒ «Первым вошёл — последним вышел»
• Может расти бесконечно
• Поведение при исчерпании (снятии с пустого стека) не определено

Реализация стека в машинных кодах

• «Объект» — обычно ячейка
• в некоторых архитектурах можно было бы хранить объекты разной длины (байты, полуслова, слова и т. п.), но задача доступа к N-му элементу стека из константной становится линейной сложности, и надо хранить где-то размеры ячеек
• Хранилище — область памяти, ограниченная только с одной стороны («дно» стека), а с другой — «бесконечно» растущая (пока не достигнет занятой области памяти)
• Рост/снятие: специальная ячейка памяти, хранящая адрес вершины стека + знание адреса дна сетка
  • Используется косвенная адресация
  • ⇒ Удобно (на некоторых архитектурах — единственно возможно) хранить в регистре
  • Переполнение (попытку положить на стек больше значений, чем предусмотрено конвенцией) надо как-то проверять
  • Исчерпание (попытку снять со стека больше значений, чем там есть в данный момент) тоже надо как-то проверять

Возможная аппаратная поддержка стека

• Отдельный небольшой стек на регистровой памяти

  • а чем он лучше того же числа регистров? (нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер) Организацией доступа. Поскольку аппаратный стек не надо адресовать вручную, его можно сделать довольно глубоким, на сложности команд или самого процессора это не скажется никак. Плюс можно организовать его не пословно, а поблочно, чтобы за раз записывать сразу все s-регистры в одну "ячейку". Примерно так сделано в контроллерах ch32 (в других контроллерах — иначе!): аппаратный стек на 2-4 уровня, в которой аппаратно же сохраняются s-регистры при входе в прерывание. Для каких прерываний использовать аппаратный стек, а для каких — обычный настраивается в специальных управляющих регистрах. То есть самым критичным прерываниям назначаем максимальный приоритет и выделяем аппаратный стек, а всем остальным - обычный.

• Атомарные операции добавления/снятия (в обычном случае действия два: чтение/запись значения и изменение указателя)
  • Например, автоувеличение/автоуменьшение указателя прямо в процессе взятия значения
    • В случае программного стека, как в RISC-V, эта операция не такая уж частая. На стек кладётся обычно не одно значение, а несколько, так что эффективнее сначала изменить указатель сразу на требуемое под все значения смещение, а затем заполнить память значениями.

• Двойная косвенная адресация позволяет напрямую обращаться к данным, адреса которых лежат в стеке

  • Соответствует использованию указателей в Си, и сильно упрощает программисту реализацию любых структур с указателями (например, связных списков)

  • В случае RISC-V — недопустимо «тяжёлое» двойное обращение к памяти

Реализация стека в RARS

…регулируется соотв. конвенцией:

• Выделенный регистр sp (x2)

• Дно стека — 0x7ffffffc (непосредственно под областью ядра)

• Начальное значение 0x7fffeffc отделено от дна буфером

• Стек растёт вниз по одному слову (4 байта)

• Предел стека — область кучи (0x10040000 или выше, если куча наросла), определяется вручную или ядром операционной системы

• Операции добавления и снятия — неатомарные:

  • при добавлении сначала уменьшается указатель, затем записывается значение
  • при снятии сначала считывается значение, затем увеличивается указатель

  • при такой организации не используется исходная ячейка стека — 0x7fffeffc

• пример:

     1         li t1 123        # какое-то значение
     2         addi sp sp -4    # положить на стек - 1
     3         sw t1 (sp)       # положить на стек - 2
     4         addi t2 t1 100   # какое-то ещё значение
     5         addi sp sp -4    # положить на стек - 1
     6         sw t2 (sp)       # положить на стек - 2
     7         lw t3 (sp)       # доступ к вершине стека
     8         lw t4 4(sp)      # доступ ко второму элементу стека
     9         lw t0 (sp)       # снятие со стека - 1
    10         addi sp sp 4     # снятие со стека - 2
    11         addi sp sp -4    # положить на стек - 1
    12         sw zero (sp)     # положить на стек - 2
  

• Это довольно эффективный код, не содержащий ни одной составной псевдоинструкции:

  Address     Code        Basic                        Line Source
  
  0x00400000  0x07b00313  addi x6,x0,0x0000007b  1    li    t1 123    # какое-то значение
  0x00400004  0xffc10113  addi x2,x2,0xfffffffc  2    addi  sp sp -4  # положить на стек - 1
  0x00400008  0x00612023  sw x6,0(x2)            3    sw    t1 (sp)   # положить на стек - 2
  0x0040000c  0x06430393  addi x7,x6,0x00000064  4    addi  t2 t1 100 # какое-то ещё значение
  0x00400010  0xffc10113  addi x2,x2,0xfffffffc  5    addi  sp sp -4  # положить на стек - 1
  0x00400014  0x00712023  sw x7,0(x2)            6    sw    t2 (sp)   # положить на стек - 2
  0x00400018  0x00012e03  lw x28,0(x2)           7    lw    t3 (sp)   # доступ к вершине стека
  0x0040001c  0x00412e83  lw x29,4(x2)           8    lw    t4 4(sp)  # доступ ко второму элементу стека
  0x00400020  0x00012283  lw x5,0(x2)            9    lw    t0 (sp)   # снятие со стека - 1
  0x00400024  0x00410113  addi x2,x2,4           10   addi  sp sp 4   # снятие со стека - 2
  0x00400028  0xffc10113  addi x2,x2,0xfffffffc  11   addi  sp sp -4  # положить на стек - 1
  0x0040002c  0x00012023  sw x0,0(x2)            12   sw    zero (sp) # положить на стек - 2

• Операция доступа к N-му элементу стека полностью аналогична доступу к вершине стека (просто смещение не нулевое, а +N*4)
  • Наверное, ещё и поэтому стек растёт вниз — смещения проще читать
• Память, которую некоторое время занимал стек, а затем указатель ушёл выше, продолжает хранить значения, которые там лежали. Однако надеяться на то, что они там пребудут впредь, нельзя: память считается «свободной» и её, как минимум, меняют последующие добавления в стек.

• Конвенция устроена так, что все критичные данные постоянно находятся внутри стека (между началом и вершиной). Если, допустим, при снятии сначала изменять указатель, а только потом считывать значения, возникнет опасная ситуация: в это время сохранённые значения оказываются в «свободной» памяти и их может испортить кто угодно — например, обработчик прерывания.

Хранение данных в стеке

• Несколько более эффективно, чем в произвольном месте памяти (lw/sw не превращаются в псевдоинструкции), впрочем, это верно не только для стека, но и при адресации относительно регистра с фиксированным значением (например, при доступе к глобальным переменным относительно gp)

  • Оптимизированные версии процессора могут учитывать конвенцию по вызову и что-то делать с памятью (а особенно с кадром стека, но об это потом)

• Использует адресацию относительно постоянно меняющегося sp. Как следствие, требует аккуратного просчёта текущей глубины стека

• Не требует явного указания адреса и заведения метки в программе на языке ассемблера
• Может привести к сбоям в работе при переполнении/исчерпании/неаккуратном использовании стека

Универсальные подпрограммы

Простая конвенция не поддерживает вложенного вызова подпрограмм:

• ⇒ надо сохранять ra (при повторном вызове он изменится)

• Неправильное решение: выделить для каждой функции ячейку, в которую сохранять ra (не работает рекурсивный вызов)

Рекурсивный вызов — сохранение в стеке

Динамически выделять память удобнее всего на стеке. В начале подпрограммы все регистры, значения которых согласно конвенции следует сохранить до выхода из подпрограммы, а также регистр возврата ra записываются в стек операцией push. Перед выходом эти значения снимаются со стека (в обратном порядке) операцией pop. Эти значения, как правило, не используются внутри подпрограммы, важна только последовательность сохранения и восстановления.

В самом простом случае сохранять надо только ra:

   1 .text
   2 #               …код программы
   3         jal     subr1
   4 #               …код программы
   5 #               …конец программы
   6 
   7 subr1:  addi    sp sp -4        # сохраним текущий ra
   8         sw      ra (sp)         # на стеке
   9 #               …код подпрограммы 1
  10         jal     subr2           # вызов изменяет значение ra
  11 #               …код подпрограммы 1
  12         lw      ra (sp)         # восстановим текущий ra
  13         addi    sp sp 4         # из стека
  14         ret
  15 
  16 subr2:  addi    sp sp -4        # сохраним ra
  17         sw      ra (sp)         # на стеке
  18 #               …код подпрограммы 2
  19         lw      ra (sp)         # восстановим ra
  20         addi    sp sp 4         # из стека
  21         ret

Строго говоря, подпрограмма subr2 — концевая, и в ней не обязательно сохранять и восстанавливать регистры. Но с точки зрения дисциплины программирования удобнее все подпрограммы оформлять одинаково. Возможно, в процессе работы над subr2 из неё понадобится вызвать ещё подпрограмму, и она перестанет быть концевой. По всей видимости, надо исключить любые попытки подпрограмм сохранять какие-то данные не на стеке, т. к. в случае рекурсивного вызова не только ra и сохраняемые регистры.

Рассмотрим пример подпрограммы, вычисляющей функцию факториала. Вопреки здравому смыслу напишем эту подпрограмму рекурсивно: f(n)! = f(n-1)*n . Возникает одно значение — n — которое должно «переживать» рекурсивный вызов. Воспользуемся конвенцией, гарантирующей нам неизменность регистров s* , и запишем n в регистр s1. Тогда для выполнения условий конвенции текущее значение этого регистра надо сохранять в стеке в начале подпрограммы, и восстанавливать перед возвратом из неё.

   1         li      a7 5
   2         ecall
   3         jal     fact            # Параметр уже в a0 )
   4         li      a7 1
   5         ecall                   # Параметр уже в a0 ))
   6         li      a7 10
   7         ecall
   8 
   9 fact:   addi    sp sp -8        ## Запасаем две ячейки в стеке
  10         sw      ra 4(sp)        ## Сохраняем ra
  11         sw      s1 (sp)         ## Сохраняем s1
  12 
  13         mv      s1 a0           # Запоминаем N в s1
  14         addi    a0 s1 -1        # Формируем n-1 в a0
  15         li      t0 1
  16         ble     a0 t0 done      # Если n<2, готово
  17         jal     fact            # посчитаем (n-1)!
  18         mul     s1 s1 a0        # s1 пережил вызов
  19 
  20 done:   mv      a0 s1           # Возвращаемое значение
  21         lw      s1 (sp)         ## Восстанавливаем sp
  22         lw      ra 4(sp)        ## Восстанавливаем ra
  23         addi    sp sp 8         ## Восстанавливаем вершину стека
  24         ret

Здесь мы формально воспользовались конвенцией о сохранении регистров. Сохранив регистр s1, мы обеспечили себе право использовать его как динамическую переменную.

Пролог и эпилог — начальная и завершающая части подпрограммы, которые обслуживают соблюдение конвенции, а к решаемой задаче имеют только косвенное отношение. Так, пролог в примере сохраняет на стеке два регистра, а использовалось бы их больше — сохранял бы больше; эпилог эти два регистра (s0 и ra) восстанавливает (отмечены двойным знаком комментария «##»). Формирование возвращаемого значения в литературе традиционно считается частью эпилога, т. к. её нельзя пропускать ☺.

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

   1         li      a7 5
   2         ecall
   3         jal     fact            # Параметр уже в a0 )
   4         li      a7 1
   5         ecall                   # Параметр уже в a0 ))
   6         li      a7 10
   7         ecall
   8 
   9 fact:   addi    sp sp -4
  10         sw      ra (sp)         # Сохраняем ra
  11         mv      t1 a0           # Запоминаем N в t1
  12         addi    a0 t1 -1        # Формируем n-1 в a0
  13         li      t0 1
  14         ble     a0 t0 done      # Если n<2, готово
  15         addi    sp sp -4        ## Сохраняем t1 на стеке
  16         sw      t1 (sp)         ##
  17         jal     fact            # Посчитаем (n-1)!
  18         lw      t1 (sp)         ## Вспоминаем t1
  19         addi    sp sp 4         ##
  20         mul     t1 t1 a0        # Домножаем на (n-1)!
  21 done:   mv      a0 t1           # Возвращаемое значение
  22 
  23         lw      ra (sp)         # Восстанавливаем ra
  24         addi    sp sp 4         # Восстанавливаем вершину стека
  25         ret

• Подготовка к вызову подпрограммы, которую делает вызывающая программа, называется преамбулой, а действия после возврата из подпрограммы почему-то не называются никак, так что пускай будут финалом', что ли. В примере преамбула и финал обозначены двойным символом комментария «##».

• Отличие конструкции «пролог-эпилог» от «преамбула-финал» — в области ответственности. За исключением того, что явно сказано в конвенции, вызываемая подпрограмма ничего не знает о том, что происходит в преамбуле и финале, а вызывающая программа — о том, что происходит в прологе и эпилоге. Например, не нужно знать, сколько и каких регистров сохраняется на стеке в прологе данной подпрограммы, раз уж конвенция гарантирует нам сохранность регистров типа s*.

Язык ассемблера и понятие «переменная»

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

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

В тексте мы будем использовать понятие локальная переменная преимущественно для такого случая:

• Предположим, что в нашей подпрограмме используется так много объектов, что для всех них не хватает регистров, или мы по каким-то другим причинам хотим хранить некоторое значение не в регистре, а в памяти

• Понятно, что это значение надо хранить на стеке. И для того, чтобы не путаться, куда в данный момент указывает sp, выделение и инициализацию такой памяти на стеке удобно совмещать с прологом, а освобождение — с эпилогом.

   1 subr:   addi    sp sp -12       ## Выделяем три ячейки — под ra и две переменные
   2         sw      ra 8(sp)        ## Сохраняем ra
   3         sw      zero 4(sp)      ## Инициализируем первую переменную нулём
   4         sw      zero (sp)       ## Инициализируем вторую переменную нулём
   5         # …
   6         lw      t0 4(sp)        # Загружаем первую локальную переменную в t0
   7         # …
   8         sw      t1 (sp)         # Записываем t1 во вторую локальную переменную
   9         # …
  10         lw      ra 8(sp)        # Восстанавливаем ra
  11         addi    sp sp 12        # Освобождаем три ячейки стека
  12         ret

• Можно использовать сколько угодно локальных переменных

• Переменные рекомендуется инициализировать:

  • В этом месте стека наверняка лежит какой-нибудь мусор, оставшийся от предыдущих вызовов подпрограмм

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

• Если не изменять стек в процессе работы, у них всегда будут фиксированные смещения относительно вершины стека

Простая конвенция для универсальных подпрограмм

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

1. Передаваемые подпрограмме значения надо заносить в регистры a*

2. Вызов подпрограммы должен производиться командой jal или jalr

3. Никакая вызываемая подпрограмма не модифицирует содержимое стека выше того указателя, который она получила в момент вызова

4. Подпрограмма обязана сохранить на стеке значение ra

5. Подпрограмма обязана сохранить на стеке все используемые ею регистры s*

6. Подпрограмма может хранить на стеке произвольное количество переменных. Количество этих переменных и занимаемого ими места на стеке не оговаривается и может меняться в процессе работы подпрограммы.

7. Возвращаемое подпрограммой значение надо заносить в регистры a0, a1

8. Подпрограмма должна освободить все занятые локальными переменными ячейки стека

9. Подпрограмма обязана восстановить из стека сохранённые значения s* и ra

10. Подпрограмма обязана при возвращении восстановить значение sp в исходное. Это случится автомагически при соблюдении всех предыдущих требований конвенции

11. Возврат из подпрограммы должен производиться командой ret

Некоторые требования конвенции выглядят неоправданно строгими, например, чёткое предписание, где хранить переменные и регистры. Однако такая строгость резко упрощает повторное использование и отладку программ: даже не читая исходный текст программист точно знает, где искать адрес возврата, сохранённые регистры и локальные переменные. Конвенции с хранением данных на стеке крайне чувствительны к нарушению его цельности. Стоит «промахнутся» на ячейку (например, забыть про атомарность процедуры снятия со стека и не увеличить sp), и инструкции эпилога рассуют все значения не по своим местам: адрес возврата останется на стеке, в регистр ra попадёт что-то из сохраняемого регистра, сохраняемые регистры получат «чужое» содержимое и т. д. При попытке выполнить переход на такой ra в лучшем случае возникнет исключение перехода в запрещённую память (хорошо, что малые числа соответствуют зарезервированным адресам и переход на адреса в секции данных запрещён). В худшем случае содержимое ra случайно окажется из допустимого диапазона секции кода, произойдёт возврат по этому адресу и начнётся выполнение лежащего там кода. Отладка такой ситуации (называемой «stack smash», снос стека) — непростая задача для программиста.