Уровень 57: Вложенные вызовы и стек

Открыть уровень →

Задание

Цель: собрать цепочку вложенных вызовов: main вызывает funcA, funcA — funcB, funcB — funcC. Возврат по ra ломается при вложении — каждый ra перезаписывается. Решение — стек: кадр функции сохраняет ra в памяти (пролог addi sp, sp, -4 / sw ra, 0(sp); эпилог lw ra, 0(sp) / addi sp, sp, 4 / ret). sp ≡ x2, старт 0x1400 — исключающая граница над стеком 0x13C0–0x13FC. Числа тактов здесь НЕ предсказываются: уровень вводит много нового — просто соберите программу и добейтесь совпадения с эталоном. funcC — лист без кадра: 10, funcB добавляет 20, funcA — 30; main пишет результат в данные 0x1000. Защитное слово 0x13BC запрещено: чтение и запись — ERR_DATA_ADDRESS_FORBIDDEN с заморозкой.

Схема процессора не меняется: программы по-прежнему исполняет эталонное однотактное ядро (risc-run) во вкладке «Ассемблер». Новое — память получает карту со стеком, а программа — вложенные вызовы main → funcA → funcB → funcC.

Карта памяти уровня: данные программы — 0x1000–0x13B8; защитное слово 0x13BC — запрещено и для чтения, и для записи: обращение останавливает машину с ERR_DATA_ADDRESS_FORBIDDEN без побочных эффектов; стек — 0x13C0–0x13FC (16 слов, рост вниз); начальное значение sp — 0x1400, исключающая граница над стеком. Порядок проверок адреса: сначала кратность 4, потом защитное слово, потом окно данных.

Каноническая программа — «минимум: кадры и результат в DMEM». funcC — лист без кадра: x10 = 10; funcB добавляет 20, funcA — 30; main сохраняет результат в память данных по адресу 0x1000:

        li   sp, 0x1400      # указатель стека (lui x2, 0x1 + addi x2, x2, 0x400)
        li   x5, 0x1000      # база данных
        jal  ra, main        # вызов
.end                      # останов на месте возврата
main:   addi sp, sp, -4      # кадр main
        sw   ra, 0(sp)
        jal  ra, funcA
        lw   ra, 0(sp)
        addi sp, sp, 4
        sw   x10, 0(x5)      # результат 60 → 0x1000
        jalr x0, 0(ra)       # ret
funcA:  addi sp, sp, -4      # кадр funcA
        sw   ra, 0(sp)
        jal  ra, funcB
        lw   ra, 0(sp)
        addi sp, sp, 4
        addi x10, x10, 30
        jalr x0, 0(ra)
funcB:  addi sp, sp, -4      # кадр funcB
        sw   ra, 0(sp)
        jal  ra, funcC
        lw   ra, 0(sp)
        addi sp, sp, 4
        addi x10, x10, 20
        jalr x0, 0(ra)
funcC:  addi x10, x0, 10     # лист: без кадра
        jalr x0, 0(ra)

Задания уровня:

  1. Впишите шапку и тела функций так, чтобы побитно совпасть с каноном: 28 тактов, x10 = 60 в памяти 0x1000, возврат на .end (PC = 20), ra = 20, sp = 0x1400.
  2. Следите за окном стека в блоке «Исполнение»: три сохранённых ra ложатся в 0x13FC–0x13F4, маркер sp опускается и поднимается.
  3. Негатив: замените одну запись на sw x1, 0(x2) с x2 = 0x13BC — машина обязана замереть с ERR_DATA_ADDRESS_FORBIDDEN, не изменив ни памяти, ни регистров.
  4. Предсказывать такты на этом уровне не нужно: он вводит много нового, «Проверить» сразу сравнивает прогон с эталоном.

Попробуйте (без проверки): перепишите funcA так, чтобы она вызывала сама себя — рекурсивный fib с глубиной не больше 5 кадров. Стек из 16 слов выдержит, а трасса покажет, как кадры растут и схлопываются.

Решение для самопроверки

Сначала напишите кадры сами. Решение ниже — контрольный список.

Что должно получиться: вложенные вызовы совпадают с эталоном: 28 тактов, x10 = 60 и слово 0x1000 = 60, ra = 20, sp = 0x1400; негатив — sw в защитное слово 0x13BC даёт ERR_DATA_ADDRESS_FORBIDDEN без изменения памяти и регистров.

Шаг 1 — пролог и эпилог. Пролог: addi sp, sp, -4, затем sw ra, 0(sp). Эпилог: lw ra, 0(sp), затем addi sp, sp, 4 и ret (это jalr x0, 0(ra)). Порядок важен: сначала читаем ra, потом отпускаем кадр. Лист (funcC) не вызывает никого — кадр ему не нужен.

Шаг 2 — такты. Шапка: lui + addi + li(2 слова) + jal = 5; main — 7 команд; funcA — 7; funcB — 7; funcC — 2. Итого 5 + 7 + 7 + 7 + 2 = 28; останов .end такта не добавляет, PC замерает на 20.

Шаг 3 — проверка состояния. Итог: x10 = 60 (10 + 20 + 30), слово 0x1000 = 60, x1 = 20 (адрес возврата в main), x2 = 0x1400 (стек сбалансирован). Слова стека 0x13FC/0x13F8/0x13F4 остаются «грязными» — кадр снимается указателем, а не очисткой; маска сравнения смотрит только область данных 0x1000–0x13B8.

Шаг 4 — мутант «убрано восстановление ra». Уберите из funcA lw ra: к моменту возврата из B регистр ra всё ещё указывает на возврат из B в A. Эпилог A исполняется снова — и снова прыгает по тому же ra. PC закручивается по кругу, до останова программа не дойдёт (ядро упирается в лимит тактов). Это не ошибка каталога: jalr верит регистру, а не стеку.

Шаг 5 — защитное слово. li x2, 0x13BC и sw x1, 0(x2): кратность 4 в порядке, но адрес в запретной зоне — заморозка с ERR_DATA_ADDRESS_FORBIDDEN, память и регистры не меняются. Порядок проверок важен: 0x13BE сначала поймает кратность (ERR_DATA_ADDRESS_MISALIGNED), и только выровненное обращение дойдёт до проверки запретной зоны.

Проверь себя

Почему ra без сохранения ломается при первом же вложении?

Каждый jal перезаписывает ra: к возврату из funcA в нём лежит адрес возврата из funcB, и эпилог A прыгает по кругу до лимита тактов. Кадр сохраняет ra в памяти и возвращает его перед ret — jalr верит регистру, а не стеку.