- PVSM.RU - https://www.pvsm.ru -
Для ясности теоретического понимания нет лучшего пути, чем учиться на своих собственных ошибках, на собственном горьком опыте. (Фридрих Энгельс)
Всем привет!
Несколько недель назад мне в линкедине написал коллега и сообщил, что в моем проекте [1] на гитхабе не совсем верно работает хеш-таблица.
Мне прислали тесты и фикс, и действительно создавалась ситуация, где система "зависала". При расследовании проблемы я понял, что допустил несколько ошибок при верификации. На Хабре тема верификации RTL-кода не слишком подробна расписана, поэтому я и решил написать статью.
Из статьи вы узнаете:
Добро пожаловать под кат!
Цели, которые я ставил перед началом проекта:
Я хочу получить максимальную производительность, поэтому организовываю конвейер:
Вход (ht_cmd
):
typedef enum logic [1:0] {
OP_SEARCH,
OP_INSERT,
OP_DELETE
} ht_opcode_t;
typedef struct packed {
logic [KEY_WIDTH-1:0] key;
logic [VALUE_WIDTH-1:0] value;
ht_opcode_t opcode;
} ht_command_t;
Выход (ht_res
):
typedef enum int unsigned {
SEARCH_FOUND,
SEARCH_NOT_SUCCESS_NO_ENTRY,
INSERT_SUCCESS,
INSERT_SUCCESS_SAME_KEY,
INSERT_NOT_SUCCESS_TABLE_IS_FULL,
DELETE_SUCCESS,
DELETE_NOT_SUCCESS_NO_ENTRY
} ht_rescode_t;
typedef struct packed {
ht_command_t cmd;
ht_rescode_t rescode;
logic [BUCKET_WIDTH-1:0] bucket;
// valid only for opcode = OP_SEARCH
logic [VALUE_WIDTH-1:0] found_value;
} ht_result_t;
Примечание:
На самом деле в ht_result_t
нас волнует только rescode
и found_value
, но чуть забегая вперед — без других полей было бы сложнее верифицировать. Всё равно, если в железе они не будут использоваться, то синтезатор их вырежет и ресурсы они не займут.
Что и где расположено:
key
, value
) хранятся в памяти data_table
.next_ptr
, next_ptr_val
).head_table
.empty_ptr_storage
хранит номера пустых строчек в data_table
.
Слово в head_table
:
typedef struct packed {
logic [HEAD_PTR_WIDTH-1:0] ptr;
logic ptr_val;
} head_ram_data_t;
Слово в data_table
:
typedef struct packed {
logic [KEY_WIDTH-1:0] key;
logic [VALUE_WIDTH-1:0] value;
logic [HEAD_PTR_WIDTH-1:0] next_ptr;
logic next_ptr_val;
} ram_data_t;
Алгоритм работы:
calc_hash
использует key
для расчета хеша (его значение и будет номером корзины (bucket_num
)).bucket_num
как адрес для head_table
: получаем указатель на начало связанного списка для корзины.data_table_search
, data_table_insert
, data_table_delete
) (ориентируясь на opcode
).task
) на исполнение (найти, вставить, удалить) и читают/пишут из data_table
(бегают по связанному списку). Формируют результат ht_res
.Интересные нюансы:
data_table
имеет задержку на чтение в два такта, поэтому для того, чтобы каждый такт производить поиск, сделаны несколько (пять) параллельных модулей, задания между которыми распределяются round-robin'ом.empty_ptr_storage
. На момент написания статьи он реализован очень нерационально: вектором empty_ptr_mask
(его длина — количество ячеек таблицы data_table
), который хранится на регистрах. А поиск пустого элемента происходит "перебором" за ноль тактов (на комбинационке). С точки зрения ресурсов и частоты — это не самое лучшее решение.
Выглядит это так (кликните для увеличения):
[2]
Перед тем, как начать делать хеш-таблицу, я понимал, что проект непростой, поэтому заранее предусмотрел некоторые вещи, которые ускорили разработку и упростили отладку.
В качестве HDL-языка использовался SystemVerilog и корпоративный кодинг стайл.
Он позволяет удобно описывать структуры (см. выше) и создавать свои типы данных, например для описания FSM:
enum int unsigned {
IDLE_S,
NO_VALID_HEAD_PTR_S,
READ_HEAD_S,
GO_ON_CHAIN_S,
KEY_MATCH_S,
ON_TAIL_WITHOUT_MATCH_S
} state, next_state;
При разработке конвейера нужно хорошо понимать когда он будет останавливаться [3].
Можно напридумывать много чего, но лучше всего использовать уже готовые, разработанные интерфейсы.
На работе я пишу под FPGA компании Altera, поэтому я лучше знаком с интерфейсами, которые они предлагают/продвигают. В этом проекте я использовал семейство Avalon [4].
Команды это просто поток данных (одно слово — одна команда), поэтому я использовал стандарт Avalon-Streaming (Avalon-ST)
(сигналы data
, ready
, valid
).
Вот так выглядит транзакция на Avalon-ST
при readyLatency = 0
(взято из стандарта):
На этой картинке видно, что сигнал ready, которым управляет слейв, затыкает транзакцию и передачу данных.
Когда я прикидывал как я буду делать эту хеш-таблицу, я понимал, что самое сложное будет в её верификации. Очевидно, что самые интересные нюансы проявляются тогда, когда ты пытаешься добавить в цепочку, где уже есть данные, либо удаляешь из длинной цепочки и так далее.
Это значит, что когда подается воздействие на систему, то нужно иметь возможность по заранее заданному номеру корзины легко генерировать ключ (key
).
С настоящими хеш-функциями это проблематично, поэтому предусмотрено значение параметра HASH_TYPE
равное "dummy hash"
.
Если выбран этот тип хэша, то номер корзины — это просто старшие BUCKET_WIDTH
бит от ключа.
Следовательно, когда key = 0x92123456
, а BUCKET_WIDTH
равен 8, то bucket_num = 0x92
.
Это позволит легко составить необходимое воздейстие для генерации тех или иных граничных случаев.
Иногда разработчики отлаживают свои RTL-модули прямо на железе (читай, платах) с использованием SignalTap [5] или ChipScope [6]. Такой подход не всегда самый быстрый и продуктивный — требуется пересборка всего проекта (от 10 минут до нескольких часов) (а иногда не один раз), плата под рукой, отладчик, генерация входных воздействий и т.д.
Для ускорения разработки используются специальные симуляторы [7], такие как ModelSim [8], VCS, Icarus Verilog и др. Они позволяют отслеживать значения всех (либо выбранных) сигналов/переменных во время отладки путем построения временных диаграмм (времянок). На просмотр этих диаграмм может уходить огромное количество времени при дебаге.
Решение:
Логировать все действия, что происходят, для быстрого просмотра глазами.
Для этого в data_table_insert
, data_table_delete
, data_table_search
я добавил функции, которые печатают в лог:
function void print( string s );
$display("%08t: %m: %s", $time, s);
endfunction
Формат display
похож на printf
(можно %d
, %f
и пр. использовать):
%08t
— выведет время симуляции (будет удобно потом прыгнуть в нужный момент времени).%m
— напечатает модуль (иерархическое имя), где это произошло. (Внимание: это не требует аргументов!) %s
— печать строчкиЛогируем переходы FSM:
function void print_state_transition( );
string msg;
if( next_state != state )
begin
$sformat( msg, "%s -> %s", state, next_state );
print( msg );
end
endfunction
Печатаем прием нового задания:
function string pdata2str( input ht_pdata_t pdata );
string s;
$sformat( s, "opcode = %s key = 0x%x value = 0x%x head_ptr = 0x%x head_ptr_val = 0x%x",
pdata.cmd.opcode, pdata.cmd.key, pdata.cmd.value, pdata.head_ptr, pdata.head_ptr_val );
return s;
endfunction
function void print_new_task( ht_pdata_t pdata );
print( pdata2str( pdata ) );
endfunction
И так далее...
Для симуляции я использую ModelSim. В его логе, который отображается на экране (и по умолчанию попадет в файл transcript
) возникают такие строчки:
1465: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: opcode = OP_SEARCH key = 0x04000000 value = 0x0000 head_ptr = 0x000 head_ptr_val = 0x0
1465: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: IDLE_S -> NO_VALID_HEAD_PTR_S
1475: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: RES: key = 0x04000000 value = 0x0000 rescode = SEARCH_NOT_SUCCESS_NO_ENTRY
1475: top_tb.dut.d_tbl.sea_eng.g_s_eng[3].search.print: NO_VALID_HEAD_PTR_S -> IDLE_S
1475: ht_tb.print: IN_MONITOR: key = 0x04000000 value = 0x0000 rescode = SEARCH_NOT_SUCCESS_NO_ENTRY
1485: top_tb.dut.d_tbl.del_eng.print: opcode = OP_DELETE key = 0x04111111 value = 0x0000 head_ptr = 0x000 head_ptr_val = 0x0
1485: top_tb.dut.d_tbl.del_eng.print: IDLE_S -> NO_VALID_HEAD_PTR_S
1495: top_tb.dut.d_tbl.del_eng.print: RES: key = 0x04111111 value = 0x0000 rescode = DELETE_NOT_SUCCESS_NO_ENTRY
1495: top_tb.dut.d_tbl.del_eng.print: NO_VALID_HEAD_PTR_S -> IDLE_S
1495: ht_tb.print: IN_MONITOR: key = 0x04111111 value = 0x0000 rescode = DELETE_NOT_SUCCESS_NO_ENTRY
1505: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x04000000 value = 0xb95f head_ptr = 0x000 head_ptr_val = 0x0
1505: top_tb.dut.d_tbl.ins_eng.print: IDLE_S -> NO_HEAD_PTR_WR_HEAD_PTR_S
1515: top_tb.dut.h_tbl.print: addr = 0x04 wr_data.ptr = 0x003 wr_data.ptr_val = 0x1
1515: top_tb.dut.d_tbl.ins_eng.print: NO_HEAD_PTR_WR_HEAD_PTR_S -> NO_HEAD_PTR_WR_DATA_S
1525: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x003 key = 0x04000000 value = 0xb95f next_ptr = 0x000, next_ptr_val = 0x0
1525: top_tb.dut.d_tbl.ins_eng.print: RES: key = 0x04000000 value = 0xb95f rescode = INSERT_SUCCESS
1525: top_tb.dut.d_tbl.ins_eng.print: NO_HEAD_PTR_WR_DATA_S -> IDLE_S
Такой текстовый лог легко grep'ать, либо побегать поиском (например, в vim'e).
Логи сэкономили огромное количество времени: при подаче простых примеров я знал, что в каком порядке должно писаться и просто смотрел в лог. Если происходила ошибка, то переходил к анализу кода, а не временных диаграмм.
Всем советую в качестве челенджа попробовать в течение недели отлаживать RTL-код без времянок (выйти из зоны комфорта).
Если обратиться к хорошей литературе, например, SystemVerilog for Verification [9], то в качестве хорошего, правильного тестбенча там приводится следующая схема:
В этой статье забирать хлеб у Chris Spear я не собираюсь, поэтому о том что обозначают все эти компоненты подробно рассказывать не буду.
Схема моего тестбенча:
Топовый модуль.
Наш подопытный — экземпляр модуля hash_table_top
.
gen2drv
, который предназначен для команд, которые будут отправлены в DUT
.DUT
.DUT
, она копируется в ht_scoreboard
.Для того, чтобы положить команду в этот mailbox используется иерархический доступ:
task send_to_dut_c( input ht_command_t c );
// using hierarchial access to put command in mailbox
env.drv.gen2drv.put( c );
endtask
Для проверки работоспособности были написаны три теста/входных воздействия.
Макросы для упрощения работы:
`define CMD( _OP, _KEY, _VALUE ) cmds.push_back( '{ opcode : _OP, key : _KEY, value : _VALUE } );
`define CMD_SEARCH( _KEY ) `CMD( OP_SEARCH, _KEY, 0 )
`define CMD_INSERT( _KEY, _VALUE ) `CMD( OP_INSERT, _KEY, _VALUE )
`define CMD_INSERT_RAND( _KEY ) `CMD_INSERT( _KEY, $urandom() )
`define CMD_DELETE( _KEY ) `CMD( OP_DELETE, _KEY, 0 )
Пример теста:
task test_01( );
ht_command_t cmds[$];
$display("%m:");
`CMD_INSERT( 32'h01_00_00_00, 16'h1234 )
`CMD_INSERT( 32'h01_00_10_00, 16'h1235 )
`CMD_INSERT_RAND( 32'h01_00_00_00 )
`CMD_INSERT_RAND( 32'h01_00_00_01 )
`CMD_DELETE ( 32'h01_00_00_00 )
`CMD_INSERT_RAND( 32'h01_00_00_02 )
`CMD_SEARCH( 32'h01_00_00_00 )
`CMD_SEARCH( 32'h01_00_00_01 )
`CMD_SEARCH( 32'h01_00_00_01 )
`CMD_SEARCH( 32'h01_00_00_03 )
foreach( cmds[i] )
begin
send_to_dut_c( cmds[i] );
end
endtask
ht_res
. ht_scoreboard
.Проверяет корректность работы DUT'a.
В себе содержит:
mailbox
, куда кладут команды и результат ht_driver
и ht_monitor
соответственно.ref_hash_table
.Алгоритм работы:
ht_res
, то вынимаются из очереди он и соответствующий ему запрос. Здесь нам на руку то, что на каждую команду будет ответ.check
, которая скармливает команду в референсную модель и сравнивает результаты от DUT'a и референсной модели.$error
будет распечатано об этом сообщение в лог, а в GUI ModelSim'a появится красная стрелочка в том момент времени, когда это произошло.Итак, уже есть система (если хотите, фреймворк), которая позволяет отправлять различные входные воздейстия, а так же анализировать корректность реакции DUT. Для того, чтобы убедиться, что багов нет, необходимо покрыть "все возможные" варианты.
Для оценки покрытия в языке SystemVerilog введены такие объекты как covergroup и coverpoint [10]. С их помощью можно описать те точки, где мы хотим сэмплировать, а так же какую статистику собирать.
covergroup cg();
option.per_instance = 1;
CMDOP: coverpoint result_locked.cmd.opcode;
CMDRES: coverpoint result_locked.rescode;
BUCKOCUP: coverpoint bucket_occup[ result_locked.bucket ] {
bins zero = { 0 };
bins one = { 1 };
bins two = { 2 };
bins three = { 3 };
bins four = { 4 };
bins other = { [5:$] };
}
CMDOP_BUCKOCUP: cross CMDOP, BUCKOCUP;
CMDRES_BUCKOCUP: cross CMDRES, BUCKOCUP {
// we should ignore SEARCH_FOUND, INSERT_SUCCESS_SAME_KEY, DELETE_SUCCESS
// when in bucket was zero elements, because it's not real situation
ignore_bins not_real = binsof( CMDRES ) intersect{ SEARCH_FOUND, INSERT_SUCCESS_SAME_KEY, DELETE_SUCCESS } &&
binsof( BUCKOCUP ) intersect{ 0 };
}
endgroup
Пояснение:
CMDOP
и CMDRES
следят за тем, какие были операции ht_cmd
и результаты ht_res
.bucket_occup
хранит количество элементов, которые были в корзине в момент операции.CMDOP_BUCKOCUP
— "скрещивает" команды с количеством элементов в корзине: получаем события была команда X, а в корзине, к которой относился key
, где было Y элементов.CMDRES_BUCKOCUP
— "скрещивает" результат с количество элементов в корзине.После окончания симуляции в консоли ModelSim'a можно получить отчет:
coverage save 1.ucdb
vcover report 1.ucdb -verbose -cvg
Отчёт:
COVERGROUP COVERAGE:
----------------------------------------------------------------------------------------------------
Covergroup Metric Goal/ Status
At Least
----------------------------------------------------------------------------------------------------
TYPE /top_tb/dut/resm/cg 94.0% 100 Uncovered
Coverpoint cg::CMDOP 100.0% 100 Covered
Coverpoint cg::CMDRES 85.7% 100 Uncovered
Coverpoint cg::BUCKOCUP 100.0% 100 Covered
Cross cg::CMDOP_BUCKOCUP 100.0% 100 Covered
Cross cg::CMDRES_BUCKOCUP 84.6% 100 Uncovered
Covergroup instance /top_tb/dut/resm/cg1 94.0% 100 Uncovered
Coverpoint CMDOP 100.0% 100 Covered
covered/total bins: 3 3
missing/total bins: 0 3
bin auto[OP_SEARCH] 21 1 Covered
bin auto[OP_INSERT] 21 1 Covered
bin auto[OP_DELETE] 18 1 Covered
Coverpoint CMDRES 85.7% 100 Uncovered
covered/total bins: 6 7
missing/total bins: 1 7
bin auto[SEARCH_FOUND] 12 1 Covered
bin auto[SEARCH_NOT_SUCCESS_NO_ENTRY] 9 1 Covered
bin auto[INSERT_SUCCESS] 14 1 Covered
bin auto[INSERT_SUCCESS_SAME_KEY] 7 1 Covered
bin auto[INSERT_NOT_SUCCESS_TABLE_IS_FULL] 0 1 ZERO
bin auto[DELETE_SUCCESS] 11 1 Covered
bin auto[DELETE_NOT_SUCCESS_NO_ENTRY] 7 1 Covered
Coverpoint BUCKOCUP 100.0% 100 Covered
covered/total bins: 6 6
missing/total bins: 0 6
bin zero 7 1 Covered
bin one 13 1 Covered
bin two 9 1 Covered
bin three 12 1 Covered
bin four 8 1 Covered
bin other 11 1 Covered
Cross CMDOP_BUCKOCUP 100.0% 100 Covered
covered/total bins: 18 18
missing/total bins: 0 18
bin <auto[OP_SEARCH],zero> 1 1 Covered
bin <auto[OP_INSERT],zero> 5 1 Covered
bin <auto[OP_SEARCH],one> 5 1 Covered
...
Cross CMDRES_BUCKOCUP 84.6% 100 Uncovered
covered/total bins: 33 39
missing/total bins: 6 39
bin <auto[SEARCH_NOT_SUCCESS_NO_ENTRY],zero>
1 1 Covered
bin <auto[INSERT_SUCCESS],zero> 5 1 Covered
bin <auto[DELETE_NOT_SUCCESS_NO_ENTRY],zero>
1 1 Covered
...
Все возможные перекрещивания получены автоматически — ничего дополнительного мы не писали.
После трех тестов видно, что:
OP_INSERT
было 21, а на удаление 18INSERT_NOT_SUCCESS_TABLE_IS_FULL
Оказалось, если подать такое воздействие:
`CMD_INSERT_RAND( 32'h05_00_00_00 )
`CMD_INSERT_RAND( 32'h05_00_00_01 )
`CMD_DELETE ( 32'h05_00_00_01 )
`CMD_INSERT_RAND( 32'h05_00_00_02 )
`CMD_INSERT_RAND( 32'h05_00_00_03 )
то это приведёт к тому, что при вставке ключа 0x05000003
модуль data_table_insert
"зависал":
state
висит в GO_ON_CHAIN_S
(и из него больше никогда не выйдет)
[11]
(кликните для увеличения)
В логе возникли сообщения:
385: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000003 value = 0x7e7e head_ptr = 0x000 head_ptr_val = 0x1
385: top_tb.dut.d_tbl.ins_eng.print: IDLE_S -> READ_HEAD_S
415: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1
415: top_tb.dut.d_tbl.ins_eng.print: READ_HEAD_S -> GO_ON_CHAIN_S
445: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
475: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
505: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
535: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
...
Отмотаем немного лог и проанализируем его. Я привёл только те строчки, которые нам интересны (что читалось и писалось в таблицу data_table
):
75: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000000 value = 0x1f62 head_ptr = 0x000 head_ptr_val = 0x0
95: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x000, next_ptr_val = 0x0
115: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000001 value = 0x3ff2 head_ptr = 0x000 head_ptr_val = 0x1
145: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x000, next_ptr_val = 0x0
155: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x001 key = 0x05000001 value = 0x3ff2 next_ptr = 0x000, next_ptr_val = 0x0
165: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1
185: top_tb.dut.d_tbl.del_eng.print: opcode = OP_DELETE key = 0x05000001 value = 0x0000 head_ptr = 0x000 head_ptr_val = 0x1
215: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1
245: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x001 key = 0x05000001 value = 0x3ff2 next_ptr = 0x000, next_ptr_val = 0x0
255: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x001 key = 0x05000001 value = 0x3ff2 next_ptr = 0x000, next_ptr_val = 0x0
265: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x000, next_ptr_val = 0x0
285: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000002 value = 0x5429 head_ptr = 0x000 head_ptr_val = 0x1
315: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1
345: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x000, next_ptr_val = 0x0
355: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x001 key = 0x05000002 value = 0x5429 next_ptr = 0x000, next_ptr_val = 0x0
365: top_tb.dut.d_tbl.ins_eng.print: WR: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
385: top_tb.dut.d_tbl.ins_eng.print: opcode = OP_INSERT key = 0x05000003 value = 0x7e7e head_ptr = 0x000 head_ptr_val = 0x1
415: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x000 key = 0x05000000 value = 0x1f62 next_ptr = 0x001, next_ptr_val = 0x1
445: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
475: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
505: top_tb.dut.d_tbl.ins_eng.print: RD: addr = 0x001 key = 0x00000000 value = 0x0000 next_ptr = 0x001, next_ptr_val = 0x1
Можно заметить, что в момент времени 255-265 нс произошли странные события: сначала в addr = 0x001
записали одно значение, а затем другое.
Это приводит к тому, что таблица data_table
содержит некорректные данные:
next_ptr = 0x001
, next_ptr_val = 0x1
)dummy hash
.При добавлении ключа 0x05000002 происходит интересная ситуация: снова происходит запись два раза в одну ячейку 0x001.
empty_ptr_storage
выдал, что 0x001 пустует (нам повезло, что сейчас алгоритм работы этого модуля такой, что он отдает самый маленький адрес, который считается пустым)При попытке добавления ключа 0x05000003 происходит зацикливание при проходе по цепочке. Начиная с 445 нс мы будем бесконечно бегать по цепочке и читать один и тот же адрес.
Очевидно, что ошибку вносит модуль, который удалял данные (data_table_delete
).
В момент 255 нс он должен был в ячейке 0x000 флаг next_ptr_val
сделать равным нулю, а в момент 265 нс записать в 0x001 записать все нули. Так предполагалось по коду этого модуля, но этого, как видим, не произошло.
Дело в том, что надо было отдельно сохранить rd_addr
и rd_data
, которые мы прочитали с конца цепочки, а так мы использовали значения, с которыми только что работали.
Такие ошибки (лишняя задержка на один такт, перезаписанные данные не вовремя и пр.) весьма типичны в RTL-коде. Интереса они особого не представляют, поэтому я это не особо расписываю в статье.
Дело в том, что я не довёл проект до логического конца, который я себе представлял. Почему — сейчас уже не вспомню.
Например, в README
в проекта не указано того, где и как использовался/тестировался этот модуль.
Сравните две фразы:
Если бы я явно указал, что этот модуль я написал просто так на выходных и никуда его не встраивал, то, возможно, сторонние разработчики не использовали мой модуль и съэкономили бы себе время (правда, тогда бы я не узнал, что у меня есть бага, а вы бы не прочитали эту статью).
Когда я начал разбираться где проблема в коде, я расстроился, когда увидел, что проблема есть с переменной prev_rd_addr
. Блок, где присваивают её значение, выглядит вот так:
always_ff @( posedge clk_i or posedge rst_i )
if( rst_i )
prev_rd_addr <= '0;
else
if( rd_en_o ) //FIXME
prev_rd_addr <= rd_addr;
FIXME
без пояснения — это плохо. Лишние пять минут описания проблемы всегда окупятся в будущем.
*Выводы:
KNOWN_PROBLEMS
/KNOWN_BUGS
Легко заметить, что те точки, на которое смотрит покрытие, не дает полной картины:
Исправляем:
Вводим тип ht_chain_state_t
, который будет показывать, где мы остановились при операции:
typedef enum int unsigned {
NO_CHAIN,
IN_HEAD,
IN_MIDDLE,
IN_TAIL,
IN_TAIL_NO_MATCH
} ht_chain_state_t;
// добавляем его в ht_result_t
...
// only for verification
ht_chain_state_t chain_state;
} ht_result_t;
В соотстветвующих модулях добавляем анализ. Для data_table_delete
это выглядит так:
ht_chain_state_t chain_state;
always_ff @( posedge clk_i or posedge rst_i )
if( rst_i )
chain_state <= NO_CHAIN;
else
if( state != next_state )
begin
case( next_state )
NO_VALID_HEAD_PTR_S : chain_state <= NO_CHAIN;
IN_TAIL_WITHOUT_MATCH_S : chain_state <= IN_TAIL_NO_MATCH;
KEY_MATCH_IN_HEAD_S : chain_state <= IN_HEAD;
KEY_MATCH_IN_MIDDLE_S : chain_state <= IN_MIDDLE;
KEY_MATCH_IN_TAIL_S : chain_state <= IN_TAIL;
// no default: just keep old value
endcase
end
// кладем в результат, чтобы проанализировать в ```ht_res_monitor```
assign result_o.chain_state = chain_state;
Изменения в ht_res_monitor
:
// история результатов
ht_result_t result_history [HISTORY_DELAY:1];
always_ff @( posedge clk_i )
begin
if( result_locked_val )
begin
result_history[1] <= result_locked;
for( int i = 2; i <= HISTORY_DELAY; i++ )
begin
result_history[i] <= result_history[i-1];
end
end
end
// 1 в маске обозначает, что корзины (bucket) совпали в истории
logic [HISTORY_DELAY:1] bucket_hist_mask;
always_comb
begin
for( int i = 1; i <= HISTORY_DELAY; i++ )
bucket_hist_mask[i] = ( result_history[i].bucket == result_locked.bucket );
end
Добавляем в covergroup:
...
CMDOP_D1: coverpoint result_history[1].cmd.opcode;
CMDOP_D2: coverpoint result_history[2].cmd.opcode;
CMDRES_D1: coverpoint result_history[1].rescode;
CMDRES_D2: coverpoint result_history[2].rescode;
CHAIN: coverpoint result_locked.chain_state;
BUCK_HIST_MASK: coverpoint bucket_hist_mask;
CMDOP_HISTORY_D2: cross CMDOP_D2, CMDOP_D1, CMDOP, BUCK_HIST_MASK;
CMDRES_HISTORY_D2: cross CMDRES_D2, CMDRES_D1, CMDRES, BUCK_HIST_MASK {
ignore_bins not_check_now = binsof( CMDRES ) intersect{ INSERT_NOT_SUCCESS_TABLE_IS_FULL } ||
binsof( CMDRES_D1 ) intersect{ INSERT_NOT_SUCCESS_TABLE_IS_FULL } ||
binsof( CMDRES_D2 ) intersect{ INSERT_NOT_SUCCESS_TABLE_IS_FULL };
}
CMDOP_CHAIN: cross CMDOP, CHAIN {
ignore_bins insert_in_middle = binsof( CMDOP ) intersect { OP_INSERT } &&
binsof( CHAIN ) intersect { IN_MIDDLE };
ignore_bins insert_in_tail_no_match = binsof( CMDOP ) intersect { OP_INSERT } &&
binsof( CHAIN ) intersect { IN_TAIL_NO_MATCH };
}
Для того, чтобы стало ясно что будет анализироваться приведу пример bin для CMDOP_HISTORY_D2
:
bin <auto[OP_DELETE],auto[OP_SEARCH],auto[OP_SEARCH],auto['b10]>
Произойдет попадание, если:
OP_SEARCH
,OP_SEARCH
в корзину, отличную от текущейOP_DELETE
в корзину, которая совпадает с текущейДо всех фиксов у меня были написаны руками три простых теста. Запустим их:
Coverpoint cg::CMDOP 100.0% 100 Covered
Coverpoint cg::CMDRES 85.7% 100 Uncovered
Coverpoint cg::CMDOP_D1 100.0% 100 Covered
Coverpoint cg::CMDOP_D2 100.0% 100 Covered
Coverpoint cg::CMDRES_D1 85.7% 100 Uncovered
Coverpoint cg::CMDRES_D2 85.7% 100 Uncovered
Coverpoint cg::CHAIN 100.0% 100 Covered
Coverpoint cg::BUCK_HIST_MASK 100.0% 100 Covered
Coverpoint cg::BUCKOCUP 100.0% 100 Covered
Cross cg::CMDOP_BUCKOCUP 100.0% 100 Covered
Cross cg::CMDRES_BUCKOCUP 84.6% 100 Uncovered
Cross cg::CMDOP_HISTORY_D2 18.5% 100 Uncovered
covered/total bins: 20 108
missing/total bins: 88 108
Cross cg::CMDRES_HISTORY_D2 3.1% 100 Uncovered
covered/total bins: 27 864
missing/total bins: 837 864
Cross cg::CMDOP_CHAIN 84.6% 100 Uncovered
(остальной лог я убрал, т.к. он очень большой)
Как видим, у точек с HISTORY
отвратительное покрытие (18.5% и 3.1%). Три теста, написанные руками, не смогли дать нужного разнообразия.
Почему я анализирую только три последних результата, включая текущее?
Это число взято наугад. Разумеется, чем больше, тем лучше, но и чем больше получается вариантов, тем больше тестов нужно будет для 100% покрытия.
Где здесь грань и какое самое оптимальное число для анализа — я не знаю. Наверно, это значение должно равнятся задержке модуля в количестве команд в худшем случае (порядка 5 или 6 специально это число я не считал).
Выводы:
При верификации сложных и больших систем необходимо убедится, что покрываются или почти все варианты.
Вручную сложно сделать все варианты. Выход — рандомизированное тестирование. Но просто генерировать случайные данные на входе, не самая лучшая идея: есть методика Constrained Random Verification [13].
Да, мы подаем случайные значения, но они чем-то ограничены, либо подчиняются какому-то простому (или не очень) закону, для воспроизведения того, что вам надо.
Сделаем функцию, которая дает нам случайный ключ в нужном диапазоне корзин и значения ключей:
function bit [KEY_WIDTH-1:0] gen_rand_key( int min_bucket_num = 0,
int max_bucket_num = ( 2**BUCKET_WIDTH - 1 ),
int max_key_value = ( 2**( KEY_WIDTH - BUCKET_WIDTH ) - 1 ) );
bit [BUCKET_WIDTH-1:0] bucket_num;
bit [KEY_WIDTH-1:0] gen_key;
if( hash_table::HASH_TYPE != "dummy" )
begin
$display("%m: hash_type = %s not supported here!", hash_table::HASH_TYPE );
$fatal();
end
bucket_num = $urandom_range( max_bucket_num, min_bucket_num );
gen_key = $urandom_range( max_key_value, 0 );
// replace high bits by bucket_num (is needs in dummy hash)
gen_key[ KEY_WIDTH - 1 : KEY_WIDTH - BUCKET_WIDTH ] = bucket_num;
return gen_key;
endfunction
Теперь сгенерируем случайные транзакции для корзин [0;15]
и значений ключей [0;7]
.
// testing small amount of buckets with random commands
task test_05( );
ht_command_t cmds[$];
$display("%m:");
for( int c = 0; c < 5000; c++ )
begin
`CMD_SEARCH ( gen_rand_key( 0, 15, 7 ) )
`CMD_INSERT_RAND ( gen_rand_key( 0, 15, 7 ) )
`CMD_DELETE ( gen_rand_key( 0, 15, 7 ) )
end
// взболтать, но не смешивать :)
cmds.shuffle( );
foreach( cmds[i] )
begin
send_to_dut_c( cmds[i] );
end
endtask
Как видим даже это не даёт полного покрытия:
Cross cg::CMDOP_HISTORY_D2 98.1% 100 Uncovered
covered/total bins: 106 108
missing/total bins: 2 108
Cross cg::CMDRES_HISTORY_D2 81.1% 100 Uncovered
covered/total bins: 701 864
missing/total bins: 163 864
Если посмотреть, какие bin'ы не покрылись, то станет ясно, что нужен отдельный тест на одну корзину:
// testing only one bucket with random commands
task test_06( );
ht_command_t cmds[$];
$display("%m:");
for( int c = 0; c < 1000; c++ )
begin
`CMD_SEARCH ( gen_rand_key( 0, 0, 7 ) )
`CMD_INSERT_RAND( gen_rand_key( 0, 0, 7 ) )
`CMD_DELETE ( gen_rand_key( 0, 0, 7 ) )
end
cmds.shuffle( );
foreach( cmds[i] )
begin
send_to_dut_c( cmds[i] );
end
endtask
Результат:
Cross cg::CMDOP_HISTORY_D2 100.0% 100 Covered
covered/total bins: 108 108
missing/total bins: 0 108
Cross cg::CMDRES_HISTORY_D2 99.1% 100 Uncovered
covered/total bins: 857 864
missing/total bins: 7 864
Дополнительно добавил тест, который вставляет огромное количество данных (для того, чтобы создать rescode=INSERT_NOT_SUCCESS_TABLE_IS_FULL
)
Примечание:
Выводы:
Нюанс этого проекта был в том, что если причина ошибки от следствии может быть отделено огромным симуляционным временем.
При возникновении ошибки (а её детектирование происходит по выходу ht_res
), придется "отматывать" время симуляции, логи и т. д. При больших и сложных системах это может быть трудоёмким процессом.
Наша задача как разработчиков (и верификаторов) — найти ошибку как можно ближе по времени и месту (модулю) в котором она расположена.
В этом проекте есть несколько хранилищ:
head_table
data_table
empty_ptr_storage
Эта бага приводила к тому, что в какой-то из моментов времени данные в таблице становились некорректными.
Если мы сразу же (с точки зрения симуляции) это выясним, то багу будет проще исправить/дебажить.
Выведем правила, которым должны подчиняться данные в таблицах:
head_table
:
ptr_val
ptr_val
не может указывать на ячейку, которая помечена как empty
data_table
:
key
должно принадлежать этой цепочке/корзинеnext_ptr_val
не должен указывать на ячейку, которая помечена как пустаяhead_table
, ни от какой-либо цепочки)
empty_ptr_storage
:
data_table_*
не должны просить очистить ячейку, если она уже пустаяКомментарий к любому моменту времени:
Был написан tables_monitor
, который в себе содержит референсные модели head_table
, data_table
, empty_ptr
.
Так же там написана функция, которая обходит таблицы и проверяет на те условия, которые мы описали ранее. Файл полностью можно глянуть тут [15].
Откатим фикс для воспроизведения баги и посмотрим лог:
...
1195: top_tb.dut.d_tbl.del_eng.print: opcode = OP_DELETE key = 0x01000000 value = 0x0000 head_ptr = 0x001 head_ptr_val = 0x1
1195: top_tb.dut.d_tbl.del_eng.print: IDLE_S -> READ_HEAD_S
1225: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x001 key = 0x01001000 value = 0x1235 next_ptr = 0x002 next_ptr_val = 0x1
1225: top_tb.dut.d_tbl.del_eng.print: READ_HEAD_S -> GO_ON_CHAIN_S
1255: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x002 key = 0x01000001 value = 0x3ff2 next_ptr = 0x000 next_ptr_val = 0x1
1285: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x000 key = 0x01000002 value = 0x5429 next_ptr = 0x004 next_ptr_val = 0x1
1315: top_tb.dut.d_tbl.del_eng.print: RD: addr = 0x004 key = 0x01000000 value = 0x1cc0 next_ptr = 0x000 next_ptr_val = 0x0
1315: top_tb.dut.d_tbl.del_eng.print: GO_ON_CHAIN_S -> KEY_MATCH_IN_TAIL_S
1325: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x004 key = 0x01000000 value = 0x1cc0 next_ptr = 0x000 next_ptr_val = 0x0
1325: top_tb.dut.d_tbl.del_eng.print: KEY_MATCH_IN_TAIL_S -> CLEAR_RAM_AND_PTR_S
1335: top_tb.dut.d_tbl.del_eng.print: WR: addr = 0x004 key = 0x00000000 value = 0x0000 next_ptr = 0x000 next_ptr_val = 0x0
1335: top_tb.dut.d_tbl.del_eng.print: RES: key = 0x01000000 value = 0x0000 rescode = DELETE_SUCCESS chain_state = IN_TAIL
1335: top_tb.dut.d_tbl.del_eng.print: CLEAR_RAM_AND_PTR_S -> IDLE_S
1335: ht_tb.print: IN_MONITOR: key = 0x01000000 value = 0x0000 rescode = DELETE_SUCCESS chain_state = IN_TAIL
1335: top_tb.dut.d_tbl.empty_ptr_storage.print: add_empty_ptr: 0x004
** Error: ERROR: addr = 0x004. This addr is empty, but ptr is val
Time: 1340 ns Scope: top_tb.tm.check_one_addr File: ../tb/tables_monitor.sv Line: 119
** Error: ERROR: addr = 0x004 key=0x00000000 don't match bucket_num = 0x01
Time: 1340 ns Scope: top_tb.tm.check_one_addr File: ../tb/tables_monitor.sv Line: 127
Оказалось, что ошибка детектируется уже на тех трех ручных тестах (без участия рандомизированных)!
Обход ячеек показал:
key = 0x00000000
, который не может принадлежать корзине 0x01 (т.к. используется dummy hash).Выводы:
Дураки говорят, что они учатся на собственном опыте, я предпочитаю учиться на опыте других. (Отто фон Бисмарк)
В этой статье я рассказал из чего может состоять простой тестбенч для верификации простых IP-ядер для ASIC/FPGA в разрезе проекта хеш-таблицы.
Исходники:
Главной своей ошибкой я считаю то, что не доделал до конца проект в своё время. План по верификации у меня был [20], и там были отмечены часть идей, которые мы и реализовали в этой статье.
Надеюсь, статья была интересна начинающим RTL-разработчикам, которые хотят улучшить свои тестбенчи.
Делитесь в комментариях, какой болезненный опыт был у вас при верификации RTL-кода :)
Спасибо за внимание! Буду рад вопросам и замечаниям в комментариях или в личной почте.
P.S.:
Это мой первый пост на Хабре в маркдауне на Хабре.
Подскажите, пожалуйста:
systemverilog
? GitHub Flavored Markdown вроде как должен знать это...spoiler
приводит к тому, что весь дальнейший текст не распознается как markdown?Автор: НТЦ Метротек
Источник [21]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/113372
Ссылки в тексте:
[1] проекте: https://github.com/johan92/fpga-hash-table
[2] Image: https://habrastorage.org/files/d08/eae/6d1/d08eae6d1671420cb6867a7ac00a996a.png
[3] останавливаться: https://habrahabr.ru/company/metrotek/blog/235037/
[4] Avalon: https://www.altera.com/content/dam/altera-www/global/en_US/pdfs/literature/manual/mnl_avalon_spec.pdf
[5] SignalTap: https://marsohod.org/11-blog/213-signaltap
[6] ChipScope: http://www.xilinx.com/products/design-tools/chipscopepro.html
[7] симуляторы: https://en.wikipedia.org/wiki/List_of_HDL_simulators
[8] ModelSim: https://www.mentor.com/products/fv/modelsim/
[9] SystemVerilog for Verification: http://www.amazon.com/SystemVerilog-Verification-Learning-Testbench-Language/dp/1461407141
[10] covergroup и coverpoint: http://www.testbench.in/CO_00_INDEX.html
[11] Image: https://habrastorage.org/files/026/798/6d3/0267986d381f4dd8b0294c40be007eb7.png
[12] 100G коммутаторе: http://metrotek.spb.ru/b100.html
[13] Constrained Random Verification: http://www.testbench.in/CR_01_CONSTRAINED_RANDOM_VERIFICATION.html
[14] constraint блок: http://www.testbench.in/CR_08_CONSTRAINT_BLOCK.html
[15] тут: https://github.com/johan92/fpga-hash-table/blob/master/tb/tables_monitor.sv
[16] assertion: http://www.asic-world.com/systemverilog/assertions2.html
[17] проект до фикса баги: https://github.com/johan92/fpga-hash-table/tree/2b502a8b5228392c4db05c3b571c8b25f5f9cfca
[18] проект после фикса баги: https://github.com/johan92/fpga-hash-table/tree/4c2c6196c075d923bc3a1a1c3ef38d005a7631cd
[19] проект на момент статьи: https://github.com/johan92/fpga-hash-table/tree/dc74c7ff2f247d7b2067e977f75148b2130ab7e0
[20] был: https://github.com/johan92/fpga-hash-table/blob/2b502a8b5228392c4db05c3b571c8b25f5f9cfca/tb/verification_testplan.ru
[21] Источник: https://habrahabr.ru/post/277313/
Нажмите здесь для печати.