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