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