Для ясности теоретического понимания нет лучшего пути, чем учиться на своих собственных ошибках, на собственном горьком опыте. (Фридрих Энгельс)

Всем привет!

Несколько недель назад мне в линкедине написал коллега и сообщил, что в моем проекте на гитхабе не совсем верно работает хеш-таблица.

Мне прислали тесты и фикс, и действительно создавалась ситуация, где система "зависала". При расследовании проблемы я понял, что допустил несколько ошибок при верификации. На Хабре тема верификации RTL-кода не слишком подробна расписана, поэтому я и решил написать статью.

Из статьи вы узнаете:

• как можно организовать хеш-таблицу на FPGA.
• на чём была построена верификация.
• какие ошибки я допустил (они привели к тому, что бага не была замечена раньше).
• как это всё можно исправить.

Добро пожаловать под кат!

Кратко о проекте

Цели и предпосылки

Цели, которые я ставил перед началом проекта:

• если заявляется, что хеш-таблица на N элементов, то гарантированно поместится там любых N элементов.
• таблица сама разрешает коллизии, ограничения на количество элементов в корзине нет (но не больше размера хеш-таблицы, разумеется).
• таблица позволяет производить операции добавления, поиска и удаления по ключу
• если при поиске не возникает коллизий, то таблица готова принимать задания для поиска каждый такт (максимальная производительность).
• по поводу ресурсов и тактовой частоты я не беспокоюсь.

Внутренее устройство

Я хочу получить максимальную производительность, поэтому организовываю конвейер:


Вход (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), который хранится на регистрах. А поиск пустого элемента происходит "перебором" за ноль тактов (на комбинационке). С точки зрения ресурсов и частоты — это не самое лучшее решение.

Выглядит это так (кликните для увеличения):

Что я сделал для того, чтобы избежать ошибок/упростить отладку

Перед тем, как начать делать хеш-таблицу, я понимал, что проект непростой, поэтому заранее предусмотрел некоторые вещи, которые ускорили разработку и упростили отладку.

SystemVerilog & Coding Style

В качестве 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;

Потоковый интерфейс (Avalon-ST)

При разработке конвейера нужно хорошо понимать когда он будет останавливаться.
Можно напридумывать много чего, но лучше всего использовать уже готовые, разработанные интерфейсы.

На работе я пишу под FPGA компании Altera, поэтому я лучше знаком с интерфейсами, которые они предлагают/продвигают. В этом проекте я использовал семейство Avalon.

Команды это просто поток данных (одно слово — одна команда), поэтому я использовал стандарт Avalon-Streaming (Avalon-ST) (сигналы data, ready, valid).

Вот так выглядит транзакция на Avalon-ST при readyLatency = 0 (взято из стандарта):


На этой картинке видно, что сигнал ready, которым управляет слейв, затыкает транзакцию и передачу данных.

Dummy hash

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

Это значит, что когда подается воздействие на систему, то нужно иметь возможность по заранее заданному номеру корзины легко генерировать ключ (key).

С настоящими хеш-функциями это проблематично, поэтому предусмотрено значение параметра HASH_TYPE равное "dummy hash".
Если выбран этот тип хэша, то номер корзины — это просто старшие BUCKET_WIDTH бит от ключа.

Следовательно, когда key = 0x92123456, а BUCKET_WIDTH равен 8, то bucket_num = 0x92.
Это позволит легко составить необходимое воздейстие для генерации тех или иных граничных случаев.

Логирование в симуляции

Иногда разработчики отлаживают свои RTL-модули прямо на железе (читай, платах) с использованием SignalTap или ChipScope. Такой подход не всегда самый быстрый и продуктивный — требуется пересборка всего проекта (от 10 минут до нескольких часов) (а иногда не один раз), плата под рукой, отладчик, генерация входных воздействий и т.д.

Для ускорения разработки используются специальные симуляторы, такие как ModelSim, 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, то в качестве хорошего, правильного тестбенча там приводится следующая схема:


В этой статье забирать хлеб у Chris Spear я не собираюсь, поэтому о том что обозначают все эти компоненты подробно рассказывать не буду.

Схема моего тестбенча:

top_tb

Топовый модуль.

DUT (Device/Design Under Test)

Наш подопытный — экземпляр модуля hash_table_top.

ht_driver

• содержит mailbox 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                                                        

tests

Для проверки работоспособности были написаны три теста/входных воздействия.

Макросы для упрощения работы:

`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_monitor

• следит за выходным интерфейсом ht_res.
• как только там есть результат, то выцепляет его и отправляет в ht_scoreboard.

ht_scoreboard

Проверяет корректность работы DUT'a.

В себе содержит:

• два mailbox, куда кладут команды и результат ht_driver и ht_monitor соответственно.
• референсная модель хеш-таблицы ref_hash_table.

Алгоритм работы:

• как только пришел результат ht_res, то вынимаются из очереди он и соответствующий ему запрос. Здесь нам на руку то, что на каждую команду будет ответ.
• вызывается функция check, которая скармливает команду в референсную модель и сравнивает результаты от DUT'a и референсной модели.
• если совпадения нет, то с помощью $error будет распечатано об этом сообщение в лог, а в GUI ModelSim'a появится красная стрелочка в том момент времени, когда это произошло.

Coverage

Итак, уже есть система (если хотите, фреймворк), которая позволяет отправлять различные входные воздейстия, а так же анализировать корректность реакции DUT. Для того, чтобы убедиться, что багов нет, необходимо покрыть "все возможные" варианты.

Для оценки покрытия в языке SystemVerilog введены такие объекты как covergroup и coverpoint. С их помощью можно описать те точки, где мы хотим сэмплировать, а так же какую статистику собирать.

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, а на удаление 18
• всего один раз пытались искать, когда в корзине не было элементов
• ни разу не было события INSERT_NOT_SUCCESS_TABLE_IS_FULL

В итоге

• есть система, которая проверяет правильно ли работает DUT, сравнивая её выход с референсной моделью.
• есть небольшой набор тестов, которые генерируют входные воздействия.
• есть обратная связь о качестве тестов (coverage).
• заранее упростили дебаг и симуляцию, используя "dummy hash" и логирование.

В чем заключалась бага

Оказалось, если подать такое воздействие:

`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 "зависал":

• постоянно читает из адреса 0x001
• состояние FSM state висит в GO_ON_CHAIN_S (и из него больше никогда не выйдет)

(кликните для увеличения)

В логе возникли сообщения:

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 содержит некорректные данные:

• ячейка 0x000 указывает, что в ячейке 0x001 есть продолжение цепочки (next_ptr = 0x001, next_ptr_val = 0x1)
• в ячейке 0x001 хранится ключ 0x00000000. Он никак не может быть в корзине 0x05, т.к. в симуляции используется dummy hash.

При добавлении ключа 0x05000002 происходит интересная ситуация: снова происходит запись два раза в одну ячейку 0x001.

• запись на 355 нс записывает новое значение, т.к. модуль empty_ptr_storage выдал, что 0x001 пустует (нам повезло, что сейчас алгоритм работы этого модуля такой, что он отдает самый маленький адрес, который считается пустым)
• запись на 365 нс обновляет ячейку, которая предыдущая в цепочке, и по мнению модуля это 0x001. В итоге 0x001 теперь указывает на 0x001.

При попытке добавления ключа 0x05000003 происходит зацикливание при проходе по цепочке. Начиная с 445 нс мы будем бесконечно бегать по цепочке и читать один и тот же адрес.

В чём оказалась ошибка

Очевидно, что ошибку вносит модуль, который удалял данные (data_table_delete).

В момент 255 нс он должен был в ячейке 0x000 флаг next_ptr_val сделать равным нулю, а в момент 265 нс записать в 0x001 записать все нули. Так предполагалось по коду этого модуля, но этого, как видим, не произошло.

Дело в том, что надо было отдельно сохранить rd_addr и rd_data, которые мы прочитали с конца цепочки, а так мы использовали значения, с которыми только что работали.

Такие ошибки (лишняя задержка на один такт, перезаписанные данные не вовремя и пр.) весьма типичны в RTL-коде. Интереса они особого не представляют, поэтому я это не особо расписываю в статье.

Какие ошибки были допущены (при разработке)

Ведение проекта "неидеально"

Дело в том, что я не довёл проект до логического конца, который я себе представлял. Почему — сейчас уже не вспомню.

Например, в README в проекта не указано того, где и как использовался/тестировался этот модуль.

Сравните две фразы:

1. этот проект используется в продакшене в 100G коммутаторе.
2. этот проект писался по приколу на нескольких выходных за банками пива томатным соком.

Если бы я явно указал, что этот модуль я написал просто так на выходных и никуда его не встраивал, то, возможно, сторонние разработчики не использовали мой модуль и съэкономили бы себе время (правда, тогда бы я не узнал, что у меня есть бага, а вы бы не прочитали эту статью).

Когда я начал разбираться где проблема в коде, я расстроился, когда увидел, что проблема есть с переменной 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 без пояснения — это плохо. Лишние пять минут описания проблемы всегда окупятся в будущем.

*Выводы:

• если что-то выкладываете в опенсорс, указывайте явно как и где оно тестировалось на железе (если тестировалось). Если оно не тестировалось, то напишите об этом явно.
• если ведете проект в одиночку, просите кого-то (возможно со стороны, например на electronix.ru) отревьюить код. Возможно, он даст кое-какие советы, замечания.
• даже если есть проблемы, которые вы не смогли решить (например, было вам лень), то явно указывайте это в файле типа, KNOWN_PROBLEMS/KNOWN_BUGS

Coverage

Легко заметить, что те точки, на которое смотрит покрытие, не дает полной картины:

• не учитывается "история": как шли запросы друг за другом и к каким корзинам они относились.
• не учитывается в какой части цепочки остановился поиск, либо было удалены данные (в начале/середине/конце).

Исправляем:

Вводим тип 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 специально это число я не считал).

Выводы:

• coverage ваш друг и союзник. Без лишних затрат он смотрит на те точки, которые вы указали и подсчитывает статистику. Можно автоматически сделать сочетания между различными переменными и проверить, что во всех возможных комбинациях эти переменные появляются.
• чем в больших ситуациях побывает модуль, тем больше вероятность нахождения ошибки.
• если вам доступен RTL, который тестируете (белый ящик), то подумайте какие граничные ситуации там бывают. Предусмотрите это в bin'ах для анализа.

Нет рандомизированного теста

При верификации сложных и больших систем необходимо убедится, что покрываются или почти все варианты.
Вручную сложно сделать все варианты. Выход — рандомизированное тестирование. Но просто генерировать случайные данные на входе, не самая лучшая идея: есть методика Constrained Random Verification.

Да, мы подаем случайные значения, но они чем-то ограничены, либо подчиняются какому-то простому (или не очень) закону, для воспроизведения того, что вам надо.

Сделаем функцию, которая дает нам случайный ключ в нужном диапазоне корзин и значения ключей:

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)

Примечание:

• конечно, вот такая случайная генерация и shuffle, не самая красивая идея. Действенная и простая в реализации, но не красивая. В SystemVerilog есть специальная конструкция constraint блок: с его помощью можно создавать осмысленные транзакции с нужными ограничениями.

Выводы:

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

Нет отслеживания проблем в "реальном" времени

Нюанс этого проекта был в том, что если причина ошибки от следствии может быть отделено огромным симуляционным временем.

При возникновении ошибки (а её детектирование происходит по выходу 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.
Так же там написана функция, которая обходит таблицы и проверяет на те условия, которые мы описали ранее. Файл полностью можно глянуть тут.

Откатим фикс для воспроизведения баги и посмотрим лог:

...
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

Оказалось, что ошибка детектируется уже на тех трех ручных тестах (без участия рандомизированных)!

Обход ячеек показал:

• есть указание на адрес 0x004, хотя референсная модель считает, что эта ячейка пустая, т.к. на 1335 нс её освободили.
• в ячейке 0x004 лежит key = 0x00000000, который не может принадлежать корзине 0x01 (т.к. используется dummy hash).

Выводы:

• подумайте, какие ситуации не должны происходить при корректной работе. Напишите правила и проверяйте на это! Любое отклонение от нормы явно говорит о неверном (или неожидаемом) поведении.
• очень часто проверки встраивают в интерфейсы общения между модулями. Тогда лучше использовать такую конструкцию как assertion.

Заключение

Дураки говорят, что они учатся на собственном опыте, я предпочитаю учиться на опыте других. (Отто фон Бисмарк)

В этой статье я рассказал из чего может состоять простой тестбенч для верификации простых IP-ядер для ASIC/FPGA в разрезе проекта хеш-таблицы.

Исходники:

• проект
• проект до фикса баги
• проект после фикса баги
• проект на момент статьи

Главной своей ошибкой я считаю то, что не доделал до конца проект в своё время. План по верификации у меня был, и там были отмечены часть идей, которые мы и реализовали в этой статье.

Надеюсь, статья была интересна начинающим RTL-разработчикам, которые хотят улучшить свои тестбенчи.

Делитесь в комментариях, какой болезненный опыт был у вас при верификации RTL-кода :)

Спасибо за внимание! Буду рад вопросам и замечаниям в комментариях или в личной почте.

P.S.:
Это мой первый пост на Хабре в маркдауне на Хабре.
Подскажите, пожалуйста:

• почему не подсвечивается адекватно код, хотя я ему указал systemverilog? GitHub Flavored Markdown вроде как должен знать это...
• почему тэг spoiler приводит к тому, что весь дальнейший текст не распознается как markdown?