Pull to refresh

Как я ошибся при написании хеш-таблицы и какие выводы из этого сделал

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

Всем привет!


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


Мне прислали тесты и фикс, и действительно создавалась ситуация, где система "зависала". При расследовании проблемы я понял, что допустил несколько ошибок при верификации. На Хабре тема верификации 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?
Tags:
Hubs:
+35
Comments 9
Comments Comments 9

Articles