control/map/kv_map.v

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