aboutsummaryrefslogtreecommitdiffstats
path: root/fpga/usrp3/lib/control/map
diff options
context:
space:
mode:
Diffstat (limited to 'fpga/usrp3/lib/control/map')
-rw-r--r--fpga/usrp3/lib/control/map/AUTHORS3
-rw-r--r--fpga/usrp3/lib/control/map/axis_muxed_kv_map.v206
-rw-r--r--fpga/usrp3/lib/control/map/cam.v103
-rw-r--r--fpga/usrp3/lib/control/map/cam_bram.v259
-rw-r--r--fpga/usrp3/lib/control/map/cam_priority_encoder.v94
-rw-r--r--fpga/usrp3/lib/control/map/cam_srl.v223
-rw-r--r--fpga/usrp3/lib/control/map/kv_map.v253
7 files changed, 1141 insertions, 0 deletions
diff --git a/fpga/usrp3/lib/control/map/AUTHORS b/fpga/usrp3/lib/control/map/AUTHORS
new file mode 100644
index 000000000..c727d8d3c
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/AUTHORS
@@ -0,0 +1,3 @@
+Contributions from:
+Ettus Research, A National Instruments Company
+Alex Forencich <alex@alexforencich.com> \ No newline at end of file
diff --git a/fpga/usrp3/lib/control/map/axis_muxed_kv_map.v b/fpga/usrp3/lib/control/map/axis_muxed_kv_map.v
new file mode 100644
index 000000000..152cee8eb
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/axis_muxed_kv_map.v
@@ -0,0 +1,206 @@
+//
+// Copyright 2018 Ettus Research, A National Instruments Company
+//
+// SPDX-License-Identifier: LGPL-3.0-or-later
+//
+// Module: axis_muxed_kv_map
+//
+// Description:
+//
+// This module implements a memory that stores key and value (KV) pairs such
+// that the value can be looked up using the key (e.g., for a routing table).
+// This implementation uses AXI stream for both inserting key-value pairs and
+// for looking up a value by its key. It also supports multiple find/result
+// AXI streams, which share the same KV map internally.
+//
+// Values are inserted into the KV map using the axis_insert_* AXI stream. A
+// value can be looked up by its key using the axis_find_* AXI stream, in
+// which case the resulting value is output on the axis_result_* AXI stream.
+//
+// Ports:
+//
+// axis_insert_tdest : Key to insert into the KV map
+// axis_insert_tdata : Value to associate with the key in TDEST
+// axis_insert_tvalid : Standard AXI stream TVALID
+// axis_insert_tready : Standard AXI stream TREADY
+//
+// axis_find_tdata : Key to look up in the KV map
+// axis_find_tvalid : Standard AXI stream TVALID
+// axis_find_tready : Standard AXI stream TREADY
+//
+// axis_result_tdata : Value associated with key that was input on axis_find
+// axis_result_tkeep : Indicates if TDATA contains a valid value (i.e.,
+// TKEEP is 0 if the lookup fails to find a match)
+// axis_result_tvalid : Standard AXI stream TVALID
+// axis_result_tready : Standard AXI stream TREADY
+//
+// Parameters:
+//
+// KEY_WIDTH : Width of the key (axis_insert_tdest, axis_find_tdata)
+// VAL_WIDTH : Width of the value (axis_insert_tdata, axis_result_tdata)
+// SIZE : Size of the KV map (i.e., 2**SIZE key-value pairs)
+// NUM_PORTS : Number of AXI-Stream ports for the find and result interfaces
+//
+
+module axis_muxed_kv_map #(
+ parameter KEY_WIDTH = 16,
+ parameter VAL_WIDTH = 32,
+ parameter SIZE = 6,
+ parameter NUM_PORTS = 4
+) (
+ input wire clk,
+ input wire reset,
+
+ input wire [KEY_WIDTH-1:0] axis_insert_tdest,
+ input wire [VAL_WIDTH-1:0] axis_insert_tdata,
+ input wire axis_insert_tvalid,
+ output wire axis_insert_tready,
+
+ input wire [(KEY_WIDTH*NUM_PORTS)-1:0] axis_find_tdata,
+ input wire [NUM_PORTS-1:0] axis_find_tvalid,
+ output wire [NUM_PORTS-1:0] axis_find_tready,
+
+ output wire [(VAL_WIDTH*NUM_PORTS)-1:0] axis_result_tdata,
+ output wire [NUM_PORTS-1:0] axis_result_tkeep,
+ output wire [NUM_PORTS-1:0] axis_result_tvalid,
+ input wire [NUM_PORTS-1:0] axis_result_tready
+);
+
+ localparam MUX_W = $clog2(NUM_PORTS) + KEY_WIDTH;
+ localparam DEMUX_W = $clog2(NUM_PORTS) + VAL_WIDTH + 1;
+ genvar i;
+
+ localparam [1:0] ST_IDLE = 2'd0;
+ localparam [1:0] ST_REQUEST = 2'd1;
+ localparam [1:0] ST_PENDING = 2'd2;
+
+ //---------------------------------------------------------
+ // Demux find ports
+ //---------------------------------------------------------
+ wire [KEY_WIDTH-1:0] find_key, find_key_reg;
+ wire find_key_stb;
+ wire [$clog2(NUM_PORTS)-1:0] find_dest, find_dest_reg;
+ wire find_key_valid, find_key_valid_reg;
+ wire find_ready;
+ reg find_in_progress = 1'b0;
+ wire insert_stb;
+ wire insert_busy;
+ wire find_res_stb;
+ wire [VAL_WIDTH-1:0] find_res_val;
+ wire find_res_match, find_res_ready;
+
+ wire [(MUX_W*NUM_PORTS)-1:0] mux_tdata;
+ generate for (i = 0; i < NUM_PORTS; i = i + 1) begin : gen_mux_input
+ assign mux_tdata[(MUX_W*i)+KEY_WIDTH-1:MUX_W*i] = axis_find_tdata[(KEY_WIDTH*i)+:KEY_WIDTH];
+ assign mux_tdata[(MUX_W*(i+1))-1:(MUX_W*i)+KEY_WIDTH] = i;
+ end endgenerate
+
+ axi_mux #(
+ .WIDTH(KEY_WIDTH+$clog2(NUM_PORTS)), .SIZE(NUM_PORTS),
+ .PRE_FIFO_SIZE(0), .POST_FIFO_SIZE($clog2(NUM_PORTS))
+ ) mux_i (
+ .clk(clk), .reset(reset), .clear(1'b0),
+ .i_tdata(mux_tdata), .i_tlast({NUM_PORTS{1'b1}}),
+ .i_tvalid(axis_find_tvalid), .i_tready(axis_find_tready),
+ .o_tdata({find_dest_reg, find_key_reg}), .o_tlast(),
+ .o_tvalid(find_key_valid_reg), .o_tready(find_ready)
+ );
+
+ axi_fifo #(
+ .WIDTH(KEY_WIDTH+$clog2(NUM_PORTS)), .SIZE(1)
+ ) mux_reg_i (
+ .clk(clk), .reset(reset), .clear(1'b0),
+ .i_tdata({find_dest_reg, find_key_reg}),
+ .i_tvalid(find_key_valid_reg), .i_tready(find_ready),
+ .o_tdata({find_dest, find_key}),
+ .o_tvalid(find_key_valid), .o_tready(find_res_stb),
+ .space(), .occupied()
+ );
+
+ always @(posedge clk) begin
+ if (reset) begin
+ find_in_progress <= 1'b0;
+ end else begin
+ if (find_key_stb) begin
+ find_in_progress <= 1'b1;
+ end else if (find_res_stb) begin
+ find_in_progress <= 1'b0;
+ end
+ end
+ end
+
+ // find_key_stb indicates when to begin a new KV map lookup. We must wait
+ // until the output mux is ready before starting a lookup.
+ assign find_key_stb = find_key_valid & find_res_ready & ~find_in_progress;
+
+ //---------------------------------------------------------
+ // Insert logic
+ //---------------------------------------------------------
+ reg [1:0] ins_state = ST_IDLE;
+ always @(posedge clk) begin
+ if (reset) begin
+ ins_state <= ST_IDLE;
+ end else begin
+ case (ins_state)
+ ST_IDLE:
+ if (axis_insert_tvalid & ~insert_busy)
+ ins_state <= ST_REQUEST;
+ ST_REQUEST:
+ ins_state <= ST_PENDING;
+ ST_PENDING:
+ if (~insert_busy)
+ ins_state <= ST_IDLE;
+ default:
+ ins_state <= ST_IDLE;
+ endcase
+ end
+ end
+
+ assign axis_insert_tready = axis_insert_tvalid & (ins_state == ST_PENDING) & ~insert_busy;
+ assign insert_stb = axis_insert_tvalid & (ins_state == ST_REQUEST);
+
+ //---------------------------------------------------------
+ // KV map instantiation
+ //---------------------------------------------------------
+ kv_map #(
+ .KEY_WIDTH (KEY_WIDTH),
+ .VAL_WIDTH (VAL_WIDTH),
+ .SIZE (SIZE)
+ ) map_i (
+ .clk (clk),
+ .reset (reset),
+ .insert_stb (insert_stb),
+ .insert_key (axis_insert_tdest),
+ .insert_val (axis_insert_tdata),
+ .insert_busy (insert_busy),
+ .find_key_stb (find_key_stb),
+ .find_key (find_key),
+ .find_res_stb (find_res_stb),
+ .find_res_match (find_res_match),
+ .find_res_val (find_res_val),
+ .count (/* unused */)
+ );
+
+ //---------------------------------------------------------
+ // Mux results port
+ //---------------------------------------------------------
+ wire [(DEMUX_W*NUM_PORTS)-1:0] demux_tdata;
+ wire [DEMUX_W-1:0] hdr;
+ axi_demux #(
+ .WIDTH(DEMUX_W), .SIZE(NUM_PORTS),
+ .PRE_FIFO_SIZE(1), .POST_FIFO_SIZE(0)
+ ) demux_i (
+ .clk(clk), .reset(reset), .clear(1'b0),
+ .header(hdr), .dest(hdr[DEMUX_W-1:VAL_WIDTH+1]),
+ .i_tdata({find_dest, find_res_match, find_res_val}), .i_tlast(1'b1),
+ .i_tvalid(find_res_stb), .i_tready(find_res_ready),
+ .o_tdata(demux_tdata), .o_tlast(),
+ .o_tvalid(axis_result_tvalid), .o_tready(axis_result_tready)
+ );
+
+ generate for (i = 0; i < NUM_PORTS; i = i + 1) begin : gen_result_output
+ assign axis_result_tdata[(VAL_WIDTH*i)+:VAL_WIDTH] = demux_tdata[(DEMUX_W*i)+VAL_WIDTH-1:DEMUX_W*i];
+ assign axis_result_tkeep[i] = demux_tdata[(DEMUX_W*i)+VAL_WIDTH];
+ end endgenerate
+
+endmodule
diff --git a/fpga/usrp3/lib/control/map/cam.v b/fpga/usrp3/lib/control/map/cam.v
new file mode 100644
index 000000000..6b3237b6f
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/cam.v
@@ -0,0 +1,103 @@
+/*
+
+Copyright (c) 2015-2016 Alex Forencich
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+
+*/
+
+// Language: Verilog 2001
+
+`timescale 1ns / 1ps
+
+/*
+ * Content Addressable Memory
+ */
+module cam #(
+ // search data bus width
+ parameter DATA_WIDTH = 64,
+ // memory size in log2(words)
+ parameter ADDR_WIDTH = 5,
+ // CAM style (SRL, BRAM)
+ parameter CAM_STYLE = "SRL",
+ // width of data bus slices
+ parameter SLICE_WIDTH = 4
+)
+(
+ input wire clk,
+ input wire rst,
+
+ input wire [ADDR_WIDTH-1:0] write_addr,
+ input wire [DATA_WIDTH-1:0] write_data,
+ input wire write_delete,
+ input wire write_enable,
+ output wire write_busy,
+
+ input wire [DATA_WIDTH-1:0] compare_data,
+ output wire [2**ADDR_WIDTH-1:0] match_many,
+ output wire [2**ADDR_WIDTH-1:0] match_single,
+ output wire [ADDR_WIDTH-1:0] match_addr,
+ output wire match
+);
+
+generate
+ if (CAM_STYLE == "SRL") begin
+ cam_srl #(
+ .DATA_WIDTH(DATA_WIDTH),
+ .ADDR_WIDTH(ADDR_WIDTH),
+ .SLICE_WIDTH(SLICE_WIDTH)
+ )
+ cam_inst (
+ .clk(clk),
+ .rst(rst),
+ .write_addr(write_addr),
+ .write_data(write_data),
+ .write_delete(write_delete),
+ .write_enable(write_enable),
+ .write_busy(write_busy),
+ .compare_data(compare_data),
+ .match_many(match_many),
+ .match_single(match_single),
+ .match_addr(match_addr),
+ .match(match)
+ );
+ end else if (CAM_STYLE == "BRAM") begin
+ cam_bram #(
+ .DATA_WIDTH(DATA_WIDTH),
+ .ADDR_WIDTH(ADDR_WIDTH),
+ .SLICE_WIDTH(SLICE_WIDTH)
+ )
+ cam_inst (
+ .clk(clk),
+ .rst(rst),
+ .write_addr(write_addr),
+ .write_data(write_data),
+ .write_delete(write_delete),
+ .write_enable(write_enable),
+ .write_busy(write_busy),
+ .compare_data(compare_data),
+ .match_many(match_many),
+ .match_single(match_single),
+ .match_addr(match_addr),
+ .match(match)
+ );
+ end
+endgenerate
+
+endmodule
diff --git a/fpga/usrp3/lib/control/map/cam_bram.v b/fpga/usrp3/lib/control/map/cam_bram.v
new file mode 100644
index 000000000..c18df1084
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/cam_bram.v
@@ -0,0 +1,259 @@
+/*
+
+Copyright (c) 2015-2016 Alex Forencich
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+
+*/
+
+// Language: Verilog 2001
+
+`timescale 1ns / 1ps
+
+/*
+ * Content Addressable Memory (block RAM based)
+ */
+module cam_bram #(
+ // search data bus width
+ parameter DATA_WIDTH = 64,
+ // memory size in log2(words)
+ parameter ADDR_WIDTH = 5,
+ // width of data bus slices
+ parameter SLICE_WIDTH = 9
+)
+(
+ input wire clk,
+ input wire rst,
+
+ input wire [ADDR_WIDTH-1:0] write_addr,
+ input wire [DATA_WIDTH-1:0] write_data,
+ input wire write_delete,
+ input wire write_enable,
+ output wire write_busy,
+
+ input wire [DATA_WIDTH-1:0] compare_data,
+ output wire [2**ADDR_WIDTH-1:0] match_many,
+ output wire [2**ADDR_WIDTH-1:0] match_single,
+ output wire [ADDR_WIDTH-1:0] match_addr,
+ output wire match
+);
+
+// total number of slices (enough to cover DATA_WIDTH with address inputs)
+localparam SLICE_COUNT = (DATA_WIDTH + SLICE_WIDTH - 1) / SLICE_WIDTH;
+// depth of RAMs
+localparam RAM_DEPTH = 2**ADDR_WIDTH;
+
+localparam [2:0]
+ STATE_INIT = 3'd0,
+ STATE_IDLE = 3'd1,
+ STATE_DELETE_1 = 3'd2,
+ STATE_DELETE_2 = 3'd3,
+ STATE_WRITE_1 = 3'd4,
+ STATE_WRITE_2 = 3'd5;
+
+reg [2:0] state_reg = STATE_INIT, state_next;
+
+wire [SLICE_COUNT*SLICE_WIDTH-1:0] compare_data_padded = {{SLICE_COUNT*SLICE_WIDTH-DATA_WIDTH{1'b0}}, compare_data};
+wire [SLICE_COUNT*SLICE_WIDTH-1:0] write_data_padded = {{SLICE_COUNT*SLICE_WIDTH-DATA_WIDTH{1'b0}}, write_data};
+
+reg [SLICE_WIDTH-1:0] count_reg = {SLICE_WIDTH{1'b1}}, count_next;
+
+reg [SLICE_COUNT*SLICE_WIDTH-1:0] ram_addr = {SLICE_COUNT*SLICE_WIDTH{1'b0}};
+reg [RAM_DEPTH-1:0] set_bit;
+reg [RAM_DEPTH-1:0] clear_bit;
+reg wr_en;
+
+reg [ADDR_WIDTH-1:0] write_addr_reg = {ADDR_WIDTH{1'b0}}, write_addr_next;
+reg [SLICE_COUNT*SLICE_WIDTH-1:0] write_data_padded_reg = {SLICE_COUNT*SLICE_WIDTH{1'b0}}, write_data_padded_next;
+reg write_delete_reg = 1'b0, write_delete_next;
+
+reg write_busy_reg = 1'b1;
+
+assign write_busy = write_busy_reg;
+
+reg [RAM_DEPTH-1:0] match_raw_out[SLICE_COUNT-1:0];
+reg [RAM_DEPTH-1:0] match_many_raw;
+
+assign match_many = match_many_raw;
+
+reg [DATA_WIDTH-1:0] erase_ram [RAM_DEPTH-1:0];
+reg [DATA_WIDTH-1:0] erase_data = {DATA_WIDTH{1'b0}};
+reg erase_ram_wr_en;
+
+integer i;
+
+initial begin
+ for (i = 0; i < RAM_DEPTH; i = i + 1) begin
+ erase_ram[i] = {SLICE_COUNT*SLICE_WIDTH{1'b0}};
+ end
+end
+
+integer k;
+
+always @* begin
+ match_many_raw = {RAM_DEPTH{1'b1}};
+ for (k = 0; k < SLICE_COUNT; k = k + 1) begin
+ match_many_raw = match_many_raw & match_raw_out[k];
+ end
+end
+
+cam_priority_encoder #(
+ .WIDTH(RAM_DEPTH),
+ .LSB_PRIORITY("HIGH")
+)
+priority_encoder_inst (
+ .input_unencoded(match_many_raw),
+ .output_valid(match),
+ .output_encoded(match_addr),
+ .output_unencoded(match_single)
+);
+
+// BRAMs
+genvar slice_ind;
+generate
+ for (slice_ind = 0; slice_ind < SLICE_COUNT; slice_ind = slice_ind + 1) begin : slice
+ localparam W = slice_ind == SLICE_COUNT-1 ? DATA_WIDTH-SLICE_WIDTH*slice_ind : SLICE_WIDTH;
+
+ wire [RAM_DEPTH-1:0] match_data;
+ wire [RAM_DEPTH-1:0] ram_data;
+
+ ram_2port #(
+ .DWIDTH(RAM_DEPTH),
+ .AWIDTH(W)
+ )
+ ram_inst
+ (
+ .clka(clk),
+ .ena(1'b1),
+ .wea(1'b0),
+ .addra(compare_data[SLICE_WIDTH * slice_ind +: W]),
+ .dia({RAM_DEPTH{1'b0}}),
+ .doa(match_data),
+ .clkb(clk),
+ .enb(1'b1),
+ .web(wr_en),
+ .addrb(ram_addr[SLICE_WIDTH * slice_ind +: W]),
+ .dib((ram_data & ~clear_bit) | set_bit),
+ .dob(ram_data)
+ );
+
+ always @* begin
+ match_raw_out[slice_ind] <= match_data;
+ end
+ end
+endgenerate
+
+// erase
+always @(posedge clk) begin
+ erase_data <= erase_ram[write_addr_next];
+ if (erase_ram_wr_en) begin
+ erase_data <= write_data_padded_reg;
+ erase_ram[write_addr_next] <= write_data_padded_reg;
+ end
+end
+
+// write
+always @* begin
+ state_next = STATE_IDLE;
+
+ count_next = count_reg;
+ ram_addr = erase_data;
+ set_bit = {RAM_DEPTH{1'b0}};
+ clear_bit = {RAM_DEPTH{1'b0}};
+ wr_en = 1'b0;
+
+ erase_ram_wr_en = 1'b0;
+
+ write_addr_next = write_addr_reg;
+ write_data_padded_next = write_data_padded_reg;
+ write_delete_next = write_delete_reg;
+
+ case (state_reg)
+ STATE_INIT: begin
+ // zero out RAMs
+ ram_addr = {SLICE_COUNT{count_reg}} & {{SLICE_COUNT*SLICE_WIDTH-DATA_WIDTH{1'b0}}, {DATA_WIDTH{1'b1}}};
+ set_bit = {RAM_DEPTH{1'b0}};
+ clear_bit = {RAM_DEPTH{1'b1}};
+ wr_en = 1'b1;
+
+ if (count_reg == 0) begin
+ state_next = STATE_IDLE;
+ end else begin
+ count_next = count_reg - 1;
+ state_next = STATE_INIT;
+ end
+ end
+ STATE_IDLE: begin
+ // idle state
+ write_addr_next = write_addr;
+ write_data_padded_next = write_data_padded;
+ write_delete_next = write_delete;
+
+ if (write_enable) begin
+ // wait for read from erase_ram
+ state_next = STATE_DELETE_1;
+ end else begin
+ state_next = STATE_IDLE;
+ end
+ end
+ STATE_DELETE_1: begin
+ // wait for read
+ state_next = STATE_DELETE_2;
+ end
+ STATE_DELETE_2: begin
+ // clear bit and write back
+ clear_bit = 1'b1 << write_addr;
+ wr_en = 1'b1;
+ if (write_delete_reg) begin
+ state_next = STATE_IDLE;
+ end else begin
+ erase_ram_wr_en = 1'b1;
+ state_next = STATE_WRITE_1;
+ end
+ end
+ STATE_WRITE_1: begin
+ // wait for read
+ state_next = STATE_WRITE_2;
+ end
+ STATE_WRITE_2: begin
+ // set bit and write back
+ set_bit = 1'b1 << write_addr;
+ wr_en = 1'b1;
+ state_next = STATE_IDLE;
+ end
+ endcase
+end
+
+always @(posedge clk) begin
+ if (rst) begin
+ state_reg <= STATE_INIT;
+ count_reg <= {SLICE_WIDTH{1'b1}};
+ write_busy_reg <= 1'b1;
+ end else begin
+ state_reg <= state_next;
+ count_reg <= count_next;
+ write_busy_reg <= state_next != STATE_IDLE;
+ end
+
+ write_addr_reg <= write_addr_next;
+ write_data_padded_reg <= write_data_padded_next;
+ write_delete_reg <= write_delete_next;
+end
+
+endmodule
diff --git a/fpga/usrp3/lib/control/map/cam_priority_encoder.v b/fpga/usrp3/lib/control/map/cam_priority_encoder.v
new file mode 100644
index 000000000..5125134f6
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/cam_priority_encoder.v
@@ -0,0 +1,94 @@
+/*
+
+Copyright (c) 2014-2016 Alex Forencich
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+
+*/
+
+// Language: Verilog 2001
+
+`timescale 1ns / 1ps
+
+/*
+ * Priority encoder module
+ */
+module cam_priority_encoder #
+(
+ parameter WIDTH = 4,
+ // LSB priority: "LOW", "HIGH"
+ parameter LSB_PRIORITY = "LOW"
+)
+(
+ input wire [WIDTH-1:0] input_unencoded,
+ output wire output_valid,
+ output wire [$clog2(WIDTH)-1:0] output_encoded,
+ output wire [WIDTH-1:0] output_unencoded
+);
+
+// power-of-two width
+parameter W1 = 2**$clog2(WIDTH);
+parameter W2 = W1/2;
+
+generate
+ if (WIDTH == 2) begin
+ // two inputs - just an OR gate
+ assign output_valid = |input_unencoded;
+ if (LSB_PRIORITY == "LOW") begin
+ assign output_encoded = input_unencoded[1];
+ end else begin
+ assign output_encoded = ~input_unencoded[0];
+ end
+ end else begin
+ // more than two inputs - split into two parts and recurse
+ // also pad input to correct power-of-two width
+ wire [$clog2(W2)-1:0] out1, out2;
+ wire valid1, valid2;
+ cam_priority_encoder #(
+ .WIDTH(W2),
+ .LSB_PRIORITY(LSB_PRIORITY)
+ )
+ priority_encoder_inst1 (
+ .input_unencoded(input_unencoded[W2-1:0]),
+ .output_valid(valid1),
+ .output_encoded(out1)
+ );
+ cam_priority_encoder #(
+ .WIDTH(W2),
+ .LSB_PRIORITY(LSB_PRIORITY)
+ )
+ priority_encoder_inst2 (
+ .input_unencoded({{W1-WIDTH{1'b0}}, input_unencoded[WIDTH-1:W2]}),
+ .output_valid(valid2),
+ .output_encoded(out2)
+ );
+ // multiplexer to select part
+ assign output_valid = valid1 | valid2;
+ if (LSB_PRIORITY == "LOW") begin
+ assign output_encoded = valid2 ? {1'b1, out2} : {1'b0, out1};
+ end else begin
+ assign output_encoded = valid1 ? {1'b0, out1} : {1'b1, out2};
+ end
+ end
+endgenerate
+
+// unencoded output
+assign output_unencoded = 1 << output_encoded;
+
+endmodule
diff --git a/fpga/usrp3/lib/control/map/cam_srl.v b/fpga/usrp3/lib/control/map/cam_srl.v
new file mode 100644
index 000000000..6bc4146b0
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/cam_srl.v
@@ -0,0 +1,223 @@
+/*
+
+Copyright (c) 2015-2016 Alex Forencich
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+
+*/
+
+// Language: Verilog 2001
+
+`timescale 1ns / 1ps
+
+/*
+ * Content Addressable Memory (shift register based)
+ */
+module cam_srl #(
+ // search data bus width
+ parameter DATA_WIDTH = 64,
+ // memory size in log2(words)
+ parameter ADDR_WIDTH = 5,
+ // width of data bus slices (4 for SRL16, 5 for SRL32)
+ parameter SLICE_WIDTH = 4
+)
+(
+ input wire clk,
+ input wire rst,
+
+ input wire [ADDR_WIDTH-1:0] write_addr,
+ input wire [DATA_WIDTH-1:0] write_data,
+ input wire write_delete,
+ input wire write_enable,
+ output wire write_busy,
+
+ input wire [DATA_WIDTH-1:0] compare_data,
+ output wire [2**ADDR_WIDTH-1:0] match_many,
+ output wire [2**ADDR_WIDTH-1:0] match_single,
+ output wire [ADDR_WIDTH-1:0] match_addr,
+ output wire match
+);
+
+// total number of slices (enough to cover DATA_WIDTH with address inputs)
+localparam SLICE_COUNT = (DATA_WIDTH + SLICE_WIDTH - 1) / SLICE_WIDTH;
+// depth of RAMs
+localparam RAM_DEPTH = 2**ADDR_WIDTH;
+
+localparam [1:0]
+ STATE_INIT = 2'd0,
+ STATE_IDLE = 2'd1,
+ STATE_WRITE = 2'd2,
+ STATE_DELETE = 2'd3;
+
+reg [1:0] state_reg = STATE_INIT, state_next;
+
+wire [SLICE_COUNT*SLICE_WIDTH-1:0] compare_data_padded = {{SLICE_COUNT*SLICE_WIDTH-DATA_WIDTH{1'b0}}, compare_data};
+wire [SLICE_COUNT*SLICE_WIDTH-1:0] write_data_padded = {{SLICE_COUNT*SLICE_WIDTH-DATA_WIDTH{1'b0}}, write_data};
+
+reg [SLICE_WIDTH-1:0] count_reg = {SLICE_WIDTH{1'b1}}, count_next;
+
+reg [SLICE_COUNT-1:0] shift_data;
+reg [RAM_DEPTH-1:0] shift_en;
+
+reg [ADDR_WIDTH-1:0] write_addr_reg = {ADDR_WIDTH{1'b0}}, write_addr_next;
+reg [SLICE_COUNT*SLICE_WIDTH-1:0] write_data_padded_reg = {SLICE_COUNT*SLICE_WIDTH{1'b0}}, write_data_padded_next;
+
+reg write_busy_reg = 1'b1;
+
+assign write_busy = write_busy_reg;
+
+reg [RAM_DEPTH-1:0] match_raw_out[SLICE_COUNT-1:0];
+reg [RAM_DEPTH-1:0] match_many_raw;
+reg [RAM_DEPTH-1:0] match_many_reg = {RAM_DEPTH{1'b0}};
+
+assign match_many = match_many_reg;
+
+integer k;
+
+always @* begin
+ match_many_raw = ~shift_en;
+ for (k = 0; k < SLICE_COUNT; k = k + 1) begin
+ match_many_raw = match_many_raw & match_raw_out[k];
+ end
+end
+
+cam_priority_encoder #(
+ .WIDTH(RAM_DEPTH),
+ .LSB_PRIORITY("HIGH")
+)
+priority_encoder_inst (
+ .input_unencoded(match_many_reg),
+ .output_valid(match),
+ .output_encoded(match_addr),
+ .output_unencoded(match_single)
+);
+
+integer i;
+
+// SRLs
+genvar row_ind, slice_ind;
+generate
+ for (row_ind = 0; row_ind < RAM_DEPTH; row_ind = row_ind + 1) begin : row
+ for (slice_ind = 0; slice_ind < SLICE_COUNT; slice_ind = slice_ind + 1) begin : slice
+ reg [2**SLICE_WIDTH-1:0] srl_mem = {2**SLICE_WIDTH{1'b0}};
+
+ // match
+ always @* begin
+ match_raw_out[slice_ind][row_ind] = srl_mem[compare_data_padded[SLICE_WIDTH * slice_ind +: SLICE_WIDTH]];
+ end
+
+ // write
+ always @(posedge clk) begin
+ if (shift_en[row_ind]) begin
+ srl_mem <= {srl_mem[2**SLICE_WIDTH-2:0], shift_data[slice_ind]};
+ end
+ end
+ end
+ end
+endgenerate
+
+// match
+always @(posedge clk) begin
+ match_many_reg <= match_many_raw;
+end
+
+// write
+always @* begin
+ state_next = STATE_IDLE;
+
+ count_next = count_reg;
+ shift_data = {SLICE_COUNT{1'b0}};
+ shift_en = {RAM_DEPTH{1'b0}};
+
+ write_addr_next = write_addr_reg;
+ write_data_padded_next = write_data_padded_reg;
+
+ case (state_reg)
+ STATE_INIT: begin
+ // zero out shift registers
+ shift_en = {RAM_DEPTH{1'b1}};
+ shift_data = {SLICE_COUNT{1'b0}};
+
+ if (count_reg == 0) begin
+ state_next = STATE_IDLE;
+ end else begin
+ count_next = count_reg - 1;
+ state_next = STATE_INIT;
+ end
+ end
+ STATE_IDLE: begin
+ if (write_enable) begin
+ write_addr_next = write_addr;
+ write_data_padded_next = write_data_padded;
+ count_next = {SLICE_WIDTH{1'b1}};
+ if (write_delete) begin
+ state_next = STATE_DELETE;
+ end else begin
+ state_next = STATE_WRITE;
+ end
+ end else begin
+ state_next = STATE_IDLE;
+ end
+ end
+ STATE_WRITE: begin
+ // write entry
+ shift_en = 1'b1 << write_addr;
+
+ for (i = 0; i < SLICE_COUNT; i = i + 1) begin
+ shift_data[i] = count_reg == write_data_padded_reg[SLICE_WIDTH * i +: SLICE_WIDTH];
+ end
+
+ if (count_reg == 0) begin
+ state_next = STATE_IDLE;
+ end else begin
+ count_next = count_reg - 1;
+ state_next = STATE_WRITE;
+ end
+ end
+ STATE_DELETE: begin
+ // delete entry
+ shift_en = 1'b1 << write_addr;
+ shift_data = {SLICE_COUNT{1'b0}};
+
+ if (count_reg == 0) begin
+ state_next = STATE_IDLE;
+ end else begin
+ count_next = count_reg - 1;
+ state_next = STATE_DELETE;
+ end
+ end
+ endcase
+end
+
+always @(posedge clk) begin
+ if (rst) begin
+ state_reg <= STATE_INIT;
+ count_reg <= {SLICE_WIDTH{1'b1}};
+ write_busy_reg <= 1'b1;
+ end else begin
+ state_reg <= state_next;
+ count_reg <= count_next;
+ write_busy_reg <= state_next != STATE_IDLE;
+ end
+
+ write_addr_reg <= write_addr_next;
+ write_data_padded_reg <= write_data_padded_next;
+end
+
+endmodule
diff --git a/fpga/usrp3/lib/control/map/kv_map.v b/fpga/usrp3/lib/control/map/kv_map.v
new file mode 100644
index 000000000..dfb0bca43
--- /dev/null
+++ b/fpga/usrp3/lib/control/map/kv_map.v
@@ -0,0 +1,253 @@
+//
+// Copyright 2018 Ettus Research, A National Instruments Company
+//
+// SPDX-License-Identifier: LGPL-3.0-or-later
+//
+// Module: kv_map
+
+module kv_map #(
+ parameter KEY_WIDTH = 16,
+ parameter VAL_WIDTH = 32,
+ parameter SIZE = 6
+) (
+ // Clock and reset
+ input wire clk,
+ input wire reset,
+ // Insert port
+ input wire insert_stb,
+ input wire [KEY_WIDTH-1:0] insert_key,
+ input wire [VAL_WIDTH-1:0] insert_val,
+ output wire insert_busy,
+ // Find port
+ input wire find_key_stb,
+ input wire [KEY_WIDTH-1:0] find_key,
+ output wire find_res_stb,
+ output wire find_res_match,
+ output wire [VAL_WIDTH-1:0] find_res_val,
+ // Count
+ output reg [SIZE-1:0] count = {SIZE{1'b0}}
+);
+
+ //-------------------------------------------------
+ // Instantiate a CAM and a RAM
+ //-------------------------------------------------
+ // The CAM serves as a "set" and the RAM serves as a
+ // random addressable "array". Using thse two data structures
+ // we can build a map. The role of the CAM is to compress
+ // the key to an address that can be used to lookup data
+ // stored in the RAM
+
+ wire cam_wr_en, cam_wr_busy, cam_rd_match;
+ wire [SIZE-1:0] cam_wr_addr, cam_rd_addr;
+ wire [KEY_WIDTH-1:0] cam_wr_data, cam_rd_key;
+
+ wire ram_wr_en;
+ wire [SIZE-1:0] ram_wr_addr;
+ reg [SIZE-1:0] ram_rd_addr;
+ wire [VAL_WIDTH-1:0] ram_wr_data, ram_rd_data;
+
+ cam #(
+ .DATA_WIDTH (KEY_WIDTH),
+ .ADDR_WIDTH (SIZE),
+ .CAM_STYLE (SIZE > 8 ? "BRAM" : "SRL"),
+ .SLICE_WIDTH (SIZE > 8 ? 9 : 5)
+ ) cam_i (
+ .clk (clk),
+ .rst (reset),
+ .write_addr (cam_wr_addr),
+ .write_data (cam_wr_data),
+ .write_delete(1'b0),
+ .write_enable(cam_wr_en),
+ .write_busy (cam_wr_busy),
+ .compare_data(cam_rd_key),
+ .match_addr (cam_rd_addr),
+ .match (cam_rd_match),
+ .match_many (),
+ .match_single()
+ );
+
+ ram_2port #(
+ .DWIDTH(VAL_WIDTH),
+ .AWIDTH(SIZE)
+ ) mem_i (
+ .clka (clk),
+ .ena (ram_wr_en),
+ .wea (1'b1),
+ .addra (ram_wr_addr),
+ .dia (ram_wr_data),
+ .doa (/* Write port only */),
+ .clkb (clk),
+ .enb (1'b1),
+ .web (1'b0),
+ .addrb (ram_rd_addr),
+ .dib (/* Read port only */),
+ .dob (ram_rd_data)
+ );
+
+ // Pipeline read address into RAM
+ always @(posedge clk)
+ ram_rd_addr <= cam_rd_addr;
+
+ //-------------------------------------------------
+ // Find state machine
+ //-------------------------------------------------
+ // The lookup process has three cycles of latency
+ // - CAM lookup has a 1 cycle latency
+ // - The lookup address into the RAM is delayed by 1 cycle for timing
+ // - The RAM takes 1 cycle to produce data
+
+ localparam FIND_CYC = 3;
+
+ reg [FIND_CYC-1:0] find_key_stb_shreg = {FIND_CYC{1'b0}};
+ reg [FIND_CYC-2:0] find_match_shreg = {(FIND_CYC-1){1'b0}};
+ reg find_pending = 1'b0;
+
+ wire find_busy = find_pending | find_key_stb;
+
+ // Delay the find valid signal to account for the latency
+ // of the CAM and RAM
+ always @(posedge clk) begin
+ find_key_stb_shreg <= reset ? {FIND_CYC{1'b0}} :
+ {find_key_stb_shreg[FIND_CYC-2:0], find_key_stb};
+ end
+ assign find_res_stb = find_key_stb_shreg[FIND_CYC-1];
+
+ // Latch the find signal to compute pending
+ always @(posedge clk) begin
+ if (find_key_stb)
+ find_pending <= 1'b1;
+ else if (find_pending)
+ find_pending <= ~find_res_stb;
+ end
+
+ // Delay the match signal to account for the latency of the RAM
+ always @(posedge clk) begin
+ find_match_shreg <= reset ? {(FIND_CYC-1){1'b0}} :
+ {find_match_shreg[FIND_CYC-3:0], cam_rd_match};
+ end
+ assign find_res_match = find_match_shreg[FIND_CYC-2];
+
+
+ //-------------------------------------------------
+ // Insert state machine
+ //-------------------------------------------------
+
+ localparam [2:0] ST_IDLE = 3'd0;
+ localparam [2:0] ST_WAIT_FIND = 3'd1;
+ localparam [2:0] ST_CAM_READ = 3'd2;
+ localparam [2:0] ST_CAM_CHECK_MATCH = 3'd3;
+ localparam [2:0] ST_CAM_RAM_WRITE = 3'd4;
+ localparam [2:0] ST_CAM_WRITE_WAIT = 3'd5;
+ localparam [2:0] ST_RAM_WRITE = 3'd6;
+
+ reg [2:0] ins_state = ST_IDLE;
+
+ reg [KEY_WIDTH-1:0] ins_key_cached;
+ reg [VAL_WIDTH-1:0] ins_val_cached;
+ reg [SIZE-1:0] write_addr = {SIZE{1'b0}};
+ reg [SIZE-1:0] next_addr = {SIZE{1'b0}};
+
+
+ always @(posedge clk) begin
+ if (reset) begin
+ ins_state <= ST_IDLE;
+ next_addr <= {SIZE{1'b0}};
+ end else begin
+ case (ins_state)
+
+ // Idle and waiting for an insert transaction
+ //
+ ST_IDLE: begin
+ // Cache insertion parameters
+ if (insert_stb) begin
+ ins_key_cached <= insert_key;
+ ins_val_cached <= insert_val;
+ // Wait for find to finish
+ ins_state <= find_busy ? ST_WAIT_FIND : ST_CAM_READ;
+ end
+ end
+
+ // Wait for a find transaction to finish
+ //
+ ST_WAIT_FIND: begin
+ // Wait for find to finish
+ if (~find_busy)
+ ins_state <= ST_CAM_READ;
+ end
+
+ // Read the CAM to check if the key to insert already exists
+ //
+ ST_CAM_READ: begin
+ // Ensure that find always has priority
+ if (~find_key_stb)
+ ins_state <= ST_CAM_CHECK_MATCH;
+ end
+
+ // Look at the CAM match signal to evaluate if we skip writing the CAM
+ //
+ ST_CAM_CHECK_MATCH: begin
+ // If the CAM already has this key, then overwrite it
+ if (cam_rd_match) begin
+ ins_state <= ST_RAM_WRITE;
+ write_addr <= cam_rd_addr;
+ end else if (~cam_wr_busy) begin
+ ins_state <= ST_CAM_RAM_WRITE;
+ write_addr <= next_addr;
+ next_addr <= next_addr + 1'b1;
+ end
+ end
+
+ // Write the specified key to the CAM and value to the RAM
+ //
+ ST_CAM_RAM_WRITE: begin
+ ins_state <= ST_CAM_WRITE_WAIT;
+ end
+
+ // Wait for CAM write to finish
+ //
+ ST_CAM_WRITE_WAIT: begin
+ if (~cam_wr_busy) begin
+ ins_state <= ST_IDLE;
+ count <= next_addr;
+ end
+ end
+
+ // Write the specified value to the RAM
+ //
+ ST_RAM_WRITE: begin
+ ins_state <= ST_IDLE;
+ count <= next_addr;
+ end
+
+ default: begin
+ // We should not get here
+ ins_state <= ST_IDLE;
+ end
+ endcase
+ end
+ end
+
+ // CAM Read Port:
+ // - Find has priority so it can interrupt an insert
+ assign cam_rd_key =
+ (ins_state != ST_CAM_READ || find_key_stb) ? find_key : ins_key_cached;
+
+ // RAM Write Port:
+ // - The RAM write enable is held high for 1 cycle
+ // - The address may come from a CAM lookup or could generated
+ assign ram_wr_en = (ins_state == ST_RAM_WRITE || ins_state == ST_CAM_RAM_WRITE);
+ assign ram_wr_addr = write_addr;
+ assign ram_wr_data = ins_val_cached;
+
+ // CAM Write Port:
+ // - The CAM write enable is held high for 1 cycle
+ // - The address may come from a CAM lookup or could generated (same as RAM)
+ assign cam_wr_en = (ins_state == ST_CAM_RAM_WRITE);
+ assign cam_wr_addr = write_addr;
+ assign cam_wr_data = ins_key_cached;
+
+ // Outputs
+ assign insert_busy = (ins_state != ST_IDLE);
+ assign find_res_val = ram_rd_data;
+
+endmodule
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-08 00:03:08 +0000