TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Decoder
   3 from nmigen.cli import main #, verilog
   4
   5 from CamEntry import CamEntry
   6 from AddressEncoder import AddressEncoder
   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, data_size, cam_size):
  29         """ Arguments:
  30             * data_size: (bit count) The size of the data
  31             * cam_size: (entry count) The number of entries int he CAM
  32         """
  33
  34         # Internal
  35         self.cam_size = cam_size
  36         self.encoder = AddressEncoder(cam_size)
  37         self.decoder = Decoder(cam_size)
  38         self.entry_array = Array(CamEntry(data_size) \
  39                             for x in range(cam_size))
  40
  41         # Input
  42         self.enable = Signal(1)
  43         self.write_enable = Signal(1)
  44         self.data_in = Signal(data_size) # The data to be written
  45         self.data_mask = Signal(data_size) # mask for ternary writes
  46         self.address_in = Signal(max=cam_size) # address of CAM Entry to write
  47
  48         # Output
  49         self.read_warning = Signal(1) # High when a read interrupts a write
  50         self.single_match = Signal(1) # High when there is only one match
  51         self.multiple_match = Signal(1) # High when there at least two matches
  52         self.match_address = Signal(max=cam_size) # The lowest address matched
  53
  54     def elaborate(self, platform=None):
  55         m = Module()
  56         # Encoder checks for multiple matches
  57         m.submodules.AddressEncoder = self.encoder
  58         # Decoder is used to select which entry will be written to
  59         m.submodules.decoder = self.decoder
  60         # Don't forget to add all entries to the submodule list
  61         entry_array = self.entry_array
  62         m.submodules += entry_array
  63
  64         # Decoder logic
  65         m.d.comb += [
  66             self.decoder.i.eq(self.address_in),
  67             self.decoder.n.eq(0)
  68         ]
  69
  70         with m.If(self.enable):
  71             # Set the key value for every CamEntry
  72             for index in range(self.cam_size):
  73
  74                 # Read Operation
  75                 with m.If(~self.write_enable):
  76                     m.d.comb += entry_array[index].command.eq(1)
  77
  78                 # Write Operation
  79                 with m.Else():
  80                     with m.If(self.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
  85                 # Send data input to all entries
  86                 m.d.comb += entry_array[index].data_in.eq(self.data_in)
  87                 #Send all entry matches to encoder
  88                 m.d.comb += self.encoder.i[index].eq(entry_array[index].match)
  89
  90             # Accept output from encoder module
  91             m.d.comb += [
  92                 self.single_match.eq(self.encoder.single_match),
  93                 self.multiple_match.eq(self.encoder.multiple_match),
  94                 self.match_address.eq(self.encoder.o)
  95             ]
  96
  97         # If the CAM is not enabled set all outputs to 0
  98         with m.Else():
  99             m.d.comb += [
 100                     self.read_warning.eq(0),
 101                     self.single_match.eq(0),
 102                     self.multiple_match.eq(0),
 103                     self.match_address.eq(0)
 104             ]
 105
 106         return m
 107
 108 if __name__ == '__main__':
 109     cam = Cam(4, 4)
 110     main(cam, ports=[cam.enable, cam.write_enable,
 111                      cam.data_in, cam.data_mask,
 112                      cam.read_warning, cam.single_match,
 113                      cam.multiple_match, cam.match_address])
 114