How I made a mistake when writing a hash table and what conclusions did I make of it

For clarity of theoretical understanding, there is no better way than to learn from your own mistakes, the hard way. (Friedrich Engels)

Hello!

A few weeks ago, a colleague wrote to me in Linkedin and said that the hash table does not quite work correctly on my github project .

They sent me tests and fixes, and really created a situation where the system was "hanging". When investigating a problem, I realized that I had made several verification errors. On Habré, the topic of verification of the RTL code is not too detailed, so I decided to write an article.

From the article you will learn:

• how can you organize a hash table on FPGA.
• what was built verification.
• what mistakes I made (they led to the fact that the bug was not noticed earlier).
• how this can be fixed.

Welcome under the cut!

Briefly about the project

Goals and background

The goals that I set before the start of the project:

• if it is claimed that the hash table has N elements, then it is guaranteed that any N elements will fit there.
• the table itself resolves collisions, there is no limit on the number of items in the basket (but not more than the size of the hash table, of course).
• the table allows you to add, search, and delete by key
• if the search does not cause collisions, then the table is ready to accept tasks for searching every clock cycle (maximum performance).
• I don’t worry about resources and clock frequency.

Internal device

I want to get maximum performance, so I organize the pipeline:

Login ( 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; 

Output ( 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; 

Note :
In fact, in ht_result_t we are only concerned with rescode and found_value , but running a little ahead, it would be more difficult to verify without other fields. Anyway, if they are not used in hardware, the synthesizer will cut them out and they will not occupy resources.

What and where is located:

• All data ( key , value ) is stored in data_table memory.
• Next to the data is stored information for organizing a linked list ( next_ptr , next_ptr_val ).
• The cell number where the start of the linked list for the cart is located is stored in the head_table .
• empty_ptr_storage stores numbers of empty lines in data_table .

Word in head_table :

 typedef struct packed { logic [HEAD_PTR_WIDTH-1:0] ptr; logic ptr_val; } head_ram_data_t; 

Word in 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; 

Work algorithm:

• calc_hash uses the key to calculate the hash (its value will be the basket number ( bucket_num )).
• use bucket_num as the address for head_table : we get a pointer to the beginning of the linked list for the basket.
• the multiplexer distributes the job to the desired module ( data_table_search , data_table_insert , data_table_delete ) (focusing on opcode ).
• modules that receive the corresponding tasks ( task ) for execution (find, insert, delete) and read / write from the data_table (run on the linked list). Form the result ht_res .

Interesting nuances:

• The data_table memory has a read delay of two clocks, so in order to perform a search for each beat, several (five) parallel modules are made, the tasks between which are distributed by round-robin.
• For speeding up the search for a free cell, an empty_ptr_storage provided. At the time of this writing, it is implemented very inefficiently: with the vector empty_ptr_mask (its length is the number of cells in the data_table table), which is stored on the registers. And the search for an empty element occurs "brute force" for zero cycles (on the combination). In terms of resources and frequency, this is not the best solution.

It looks like this ( click to enlarge ):

What I did to avoid errors / simplify debugging

Before starting to make a hash table, I understood that the project was not easy, so I had foreseen in advance some things that accelerated development and simplified debugging.

SystemVerilog & Coding Style

SystemVerilog and corporate coding style were used as the HDL language.

It allows you to conveniently describe the structure (see above) and create your own data types, for example, to describe the 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; 

Stream Interface (Avalon-ST)

When designing a pipeline, you need to be well aware of when it will stop .
You can think of a lot of things, but it is best to use ready-made, developed interfaces.

At work, I write under Altera's FPGA, so I’m better acquainted with the interfaces that they offer / promote. In this project, I used the Avalon family.

Commands are just a data stream (one word is one command), so I used the standard Avalon-Streaming (Avalon-ST) ( data , ready , valid signals).

This is how a transaction on Avalon-ST looks like with readyLatency = 0 ( taken from the standard ):

In this picture you can see that the ready signal, which is controlled by the slave, closes the transaction and data transfer.

Dummy hash

When I wondered how I would make this hash table, I understood that the most difficult thing would be in its verification. Obviously, the most interesting nuances appear when you try to add to the chain, where you already have data, or you delete it from the long chain and so on.

This means that when the impact on the system is given, then you need to be able to easily generate a key using a predefined basket number.

With real hash functions, this is problematic, so the HASH_TYPE parameter is HASH_TYPE to "dummy hash" .
If this type of hash is selected, then the basket number is simply the highest BUCKET_WIDTH bit from the key.

Therefore, when key = 0x92123456 , and BUCKET_WIDTH is 8, then bucket_num = 0x92 .
This will make it easy to make the necessary impact for the generation of certain boundary cases.

Logging in simulation

Sometimes developers debug their RTL modules directly on hardware (read, boards) using SignalTap or ChipScope . This approach is not always the fastest and most productive - it requires rebuilding the entire project (from 10 minutes to several hours) (and sometimes more than once), the board is at hand, the debugger, the generation of input effects, etc.

To speed up development, special simulators are used , such as ModelSim , VCS, Icarus Verilog, etc. They allow you to track the values ​​of all (or selected) signals / variables during debugging by constructing time diagrams (time frame). A huge amount of time can be spent on viewing these diagrams during debugging.

Solution :
Log all actions that occur, for quick viewing with your eyes.

To do this, in data_table_insert , data_table_delete , data_table_search I added functions that print to the log:

 function void print( string s ); $display("%08t: %m: %s", $time, s); endfunction 

The display format is similar to printf (you can use %d , %f , etc.):

• %08t - displays the simulation time (it will be convenient then to jump at the right time).
• %m - prints the module (hierarchical name) where it occurred. (Attention: this does not require arguments!)
• %s - print line

Log FSM transitions:

 function void print_state_transition( ); string msg; if( next_state != state ) begin $sformat( msg, "%s -> %s", state, next_state ); print( msg ); end endfunction 

We are printing a new assignment:

 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 

And so on...

For simulation I use ModelSim. In his log, which is displayed on the screen (and by default will go into the transcript file), the following lines appear:

 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 

Such a text log is easy to grep'at, or run a search (for example, in vim'e).

The logs saved a huge amount of time: when submitting simple examples, I knew what order should be written and just looked in the log. If an error occurred, then proceeded to the analysis of the code, and not the time diagrams.

I advise everyone to try to debug the RTL-code without a temporary house during the week (leave the comfort zone).

Verification

If you turn to good literature, for example, SystemVerilog for Verification , then as a good, correct testbench the following scheme is given there:

In this article, I'm not going to take away the bread from Chris Spear, so I’m not going to talk in detail about what all these components mean.

My testbench circuit:

top_tb

Top module.

DUT (Device / Design Under Test)

Our experimental is an instance of the hash_table_top module.

ht_driver

• contains the mailbox gen2drv , which is intended for commands that will be sent to the DUT .
• as soon as a command appears in this queue, it will be sent to the DUT .
• after sending the command to the DUT , it is copied to the ht_scoreboard .

To put a command in this mailbox, hierarchical access is used:

 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

To test the performance were written three tests / input effects.

Macros to simplify work:

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

Test example:

 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

• monitors the output interface ht_res .
• as soon as there is a result, it hooks it out and sends it to the ht_scoreboard .

ht_scoreboard

Checks the correctness of the DUT'a work.

It contains:

• two mailbox , where put the command and the result of ht_driver and ht_monitor respectively.
• reference hash table ref_hash_table .

Work algorithm:

• as soon as the result of ht_res came, he and the corresponding request are removed from the queue. Here we are in the hands of the fact that each team will be answered.
• the check function is called, which feeds the command to the reference model and compares the results from the DUT and the reference model.
• if there is no match, then using $error the message will be printed to the log, and a red arrow will appear in the ModelSim GUI at the moment it happened.

Coverage

So, there is already a system (if you wish, a framework) that allows you to send various input effects, as well as analyze the correctness of the DUT reaction. In order to make sure that there are no bugs, it is necessary to cover "all possible" options.

Objects such as covergroup and coverpoint are introduced to assess coverage in the SystemVerilog language. With their help, you can describe those points where we want to sample, as well as what statistics to collect.

 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 

Explanation:

• CMDOP and CMDRES keep track of what the ht_cmd operations ht_cmd and the results of ht_res .
• array bucket_occup stores the number of items that were in the basket at the time of the operation.
• CMDOP_BUCKOCUP - "crosses" the commands with the number of items in the basket: we get the events, the command was X, and in the basket, to which the key belonged, where were the Y elements.
• CMDRES_BUCKOCUP - "crosses" the result with the number of items in the basket.

After the simulation is finished, you can get a report in the ModelSim console:

 coverage save 1.ucdb vcover report 1.ucdb -verbose -cvg 

Report:

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

All possible crosses were obtained automatically - we did not write anything extra.

After three tests, it is clear that:

• OP_INSERT were 21 OP_INSERT insertion OP_INSERT , and 18
• only once tried to search when there were no items in the basket
• never had an INSERT_NOT_SUCCESS_TABLE_IS_FULL event

Eventually

• There is a system that checks whether the DUT is working correctly by comparing its output with the reference model.
• There is a small set of tests that generate input effects.
• There is a feedback about the quality of tests (coverage).
• debug and simulate in advance using dummy hash and logging.

What was the bug

It turned out, if you submit such an impact:

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

then this will cause the 0x05000003 module data_table_insert "hang" when inserting the key 0x05000003 :

• constantly reading from address 0x001
• the state of the FSM state hangs in GO_ON_CHAIN_S (and will never leave it again)

( click to enlarge )

There are messages in the log:

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

Rewind a little log and analyze it. I gave only those lines that are interesting to us (what was read and written in the data_table 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 

You may notice that at the time point of 255-265 ns strange events occurred: first, one value was written to addr = 0x001 and then another value.

This leads to the fact that the data_table table contains incorrect data:

• cell 0x000 indicates that there is a continuation of the chain in cell 0x001 ( next_ptr = 0x001 , next_ptr_val = 0x1 )
• In cell 0x001, the key 0x00000000 is stored. It can not be in the basket 0x05, because dummy hash used in the simulation.

When adding the key 0x05000002, an interesting situation occurs: again, writing to the same cell 0x001 occurs twice.

• writing to 355 ns records the new value, since the empty_ptr_storage module issued that 0x001 is empty (we were lucky that now the algorithm of this module is such that it gives the smallest address that is considered empty)
• the 365 ns record updates the cell that is previous in the chain, and in the opinion of the module it is 0x001. In total, 0x001 now points to 0x001.

When you try to add a key 0x05000003, a loop occurs as you move through the chain. Starting from 445 ns, we will run endlessly along the chain and read the same address.

What was the mistake

Obviously, the error is made by the module that deleted the data ( data_table_delete ).

At 255 ns, he should have made the next_ptr_val flag in cell 0x000 equal to zero, and at 265 ns, write 0x001 to write all zeros. So it was assumed by the code of this module, but this, as we see, did not happen.

The fact is that it was necessary to separately save rd_addr and rd_data , which we read from the end of the chain, and so we used the values ​​we had just worked with.

Such errors (an extra delay by one clock cycle, overwritten data at the wrong time, etc.) are quite typical in the RTL code. They don’t have much interest, so I’m not really writing about it in the article.

What mistakes were made (during development)

Keeping the project "imperfect"

The fact is that I did not bring the project to its logical end, which I imagined. Why - now I do not remember.

For example, in the project's README is not specified where and how this module was used / tested.

Compare two phrases:

1. This project is used in production on a 100G switch .
2. this project was written for fun on several weekends over cans of beer tomato juice.

If I explicitly indicated that I wrote this module just like that on weekends and did not embed it anywhere, then perhaps third-party developers would not use my module and save themselves time (although then I would not know that I have a bug , and you would not read this article).

When I started to prev_rd_addr out where the problem is in the code, I was upset when I saw that the problem was with the variable prev_rd_addr . The block where its value is assigned looks like this:

 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 without explanation is bad. The extra five minutes of describing a problem will always pay off in the future.

* Conclusions :

• if you lay out something in open-source, clearly indicate how and where it was tested on hardware (if tested). If it has not been tested, then write about it explicitly.
• , - ( , 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 

Result:

 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 )

Note :

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

Conclusion

, , . ( )

IP- ASIC/FPGA -.

:

• project

, . , , .

, RTL-, .

, RTL- :)

Thanks for attention! .

PS:
.
, :

• , systemverilog ? GitHub Flavored Markdown ...
• spoiler , markdown?