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