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

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


Всем привет!

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

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

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

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


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

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


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


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

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


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


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

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


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

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


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

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 (взято из стандарта):

54d8b69ca360b5f8202f681a65564dc8.png
На этой картинке видно, что сигнал 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, то в качестве хорошего, правильного тестбенча там приводится следующая схема:

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

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

a4243d53696649628ddc6eda431e56a7.png

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                           1          1 Covered                   
        bin                           5          1 Covered                             
        bin                            5          1 Covered                   
        ...                
    Cross CMDRES_BUCKOCUP                               84.6%        100 Uncovered                 
        covered/total bins:                                33         39                           
        missing/total bins:                                 6         39                           
        bin  
                                                            1          1 Covered                   
        bin                      5          1 Covered                   
        bin  
                                                            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 «зависал»:

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


0267986d381f4dd8b0294c40be007eb7.png
(кликните для увеличения)

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

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

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


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

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


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

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


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

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

Дело в том, что надо было отдельно сохранить 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 


Произойдет попадание, если:

  • сейчас команда 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_
    
            

© Habrahabr.ru