Моя рекурсия зависла навсегда, и это был правильный результат

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

Написал рекурсию тем же способом. Программа напечатала подпись и повисла: не соврала, не упала, а именно повисла, навсегда. Вернуться ей было некуда, и починил я это за 10 минут.

А в конце статьи сломаю тот же код второй раз, уже по-другому, и вот тогда пойму, как мне повезло с первым отказом.

▍ Навигация по серии

• Часть 1. Двенадцать символов, двадцать один байт

• Часть 2. Мой код терял бы 230 байт из 231

• Часть 3. Моя рекурсия зависла навсегда ← вы здесь

Что получится в конце

Числа Фибоначчи, посчитанные рекурсивно на голом RISC-V:

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

Чем кончился прошлый приём

Напомню, как было: адрес возврата клали в свободный регистр, у каждой функции свой.

    jal     t6, putc        /* putc вернётся по t6 */    jal     t5, print_dec   /* print_dec по t5     */

Пока функции разные, всё честно. А теперь пусть функция вызовет саму себя.

fib_broken:    li      t0, 2    blt     a0, t0, fb_ret      /* база: fib(0)=0, fib(1)=1 */    mv      t1, a0              /* запомнили n */    addi    a0, t1, -1    jal     t5, fib_broken      /* вложенный вызов кладёт в t5 свой адрес */    mv      t2, a0    addi    a0, t1, -2    jal     t5, fib_broken    add     a0, a0, t2fb_ret:    jr      t5

Сразу оговорюсь, потому что сам подумал об этом первым делом: условие остановки тут есть, вторая строка. До бесконечности рекурсия не уходит, дело не в нём.

Ломается возврат, и ломается коварно: не сразу, а сильно позже того места, где напортачили.

Тут надо вспомнить, что jal t5, метка делает две вещи. Кладёт в t5 адрес следующей за собой строки и прыгает. То есть каждый вызов пишет в t5 своё, поверх чужого.

Проследим на fib(2), этого достаточно.

start зовёт fibbroken, в t5 ложится адрес возврата в start. Дальше строка jal t5, fibbroken вызывает fib(1) и кладёт в t5 адрес строки mv t2, a0. Всё, адрес возврата в _start исчез. Он нигде больше не хранился.

А теперь неприятное. Какое-то время всё ещё работает правильно. fib(1) возвращается по t5 ровно куда надо, fib(0) тоже: для них t5 как раз свежий. Сломан только самый внешний возврат, тот, который должен был уйти обратно в _start, и до него очередь дойдёт в самом конце.

Доходит. Внешний вызов досчитал ответ, выполняет jr t5, а там лежит адрес предпоследней строки его же тела. Управление уходит туда, оттуда снова на jr t5, и снова туда.

То есть остановиться-то рекурсия остановилась. Вернуться не смогла.

qemu-system-riscv32 -machine virt -nographic -bios none \    -kernel broken.elf -accel tcg,one-insn-per-tb=on -d cpu -D cpu.log

pc 8000005c    add  a0,a0,t2      t5 = 8000005cpc 80000060    jr   t5            t5 = 8000005c

Те же шаги рядом с тем, как это выглядит со стеком:

Программа печатает fib(5) без стека = и уходит в вечный цикл. Я убил её по таймауту.

Регистр один, а адресов возврата столько, сколько вложенных вызовов. Складывать их надо по порядку: последним пришёл, первым ушёл. Такая штука называется стеком.

Стек это просто кусок памяти

Я почему-то думал, что стек встроен в процессор. Ничего подобного: это область памяти, которую программа объявляет сама, в линкер-скрипте.

    .stack (NOLOAD) : {        . = ALIGN(16);        _stack_bottom = .;        . += 1024;        _stack_top = .;    } > RAM

NOLOAD значит, что грузить туда нечего: в файле программы этих байтов нет, они просто резервируются в памяти. Число там сначала было 4096, потому что 4 килобайта показались приличным размером; откуда взялось 1024, посчитаем в конце.

Чтобы куском начал пользоваться код, его адрес кладут в sp. Первой строкой программы:

_start:    la      sp, _stack_top

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

Обратите внимание, что кладётся верхняя граница: по соглашению стек растёт вниз, от больших адресов к меньшим, отсюда и вычитание, которое сейчас появится. Именно по соглашению, а не потому, что так устроен процессор. Расти он мог бы и вверх, просто все договорились иначе.

Пролог и эпилог

Вот та же функция, но по-человечески:

fib:    addi    sp, sp, -16         /* заняли кадр, 16 байт */    sw      ra, 12(sp)          /* спрятали адрес возврата */    sw      s3, 8(sp)    sw      s4, 4(sp)    ...    lw      ra, 12(sp)          /* достали обратно */    lw      s3, 8(sp)    lw      s4, 4(sp)    addi    sp, sp, 16          /* отдали кадр */    ret

Первые 4 строки называются прологом, последние 5 эпилогом. Между ними живёт тело функции, и она может вкладываться вглубь: адрес возврата лежит в памяти, а не в регистре, и вложенный вызов его не затрёт. Он займёт свой кадр ниже нашего, поработает и отдаст обратно.

Вглубь, но не бесконечно: кадров влезает столько, сколько нарезано памяти, у нас 1024 байта по 16 на кадр, то есть 64 штуки. Что бывает, когда очередной кадр не влез, разберём в конце. Забегая вперёд: не то, чего я ожидал.

Кадр занимает 16 байт, хотя полезного в нём 3 слова: соглашение требует держать sp кратным 16, и 4 байта просто пустуют. Дальше выяснится, что именно они спасли положение.

И мелочь, которая меня удивила: пролог выполняется до проверки базового случая, так что fib(1) тоже занимает полноценный кадр, хотя ничего не считает. Цепочка для fib(4) это 4 кадра, а не 3.

Соглашение о вызовах

Раз функции стали настоящими, им пора договориться, кто что портит. Правило простое: если значение должно пережить вызов, оно едет в s-регистр и сохраняется в кадре. А для того, что живёт три инструкции и умирает, есть t, там сохранять нечего.

У fib таких долгоживущих значений два: n и результат первого рекурсивного вызова. Оба должны пережить второй вызов, вот они и сидят в s3 и s4, а кадр их бережёт.

Почему Фибоначчи, а не факториал

Хотел взять факториал, как все. Начал писать и понял, что он ничего не покажет.

У факториала из функции идёт один рекурсивный вызов, и переживать между вызовами нечего: позвал себя, умножил на n, вернул. Кадр в такой рекурсии нужен ровно под адрес возврата, то есть стек в ней не виден.

У Фибоначчи вызова два подряд. Результат первого надо где-то держать, пока считается второй, а второй затопчет и a0, и все временные регистры. Вот тут кадр перестаёт быть формальностью: в нём лежит s4, и без него ничего не сходится. Тема статьи это стек, а не рекурсия вообще, а факториал показал бы рекурсию и спрятал стек.

Есть причина и попроще: в fib только сложение, а факториал требует умножения, которого в базовом наборе RV32I нет, как нет деления. Но это отговорка слабая, умножение сложением пишется строк за пять, тем же приёмом, что и деление в прошлой статье.

Цифры

Считаем fib(20) наивной рекурсией, без запоминания промежуточных значений.

Вызовов 21 891, а памяти нужно 320 байт: кадры живут только пока вызов не вернулся, и глубина не растёт дальше самой длинной цепочки.

Числа тут не мои, а программы. Размер кадра виден в дизассемблере первой же строкой, addi sp,sp,-16, а два остальных программа посчитала про себя сама. В репозитории рядом лежит boot-count.s: тот же код плюс 8 строк в прологе, которые считают вызовы и следят за самым нижним sp. make count && make run-count:

fib(20) = 6765вызовов: 21891пик по счётчику: 320 байтпик по заливке: 316 байт

Пик меряется двумя способами, и это не перестраховка: они меряют разное.

Счётчик прямолинеен. В прологе, сразу после addi sp, sp, -16, программа смотрит на sp и запоминает самое нижнее значение, какое видела. Вопрос, на который он отвечает: докуда заходил указатель.

Заливка работает с другого конца. Это известный приём из встраиваемой практики: перед стартом весь стек забивается одним и тем же байтом, я взял 0xaa, а в конце снизу вверх ищется первый байт, который перестал быть 0xaa. Всё, что ниже него, за время работы никто не тронул. А это уже не про указатель, а про то, что после него осталось записано.

Расходятся они ровно на 4 байта, и не врёт ни один. Пролог кладёт ra, s3 и s4 по смещениям 12, 8 и 4, а нижние 4 байта кадра, добитые для выравнивания, не трогает вовсе. Указатель туда опускался, запись туда не дошла, 0xaa в них так и остался.

И честно про слабость заливки, раз уж я ей меряю. Она показывает не глубину стека, а то, что перестало быть 0xaa. Затереть эти байты мог кто угодно, не обязательно кадр. А байт, в который случайно записали то же самое 0xaa, засчитается нетронутым. Как единственный измеритель не годится, как второе мнение рядом со счётчиком вполне.

Где я споткнулся

Решил, что разобрался со стеком, когда понял, что это просто память. Оказалось, я недоразобрался.

Я успокоился было на мысли «ладно, память наша, зато регистр sp процессорный». А потом попросил дизассемблер печатать номера регистров вместо имён, ключом -M numeric, и увидел на месте sp обычный x2, а на месте ra обычный x1, при тех же самых байтах. Никакого sp в наборе команд нет.

Имена не выдумка моего ассемблера. Они записаны в psABI, отдельном документе поверх спецификации процессора, и потому одинаковы во всех тулчейнах: и в GCC, и в LLVM, и в чужом коде, который вы подключите. Там же, в psABI, а не в железе, закреплено и то, что стек растёт вниз.

$ riscv-none-elf-objdump -d hello.elf80000098:  ff010113   addi  sp,sp,-168000009c:  00112623   sw    ra,12(sp)$ riscv-none-elf-objdump -d -M numeric hello.elf80000098:  ff010113   addi  x2,x2,-168000009c:  00112623   sw    x1,12(x2)

Ни одна инструкция базового набора не трогает x2 сама по себе. Нет push, нет pop, при исключении процессор тоже ничего никуда не кладёт. Перепишите пролог на x18, договоритесь, что указатель теперь там, и процессор не заметит подмены. Заметят отладчик и чужой код.

Одно исключение по всему набору всё же есть, и касается оно не x2, а x1. Спецификация советует процессору смотреть на x1 и x5 в переходах как на подсказку для предсказателя адресов возврата. Это про скорость предсказания ветвлений, а не про стек, и на нашем стенде ненаблюдаемо, но x1 в этом смысле всё-таки чуть менее обычный, чем остальные.

Я шёл сюда с картинкой из ARM и x86, где стек встроен в железо, а нашёл соглашение между людьми, которое держится на том, что все его соблюдают.

А вот главное. Код заработал с первого прогона, и меня это насторожило.

После двух статей, где эмулятор прятал от меня ошибку, «сразу заработало» перестало быть хорошей новостью. Стека я тогда зарезервировал 4096 байт при пике в 320: запас в 12 раз и взятый с потолка. А проверять, что очередной кадр влез, попросту некому: такой проверки нет нигде во всей цепочке. Что будет, если не влезет?

Поставил 128 байт вместо 4096 и собрал. Про стек сборка не сказала ни слова. Программа посыпалась.

Два прогона подряд, разница между ними в одной цифре линкер-скрипта:

было (4096 байт):fib(1..10): 1 1 2 3 5 8 13 21 34 55fib(20) = 6765стало (128 байт):fib(1..10): 1 1 2 3 5 8 13 21 34 55^Bfib(20)^A

^B и ^A не опечатка, это управляющие байты 0x02 и 0x01, вылезшие в поток вместо пробела и хвоста подписи. Числа при этом все до одного верные, перевода строки нет вовсе, а дальше программа зависла.

Вывод показывает симптом, а причину видно в памяти. Вот один и тот же адрес в двух сборках, 16 байт, снято монитором QEMU у работающей машины:

1024 байта стека:800001b0  28 32 30 29 20 3d 20 00  20 00 0a 00 00 00 00 00  |(20) = . .......|128 байт стека:800001b0  28 32 30 29 02 00 00 00  04 00 00 00 c8 00 00 80  |(20)............|

Первые 4 байта целы, (20) на месте. Дальше в исправной сборке лежит хвост строки fib(20) = и за ним пробел с переводом строки, а в сломанной вместо них кадр функции: промежуточный результат 2, аргумент 4 и адрес возврата 0x800000c8. Адрес настоящий, в дизассемблере по нему стоит add a0, a0, s4, инструкция сразу за вторым рекурсивным вызовом.

То есть строки никуда не делись, просто поверх них живёт стек.

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

Разбор по адресам: почему сломалось ровно так

Дно на 0x800001d0, вершина на 0x80000250: те самые 128 байт, 8 кадров. fib(8) укладывается впритык, sp доходит до дна и не переступает.

fib(9) это 9 кадров, sp уходит до 0x800001c0, на 16 байт ниже дна, прямо в буфер цифр. Но 34 в выводе верное, и не по везению: буфер заполняет print_dec, а работает он уже после возврата, когда кадры сняты.

На fib(10) указатель проваливается до 0x800001b0, на 32 байта ниже дна. Ниже буфера лежат строки, и вот тут ломается.

Дальше работает деталь, о которой я говорил в начале и сам забыл, когда считал. Пролог пишет только по смещениям 12, 8 и 4, а нижние 4 байта кадра, добитые для выравнивания, не трогает. Значит портится 0x1b4..0x1bf, а не 0x1b0..0x1bf. Дамп это и показал: (20) уцелело, потому что лежит ниже 0x1b4.

Строка начинается с 0x1ad, значит от неё осталось 7 байт, ровно fib(20). Пиши пролог все 16, осталось бы 3, и на экране было бы fib. 4 байта выравнивания спасли 4 символа.

А fib(20) потянулась бы на 20 кадров, 320 байт, это уже глубоко внутри кода. Оттуда программа и не вернулась.

Повторяется тремя командами: make small, riscv-none-elf-nm -n small.elf за адресами и python dump-mem.py small.elf 0x800001b0 за дампом.

Про переполнение стека не сказал никто: ни компоновщик, ни процессор, ни код. И заметьте, симптом на переполнение не похож, он похож на испорченную печать. Я сначала туда и полез, и потерял на этом вечер.

Вот тут стоит вернуться к началу статьи. В первом опыте рекурсия без стека зависла намертво, и я назвал это правильным результатом. Теперь понятно, почему.

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

Из двух отказов первый честный, второй подлый. Первый я починил за 10 минут, второй искал вечер, хотя знал, куда смотреть, потому что сам его и подстроил.

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

Сколько же стека нужно на самом деле

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

Досчитал: глубина для fib(n) это ровно n кадров по 16 байт, а осмысленное n упирается в 46, дальше результат не влезает в наше 32-битное число. Итого 736 байт, округлил до 1024 и вписал расчёт прямо в линкер-скрипт, чтобы следующий не гадал.

Разница между 4096 и 1024 тут не в экономии памяти, её у нас 128 мегабайт. Одно число посчитано, а другое угадано, и это разные состояния программы, даже когда угадано удачно.

Для тех, кто хочет разобраться сам

Ссылки из первых двух статей в силе, здесь то, что понадобилось в этой.

• Спецификация RISC-V, том Unprivileged.

• RISC-V psABI. Тот самый документ, в котором закреплены и имена регистров, и направление роста стека, и выравнивание кадра. Всё, что процессор не знает.

• RISC-V Reference Card. Две страницы таблиц: в одной колонке x0..x31, в соседней sp, ra и прочие имена из psABI. Удобно держать под рукой, чтобы видеть обе колонки сразу.

• Ассемблер RISC-V для начинающих. Соглашение о вызовах разобрано подробнее, чем у меня.

Итог

Есть стек, настоящие функции с аргументами и возвратом и рекурсия, которая правильно сворачивается обратно.

Код и история по шагам: github.com/Pro100lamer/uart-to-lang, тег article-03. Там же оба сломанных варианта, по команде на каждый: make broken это рекурсия без стека, make small тот же правильный код со стеком на 128 байт.

В следующей статье займёмся форматом ELF и линкером. Пора понять, откуда взялся адрес 0x80000000, почему сборка ругается на права RWX, и что вообще лежит в файле, который мы отдаём эмулятору.

А пока вопрос. Кто-нибудь всерьёз писал под голое железо без стека, не в учебном примере, а в работе? Мне интересно, где эта граница проходит на практике.