Кадр стека и внешние вызовы

Зачем нужен кадр

Как правило, подпрограмме необходимо хранить какие-то данные в памяти. Это, во-первых, сохраняемые значения регистров, во-вторых — параметры и возвращаемые значения подпрограммы, если их больше, чем соответствующих регистров, а в-третьих — разнообразные значения, для которых в процессе планирования вычислений не оказалось свободного регистра. Данные, которые подпрограмма временно хранит в памяти, называются локальными переменными.

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

   1 .text
   2 # подпрограмма, вычисляющая сумму и произведение двух чисел,
   3 # и хранящая их все на стеке без использования кадра, ПОТОМУ ЧТО ТАК НАДО
   4 main:   li      a7 5
   5         ecall
   6         mv      s0 a0
   7         li      a7 5
   8         ecall
   9         mv      a1 s0
  10         jal     mulsum
  11         mv      a1 s0
  12         li      a7 1
  13         ecall
  14         mv      a0 s0
  15         li      a7 1
  16         ecall
  17         li      a7 10
  18         ecall
  19 
  20 mulsum: addi    sp sp -4
  21         sw      ra (sp)         # Адрес возврата
  22         addi    sp sp -4
  23         sw      a0 (sp)         # Первая переменная
  24         addi    sp sp -4
  25         sw      a1 (sp)         # Вторая переменная
  26         # Какой-то код, который портит регистры
  27         lw      t0 4(sp)        # Первая переменная
  28         lw      t1 (sp)         # Вторая переменная
  29         add     t2 t0 t1
  30         addi    sp sp -4
  31         sw      t2 (sp)         # Сумма (смещения переменных поехали)
  32         # Какой-то код, который портит регистры
  33         lw      t0 8(sp)        # Первая переменная (да-да!)
  34         lw      t1 4(sp)        # Вторая переменная (ну хоть тут понятно)
  35         mul     t2 t0 t1
  36         addi    sp sp -4
  37         sw      t2 (sp)         # Произведение
  38         # Какой-то код, который портит регистры
  39         lw      a1 (sp)         # Произведение
  40         lw      a0 4(sp)        # Сумма
  41         lw      ra 20(sp)       # Эммм… сколько там переменных было?
  42         addi    sp sp 20        # Вроде не ошибся!
  43         addi    sp sp 4
  44         ret

• Локальные переменные характеризуются смещением относительно вершины стека. При добавлении в стек (например, очередной локальной переменной) все эти смещения меняются и это надо всегда помнить программисту (чем-то напоминает программирование в кодах). Допустим, мы положили в стек некоторое значение (например, 5). Теперь оно доступно по адресу (sp). После того, как мы положим в стек следующее значение (скажем, 100500), 5 становится доступно по адресу 4(sp) (стек растёт вниз), а 100500 — (sp). Добавление третьего снова изменит смещения относительно sp. Каждый раз, помещая в стек или снимая оттуда значения, мы вынуждены использовать новые смещения для остальных данных в стеке

• Для того, чтобы перевести sp в состояние, пригодное для восстановления ra, необходимо вести (в уме?) учёт всех сохранённых на стеке регистров и расположенных там локальных переменных, и снимать со стека ровно столько значений, сколько успели туда положить.

Возникает идея хранить в специально отведённом регистре (он называется Frame Pointer, fp) состояние sp на момент вызова функции. Тогда для восстановления sp перед возвратом из функции достаточно будет переложить туда значение fp. Предыдущее значение fp при этом тоже надо будет сохранять на стеке, т. к. кадр локален для каждого вызова функции.

Пример конвенции с использованием кадра

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

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

2. (преамбула) Если передаваемых параметров больше 8, все остальные необходимо положить в стек в обратном порядке (последний, предпоследний, … десятый, девятый)

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

4. Никакая вызываемая подпрограмма не модифицирует содержимое стека выше того указателя, который она получила в момент вызова (напомним, что «выше» — это ближе к началу)

5. (пролог) Подпрограмма обязана сохранить на стеке значения ra (адреса возврата) и fp (адрес предыдущего кадра)

6. (пролог) Значение sp, каким оно было на момент вызова подпрограммы, она обязана записать в fp

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

8. (пролог) Подпрограмма обязана выделить на стеке память для всех локальных переменных

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

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

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

12. (эпилог) Подпрограмма обязана восстановить из стека значение ra и fp

13. (эпилог) Подпрограмма обязана восстановить значение sp

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

15. (очистка стека) Если передаваемых параметров было больше 8, необходимо поднять указатель стека на нужное смещение

Согласно такой конвенции:

• Смещение относительно fp всех используемых в функции локальных данных постоянно. Можно, например, задать им мнемонические обозначения с помощью .eqv. Если локальных переменных много и они часто используются, мнемоника сильно упрощает работу с исходным кодом.

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

• Сброс кадра частично защищает программу от сноса стека (в большую сторону): если сам fp не испорчен, и ошибочное изменение стека не добралось до сохранённых значений, ошибку можно локализовать при отладке. Такая ошибка возникает, например, если разместить какие-то данные в стеке, и забыть их оттуда снять

• Дополнительные входные данные, за недостатком регистров передаваемые подпрограмме через стек, также доступны по фиксированным смещениям относительно fp, причём, в силу порядка, девятый параметр будет просто лежать по адресу 4(fp), десятый — 8(fp) и т. д. (напоминаем, стек растёт вниз).

• Что не менее важно, при отладке программы с неиспорченным стеком, можно автоматически отследить т. н. цепочку вызовов (call trace) — последовательность вызовов подпрограмм, которая привела к вызову текущей. В самом деле, fp в этой конвенции указывает на место в стеке, где хранится предыдущее значение fp, а оно указывает на пред-предыдущее и т. д.

• Цепочка вызовов — это обычный связный список, начало которого сейчас хранится в fp, и работать с ним можно соответственно!

  Список кадров в стеке (упрощённвая схема)	Кадры в стеке RISC-V по предложенной конвенции

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

Стоит заметить, что и эта конвенция

• неуниверсальна
• не для всего удобна

Например, мы можем потребовать, чтобы дополнительные параметры подпрограммы также входили в кадр (тогда инициализация кадра войдёт в преамбулу, зато не будет нужды в восстановлении стека после возврата), или, наоборот, чтобы в кадр входили только локальные переменные и временные данные (тогда сброс кадра становится слегка сложнее — к восстановленному sp надо добавлять размер области сохраняемых регистров, зато адресация локальных переменных относительно начала кадра начинается прямо с 0).

Более того, использование кадра удобно в первую очередь для программирования на языке ассемблера «вручную». Именно восстановление стека из fp позволяет в процессе работы подпрограммы сохранять на нём произвольное количество дополнительных данных. Это может потребоваться при разработке сложного алгоритма, когда регистров общего назначения внезапно перестало хватать.

Однако компилятор с любого языка программирования более высокого уровня планирует регистры автоматически, и, как следствие, всегда заранее знает, сколько места на стеке потребуется данной подпрограмме. В таком случае в использовании fp нет нужды: в прологе sp увеличивается на вычисленную константу — планируемый объём памяти на стеке, а в эпилоге — уменьшается.

Подпрограмма с использованием кадра

Это подпрограмма, сортирующая методом обмена массив целых размером a0 байтов (т. е. a0/4 элементов), лежащий по адресу a1. Подпрограмма не концевая — она вызывает ещё одну подпрограмму, поиск минимального элемента в массиве.

• Подпрограмма использует два сохраняемых регистра s для хранения счётчика и адреса обмена, поэтому эти два регистра сохраняются в кадре вместе с fp и ra

• Подпрограмма запоминает адрес и размер массива в локальных переменных, чтобы затем вернуть их, согласно конвенции, в a0 и a1. Конечно, можно было бы и в сохраняемые регистры спасти эти значения, но чего не сделаешь ради удобного примера ☺

• Все смещения заданы .eqv-константами, в том числе и размер кадра FSIZE, который просто совпадает со смещением последней локальной переменной. Точка в именах констант собственного смысла не несёт, только для красоты (а также для отличия констант-смещений в кадре от других каких-нибудь констант).

   1 # Смещение в кадре для сохраняемых регистров относительно fp
   2 .eqv    .S1     -12             # s*
   3 .eqv    .S2     -16
   4 .eqv    .ARR    -20             # Смещения в кадре
   5 .eqv    .SIZE   -24             #   для локальных переменных
   6 .eqv    FSIZE   28              # Размер кадра (+ 4 на сам fp)
   7 # Смещение в кадре для ra и fp относительно sp
   8 .eqv    .RA     24              # ra (к сожалению, RARS не умеет в FSIZE-4)
   9 .eqv    .FP     20              # fp
  10 sort:   # сортировка массива
  11         # Вход: a0 — размер массива, a1 — начало массива
  12         # Выход: a0 — размер массива, a1 — начало массива (того же!)
  13         addi    sp sp -FSIZE    # Заводим кадр
  14         sw      ra .RA(sp)      # Сохраняем ra
  15         sw      fp .FP(sp)      # Сохраняем fp
  16         addi    fp sp FSIZE     # Значение sp при входе в sort
  17         sw      s1 .S1(fp)      # Теперь у нас есть fp, сохраняем s1
  18         sw      s2 .S2(fp)      # сохраняем s2
  19 
  20         sw      a0 .SIZE(fp)    # Размер массива
  21         sw      a1 .ARR(fp)     # Адрес массива
  22 
  23         mv      s2 a0           # Регистры типа s* не меняются
  24         mv      s1 a1           # при вызовах функций
  25 fnext:  mv      a0 s2
  26         mv      a1 s1
  27         jal     getmin
  28         lw      t0 (a0)
  29         lw      t1 (s1)
  30         sw      t0 (s1)
  31         sw      t1 (a0)
  32         addi    s1 s1 4
  33         addi    s2 s2 -4
  34         bgtz    s2 fnext
  35 
  36         lw      a0 .SIZE(fp)    # Обращаемся к локальным переменным
  37         lw      a1 .ARR(fp)
  38 
  39         lw      s2 .S2(fp)      # Восстанавливаем регистры
  40         lw      s1 .S1(fp)
  41         lw      ra .RA(sp)      # Восстанавливаем адрес возврата
  42         lw      fp .FP(sp)      # Восстанавливаем кадр
  43         addi    sp sp FSIZE     # Восстанавливаем стек
  44         ret

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

   1 getmin: # концевая подпрограмма
   2         # a0 — размер массива
   3         # a1 — начало массива
   4         # a0 — адрес минимального элемента
   5         lw      t0 (a1)
   6         mv      t2 a1
   7 gmnext: addi    a0 a0 -4
   8         addi    a1 a1 4
   9         blez    a0 gmfin
  10         lw      t1 (a1)
  11         bge     t1 t0 gmnext
  12         mv      t0 t1
  13         mv      t2 a1
  14         j       gmnext
  15 gmfin:  mv      a0 t2
  16         ret

Вызывающая программа с вводом и выводом:

   1 .data
   2 .eqv    SZ 20
   3 Arr:    .space  SZ
   4 EndArr: .align  2
   5 .text
   6 
   7 main:   la      t1 Arr
   8         la      t2 EndArr
   9 input:  li      a7 5
  10         ecall
  11         sw      a0 (t1)
  12         addi    t1 t1 4
  13         bgtu    t2 t1 input
  14 
  15         li      a0 SZ
  16         la      a1 Arr
  17         jal     sort
  18 
  19         la      t1 Arr
  20         la      t2 EndArr
  21 output: li      a7 1
  22         lw      a0 (t1)
  23         ecall
  24         li      a0 '\n'
  25         li      a7 11
  26         ecall
  27         addi    t1 t1 4
  28         bgtu    t2 t1 output
  29 
  30         li      a7 10
  31         ecall

Вся программа

Обратите внимание на строгую реализацию принципа «сначала переставим стек, потом будем сохранять значения».

Дело в том, что sp в любой момент работы программы обязан указывать или на вершину стека, или за неё — иными словами, мы не можем рассчитывать на сохранность данных за пределами текущего стека. Это связано с механизмом асинхронных прерываний (он будет в нашем курсе). По той же причине в fp сразу же появляется указатель на стек, и хранится там до последнего (восстанавливается даже после ra).

При обработке прерывания выполнение программы приостанавливается в произвольном месте, и управление передаётся отдельно объявленной подпрограмме-обработчику, а после её завершения выполнение текущей программы возобновляется с того же места. При использовании плоской модели памяти и в отсутствие режима супервизора (как в RARS и других малых архитектурах, например, на микроконтроллерах) обработчику доступна та же самая память, и что более важно — тот же самый стек, что и основной программе. Если в программе записать что-то за пределами стека (например, перенести addi sp sp -FSIZE в конец пролога), а прерывание произойдёт между инструкциями sw и addi, и обработчик решит положить что-то на стек, лежащие в этом месте значения будут затёрты.

Промышленные конвенции

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

Правда, даже для таких условий эти конвенции неполны:

• Если в подпрограмме используется арифметически сопроцессор и его регистры, для них существуют отдельные конвенции (см. ../04_FloatingPoint и riscv-cc)

  • часть из вещественных также надо сохранять при вызове подпрограммы (а другую часть не надо)
  • часть используется в качестве регистров передачи параметров
  • часть используется в качестве регистров возврата значения

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

• Никак не регламентирован побочный эффект — модификация памяти вне стека.

• Частный случай побочного эффекта — возврат более, чем двух ячеек возвращаемых значений (на стеке? в куче?) также не регламентирован

Чем сложнее описываемый конвенцией случай, тем сложнее изобрести универсальную договорённость. Ниже пример нескольких документов, содержащий несколько версий «живых» ABI (application binary inverface), что соответствует части конвенций по вызову подпрограмм и запуску программ.

• В соответствии со стандартом ELF

• Используются, в частности, PLT и GOT (поддержка динамической компоновки в ОС с многозадачностью)

  • Динамическая компоновка: программа собирается в памяти из основного кода и частей библиотек во время выполнения, при этом часть библиотек уже есть в памяти, потому что они нужны и другим программам

  • ⇒ Адреса символов (данных и подпрограмм) всё время разные, они становятся известны только после загрузки библиотеки в память

  • GOT (Global Offset Table): динамически формируемая таблица этих адресов
    • загрузить известный уже во время трансляции адрес ячейки GOT, загрузить из этой ячейки реальный адрес символа

  • PLT (Procedure Linkage Table): а что, если адрес подпрограммы неизвестен на момент загрузки в память?

    • Тогда в GOT вместо него записывается сложная процедура по поиску нужной функции в нужной библиотеке, которая заполняет этот самый адрес в GOT адресом найденной функции (и вызывает саму функцию).

    • В следующий раз действие «вызывается код по адресу, взятому из GOT» сразу приведёт к вызову функции.

• Встраиваемое ABI

  • TODO This repository has been archived by the owner on Feb 2, 2024. It is now read-only.

  • Предполагает передачу вещественных параметров посредством целочисленных регистров (о как!)
• …

Наконец, полноценный ABI, в отличие от «договорённостей» предназначен не только и не столько для людей-программистов, сколько для системных программ, занимающихся исходным и машинным кодом

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

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

  • Фиксированную преамбулу (например, полное сохранение временных регистров и их восстановление после возврата)
  • Фиксированный пролог с полным сохранением сохраняемых регистров и даже, возможно, кадром фиксированного размера (в этом случае если локальных переменных меньше кадра, остальные его области не используются, а если больше — область под них выделяется в куче)
  • Соответствующий прологу фиксированный эпилог
• Отладчики, профилировщики и прочие инструменты намного надёжнее работают с такими фиксированными ABI
• В преамбулу, пролог и эпилог может включаться программная защита кода (например, защита от сноса стека)

Внешние вызовы

Строго говоря, изнутри программы невозможно определить, кто именно исполняет ecall: контекcт выполнения не меняется (за исключением самого вызова: заранее оговоренное изменение регистров, заполнение памяти и т. п.). Если это была какая-то подпрограмма — код этой подпрограммы недоступен. Более того, мы даже не знаем, на каком языке программирования на базе какой архитектуры реализована логика внешнего вызова. Хороший пример — внешние вызовы RARS, которые реализованы на языке программирования Java, а выполняются виртуальной машиной Java — а значит операционная система и даже архитектура компьютера-исполнителя могу быть разными!

Если вы пишете программу для запуска на том же компьютере, на котором работаете, скорее всего ecall — это обращение к ядру операционной системы (т. н. «системный вызов», или syscall). В Linux этот код написан на Си и выполняется тем же процессором, только на другом уровне выполнения — то есть это будут машинные коды RISC-V.

В целом можно сказать, что программа эксплуатирует какие-то функции «окружения», в котором она выполняется. Отсюда и название — Environment Call.

Время от времени мы будем называть ecall по-старинке: cистемный вызов, не обращайте внимания)

Операционная система

Задачи операционной системы: унификация, разделение и учёт ресурсов компьютера. Для взаимодействия с ОС программа следует некоторым соглашениям, называемым ABI (Application Binary Interface).

Под ресурсами поминаются оперативная память, процессорное время и разнообразные внешние устройства.

• Унификация: прикладной программе гарантируется работа на различном оборудовании, с различными (совместимыми) версиями системного ПО. В состав дисциплины могут входить абстрактные системные объекты (файл, процесс, пакет, поток и т. п.), работа с которыми однотипна независимо от того, каким аппаратным ресурсом этот объект реализован. Например, файл может быть размещён на диске, на сетевом хранилище или вообще являться потоком ввода-вывода, как stdin/stdout/stderr.

• Разделение: прикладная программа пользуется ресурсами, не опасаясь вступить конфликт с другими программами или самой ОС, если тем вдруг вздумается воспользоваться теми же ресурсами. Для этого в ОС предусмотрены различные дисциплины доступа, постоянные или временные ограничения, блокировки и т. п. Типичные пример — разделение времени между задачами, одновременно работающими под управлением ОС

• Учёт: возможность получения информации об использовании ресурсов как всей ОС в целом, так и каждой задачей в отдельности

Программный интерфейс использования ресурсов — системные вызовы — предоставляет т. н. ядро ОС

Ядро операционной системы — программный код, постоянно находящийся в памяти, имеющий доступ ко всем ресурсам компьютера и реализующий дисциплину их использования.

Аппаратная поддержка

Итак:

• Мы знаем, что окружение, в котором запускается программа, умеет выполнять какие-то функции
• Мы не умеем / не хотим / не имеем возможности самостоятельно эти функции реализовать
  • Работа с внешними устройствами в режиме полного доступа — только ядро
  • Полное отсутствие этих устройств в видимом изнутри окружении (как в RARS или виртуалках)
  • Сложный код по взаимодействию с внешними устройствами, которое нуждается в унификации и некоторой защите, — например кольцевой буфер ввода
  • …

Вариант: «системный вызов»

• Универсальная пользовательская инструкция «обратиться к ОС» — «системный вызов» (syscall)

  • Фактически это — вызов подпрограммы, в котором вместо адреса используется заданный в API/ABI номер системного вызова. Адрес подпрограммы в ядре зависит от версии ОС, версии ядра ОС и даже последовательности загрузки отдельных модулей одного и того же ядра. Одна и та же программа не сможет работать во всех случаях, если будет использовать непосредственно адрес. Введение дополнительного уровня косвенности в виде номера системного вызова снимает проблему (в адрес подпрограммы этот номер превращает ядро).

• Прозрачный (невидимый пользователю) механизм выполнения
• Защита памяти ядра
• Поддержка минимум двух потоков вычисления (пользовательская программа и ядро ОС)

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

Вариант с обобщением «функция окружения», или ecall:

• от полностью программного (выполняется машинный код из области ядра, фактически syscall)
• обращение к супервизору мимо ядра ОС (например, за статистикой, отладкой, профилированием и прочим)
• до полностью аппаратного (нужную операцию выполняет компьютер)

С точки зрения пользовательской программы это всё не слишком важно.

Многообразие внешних вызовов

Внешние вызовы не стандартизованы в рамках архитектуры — это конвенции, задаваемые самим окружением. Например, системные вызовы ядра Linux имеют совсем другие функции, чем вызовы RARS. Более того, количество и тип входных параметров и возвращаемые значения отличаются даже в рамках одного набора внешних вызовов (например, в RARS).

Такая гибкость приводит к тому, что использовать внешние вызовы на низком уровне можно только соблюдая строжайшую дисциплину: ни транслятор, ни окружение не в состоянии проверить, что программист в вызове № K разложил в правильные регистры правильные данные. Полегче становится с повышением уровня языка программирования: для каждого системного вызова создаётся функция в терминах этого языка, в которой можно проверить количество, тип, а иногда и структуру передаваемых параметров.

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

Частично с этой проблемой помогает справиться т. н. semihosting (русского перевода пока нет!). Реализуется он так: в систему команд добавляется специальная инструкция ebreak, которая означает «передать управление отладчику из окружения». Важно, чтобы окружение обладало функцией отладки: могла выяснить, по какому адресу была помещена инструкция ebreak, а так же какие инструкция располагаются непосредственно до и после неё в памяти. Эти инструкции — вариации nop, например, регистровые операции с приёмником zero — т. е. в самой программе они ничего не меняют. Зато все остальные поля инструкции — регистр-источник, код операции и т. п. — окружение анализарует и воспринимает как описание входных параметров и возвращаемого значения. После чего программист пишет — уже в рамках окружения — обработчик ebreak, который выполняет нужное действие и возвращает управление обратно программе.

И в случае syscall, и в случае ecall эта функция обычно реализована аппаратно, отдельной инструкцией.

Функции окружения RARS

Описаны в документации по RARS

Конвенции по вызову ecall в RISC-V

1. В регистр a7 помещается номер системной функции (service number)

2. В регистры a* или fa* (для вещественных чисел) помещаются параметры системного вызова, если есть

3. Инструкция ecall передаёт управление операционной системе (обычно ядру, но, например, в RARS это может быть сразу сам RARS)

4. Возврат из системного вызова — по аналогии с возвратом из подпрограммы, на следующую после ecall инструкцию

5. Возвращаемые значения (если есть) помещаются в a* или в fa0 в соответствии с работой вызванной системной функции

Механизм работы ecall со стороны ядра ОС может быть разным.

Пример: вывести на консоль число, лежащее в регистре t0

   1     li  a7 1            # Функция 1 — вывод числа
   2     mv  a0 t0
   3     ecall               # Введённое число помещается в a0

Некоторые системные вызовы RARS

Для функций выше ещё можно вообразить, что это «классическая» реализация системных вызовов: есть ядро ОС, которое работает на том же компьютере, что и наша программа, специальная инструкция переключает режим работы процессора, выполнение попадает в адресное пространство ядра и там соответствующая подпрограмма выполняется, а по завершении изменяются соответствующие регистры, и выполнение продолжается.

Однако в RARS есть и уже совсем откровенные обращения к «вышестоящему окружению»: работа с устройствами и сущностями, полностью отсутствующими в архитектуре ЭВМ, на которой работает программа.

Например:

• вызовы 40-44 — это работа с генератором случайных чисел (важно: не с аппаратной случайностью),

• вызовы 50-60 (кроме 57) — замена вызовам ввода-вывода, использующая диалоговые окна Java
• вызовы 17, 57, 62-64 и (внезапно) 1024 — работа с файлами на вашем компьютере
• вызов 93 — останов программы и всего RARS-а (как 10-й), но с возвратом в вашу операционную систему кода завершения

• 31 и 33 — проигрывание ноты на аудиокарте вашего компьютера

Работа со строками

(можно пропустить для тех, кто в теме)

• Строки — это последовательности ненулевых байтов, заканчивающихся символом с кодом 0 (однобайтным нулём) согласно формату ASCIZ

• Ввод заканчивается символом перевода строки (ASCII-код 10, соответствует нажатию Enter). Этот символ тоже попадает в строку! Так что если ваша задача ввести слово не более, чем из 10 букв, размер буфера должен быть на 2 больше — 12. 11-м символом в нём будет '\n', а 12-м — 0.

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

• Мы не можем вводить строки произвольной длины ­— разве что в случае, когда в обход операционной системе размещаем вводимую строку в конце Кучи. Но и тогда нужно было бы проверять, не упёрлись ли мы в стек…

Пример работы со строками: подсчёт количества пробелов во введённой строке.

   1 .eqv    SIZE 100                # размер буфера
   2 .data
   3 str:    .space SIZE             # буфер
   4 .text
   5         la      a0 str          # считаем строку в буфер
   6         li      a1 SIZE
   7         li      a7 8
   8         ecall
   9         mv      t0 zero         # счётчик пробелов
  10         li      t2 0x20         # пробел
  11 loop:   lb      t1 (a0)         # очередной символ
  12         beqz    t1 fin          # нулевой — конец строки
  13         bne     t1 t2 nosp      # не пробел — обойдём счётчик
  14         addi    t0 t0 1         # пробел — увеличим счётчик
  15 nosp:   addi    a0 a0 1         # следующий символ
  16         b       loop
  17 fin:    mv      a0 t0           # выведем счётчик
  18         li      a7 1
  19         ecall
  20         li      a7 10
  21         ecall

В качестве эксперимента можно попробовать воспользоваться вызовом 54 для ввода строки и вызовом 56 для вывода целого.

Заказ памяти у системы

Статическая память выделяется при трансляции секций .data . В результате трансляции в определённых областях оперативной памяти (по умолчанию — начиная с 0x10010000) резервируются области, которые затем доступны с помощью меток или непосредственно по адресам. Области могут быть инициализированы начальными значениям (как в .word, .asciz и т. п.), а могут остаться без изменения (как в .space). Добавление новых директив резервирования памяти в секцию .data приведёт к тому, что соответствующие ячейки окажутся после уже отведённых.

В процессе работы программы возникает необходимость хранить данные только в течение определённого времени. Например, данные, актуальные только в процессе вызова подпрограммы, соответствуют локальным переменным в языках программирования высокого уровня. Временные данные хранятся в стеке.

В других случаях память необходимо выделять на всё время работы программы, но размер их заранее неизвестен. Один раз это можно сделать, воспользовавшись в качестве базового адреса началом кучи — 0x10040000. Однако в дальнейшем придётся где-то хранить вершину кучи, чтобы следующая область динамически выделяемой на куче памяти не пересекалась с предыдущей.

В RARS этим занимается операционная система. Системный вызов 9, которому в a0 передаётся объём заказываемой памяти, отведёт на куче соответствующую область и вернёт в a0 её адрес. Следующий вызов ecall 9 вернёт адрес после уже заказанной области и т. д.

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

Подпрограмма принимает в a0 объём памяти, а возвращает в a0 выделенный адрес, выводя сообщение об этом.

   1 newmem: li      a7 9            # Закажем память (объём уже в a0)
   2         ecall
   3         mv      t1 a0           # Сохраним адрес
   4         li      a7 34           # Выведем адрес (a0 уже задан)
   5         ecall                   # как 16-ричное число
   6         li      a0 10           # Выведем перевод строки
   7         li      a7 11
   8         ecall
   9         mv      a0 t1           # Вспомним адрес
  10         ret

Напишем программу, которая трижды просит у системы память, причём один раз — нечётного объёма в байтах:

   1 .globl main
   2 main:   li      a0 0x100       # Закажем 256 байтов
   3         jal     newmem
   4         li      a0 0x101       # закажем 257 байтов
   5         jal     newmem
   6         li      a0 0x100       # Закажем опять 256 байтов
   7         jal     newmem

• Следующий вывод программы покажет нам, что ecall 9 при выделении памяти выравнивает адрес на границу слова:

     1 0x10040000
     2 0x10040100
     3 0x10040204
  

Несмотря на кажущуюся простоту операции, освобождать память в куче для повторного использования намного сложнее. Рассмотрим общую задачу выделения/освобождения памяти (т. н. memory management).

• Необходимо иметь возможность заказывать фрагменты памяти произвольного размера
• Необходимо иметь возможность освобождать произвольные заказанные ранее фрагменты памяти в произвольное время

• Следовательно, относительно каждого фрагмента необходимо постоянно хранить метаинформацию — размер и местоположение.

• Надо решить проблему фрагментации: если мы заказали 2048 фрагментов размером в килобайт (2 Мб суммарно), а затем освободили каждый второй, у нас не образовалось 1 Мб свободной памяти! Вместо этого у нас образовалось 1024 килобайтных фрагмента, никакие два их которых не идут в памяти подряд

• …

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

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

Д/З

Задачи к этой лекции — обычные (то есть без тестирующей части на языке ассемблера, только ввод-вывод). Для решения задач можно использовать связку «макрос+подпрограмма», а можно не использовать. Советую всё-таки использовать — чтобы убедиться в том, насколько структуризация и повторное использование делает исходные тексты понятнее и сопровождаемее.

0. Написать комплект «макрос+подпрограмма» для функция работы со строками. Формат вызова, точный список функций и логика их работы на ваше усмотрение.

   • Пример реализации (все параметры — это регистры, которые перед вызовом подпрограммы копируются в соответствующие a*-регистры).

     • В этом примере есть макросы, имена которых совпадают с именами в прошлом Д/З, а вот работа несколько отличается.

     Макрокоманда	Параметр 1	Параметр 2	Описание	→a0	→a1
     strlen	Адрес		Определение длины ASCIZ-строки	Длина строки
     strget			Ввод ASCIZ-строки длиной не более 100 байтов. Ввод происходит в статический буфер, далее для строки выделяется соответствующее место на куче, и она копируется туда (\n, если есть, из строки удаляется, в конец обязательно записывается 0)	Адрес выделенной памяти	Длина строки
     strcpy	Приёмник	Источник	(Небезопасно) копирует ASCIZ-источник по адресу «приёмник»	Приёмник	Длина строки
     strcmp	Адрес 1	Адрес 2	Лексикографическое сравнение ASCIZ-строк. Возвращает отрицательное число, если первая строка меньше, положительное, если больше и ноль, если строки равны.	Результат
     strchr	Адрес 1	Байт	Возвращает адрес первого вхождения символа char в строку по адресу addr1 или 0, если символ в строке отсутствует	Адрес 2

   • Напоминаю, что в ecall 8 параметр a1 — это именно размер буфера, включая \0 в его конце. Символов вводится при этом на 1 меньше.

   • Ещё один вариант — отказаться от использования a*-регистров в тексте программы и предусмотреть в макросах копирование результатов оттуда. Например strlen %регистр_адреса %регистр_длины будет копировать %регистр_адреса в a0, вызывать внутреннюю подпрограмму, реализующую strlen, получать в a0 длину и записывать её в %регистр_длины

   • В части с макросами можно понаписать всякого удобного: отладочную выдачу, push/pop, ecall одной строкой (причём с разным количеством параметров!) и, разумеется, пролог и эпилог подпрограммы

   • Макросы, библиотеку подпрограмм и основной текст main (не забываем про .globl main) удобно хранить в разных файлах и использовать многофайловую сборку, однако в силу специфики EJudge для решения Д/З всё надо складывать в один файл.

1. EJudge: SameLines 'Повторение строк'

   Ввести строку-шаблон, затем вводить строки примеры; окончание ввода — пустая строка. Вывести в виде «Duplicates: число» количество строк-примеров, совпадающих с шаблоном. Все входные строки короче 100 байтов.

   Input:

   QWEqwe
   as
   QWEqwe!
   QWEqw
   QWEqwe
   a
   QWEqwe
   QWEqweQWEqwe

   Output:

   Duplicates: 2

   • Вот так выглядит моё решение (без макросов и библиотеки):

        1 .include        "string.inc"    # В Д/З сюда надо вставить string.inc и string.asm
        2 .globl  main
        3 .data
        4 buf:    .space  STRSIZE         # 101
        5 .text
        6 main:   li      s3 0
        7         strget  s1 s2           # jal _strget; a0→s1 (aдрес), a2→s2 (длина)
        8         la      s4 buf
        9         li      s5 STRSIZE      # 101
       10 loop:   syscall 8 s4 s5         # s4→a0, s5→a1; ecall 8
       11         strip   s4 '\n'         # Вспомогательная процедура удаления хвостового '\n'
       12         strlen  s4 t6           # s4→a0; jal _strlen; a0→t6
       13         beqz    t6 done
       14         strcmp  s1 s4 t0        # s1→a0, s4→a1; jal _strcmp; a0→t0
       15         bnez    t0 loop
       16         addi    s3 s3 1
       17         b       loop
       18 done:   print.w "Duplicates: " s3 # Удобно для отладки, но и тут пригодилось
       19         syscall 10
     

     • Я воспользовался собственным советом и включил в параметры макросов регистры, в которые сохраняется результат

2. EJudge: LongestLine 'Наибольшая среди длинных'

   Вводить строки (длина строки не превышает 100, последняя строка пустая). Вывести строку наибольшей длины. Если таких несколько, вывести лексикографически наибольшую.

   Input:

   QWER
   qwerqwer
   as
   asdfsdff
   wqerq
   qwerzxcv
   asdf
   sdf

   Output:

   qwerzxcv

3. EJudge: FindChars 'Символы из строки'

   Ввести строку-шаблон, а затем вводить строки-примеры; конец ввода — пустая строка. Вывести все строки-примеры, в которых есть хотя бы один символ из строки-шаблона. длина строк меньше 100.

   Input:

   qwetyuqweuqwuer
   asdfhashdfasdhf
   zxcbvzbxcvbzxcrvb
   asdhfashdfasdh
   zxcbvzxbcvbzxcvq
   asdfasdfasdf
   zxcvzxcvzxcv
   fasfasfasdef
   tqtqeerqwerqwe
   zxcvzxvczxcv
   wefqwefqwef
   czxcvzxcvzxc

   Output:

   zxcbvzbxcvbzxcrvb
   zxcbvzxbcvbzxcvq
   fasfasfasdef
   tqtqeerqwerqwe
   wefqwefqwef

4. EJudge: StringSort 'Сортировка строк'

   Старая добрая сортировка обменом. Ввести натуральное число N — количество строк, а затем — N строк. Вывести их в лексикографическом порядке возрастания. Длина строк меньше 100.

   Input:

   12
   qwetyuqweuqwuer
   asdfhashdfasdhf
   zxcbvzbxcvbzxcrvb
   asdhfashdfasdh
   zxcbvzxbcvbzxcvq
   asdfasdfasdf
   zxcvzxcvzxcv
   fasfasfasdef
   tqtqeerqwerqwe
   zxcvzxvczxcv
   wefqwefqwef
   czxcvzxcvzxc

   Output:

   asdfasdfasdf
   asdfhashdfasdhf
   asdhfashdfasdh
   czxcvzxcvzxc
   fasfasfasdef
   qwetyuqweuqwuer
   tqtqeerqwerqwe
   wefqwefqwef
   zxcbvzbxcvbzxcrvb
   zxcbvzxbcvbzxcvq
   zxcvzxcvzxcv
   zxcvzxvczxcv