The MAC Table — CAM, Hashing, Capacity and Aging

// -----------------------------------------------------------------------
// mactable_pkg -- shared types for the forwarding table.
// -----------------------------------------------------------------------
package mactable_pkg;

  localparam int ADDR_W = 48;

  // What an insert did. Chapter 12.2 Section 6 named the first four; this
  // chapter adds the two that only a hashed structure can produce.
  typedef enum logic [2:0] {
    TI_INSERT     = 3'd0,  // new key, free way in its set
    TI_REFRESH    = 3'd1,  // same key, same port -- age reset
    TI_MOVE       = 3'd2,  // same key, different port
    TI_EVICT      = 3'd3,  // new key, set full -- something was displaced
    TI_SET_FULL   = 3'd4,  // new key, set full, eviction NOT permitted
    TI_NONE       = 3'd5
  } table_insert_e;

  // An entry. Chapter 12.2 Section 6 established the five fields; the
  // hashed structure adds nothing, because the hash is recomputed rather
  // than stored.
  typedef struct packed {
    logic                valid;
    logic [ADDR_W-1:0]   key;      // the FULL address -- a hash is not
                                   // reversible, so the tag is 48 bits
    logic [4:0]          port;
    logic [8:0]          age;      // 300 s at a 1 s tick
    logic                stat;     // operator-asserted, never ages
  } tentry_t;

endpackage

// -----------------------------------------------------------------------
// cam_lookup_model -- a binary content-addressable memory.
//
// BEHAVIOURAL. A real CAM is a custom cell array, not a synthesized
// comparator tree, and this module exists to make the COST structure
// explicit rather than to be built. Every entry compares in parallel; the
// answer is available in one compare plus one priority encode.
// -----------------------------------------------------------------------
module cam_lookup_model
  import mactable_pkg::*;
#(
  parameter int N_ENTRIES = 8192,
  parameter int IDX_W     = 13,
  parameter int CNT_W     = 32
)(
  input  logic                 clk,
  input  logic                 rst_n,

  input  logic                 search_valid,
  input  logic [ADDR_W-1:0]    search_key,

  input  logic                 write_valid,
  input  logic [IDX_W-1:0]     write_index,
  input  tentry_t              write_entry,

  output logic                 hit,
  output logic [IDX_W-1:0]     hit_index,
  output tentry_t              hit_entry,
  output logic                 multi_hit,      // the same key stored twice

  // Cost accounting -- the reason this module is in the chapter.
  output logic [CNT_W-1:0]     c_searches,
  output logic [CNT_W-1:0]     c_match_line_toggles,
  output logic [31:0]          compare_bits_per_search
);

  tentry_t mem [N_ENTRIES];

  logic [N_ENTRIES-1:0] match;

  // THE DEFINING PROPERTY. Every entry compares against the key, every
  // search, in one cycle. That is what buys the latency and what costs
  // the power: N_ENTRIES x ADDR_W comparison bits toggle per search,
  // whether or not any of them match.
  always_comb begin
    for (int i = 0; i < N_ENTRIES; i++)
      match[i] = mem[i].valid && (mem[i].key == search_key);
  end

  // Priority encode. A well-formed table has at most one match; multi_hit
  // means the same key was inserted twice, which a CAM does not prevent.
  always_comb begin
    hit       = 1'b0;
    hit_index = '0;
    hit_entry = '0;
    multi_hit = 1'b0;
    if (search_valid) begin
      hit       = |match;
      multi_hit = ($countones(match) > 1);
      for (int i = N_ENTRIES-1; i >= 0; i--)
        if (match[i]) begin
          hit_index = IDX_W'(i);
          hit_entry = mem[i];
        end
    end
  end

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      for (int i = 0; i < N_ENTRIES; i++) mem[i] <= '0;
      c_searches           <= '0;
      c_match_line_toggles <= '0;
    end else begin
      if (write_valid) mem[write_index] <= write_entry;
      if (search_valid) begin
        c_searches <= c_searches + 1'b1;
        // Every match line is evaluated on every search. This counter is
        // a proxy for the dynamic power a hashed structure avoids.
        c_match_line_toggles <= c_match_line_toggles + CNT_W'(N_ENTRIES);
      end
    end
  end

  assign compare_bits_per_search = 32'(N_ENTRIES) * 32'(ADDR_W);

endmodule

// -----------------------------------------------------------------------
// address_hash -- 48 bits to an index, plus the quality instrumentation
// that says whether it is spreading.
//
// The requirement is unusual: the input is NOT uniformly distributed. A
// MAC address is a 24-bit OUI followed by a 24-bit serial (Chapter 5.3),
// and a rack of identical machines shares the OUI and often has serials
// that differ in a handful of low bits. A hash that ignores the low bits,
// or that is dominated by the OUI, clusters catastrophically.
// -----------------------------------------------------------------------
module address_hash
  import mactable_pkg::*;
#(
  parameter int IDX_W = 11,            // 2048 sets
  parameter int CNT_W = 32
)(
  input  logic              clk,
  input  logic              rst_n,

  input  logic              key_valid,
  input  logic [ADDR_W-1:0] key,

  output logic [IDX_W-1:0]  index,

  // Quality instrumentation. A hash cannot be judged by inspection; it
  // has to be measured against the addresses actually present.
  input  logic              sample_enable,
  output logic [CNT_W-1:0]  c_hashed,
  output logic [IDX_W-1:0]  observed_min_index,
  output logic [IDX_W-1:0]  observed_max_index,
  output logic              low_bits_only        // index ignores the OUI
);

  // A CRC-derived fold. The low 24 bits (the vendor's serial) carry the
  // entropy; the top 24 (the OUI) are near-constant across a rack, so the
  // hash must not be dominated by them -- but it must not IGNORE them
  // either, or two vendors' identical serials collide.
  logic [IDX_W-1:0] h;

  always_comb begin
    automatic logic [23:0] lo = key[23:0];
    automatic logic [23:0] hi = key[47:24];
    automatic logic [23:0] mix;
    // Fold the OUI into the serial with a rotate, so that neither half
    // can dominate and identical serials from different vendors separate.
    mix = lo ^ {hi[11:0], hi[23:12]} ^ {lo[7:0], lo[23:8]};
    h   = mix[IDX_W-1:0] ^ mix[23:24-IDX_W];
  end

  assign index = h;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      c_hashed           <= '0;
      observed_min_index <= '1;
      observed_max_index <= '0;
      low_bits_only      <= 1'b0;
    end else if (key_valid && sample_enable) begin
      c_hashed <= c_hashed + 1'b1;
      if (h < observed_min_index) observed_min_index <= h;
      if (h > observed_max_index) observed_max_index <= h;
      // A cheap standing check: if the index never depends on the OUI,
      // an entire rack of one vendor's machines lands in a narrow band.
      if (h == key[IDX_W-1:0]) low_bits_only <= 1'b1;
    end
  end

endmodule

// -----------------------------------------------------------------------
// hashed_set_table -- W-way set-associative forwarding table.
//
// THE CENTRAL STRUCTURE OF THIS CHAPTER. The key hashes to exactly one
// set; the set is read in one access; the ways are compared in parallel.
// A key that is not in its set is not in the table -- the hash is
// deterministic, so a miss here is a real miss and not a partial search.
// -----------------------------------------------------------------------
module hashed_set_table
  import mactable_pkg::*;
#(
  parameter int N_SETS   = 2048,
  parameter int WAYS     = 4,
  parameter int IDX_W    = 11,
  parameter int WAY_W    = 2,
  parameter int PORT_W   = 5,
  parameter int AGE_W    = 9,
  parameter int CNT_W    = 32
)(
  input  logic                 clk,
  input  logic                 rst_n,

  // ---- Lookup -------------------------------------------------------
  input  logic                 lk_valid,
  input  logic [IDX_W-1:0]     lk_index,        // from address_hash
  input  logic [ADDR_W-1:0]    lk_key,
  output logic                 lk_hit,
  output logic [PORT_W-1:0]    lk_port,
  output logic [WAY_W-1:0]     lk_way,

  // ---- Insert / refresh / move --------------------------------------
  input  logic                 ins_valid,
  input  logic [IDX_W-1:0]     ins_index,
  input  logic [ADDR_W-1:0]    ins_key,
  input  logic [PORT_W-1:0]    ins_port,
  input  logic                 evict_permitted,
  input  logic [WAY_W-1:0]     evict_way,       // from set_eviction_selector
  output table_insert_e        ins_result,
  output logic [PORT_W-1:0]    displaced_port,
  output logic [ADDR_W-1:0]    displaced_key,

  // ---- Age ----------------------------------------------------------
  input  logic                 age_write,
  input  logic [IDX_W-1:0]     age_index,
  input  logic [WAY_W-1:0]     age_way,
  input  logic                 age_expire,
  input  logic [AGE_W-1:0]     age_next,
  output tentry_t              age_read_entry,

  // ---- Observability -------------------------------------------------
  output logic [3:0]           set_occupancy,   // ways used in the last set read
  output logic                 set_was_full,
  output logic [CNT_W-1:0]     occupancy,
  output logic [CNT_W-1:0]     c_set_full_refusals
);

  // The array. One read port serving lookup, insert and the ageing sweep;
  // Section 2 showed the combined demand is 14.3% of a 500 MHz memory, so
  // one port suffices and the arbitration is trivial.
  tentry_t mem [N_SETS][WAYS];

  // ---- Lookup: read the set, compare the ways ------------------------
  logic [WAYS-1:0] way_match;
  logic [3:0]      used_ways;

  always_comb begin
    way_match = '0;
    used_ways = '0;
    for (int w = 0; w < WAYS; w++) begin
      if (mem[lk_index][w].valid) begin
        used_ways = used_ways + 4'd1;
        // THE COMPARE IS AGAINST THE FULL 48-BIT KEY. A hash is not
        // reversible, so the index does not narrow the stored key at all
        // -- unlike a cache tag, nothing may be omitted.
        if (mem[lk_index][w].key == lk_key) way_match[w] = 1'b1;
      end
    end
  end

  always_comb begin
    lk_hit  = 1'b0;
    lk_port = '0;
    lk_way  = '0;
    if (lk_valid) begin
      lk_hit = |way_match;
      for (int w = WAYS-1; w >= 0; w--)
        if (way_match[w]) begin
          lk_port = mem[lk_index][w].port;
          lk_way  = WAY_W'(w);
        end
    end
  end

  assign set_occupancy = used_ways;
  assign set_was_full  = (used_ways == 4'(WAYS));

  // ---- Insert --------------------------------------------------------
  logic [WAYS-1:0] ins_match, ins_free;

  always_comb begin
    ins_match = '0;
    ins_free  = '0;
    for (int w = 0; w < WAYS; w++) begin
      if (mem[ins_index][w].valid) begin
        if (mem[ins_index][w].key == ins_key) ins_match[w] = 1'b1;
      end else begin
        ins_free[w] = 1'b1;
      end
    end
  end

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      for (int s = 0; s < N_SETS; s++)
        for (int w = 0; w < WAYS; w++) mem[s][w] <= '0;
      ins_result          <= TI_NONE;
      displaced_port      <= '0;
      displaced_key       <= '0;
      occupancy           <= '0;
      c_set_full_refusals <= '0;
    end else begin
      ins_result <= TI_NONE;

      if (ins_valid) begin
        automatic int hw = -1;
        automatic int fw = -1;
        for (int w = 0; w < WAYS; w++) begin
          if (ins_match[w]) hw = w;
          if (ins_free[w] && (fw < 0)) fw = w;
        end

        if (hw >= 0) begin
          // The key is present in its set. Refresh or move -- Chapter
          // 12.2 Section 6's distinction, unchanged by the structure.
          if (mem[ins_index][hw].port == ins_port) begin
            mem[ins_index][hw].age <= '0;
            ins_result <= TI_REFRESH;
          end else begin
            displaced_port <= mem[ins_index][hw].port;
            mem[ins_index][hw].port <= ins_port;
            mem[ins_index][hw].age  <= '0;
            ins_result <= TI_MOVE;
          end

        end else if (fw >= 0) begin
          mem[ins_index][fw] <= '{valid: 1'b1, key: ins_key,
                                  port: ins_port, age: '0, stat: 1'b0};
          occupancy  <= occupancy + 1'b1;
          ins_result <= TI_INSERT;

        end else if (evict_permitted) begin
          // THE SET IS FULL AND THE TABLE MAY NOT BE. Something must be
          // displaced, and Section 11 chooses which -- from four
          // candidates the arriving key's hash selected.
          displaced_key  <= mem[ins_index][evict_way].key;
          displaced_port <= mem[ins_index][evict_way].port;
          mem[ins_index][evict_way] <= '{valid: 1'b1, key: ins_key,
                                         port: ins_port, age: '0,
                                         stat: 1'b0};
          ins_result <= TI_EVICT;

        end else begin
          // REFUSE. Chapter 12.2 Section 12 established why refusing beats
          // evicting under attack: invented addresses cannot displace
          // stations that are actually communicating.
          ins_result <= TI_SET_FULL;
          if (!(&c_set_full_refusals))
            c_set_full_refusals <= c_set_full_refusals + 1'b1;
        end
      end

      // ---- Ageing write-back ------------------------------------------
      if (age_write) begin
        if (age_expire) begin
          mem[age_index][age_way].valid <= 1'b0;
          occupancy <= occupancy - 1'b1;
        end else begin
          mem[age_index][age_way].age <= age_next;
        end
      end
    end
  end

  assign age_read_entry = mem[age_index][age_way];

endmodule

// -----------------------------------------------------------------------
// set_occupancy_monitor -- a histogram over set load, and the derived
// quantities that say whether the hash is doing its job.
//
// Total occupancy answers "how full is the table". It cannot answer "can
// the next address be learned", which depends entirely on ONE set chosen
// by that address's hash. Section 9 shows the two diverge sharply.
// -----------------------------------------------------------------------
module set_occupancy_monitor
  import mactable_pkg::*;
#(
  parameter int N_SETS = 2048,
  parameter int WAYS   = 4,
  parameter int IDX_W  = 11,
  parameter int CNT_W  = 32
)(
  input  logic             clk,
  input  logic             rst_n,

  // Sampled from the sweep, which already visits every set once a second.
  input  logic             sample_valid,
  input  logic [IDX_W-1:0] sample_index,
  input  logic [3:0]       sample_used_ways,
  input  logic             sweep_wrapped,

  input  logic [CNT_W-1:0] occupancy,
  input  logic [CNT_W-1:0] set_full_refusals,

  output logic [CNT_W-1:0] sets_with [WAYS+1],   // histogram: 0..WAYS used
  output logic [15:0]      occupancy_pct,
  output logic [15:0]      full_sets_pct,
  output logic [IDX_W-1:0] hottest_set,
  output logic             hash_clustering,      // distribution is skewed
  output logic             refusing_while_empty, // the Section 9 condition
  output logic             histogram_valid
);

  logic [CNT_W-1:0] acc [WAYS+1];
  logic [CNT_W-1:0] acc_full;
  logic [CNT_W-1:0] prev_refusals;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      for (int i = 0; i <= WAYS; i++) begin
        acc[i] <= '0; sets_with[i] <= '0;
      end
      acc_full             <= '0;
      hottest_set          <= '0;
      occupancy_pct        <= '0;
      full_sets_pct        <= '0;
      hash_clustering      <= 1'b0;
      refusing_while_empty <= 1'b0;
      histogram_valid      <= 1'b0;
      prev_refusals        <= '0;
    end else begin
      histogram_valid <= 1'b0;

      if (sample_valid) begin
        acc[sample_used_ways] <= acc[sample_used_ways] + 1'b1;
        if (sample_used_ways == 4'(WAYS)) begin
          acc_full    <= acc_full + 1'b1;
          hottest_set <= sample_index;
        end
      end

      // One full pass of the sweep is one complete census of the table.
      if (sweep_wrapped) begin
        for (int i = 0; i <= WAYS; i++) begin
          sets_with[i] <= acc[i];
          acc[i]       <= '0;
        end

        occupancy_pct <= 16'((occupancy * CNT_W'(100)) /
                             CNT_W'(N_SETS * WAYS));
        full_sets_pct <= 16'((acc_full * CNT_W'(100)) / CNT_W'(N_SETS));

        // THE CONDITION THIS MODULE EXISTS FOR. Inserts are being refused
        // while the table as a whole is far from full -- which is a hash
        // distribution problem and NOT a capacity problem, and the two
        // have entirely different remedies.
        refusing_while_empty <=
          ((set_full_refusals != prev_refusals) &&
           (occupancy < CNT_W'((N_SETS * WAYS * 3) / 4)));

        // Skew: more full sets than a well-spread hash would produce at
        // this occupancy. At 50% occupancy a good hash gives about 5% of
        // sets full; three times that is clustering.
        hash_clustering <= (acc_full > ((CNT_W'(N_SETS) * CNT_W'(15)) / 100)) &&
                           (occupancy < CNT_W'((N_SETS * WAYS) / 2));

        prev_refusals   <= set_full_refusals;
        acc_full        <= '0;
        histogram_valid <= 1'b1;
      end
    end
  end

endmodule

// -----------------------------------------------------------------------
// set_eviction_selector -- picks a way to displace within one set.
//
// READ THE SCOPE CAREFULLY. This selects the best candidate IN THIS SET.
// It cannot select the best candidate in the table, because the other
// 2047 sets are not readable in the cycle budget and are not candidates
// at all. Section 12 and Section 18's rejected property are about the
// gap between those two sentences.
// -----------------------------------------------------------------------
module set_eviction_selector
  import mactable_pkg::*;
#(
  parameter int WAYS   = 4,
  parameter int WAY_W  = 2,
  parameter int AGE_W  = 9,
  parameter int CNT_W  = 32
)(
  input  logic             clk,
  input  logic             rst_n,

  input  logic             sel_valid,
  input  tentry_t          set_ways [WAYS],
  input  logic             attack_suspected,   // Chapter 12.2's rate limiter

  output logic             evict_permitted,
  output logic [WAY_W-1:0] evict_way,
  output logic [AGE_W-1:0] evict_age,
  output logic             all_ways_fresh,     // nothing is a good victim

  output logic [CNT_W-1:0] c_evictions,
  output logic [CNT_W-1:0] c_refusals,
  output logic [CNT_W-1:0] c_fresh_evictions,  // displaced something ACTIVE
  output logic [AGE_W-1:0] youngest_evicted
);

  // Oldest of the four. Static entries are never candidates -- Chapter
  // 12.2 Section 6 established that an operator asserted them, so no
  // automatic mechanism may retract them.
  logic [WAY_W-1:0] oldest_way;
  logic [AGE_W-1:0] oldest_age;
  logic             any_candidate;

  always_comb begin
    oldest_way    = '0;
    oldest_age    = '0;
    any_candidate = 1'b0;
    for (int w = 0; w < WAYS; w++) begin
      if (set_ways[w].valid && !set_ways[w].stat) begin
        if (!any_candidate || (set_ways[w].age > oldest_age)) begin
          oldest_age    = set_ways[w].age;
          oldest_way    = WAY_W'(w);
          any_candidate = 1'b1;
        end
      end
    end
  end

  // "FRESH" means every candidate in this set was refreshed recently, so
  // every one of them belongs to a station that is actively
  // communicating. Evicting here displaces a working conversation.
  localparam int FRESH_AGE = 10;   // seconds

  assign all_ways_fresh = any_candidate && (oldest_age < AGE_W'(FRESH_AGE));

  always_comb begin
    evict_permitted = 1'b0;
    if (sel_valid && any_candidate) begin
      // REFUSE UNDER ATTACK. Chapter 12.2 Section 12 established the
      // asymmetry: refusing lets an attacker prevent new learning;
      // evicting lets them REMOVE stations that are working. The second
      // is strictly worse, so a suspected attack switches the policy.
      if (attack_suspected)              evict_permitted = 1'b0;
      // REFUSE WHEN EVERYTHING IS FRESH. Displacing an active station to
      // admit an unknown one trades a working conversation for a guess.
      else if (all_ways_fresh)           evict_permitted = 1'b0;
      else                               evict_permitted = 1'b1;
    end
  end

  assign evict_way = oldest_way;
  assign evict_age = oldest_age;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      c_evictions       <= '0;
      c_refusals        <= '0;
      c_fresh_evictions <= '0;
      youngest_evicted  <= '1;
    end else if (sel_valid) begin
      if (evict_permitted) begin
        if (!(&c_evictions)) c_evictions <= c_evictions + 1'b1;
        // The age of what we displaced is the honest measure of the
        // eviction's damage. A 250-second-old entry was probably dead
        // anyway; a 3-second-old entry was a live conversation.
        if (oldest_age < youngest_evicted) youngest_evicted <= oldest_age;
        if (oldest_age < AGE_W'(FRESH_AGE))
          if (!(&c_fresh_evictions))
            c_fresh_evictions <= c_fresh_evictions + 1'b1;
      end else begin
        if (!(&c_refusals)) c_refusals <= c_refusals + 1'b1;
      end
    end
  end

endmodule

// -----------------------------------------------------------------------
// age_sweep_engine -- walks the table incrementally, decrementing timers
// and expiring entries, while yielding to lookups and inserts.
//
// The naive implementation ages every entry on every tick, which needs
// 8192 read-modify-writes inside one clock. This one spreads the work
// across the whole interval and is therefore nearly free -- Section 14
// quantifies "nearly".
// -----------------------------------------------------------------------
module age_sweep_engine
  import mactable_pkg::*;
#(
  parameter int N_SETS = 2048,
  parameter int WAYS   = 4,
  parameter int IDX_W  = 11,
  parameter int WAY_W  = 2,
  parameter int AGE_W  = 9,
  parameter int CNT_W  = 32
)(
  input  logic                 clk,
  input  logic                 rst_n,

  input  logic [AGE_W-1:0]     age_limit,       // 300 s, Chapter 12.2
  input  logic                 second_tick,
  input  logic                 mem_grant,       // the memory is ours

  output logic                 mem_request,
  output logic [IDX_W-1:0]     sweep_index,
  output logic [WAY_W-1:0]     sweep_way,
  input  tentry_t              sweep_entry,

  output logic                 age_write,
  output logic                 age_expire,
  output logic [AGE_W-1:0]     age_next,

  output logic                 sweep_wrapped,
  output logic [3:0]           set_used_ways,
  output logic                 sample_valid,
  output logic [CNT_W-1:0]     c_expired,
  output logic [CNT_W-1:0]     c_visited,
  output logic [15:0]          sweep_duty_ppm   // parts per million
);

  logic [IDX_W-1:0] idx_q;
  logic [WAY_W-1:0] way_q;
  logic             pass_active_q;
  logic [3:0]       used_acc;
  logic [CNT_W-1:0] cycles_this_second;
  logic [CNT_W-1:0] busy_this_second;

  // A pass begins on the second tick and runs at whatever rate the memory
  // arbiter allows. It MUST complete within the second, and Section 14
  // shows it completes in 33 microseconds of a 1000 millisecond budget.
  assign mem_request = pass_active_q;
  assign sweep_index = idx_q;
  assign sweep_way   = way_q;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      idx_q            <= '0;
      way_q            <= '0;
      pass_active_q    <= 1'b0;
      used_acc         <= '0;
      age_write        <= 1'b0;
      age_expire       <= 1'b0;
      age_next         <= '0;
      sweep_wrapped    <= 1'b0;
      sample_valid     <= 1'b0;
      set_used_ways    <= '0;
      c_expired        <= '0;
      c_visited        <= '0;
      cycles_this_second <= '0;
      busy_this_second   <= '0;
      sweep_duty_ppm     <= '0;
    end else begin
      age_write     <= 1'b0;
      age_expire    <= 1'b0;
      sweep_wrapped <= 1'b0;
      sample_valid  <= 1'b0;

      cycles_this_second <= cycles_this_second + 1'b1;
      if (pass_active_q) busy_this_second <= busy_this_second + 1'b1;

      if (second_tick) begin
        pass_active_q <= 1'b1;
        idx_q         <= '0;
        way_q         <= '0;
        used_acc      <= '0;
        // Duty in parts per million, so the "ageing is expensive" claim
        // can be checked rather than assumed.
        sweep_duty_ppm <= (cycles_this_second == '0) ? 16'd0
                        : 16'((busy_this_second * CNT_W'(1_000_000)) /
                              cycles_this_second);
        cycles_this_second <= '0;
        busy_this_second   <= '0;
      end

      // ONE ENTRY PER GRANTED CYCLE. The sweep never blocks a lookup or
      // an insert -- both are on the critical path and neither can wait,
      // while the sweep has a whole second.
      if (pass_active_q && mem_grant) begin
        if (!(&c_visited)) c_visited <= c_visited + 1'b1;

        if (sweep_entry.valid) begin
          used_acc <= used_acc + 4'd1;
          if (!sweep_entry.stat) begin
            if (sweep_entry.age >= age_limit) begin
              age_write  <= 1'b1;
              age_expire <= 1'b1;
              if (!(&c_expired)) c_expired <= c_expired + 1'b1;
            end else begin
              age_write <= 1'b1;
              age_next  <= sweep_entry.age + 1'b1;
            end
          end
        end

        // Advance. On the last way of a set, publish the occupancy sample
        // Section 8 consumes -- the census is a by-product of a walk that
        // was happening anyway.
        if (way_q == WAY_W'(WAYS-1)) begin
          set_used_ways <= used_acc + (sweep_entry.valid ? 4'd1 : 4'd0);
          sample_valid  <= 1'b1;
          used_acc      <= '0;
          way_q         <= '0;
          if (idx_q == IDX_W'(N_SETS-1)) begin
            idx_q         <= '0;
            pass_active_q <= 1'b0;
            sweep_wrapped <= 1'b1;
          end else begin
            idx_q <= idx_q + 1'b1;
          end
        end else begin
          way_q <= way_q + 1'b1;
        end
      end
    end
  end

endmodule

// -----------------------------------------------------------------------
// table_capacity_accountant -- what the table is actually holding against
// what it was asked to hold.
//
// The distinction this module exists to preserve: an address that was
// never learned because its SET was full is a different event from one
// never learned because the TABLE was full, and both are different from
// one that aged out. All three end with a station being flooded to.
// -----------------------------------------------------------------------
module table_capacity_accountant
  import mactable_pkg::*;
#(
  parameter int N_SETS = 2048,
  parameter int WAYS   = 4,
  parameter int CNT_W  = 32,
  parameter int WINDOW = 1_000_000
)(
  input  logic             clk,
  input  logic             rst_n,

  input  logic             ins_valid,
  input  table_insert_e    ins_result,
  input  logic             lookup_valid,
  input  logic             lookup_hit,
  input  logic [CNT_W-1:0] occupancy,

  output logic [CNT_W-1:0] c_insert,
  output logic [CNT_W-1:0] c_refresh,
  output logic [CNT_W-1:0] c_move,
  output logic [CNT_W-1:0] c_evict,
  output logic [CNT_W-1:0] c_set_full,

  output logic             window_valid,
  output logic [15:0]      hit_rate_pct,
  output logic [15:0]      occupancy_pct,
  output logic [15:0]      effective_cap_pct,   // stored / distinct offered
  output logic             capacity_bound,      // table genuinely full
  output logic             hash_bound           // sets full, table is not
);

  logic [CNT_W-1:0] win_lk, win_hit, win_distinct;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      c_insert   <= '0; c_refresh <= '0; c_move <= '0;
      c_evict    <= '0; c_set_full <= '0;
      win_lk     <= '0; win_hit <= '0; win_distinct <= '0;
      window_valid      <= 1'b0;
      hit_rate_pct      <= '0;
      occupancy_pct     <= '0;
      effective_cap_pct <= 16'd100;
      capacity_bound    <= 1'b0;
      hash_bound        <= 1'b0;
    end else begin
      window_valid <= 1'b0;

      if (ins_valid) begin
        unique case (ins_result)
          TI_INSERT:   begin c_insert   <= c_insert + 1'b1;
                             win_distinct <= win_distinct + 1'b1; end
          TI_REFRESH:  c_refresh  <= c_refresh + 1'b1;
          TI_MOVE:     c_move     <= c_move + 1'b1;
          TI_EVICT:    begin c_evict <= c_evict + 1'b1;
                             win_distinct <= win_distinct + 1'b1; end
          // A REFUSED address is still a distinct address the table was
          // offered. Counting it is what makes effective capacity
          // measurable rather than theoretical.
          TI_SET_FULL: begin c_set_full <= c_set_full + 1'b1;
                             win_distinct <= win_distinct + 1'b1; end
          default: ;
        endcase
      end

      if (lookup_valid) begin
        win_lk <= win_lk + 1'b1;
        if (lookup_hit) win_hit <= win_hit + 1'b1;
      end

      if (win_lk >= CNT_W'(WINDOW)) begin
        hit_rate_pct  <= 16'((win_hit * CNT_W'(100)) / win_lk);
        occupancy_pct <= 16'((occupancy * CNT_W'(100)) /
                             CNT_W'(N_SETS * WAYS));
        // Stored against distinct offered. On a four-way table offered
        // 8192 distinct addresses this converges near 80.
        effective_cap_pct <= (win_distinct == '0) ? 16'd100
                           : 16'((occupancy * CNT_W'(100)) / win_distinct);

        // THE TWO CONDITIONS THAT LOOK IDENTICAL FROM OUTSIDE. Both
        // produce refusals and flooding; one is fixed by more memory and
        // the other is not.
        capacity_bound <= (occupancy >= CNT_W'((N_SETS * WAYS * 95) / 100));
        hash_bound     <= (c_set_full != '0) &&
                          (occupancy < CNT_W'((N_SETS * WAYS * 3) / 4));

        win_lk <= '0; win_hit <= '0; win_distinct <= '0;
        window_valid <= 1'b1;
      end
    end
  end

endmodule

// -----------------------------------------------------------------------
// table_conformance_monitor -- checks the structure's invariants.
//
// What it CAN check: a key appears at most once; a key is only ever in
// the set its hash names; occupancy matches the valid bits; every
// refusal had a genuinely full set; no static entry ever expired.
//
// What it CANNOT check: that the table contains the addresses it "should"
// -- Chapter 12.2 Section 16 established that the correct contents of a
// forwarding table are not a property of the design.
// -----------------------------------------------------------------------
module table_conformance_monitor
  import mactable_pkg::*;
#(
  parameter int N_SETS = 2048,
  parameter int WAYS   = 4,
  parameter int IDX_W  = 11,
  parameter int WAY_W  = 2,
  parameter int CNT_W  = 32
)(
  input  logic                 clk,
  input  logic                 rst_n,

  // Observed from the sweep, which reads every entry once a second.
  input  logic                 sweep_valid,
  input  logic [IDX_W-1:0]     sweep_index,
  input  logic [WAY_W-1:0]     sweep_way,
  input  tentry_t              sweep_entry,
  input  logic [IDX_W-1:0]     recomputed_index,   // hash of sweep_entry.key
  input  logic                 sweep_wrapped,

  input  logic                 ins_valid,
  input  table_insert_e        ins_result,
  input  logic [3:0]           ins_set_used_ways,
  input  logic                 evict_was_static,
  input  logic                 expire_was_static,

  input  logic [CNT_W-1:0]     occupancy,

  output logic [CNT_W-1:0]     v_wrong_set,        // key not in its hash set
  output logic [CNT_W-1:0]     v_static_evicted,
  output logic [CNT_W-1:0]     v_static_expired,
  output logic [CNT_W-1:0]     v_false_refusal,    // refused a non-full set
  output logic [CNT_W-1:0]     v_occupancy_drift,
  output logic                 conformant
);

  logic [CNT_W-1:0] counted_valid;

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      counted_valid     <= '0;
      v_wrong_set       <= '0;
      v_static_evicted  <= '0;
      v_static_expired  <= '0;
      v_false_refusal   <= '0;
      v_occupancy_drift <= '0;
    end else begin
      if (sweep_valid) begin
        if (sweep_entry.valid) begin
          counted_valid <= counted_valid + 1'b1;

          // THE STRUCTURAL INVARIANT. A key lives in exactly the set its
          // hash names. If it does not, either the hash changed under a
          // live table -- a reseed without a flush -- or an insert wrote
          // the wrong index, and in both cases the key is UNFINDABLE:
          // every lookup for it will search a different set and miss,
          // while the entry sits there consuming a way forever.
          if (recomputed_index != sweep_index)
            if (!(&v_wrong_set)) v_wrong_set <= v_wrong_set + 1'b1;
        end

        // Chapter 12.2 Section 6: an operator asserted a static entry, so
        // no automatic mechanism may retract it.
        if (expire_was_static)
          if (!(&v_static_expired)) v_static_expired <= v_static_expired + 1'b1;
      end

      if (ins_valid) begin
        if ((ins_result == TI_EVICT) && evict_was_static)
          if (!(&v_static_evicted)) v_static_evicted <= v_static_evicted + 1'b1;

        // A refusal must have a full set behind it. Refusing with a free
        // way is a lost address that nothing would ever explain.
        if ((ins_result == TI_SET_FULL) && (ins_set_used_ways < 4'(WAYS)))
          if (!(&v_false_refusal)) v_false_refusal <= v_false_refusal + 1'b1;
      end

      // One complete pass is a census. The valid bits counted must equal
      // the running occupancy; drift means an insert or an expiry failed
      // to adjust it, and every capacity decision downstream is then made
      // on a wrong number.
      if (sweep_wrapped) begin
        if (counted_valid != occupancy)
          if (!(&v_occupancy_drift))
            v_occupancy_drift <= v_occupancy_drift + 1'b1;
        counted_valid <= '0;
      end
    end
  end

  assign conformant = (v_wrong_set       == '0) &&
                      (v_static_evicted  == '0) &&
                      (v_static_expired  == '0) &&
                      (v_false_refusal   == '0) &&
                      (v_occupancy_drift == '0);

endmodule

// P1. A key lives in exactly the set its hash names. An entry elsewhere
// is UNFINDABLE and consumes a way forever.
property p_key_in_its_hash_set;
  @(posedge clk) disable iff (!rst_n)
  (sweep_valid && sweep_entry.valid) |-> (recomputed_index == sweep_index);
endproperty
a_key_placement: assert property (p_key_in_its_hash_set);

// P2. The hash is a function -- the same key always yields the same
// index. A seeded hash must therefore not change under a live table.
property p_hash_is_deterministic;
  @(posedge clk) disable iff (!rst_n)
  (key_valid && (key == $past(key)) && $stable(hash_seed))
    |-> (index == $past(index));
endproperty
a_hash_stable: assert property (p_hash_is_deterministic);

// P3. The index is in range.
property p_index_in_range;
  @(posedge clk) disable iff (!rst_n)
  key_valid |-> (index < IDX_W'(N_SETS));
endproperty
a_index_range: assert property (p_index_in_range);

// P4. A lookup compares the FULL 48-bit key. A hash is not reversible, so
// unlike a cache tag nothing may be omitted.
property p_full_key_compared;
  @(posedge clk) disable iff (!rst_n)
  (lk_valid && lk_hit) |-> (mem[lk_index][lk_way].key == lk_key);
endproperty
a_full_key: assert property (p_full_key_compared);

// P5. A miss means the key is in no way of its set -- which, because the
// hash is deterministic, means it is not in the table at all.
property p_miss_means_absent;
  @(posedge clk) disable iff (!rst_n)
  (lk_valid && !lk_hit) |-> (way_match == '0);
endproperty
a_miss_complete: assert property (p_miss_means_absent);

// P6. A key appears at most once. The structure makes this automatic --
// a key has one set -- and asserting it catches an index-bit fault.
property p_key_unique;
  @(posedge clk) disable iff (!rst_n)
  lk_valid |-> $onehot0(way_match);
endproperty
a_key_unique: assert property (p_key_unique);

// P7. A free way is used before any eviction is considered.
property p_free_way_preferred;
  @(posedge clk) disable iff (!rst_n)
  (ins_valid && !(|ins_match) && (|ins_free)) |=> (ins_result == TI_INSERT);
endproperty
a_free_first: assert property (p_free_way_preferred);

// P8. A refusal implies the set really was full. Refusing with a way free
// is an address lost for no reason and with no explanation.
property p_refusal_implies_full_set;
  @(posedge clk) disable iff (!rst_n)
  (ins_valid && (ins_result == TI_SET_FULL)) |-> (ins_set_used_ways == 4'(WAYS));
endproperty
a_refusal_genuine: assert property (p_refusal_implies_full_set);

// P9. TI_SET_FULL is distinct from a table-full condition. The two have
// different remedies and only one is fixed by more memory.
property p_set_full_distinct_from_table_full;
  @(posedge clk) disable iff (!rst_n)
  (ins_valid && (ins_result == TI_SET_FULL) && (occupancy < CNT_W'(N_SETS*WAYS)))
    |-> hash_bound;
endproperty
a_set_vs_table: assert property (p_set_full_distinct_from_table_full);

// P10. A static entry is NEVER evicted. Chapter 12.2 Section 6: an
// operator asserted it, so no automatic mechanism may retract it.
property p_static_never_evicted;
  @(posedge clk) disable iff (!rst_n)
  (ins_valid && (ins_result == TI_EVICT)) |-> !set_ways[evict_way].stat;
endproperty
a_static_survives_evict: assert property (p_static_never_evicted);

// P11. A static entry is NEVER expired.
property p_static_never_expired;
  @(posedge clk) disable iff (!rst_n)
  age_expire |-> !sweep_entry.stat;
endproperty
a_static_survives_age: assert property (p_static_never_expired);

// P12. Eviction is REFUSED while an attack is suspected. Chapter 12.2
// Section 12: refusing lets an attacker block new learning; evicting
// lets them remove stations that are working.
property p_no_evict_under_attack;
  @(posedge clk) disable iff (!rst_n)
  (sel_valid && attack_suspected) |-> !evict_permitted;
endproperty
a_refuse_under_attack: assert property (p_no_evict_under_attack);

// P13. Eviction is REFUSED when every candidate is fresh -- displacing a
// live conversation to admit an unknown address trades a certainty for a
// guess.
property p_no_evict_when_all_fresh;
  @(posedge clk) disable iff (!rst_n)
  (sel_valid && all_ways_fresh) |-> !evict_permitted;
endproperty
a_refuse_when_fresh: assert property (p_no_evict_when_all_fresh);

// P14. The chosen victim is the oldest NON-STATIC way in this set. Note
// the scope: in THIS SET. See the rejected property below.
property p_victim_is_oldest_in_set;
  @(posedge clk) disable iff (!rst_n)
  (sel_valid && evict_permitted) |->
    (set_ways[evict_way].age == max_nonstatic_age_in_set);
endproperty
a_oldest_in_set: assert property (p_victim_is_oldest_in_set);

// P15. Every eviction records what it displaced, so the damage is
// measurable rather than inferred.
property p_eviction_records_victim;
  @(posedge clk) disable iff (!rst_n)
  (ins_valid && (ins_result == TI_EVICT))
    |=> ((displaced_key != '0) && $changed(c_evictions));
endproperty
a_eviction_recorded: assert property (p_eviction_records_victim);

// P16. The sweep completes a full pass within its interval. It has a
// second and needs 33 microseconds -- but only if it is granted.
property p_sweep_completes_in_interval;
  @(posedge clk) disable iff (!rst_n)
  second_tick |-> ##[1:$] sweep_wrapped within (!second_tick[*1:$] ##1 second_tick);
endproperty
a_sweep_completes: assert property (p_sweep_completes_in_interval);

// P17. The sweep NEVER wins against a lookup or an insert. It has a
// second; they have 28 nanoseconds.
property p_sweep_lowest_priority;
  @(posedge clk) disable iff (!rst_n)
  (mem_request && (lk_valid || ins_valid)) |-> !mem_grant;
endproperty
a_sweep_yields: assert property (p_sweep_lowest_priority);

// P18. An entry expires only at or after the configured interval --
// Chapter 12.2's P14, restated at the structure.
property p_no_early_expiry;
  @(posedge clk) disable iff (!rst_n)
  age_expire |-> (sweep_entry.age >= age_limit);
endproperty
a_no_early_expiry: assert property (p_no_early_expiry);

// P19. Every visited valid entry either ages or expires -- an entry the
// sweep skips never expires at all.
property p_every_entry_aged;
  @(posedge clk) disable iff (!rst_n)
  (mem_grant && pass_active_q && sweep_entry.valid && !sweep_entry.stat)
    |-> age_write;
endproperty
a_all_aged: assert property (p_every_entry_aged);

// P20. Expiry decrements occupancy exactly once.
property p_expiry_adjusts_occupancy;
  @(posedge clk) disable iff (!rst_n)
  (age_write && age_expire) |=> (occupancy == $past(occupancy) - 1);
endproperty
a_expiry_occupancy: assert property (p_expiry_adjusts_occupancy);

// P21. The census matches the running occupancy at the end of a pass.
property p_occupancy_census_agrees;
  @(posedge clk) disable iff (!rst_n)
  sweep_wrapped |-> (counted_valid == occupancy);
endproperty
a_occupancy_honest: assert property (p_occupancy_census_agrees);

// P22. Occupancy never exceeds nominal capacity.
property p_occupancy_bounded;
  @(posedge clk) disable iff (!rst_n)
  (occupancy <= CNT_W'(N_SETS * WAYS));
endproperty
a_occupancy_bounded: assert property (p_occupancy_bounded);

// P23. A refused address is still counted as OFFERED, or effective
// capacity is trivially 100% by construction.
property p_refusal_counted_as_offered;
  @(posedge clk) disable iff (!rst_n)
  (ins_valid && (ins_result == TI_SET_FULL)) |=> $changed(win_distinct);
endproperty
a_refusal_offered: assert property (p_refusal_counted_as_offered);

// P24. The two bound conditions are distinguished, because one is fixed
// by more memory and the other is not.
property p_bounds_are_distinct;
  @(posedge clk) disable iff (!rst_n)
  window_valid |-> !(capacity_bound && hash_bound);
endproperty
a_bounds_distinct: assert property (p_bounds_are_distinct);

// P25. The lookup completes within Chapter 12.3's budget, every time.
property p_lookup_meets_deadline;
  @(posedge clk) disable iff (!rst_n)
  lk_valid |-> ##[1:4] lk_done;
endproperty
a_lookup_deadline: assert property (p_lookup_meets_deadline);

// P26. The lookup latency is CONSTANT -- it does not depend on how full
// the set is, which is what makes the deadline assertable at all.
property p_lookup_latency_constant;
  @(posedge clk) disable iff (!rst_n)
  lk_done |-> (lk_latency_cy == 3'd4);
endproperty
a_constant_latency: assert property (p_lookup_latency_constant);

// P27. Conformance means the structure's invariants hold -- never that
// the table has the right contents.
property p_conformant_definition;
  @(posedge clk) disable iff (!rst_n)
  conformant |-> ((v_wrong_set == '0) && (v_static_evicted == '0) &&
                  (v_static_expired == '0) && (v_false_refusal == '0) &&
                  (v_occupancy_drift == '0));
endproperty
a_conformant_def: assert property (p_conformant_definition);

// P28. A hash reseed is accompanied by a flush, or every key is now in
// the wrong set.
property p_reseed_implies_flush;
  @(posedge clk) disable iff (!rst_n)
  $changed(hash_seed) |-> ##[0:2] table_flush;
endproperty
a_reseed_flushes: assert property (p_reseed_implies_flush);