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