TLB/Cam.py

   1 from nmigen import Array, Module, Signal
   2 from nmigen.lib.coding import Encoder
   3
   4 from CamEntry import CamEntry
   5
   6 # Content Addressable Memory (CAM)
   7 # The purpose of this module is to quickly look up whether an entry exists
   8 # given a certain key and return the mapped data.
   9 # This module when given a key will search for the given key
  10 # in all internal entries and output whether a match was found or not.
  11 # If an entry is found the data will be returned and data_hit is HIGH,
  12 # if it is not LOW is asserted on data_hit. When given a write
  13 # command it will write the given key and data into the given cam entry index.
  14 # Entry managment should be performed one level above this block as lookup is
  15 # performed within.
  16 class Cam():
  17
  18     # Arguments:
  19     #  key_size: (bit count) The size of the key
  20     #  data_size: (bit count) The size of the data
  21     #  cam_size: (entry count) The number of entries int he CAM
  22     def __init__(self, key_size, data_size, cam_size):
  23         # Internal
  24         self.cam_size = cam_size
  25         self.entry_array = Array(CamEntry(key_size, data_size) \
  26                             for x in range(cam_size))
  27         self.encoder_input = Signal(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 get_fragment(self, platform=None):
  40         m = Module()
  41
  42         m.d.submodules.encoder = encoder = Encoder(self.cam_size)
  43
  44         # Set the key value for every CamEntry
  45         for index in range(self.cam_size):
  46             with m.If(self.command == 3):
  47                 m.d.sync += [
  48                        self.entry_array[index].write.eq(0),
  49                        self.entry_array[index].key_in.eq(self.key_in),
  50                        self.entry_array[index].data_in.eq(self.data_in),
  51                        self.encoder_input[index].eq(self.entry_array[index].match)
  52                 ]
  53
  54         with m.Switch(self.command):
  55             # Read
  56             with m.Case("01"):
  57                 m.d.sync += [
  58                     self.data_hit.eq(0),
  59                     self.data_out.eq(self.entry_array[self.address].data)
  60                 ]
  61             # Write
  62             with m.Case("10"):
  63                 m.d.sync += [
  64                     self.data_hit.eq(0),
  65                     self.entry_array[self.address].write.eq(1),
  66                     self.entry_array[self.address].key_in.eq(self.key_in),
  67                     self.entry_array[self.address].data.eq(self.data_in)
  68                 ]
  69             # Search
  70             with m.Case("11"):
  71                 m.d.sync += encoder.i.eq(self.encoder_input)
  72                 with m.If(encoder.n == 0):
  73                     m.d.sync += [
  74                         self.data_hit.eq(0),
  75                         self.data_out.eq(self.entry_array[encoder.o].data)
  76                     ]
  77                 with m.Else():
  78                     m.d.sync += self.data_hit.eq(1)
  79             # NA
  80             with m.Case():
  81                 self.data_hit.eq(0)
  82
  83         return m