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 from nmigen.lib.coding import Encoder
  22
  23 from ptw import TLBUpdate, PTE, ASID_WIDTH
  24
  25 TLB_ENTRIES = 4
  26
  27
  28 class TLBEntry:
  29     def __init__(self):
  30         self.asid = Signal(ASID_WIDTH)
  31         # SV39 defines three levels of page tables
  32         self.vpn0 = Signal(9)
  33         self.vpn1 = Signal(9)
  34         self.vpn2 = Signal(9)
  35         self.is_2M = Signal()
  36         self.is_1G = Signal()
  37         self.valid = Signal()
  38
  39     def flatten(self):
  40         return Cat(*self.ports())
  41
  42     def eq(self, x):
  43         return self.flatten().eq(x.flatten())
  44
  45     def ports(self):
  46         return [self.asid, self.vpn0, self.vpn1, self.vpn2,
  47                 self.is_2M, self.is_1G, self.valid]
  48
  49
  50 class TLBContent:
  51     def __init__(self, pte_width):
  52         self.pte_width = pte_width
  53         self.flush_i = Signal()  # Flush signal
  54         # Update TLB
  55         self.update_i = TLBUpdate()
  56         self.vpn2 = Signal(9)
  57         self.vpn1 = Signal(9)
  58         self.vpn0 = Signal(9)
  59         self.replace_en = Signal() # replace the following entry,
  60                                    # set by replacement strategy
  61         # Lookup signals
  62         self.lu_asid_i = Signal(ASID_WIDTH)
  63         self.lu_content_o = Signal(self.pte_width)
  64         self.lu_is_2M_o = Signal()
  65         self.lu_is_1G_o = Signal()
  66         self.lu_hit_o = Signal()
  67
  68     def elaborate(self, platform):
  69         m = Module()
  70
  71         tags = TLBEntry()
  72         content = Signal(self.pte_width)
  73
  74         m.d.comb += self.lu_hit_o.eq(0)
  75         # temporaries for 1st level match
  76         asid_ok = Signal(reset_less=True)
  77         vpn2_ok = Signal(reset_less=True)
  78         tags_ok = Signal(reset_less=True)
  79         vpn2_hit = Signal(reset_less=True)
  80         m.d.comb += [tags_ok.eq(tags.valid),
  81                      asid_ok.eq(tags.asid == self.lu_asid_i),
  82                      vpn2_ok.eq(tags.vpn2 == self.vpn2),
  83                      vpn2_hit.eq(tags_ok & asid_ok & vpn2_ok)]
  84         # temporaries for 2nd level match
  85         vpn1_ok = Signal(reset_less=True)
  86         tags_2M = Signal(reset_less=True)
  87         vpn0_ok = Signal(reset_less=True)
  88         vpn0_or_2M = Signal(reset_less=True)
  89         m.d.comb += [vpn1_ok.eq(self.vpn1 == tags.vpn1),
  90                      tags_2M.eq(tags.is_2M),
  91                      vpn0_ok.eq(self.vpn0 == tags.vpn0),
  92                      vpn0_or_2M.eq(tags_2M | vpn0_ok)]
  93         # first level match, this may be a giga page,
  94         # check the ASID flags as well
  95         with m.If(vpn2_hit):
  96             # second level
  97             with m.If (tags.is_1G):
  98                 m.d.sync += self.lu_content_o.eq(content)
  99                 m.d.comb += [ self.lu_is_1G_o.eq(1),
 100                               self.lu_hit_o.eq(1),
 101                             ]
 102             # not a giga page hit so check further
 103             with m.Elif(vpn1_ok):
 104                 # this could be a 2 mega page hit or a 4 kB hit
 105                 # output accordingly
 106                 with m.If(vpn0_or_2M):
 107                     m.d.sync += self.lu_content_o.eq(content)
 108                     m.d.comb += [ self.lu_is_2M_o.eq(tags.is_2M),
 109                                   self.lu_hit_o.eq(1),
 110                                 ]
 111
 112         # ------------------
 113         # Update and Flush
 114         # ------------------
 115
 116         replace_valid = Signal(reset_less=True)
 117         m.d.comb += replace_valid.eq(self.update_i.valid & self.replace_en)
 118         with m.If (self.flush_i):
 119             # invalidate (flush) conditions: all if zero or just this ASID
 120             with m.If (self.lu_asid_i == Const(0, ASID_WIDTH) |
 121                       (self.lu_asid_i == tags.asid)):
 122                 m.d.sync += tags.valid.eq(0)
 123
 124         # normal replacement
 125         with m.Elif(replace_valid):
 126             m.d.sync += [ # update tag array
 127                           tags.asid.eq(self.update_i.asid),
 128                           tags.vpn2.eq(self.update_i.vpn[18:27]),
 129                           tags.vpn1.eq(self.update_i.vpn[9:18]),
 130                           tags.vpn0.eq(self.update_i.vpn[0:9]),
 131                           tags.is_1G.eq(self.update_i.is_1G),
 132                           tags.is_2M.eq(self.update_i.is_2M),
 133                           tags.valid.eq(1),
 134                           # and content as well
 135                           content.eq(self.update_i.content.flatten())
 136                         ]
 137
 138         return m
 139
 140     def ports(self):
 141         return [self.flush_i,
 142                  self.lu_asid_i,
 143                  self.lu_is_2M_o, self.lu_is_1G_o, self.lu_hit_o,
 144                 ] + self.update_i.content.ports() + self.update_i.ports()
 145
 146
 147 class PLRU:
 148     def __init__(self):
 149         self.lu_hit = Signal(TLB_ENTRIES)
 150         self.replace_en = Signal(TLB_ENTRIES)
 151         self.lu_access_i = Signal()
 152
 153     def elaborate(self, platform):
 154         m = Module()
 155
 156         # -----------------------------------------------
 157         # PLRU - Pseudo Least Recently Used Replacement
 158         # -----------------------------------------------
 159
 160         TLBSZ = 2*(TLB_ENTRIES-1)
 161         plru_tree = Signal(TLBSZ)
 162
 163         # The PLRU-tree indexing:
 164         # lvl0        0
 165         #            / \
 166         #           /   \
 167         # lvl1     1     2
 168         #         / \   / \
 169         # lvl2   3   4 5   6
 170         #       / \ /\/\  /\
 171         #      ... ... ... ...
 172         # Just predefine which nodes will be set/cleared
 173         # E.g. for a TLB with 8 entries, the for-loop is semantically
 174         # equivalent to the following pseudo-code:
 175         # unique case (1'b1)
 176         # lu_hit[7]: plru_tree[0, 2, 6] = {1, 1, 1};
 177         # lu_hit[6]: plru_tree[0, 2, 6] = {1, 1, 0};
 178         # lu_hit[5]: plru_tree[0, 2, 5] = {1, 0, 1};
 179         # lu_hit[4]: plru_tree[0, 2, 5] = {1, 0, 0};
 180         # lu_hit[3]: plru_tree[0, 1, 4] = {0, 1, 1};
 181         # lu_hit[2]: plru_tree[0, 1, 4] = {0, 1, 0};
 182         # lu_hit[1]: plru_tree[0, 1, 3] = {0, 0, 1};
 183         # lu_hit[0]: plru_tree[0, 1, 3] = {0, 0, 0};
 184         # default: begin /* No hit */ end
 185         # endcase
 186         LOG_TLB = int(log2(TLB_ENTRIES))
 187         for i in range(TLB_ENTRIES):
 188             # we got a hit so update the pointer as it was least recently used
 189             hit = Signal(reset_less=True)
 190             m.d.comb += hit.eq(self.lu_hit[i] & self.lu_access_i)
 191             with m.If(hit):
 192                 # Set the nodes to the values we would expect
 193                 for lvl in range(LOG_TLB):
 194                     idx_base = (1<<lvl)-1
 195                     # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 196                     shift = LOG_TLB - lvl;
 197                     new_idx = Const(~((i >> (shift-1)) & 1), 1)
 198                     print ("plru", i, lvl, hex(idx_base),
 199                                   idx_base + (i >> shift), shift, new_idx)
 200                     m.d.sync += plru_tree[idx_base + (i >> shift)].eq(new_idx)
 201
 202         # Decode tree to write enable signals
 203         # Next for-loop basically creates the following logic for e.g.
 204         # an 8 entry TLB (note: pseudo-code obviously):
 205         # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
 206         # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
 207         # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
 208         # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
 209         # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
 210         # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
 211         # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
 212         # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
 213         # For each entry traverse the tree. If every tree-node matches
 214         # the corresponding bit of the entry's index, this is
 215         # the next entry to replace.
 216         for i in range(TLB_ENTRIES):
 217             en = Signal(LOG_TLB, reset_less=True)
 218             for lvl in range(LOG_TLB):
 219                 idx_base = (1<<lvl)-1
 220                 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 221                 shift = LOG_TLB - lvl;
 222                 new_idx = (i >> (shift-1)) & 1;
 223                 plru = Signal(reset_less=True)
 224                 m.d.comb += plru.eq(plru_tree[idx_base + (i>>shift)])
 225                 # en &= plru_tree_q[idx_base + (i>>shift)] == new_idx;
 226                 if new_idx:
 227                     m.d.comb += en[lvl].eq(~plru) # yes inverted (using bool())
 228                 else:
 229                     m.d.comb += en[lvl].eq(plru)  # yes inverted (using bool())
 230             print ("plru", i, en)
 231             # boolean logic manipluation:
 232             # plur0 & plru1 & plur2 == ~(~plru0 | ~plru1 | ~plru2)
 233             m.d.sync += self.replace_en[i].eq(~Cat(*en).bool())
 234
 235         return m
 236
 237
 238 class TLB:
 239     def __init__(self):
 240         self.flush_i = Signal()  # Flush signal
 241         # Lookup signals
 242         self.lu_access_i = Signal()
 243         self.lu_asid_i = Signal(ASID_WIDTH)
 244         self.lu_vaddr_i = Signal(64)
 245         self.lu_content_o = PTE()
 246         self.lu_is_2M_o = Signal()
 247         self.lu_is_1G_o = Signal()
 248         self.lu_hit_o = Signal()
 249         # Update TLB
 250         self.pte_width = len(self.lu_content_o.flatten())
 251         self.update_i = TLBUpdate()
 252
 253     def elaborate(self, platform):
 254         m = Module()
 255
 256         vpn2 = Signal(9)
 257         vpn1 = Signal(9)
 258         vpn0 = Signal(9)
 259
 260         #-------------
 261         # Translation
 262         #-------------
 263         m.d.comb += [ vpn0.eq(self.lu_vaddr_i[12:21]),
 264                       vpn1.eq(self.lu_vaddr_i[21:30]),
 265                       vpn2.eq(self.lu_vaddr_i[30:39]),
 266                     ]
 267
 268         # SV39 defines three levels of page tables
 269         tc = []
 270         for i in range(TLB_ENTRIES):
 271             tlc = TLBContent(self.pte_width)
 272             setattr(m.submodules, "tc%d" % i, tlc)
 273             tc.append(tlc)
 274             # connect inputs
 275             m.d.comb += [tlc.vpn0.eq(vpn0),
 276                          tlc.vpn1.eq(vpn1),
 277                          tlc.vpn2.eq(vpn2),
 278                          tlc.flush_i.eq(self.flush_i),
 279                          tlc.update_i.eq(self.update_i),
 280                          tlc.lu_asid_i.eq(self.lu_asid_i)]
 281         tc = Array(tc)
 282
 283         #--------------
 284         # Select hit
 285         #--------------
 286
 287         # use Encoder to select hit index
 288         # XXX TODO: assert that there's only one valid entry
 289         hitsel = Encoder(TLB_ENTRIES)
 290         m.submodules.hitsel = hitsel
 291
 292         hits = []
 293         for i in range(TLB_ENTRIES):
 294             hits.append(tc[i].lu_hit_o)
 295         m.d.comb += hitsel.i.eq(Cat(*hits))
 296         idx = hitsel.o
 297
 298         active = Signal(reset_less=True)
 299         m.d.comb += active.eq(~hitsel.n)
 300         with m.If(active):
 301             # active hit, send selected as output
 302             m.d.comb += [ self.lu_is_1G_o.eq(tc[idx].lu_is_1G_o),
 303                           self.lu_is_2M_o.eq(tc[idx].lu_is_2M_o),
 304                           self.lu_hit_o.eq(1),
 305                           self.lu_content_o.flatten().eq(tc[idx].lu_content_o),
 306                         ]
 307
 308         #--------------
 309         # PLRU.
 310         #--------------
 311
 312         p = PLRU()
 313         m.submodules.plru = p
 314
 315         # connect PLRU inputs/outputs
 316         en = []
 317         for i in range(TLB_ENTRIES):
 318             en.append(tc[i].replace_en)
 319         m.d.comb += [Cat(*en).eq(p.replace_en), # output from PLRU into tags
 320                      p.lu_hit.eq(hitsel.i),
 321                      p.lu_access_i.eq(self.lu_access_i)]
 322
 323         #--------------
 324         # Sanity checks
 325         #--------------
 326
 327         assert (TLB_ENTRIES % 2 == 0) and (TLB_ENTRIES > 1), \
 328             "TLB size must be a multiple of 2 and greater than 1"
 329         assert (ASID_WIDTH >= 1), \
 330             "ASID width must be at least 1"
 331
 332         return m
 333
 334         """
 335         # Just for checking
 336         function int countSetBits(logic[TLB_ENTRIES-1:0] vector);
 337           automatic int count = 0;
 338           foreach (vector[idx]) begin
 339             count += vector[idx];
 340           end
 341           return count;
 342         endfunction
 343
 344         assert property (@(posedge clk_i)(countSetBits(lu_hit) <= 1))
 345           else $error("More then one hit in TLB!"); $stop(); end
 346         assert property (@(posedge clk_i)(countSetBits(replace_en) <= 1))
 347           else $error("More then one TLB entry selected for next replace!");
 348         """
 349
 350     def ports(self):
 351         return [self.flush_i, self.lu_access_i,
 352                  self.lu_asid_i, self.lu_vaddr_i,
 353                  self.lu_is_2M_o, self.lu_is_1G_o, self.lu_hit_o,
 354                 ] + self.lu_content_o.ports() + self.update_i.ports()
 355
 356 if __name__ == '__main__':
 357     tlb = TLB()
 358     vl = rtlil.convert(tlb, ports=tlb.ports())
 359     with open("test_tlb.il", "w") as f:
 360         f.write(vl)
 361