Кадр вызова функции, системные вызовы и макрокоманды
Лекция оказалась простой, но трудно поверить, что это всё уместилось в 2 часа. Тем не менее!
Содержание
Кадр стека и промышленные конвенции
Зачем нужен кадр
Как правило, подпрограмме необходимо хранить какие-о данные в памяти. Это, во-первых, сохраняемые значения регистров, во-вторых — параметры и возвращаемые значения подпрограммы, если их больше, чем соответствующих регистров, а в-третьих — разнообразные значения, для которых в процессе планирования вычислений не оказалось свободного регистра. Данные, которые подпрограмма временно хранит в памяти, называются локальными переменными.
Если подпрограмма использует много локальных переменных, описанная ранее конвенция оказывается довольно неудобной (
1 # подпрограмма, вычисляющая сумму и произведение двух чисел,
2 # и хранящая их все на стеке без использования кадра, ПОТОМУ ЧТО ТАК НАДО
3 main: li $v0 5
4 syscall
5 move $a0 $v0
6 li $v0 5
7 syscall
8 move $a1 $v0
9 jal addmul
10
11 move $t0 $v0
12 move $t1 $v1
13 move $a0 $t0
14 li $v0 1
15 syscall
16 li $a0 ' '
17 li $v0 11
18 syscall
19 move $a0 $t1
20 li $v0 1
21 syscall
22 li $a0 '\n'
23 li $v0 11
24 syscall
25 li $v0 10
26 syscall
27
28 addmul: addiu $sp $sp -4
29 sw $ra ($sp)
30 addiu $sp $sp -4
31 sw $a0 ($sp) # первая переменная
32 addiu $sp $sp -4
33 sw $a1 ($sp) # вторая переменная
34 # какой-то код, портящий регистры
35 lw $t0 4($sp) # первая переменная
36 lw $t1 ($sp) # вторая переменная
37 addu $t2 $t1 $t0
38 addiu $sp $sp -4
39 sw $t2 ($sp) # сумма
40 # какой-то код, портящий регистры
41 lw $t0 8($sp) # внезапно первая переменная
42 lw $t1 4($sp) # соответственно вторая переменная
43 mul $t2 $t1 $t0
44 addiu $sp $sp -4
45 sw $t2 ($sp) # произведение
46 # какой-то код, портящий регистры
47 lw $v1 ($sp) # произведение
48 lw $v0 4($sp) # сумма
49 # жэээсть, что я тут в стек понадобавлял
50 # сколько сбрасывать-то??
51 addiu $sp $sp 16
52 lw $ra ($sp)
53 addiu $sp $sp 4
54 jr $ra
55
56
57
58
Локальные переменные характеризуются смещением относительно вершины стека. При добавлении в стек (например, очередной локальной переменной) все эти смещения меняются и это надо всегда помнить программисту (чем-то напоминает программирование в кодах). Допустим, мы положили в стек некоторое значение (например, 5). Теперь оно доступно по адресу $(sp). После того, как мы положим в стек следующее значение (скажем, 100500), 5 становится доступно по адресу 4($sp) (стек растёт вниз), а 100500 — $(sp). Добавление третьего снова изменит смещения относительно $sp. Каждый раз, помещая в стек или снимая оттуда значения, мы вынуждены использовать новые смещения для остальных данных в стеке
Для того, чтобы перевести $sp в состояние, пригодное для восстановления $ra, необходимо вести (в уме?) учёт всех сохранённых на стеке регистров и расположенных там локальных переменных, и снимать со стека ровно столько значений, сколько успели туда положить.
Возникает идея хранить в специально отведённом регистре (он называется Frame Pointer, $fp) состояние $sp на момент вызова функции. Тогда для восстановления $sp перед возвратом из функции достаточно будет переложить туда значение $fp. Предыдущее значение $fp при этом тоже надо будет сохранять на стеке, т. к. кадр локален для каждого вызова функции.
Пример конвенции с использованием кадра
Как обычно, в конвенции присутствует преамбула и восстановление стека, то есть код, дополнительно выполняемый вызывающей стороной, а также пролог и эпилог, то есть код, дополнительно выполняемый подпрограммой. Они заметно расширились — за удобство платим объёмом кода.
(преамбула) Передаваемые подпрограмме значения надо заносить в регистры $a
- (преамбула) Если передаваемых параметров больше 4, все остальные необходимо положить в стек в обратном порядке (последний, предпоследний, … шестой, пятый)
Вызов подпрограммы должен производиться командой jal или jalr
- Никакая вызываемая подпрограмма не модифицирует содержимое стека выше того указателя, который она получила в момент вызова
(пролог) Подпрограмма обязана сохранить на стеке значение $fp (старый кадр) в первую очередь
(пролог) Значение $sp, каким оно было на момент вызова подпрограммы, она обязана записать в $fp
(пролог) Подпрограмма обязана сохранить на стеке значения $ra и всех используемых ею регистров типа $s
- (пролог) Подпрограмма обязана выделить на стеке память для всех локальных переменных
Подпрограмма может хранить на стеке произвольное количество временных данных. Количество этих данных и занимаемого ими места на стеке не оговаривается и может меняться в процессе работы подпрограммы. Такие данные, например, могут образоваться в преамбуле вызова подпрограммы при размещении параметров в стеке. Локальные переменные рекомендуется размещать в пределах кадра.
Возвращаемое подпрограммой значение надо заносить в регистры $v
(эпилог) Подпрограмма обязана сбросить кадр путём восстановления $sp из $fp
(эпилог) Подпрограмма обязана восстановить из стека сохранённые значения $s, $fp и $ra
Возврат из подпрограммы должен производиться командой jr $ra
- (очистка стека) Если передаваемых параметров было больше 4, необходимо очистить стек от 5-го, 6-го и т. д. параметров
Согласно такой конвенции:
Смещение относительно $fp всех используемых в функции локальных данных постоянно. Можно, например, задать им мнемонические обозначения с помощью .eqv. Если локальных переменных много и они часто используются, мнемоника сильно упрощает работу с исходным кодом.
Восстановление стека перед выходом не зависит от актуального размера кадра, достаточно, чтобы $fp не изменился
Сброс кадра частично защищает программу от сноса стека (в большую сторону): если сам $fp не испорчен, и ошибочное изменение стека не добралось до сохранённых значений, ошибку можно локализовать при отладке. Такая ошибка возникает, например, если разместить какие-то данные в стеке, и забыть их оттуда снять
Дополнительные входные данные, передаваемые подпрограмме через стек, также доступны по фиксированным смещениям относительно $fp, причём, в силу порядка, 5-й параметр будет просто лежать по адресу ($fp), шестой — 4($fp) и т. д. (напоминаем, стек растёт вниз).
Что не менее важно, при отладке программы с неиспорченным стеком, можно автоматически отследить т. н. цепочку вызовов (call trace) — последовательность вызовов подпрограмм, которая привела к вызову текущей. В самом деле, в $fp хранится значение $sp на момент вызова процедуры. Значит, в 4$(fp) лежит сохранённое согласно конвенции предыдущее значение $fp. Перед которым на стеке лежит пред-предыдущее значение $fp и т. д.
Стоит заметить, что и эта конвенция
- неуниверсальна
- не для всего удобна
Например, мы можем потребовать, чтобы дополнительные параметры подпрограммы также входили в кадр (тогда инициализация кадра войдёт в преамбулу, зато не будет нужды в восстановлении стека после возврата), или, наоборот, чтобы в кадр входили только локальные переменные и временные данные (тогда сброс кадра становится слегка сложнее — к восстановленному $sp надо добавлять размер области сохраняемых регистров, зато адресация локальных переменных относительно начала кадра начинается прямо с 0).
Подпрограмма с использованием кадра
Это подпрограмма, сортирующая методом обмена массив целых размером $a0 байтов (т. е. $a0/4 элементов), лежащий по адресу ($a1). Подпрограмма не концевая — она вызывает ещё одну подпрограмму, поиск минимального элемента в массиве.
Подпрограмма использует два сохраняемых регистра $s для хранения счётчика и адреса обмена, поэтому эти два регистра сохраняются в кадре вместе с $fp и $ra
Подпрограмма запоминает адрес и размер массива в локальных переменных, чтобы затем вернуть их, согласно конвенции, в $v1 и $v0. Конечно, можно было бы и в сохраняемые регистры спасти эти значения, но чего не сделаешь ради удобного примера ☺
- Все смещения заданы .eqv-константами, в том числе и размер кадра FSIZE, который просто совпадает со смещением последней локальной переменной. Точка в именах констант собственного смысла не несёт, только для красоты.
1 function:
2 # общая подпрограмма
3 # a0 — размер массива
4 # a1 — начало массива
5 # v0 — размер выходного массива (того же самого :)
6 # v1 — начало выходного массива
7 .eqv FP -4 # Смещения в кадре
8 .eqv .RA -8($fp) # для сохраняемых регистров
9 .eqv .S0 -12($fp)
10 .eqv .S1 -16($fp)
11 .eqv .ARR -20($fp) # Смещения в кадре
12 .eqv .SIZE -24($fp) # для локальных переменных
13 .eqv FSIZE -24 # Размер кадра
14 sw $fp FP($sp) # Сохраняем кадр
15 move $fp $sp # Переставляем кадр
16 addiu $sp $sp FSIZE # Переставляем стек
17 sw $ra .RA # Сохраняем регистры
18 sw $s0 .S0
19 sw $s1 .S1
20
21 sw $a0 .SIZE # Размер массива
22 sw $a1 .ARR # Адрес массива
23
24 move $s0 $a0 # Регистры типа $s* не меняются
25 move $s1 $a1 # при вызовах функций
26 fnext: move $a0 $s0
27 move $a1 $s1
28 jal getmin
29 lw $t0 ($v0)
30 lw $t1 ($s1)
31 sw $t0 ($s1)
32 sw $t1 ($v0)
33 addiu $s1 $s1 4
34 addiu $s0 $s0 -4
35 bleu $a0 4 fnext ### TODO ??? A0 или s0?
36
37 lw $v0 .SIZE # Обращаемся к локальным переменным
38 lw $v1 .ARR
39
40 lw $ra .RA # Восстанавливаем регистры
41 lw $s0 .S0
42 lw $s1 .S1
43 move $sp $fp # Восстанавливаем стек
44 lw $fp FP($sp) # Восстанавливаем предыдущий кадр
45 jr $ra
Концевая подпрограмма не использует кадр, так что формально она не соответствует конвенции. Несмотря на то, что основные договорённости не нарушаются (все сохраняемые регистры целы, стек не тронут), отладка такой подпрограммы может представлять известную трудность по сравнению с отладкой подпрограммы с кадром, если всё-таки в ней появляются локальные переменные, сохранение регистров и т. п.
Впрочем, наша подпрограмма и стек не использует:
1 getmin: # концевая подпрограмма
2 # a0 — размер массива
3 # a1 — начало массива
4 # v0 — адрес минимального элемента
5 lw $t0 ($a1)
6 move $v0 $a1
7 gmnext: addiu $a0 $a0 -4
8 addiu $a1 $a1 4
9 blez $a0 gmfin
10 lw $t1 ($a1)
11 bge $t1 $t0 gmnext
12 move $t0 $t1
13 move $v0 $a1
14 j gmnext
15 gmfin: jr $ra
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 $v0 5
10 syscall
11 sw $v0 ($t1)
12 addiu $t1 $t1 4
13 bne $t2 $t1 input
14
15 li $a0 SZ
16 la $a1 Arr
17 jal function
18
19 la $t1 Arr
20 la $t2 EndArr
21 output: li $v0 1
22 lw $a0 ($t1)
23 syscall
24 li $a0 '\n'
25 li $v0 11
26 syscall
27 sw $v0 ($t1)
28 addiu $t1 $t1 4
29 bne $t2 $t1 output
30
31 li $v0 10
32 syscall
33
34 function:
35 # общая подпрограмма
36 # a0 — размер массива
37 # a1 — начало массива
38 # v0 — размер выходного массива (того же самого :)
39 # v1 — начало выходного массива
40 .eqv FP -4 # Смещения в кадре
41 .eqv .RA -8($fp) # для сохраняемых регистров
42 .eqv .S0 -12($fp)
43 .eqv .S1 -16($fp)
44 .eqv .ARR -20($fp) # Смещения в кадре
45 .eqv .SIZE -24($fp) # для локальных переменных
46 .eqv FSIZE -24 # Размер кадра
47 sw $fp FP($sp) # Сохраняем кадр
48 move $fp $sp # Переставляем кадр
49 addiu $sp $sp FSIZE # Переставляем стек
50 sw $ra .RA # Сохраняем регистры
51 sw $s0 .S0
52 sw $s1 .S1
53
54 sw $a0 .SIZE # Размер массива
55 sw $a1 .ARR # Адрес массива
56
57 move $s0 $a0 # Регистры типа $s* не меняются
58 move $s1 $a1 # при вызовах функций
59 fnext: move $a0 $s0
60 move $a1 $s1
61 jal getmin
62 lw $t0 ($v0)
63 lw $t1 ($s1)
64 sw $t0 ($s1)
65 sw $t1 ($v0)
66 addiu $s1 $s1 4
67 addiu $s0 $s0 -4
68 bleu $a0 4 fnext ### TODO ??? A0 или s0?
69
70 lw $v0 .SIZE # Обращаемся к локальным переменным
71 lw $v1 .ARR
72
73 lw $ra .RA # Восстанавливаем регистры
74 lw $s0 .S0
75 lw $s1 .S1
76 move $sp $fp # Восстанавливаем стек
77 lw $fp FP($sp) # Восстанавливаем предыдущий кадр
78 jr $ra
79
80 getmin: # концевая подпрограмма
81 # a0 — размер массива
82 # a1 — начало массива
83 # v0 — адрес минимального элемента
84 lw $t0 ($a1)
85 move $v0 $a1
86 gmnext: addiu $a0 $a0 -4
87 addiu $a1 $a1 4
88 blez $a0 gmfin
89 lw $t1 ($a1)
90 bge $t1 $t0 gmnext
91 move $t0 $t1
92 move $v0 $a1
93 j gmnext
94 gmfin: jr $ra
Промышленные конвенции
Описанные нами конвенции достаточно удобны, чтобы программировать «вручную»: весь код программы и подпрограммы пишется на языке ассемблера (возможно, разными программистами), при этом учёт сохраняемых на стеке данных и размер кадра программист «держит в голове».
Правда, даже для таких условий эти конвенции неполны:
Помимо работы с целочисленными ячейками (или, что то же самое, с адресами), архитектура MIPS поддерживает модель вещественной арифметики. Для этого в компьютере предусмотрено отдельное устройство (математический сопроцессор) и отдельный набор регистров (так называемые регистры $f),
- часть из вещественных также надо сохранять при вызове подпрограммы
- часть используется в качестве регистров передачи параметров
- часть используется в качестве регистров возврата значения
Не полностью описана ситуация, когда подпрограмме надо передавать массивы данных. Не всегда передавать все данные через стек, как в конвенции с кадром, очевидно, в этом случае надо формировать блок параметров в памяти, а в регистре передавать ссылку на этот блок. Неочевидно, надо ли регламентировать, где выделать такой блок — всё-таки на стеке, в статической памяти или в куче
Никак не регламентирован побочный эффект — модификация памяти вне стека.
- Частный случай побочного эффекта — возврат более, чем двух ячеек возвращаемых значений (на стеке? в куче?) также не регламентирован
Чем сложнее описываемый конвенцией случай, тем сложнее изобрести универсальную договорённость. Ниже пример нескольких документов, содержащий несколько версий «живых» ABI (application binary inverface), что соответствует части конвенций по вызову подпрограмм и запуску программ.
MIPSpro™ N32 ABI Handbook — несколько ABI
Пояснительный текст относительно этих ABI, содержащий показательные ремарки вида «это — очевидная, но бессмысленная попытка обеспечить совместимость» или «в ABI были включены значащие названия для плавающих регистров, но их всё равно почти никто не использует»
SYSTEM V APPLICATION BINARY INTERFACE для MIPS (250 страниц!)
Наконец, полноценный ABI, в отличие от «договорённостей» предназначен не только и не столько для людей-программистов, сколько для системных программ, занимающихся исходным и машинным кодом
- Транслятор из нескольких входных файлов должен обеспечивать изоляцию одних имён (меток) и видимость других (например, возможно вызвать подпрограмму по имени, но метки внутри этой подпрограммы не должны смешиваться с метка ми внутри вызывающего кода, и даже могут совпадать, не вызывая конфликта). Это накладывает некоторые требования к именованию и правлам видимости имён.
- Компоновщик из нескольких уже странслированных фрагментов программ формирует результирующий код. Для этого ему нужны знания о типе и размере данных, количестве параметров и возвращаемых значений функций, их типах и т. п. ABI должен описывать все возможные варианты и запрещать то, что не удалось описать
Компилятор с языка высокого уровня в язык ассемблера может не справиться с формированием произвольных эффективных пролога и эпилога, задействующих только используемые сохраняемые регистры, не использущих кадр, если тот не нужен и т. п. Универсальный ABI для высокоуровневых компиляторов может описывать код, содержащий
- Фиксированную преамбулу (например, полное сохранение временных регистров и их восстановление после возврата)
- Фиксированный пролог с полным сохранением сохраняемых регистров и даже, возможно, кадром фиксированного размера (в этом случае если локальных переменных меньше кадра, остальные его области не используются, а если больше — область под них выделяется в куче)
- Соответствующий прологу фиксированный эпилог
- Отладчики, профилировщики и прочие инструменты намного надёжнее работают с такими фиксированными ABI
- В преамбулу, пролог и эпилог может включаться программная защита кода (например, защита от сноса стека)
Системные вызовы
Операционная система
Задачи операционной системы: унификация, разделение и учёт ресурсов компьютера. Для взаимодействия с ОС программа следует некоторым соглашениям, называемым ABI (Application Binary Interface).
Под ресурсами поминаются оперативная память, процессорное время и разнообразные внешние устройства.
Унификация: прикладной программе гарантируется работа на различном оборудовании, с различными (совместимыми) версиями системного ПО. В состав дисциплины могут входить абстрактные системные объекты (файл, процесс, пакет, поток и т. п.), работа с которыми однотипна независимо от того, каким аппаратным ресурсом этот объект реализован. Например, файл может быть размещён на диске, на сетевом хранилище или вообще являться потоком ввода-вывода, как stid/stdout/stderr.
Разделение: прикладная программа пользуется ресурсами, не опасаясь вступить конфликт с другими программами или самой ОС, если тем вдруг вздумается воспользоваться теми же ресурсами. Для этого в ОС предусмотрены различные дисциплины доступа, постоянные или временные ограничения, блокировки и т. п. Типичные пример — разделение времени между задачами, одновременно работающими под управлением ОС
Учёт: возможность получения информации об использовании ресурсов как всей ОС в целом, так и каждой задачей в отдельности
Программный интерфейс использования ресурсов — системные вызовы — предоставляет т. н. ядро ОС
Ядро операционной системы — программный код, постоянно находящийся в памяти, имеющий доступ ко всем ресурсам компьютера и реализующий дисциплину их использования.
Аппаратная поддержка
Универсальная пользовательская инструкция «обратиться к ОС» — syscall
Фактически это — вызов подпрограммы, в котором вместо адреса используется заданный в API/ABI номер системного вызова. Адрес подпрограммы в ядре зависит от версии ОС, версии ядра ОС и даже последовательности загрузки отдельных модулей одного и того же ядра. Одна и та же программа не сможет работать во всех случаях, если будет использовать непосредственно адрес. Введение дополнительного уровня косвенности в виде номера системного вызова снимает проблему (в адрес подпрограммы этот номер превращает ядро).
- Прозрачный (невидимый пользователю) механизм выполнения syscall
- от полностью программного (выполняется машинный код из области ядра)
- до полностью аппаратного (нужную операцию выполняет компьютер)
- Защита памяти ядра
- Поддержка минимум двух потоков вычисления (пользовательская программа и ядро ОС)
разделение режимов работы процессора на режим ядра (полный доступ к ресурсам) и режим пользователя (ограниченный доступ и/или доступ к виртуализованным посредникам)
ВНИМАНИЕ! Большая часть системных вызовов в MARS реализована аппаратно!
Системные вызовы MARS
Описаны документация MARS
Системный вызов — механизм программного обращения к ядру операционной системы. На архитектурах, имеющих аппаратную поддержку режима ядра, реализован отдельной инструкцией.
Конвенции по вызову syscall в MIPS
В регистр $v0 помещается номер системной функции (service number)
В регистры $a0-$a3 или $f12 (для вещественных чисел) помещаются параметры системного вызова, если есть
Инструкция syscall передаёт управление операционной системе (обычно ядру, но, например, в MARS это может быть сразу сам MARS)
Возврат из системного вызова — по аналогии с возвратом из подпрограммы, на следующую после syscall инструкцию
Возвращаемые значения (если есть) помещаются в $v0, $a0-$a1 или в $f0 в соответствии с работой вызванной системной функции
Механизм работы syscall со стороны ядра ОС может быть разным.
Пример: вывести на консоль число, лежащее в регистре $t0
Некоторые системные вызовы MARS
Функция |
Тип |
Параметры |
Возвращаемое значение |
вывод целого |
1 |
$a0 = целое |
|
вывод вещественного |
2 |
$f12 = вещественное |
|
вывод вещественного двойной длины |
3 |
$f12 = двойное вещественное |
|
вывод строки |
4 |
$a0 = адрес ASCIIZ-строки |
|
ввод целого |
5 |
|
$v0 — введённое целое (word) |
ввод вещественного |
6 |
|
$f0 — введённое вещественное (float) |
ввод двойного вещественного |
7 |
|
$f0 — введенное двойное вещественное (double) |
ввод строки |
8 |
$a0 = адрес памяти для размещения строки |
Если строка короче буфера, все её символы записываются в буфер, после чего туда дописывается нулевой байт Если строка не короче буфера, в него записывается первые $a1-1 символов, а в последний оставшийся байт записывается 0 Таким образом формируется ASCIIZ-строка |
выделение памяти в Куче (sbrk) |
9 |
$a0 = размер требуемой памяти в байтах |
$v0 — адрес требуемой памяти |
останов (exit) |
10 |
|
|
вывод символа |
11 |
$a0 = символ |
Некоторые управляющие символы, например, перевод строки (код 10) тоже имеет смысл выводить |
ввод символа |
12 |
|
$v0 — считанный символ (в командной строке всё равно придётся нажать ещё и Enter |
системное время (time) |
30 |
|
Время выдаётся в милисекундах с начала мира (полночь на 1 января 1970 года), так что помещается как длинное целое в два слова $a0 = старшее слово $a1 = младшее слово |
приостановка выполнения (sleep) |
32 |
$a0 = время простоя в милисекундах. |
|
вывод шестнадцатеричного |
34 |
$a0 = целое |
|
вывод двоичного |
35 |
$a0 = целое |
|
вывод беззнакового |
36 |
$a0 = целое |
|
)
Замечания
- Строки — это последовательности ненулевых байтов, заканчивающихся символом с кодом 0 (однобайтным нулём) согласно формату ASCIIZ
Ввод заканчивается символом перевода строки (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 $v0 8
8 syscall
9 move $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: move $a0 $t0 # выведем счётчик
18 li $v0 1
19 syscall
20 li $v0 10
21 syscall
- В MARS реализованы и другие, более сложные или более экзотические системные вызовы, например
- Работа с файлами (13-16)
- Работа с MIDI-органичиком (31, 33)
- Работа со случайными числами (40-44)
Вызов диалоговых окон Java (!) (50-59) для ввода/вывода/опроса пользователя
Заказ памяти у системы
Статическая память выделяется при трансляции секций .data . В результате трансляции в определённых областях оперативной памяти (по умолчанию — начиная с 0x10010000) резервируются области, которые затем доступны с помощью меток или непосредственно по адресам. Области могут быть инициализированы начальными значениям (как в .word, .asciiz и т. п.), а могут остаться без изменения (как в .space). Добавление новых директив резервирования памяти в секцию .data приведёт к тому, что соответствующие ячейки окажутся после уже отведённых.
В процессе работы программы возникает необходимость хранить данные только в течение определённого времени. Например, данные, актуальные только в процессе вызова подпрограммы, соответствуют локальным переменным в языках программирования высокого уровня. Временные данные хранятся в стеке.
В других случаях память необходимо выделять на всё время работы программы, но размер их заранее неизвестен. Один раз это можно сделать, воспользовавшись в качестве базового адреса началом кучи — 0x10040000. Однако в дальнейшем придётся где-то хранить вершину кучи, чтобы следующая область динамически выделяемой на куче памяти не пересекалась с предыдущей.
В MARS этим занимается операционная система. Системный вызов 9, которому в $a0 передаётся объём заказываемой памяти, отведёт на куче соответствующую область и вернёт в $v0 её адрес. Следующий вызов syscall 9 вернёт адрес после уже заказанной области и т. д.
Пример. Напишем подпрограмму, которая заказывает память и тут же выводит адрес, полученный в результате системного вызова. В этом примере мы воспользовались конвенцией для концевой подпрограммы и не сохраняли на стеке ничего, кроме адреса.
Подпрограмма принимает в $a0 объём памяти, а возвращает в $v0 выделенный адрес.
1 newmem: li $v0 9 # Закажем память (объём уже в $a0)
2 syscall
3 addi $sp $sp -4
4 sw $v0 ($sp) # Сохраним адрес
5 move $a0 $v0 # Выведем адрес
6 li $v0 34 # как 16-ричное число
7 syscall
8 li $a0 10 # Выведем перевод строки
9 li $v0 11
10 syscall
11 lw $v0 ($sp) # Вспомним адрес
12 addi $sp $sp 4
13 jr $ra
Напишем программу, которая трижды просит у системы память, причём один раз — нечётного объёма в байтах:
- Следующий вывод программы покажет нам, что syscall 9 при выделении памяти выравнивает адрес на границу слова:
Несмотря на кажущуюся простоту, освобождать в куче память для повторного использования намного сложнее. Рассмотрим общую задачу выделения/освобождения памяти (т. н. memory management).
- Необходимо иметь возможность заказывать фрагменты памяти произвольного размера
- Необходимо иметь возможность освобождать произвольные заказанные ранее фрагменты памяти в произвольное время
Следовательно, относительно каждого фрагмента необходимо постоянно хранить метаинформацию — размер и местоположение.
Надо решить проблему фрагментации: если мы заказали 2048 фрагментов размером в килобайт (2 Мб суммарно), а затем освободили каждый второй, у нас не образовалось 1 Мб свободной памяти! Вместо этого у нас образовалось 1024 килобайтных фрагмента, никакие два их которых не идут в памяти подряд
- …
Один из простейших вариантов решения — собственно Куча, как алгоритм работы с динамической памятью (описан в литературе, не путать со структурой данных «куча»): все когда-либо запрошенные области памяти (занятые и уже освобождённые) составляют список, и когда приходит запрос на выделение памяти, сначала просматривается этот список (точнее, его часть, содержащая освобождённые области), а если подходящей освобождённой области нет, заводится новая. У Кучи есть масса модификаций, но это уже предмет курся «Операционные системы».
Относительно несложно освобождать только последний выделенный кусок (на манер того, как это устроено в стеке), но особого смысла в этом нет: если для решения задачи нужен стек, то и решать её надо с помощью стека.
Макроподстановка и макрокоманды
Макроподстановка — механизм поиска шаблона в тексте и замены его другим текстом. Полученный текст также может содержать шаблоны, так что процесс макроподстановки обычно рекурсивен.
Псевдоннимы
Примитивный макрос — директива .eqv имя строка, которая добавляет имя в список распознаваемых ассемблером лексем, а в результате препроцессинга (обработки текста перед трансляцией) происходит замена этой лексемы на строку
Макроподстановка и простые макросы
(Да, я знаю, что правильно «макро», а «макрос» — это множественное число но ничего не могу с собой поделать).
Механизм макроподстановки может быть и посложнее:
Первые 4 строчки — задание макроса exit, оно же макроопределение, последняя — использование этого макроса, оно же макрокоманда. (Не «вызов макроса», потому что на месте макрокоманды не будет никакой инструкции вызова, только то, что составляло тело макроса).
Добрый Mars даже распишет номера строк, в которых находилось макросово тело:
Здесь 7 и 8 — номера строк исходного текста, а <2> и <3> — номера строк, на которых располагалось тело макроса.
Сам макрос (в отличие от подпрограммы), конечно, ни во что не странслировался, потому что он — всего лишь задание нового правила для трансляции каждой макрокоманды.
Самое удобное в макроподстановке — параметризация макрокоманд. Общий вид макроопределения:
Например:
Здесь макрокоманда print дважды раскрывается в три инструкции, причём первая из них (move) в первом случае подставится в виде move $a0 $t0, а во втором — в виде move $a0 $t1:
Обратите внимание на то, как отмечает Mars номера строк исходного кода и строк в теле макроса.
Макроподстановка, вообще говоря, может не иметь никакого отношения к синтаксису того текста, в котором встречаются макросы (например, универсальные макропроцессоры m4 или cpp). В ассемблере MARS присутствует ограничение: параметрами макрокоманды могут быть только лексемы самого ассемблера, а не произвольные строки.
Такая реализация проще (для препроцессора и для последующей трансляции используется один и тот же анализатор), но не такая гибкая. Подставить «--» вместо $t0 в макрокоманде из примера не удастся ещё на этапе макорподстановки (ошибка «mips2.asm line 10 column 2: forward reference or invalid parameters for macro "print"» в строке с макрокомандой). А вот 100500 вместо $t0 пройдёт макроподстановку (потому что 100500 — это хорошее годное целое число), но полученный текст не пройдёт трансляцию с сообщением «mips2.asm line 10->2 column 11: "100500": operand is of incorrect type». Ошибка возникнет, с точки зрения ассемблера Mars, всё в той же строке 10, но по вине строки 2 макроопределения.
Кстати, print-ы в примере слились в одну строку, потому что никто не вывел между ними ещё и разделителя. Чтобы исправить это положение, не надо модифицировать основную программу! Достаточно добавить в макроопеделение print такой вывод:
Сама программа при этом разрастётся чуть ли не в два раза:
Макровзрыв
В макроопределении могу встречаться другие макрокоманды. В силу рекурсивной природы макроподстановки, эти макрокоманды будут в свою очередь тоже раскрыты, и так до тех пор, пока в полученном тексте не останется ни одной.
Определим новый макрос printS, который выводит строку, и input, который выводит строку-подсказку (задаётся непосредственным адресом), а затем вводит число. В макрос print тоже добавим подсказку. Ассемблер MARS позволяет определять несколько макросов с одинаковым именем, но разным количеством параметров. Воспользуемся этим.
1 .macro print %reg 2 move $a0 %reg 3 li $v0 1 4 syscall 5 li $a0 10 6 li $v0 11 7 syscall 8 .end_macro 9 10 .macro printS %addr 11 la $a0 %addr 12 li $v0 4 13 syscall 14 .end_macro 15 16 .macro print %msg %reg 17 printS %msg 18 print %reg 19 .end_macro 20 21 .macro input %msg %reg 22 printS %msg 23 li $v0 5 24 syscall 25 move %reg $v0 26 .end_macro 27 28 .data 29 msg1: .asciiz "First number: " 30 msg2: .asciiz "Second number: " 31 res1: .asciiz "Result 1: " 32 res2: .asciiz "Result 2: " 33 .text 34 input msg1 $t0 35 input msg2 $t1 36 print res1 $t0 37 print res2 $t1
Второй макрос print (тот, что с двумя параметрами0, получился совсем «короткий» — всего две макрокоманды. Но на самом деле он довольно-таки объёмистый, раскрывается в 9 инструкций ассемблера (в 10, с учётом псевдоинструкции la).. Наши четыре строчки кода программы превратились в 34 инструкции!
}} Если активно использовать удачно названные и спланированные макросы в своих программах - программы становятся хорошо читаемыми
- код программы разрастается с невероятной скоростью
Вопрос: Если вы использовали в программе 10 макрокоманд, каждая из которых состояла из 10 макрокоманд, каждая из которых состояла из 10 инструкций, сколько инструкций (не считая другого полезного кода) появится в оттранслированной программе?
Хорошим тоном считается составить подпрограмму, а её вызов уже «обернуть» в макрос. В этом случае макроподстановка растиражирует только преамбулу и вызов подпрограммы, а содержательный код будет оттранслирован единожды в её составе.
1 .text 2 _input: # $a0 — message / $v0 — input value 3 li $v0 4 4 syscall 5 li $v0 5 6 syscall 7 jr $ra 8 9 .macro input %msg %reg 10 la $a0 %msg 11 jal _input 12 move %reg $v0 13 .end_macro 14 15 _print: # $a0 — message, $a1 — number 16 li $v0 4 17 syscall 18 move $a0 $a1 19 li $v0 1 20 syscall 21 li $a0 10 22 li $v0 11 23 syscall 24 jr $ra 25 26 .macro print %msg %reg 27 la $a0 %msg 28 move $a1 %reg 29 jal _print 30 .end_macro 31 32 .data 33 msg1: .asciiz "First number: " 34 msg2: .asciiz "Second number: " 35 res1: .asciiz "Result 1: " 36 res2: .asciiz "Result 2: " 37 38 .text 39 main: 40 input msg1 $t0 41 input msg2 $t1 42 print res1 $t0 43 print res2 $t1
Такая программа уже стала короче предыдущей:
При дальнейшем использовании print и input будет прирастать на 4 инструкции, а не на 7 или 10.
Метки и макроподстановка
Мы уже знаем, что процесс макроподстановки достаточно умён, чтобы находить в макроопределении формальные параметры и подставлять вместо них фактические. Не меньше (а может быть, и больше) интеллекта ему требуется, чтобы отслеживать метки.
В самом деле, стоит появиться метке в теле макроопределения, как вторая же макрокоманда раскроется в последовательность инструкций, в которой окажется такая же метка, какая была в первой. По идее это должно привести к ошибке.
Однако ассемблер MARS во время макроподстановки переименовывает все метки, которые встретит в макроопределении — и задание меток, и обращение к ним. Правило такое: метка метка переименовывается в метку метка_M№, где № — это число, счётчик макрокоманд:
после макроподстановки будет выглядеть примерно как
}} Не слишком красивый приём, с учётом того, что программист может случайно сам завести такую метку в своей программе. Однако действенный: внутри раскрытого макроса метка актуальна, а во всей программе — уникальна.
Генерация меток наводит на мысль о том, что наши макрос-функции print и input можно сделать ещё более удобными, если строку-подсказку передавать макросу прямо в качестве параметра, а превращать в .asciiz уже в теле макроса:
1 .globl main 2 3 .text 4 _input: # $a0 — message / $v0 — input value 5 li $v0 4 6 syscall 7 li $v0 5 8 syscall 9 jr $ra 10 11 .macro input %msg %reg 12 .data 13 msg: .ascii %msg 14 .asciiz ": " 15 .text 16 la $a0 msg 17 jal _input 18 move %reg $v0 19 .end_macro 20 21 _print: # $a0 — message, $a1 — number 22 li $v0 4 23 syscall 24 move $a0 $a1 25 li $v0 1 26 syscall 27 li $a0 10 28 li $v0 11 29 syscall 30 jr $ra 31 32 .macro print %msg %reg 33 .data 34 msg: .ascii %msg 35 .asciiz ": " 36 .text 37 la $a0 msg 38 move $a1 %reg 39 jal _print 40 .end_macro 41 42 .text 43 main: 44 input "First input" $t0 45 input "Second input" $t1 46 print "First result" $t0 47 print "Second result" $t1
Обратите внимание на то, как чередуются .data и .text: на самом деле никакой чересполосицы кода и данных не получится, потому что каждая директива .data просто размещает последующие данные строго после содержимого предыдущей секции .data (если не задавать явно адрес — начиная с 0x10010000); то же самое верно и для .text (начиная с 0x400000). Кроме того, теперь в параметре задаётся только содержательная подсказка, а ": " «приклеивается» к ней уже в макросе. Полученный код столь же компактен:
}}
Свойства макроассемблера MARS
Замечания авторов MARS относительно их макроассемблера:
Макроопределение должно идти в тексте программы до соответствующей макрокоманды (иначе пришлось бы анализировать текст дважды)
Макроопределение локально в пределах одного файла. Это с очевидностью вытекает из самого процесса макроподстановки перед трансляцией. Если нужно, чтобы один и тот же макрос был виден из нескольких файлов, используйте .include
Вложенные макросы не поддерживаются, т. е. внутри макроопределения не может встречаться директива .macro
- Внутри макроопределения, как и в тексте программы, могут встречаться только ранее определённые макрокоманды, искать их определения далее по тексту никто не будет
Все метки меняются в процессе макроподстановки, превращаясь в метка_M№
(Замечание от меня: нет, на все! если передать метку в качестве параметр, а потом написать что-то вроде %label: , _M№ к ней не припишется. Не знаю, как и зачем это можно использовать…)
- Несколько макроса с одинаковым именем, но разным количеством параметров, считаются различными, и их можно использовать все
- Повторное определение макроса с тем же именем и тем же количеством параметров игнорируется, макрокоманда раскрывается в первое определение
Параметром макроса (в силу ограниченной реализации) может быть только атомарная лексема языка ассемблера. Например, параметром не может быть "4($t0)", потому что это две лексемы, а не одна
- Макросредства ассемблера не входят ни в какой стандарт и остаются на усмотрение авторов ассемблера
В больших многофайловых проектах принято все макросы складывать в отдельный файл и включать их в код программы с помощью директивы .include файл_с_макросами . Подпрограммы при этом складываются в другой файл (возможно. не один), т. н. «библиотеку», и подключаются посредством многофайловой сборки. На предыдущем примере:
Файл с программой prog.asm:
Файл с подпрограммами lib.asm:
На забываем метки всех подпрограмм, которые понадобятся в других файлах, объявлять как .globl
Файл с макросами macros.inc (имя файла не заканчивается на .asm в знак того, что его не нужно транслировать отдельно):
1 .macro input %msg %reg 2 .data 3 msg: .ascii %msg 4 .asciiz ": " 5 .text 6 la $a0 msg 7 jal _input 8 move %reg $v0 9 .end_macro 10 11 .macro print %msg %reg 12 .data 13 msg: .ascii %msg 14 .asciiz ": " 15 .text 16 la $a0 msg 17 move $a1 %reg 18 jal _print 19 .end_macro 20 21 .macro exit 22 li $v0 10 23 syscall 24 .end_macro
Чего нет в Mars
Макроассемблер Mars вполне достаточен для учебных целей, но не реализует много из того, что есть в промышленных средствах программирования на ассемблере
Библиотека макросов и подпрограмм. Чтобы написать большую программу, потребуется множество подпрограмм, реализующих стандартные приёмы работы — ввод-вывод, работа с дисками, управление внешними устройствами и т. п. Для этого в профессиональных инструментариях, типа NASM или Gnu Assebmler, имеются заранее подготовленные библиотеки макросов и подпрограмм. А мы пишем их сами
- «Настоящий» макропроцессор. Макропросессор в Mars опирается только на лексемы языка ассемблера и не имеет собственного языка. Это почти не мешает, но временами (как в примере с 4($t0) ) слегка неудобно
Адресная арифметика. Вычисление некоторых значений. смещений и размеров на основании уже известных адресов находится в ассемблере Mars в зачаточном состоянии.
Переменные периода трансляции. полезно уметь назначать мнемонические имена результатам таких вычислений, чего Mars делать тоже не умеет
Например SIZE=ArrEnd-Arr, и потом использование константы SIZE
⇒ Вычисление выражений с использованием переменных и констант. В промышленных макропроцессорах возможно вычисление любых арифметических выражений и задание констант для них. Ещё раз напомним, что всё это происходит до трансляции, и в оттранслированный код попадает результат таких вычислений
Условная трансляция. Наиболее полезное свойство вычислений в период трансляции — это возможность транслировать или не транслировать части текста в зависимости от результата этих вычислений. Например можно вставить исходный текст отладочные сообщения, но транслировать их только если определена некоторая переменная периода трансляции DEBUG. Как-нибудь так:
- Генерация макроопределений. Если разрешить создавать макросы внутри макросов, можно развёртывать целые семейства определений в зависимости от исходного параметра внешнего макроса
Конкатенация.. Иногда необходимо, чтобы результат постановки нескольких макросов интерпретировался затем как одна лексема языка (например, строка label##suffix##index превращалась при наличии констант suffix=_M и index=5 в label_M5). В Mars такого механизма нет
- Бывает очень полезно ограничить видимость меток сильнее, чем просто внутри файла. Например, если в файле задано несколько подпрограмм, в каждой из них хотелось бы иметь возможность использовать метки типа start, finish, loop или стандартные имена переменных. Это можно было бы сделать, введя особенный синтаксис временных меток или ограничить видимость меток специальной конструкцией «локальное пространство имён» и т. п. В целом макроассемблер Mars достаточен для написания программ среднего объёма, а написание действительно крупных проектов на языке ассемблера выходит за рамки данного курса
Д/З
Прочесть всю лекцию (сложное задание, я знаю
) Написать библиотеку нужных макроопределений. Эту библиотеку при реальной работе можно включать директивой .include, но при сдаче Д/З в EJudge надо вставлять непосредственно в код. Дальнейшие формулировки Д/З исходят из того, что такая библиотека есть, и ею можно пользоваться (соответственно уменьшается объём написанного кода). Например, вывод чисел теперь будет в столбик
. Предполагаю, что в библиотеке будут разные макросы ввода и вывода, push и pop, а также пролог и эпилог хорошей конвенциальной подпрограммы. На самом деле такой инклюдник можно писать по ходу: подвернётся подходящий макро — добавить.
TODO Примерные задания.
EJudge: CrtDraw 'ASCII-арт'
Input:Написать полную программу. Вводятся два целых числа, M и N, выводится «решётка» из символов «+», «-», «|» и « », в которой содержится M×N клеток.
Output:3 4
+-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+ | | | | +-+-+-+
EJudge: TacStr 'Задом наперёд'
Input:Написать полную программу, которая вводит строки до тех пор, пока не будет введена пустая (в действительности она состоит из двух символов — перевода строки и нулевого байта в конце), а затем выводит все непустые строки в обратном порядке — сначала последнюю, потом предпоследнюю, и т. д. до первой.
Output:404. Thats an error. The requested URL /sea was not found on this server. Thats all we know.
Thats all we know. The requested URL /sea was not found on this server. 404. Thats an error.
EJudge: KeySort 'Сортировка по ключу'
Input:Сортировка по ключу. Написать полную программу, в которой будет подпрограмма сортировки массива по адресу $a0 и $a1 элементов, причем в $a2 передаётся размер одного элемента (пока что всегда 4), а в $a3 — адрес подпрограммы сравнения двух элементов в памяти (эта подпрограмма, в свою очередь, принимает два параметра, $a0 и $a1). Программа вводит натуральное число N, затем — 0 или 1, затем — N штук целых чисел, сортирует их, и выдаёт в столбик. Написать две подпрограммы сравнения: если был введён 0, числа упорядочиваются по возрастанию, если 1 — по убыванию остатка от деления на 10 (сортировка должна быть устойчивой, например, пузырьком).
Output:9 0 34 456 2 5 567 2 2 0 42
0 2 2 2 5 34 42 456 567