MMU description » History » Revision 131
Revision 130 (Alexander Kamkin, 02/13/2015 09:40 AM) → Revision 131/132 (Alexander Kamkin, 02/13/2015 10:07 AM)
h1. MMU Description
_~By Alexander Kamkin, Taya Sergeeva, and Andrei Tatarnikov~_
{{toc}}
A _memory management unit_ (_MMU_) is known to be one of the most complex and error-prone components of a modern microprocessor. MicroTESK has a special subsystem, called _MMU subsystem_, intended for (1) specifying memory devices and (2) deriving testing knowledge from such specifications. The subsystem provides unified facilities for describing memory buffers (like _L1_ and _L2 caches_, _translation look-aside buffers_ (_TLBs_), etc.) as well as a means for connecting several buffers into a memory hierarchy.
h2. Grammar
<pre>
startRule
: declaration* EOF!
;
declaration
: address
| segment
| buffer
| mmu
;
</pre>
The expression syntax is derived from nML/Sim-nML (see [[Sim-nML Language Reference]]).
h2. Address Description (address)
A buffer is accessed by an _address_, which is typically a _bit vector_ of a fixed length (width). Different buffers are allowed to have a common address space (e.g., L1 and L2 are usually both addressed by physical addresses). However, in general case, each buffer has its own domain.
An address space is described using a keyword @address@. The description includes the address type _identifier_ and the address _width_. The latter is specified in brackets. Its value should be non-negative (zero-length addresses are permitted).
h3. Grammar
<pre>
address
: ''address'' addressTypeID ''('' expr '')''
;
</pre>
h3. Examples
<pre>// A 64-bit virtual address (VA).
address VA(64)</pre>
<pre>// A 36-bit physical address (PA).
address PA(36)</pre>
h2. Address Space Segment Description (segment)
An address space segment is specified using the @segment@ keyword. A segment is associated with a specific address type. It is possible to specify any number (≥ 0) of segments (with different names) for one address type. Each segment is characterized by its _identifier_ and _address range_. Different segments should have different names, but address ranges are allowed to overlap, and moreover, to be the same.
h3. Grammar
<pre>
segment
: ''segment'' segmentID ''('' argumentID '':'' addressTypeID '')''
''range'' ''='' ''('' expr '','' expr '')''
;
</pre>
h3. Examples
<pre>
segment USEG (va: VA)
range = (0x0000000000000000, 0x000000007fffffff)
</pre>
h2. Buffer Description (buffer)
A buffer is described using a keyword @buffer@. The description specifies a set of parameters, including @ways@, @sets@, @entry@, @index@, @match@ and @policy@. All of the parameters except @index@ (if @sets = 1@) and @policy@ are obligatory.
h3. Grammar
<pre>
buffer
: ''buffer'' bufferTypeID ''('' addressArgID '':'' addressTypeID '')''
(bufferParameter)*
;
bufferParameter
: ways
| sets
| entry
| index
| match
| policy
;
</pre>
h3. Buffer Associativity (ways)
The @ways@ parameter specifies the buffer _associativity_ (the number of lines in a set). The parameter is obligatory; its value should be positive.
h4. Grammar
<pre>
ways
: ''ways'' ''='' expr
;
</pre>
h3. Buffer Length (sets)
The @sets@ parameter specifies the buffer _length_ (the number of sets a cache). The parameter is obligatory; its value should be positive.
h4. Grammar
<pre>
sets
: ''sets'' ''='' expr
;
</pre>
h3. Buffer Line Format (entry)
The @entry@ parameter specifies the buffer _line format_ (a number of named fields). A field has three attributes: a name, a width and, optionally, an initial value.
h4. Grammar
<pre>
format
: ''entry'' ''='' ''('' field ('','' field)* '')''
;
field
: fieldID '':'' expr (''='' expr)?
;
</pre>
h3. Buffer Index Function (index)
The @index@ parameter specifies the _address-to-index function_, which maps an address into the set index. The function may be omitted if the number of sets is @1@.
h4. Grammar
<pre>
index
: ''index'' ''='' expr
;
</pre>
h3. Buffer Match Predicate (match)
The @match@ parameter specifies the _address-line match predicate_, which checks if an address matches a line. The parameter is obligatory.
h4. Grammar
<pre>
index
: ''match'' ''='' expr
;
</pre>
h3. Buffer Data Replacement Policy (policy)
The @policy@ parameters specifies the _data replacement_ (_eviction_) _policy_. The parameter is optional. The list of supported policies includes: @RANDOM@, @FIFO@, @PLRU@ and @LRU@.
h4. Grammar
<pre>
policy
: ''policy'' ''='' policyID
;
</pre>
h3. Examples
<pre>
// A 4-way set associative cache (L1) addressed by physical addresses (PA).
buffer L1(addr: PA)
// The cache associativity.
ways = 4
// The number of sets.
sets = 128
// The line format.
entry = (
V : 1 = 0, // The validity flag (by default, the line is invalid).
TAG : 24, // The tag (the <35..12> address bits).
DATA : 256 // The data (4 double words).
)
// The address-to-index function (example: using address fields).
index = addr.INDEX
// The address-line predicate (example: using address bits).
match = addr<35..12> == TAG
// The data replacement policy (example: using predefined policy LRU - Least Recently Used).
policy = LRU
</pre>
h2. MMU Description (mmu)
Memory management unit logic is described using the @mmu@ keyword. The description includes two obligatory parameters @read@ and @write@ that describe the semantics of memory read and memory write actions respectively.
h3. Grammar
<pre>
mmu
: ''mmu'' memoryTypeID ''('' addressArgID '':'' addressTypeID '')'' = dataArgID
(mmuVariable)*
(mmuParameter)*
;
mmuVariable
: ''var'' variableID '':'' variableTypeID (''.'' ''entry'')? '';''
;
mmuParameter
: read
| write
;
</pre>
h3. Memory Read Action (read)
The @read@ parameter specifies the _read action_, which is a sequence of statements describing how the read operation is to be performed (by means of data transfers between buffers). The parameter is obligatory.
h4. Grammar
<pre>
read
: ''read'' ''='' ''{'' sequence ''}''
;
</pre>
h3. Memory Write Action (write)
The @write@ parameter specifies the _read action_, which is a sequence of statements describing how the write operation is to be performed (by means of data transfers between buffers). The parameter is obligatory.
h4. Grammar
<pre>
write
: ''write'' ''='' ''{'' sequence ''}''
;
</pre>
h3. Examples
<pre>
// A memory unit addressed by virtual addresses (VA).
mmu Memory(addr: VA) = data
// The read action.
read = {
// Some statements.
...
}
// The write action.
write = {
// Some statements.
...
}
</pre>
h2. Simplified Specification of MIPS''s MMU
<pre>
//==================================================================================================
// Virtual Address (VA)
//==================================================================================================
address VA(64)
//--------------------------------------------------------------------------------------------------
// User Mode Segments
//--------------------------------------------------------------------------------------------------
segment USEG (va: VA)
range = (0x0000000000000000, 0x000000007fffffff)
segment XUSEG(va: VA)
range = (0x0000000080000000, 0x000000ffffffffff)
//--------------------------------------------------------------------------------------------------
// Supervisor Mode Segments
//--------------------------------------------------------------------------------------------------
segment SUSEG(va: VA)
range = (0x0000000000000000, 0x000000007fffffff)
segment XSUSEG(va: VA)
range = (0x0000000080000000, 0x000000ffffffffff)
segment XSSEG(va: VA)
range = (0x4000000000000000, 0x400000ffffffffff)
segment CSSEG(va: VA)
range = (0xffffffffc0000000, 0xffffffffdfffffff)
//--------------------------------------------------------------------------------------------------
// Kernel Mode Segments
//--------------------------------------------------------------------------------------------------
segment KUSEG (va: VA)
range = (0x0000000000000000, 0x000000007fffffff)
segment XKUSEG (va: VA)
range = (0x0000000080000000, 0x000000ffffffffff)
segment XKSSEG (va: VA)
range = (0x4000000000000000, 0x400000ffffffffff)
segment XKSEG (va: VA)
range = (0xc000000000000000, 0xc00000ff7fffffff)
segment CKSSEG (va: VA)
range = (0xffffffffc0000000, 0xffffffffdfffffff)
segment CKSEG3(va: VA)
range = (0xffffffffe0000000, 0xffffffffffffffff)
//==================================================================================================
// Physical Address (PA)
//==================================================================================================
address PA(36)
//==================================================================================================
// Translation Lookaside Buffer (TLB)
//==================================================================================================
buffer DTLB (va: VA)
ways = 4
sets = 1
entry = (ASID: 8, VPN2: 27, R: 2, // EntryHi
G0: 1, V0: 1, D0: 1, C0: 3, PFN0: 24, // EntryLo0
G1: 1, V1: 1, D1: 1, C1: 3, PFN1: 24) // EntryLo1
index = 0
match = VPN2 == va<39..13> // ASID, G and non-4KB non-4FB pages are unsupported
policy = PLRU
buffer JTLB (va: VA)
ways = 64
sets = 1
entry = (ASID: 8, VPN2: 27, R: 2, // EntryHi
G0: 1, V0: 1, D0: 1, C0: 3, PFN0: 24, // EntryLo0
G1: 1, V1: 1, D1: 1, C1: 3, PFN1: 24) // EntryLo1
index = 0
match = VPN2 == va<39..13> // ASID, G and non-4KB non-4FB pages are unsupported
policy = NONE
//==================================================================================================
// Cache Memory (L1 and L2)
//==================================================================================================
buffer L1 (pa: PA)
ways = 4
sets = 128
entry = (V: 1 = 0, TAG: 24, DATA: 256)
index = pa<11..5>
match = V == 1 && TAG == pa<35..12>
policy = PLRU
buffer L2 (pa: PA)
ways = 4
sets = 4096
entry = (V: 1 = 0, TAG: 19, DATA: 256)
index = pa<16..5>
match = V == 1 && TAG == pa<35..17>
policy = PLRU
//==================================================================================================
// MMU Logic (Interaction between TLB, L1 and L2)
//==================================================================================================
mmu pmem(va: VA) = (data: 64)
var tlbEntry: JTLB.entry;
var l1Entry: L1.entry;
var l2Entry: L2.entry;
var evenOddBit: 5;
var g: 1;
var v: 1;
var d: 1;
var c: 3;
var pfn: 24;
var pa: PA;
var cachePA: PA;
var cacheData: 256;
read = {
// The address is unaligned.
if va<0..2> != 0 then
exception("AddressError");
endif; // If the address is unaligned.
// The default cache policy.
c = 3;
// The address is from the USEG segment (only USEG and KSEG segments are supported).
if USEG(va).hit then
// The address hits the DTLB.
if DTLB(va).hit then
tlbEntry = DTLB(va);
// The address hits the JTLB.
elif JTLB(va).hit then
tlbEntry = JTLB(va);
// The address does not hit the TLB.
else
exception("TLBMiss");
endif; // If the address hits the DTLB.
// Only 4KB pages are supported.
evenOddBit = 12;
// The VPN is even.
if va<evenOddBit> == 0 then
g = tlbEntry.G0;
v = tlbEntry.V0;
d = tlbEntry.D0;
c = tlbEntry.C0;
pfn = tlbEntry.PFN0;
// The VPN is odd.
else
g = tlbEntry.G1;
v = tlbEntry.V1;
d = tlbEntry.D1;
c = tlbEntry.C1;
pfn = tlbEntry.PFN1;
endif; // If the VPN is even.
// The EntryLo is valid.
if v == 1 then
pa = pfn<24..(evenOddBit - 12)>::va<(evenOddBit - 1)..0>;
// The EntryLo is invalid.
else
exception("TLBInvalid");
endif; // If the EntryLo is valid.
// The address is from the KSEG0 or KSEG1 segment.
else
pa = va<28..0>;
endif; // If the address is from the USEG segment.
// The address is cacheable.
if c<1..0> != 2 then
cachePA = pa;
cachePA<4..0> = 0;
// The address hits the L1.
if L1(pa).hit then
l1Entry = L1(pa);
cacheData = l1Entry.DATA;
data = cacheData<(8 * pa<4..0> + 63)..(8 * pa<4..0>)>;
// The address does not hit the L1.
else
// The L2 cache is used.
if c<1..0> == 3 then
// The address hits the L2.
if L2(pa).hit then
l2Entry = L2(pa);
cacheData = l2Entry.DATA;
data = cacheData<(8 * pa<4..0> + 63)..(8 * pa<4..0>)>;
// Fill the L1.
l1Entry.V = 1;
l1Entry.TAG = pa<35..12>;
l1Entry.DATA = cacheData;
L1(pa) = l1Entry;
// The address does not hit the L2.
else
cacheData = pmem[cachePA + 24]::pmem[cachePA + 16]::pmem[cachePA + 8]::pmem[cachePA];
data = cacheData<(8 * pa<4..0> + 63)..(8 * pa<4..0>)>;
// Fill L2.
l2Entry.V = 1;
l2Entry.TAG = pa<35..17>;
l2Entry.DATA = cacheData;
L2(pa) = l2Entry;
// Fill L1.
l1Entry.V = 1;
l1Entry.TAG = pa<35..12>;
l1Entry.DATA = cacheData;
L1(pa) = l1Entry;
endif; // If the address hits the L2.
// The L2 cache is bypassed.
else
cacheData = pmem[cachePA + 24]::pmem[cachePA + 16]::pmem[cachePA + 8]::pmem[cachePA];
data = cacheData<(8 * pa<4..0> + 63)..(8 * pa<4..0>)>;
l1Entry.V = 1;
l1Entry.TAG = pa<35..12>;
l1Entry.DATA = cacheData;
L1(pa) = l1Entry;
endif; // If the L2 cache is used.
endif; // If the address hits the L1.
// The address is uncacheable.
else
data = pmem[pa];
endif; // If the address is cacheable.
}
write = {
// The address is unaligned.
if va<0..2> != 0 then
exception("AddressError");
endif; // If the address is unaligned.
// The default cache policy.
c = 3;
// The address is from the USEG segment (only USEG and KSEG segments are supported).
if USEG(va).hit then
// The address hits the DTLB.
if DTLB(va).hit then
tlbEntry = DTLB(va);
// The address hits the JTLB.
elif JTLB(va).hit then
tlbEntry = JTLB(va);
// The address does not hit the TLB.
else
exception("TLBMiss");
endif; // If the address hits the DTLB.
// Only 4KB pages are supported.
evenOddBit = 12;
// The VPN is even.
if va<evenOddBit> == 0 then
g = tlbEntry.G0;
v = tlbEntry.V0;
d = tlbEntry.D0;
c = tlbEntry.C0;
pfn = tlbEntry.PFN0;
// The VPN is odd.
else
g = tlbEntry.G1;
v = tlbEntry.V1;
d = tlbEntry.D1;
c = tlbEntry.C1;
pfn = tlbEntry.PFN1;
endif; // If the VPN is even.
// The EntryLo is valid.
if v == 1 then
// The EntryLo is clean.
if d == 1 then
pa = pfn<24..(evenOddBit - 12)>::va<(evenOddBit - 1)..0>;
// The EntryLo is dirty.
else
exception("TLBModified");
endif; // If the EntryLo is clean.
// The EntryLo is invalid.
else
exception("TLBInvalid");
endif; // If the EntryLo is valid.
// The address is from the KSEG0 or KSEG1 segment.
else
pa = va<28..0>;
endif; // If the address is from the USEG segment.
// The address is cacheable.
if c<1..0> != 2 then
cachePA = pa;
cachePA<4..0> = 0;
// The address hits the L1.
if L1(pa).hit then
// Update the L1.
l1Entry = L1(pa);
l1Entry.DATA<(8 * pa<4..0> + 63)..(8 * pa<4..0>)> = data;
L1(pa) = l1Entry;
// Only the write-through policy is supported.
pmem[pa] = data;
// The address does not hit the L1.
else
// The L2 cache is used.
if c<1..0> == 3 then
// The address hits the L2.
if L2(pa).hit then
// Update the L2.
l2Entry = L2(pa);
l2Entry.DATA<(8 * pa<4..0> + 63)..(8 * pa<4..0>)> = data;
L2(pa) = l2Entry;
// Fill the L1.
l1Entry.V = 1;
l1Entry.TAG = pa<35..12>;
l1Entry.DATA = l2Entry.DATA;
L1(pa) = l1Entry;
// Only the write-through policy is supported.
pmem[pa] = data;
// The address does not hit the L2.
else
pmem[pa] = data;
cacheData = pmem[cachePA + 24]::pmem[cachePA + 16]::pmem[cachePA + 8]::pmem[cachePA];
// Fill the L2.
l2Entry.V = 1;
l2Entry.TAG = pa<35..17>;
l2Entry.DATA = cacheData;
L2(pa) = l2Entry;
// Fill the L1.
l1Entry.V = 1;
l1Entry.TAG = pa<35..12>;
l1Entry.DATA = cacheData;
L1(pa) = l1Entry;
endif; // If the address hits the L2.
// The L2 cache is bypassed.
else
pmem[pa] = data;
cacheData = pmem[cachePA + 24]::pmem[cachePA + 16]::pmem[cachePA + 8]::pmem[cachePA];
// Fill the L2
l1Entry.V = 1;
l1Entry.TAG = pa<35..12>;
l1Entry.DATA = cacheData;
L1(pa) = l1Entry;
endif; // If the L2 cache is used.
endif; // If the address hits the L1.
// The address is uncacheable.
else
pmem[pa] = data;
endif; // If the address is cacheable.
}
//==================================================================================================
// The End
//==================================================================================================
</pre>