Инфраструктура (2)
Средство диагностики багов — трассировка
Мы уже знаем: программа — конечный автомат; если программа усложняется, усложняются и переходы автомата. Не говоря уже о деталях каждого состояния, даже то, какие переходы автомат совершил, полностью разглядеть трудно.
Разбирать этот процесс через GDB будет неэффективно. Чтобы повысить эффективность, можно через printf() вывести ту информацию, которая нас интересует. Раз нас интересуют детали переходов этого конечного автомата, значит нас интересует и ход выполнения программы. В программной инженерии информацию, которая записывает ход выполнения программы, называют трассировкой (trace). По трассировке можно судить, соответствует ли выполнение ожидаемому, и тем самым диагностировать баги.
Трассировка выполнения инструкций — itrace
NEMU уже реализовал простую функцию трассировки — itrace (instruction trace): она может записывать каждую инструкцию, выполненную гостевой программой. Реализация itrace очень проста: код лишь записывает каждую инструкцию, выбранную instr_fetch(), затем вызывает функцию дизассемблирования из проекта llvm (реализована в nemu/src/utils/disasm.cc). itrace выводит PC инструкции, её двоичное представление и результат дизассемблирования. В каркасном коде эта возможность по умолчанию включена; инструкции, выполненные гостевой программой, записываются в build/nemu-log.txt. Посмотрев этот файл, вы увидите, как работает гостевая программа.
NEMU может ограничивать момент вывода trace: можно вручную указать, когда их выводить, и даже задать свои условия вывода. Как именно — RTFSC. Поскольку сейчас поведение программы детерминировано, повторные запуски дадут тот же результат. Это помогает понять, когда программа оказалась в ошибочном состоянии.
Для регулярных trace можно ещё отфильтровать их текстовыми инструментами вроде grep, awk, sed и т.д. Поэтому если освоите shell-команды для обработки текста, эффективность отладки вырастет ещё.
Кольцевой буфер инструкций — iringbuf
Как правило, нас интересует только trace перед местом ошибки: при запуске больших программ ранний trace чаще всего не нужно ни смотреть, ни даже выводить. Естественная мысль: нельзя ли в момент ошибки гостевой программы (например, выход за границы физической памяти) вывести несколько последних выполненных инструкций?
Реализовать это нетрудно: достаточно поддерживать очень простую структуру данных — кольцевой буфер (ring buffer). Конкретно при выполнении каждой инструкции её информацию записывают в кольцевой буфер; если буфер полон, старое содержимое перезаписывается. Когда гостевая программа сталкивается с ошибкой, инструкции из кольцевого буфера печатают — как справку для отладки. Пример вывода ниже, где --> указывает инструкцию, на которой произошла ошибка.
0x80002b00: srli a2, a2, 1 00 16 56 13
0x80002b04: slli a1, a1, 1 00 15 95 93
0x80002b08: or a0, s1, a5 00 f4 e5 33
0x80002b0c: sub s0, s0, a5 40 f4 04 33
0x80002b10: jal -112 f9 1f f0 ef
0x80002aa0: lui a5, 524295 80 00 77 b7
0x80002aa4: lw a5, 2028(a5) 7e c7 a7 83
0x80002aa8: addi sp, sp, -32 fe 01 01 13
--> 0x80002aac: sw s2, 16(sp) 01 21 28 23
0x80002b3c: ret 00 00 80 67
0x80002b14: add s2, s2, a0 00 a9 09 33
0x80002b18: bnez s0, -40 fc 04 1c e3
0x80002af0: neg a5, s0 40 80 07 b3
0x80002af4: and a5, a5, s0 00 87 f7 b3
0x80002af8: or a2, s3, a5 00 f9 e6 33
0x80002afc: or a1, s4, a5 00 fa 65 b3
Реализовать iringbuf
По содержанию выше реализуйте iringbuf в NEMU. Формат вывода можете спроектировать по своему вкусу. Если хотите выводить дизассемблирование инструкции, смотрите связанный код itrace. Если не знаете, какой код куда добавить, нужен RTFSC.
Трассировка обращений к памяти — mtrace
Обращения к памяти занимают большую долю выполнения программы; если вы уже встречали связанные с памятью ошибки (например, выход за границы физической памяти), вам наверняка захочется знать конкретное поведение обращений программы к памяти и найти среди них неверные — чтобы диагностировать баг. На самом деле результаты обращений к памяти легко отслеживать и собирать трассировку памяти (memory trace).
Реализовать mtrace
Эта функция настолько проста, что вы уже придумали, как её реализовать: достаточно записывать в paddr_read() и paddr_write(). Формат вывода mtrace можете задать сами.
Однако в отличие от iringbuf, который выводит только один раз в конце, программы обычно выполняют много инструкций обращения к памяти. Значит, включённый mtrace породит огромный вывод, поэтому лучше уметь выключать mtrace, когда он не нужен. О, тогда посмотрите связанную реализацию itrace: попробуйте добавить соответствующий код в Kconfig и связанные файлы, чтобы включать и выключать mtrace через menuconfig. Можно также реализовать условия вывода mtrace: например, вас может интересовать только доступ к некоторому интервалу памяти. С таким условным управлением mtrace пользоваться гораздо гибче.
Трассировка вызовов функций — ftrace
itrace и mtrace оба трассируют программу с нижнего взгляда конечного автомата; но если хотим понять семантическое поведение программы, itrace и mtrace уже не помогут. Поэтому нужен инструмент, который трассирует семантическое поведение программы.
Вопрос: какую семантику выбрать? На курсе программирования мы учили: программа состоит из функций, функция — из операторов, оператор компилируется в несколько инструкций; значит, ясно нести семантику программы может только функция. Представьте: если спроектировать инструмент ftrace, который трассирует вызовы и возвраты функций в ходе выполнения, разве мы не узнаем, как примерно работает программа?
Это на самом деле нетрудно: itrace уже трассирует все инструкции, выполненные программой. Чтобы реализовать ftrace, достаточно заботиться об инструкциях вызова и возврата функций. В инструкции вызова можно записать адрес назначения — значит, будет вызвана некоторая функция; затем в инструкции возврата записать текущий PC — значит, возвращаемся из функции, где лежит этот PC. Добавить такой код в реализацию связанных инструкций легко. Но адрес назначения и значение PC всё ещё без семантики программы; если перевести их в имена функций, понять будет легче!
Дан адрес в сегменте кода — как узнать, в какой он функции? Тут помогает таблица символов (symbol table) в файле ELF. Таблица символов — секция исполняемого файла; она записывает некоторую информацию времени компиляции, в том числе о переменных и функциях. Чтобы реализовать ftrace, сначала нужно узнать, какая информация записана в таблице символов.
Возьмём пользовательскую программу add из cpu-tests: командой readelf посмотрим информацию об ELF-исполняемом файле.
riscv64-linux-gnu-readelf -a add-riscv32-nemu.elf
Вы увидите, что readelf выводит много информации, полезной для понимания структуры ELF; советуем внимательно прочитать её после занятий. Сейчас достаточно заботиться об информации таблицы символов; найдите её в выводе:
Symbol table '.symtab' contains 28 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 80000000 0 SECTION LOCAL DEFAULT 1
2: 80000108 0 SECTION LOCAL DEFAULT 2
3: 8000010c 0 SECTION LOCAL DEFAULT 3
4: 8000020c 0 SECTION LOCAL DEFAULT 4
5: 00000000 0 SECTION LOCAL DEFAULT 5
6: 00000000 0 FILE LOCAL DEFAULT ABS add.c
7: 00000000 0 FILE LOCAL DEFAULT ABS trm.c
8: 80000108 1 OBJECT LOCAL DEFAULT 2 mainargs
9: 800000e8 32 FUNC GLOBAL DEFAULT 1 _trm_init
10: 80009000 0 NOTYPE GLOBAL DEFAULT 4 _stack_pointer
11: 80000108 0 NOTYPE GLOBAL DEFAULT 1 _etext
12: 80000000 0 NOTYPE GLOBAL DEFAULT ABS _pmem_start
13: 8000022c 0 NOTYPE GLOBAL DEFAULT 4 _bss_start
14: 80000109 0 NOTYPE GLOBAL DEFAULT 2 edata
15: 80009000 0 NOTYPE GLOBAL DEFAULT 4 _heap_start
16: 80001000 0 NOTYPE GLOBAL DEFAULT 4 _stack_top
17: 80009000 0 NOTYPE GLOBAL DEFAULT 4 end
18: 80000010 24 FUNC GLOBAL DEFAULT 1 check
19: 80000108 0 NOTYPE GLOBAL DEFAULT 1 etext
20: 80000000 0 FUNC GLOBAL DEFAULT 1 _start
21: 00000000 0 NOTYPE GLOBAL DEFAULT ABS _entry_offset
22: 80000028 180 FUNC GLOBAL DEFAULT 1 main
23: 80000109 0 NOTYPE GLOBAL DEFAULT 2 _data
24: 8000010c 256 OBJECT GLOBAL DEFAULT 3 ans
25: 80009000 0 NOTYPE GLOBAL DEFAULT 4 _end
26: 800000dc 12 FUNC GLOBAL DEFAULT 1 halt
27: 8000020c 32 OBJECT GLOBAL DEFAULT 4 test_data
Каждая строка — элемент таблицы, каждый столбец перечисляет некоторые свойства элемента. Сейчас достаточно заботиться об элементах, у которых свойство Type равно FUNC. Внимательно посмотрев свойство Name, увидите: эти элементы как раз соответствуют функциям, определённым в программе; соответствующее свойство Value — их начальный адрес (можно сравнить с результатом дизассемблирования), а свойство Size даёт размер функции.
Исчезнувшие символы
В am-kernels/tests/cpu-tests/tests/add.c мы определили макрос NR_DATA, а в функции add() ещё локальную переменную c и параметры a, b. Но в таблице символов соответствующих элементов не найдёте — почему так? Подумайте: что вообще считается символом (symbol)?
О, через таблицу символов можно построить отображение между именами функций и их адресами! Но вывод readelf уже разобран: на самом деле свойство Name в таблице символов хранит смещение строки в таблице строк (string table). Чтобы посмотреть таблицу строк, сначала посмотрим информацию Section Headers в выводе readelf.
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 80000000 001000 000108 00 AX 0 0 4
[ 2] .sdata2.mainargs PROGBITS 80000108 001108 000001 00 A 0 0 4
[ 3] .data.ans PROGBITS 8000010c 00110c 000100 00 WA 0 0 4
[ 4] .data.test_data PROGBITS 8000020c 00120c 000020 00 WA 0 0 4
[ 5] .comment PROGBITS 00000000 00122c 00001c 01 MS 0 0 1
[ 6] .symtab SYMTAB 00000000 001248 0001c0 10 7 9 4
[ 7] .strtab STRTAB 00000000 001408 00009b 00 0 0 1
[ 8] .shstrtab STRTAB 00000000 0014a3 000055 00 0 0 1
Из информации Section Headers видно: таблица строк в файле ELF начинается со смещения 0x1408. Шестнадцатеричный вид файла ELF можно вывести напрямую следующей командой:
hd add-riscv32-nemu.elf
Посмотрите в выводе этой команды окрестность 0x1408: таблица строк — не более чем склеенные строки идентификаторов. Теперь можно прояснить отношение таблицы символов и таблицы строк:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 7] .strtab STRTAB 00000000 001408 00009b 00 0 0 1
|
+--------------+
++ V
00001400 |V 00 61 64 64 2e 63 00 74 | ........add.c.t|
00001410 72 6d 2e 63 00|6d 61 69 6e 61 72 67 73 00 5f 74 |rm.c.mainargs._t|
00001420 72 6d 5f 69 6e|69 74 00 ^ |rm_init._stack_p|
| |
| +----------------+
| |
+-----------------------------------------+ |
Symbol table '.symtab' contains 10 entries: | |
Num: Value Size Type Bind Vis Ndx Name | |
7: 00000000 0 FILE LOCAL DEFAULT ABS 7 (trm.c) | |
8: 80000108 1 OBJECT LOCAL DEFAULT 2 13(mainargs) --+ |
9: 800000e8 32 FUNC GLOBAL DEFAULT 1 22(_trm_init) -----+
Найти "Hello World!"
Напишите под Linux программу Hello World, скомпилируйте и описанным выше способом найдите таблицу строк ELF-файла. В каком месте таблицы строк вы нашли строку "Hello World!"? Почему так?
Теперь данный адрес можно перевести в имя функции: поскольку диапазоны функций не пересекаются, можно по очереди просмотреть каждый элемент таблицы символов со свойством Type, равным FUNC, и проверить, попадает ли данный адрес в интервал [Value, Value + Size); если да — по свойству Name элемента найти соответствующую строку в таблице строк и вернуть её как имя функции. Если подходящего элемента нет, можно вернуть строку "???"; впрочем, это скорее всего из-за ошибки в вашей реализации — проверьте её ещё раз.
Возьмём recursion из cpu-tests: частичный пример вывода ftrace ниже (только для справки; разные версии компилятора могут дать разный вывод, можно разбирать вместе с результатом дизассемблирования).
0x8000000c: call [_trm_init@0x80000260]
0x80000270: call [main@0x800001d4]
0x800001f8: call [f0@0x80000010]
0x8000016c: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x8000016c: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x8000016c: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x8000016c: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x8000016c: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x80000058: ret [f0] # note(2)
0x800000fc: ret [f2] # note(1)
0x80000180: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x80000058: ret [f0]
0x800000fc: ret [f2]
0x800001b0: ret [f3] # note (3)
0x800000fc: ret [f2]
0x80000180: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x8000016c: call [f2@0x800000a4]
0x800000e8: call [f1@0x8000005c]
0x80000058: ret [f0]
Реализовать ftrace
По содержанию выше реализуйте ftrace в NEMU. Формат вывода можете выбрать сами. Обратите внимание на следующее:
- NEMU нужно передать ELF-файл; это можно сделать, добавив связанный код в
parse_args() - при инициализации ftrace, возможно, нужно прочитать из ELF таблицу символов и таблицу строк, чтобы пользоваться ими дальше
- как разбирать файлы ELF, см.
man 5 elf - если выбрана riscv32, ещё нужно подумать, как из инструкций
jalиjalrправильно распознать инструкции вызова функции и возврата из функции
Несовпадающие вызовы и возвраты функций
Если внимательно посмотреть пример вывода recursion выше, заметите любопытное. Конкретно ret у note (1) совпадает с соответствующим call: call вызвал f2, и соответствующий ret тоже возвращается из f2; но у пары call и ret, указанной note (2), иначе: call вызвал f1, а возврат — из f0; у пары, указанной note (3), похожее: call вызвал f1, а возврат — из f3.
Попробуйте вместе с результатом дизассемблирования разобрать, почему так выходит.
Лишние таблицы символов
Напишите под Linux программу Hello World, затем командой strip отбросьте таблицу символов в исполняемом файле:
gcc -o hello hello.c
strip -s hello
Через readelf посмотрите информацию hello: таблица символов отброшена. Сможет ли программа hello успешно работать?
В объектном файле тоже есть таблица символов, её тоже можно отбросить:
gcc -c hello.c
strip -s hello.o
Через readelf посмотрите информацию hello.o: таблица символов отброшена. Попробуйте слинковать hello.o:
gcc -o hello hello.o
Какую проблему вы обнаружили? Сравните два случая и разберите причины.
Трассировка и оптимизация производительности
Мы просим вас реализовать инструменты trace в NEMU как инфраструктуру, чтобы помогать отладке. На самом деле, кроме того что trace помогает понять, как работает программа, он ещё может направлять разработчиков в оптимизации программ и систем, например:
- по ftrace можно дальше разобрать аргументы при вызове
memcpy(): выровнены лиdestиsrc, длинное копирование или короткое, — и по часто встречающимся комбинациям оптимизировать алгоритмmemcpy() - по ftrace можно посчитать число вызовов функций и оптимизировать те, к которым обращаются чаще, — это заметно поднимет производительность программы
- по itrace можно отфильтровать выполнение инструкций условного перехода и подать это на вход предсказателя переходов (branch predictor, узел современных процессоров, повышающий производительность), чтобы подстроить реализацию предсказателя и тем самым поднять производительность процессора
- по mtrace можно получить последовательность обращений программы к памяти и подать её на вход модели кэша (другой узел современных процессоров, повышающий производительность), чтобы направлять оптимизацию алгоритмов предвыборки и замещения (это вы ощутите в Lab4)
Trace так важен для оптимизации производительности, потому что отражает настоящее поведение программы: если с наскока оптимизировать функцию, которая вызовется один раз, такая оптимизация почти не поднимет общую производительность. А trace как раз показывает детальные события хода выполнения; если сделать по ним статистический анализ, станет ясно, какие события происходят часто, — и оптимизация именно частых событий статистически поднимает производительность программы и системы. Это и есть научный метод оптимизации производительности.
AM как инфраструктура
Написать klib, затем запустить программу string на NEMU и посмотреть, пройдёт ли тест. На поверхности это вроде нормально; но если тест не пройдёт, при отладке вы точно будете думать: klib написан неверно или в NEMU баг? Если этот вопрос не решить, сложность отладки вырастет: вполне можно неделю крутить NEMU и в конце обнаружить, что баг в реализации klib.
Проблема в том, что и ПО (klib), и железо (NEMU) написали вы, и правильность ни того ни другого не гарантирована на 100%. В школе все учили метод контроля переменных: если одну сторону заменить реализацией, которую считаем правильной, можно отдельно проверить правильность другой! Например, тестируем klib на настоящей машине: если тест не прошёл — проблема в klib, потому что аппаратной реализации настоящей машины можно верить всегда; наоборот, если тест прошёл — с klib всё в порядке, баг в NEMU.
Новый вопрос: правда ли ПО так легко перенести на другое железо для теста? Догадливый читатель уже вспомнит ядро идеи AM: через набор абстрактных API развязать программу и архитектуру. Идея AM гарантирует: код поверх AM (включая klib) не зависит от архитектуры — как раз это повышает переносимость. Представьте: если в string.c есть инструкция nemu_trap, которую можно выполнить только в NEMU, на настоящей машине она не запустится.
В abstract-machine есть особая архитектура native: API AM реализован средой выполнения GNU/Linux по умолчанию. Например, когда компилируем программу через gcc hello.c, она компилируется в среду выполнения GNU/Linux; Super Mario, в которую вы играли в PA1, тоже скомпилирована в native и запущена. По сравнению с $ISA-nemu у native такие плюсы:
- работает прямо на настоящей машине — поведению настоящей машины можно верить всегда
- даже если в ПО есть баги, на
nativeих отлаживать удобнее (например GDB — куда удобнее, чем monitor NEMU)
Поэтому вместо того чтобы сразу отлаживать ПО в $ISA-nemu, лучше сначала отладить ПО на native, затем перенести запуск в $ISA-nemu и тестировать уже NEMU. В abstract-machine программу легко скомпилировать на другую архитектуру: например, в каталоге am-kernels/tests/cpu-tests/ выполните
make ALL=string ARCH=native run
так программу string скомпилируете в native и запустите. Поскольку программы мы компилируем на разные архитектуры, следите за параметром ARCH в команде make. Если string не пройдёт тест, терминал выведет
make[1]: *** [run] Error 1
Разумеется, может вывестись и информация вроде ошибки сегментации.
Как порождается исполняемый файл native
Прочитайте связанный Makefile и попробуйте понять, как abstract-machine порождает исполняемые файлы native.
Странный код ошибки
Почему код ошибки — 1? Знаете ли вы, как программа make получает этот код ошибки?
Не радуйтесь слишком рано: при компиляции в native по умолчанию линкуется glibc; чтобы тестировать, нужно, чтобы вызовы этих библиотечных функций линковались к написанному нами klib. Это можно сделать, определив макрос __NATIVE_USE_KLIB__ в abstract-machine/klib/include/klib.h. Если макрос не определён, библиотечные функции слинкуются с glibc — её можно взять как правильную эталонную реализацию для сравнения.
Как это устроено?
Почему после определения макроса __NATIVE_USE_KLIB__ эти библиотечные функции на native линкуются к klib? Как именно это происходит? Попробуйте объяснить явление знаниями о линковке с занятий.
Хорошо, теперь реализацию klib можно тестировать и отлаживать на native, для отладки пользоваться выводом символов через putch() и даже GDB. Когда реализация верна, скомпилируйте программу в $ISA-nemu (не забудьте убрать вставленный при отладке putch()) и тестируйте NEMU.
Писать переносимые программы
Чтобы не портить переносимость программы, больше нельзя опираться на предположения, связанные с архитектурой: например, «длина указателя — 4 байта» больше не верно, потому что на native длина указателя — 8 байт, и программа, написанная по этому предположению, на native с большой вероятностью вызовет ошибку сегментации.
Разумеется, способы решить проблему есть; как именно — по старой привычке, STFW.
Протестируйте свой klib
Программа string просто вызывает функции klib: сама она — гостевая программа, чтобы тестировать реализацию NEMU, и реализацию klib проверяет недостаточно. Поэтому нужно написать достаточно тестовых случаев специально для реализации klib. Тестовый случай в основном состоит из тестового входа и тестового выхода; если хотим эффективно строить тесты, нужно найти способ получить тестовый выход независимо от объекта теста.
+----> Объект теста ----> Фактический вывод
| |
Вход +----> Одинаково?
| |
+----> Некоторый метод ----> Ожидаемый вывод
В klib функции, которые нужно реализовать, в основном трёх классов.
- Функции записи в память и строки, например
memset(),strcpy()и т.д. - Функции только чтения памяти и строк, например
memcmp(),strlen()и т.д. - Функции форматированного вывода, например
sprintf()и т.д.
Для первого класса: как построить тестовый сценарий, чтобы ожидаемый выход было легко получить каким-то методом? Заметьте: все эти функции пишут в область памяти. Рассмотрим следующий массив.
#define N 32
uint8_t data[N];
void reset() {
int i;
for (i = 0; i < N; i ++) {
data[i] = i + 1;
}
}
В таком массиве каждый элемент — 1 байт, и значения у всех разные. Если тестировать на этом массиве, любой неверный байт фактического вывода с большой вероятностью будет пойман. Чтобы получить ожидаемый выход, ещё нужно подумать об ожидаемом поведении тестируемой функции: все функции выше пишут в непрерывный интервал массива, поэтому ожидаемый выход можно проверить тремя кусками:
- первый — слева от интервала записи: туда не писали, поэтому должно быть
assert(data[i] == i + 1) - второй — сам интервал записи: ожидаемый результат связан с конкретным поведением функции
- третий — справа от интервала записи: туда не писали, поэтому должно быть
assert(data[i] == i + 1)
Тогда можно написать две вспомогательные функции для проверки:
// проверить, что значения в интервале [l,r) идут как val, val + 1, val + 2...
void check_seq(int l, int r, int val) {
int i;
for (i = l; i < r; i ++) {
assert(data[i] == val + i - l);
}
}
// проверить, что все значения в интервале [l,r) равны val
void check_eq(int l, int r, int val) {
int i;
for (i = l; i < r; i ++) {
assert(data[i] == val);
}
}
С этими двумя функциями можно перебирать разные входы и легко писать ожидаемый выход тестируемой функции. Например, для memset() можно написать такой тестовый код.
void test_memset() {
int l, r;
for (l = 0; l < N; l ++) {
for (r = l + 1; r <= N; r ++) {
reset();
uint8_t val = (l + r) / 2;
memset(data + l, val, r - l);
check_seq(0, l, 1);
check_eq(l, r, val);
check_seq(r, N, r + 1);
}
}
}
Написать больше тестов
Попробуйте понять, как тестовый код выше проводит проверку, и в каталоге am-kernels/tests/ добавьте новый набор тестов klib-tests для klib; структуру файлов можно взять с am-kernels/tests/am-tests или am-kernels/kernels/hello.
Затем напишите тестовый код для первого класса функций записи, описанного выше. При написании тестов учтите:
- поведение
memcpy()при перекрытии интервалов — UB; при переборе можно проверять, перекрываются ли интервалы, и если да — пропускать эту проверку; либо взять другой такой же массив какsrc, тогда перекрытия не будет - у функций обработки строк отдельно следите за
\0и переполнением буфера
Написав, сначала на native проверьте свой тестовый код библиотечными функциями glibc, затем на native этими тестами проверьте реализацию klib, наконец запустите тесты на NEMU, чтобы проверить реализацию NEMU.
Эти библиотечные функции такие простые, можно не тестировать?
Можно. Но непротестированный код всегда неверен, и позже этими функциями вы будете писать более сложные программы (например ОС); если не хотите потом себя подставить, лучше сейчас потратить время на тесты. Кроме того, если позже захотите оптимизировать эти функции (например memcpy() и memset() потом используют часто), возможно, напишете чуть более сложный алгоритм — и тогда увидите, насколько эти тесты важны.
Написать больше тестов (2)
Попробуйте добавить в klib-tests тесты для второго класса функций только чтения, например memcmp(), strlen() и т.д. Подумайте: как получить ожидаемый выход функции?
Наконец, функции форматированного вывода. Возьмём %d: нужно построить некоторые входы. Но диапазон целых слишком велик, все не перебрать, поэтому нужно выбрать представительные целые. В стандартном заголовке C limits.h есть определения наибольших и наименьших чисел; можно открыть /usr/include/limits.h и прочитать. Некоторые представительные целые могут быть:
int data[] = {0, INT_MAX / 17, INT_MAX, INT_MIN, INT_MIN + 1,
UINT_MAX / 17, INT_MAX / 17, UINT_MAX};
Чтобы получить соответствующий ожидаемый выход, можно сначала написать программу native и вывести их через printf, затем уложить вывод в тестовый код. Ожидаемый выход в cpu-tests порождён так же.
Написать больше тестов (3)
Попробуйте добавить в klib-tests тесты для функций форматированного вывода. Фактический выход можно сначала напечатать в буфер через sprintf(), затем сравнить с ожидаемым через strcmp().
Можно также рассмотреть реализацию ширины, точности, модификаторов длины и т.д., и породить соответствующие тестовые случаи.
Differential Testing
Поняв процесс выполнения инструкций, добавлять разные инструкции — уже скорее инженерная реализация. В инженерной реализации баги неизбежны; как быстро отладить, когда реализация неверна, тоже относится к инфраструктуре. Подумайте: при декодировании инструкций так много (у x86 самих инструкций уже много), у некоторых поведение ещё довольно сложное (большинство инструкций x86 сложные), если реализация где-то ошибочна — как это обнаружить?
Интуитивно это кажется непростым, но давайте разберём, почему. Допустим, мы случайно заполнили неверный тип у какой-то инструкции: когда NEMU дойдёт до неё, будет декодировать неверным типом, и либо возьмёт неверные исходные операнды, либо запишет верный результат в неверный операнд назначения. Тогда результат выполнения этой инструкции в NEMU нарушит её исходную семантику, и дальше зависящие от неё инструкции тоже не смогут выполниться правильно. С точки зрения нарушения соглашения результат — UB. В итоге увидим: гостевая программа выходит за границы памяти, зацикливается, или HIT BAD TRAP, или даже сам NEMU ловит ошибку сегментации.
Методы отладки мы уже обсуждали в PA1; однако для багов реализации инструкций эти методы всё ещё слабо работают: через assert() правильное поведение инструкции выразить трудно, а printf() и GDB на самом деле не сокращают расстояние между error и failure.
Если есть способ выразить правильное поведение инструкции, на нём можно строить проверки в духе assert(). Так что же выражает правильное поведение инструкции? Самое прямое, конечно, руководство ISA; но инструкции в NEMU мы как раз и реализуем по поведению из руководства ISA — один и тот же набор методов нельзя использовать и для реализации, и для проверки. Было бы хорошо иметь эталонную реализацию руководства ISA. Эй! Разве настоящая машина, которой мы пользуемся, не реализована по руководству ISA? Пусть каждая инструкция, выполненная в NEMU, выполнится и на настоящей машине, затем сравним состояние NEMU и настоящей машины: если состояния не совпали — мы поймали error!
Это на самом деле очень действенный метод тестирования; в области тестирования ПО его называют differential testing (далее DiffTest). Обычно для DiffTest нужен REF (Reference, эталонная реализация) с той же функцией, что у DUT (Design Under Test, объект теста), но с другой реализацией; затем им дают один и тот же определённый вход и смотрят, одинаково ли поведение.
Мы только что говорили о «состоянии» — что именно это значит? В PA1 мы уже поняли: и программу, и компьютер можно рассматривать как конечный автомат, состояние можно записать парой S = <R, M>, где R — значения регистров, M — значения памяти. Чтобы проверить, верна ли реализация инструкции, достаточно проверить, совпадают ли состояния DUT и REF после её выполнения! DiffTest очень своевременно ловит error: в первый момент, когда состояние NEMU отличается от настоящей машины, это как раз из-за неверной реализации текущей инструкции. Тогда до error очень близко: error не успевает распространиться дальше, и вернуться к fault тоже гораздо легче.
Какая прекрасная возможность — и за ней ещё глубокий принцип сути компьютера! Но жаль: не забудьте, что на настоящей машине работает ОС GNU/Linux, программы AM, скомпилированные в x86-nemu, в native запустить нельзя, а программы mips32 и riscv32 настоящая машина тем более не выполнит напрямую. Поэтому нужен не только верный реализатор руководства ISA, но и чтобы на нём корректно работали программы AM, скомпилированные в $ISA-nemu.
В PA1 мы представляли: NEMU — полносистемный эмулятор. Можно взять другие полносистемные эмуляторы как REF: они симулируют полную компьютерную систему, а цель NEMU — лишь подмножество, поэтому программа, которая работает в NEMU, естественно сможет работать и на другом эмуляторе. Итак, чтобы методом DiffTest проверить правильность реализации NEMU, пусть NEMU и другой эмулятор поинструкционно выполняют одну и ту же гостевую программу. После каждой инструкции обе стороны проверяют состояние регистров и памяти; если состояния не совпали — сразу сообщают об ошибке и останавливают выполнение гостевой программы.
Инфраструктура — секрет победы в Кубке Loongson
Идея DiffTest очень проста: найти правильную реализацию и сравнить с ней результат. На самом деле в генераторе выражений, который вы реализовали в PA1, тоже заложена идея DiffTest: программа на C — это REF. cpu-tests в am-kernels тоже: эти тесты сначала запускают на native, получают правильный результат, и вы по сути берёте native как REF, чтобы сравнить результат работы программы (HIT GOOD/BAD TRAP).
Конечно, зерно DiffTest, о котором здесь речь, тоньше: сравниваем не только итог работы программы, а поведение каждой инструкции. Так можно быстро найти и локализовать баги реализации инструкций. Эту идею мы унаследовали на Кубке Loongson: CPU, написанный на verilog/chisel, — DUT, уже реализованный NEMU — REF, и баги в verilog/chisel находятся и чинятся очень быстро. С помощью DiffTest на втором Кубке Loongson мы записали миф:
за неделю правильно реализовать процессор с полным внеочередным исполнением и запустить на нём самодельную ОС разделения времени с многозадачностью Nanos и сложное приложение Chinese paladin
Другой пример силы DiffTest — горячая тема июля 2020: пятеро бакалавров Университета Китайской академии наук с ультражёстким дипломом: выпуск со спроектированным ими процессорным чипом. Под руководством преподавателей студенты через DiffTest сравнивали свой дизайн процессора с NEMU онлайн: за 5 дней успешно загрузили Linux и запустили набор Busybox, за 4 дня успешно загрузили Debian и запустили сложные приложения вроде GCC и QEMU. Студенты ещё делились опытом дизайна процессоров на семинаре альянса 2020 (video, slide) и RISC-V Global Forum (video, slide); DiffTest в обоих случаях подавали как ключевую технику.
Эти примеры снова и снова показывают важность инфраструктуры: развитая инфраструктура делает дизайн CPU эффективным и простым, даже задачи, которые предшественники не могли выполнить. С инфраструктурой пугающий аппаратный дизайн процессора может переродиться: почти не нужно смотреть головокружительные осциллограммы, чтобы отлаживать аппаратный код. В области аппаратного дизайна недавно поднялась волна agile-разработки — роль инфраструктуры в ней очевидна. Если это интересно, пишите нам — вместе искать, куда развивать инфраструктуру.
Чтобы было удобнее реализовать DiffTest, между DUT и REF определили такой набор API:
// скопировать `n` байт между `buf` в host memory DUT и `addr` в guest memory REF;
// `direction` задаёт направление копирования: `DIFFTEST_TO_DUT` — копировать в DUT, `DIFFTEST_TO_REF` — копировать в REF
void difftest_memcpy(paddr_t addr, void *buf, size_t n, bool direction);
// когда `direction` — `DIFFTEST_TO_DUT`, прочитать состояние регистров REF в `dut`;
// когда `direction` — `DIFFTEST_TO_REF`, задать состояние регистров REF равным `dut`;
void difftest_regcpy(void *dut, bool direction);
// дать REF выполнить `n` инструкций
void difftest_exec(uint64_t n);
// инициализировать функцию DiffTest у REF
void difftest_init();
При этом состояние регистров dut требует, чтобы члены-регистры шли в некотором порядке; если порядок не соблюдён, поведение difftest_regcpy() не определено (так ответственность сваливаем на вас ^_^). REF должен реализовать эти API, DUT будет ими пользоваться для DiffTest. Здесь DUT и REF — соответственно NEMU и другие эмуляторы.
Каркасный код NEMU уже подготовил функцию DiffTest; в menuconfig включите соответствующую опцию:
Testing and Debugging
[*] Enable differential testing
Затем перекомпилируйте NEMU и запускайте. Система конфигурации NEMU по ISA выберет подходящий эмулятор как REF:
- x86: KVM. KVM через аппаратную виртуализацию может прямо на железе поднять компьютерную систему, как настоящая машина. KVM даёт пользовательским программам Linux набор API на основе
ioctl(); через этот API можно ввести железо в режим виртуализации, положить туда гостевую программу, выполнить её и получить её состояние. - mips32: QEMU. QEMU — полный полносистемный эмулятор, поддерживает несколько ISA. Но состояние QEMU мы можем получать только через протокол GDB на сокетах, накладные расходы связи велики. Чтобы запускать QEMU, его ещё нужно установить:
apt-get install qemu-system
- riscv32: Spike. Spike — полносистемный эмулятор сообщества RISC-V, работает очень похоже на NEMU. Чтобы реализовать API DiffTest, мы добавили в Spike немного интерфейсов, спасибо Chenlu выпуска 2018. Поскольку в Spike много исходных файлов, компиляция может занять несколько минут. Чтобы запускать Spike, нужно установить ещё один инструмент.
apt-get install device-tree-compiler
Исправить ошибки компиляции Spike
8 апреля 2023 в 01:15 мы обновили код Spike. Если код NEMU вы получили до этого времени, а код Spike — после, можете столкнуться с ошибкой компиляции tools/spike-diff/difftest.cc; обновите связанные файлы по этой странице.
Если код Spike получен до указанного времени или код NEMU — после, об этом можно не беспокоиться.
Игнорировать следующие сообщения при компиляции Spike
Следующая информация на результат компиляции Spike не влияет, её можно игнорировать.
Makefile:349: warning: overriding recipe for target 'disasm.o'
Makefile:349: warning: ignoring old recipe for target 'disasm.o'
make[2]: Circular libcustomext.so <- libcustomext.so dependency dropped.
make[2]: Circular libsoftfloat.so <- libsoftfloat.so dependency dropped.
В nemu/tools/difftest.mk уже заданы соответствующие правила и параметры: автоматически зайдут в соответствующий подкаталог nemu/tools/ (kvm-diff, qemu-diff или spike-diff), скомпилируют динамическую библиотеку и передадут её как аргумент опции --diff у NEMU. После включения DiffTest init_difftest() в nemu/src/cpu/difftest/dut.c дополнительно сделает следующее:
- откроет переданный файл динамической библиотеки
ref_so_file - через динамическую линковку выполнит разрешение символов и перемещение указанных выше API в динамической библиотеке и вернёт их адреса
- инициализирует функцию DiffTest у REF; конкретное поведение зависит от REF
- скопирует guest memory DUT в REF
- скопирует состояние регистров DUT в REF
После этой инициализации DUT и REF в одинаковом состоянии. Дальше можно сравнивать состояния после каждой инструкции; это делает функция difftest_step() (определена в nemu/src/cpu/difftest/dut.c). Её вызывают в главном цикле cpu_exec(): после выполнения одной инструкции в NEMU в difftest_step() дают REF выполнить ту же инструкцию, затем читают регистры REF и сравнивают. Поскольку регистры у разных ISA разные, каркас абстрагировал сравнение регистров в API, связанный с ISA, — функцию isa_difftest_checkregs() (определена в nemu/src/isa/$ISA/difftest/dut.c). Вам нужно реализовать isa_difftest_checkregs(): сравнить регистры общего назначения и PC со значениями регистров, прочитанными из DUT. Если сравнение совпало, функция возвращает true; если значения разные — false, и каркас автоматически остановит гостевую программу. В частности, когда сравнение isa_difftest_checkregs() не совпало, второй параметр pc должен указывать на инструкцию, из-за которой сравнение разошлось, — это можно использовать для печати подсказки.
Реализовать DiffTest
Выше, представляя соглашение API, мы говорили: состояние регистров r должно располагать регистры в некотором порядке. Сначала нужно RTFSC, найти этот порядок и проверить, удовлетворяет ли ему уже ваша реализация NEMU.
Затем добавьте соответствующий код в isa_difftest_checkregs(), чтобы реализовать ядро DiffTest. Когда реализация верна, у вас будет необычайно мощный инструмент тестирования.
Ощутив силу DiffTest, подумайте: как инфраструктура, сколько времени на отладку DiffTest вам сэкономит?
Э? А состояние памяти сравнивать не нужно? На самом деле получить из REF позиции памяти, которые изменила инструкция, нелегко, а сравнивать всю память — большие накладные расходы, поэтому состояние памяти мы не сравниваем. Упрощённая реализация NEMU ещё приводит к тому, что состояние некоторых регистров не совпадает с REF, например EFLAGS у x86: NEMU реализовал лишь немногие флаги EFLAGS и упростил обновление EFLAGS некоторыми инструкциями. Кроме того, некоторые особые системные регистры тоже реализованы не полностью. Поэтому наш DiffTest сравнивает состояния REF и NEMU не полностью; но и память, и особые регистры, если их изменила инструкция гостевой программы, вскоре снова будут использованы — и тогда различие состояния всё равно поймается. Итак, мы жертвуем частью точности сравнения ради производительности; но даже так DiffTest нужно общаться с REF и давать REF выполнять инструкции, поэтому скорость NEMU всё равно упадёт. Поэтому, если не отлаживаете, включать DiffTest при запуске NEMU не советуем.
Упрощения NEMU приводят к тому, что поведение некоторых инструкций отличается от REF, и сравнивать их нельзя. Чтобы это решить, в каркасе подготовили две функции: difftest_skip_ref() и difftest_skip_dut():
Есть инструкции, которые REF нельзя выполнить напрямую, или поведение после выполнения наверняка отличается от NEMU. Например, инструкция
nemu_trap: в REF после выполнения будет отладочное исключение. Это можно калибровать черезdifftest_skip_ref(): после её вызова вdifftest_step()REF пропустит выполнение текущей инструкции и сразу синхронизирует в REF текущее состояние регистров NEMU. Эффект эквивалентен «результат выполнения этой инструкции берём по состоянию NEMU».Из-за особенностей реализации QEMU иногда упаковывает несколько инструкций и выполняет их вместе. Тогда один вызов
difftest_step()— и QEMU выполнит несколько инструкций. Ноfetch_decode_exec_updatepc()в NEMU выполняет по одной инструкции, и появится расхождение. Это можно калибровать черезdifftest_skip_dut(int nr_ref, int nr_dut): после вызова сразу дадут REF выполнить пошаговоnr_refраз, затем ожидают, что NEMU догонит состояние REF заnr_dutинструкций, и проверки всех инструкций на этом промежутке пропускаются.
Инструкции, которые нужно калибровать
В PA2 калибровать нужно:
- x86: нет
- riscv32: нет
- mips32: различные инструкции перехода
- потому что в
mips32-NEMUне реализован слот задержки перехода; можно калибровать черезdifftest_skip_dut(2, 1)
- потому что в
Невероятное поведение QEMU (чуть сложнее)
В некоторых старых версиях mips32-QEMU инструкции упаковываются, только если младшие 12 бит PC указанной выше инструкции равны 0xffc. Условие упаковки выглядит очень странно; знаете ли вы, в чём может быть причина?
Spike не поддерживает невыровненные обращения к памяти
RISC-V как RISC-архитектура обычно не поддерживает невыровненный доступ: выполнение в Spike инструкции обращения с невыровненным адресом выбросит исключение, PC перейдёт в 0. NEMU для упрощения такой функции не реализовал, поэтому если NEMU и Spike одновременно выполнят такую инструкцию, DiffTest сообщит об ошибке. Впрочем, это скорее всего проблема вашей программной реализации (например klib); проверьте и поправьте связанный код.
Когда REF — QEMU, не запускайте два экземпляра NEMU одновременно
DiffTest подключается к QEMU через фиксированный порт; если одновременно запущены два NEMU с включённым DiffTest, появится сообщение:
Failed to find an available port: Address already in use
Если вы уверены, что два NEMU не запущены, но сообщение всё равно есть, оставшийся в фоне QEMU можно убить командой
pkill -9 qemu
Регрессионное тестирование в один клик
Пока реализуете инструкции, тестовые случаи нужно гонять по одному. Но когда инструкции реализованы верно, значит ли это, что с тестовыми случаями можно попрощаться? Очевидно нет. Позже в NEMU вы будете добавлять новые функции; чтобы новые не затронули уже реализованные, эти тестовые случаи нужно запускать снова. В тестировании ПО этот процесс называют регрессионным тестированием.
Раз эти тестовые случаи придётся запускать снова, гонять каждый вручную будет неэффективно. Чтобы повысить эффективность, для cpu-tests есть команда регрессионного тестирования в один клик:
make ARCH=$ISA-nemu run
Этой командой автоматически пакетно запустите все тесты в cpu-tests и получите отчёт по каждому тестовому случаю.
Суть NEMU
Вы уже знаете: NEMU — программа, которая выполняет другие программы. В теории вычислимости у такой программы есть особое имя — универсальная программа (Universal Program); в обыденном смысле: то, что умеют другие программы, умеет и она. Существование универсальных программ доказано специально, здесь в это не углубляемся; но то, что мы можем написать NEMU, ставить опыты в Docker/виртуальных машинах и вообще делать на компьютере самые разные вещи, за всем этим — идея универсальной программы: NEMU и разные эмуляторы — лишь конкретизации универсальной программы, и без преувеличения можно сказать: компьютер — воплощение универсальной программы. Существование универсальной программы заложило теоретический фундамент появления компьютера, это крайне важный вывод теории вычислимости; если существование универсальной программы не доказано, компьютером нельзя пользоваться спокойно и нельзя с полным правом сказать «машина всегда права».
Написанный нами NEMU в итоге скомпилируется в машинный код x86 и инструкциями x86 будет симулировать выполнение гостевых инструкций. На самом деле ещё в 1983 профессор Martin Davis в книге "Computability, complexity, and languages: fundamentals of theoretical computer science" предложил язык программирования L всего с тремя инструкциями и доказал, что вычислительная сила языка L эквивалентна всем остальным языкам программирования. Три инструкции языка L:
V = V + 1
V = V - 1
IF V != 0 GOTO LABEL
В терминах инструкций x86 это inc, dec и jne.
Ещё удивительнее: профессор Martin Davis доказал, что без учёта физических ограничений (считаем память бесконечной, и каждая ячейка может хранить сколь угодно большое число) на языке L тоже можно написать универсальную программу, похожую на NEMU! И каркас этой универсальной программы на L на удивление такой же, как функция cpu_exec() в NEMU: выборка, декодирование, выполнение... Это не совпадение, а применение симуляции (Simulation) в информатике.
Задолго до того, как профессор Martin Davis предложил язык L, учёные уже искали, какие задачи вычислимы. Если вернуться в 1830-е, пытаясь ответить на этот вопрос, разные учёные предлагали и исследовали разные модели вычислений, включая рекурсивные функции, которые изучали Gödel, Herbrand и Kleen, λ-исчисление Church, машину Тьюринга Turing; позже оказалось, что по вычислительной силе эти модели эквивалентны; к 1840-м компьютеры уже изготовили. Позже даже доказали: если склеить бесконечно много счётов и считать на них, вычислительная сила эквивалентна машине Тьюринга! Отсюда следствие: универсальная программа в разных моделях вычислений имеет разный облик. NEMU как универсальная программа в 1830-е имел бы необычайный смысл. Если бы вы спроектировали NEMU 90 лет назад, не исключено, что «премия Тьюринга» носила бы ваше имя. Серия научно-популярных статей Пределы вычисления рассказывает историю теории вычислимости; кому интересно — можно почитать и ощутить цивилизацию (некоторая математическая подготовка всё же нужна). Если теория вычислимости интересна, можно взять курс введения в теорию вычислений преподавателя Fangmin Song.
Вернёмся мыслями к PA: свойство универсальной программы говорит, что потенциал NEMU бесконечен. Чтобы сотворить пёстрый мир, чего, по-вашему, NEMU ещё не хватает?
Поймать бесконечный цикл (чуть сложнее)
Кроме эмулятора, у NEMU есть простая отладочная функция: можно ставить точки останова и смотреть состояние программы. Если добавить в NEMU такую возможность:
Когда гостевая программа попала в бесконечный цикл, приостановить гостевую программу и вывести соответствующий журнал.
Как, по-вашему, это сделать? Если растерялись — поищите сведения в интернете.
Подсказка
На этом заканчивается этап 2 PA2.