TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Encoder, Decoder
   3 from nmigen.compat.fhdl.structure import ClockDomain
   4
   5 from CamEntry import CamEntry
   6
   7 # Content Addressable Memory (CAM)
   8 # The purpose of this module is to quickly look up whether an entry exists
   9 # given a certain key and return the mapped data.
  10 # This module when given a key will search for the given key
  11 # in all internal entries and output whether a match was found or not.
  12 # If an entry is found the data will be returned and data_hit is HIGH,
  13 # if it is not LOW is asserted on data_hit. When given a write
  14 # command it will write the given key and data into the given cam entry index.
  15 # Entry managment should be performed one level above this block as lookup is
  16 # performed within.
  17 # Notes:
  18 # The search, write, and reset operations take one clock cycle to complete.
  19 # Performing a read right after a search will cause the read to be ignored.
  20 class Cam():
  21
  22     # Arguments:
  23     #  key_size: (bit count) The size of the key
  24     #  data_size: (bit count) The size of the data
  25     #  cam_size: (entry count) The number of entries int he CAM
  26     def __init__(self, key_size, data_size, cam_size):
  27         # Internal
  28         self.cam_size = cam_size
  29         self.entry_array = Array(CamEntry(key_size, data_size) \
  30                             for x in range(cam_size))
  31
  32         # Input
  33         # 000 => NA 001 => Read 010 => Write 011 => Search
  34         # 100 => Reset 101, 110, 111 => Reserved
  35         self.command = Signal(3)
  36         self.address = Signal(max=cam_size) # address of CAM Entry to write/read
  37         self.key_in = Signal(key_size) # The key to search for or to be written
  38         self.data_in = Signal(key_size) # The data to be written
  39
  40         # Output
  41         self.data_hit = Signal(1) # Denotes a key data pair was stored at key_in
  42         self.data_out = Signal(data_size) # The data mapped to by key_in
  43
  44     def elaborate(self, platform=None):
  45         m = Module()
  46
  47
  48         # Encoder is used to selecting what data is output when searching
  49         m.submodules.encoder = encoder = Encoder(self.cam_size)
  50         # Decoder is used to select which entry will be written to
  51         m.submodules.decoder = decoder = Decoder(self.cam_size)
  52         # Don't forget to add all entries to the submodule list
  53         entry_array = self.entry_array
  54         m.submodules += entry_array
  55
  56         # Decoder logic
  57         m.d.comb += [
  58             decoder.i.eq(self.address),
  59             decoder.n.eq(0)
  60         ]
  61
  62         # Set the key value for every CamEntry
  63         for index in range(self.cam_size):
  64             with m.Switch(self.command):
  65                 # Read from a single entry
  66                 with m.Case("0-1"):
  67                     m.d.comb += entry_array[index].command.eq(1)
  68                     # Only read if an encoder value is not ready
  69                     with m.If(decoder.o[index] & encoder.n):
  70                         m.d.comb += self.data_out.eq(entry_array[index].data)
  71                 # Write only to one entry
  72                 with m.Case("010"):
  73                     # Address is decoded and selects which
  74                     # entry will be written to
  75                     with m.If(decoder.o[index]):
  76                         m.d.comb += entry_array[index].command.eq(2)
  77                     with m.Else():
  78                         m.d.comb += entry_array[index].command.eq(0)
  79                 # Search all entries
  80                 with m.Case("011"):
  81                     m.d.comb += entry_array[index].command.eq(1)
  82                 # Reset
  83                 with m.Case("100"):
  84                     m.d.comb += entry_array[index].command.eq(3)
  85                 # NA / Reserved
  86                 with m.Case():
  87                     m.d.comb += entry_array[index].command.eq(0)
  88
  89             m.d.comb += [
  90                    entry_array[index].key_in.eq(self.key_in),
  91                    entry_array[index].data_in.eq(self.data_in),
  92                    encoder.i[index].eq(entry_array[index].match)
  93             ]
  94
  95         # Process out data based on encoder address
  96         with m.If(encoder.n == 0):
  97             m.d.comb += [
  98                 self.data_hit.eq(1),
  99                 self.data_out.eq(entry_array[encoder.o].data)
 100             ]
 101         with m.Else():
 102             m.d.comb += self.data_hit.eq(0)
 103
 104         return m