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 log
  19
  20 # SV39 defines three levels of page tables
  21 class TLBEntry:
  22     def __init__(self):
  23         self.asid = Signal(ASID_WIDTH)
  24         self.vpn2 = Signal(9)
  25         self.vpn1 = Signal(9)
  26         self.vpn0 = Signal(9)
  27         self.is_2M = Signal()
  28         self.is_1G = Signal()
  29         self.valid = Signal()
  30
  31 TLB_ENTRIES = 4
  32 ASID_WIDTH  = 1
  33
  34 from .tlb import TLBUpdate, PTE
  35
  36 module tlb #(
  37   )(
  38     flush_i = Signal(),  # Flush signal
  39     # Update TLB
  40     update_i = TLBUpdate()
  41     # Lookup signals
  42     lu_access_i = Signal()
  43     lu_asid_i = Signal(ASID_WIDTH)
  44     lu_vaddr_i = Signal(64)
  45     lu_content_o = PTE()
  46     lu_is_2M_o = Signal()
  47     lu_is_1G_o = Signal()
  48     lu_hit_o = Signal()
  49 )
  50
  51     tags = TLBEntry()
  52     # SV39 defines three levels of page tables
  53
  54     content = Array([TLB() for i in range(TLB_ENTRIES)])
  55
  56     vpn2 = Signal(9)
  57     vpn1 = Signal(9)
  58     vpn0 = Signal(9)
  59     lu_hit = Signal(TLB_ENTRIES)     # to replacement logic
  60     replace_en = Signal(TLB_ENTRIES) # replace the following entry,
  61                                      # set by replacement strategy
  62     #-------------
  63     # Translation
  64     #-------------
  65         m.d.comb += [ vpn0.eq(lu_vaddr_i[12:21],
  66                       vpn1.eq(lu_vaddr_i[21:30],
  67                       vpn2.eq(lu_vaddr_i[30:39]
  68                     ]
  69
  70         for i in range(TLB_ENTRIES):
  71             m.d.comb += lu_hit[i].eq(0)
  72             # first level match, this may be a giga page,
  73             # check the ASID flags as well
  74             with m.If(tags[i].valid & \
  75                       tags[i].asid == lu_asid_i &  \
  76                       tags[i].vpn2 == vpn2):
  77                 # second level
  78                 with m.If (tags[i].is_1G):
  79                     m.d.sync += lu_content_o.eq(content[i])
  80                     m.d.comb += [ lu_is_1G_o.eq(1),
  81                                   lu_hit_o.eq(1),
  82                                   lu_hit[i].eq(1),
  83                                 ]
  84                 # not a giga page hit so check further
  85                 with m.Elif(vpn1 == tags[i].vpn1):
  86                     # this could be a 2 mega page hit or a 4 kB hit
  87                     # output accordingly
  88                     with m.If(tags[i].is_2M | vpn0 == tags[i].vpn0):
  89                         m.d.sync += lu_content_o.eq(content[i])
  90                         m.d.comb += [ lu_is_2M_o.eq(tags[i].is_2M),
  91                                       lu_hit_o.eq(1),
  92                                       lu_hit[i].eq(1),
  93                                     ]
  94
  95     # ------------------
  96     # Update and Flush
  97     # ------------------
  98
  99         for i in range(TLB_ENTRIES):
 100             with m.If (flush_i):
 101                 # invalidate logic: flush conditions
 102                 with m.If ((lu_asid_i == Const(0, ASID_WIDTH) | # all if zero
 103                            (lu_asid_i == tags[i].asid):       # just this ASID
 104                     m.d.sync += tags[i].valid.eq(0)
 105
 106             # normal replacement
 107             with m.Elif(update_i.valid & replace_en[i]):
 108                 m.d.sync += [ # update tag array
 109                               tags[i].asid.eq(update_i.asid),
 110                               tags[i].vpn2.eq(update_i.vpn [18:27]),
 111                               tags[i].vpn1.eq(update_i.vpn [9:18]),
 112                               tags[i].vpn0.eq(update_i.vpn[0:9]),
 113                               tags[i].is_1G.eq(update_i.is_1G),
 114                               tags[i].is_2M.eq(update_i.is_2M),
 115                               tags[i].valid.eq(1),
 116                               # and content as well
 117                               content[i].eq(update_i.content)
 118                             ]
 119
 120     # -----------------------------------------------
 121     # PLRU - Pseudo Least Recently Used Replacement
 122     # -----------------------------------------------
 123         TLBSZ = 2*(TLB_ENTRIES-1)
 124         plru_tree = Signal(TLBSZ)
 125
 126         # The PLRU-tree indexing:
 127         # lvl0        0
 128         #            / \
 129         #           /   \
 130         # lvl1     1     2
 131         #         / \   / \
 132         # lvl2   3   4 5   6
 133         #       / \ /\/\  /\
 134         #      ... ... ... ...
 135         # Just predefine which nodes will be set/cleared
 136         # E.g. for a TLB with 8 entries, the for-loop is semantically
 137         # equivalent to the following pseudo-code:
 138         # unique case (1'b1)
 139         # lu_hit[7]: plru_tree[0, 2, 6] = {1, 1, 1};
 140         # lu_hit[6]: plru_tree[0, 2, 6] = {1, 1, 0};
 141         # lu_hit[5]: plru_tree[0, 2, 5] = {1, 0, 1};
 142         # lu_hit[4]: plru_tree[0, 2, 5] = {1, 0, 0};
 143         # lu_hit[3]: plru_tree[0, 1, 4] = {0, 1, 1};
 144         # lu_hit[2]: plru_tree[0, 1, 4] = {0, 1, 0};
 145         # lu_hit[1]: plru_tree[0, 1, 3] = {0, 0, 1};
 146         # lu_hit[0]: plru_tree[0, 1, 3] = {0, 0, 0};
 147         # default: begin /* No hit */ end
 148         # endcase
 149         LOG_TLB = int(log2(TLB_ENTRIES))
 150         for i in range(TLB_ENTRIES):
 151             # we got a hit so update the pointer as it was least recently used
 152             with m.If (lu_hit[i] & lu_access_i):
 153                 # Set the nodes to the values we would expect
 154                 for lvl in range(LOG_TLB):
 155                     idx_base = (1<<lvl)-1
 156                     # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 157                     shift = LOG_TLB - lvl;
 158                     new_idx = Const(~((i >> (shift-1)) & 1)
 159                     m.d.sync += plru_tree[idx_base + (i >> shift)].eq(new_idx)
 160
 161         # Decode tree to write enable signals
 162         # Next for-loop basically creates the following logic for e.g.
 163         # an 8 entry TLB (note: pseudo-code obviously):
 164         # replace_en[7] = &plru_tree[ 6, 2, 0]; #plru_tree[0,2,6]=={1,1,1}
 165         # replace_en[6] = &plru_tree[~6, 2, 0]; #plru_tree[0,2,6]=={1,1,0}
 166         # replace_en[5] = &plru_tree[ 5,~2, 0]; #plru_tree[0,2,5]=={1,0,1}
 167         # replace_en[4] = &plru_tree[~5,~2, 0]; #plru_tree[0,2,5]=={1,0,0}
 168         # replace_en[3] = &plru_tree[ 4, 1,~0]; #plru_tree[0,1,4]=={0,1,1}
 169         # replace_en[2] = &plru_tree[~4, 1,~0]; #plru_tree[0,1,4]=={0,1,0}
 170         # replace_en[1] = &plru_tree[ 3,~1,~0]; #plru_tree[0,1,3]=={0,0,1}
 171         # replace_en[0] = &plru_tree[~3,~1,~0]; #plru_tree[0,1,3]=={0,0,0}
 172         # For each entry traverse the tree. If every tree-node matches
 173         # the corresponding bit of the entry's index, this is
 174         # the next entry to replace.
 175         for i in range(TLB_ENTRIES):
 176             en = [Const(1)]
 177             for lvl in range(LOG_TLB):
 178                 idx_base = (1<<lvl)-1
 179                 # lvl0 <=> MSB, lvl1 <=> MSB-1, ...
 180                 shift = LOG_TLB - lvl;
 181                 new_idx = (i >> (shift-1)) & 1;
 182                 plru = plru_tree[idx_base + (i>>shift)]
 183                 # en &= plru_tree_q[idx_base + (i>>shift)] == new_idx;
 184                 if new_idx:
 185                     en.append(~plru) # yes inverted (using bool())
 186                 else:
 187                     en.append(plru)  # yes inverted (using bool())
 188             # boolean logic manipluation:
 189             # plur0 & plru1 & plur2 == ~(~plru0 | ~plru1 | ~plru2)
 190             m.d.sync += replace_en[i].eq(~Cat(*en).bool())
 191
 192     #--------------
 193     # Sanity checks
 194     #--------------
 195
 196     assert (TLB_ENTRIES % 2 == 0) and (TLB_ENTRIES > 1)), \
 197         "TLB size must be a multiple of 2 and greater than 1"
 198     assert (ASID_WIDTH >= 1),
 199         "ASID width must be at least 1")
 200
 201     """
 202     # Just for checking
 203     function int countSetBits(logic[TLB_ENTRIES-1:0] vector);
 204       automatic int count = 0;
 205       foreach (vector[idx]) begin
 206         count += vector[idx];
 207       end
 208       return count;
 209     endfunction
 210
 211     assert property (@(posedge clk_i)(countSetBits(lu_hit) <= 1))
 212       else begin $error("More then one hit in TLB!"); $stop(); end
 213     assert property (@(posedge clk_i)(countSetBits(replace_en) <= 1))
 214       else begin $error("More then one TLB entry selected for next replace!");
 215     """
 216