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         m.d.comb += [ vpn0.eq(self.lu_vaddr_i[12:21]),
 270                       vpn1.eq(self.lu_vaddr_i[21:30]),
 271                       vpn2.eq(self.lu_vaddr_i[30:39]),
 272                     ]
 273
 274         # SV39 defines three levels of page tables
 275         tc = []
 276         for i in range(TLB_ENTRIES):
 277             tlc = TLBContent(self.pte_width)
 278             setattr(m.submodules, "tc%d" % i, tlc)
 279             tc.append(tlc)
 280             # connect inputs
 281             tlc.update_i = self.update_i     # saves a lot of graphviz links
 282             m.d.comb += [tlc.vpn0.eq(vpn0),
 283                          tlc.vpn1.eq(vpn1),
 284                          tlc.vpn2.eq(vpn2),
 285                          tlc.flush_i.eq(self.flush_i),
 286                          #tlc.update_i.eq(self.update_i),
 287                          tlc.lu_asid_i.eq(self.lu_asid_i)]
 288         tc = Array(tc)
 289
 290         #--------------
 291         # Select hit
 292         #--------------
 293
 294         # use Encoder to select hit index
 295         # XXX TODO: assert that there's only one valid entry (one lu_hit)
 296         hitsel = Encoder(TLB_ENTRIES)
 297         m.submodules.hitsel = hitsel
 298
 299         hits = []
 300         for i in range(TLB_ENTRIES):
 301             hits.append(tc[i].lu_hit_o)
 302         m.d.comb += hitsel.i.eq(Cat(*hits))
 303         idx = hitsel.o
 304
 305         active = Signal(reset_less=True)
 306         m.d.comb += active.eq(~hitsel.n)
 307         with m.If(active):
 308             # active hit, send selected as output
 309             m.d.comb += [ self.lu_is_1G_o.eq(tc[idx].lu_is_1G_o),
 310                           self.lu_is_2M_o.eq(tc[idx].lu_is_2M_o),
 311                           self.lu_hit_o.eq(1),
 312                           self.lu_content_o.flatten().eq(tc[idx].lu_content_o),
 313                         ]
 314
 315         #--------------
 316         # PLRU.
 317         #--------------
 318
 319         p = PLRU()
 320         m.submodules.plru = p
 321
 322         # connect PLRU inputs/outputs
 323         # XXX TODO: assert that there's only one valid entry (one replace_en)
 324         en = []
 325         for i in range(TLB_ENTRIES):
 326             en.append(tc[i].replace_en_i)
 327         m.d.comb += [Cat(*en).eq(p.replace_en_o), # output from PLRU into tags
 328                      p.lu_hit.eq(hitsel.i),
 329                      p.lu_access_i.eq(self.lu_access_i)]
 330
 331         #--------------
 332         # Sanity checks
 333         #--------------
 334
 335         assert (TLB_ENTRIES % 2 == 0) and (TLB_ENTRIES > 1), \
 336             "TLB size must be a multiple of 2 and greater than 1"
 337         assert (ASID_WIDTH >= 1), \
 338             "ASID width must be at least 1"
 339
 340         return m
 341
 342         """
 343         # Just for checking
 344         function int countSetBits(logic[TLB_ENTRIES-1:0] vector);
 345           automatic int count = 0;
 346           foreach (vector[idx]) begin
 347             count += vector[idx];
 348           end
 349           return count;
 350         endfunction
 351
 352         assert property (@(posedge clk_i)(countSetBits(lu_hit) <= 1))
 353           else $error("More then one hit in TLB!"); $stop(); end
 354         assert property (@(posedge clk_i)(countSetBits(replace_en) <= 1))
 355           else $error("More then one TLB entry selected for next replace!");
 356         """
 357
 358     def ports(self):
 359         return [self.flush_i, self.lu_access_i,
 360                  self.lu_asid_i, self.lu_vaddr_i,
 361                  self.lu_is_2M_o, self.lu_is_1G_o, self.lu_hit_o,
 362                 ] + self.lu_content_o.ports() + self.update_i.ports()
 363
 364 if __name__ == '__main__':
 365     tlb = TLB()
 366     vl = rtlil.convert(tlb, ports=tlb.ports())
 367     with open("test_tlb.il", "w") as f:
 368         f.write(vl)
 369