3b91b0b8a0d9d3a1ffaeb72813f1947b74f9487f
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.
12 # Author: David Schaffenrath, TU Graz
13 # Author: Florian Zaruba, ETH Zurich
15 # Description: Translation Lookaside Buffer, SV39
16 # fully set-associative
18 Implementation in c++:
19 https://raw.githubusercontent.com/Tony-Hu/TreePLRU/master/TreePLRU.cpp
22 https://people.cs.clemson.edu/~mark/464/p_lru.txt
25 from nmigen
import Signal
, Module
, Cat
, Const
, Array
26 from nmigen
.cli
import verilog
, rtlil
27 from nmigen
.lib
.coding
import Encoder
29 from ptw
import TLBUpdate
, PTE
, ASID_WIDTH
36 self
.asid
= Signal(ASID_WIDTH
)
37 # SV39 defines three levels of page tables
46 return Cat(*self
.ports())
49 return self
.flatten().eq(x
.flatten())
52 return [self
.asid
, self
.vpn0
, self
.vpn1
, self
.vpn2
,
53 self
.is_2M
, self
.is_1G
, self
.valid
]
57 def __init__(self
, pte_width
):
58 self
.pte_width
= pte_width
59 self
.flush_i
= Signal() # Flush signal
61 self
.update_i
= TLBUpdate()
65 self
.replace_en_i
= Signal() # replace the following entry,
66 # set by replacement strategy
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()
74 def elaborate(self
, platform
):
78 content
= Signal(self
.pte_width
)
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)]
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
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),
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
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
),
125 replace_valid
= Signal(reset_less
=True)
126 m
.d
.comb
+= replace_valid
.eq(self
.update_i
.valid
& self
.replace_en_i
)
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)
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
),
145 # and content as well
146 content
.eq(self
.update_i
.content
.flatten())
151 return [self
.flush_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()
158 """ PLRU - Pseudo Least Recently Used Replacement
171 self
.lu_hit
= Signal(TLB_ENTRIES
)
172 self
.replace_en_o
= Signal(TLB_ENTRIES
)
173 self
.lu_access_i
= Signal()
175 def elaborate(self
, platform
):
178 # Tree (bit per entry)
179 TLBSZ
= 2*(TLB_ENTRIES
-1)
180 plru_tree
= Signal(TLBSZ
)
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:
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
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
)
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
)
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.
228 for i
in range(TLB_ENTRIES
):
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;
241 en
.append(~plru
) # yes inverted (using bool())
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
))
255 self
.flush_i
= Signal() # Flush signal
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()
265 self
.pte_width
= len(self
.lu_content_o
.flatten())
266 self
.update_i
= TLBUpdate()
268 def elaborate(self
, platform
):
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]),
286 for i
in range(TLB_ENTRIES
):
287 tlc
= TLBContent(self
.pte_width
)
288 setattr(m
.submodules
, "tc%d" % i
, tlc
)
291 tlc
.update_i
= self
.update_i
# saves a lot of graphviz links
292 m
.d
.comb
+= [tlc
.vpn0
.eq(vpn0
),
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
)]
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
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)
315 active
= Signal(reset_less
=True)
316 m
.d
.comb
+= active
.eq(~hitsel
.n
)
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
),
322 self
.lu_content_o
.flatten().eq(tc
[idx
].lu_content_o
),
330 m
.submodules
.plru
= p
332 # connect PLRU inputs/outputs
333 # XXX TODO: assert that there's only one valid entry (one replace_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
)]
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"
354 function int countSetBits(logic[TLB_ENTRIES-1:0] vector);
355 automatic int count = 0;
356 foreach (vector[idx]) begin
357 count += vector[idx];
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!");
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()
374 if __name__
== '__main__':
376 vl
= rtlil
.convert(tlb
, ports
=tlb
.ports())
377 with
open("test_tlb.il", "w") as f
: