TLB/src/ariane/tlb.py

   1 """
   2 # Copyright 2018 ETH Zurich and University of Bologna.
   3 # Copyright and related rights are licensed under the Solderpad Hardware
   4 # License, Version 0.51 (the "License"); you may not use this file except in
   5 # compliance with the License.  You may obtain a copy of the License at
   6 # http:#solderpad.org/licenses/SHL-0.51. Unless required by applicable law
   7 # or agreed to in writing, software, hardware and materials distributed under
   8 # this License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
   9 # CONDITIONS OF ANY KIND, either express or implied. See the License for the
  10 # specific language governing permissions and limitations under the License.
  11 #
  12 # Author: David Schaffenrath, TU Graz
  13 # Author: Florian Zaruba, ETH Zurich
  14 # Date: 21.4.2017
  15 # Description: Translation Lookaside Buffer, SV39
  16 #              fully set-associative
  17 """
  18 from math import log2
  19 from nmigen import Signal, Module, Cat, Const, Array
  20 from nmigen.cli import verilog, rtlil
  21
  22
  23 # SV39 defines three levels of page tables
  24 class TLBEntry:
  25     def __init__(self):
  26         self.asid = Signal(ASID_WIDTH)
  27         self.vpn2 = Signal(9)
  28         self.vpn1 = Signal(9)
  29         self.vpn0 = Signal(9)
  30         self.is_2M = Signal()
  31         self.is_1G = Signal()
  32         self.valid = Signal()
  33
  34 TLB_ENTRIES = 4
  35 ASID_WIDTH  = 1
  36
  37 from ptw import TLBUpdate, PTE
  38
  39
  40 class TLB:
  41     def __init__(self):
  42         self.flush_i = Signal()  # Flush signal
  43         # Update TLB
  44         self.update_i = TLBUpdate()
  45         # Lookup signals
  46         self.lu_access_i = Signal()
  47         self.lu_asid_i = Signal(ASID_WIDTH)
  48         self.lu_vaddr_i = Signal(64)
  49         self.lu_content_o = PTE()
  50         self.lu_is_2M_o = Signal()
  51         self.lu_is_1G_o = Signal()
  52         self.lu_hit_o = Signal()
  53
  54     def elaborate(self, platform):
  55         m = Module()
  56
  57         # SV39 defines three levels of page tables
  58         tags = Array([TLBEntry() for i in range(TLB_ENTRIES)])
  59         content = Array([PTE() for i in range(TLB_ENTRIES)])
  60
  61         vpn2 = Signal(9)
  62         vpn1 = Signal(9)
  63         vpn0 = Signal(9)
  64         lu_hit = Signal(TLB_ENTRIES)     # to replacement logic
  65         replace_en = Signal(TLB_ENTRIES) # replace the following entry,
  66                                          # set by replacement strategy
  67         #-------------
  68         # Translation
  69         #-------------
  70         m.d.comb += [ vpn0.eq(self.lu_vaddr_i[12:21]),
  71                       vpn1.eq(self.lu_vaddr_i[21:30]),
  72                       vpn2.eq(self.lu_vaddr_i[30:39]),
  73                     ]
  74
  75         for i in range(TLB_ENTRIES):
  76             m.d.comb += lu_hit[i].eq(0)
  77             # temporaries for 1st level match
  78             asid_ok = Signal()
  79             vpn2_ok = Signal()
  80             tags_ok = Signal()
  81             vpn2_hit = Signal()
  82             m.d.comb += [tags_ok.eq(tags[i].valid),
  83                          asid_ok.eq(tags[i].asid == self.lu_asid_i),
  84                          vpn2_ok.eq(tags[i].vpn2 == vpn2),
  85                          vpn2_hit.eq(tags_ok & asid_ok & vpn2_ok)]
  86             # temporaries for 2nd level match
  87             vpn1_ok = Signal()
  88             tags_2M = Signal()
  89             vpn0_ok = Signal()
  90             vpn0_or_2M = Signal()
  91             m.d.comb += [vpn1_ok.eq(vpn1 == tags[i].vpn1),
  92                          tags_2M.eq(tags[i].is_2M),
  93                          vpn0_ok.eq(vpn0 == tags[i].vpn0),
  94                          vpn0_or_2M.eq(tags_2M | vpn0_ok)]
  95             # first level match, this may be a giga page,
  96             # check the ASID flags as well
  97             with m.If(vpn2_hit):
  98                 # second level
  99                 with m.If (tags[i].is_1G):
 100                     m.d.sync += self.lu_content_o.eq(content[i])
 101                     m.d.comb += [ self.lu_is_1G_o.eq(1),
 102                                   self.lu_hit_o.eq(1),
 103                                   lu_hit[i].eq(1),
 104                                 ]
 105                 # not a giga page hit so check further
 106                 with m.Elif(vpn1_ok):
 107                     # this could be a 2 mega page hit or a 4 kB hit
 108                     # output accordingly
 109                     with m.If(vpn0_or_2M):
 110                         m.d.sync += self.lu_content_o.eq(content[i])
 111                         m.d.comb += [ self.lu_is_2M_o.eq(tags[i].is_2M),
 112                                       self.lu_hit_o.eq(1),
 113                                       lu_hit[i].eq(1),
 114                                     ]
 115
 116         # ------------------
 117         # Update and Flush
 118         # ------------------
 119
 120         for i in range(TLB_ENTRIES):
 121             replace_valid = Signal()
 122             m.d.comb += replace_valid.eq(self.update_i.valid & replace_en[i])
 123             with m.If (self.flush_i):
 124                 # invalidate (flush) conditions: all if zero or just this ASID
 125                 with m.If (self.lu_asid_i == Const(0, ASID_WIDTH) |
 126                           (self.lu_asid_i == tags[i].asid)):
 127                     m.d.sync += tags[i].valid.eq(0)
 128
 129             # normal replacement
 130             with m.Elif(replace_valid):
 131                 m.d.sync += [ # update tag array
 132                               tags[i].asid.eq(self.update_i.asid),
 133                               tags[i].vpn2.eq(self.update_i.vpn[18:27]),
 134                               tags[i].vpn1.eq(self.update_i.vpn[9:18]),
 135                               tags[i].vpn0.eq(self.update_i.vpn[0:9]),
 136                               tags[i].is_1G.eq(self.update_i.is_1G),
 137                               tags[i].is_2M.eq(self.update_i.is_2M),
 138                               tags[i].valid.eq(1),
 139                               # and content as well
 140                               content[i].eq(self.update_i.content)
 141                             ]
 142
 143         # -----------------------------------------------
 144         # PLRU - Pseudo Least Recently Used Replacement
 145         # -----------------------------------------------
 146
 147         TLBSZ = 2*(TLB_ENTRIES-1)
 148         plru_tree = Signal(TLBSZ)
 149
 150         # The PLRU-tree indexing:
 151         # lvl0        0
 152         #            / \
 153         #           /   \
 154         # lvl1     1     2
 155         #         / \   / \
 156         # lvl2   3   4 5   6
 157         #       / \ /\/\  /\
 158         #      ... ... ... ...
 159         # Just predefine which nodes will be set/cleared
 160         # E.g. for a TLB with 8 entries, the for-loop is semantically
 161         # equivalent to the following pseudo-code:
 162         # unique case (1'b1)
 163         # lu_hit[7]: plru_tree[0, 2, 6] = {1, 1, 1};
 164         # lu_hit[6]: plru_tree[0, 2, 6] = {1, 1, 0};
 165         # lu_hit[5]: plru_tree[0, 2, 5] = {1, 0, 1};
 166         # lu_hit[4]: plru_tree[0, 2, 5] = {1, 0, 0};
 167         # lu_hit[3]: plru_tree[0, 1, 4] = {0, 1, 1};
 168         # lu_hit[2]: plru_tree[0, 1, 4] = {0, 1, 0};
 169         # lu_hit[1]: plru_tree[0, 1, 3] = {0, 0, 1};
 170         # lu_hit[0]: plru_tree[0, 1, 3] = {0, 0, 0};
 171         # default: begin /* No hit */ end
 172         # endcase
 173         LOG_TLB = int(log2(TLB_ENTRIES))
 174         for i in range(TLB_ENTRIES):
 175             # we got a hit so update the pointer as it was least recently used
 176             hit = Signal()
 177             m.d.comb += hit.eq(lu_hit[i] & self.lu_access_i)
 178             with m.If(hit):
 179                 # Set the nodes to the values we would expect
 180                 for lvl in range(LOG_TLB):
 181                     idx_base = (1<<lvl)-1
 182                     # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 183                     shift = LOG_TLB - lvl;
 184                     new_idx = Const(~((i >> (shift-1)) & 1), 1)
 185                     print ("plru", i, lvl, hex(idx_base), shift, new_idx)
 186                     m.d.sync += plru_tree[idx_base + (i >> shift)].eq(new_idx)
 187
 188         # Decode tree to write enable signals
 189         # Next for-loop basically creates the following logic for e.g.
 190         # an 8 entry TLB (note: pseudo-code obviously):
 191         # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
 192         # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
 193         # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
 194         # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
 195         # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
 196         # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
 197         # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
 198         # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
 199         # For each entry traverse the tree. If every tree-node matches
 200         # the corresponding bit of the entry's index, this is
 201         # the next entry to replace.
 202         for i in range(TLB_ENTRIES):
 203             en = Signal(LOG_TLB)
 204             for lvl in range(LOG_TLB):
 205                 idx_base = (1<<lvl)-1
 206                 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 207                 shift = LOG_TLB - lvl;
 208                 new_idx = (i >> (shift-1)) & 1;
 209                 plru = Signal()
 210                 m.d.comb += plru.eq(plru_tree[idx_base + (i>>shift)])
 211                 # en &= plru_tree_q[idx_base + (i>>shift)] == new_idx;
 212                 if new_idx:
 213                     en[lvl].eq(~plru) # yes inverted (using bool())
 214                 else:
 215                     en[lvl].eq(plru)  # yes inverted (using bool())
 216             print ("plru", i, en)
 217             # boolean logic manipluation:
 218             # plur0 & plru1 & plur2 == ~(~plru0 | ~plru1 | ~plru2)
 219             m.d.sync += replace_en[i].eq(~Cat(*en).bool())
 220
 221         #--------------
 222         # Sanity checks
 223         #--------------
 224
 225         assert (TLB_ENTRIES % 2 == 0) and (TLB_ENTRIES > 1), \
 226             "TLB size must be a multiple of 2 and greater than 1"
 227         assert (ASID_WIDTH >= 1), \
 228             "ASID width must be at least 1"
 229
 230         return m
 231
 232         """
 233         # Just for checking
 234         function int countSetBits(logic[TLB_ENTRIES-1:0] vector);
 235           automatic int count = 0;
 236           foreach (vector[idx]) begin
 237             count += vector[idx];
 238           end
 239           return count;
 240         endfunction
 241
 242         assert property (@(posedge clk_i)(countSetBits(lu_hit) <= 1))
 243           else $error("More then one hit in TLB!"); $stop(); end
 244         assert property (@(posedge clk_i)(countSetBits(replace_en) <= 1))
 245           else $error("More then one TLB entry selected for next replace!");
 246         """
 247
 248     def ports(self):
 249         return [self.flush_i, self.lu_access_i,
 250                  self.lu_asid_i, self.lu_vaddr_i,
 251                  self.lu_is_2M_o, self.lu_is_1G_o, self.lu_hit_o,
 252                 ] + self.lu_content_o.ports() + self.update_i.ports()
 253
 254 if __name__ == '__main__':
 255     tlb = TLB()
 256     vl = rtlil.convert(tlb, ports=tlb.ports())
 257     with open("test_tlb.il", "w") as f:
 258         f.write(vl)
 259