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