ハッシュテーブルを作成するときにミスを犯した方法と、これからどのような結論を導き出しましたか

理論的な理解を明確にするために、あなた自身の過ちから、あなた自身の苦い経験から学ぶよりも良い方法はありません。 （フリードリッヒエンゲルス）

みなさんこんにちは！

同僚が数週間前にリンクインで私に手紙を書いて、ハッシュテーブルが私のgithub プロジェクトで正しく機能しないと言った。

テストと修正が私に送られ、システムが「ハング」する状況が実際に作成されました。 問題を調査すると、検証中にいくつかの間違いを犯したことに気付きました。 Habrでは、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; 

注 ：
実際、 found_valueではrescodeとfound_valueのみに関心がありfound_valueが、少し先を見ています。他のフィールドがないと、検証するのが難しくなります。 とにかく、それらが鉄で使用されていない場合、シンセサイザーはそれらを切り取り、リソースを消費しません。

何がどこにあるか：

• すべてのデータ（ key 、 value ）はdata_table保存されdata_table 。
• 情報は、リンクリストを整理するためのデータ（ next_ptr 、 next_ptr_val ）の隣に格納されます。
• バスケットのリンクリストの先頭が位置するセル番号は、 head_table格納されhead_table 。
• empty_ptr_storageは、空の行番号をdata_table保存しdata_table 。

head_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 ）を実行（find、insert、delete）のために受け取り、 data_tableから読み書きする（リンクされたリストを実行task ）モジュール。 ht_resの結果をht_resます。

興味深いニュアンス：

• data_tableメモリには2クロックの読み取り遅延があるため、各クロックサイクルを検索するために、複数の（5つの）並列モジュールが作成され、タスクはラウンドロビンによって分散されます。
• 空きセルの検索を高速化するために、 empty_ptr_storage提供されています。 執筆時点では、これは非常に非合理的に実装されていました。ベクトルempty_ptr_mask （その長さはdata_tableテーブル内のセルの数です）により、レジスタに格納されています。 また、空の要素の検索は、（組み合わせで）ゼロメジャーを「無効化」することによって行われます。 リソースと頻度の点では、これは最適なソリューションではありません。

次のようになります（ クリックして拡大 ）：

エラーを回避/デバッグを簡素化するために私がしたこと

ハッシュテーブルの作成を開始する前に、プロジェクトが簡単ではないことを理解したため、開発を加速しデバッグを簡素化するいくつかのことを事前に予測しました。

SystemVerilogとコーディングスタイル

SystemVerilogと企業スタイルのコーディングがHDL言語として使用されました。

これにより、構造を簡単に記述し（上記を参照）、独自のデータ型を作成して、たとえば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を使用して作成しているため、アルテラのFPGAが提供/促進するインターフェースに精通しています。 このプロジェクトでは、 Avalonファミリーを使用しました。

コマンドは単なるデータストリーム（1ワードAvalon-Streaming (Avalon-ST)コマンド）であるため、 Avalon-Streaming (Avalon-ST)標準Avalon-Streaming (Avalon-ST) （ data 、 ready 、 valid信号）を使用しました。

これは、 readyLatency = 0 （ 標準から取得 ）のときのAvalon-ST上のトランザクションの様子です。

この図では、スレーブが制御するレディ信号がトランザクションとデータ転送をシャットダウンしていることがわかります。

ダミーハッシュ

このハッシュテーブルをどのように作成するのか疑問に思ったとき、最も困難なことは検証することであることに気付きました。 明らかに、最も興味深いニュアンスは、すでにデータがあるチェーンに追加しようとしたり、長いチェーンから削除したりするときに表示されます。

これは、システムへの影響が適用されたときに、事前定義されたバスケット番号を使用してキー（ key ）を簡単に生成できる必要があることを意味します。

実際のハッシュ関数では、これには問題があるため、 HASH_TYPEパラメーターの値は"dummy hash"等しくHASH_TYPEます。
このタイプのハッシュが選択されている場合、バスケット番号は単にキーの上位BUCKET_WIDTHビットです。

したがって、 key = 0x92123456で、 BUCKET_WIDTHが8の場合、 bucket_num = 0x92です。
これにより、特定の境界ケースの生成に必要なアクションを簡単に作成できます。

シミュレーションロギング

開発者は、 SignalTapまたはChipScopeを使用して、ハードウェア（読み取り、ボード）でRTLモジュールを直接デバッグする場合があります 。 このアプローチは、常に最速かつ最も生産的ではありません-プロジェクト全体（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で）。

ログは時間を大幅に節約しました。簡単な例を送信するとき、どの順序で書かれるべきかを知っていて、ログを見るだけでした。 エラーが発生した場合、タイミング図ではなくコードを分析しました。

チャレンジとして、タイムアウトなしで1週間以内にRTLコードをデバッグすることをお勧めします（快適ゾーンを離れる）。

検証

System Verilog for Verificationなどの優れた文献に目を向けると、優れた正しいテストベンチとして次の図があります。

この記事では、Chris Spearからパンを取り上げるつもりはないので、これらすべてのコンポーネントの意味については詳しく説明しません。

私のテストベンチのスキーム：

top_tb

トップモジュール。

DUT（デバイス/テスト対象設計）

テスト対象は、 hash_table_topモジュールのインスタンスです。

ht_driver

• はメールボックスgen2drv含みます、これはコマンドがDUT送られるためです。
• このキューにコマンドが表示されるとすぐに、コマンドはDUT送信されDUT 。
• コマンドをDUTに送信した後、コマンドはht_scoreboardコピーされht_scoreboard 。

このメールボックスにコマンドを配置するには、階層アクセスが使用されます。

 task send_to_dut_c( input ht_command_t c ); // using hierarchial access to put command in mailbox env.drv.gen2drv.put( c ); endtask 

テスト

パフォーマンスをテストするために、3つのテスト/入力アクションが作成されました。

作業を簡素化するマクロ：

 `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送信しht_scoreboard 。

ht_scoreboard

DUTの正しい動作を確認します。

次のものが含まれます。

• 2つのmailbox 、チームはそれぞれht_driverとht_monitorの結果を入れます。
• ハッシュテーブルref_hash_table参照モデル。

操作アルゴリズム：

• ht_resの結果がht_resとすぐに、彼と対応するリクエストはキューから取り出されます。 ここで、各チームに答えがあるのは私たちの手にあります。
• check関数が呼び出され、コマンドが参照モデルに入力され、DUTと参照モデルの結果が比較されます。
• 一致するものがない場合は、 $errorを使用して、これについてログにメッセージが出力され、ModelSimのGUIにこれが発生した瞬間に赤い矢印が表示されます。

カバレッジ

そのため、さまざまな入力の影響を送信したり、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結果ht_res何であったかを追跡します。
• bucket_occup配列には、操作時にバスケットにあった要素の数が格納されます。
• CMDOP_BUCKOCUPコマンドをバスケット内の要素の数と「交差」させます。イベントはXコマンドであり、バスケットではYの要素が存在するkey属していました。
• CMDRES_BUCKOCUP結果をバスケット内のアイテム数と「 CMDRES_BUCKOCUP 」させます。

シミュレーションの終了後、ModelSimコンソールでレポートを取得できます。

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

すべての可能な交差点は自動的に受信されました-私たちは余分なことを書きませんでした。

3つのテストの後、次のことが明らかになります。

• OP_INSERTを挿入するコマンドが21 OP_INSERT 、削除するコマンドが18個ありました
• バスケットにアイテムがなかったときに一度だけ検索しようとした
• INSERT_NOT_SUCCESS_TABLE_IS_FULLイベントは一度もなかった

最後に

• 出力を参照モデルと比較することにより、DUTが正常に機能しているかどうかを確認するシステムがあります。
• 入力効果を生成するテストの小さなセットがあります。
• テストの品質（カバレッジ）に関するフィードバックがあります。
• 「ダミーハッシュ」とロギングを使用して、デバッグとシミュレーションを事前に簡素化しました。

バグは何でしたか

この効果を適用すると、次のことがわかりました。

 `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挿入されると、 0x05000003モジュールが「ハング」するという事実につながります。

• 常にアドレス0x001から読み取ります
• FSM stateはGO_ON_CHAIN_Sハングし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 nsの奇妙なイベントが発生した瞬間に気付くかもしれません。最初に、 addr = 0x001が1つの値を記録し、次に別の値を記録しました。

これにより、 data_tableに誤ったデータが含まれるという事実につながります。

• セル0x000は、セル0x001にチェーンの継続があることを示します（ next_ptr = 0x001 、 next_ptr_val = 0x1 ）
• セル0x001はキー0x00000000を保存します。 バスケット0x05に入れることはできません。なぜなら、 シミュレーションではdummy hash使用しdummy hash 。

キー0x05000002を追加すると、興味深い状況が発生します。1つのセル0x001で記録が2回発生します。

• 355 nsで記録すると、新しい値が記録されます。 empty_ptr_storageモジュールempty_ptr_storage 、0x001が空であることをempty_ptr_storageた（このモジュールのアルゴリズムが、空と見なされる最小のアドレスを提供するようになったことは幸運です）
• 365 nsに書き込むと、チェーンの前のセルであるセルが更新され、モジュールによると0x001になります。 その結果、0x001は0x001を指すようになりました。

キー0x05000003を追加しようとすると、チェーンを通過するときにループが発生します。 445 nsからは、チェーンに沿って無限に実行し、同じアドレスを読み取ります。

間違いは何でしたか

明らかに、データを削除したモジュール（ data_table_delete ）によってエラーが発生します。

255 nsの時点で、 next_ptr_valセルのnext_ptr_valフラグをゼロに設定し、265 nsの時点で0x001に書き込んですべてのゼロを書き込む必要がありました。 そのため、このモジュールのコードで想定されていましたが、これは、見てのとおり、起こりませんでした。

事実、チェーンの最後から読み取るrd_addrとrd_dataを別々に保存するrd_addrあったため、作業したばかりの値を使用しました。

このようなエラー（1クロックサイクルによる余分な遅延、間違った時間に上書きされたデータなど）は、RTLコードでは非常に一般的です。 彼らはあまり関心を表していないので、この記事では特に説明しません。

どのような間違いがあったか（開発中）

プロジェクト管理は「不完全」です

事実は、私が想像したようにプロジェクトを論理的な終わりに至らなかったということです。 なぜ-今は覚えていない。

たとえば、 READMEでは、プロジェクトはこのモジュールがどこでどのように使用され、テストされたかを示していません。

2つのフレーズを比較します。

1. このプロジェクトは、 100Gスイッチの実稼働で使用されます。
2. このプロジェクトは数週間にわたって楽しみのために書かれました ビール缶 トマトジュース。

週末にこのモジュールを書いて、どこにも埋め込まなかったことを明確に示していた場合、サードパーティの開発者は私のモジュールを使用せず、時間を節約できなかったでしょう（ただし、バグがあることはわかりません） 、この記事は読みません）。

問題がコード内のどこにあるかをprev_rd_addrし始めたとき、問題が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は悪いです。 問題を説明するための余分な5分間は、将来的に常に成果を上げます。

* 結論 ：

• オープンソースに何かを投稿する場合は、ハードウェアでテストした方法と場所を明示的に示します（テストした場合）。 テストされていない場合は、明示的に記述してください。
• 単独でプロジェクトを実施している場合は、誰か（おそらく、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- :)

ご清聴ありがとうございました！ .

PS：
.
, :

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