TLB/src/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Encoder
   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 class Cam():
  18
  19     # Arguments:
  20     #  key_size: (bit count) The size of the key
  21     #  data_size: (bit count) The size of the data
  22     #  cam_size: (entry count) The number of entries int he CAM
  23     def __init__(self, key_size, data_size, cam_size):
  24         # Internal
  25         self.cam_size = cam_size
  26         self.entry_array = Array(CamEntry(key_size, data_size) \
  27                             for x in range(cam_size))
  28
  29         # Input
  30         self.command = Signal(2) # 00 => NA 01 => Read 10 => Write 11 => Search
  31         self.address = Signal(max=cam_size) # address of CAM Entry to write/read
  32         self.key_in = Signal(key_size) # The key to search for or to be written
  33         self.data_in = Signal(key_size) # The data to be written
  34
  35         # Output
  36         self.data_hit = Signal(1) # Denotes a key data pair was stored at key_in
  37         self.data_out = Signal(data_size) # The data mapped to by key_in
  38
  39     def elaborate(self, platform=None):
  40         m = Module()
  41
  42         m.submodules.encoder = encoder = Encoder(self.cam_size)
  43         m.submodules += self.entry_array
  44
  45         # Set the key value for every CamEntry
  46         for index in range(self.cam_size):
  47             with m.Switch(self.command):
  48                 # Read and Search both read from the CamEntry
  49                 with m.Case("-1"):
  50                     m.d.comb += self.entry_array[index].command.eq(1)
  51                 # Write only to one entry
  52                 with m.Case("10"):
  53                     with m.If(self.address == index):
  54                         m.d.comb += self.entry_array[index].command.eq(2)
  55                     with m.Else():
  56                         m.d.comb += self.entry_array[index].command.eq(0)
  57                 # NA
  58                 with m.Case():
  59                     m.d.comb += self.entry_array[index].command.eq(0)
  60
  61             m.d.comb += [
  62                    self.entry_array[index].key_in.eq(self.key_in),
  63                    self.entry_array[index].data_in.eq(self.data_in),
  64                    encoder.i[index].eq(self.entry_array[index].match)
  65             ]
  66
  67
  68         with m.Switch(self.command):
  69             # Read
  70             with m.Case("01"):
  71                 m.d.comb += [
  72                     self.data_hit.eq(0),
  73                     self.data_out.eq(self.entry_array[self.address].data)
  74                 ]
  75             # Write
  76             with m.Case("10"):
  77                 m.d.comb += [
  78                     self.data_hit.eq(0),
  79                     self.entry_array[self.address].key_in.eq(self.key_in),
  80                     self.entry_array[self.address].data_in.eq(self.data_in)
  81                 ]
  82             # NA / Searching
  83             with m.Case():
  84                 with m.If(encoder.n == 0):
  85                     m.d.comb += [
  86                         self.data_hit.eq(1),
  87                         self.data_out.eq(self.entry_array[encoder.o].data)
  88                     ]
  89                 with m.Else():
  90                     m.d.comb += self.data_hit.eq(0)
  91
  92         return m