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