1 using System;
  2 using System.Collections;
  3 
  4 namespace cmsx.machine
  5 {
  6     public enum Protection : byte
  7     {
  8         notPresent = 0u, 
  9         execute = 1u << 0u, 
 10         write = 1u << 1u, 
 11         read = 1u << 2u, 
 12         copyOnWrite = execute | write | read
 13     }
 14 
 15     public const byte textSegmentIndex = 0u;
 16     public const byte dataSegmentIndex = 1u;
 17     public const byte poolSegmentIndex = 2u;
 18     public const byte stackSegmentIndex = 3u;
 19     public const byte numSegments = 4u;
 20     public const ulong pageSize = 0x1000u;
 21     public const ulong pageOffsetMask = 0x0FFFu;
 22     public const byte pageOffsetBits = 12u;
 23     public const ushort numPtesInPage = 512u;
 24     public const ushort numDirectTranslationCaches = 16u;
 25     public const int numTranslationCacheEntries = 4096;
 26     public const ulong translationCacheIndexMask = (4096u / numSegments) - 1u;
 27     public const int numTranslationCacheIndexSegmentEntries = 1024;
 28     public const ushort numSegmentPageEntriesInRootPage = numPtesInPage / numSegments;
 29     public const ushort numDirectEntries = numSegmentPageEntriesInRootPage - 3u;
 30     public const ushort pteOffsetMask = 0x1FFu;
 31     //public const ushort pteOffsetMask = 0x3u; 
 32     public const byte numPteBits = 9u;
 33     //public const byte numPteBits = 2u;
 34     public const ushort maxDigit = 511u;
 35     //public const ushort maxDigit = 3u;
 36     public const ulong textSegmentBaseAddress = 0x0000000000000000u;
 37     public const ulong dataSegmentBaseAddress = 0x2000000000000000u;
 38     public const ulong poolSegmentBaseAddress = 0x4000000000000000u;
 39     public const ulong stackSegmentBaseAddress = 0x6000000000000000u;
 40     public const ulong kernelBaseAddress = 0x8000000000000000u;
 41     public const ushort kernelAddressSpaceNumber = 0u;
 42     public const ulong invalidAddress = cast<ulong>(-1);
 43     public const byte segmentNumberShift = 61u;
 44     public const byte segmentNumberMask = 0x03u;
 45     public const ulong m2Mask = ~cast<ulong>(1u);
 46     public const ulong m4Mask = ~cast<ulong>(3u);
 47     public const ulong m8Mask = ~cast<ulong>(7u);
 48     public const byte numAddressSpaceBits = 10u;
 49     public const ulong addressSpaceMask = (cast<ulong>(1u) << numAddressSpaceBits) - 1u;
 50     public const ulong invalidAddrSpaceMask = ~addressSpaceMask;
 51     public const byte numProtectionBits = 3u;
 52     public const ulong protectionMask = (cast<ulong>(1u) << numProtectionBits) - 1u;
 53     public const byte numVirtualAddressBits = 48u;
 54     public const ulong virtualAddressBase = cast<ulong>(1u) << numVirtualAddressBits;
 55     public const ulong virtualAddressBaseMask = virtualAddressBase - 1u;
 56     public const ulong kernelDataBaseAddress = kernelBaseAddress;
 57     public const ulong interruptVectorBaseAddress = kernelDataBaseAddress + dataSegmentBaseAddress + 512u;
 58     public const ulong interruptVectorEndAddress = interruptVectorBaseAddress + cast<ulong>(irqMax) * 8u;
 59     public const int maxTraps = 256;
 60     public const ulong trapTableBaseAddress = interruptVectorEndAddress;
 61     public const ulong trapTableEndAddress = trapTableBaseAddress + cast<ulong>(maxTraps) * 8u;
 62 
 63     private bool useTranslationCache = true;
 64 
 65     public inline nothrow bool UseTranslationCache()
 66     {
 67         return useTranslationCache;
 68     }
 69 
 70     public nothrow bool GetUseTranslationCache()
 71     {
 72         return useTranslationCache;
 73     }
 74 
 75     public nothrow void SetUseTranslationCacheValue(bool use)
 76     {
 77         useTranslationCache = use;
 78     }
 79 
 80     public delegate ulong KernelMaxStackSizeFunction(ushort addressSpaceNumber);
 81     public delegate bool KernelGrowStackFunction(ushort addressSpaceNumber);
 82 
 83     private KernelMaxStackSizeFunction kernelMaxStackSizeFunction;
 84     private KernelGrowStackFunction kernelGrowStackFunction;
 85 
 86     public nothrow void SetKernelMaxStackSizeFunction(KernelMaxStackSizeFunction kernelMaxStackSizeFunction_)
 87     {
 88         kernelMaxStackSizeFunction = kernelMaxStackSizeFunction_;
 89     }
 90 
 91     public nothrow void SetKernelGrowStackFunction(KernelGrowStackFunction kernelGrowStackFunction_)
 92     {
 93         kernelGrowStackFunction = kernelGrowStackFunction_;
 94     }
 95 
 96     public nothrow ulong GetMaxStackSize(ushort addressSpaceNumber)
 97     {
 98         if (cast<void*>(kernelMaxStackSizeFunction) == null)
 99         {
100             return 0u;
101         }
102         else
103         {
104             return kernelMaxStackSizeFunction(addressSpaceNumber);
105         }
106     }
107 
108     public nothrow bool GrowStack(ushort addressSpaceNumber)
109     {
110         if (cast<void*>(kernelGrowStackFunction) == null)
111         {
112             return false;
113         }
114         else
115         {
116             return kernelGrowStackFunction(addressSpaceNumber);
117         }
118     }
119 
120     public class PageFrame
121     {
122         public nothrow PageFrame() : useCount(1u)
123         {
124         }
125         public byte useCount;
126     }
127 
128     public string GetProtectionStr(Protection protection)
129     {
130         string s;
131         if (protection != Protection.notPresent)
132         {
133             if (protection == Protection.copyOnWrite)
134             {
135                 s = s + "COW";
136             }
137             else
138             {
139                 if ((protection & Protection.read) != Protection.notPresent)
140                 {
141                     s = s + "R";
142                 }
143                 if ((protection & Protection.write) != Protection.notPresent)
144                 {
145                     s = s + "W";
146                 }
147                 if ((protection & Protection.execute) != Protection.notPresent)
148                 {
149                     s = s + "X";
150                 }
151             }
152         }
153         else
154         {
155             s = s + "-";
156         }
157         return s;
158     }
159 
160     public nothrow void PrintAddressValues(bool get, ushort addressSpaceNumber, ulong pageAddress, int entryIndex, ulong sourcePageNumber)
161     {
162         string getSetStr = "get";
163         if (!get)
164         {
165             getSetStr = "set";
166         }
167         Console.Out() << getSetStr << ": space=" << addressSpaceNumber << ", page=" << ToHexString(pageAddress) << ", entry=" << entryIndex << ", source=" << ToHexString(sourcePageNumber) << endl();
168     }
169 
170     public inline nothrow ulong GetPageNumber(ulong address)
171     {
172         ulong pageNumber = address / pageSize;
173         return pageNumber;
174     }
175 
176     public inline nothrow ulong MakeVirtualTranslationRegisterValue(ulong rootPageAddress, ushort addressSpaceNumber)
177     {
178         return (rootPageAddress << numAddressSpaceBits) | cast<ulong>(addressSpaceNumber);
179     }
180 
181     public inline nothrow void UnpackVirtualTranslationRegisterValue(ulong virtualTranslationRegisterValue, ulong& rootPageAddress, ushort& addressSpaceNumber)
182     {
183         rootPageAddress = virtualTranslationRegisterValue >> numAddressSpaceBits;
184         addressSpaceNumber = cast<ushort>(virtualTranslationRegisterValue & addressSpaceMask);
185     }
186 
187     public inline nothrow ulong PackProtection(Protection pageProtection, Protection protection)
188     {
189         return (cast<ulong>(cast<byte>(pageProtection)) << 8u) | cast<ulong>(cast<byte>(protection));
190     }
191 
192     public inline nothrow void UnpackProtection(ulong packedValue, Protection& pageProtection, Protection& protection)
193     {
194         protection = cast<Protection>(cast<byte>(packedValue));
195         packedValue = packedValue >> 8u;
196         pageProtection = cast<Protection>(cast<byte>(packedValue));
197     }
198 
199     public inline nothrow ulong MakePageTableEntry(ulong pageAddress, ushort addressSpaceNumber, Protection protection)
200     {
201         ulong pte = (pageAddress << 13u) | (cast<ulong>(addressSpaceNumber) << 3u) | cast<ulong>(cast<byte>(protection));
202         return pte;
203     }
204 
205     public inline nothrow void UnpackPageTableEntry(ulong pte, ulong& pageAddress, ushort& addressSpaceNumber, Protection& protection)
206     {
207         pageAddress = pte >> 13u;
208         addressSpaceNumber = cast<ushort>((pte >> 3u) & addressSpaceMask);
209         protection = cast<Protection>(cast<byte>(pte & protectionMask));
210     }
211 
212     public nothrow Protection MakeDefaultPageProtection(byte segmentIndex)
213     {
214         switch (segmentIndex)
215         {
216             case textSegmentIndex: return cast<Protection>(Protection.read | Protection.execute);
217             case dataSegmentIndex: return cast<Protection>(Protection.read | Protection.write);
218             case poolSegmentIndex: return cast<Protection>(Protection.read | Protection.write);
219             case stackSegmentIndex: return cast<Protection>(Protection.read | Protection.write);
220         }
221         return Protection.notPresent;
222     }
223 
224     public inline nothrow byte GetSegmentIndex(ulong virtualAddress)
225     {
226         return cast<byte>((virtualAddress >> segmentNumberShift) & segmentNumberMask);
227     }
228 
229     public inline nothrow ulong GetSegmentPart(ulong virtualAddress)
230     {
231         return cast<ulong>(GetSegmentIndex(virtualAddress)) << cast<ulong>(segmentNumberShift);
232     }
233 
234     public inline nothrow ushort MakeSegmentOffset(byte segmentIndex)
235     {
236         return segmentIndex * numSegmentPageEntriesInRootPage;
237     }
238 
239     public inline nothrow void ExtractDigitsFromPageNumber(ulong pageNum, ushort& digit0, ushort& digit1, ushort& digit2)
240     {
241         digit0 = cast<ushort>(pageNum & pteOffsetMask);
242         pageNum = pageNum >> numPteBits;
243         digit1 = cast<ushort>(pageNum & pteOffsetMask);
244         pageNum = pageNum >> numPteBits;
245         digit2 = cast<ushort>(pageNum & pteOffsetMask);
246         pageNum = pageNum >> numPteBits;
247     }
248 
249     public nothrow byte ReadMemoryByte(ulong address)
250     {
251         byte b = OsReadMemoryByte(address);
252         return b;
253     }
254 
255     public nothrow void WriteMemoryByte(ulong address, byte b)
256     {
257         if (address == 0u)
258         {
259             return;
260         }
261         OsWriteMemoryByte(address, b);
262     }
263 
264     public nothrow ushort ReadMemoryUShort(ulong address)
265     {
266         ulong a = address & m2Mask;
267         byte m0 = ReadMemoryByte(a);
268         byte m1 = ReadMemoryByte(a + 1u);
269         ushort u = (cast<ushort>(m0) << 8u) | cast<ushort>(m1);
270         return u;
271     }
272 
273     public nothrow void WriteMemoryUShort(ulong address, ushort s)
274     {
275         ulong a = address & m2Mask;
276         byte m0 = cast<byte>(s >> 8u);
277         byte m1 = cast<byte>(s);
278         WriteMemoryByte(a, m0);
279         WriteMemoryByte(a + 1u, m1);
280     }
281 
282     public nothrow uint ReadMemoryUInt(ulong address)
283     {
284         ulong a = address & m4Mask;
285         byte m0 = ReadMemoryByte(a);
286         byte m1 = ReadMemoryByte(a + 1u);
287         byte m2 = ReadMemoryByte(a + 2u);
288         byte m3 = ReadMemoryByte(a + 3u);
289         uint u = (cast<uint>(m0) << 24u) | (cast<uint>(m1) << 16u) | (cast<uint>(m2) << 8u) | cast<uint>(m3);
290         return u;
291     }
292 
293     public nothrow void WriteMemoryUInt(ulong address, uint u)
294     {
295         ulong a = address & m4Mask;
296         byte m0 = cast<byte>(u >> 24u);
297         byte m1 = cast<byte>(u >> 16u);
298         byte m2 = cast<byte>(u >> 8u);
299         byte m3 = cast<byte>(u);
300         WriteMemoryByte(a, m0);
301         WriteMemoryByte(a + 1u, m1);
302         WriteMemoryByte(a + 2u, m2);
303         WriteMemoryByte(a + 3u, m3);
304     }
305 
306     public nothrow ulong ReadMemoryULong(ulong address)
307     {
308         ulong a = address & m8Mask;
309         byte m0 = ReadMemoryByte(a);
310         byte m1 = ReadMemoryByte(a + 1u);
311         byte m2 = ReadMemoryByte(a + 2u);
312         byte m3 = ReadMemoryByte(a + 3u);
313         byte m4 = ReadMemoryByte(a + 4u);
314         byte m5 = ReadMemoryByte(a + 5u);
315         byte m6 = ReadMemoryByte(a + 6u);
316         byte m7 = ReadMemoryByte(a + 7u);
317         ulong u = (cast<ulong>(m0) << 56u) | (cast<ulong>(m1) << 48u) | (cast<ulong>(m2) << 40u) | (cast<ulong>(m3) << 32u) | (cast<ulong>(m4) << 24u) | (cast<ulong>(m5) << 16u) | (cast<ulong>(m6) << 8u) | cast<ulong>(m7);
318         return u;
319     }
320 
321     public nothrow void WriteMemoryULong(ulong address, ulong u)
322     {
323         ulong a = address & m8Mask;
324         byte m0 = cast<byte>(u >> 56u);
325         byte m1 = cast<byte>(u >> 48u);
326         byte m2 = cast<byte>(u >> 40u);
327         byte m3 = cast<byte>(u >> 32u);
328         byte m4 = cast<byte>(u >> 24u);
329         byte m5 = cast<byte>(u >> 16u);
330         byte m6 = cast<byte>(u >> 8u);
331         byte m7 = cast<byte>(u);
332         WriteMemoryByte(a, m0);
333         WriteMemoryByte(a + 1u, m1);
334         WriteMemoryByte(a + 2u, m2);
335         WriteMemoryByte(a + 3u, m3);
336         WriteMemoryByte(a + 4u, m4);
337         WriteMemoryByte(a + 5u, m5);
338         WriteMemoryByte(a + 6u, m6);
339         WriteMemoryByte(a + 7u, m7);
340     }
341 
342     public class AddressTranslationCacheEntry
343     {
344         public nothrow AddressTranslationCacheEntry() : sourcePageNumber(invalidAddress), targetPageNumber(invalidAddress)
345         {
346         }
347         public ulong sourcePageNumber;
348         public ulong targetPageNumber;
349     }
350 
351     public class AddressTranslationCache
352     {
353         public nothrow AddressTranslationCache() : entries()
354         {
355         }
356         public nothrow void Clear()
357         {
358             for (int i = 0; i < numTranslationCacheEntries; ++i;)
359             {
360                 entries[i] = AddressTranslationCacheEntry();
361             }
362         }
363         public inline nothrow ulong GetEntry(ulong virtualAddress, int& entryIndex, ulong& sourcePageNumber)
364         {
365             entryIndex = cast<int>((virtualAddress >> pageOffsetBits) & translationCacheIndexMask) + numTranslationCacheIndexSegmentEntries * cast<int>(GetSegmentIndex(virtualAddress));
366             sourcePageNumber = GetSegmentPart(virtualAddress) | GetPageNumber(virtualAddress & virtualAddressBaseMask);
367             const AddressTranslationCacheEntry& entry = entries[entryIndex];
368             if (entry.sourcePageNumber == sourcePageNumber)
369             {
370                 return entry.targetPageNumber;
371             }
372             else
373             {
374                 return invalidAddress;
375             }
376         }
377         public inline nothrow void SetEntry(int entryIndex, ulong sourcePageNumber, ulong targetPageNumber)
378         {
379             AddressTranslationCacheEntry& entry = entries[entryIndex];
380             entry.sourcePageNumber = sourcePageNumber;
381             entry.targetPageNumber = targetPageNumber;
382         }
383         public AddressTranslationCacheEntry[numTranslationCacheEntries] entries;
384     }
385 
386     public class Memory
387     {
388         public nothrow Memory(Machine& machine_) : machine(machine_)
389         {
390         }
391         public ulong AllocatePage()
392         {
393             ulong pageAddress = OsAllocateMemoryPage(pageSize);
394             if (pageAddress == 0u)
395             {
396                 Console.Error() << "out of memory" << endl();
397                 throw Exception("out of memory");
398             }
399             pageFrameMap[pageAddress] = new PageFrame();
400             return pageAddress;
401         }
402         public ulong AllocateRootPage()
403         {
404             ulong rootPageAddress = AllocatePage();
405             return rootPageAddress;
406         }
407         public void FreePage(ulong pageAddress)
408         {
409             HashMap<ulong, PageFrame*>.ConstIterator it = pageFrameMap.CFind(pageAddress);
410             if (it != pageFrameMap.CEnd())
411             {
412                 PageFrame* pageFrame = it->second;
413                 #assert(pageFrame->useCount > 0u);
414                 pageFrame->useCount = pageFrame->useCount - 1u;
415                 if (pageFrame->useCount == 0u)
416                 {
417                     OsFreeMemoryPage(pageAddress);
418                     pageFrameMap.Remove(pageAddress);
419                     delete pageFrame;
420                 }
421             }
422             else
423             {
424                 Panic("page frame for page address " + ToHexString(pageAddress) + " not found");
425             }
426         }
427         public nothrow void FreeRootPage(ulong rootPageAddress)
428         {
429             FreePage(rootPageAddress);
430         }
431         public void SharePage(ulong pageAddress)
432         {
433             HashMap<ulong, PageFrame*>.ConstIterator it = pageFrameMap.CFind(pageAddress);
434             if (it != pageFrameMap.CEnd())
435             {
436                 PageFrame* pageFrame = it->second;
437                 #assert(pageFrame->useCount > 0u);
438                 pageFrame->useCount = pageFrame->useCount + 1u;
439             }
440             else
441             {
442                 Panic("page frame for page address " + ToHexString(pageAddress) + " not found");
443             }
444         }
445         public nothrow void CopyPage(ulong fromAddress, ulong toAddress)
446         {
447             OsCopyMemoryPage(fromAddress, toAddress, pageSize);
448         }
449         public nothrow ulong GetPageTableEntry(ulong virtualAddress)
450         {
451             byte segmentIndex = 0u;
452             ulong pageAddress = 0u;
453             ushort offset = 0u;
454             ushort addressSpaceNumber = 0u;
455             Protection pageProtection = Protection.notPresent;
456             ulong pteAddress = 0u;
457             return GetPageTableEntry(virtualAddress, segmentIndex, pageAddress, offset, addressSpaceNumber, pageProtection, pteAddress);
458         }
459         public nothrow ulong GetPageTableEntry(ulong virtualAddress, byte& segmentIndex, ulong& pageAddress, ushort& offset, ushort& addressSpaceNumber, Protection& pageProtection, ulong& pteAddress)
460         {
461             ulong pte = 0u;
462             pageProtection = Protection.notPresent;
463             segmentIndex = GetSegmentIndex(virtualAddress);
464             ushort segmentOffset = MakeSegmentOffset(segmentIndex);
465             ushort pageTableAddressSpaceNumber = 0u;
466             ulong rv = machine.GetRegisters().GetSpecial(Registers.rV);
467             ulong rootPageAddress = 0u;
468             UnpackVirtualTranslationRegisterValue(rv, rootPageAddress, addressSpaceNumber);
469             ulong firstRootPageEntryNumber = segmentOffset;
470             ulong lastDirectRootPageEntryNumber = firstRootPageEntryNumber + numDirectEntries - 1u;
471             ulong firstIndirectEntryNumber = lastDirectRootPageEntryNumber + 1u;
472             ulong singleIndirectEntryNumber = lastDirectRootPageEntryNumber + 1u;
473             ulong doubleIndirectEntryNumber = lastDirectRootPageEntryNumber + 2u;
474             ulong tripleIndirectEntryNumber = lastDirectRootPageEntryNumber + 3u;
475             ulong address = virtualAddress & virtualAddressBaseMask;
476             ulong pageNum = firstRootPageEntryNumber + GetPageNumber(address);
477             offset = cast<ushort>(virtualAddress & pageOffsetMask);
478             if (pageNum >= firstRootPageEntryNumber && pageNum <= lastDirectRootPageEntryNumber)
479             {
480                 pteAddress = rootPageAddress + 8u * pageNum;
481                 pte = ReadMemoryULong(pteAddress);
482                 ushort pteAddressSpaceNumber = 0u;
483                 UnpackPageTableEntry(pte, pageAddress, pteAddressSpaceNumber, pageProtection);
484                 if (pageProtection == Protection.notPresent || addressSpaceNumber != pteAddressSpaceNumber)
485                 {
486                     return 0u;
487                 }
488             }
489             else
490             {
491                 pageNum = pageNum - firstIndirectEntryNumber;
492                 ushort digit0 = 0u;
493                 ushort digit1 = 0u;
494                 ushort digit2 = 0u;
495                 ExtractDigitsFromPageNumber(pageNum, digit0, digit1, digit2);
496                 if (digit2 == 0u && digit1 == 0u)
497                 {
498                     ulong singleIndirectEntryAddress = rootPageAddress + 8u * singleIndirectEntryNumber;
499                     ulong singleIndirectPageTableEntry = ReadMemoryULong(singleIndirectEntryAddress);
500                     ulong singleIndirectPageAddress = 0u;
501                     ushort singleIndirectAddressSpaceNumber = 0u;
502                     Protection singleIndirectProtection = Protection.notPresent;
503                     UnpackPageTableEntry(singleIndirectPageTableEntry, singleIndirectPageAddress, singleIndirectAddressSpaceNumber, singleIndirectProtection);
504                     if (singleIndirectProtection == Protection.notPresent || addressSpaceNumber != singleIndirectAddressSpaceNumber)
505                     {
506                         return 0u;
507                     }
508                     pteAddress = singleIndirectPageAddress + 8u * digit0;
509                     pte = ReadMemoryULong(pteAddress);
510                     ushort pteAddressSpaceNumber = 0u;
511                     UnpackPageTableEntry(pte, pageAddress, pteAddressSpaceNumber, pageProtection);
512                     if (pageProtection == Protection.notPresent || addressSpaceNumber != pteAddressSpaceNumber)
513                     {
514                         return 0u;
515                     }
516                 }
517                 else if (digit2 == 0u && digit1 > 0u)
518                 {
519                     ulong doubleIndirectEntryAddress = rootPageAddress + 8u * doubleIndirectEntryNumber;
520                     ulong doubleIndirectPageTableEntry = ReadMemoryULong(doubleIndirectEntryAddress);
521                     ulong doubleIndirectPageAddress = 0u;
522                     ushort doubleIndirectAddressSpaceNumber = 0u;
523                     Protection doubleIndirectProtection = Protection.notPresent;
524                     UnpackPageTableEntry(doubleIndirectPageTableEntry, doubleIndirectPageAddress, doubleIndirectAddressSpaceNumber, doubleIndirectProtection);
525                     if (doubleIndirectProtection == Protection.notPresent || addressSpaceNumber != doubleIndirectAddressSpaceNumber)
526                     {
527                         return 0u;
528                     }
529                     ulong singleIndirectEntryAddress = doubleIndirectPageAddress + 8u * digit1;
530                     ulong singleIndirectPageTableEntry = ReadMemoryULong(singleIndirectEntryAddress);
531                     ulong singleIndirectPageAddress = 0u;
532                     ushort singleIndirectAddressSpaceNumber = 0u;
533                     Protection singleIndirectProtection = Protection.notPresent;
534                     UnpackPageTableEntry(singleIndirectPageTableEntry, singleIndirectPageAddress, singleIndirectAddressSpaceNumber, singleIndirectProtection);
535                     if (singleIndirectProtection == Protection.notPresent || addressSpaceNumber != singleIndirectAddressSpaceNumber)
536                     {
537                         return 0u;
538                     }
539                     pteAddress = singleIndirectPageAddress + 8u * digit0;
540                     pte = ReadMemoryULong(pteAddress);
541                     ushort pteAddressSpaceNumber = 0u;
542                     UnpackPageTableEntry(pte, pageAddress, pteAddressSpaceNumber, pageProtection);
543                     if (pageProtection == Protection.notPresent || addressSpaceNumber != pteAddressSpaceNumber)
544                     {
545                         return 0u;
546                     }
547                 }
548                 else if (digit2 >= 0u)
549                 {
550                     ulong tripleIndirectEntryAddress = rootPageAddress + 8u * tripleIndirectEntryNumber;
551                     ulong tripleIndirectPageTableEntry = ReadMemoryULong(tripleIndirectEntryAddress);
552                     ulong tripleIndirectPageAddress = 0u;
553                     ushort tripleIndirectAddressSpaceNumber = 0u;
554                     Protection tripleIndirectProtection = Protection.notPresent;
555                     UnpackPageTableEntry(tripleIndirectPageTableEntry, tripleIndirectPageAddress, tripleIndirectAddressSpaceNumber, tripleIndirectProtection);
556                     if (tripleIndirectProtection == Protection.notPresent || addressSpaceNumber != tripleIndirectAddressSpaceNumber)
557                     {
558                         return 0u;
559                     }
560                     ulong doubleIndirectEntryAddress = tripleIndirectPageAddress + 8u * digit2;
561                     ulong doubleIndirectPageTableEntry = ReadMemoryULong(doubleIndirectEntryAddress);
562                     ulong doubleIndirectPageAddress = 0u;
563                     ushort doubleIndirectAddressSpaceNumber = 0u;
564                     Protection doubleIndirectProtection = Protection.notPresent;
565                     UnpackPageTableEntry(doubleIndirectPageTableEntry, doubleIndirectPageAddress, doubleIndirectAddressSpaceNumber, doubleIndirectProtection);
566                     if (doubleIndirectProtection == Protection.notPresent || addressSpaceNumber != doubleIndirectAddressSpaceNumber)
567                     {
568                         return 0u;
569                     }
570                     ulong singleIndirectEntryAddress = doubleIndirectPageAddress + 8u * digit1;
571                     ulong singleIndirectPageTableEntry = ReadMemoryULong(singleIndirectEntryAddress);
572                     ulong singleIndirectPageAddress = 0u;
573                     ushort singleIndirectAddressSpaceNumber = 0u;
574                     Protection singleIndirectProtection = Protection.notPresent;
575                     UnpackPageTableEntry(singleIndirectPageTableEntry, singleIndirectPageAddress, singleIndirectAddressSpaceNumber, singleIndirectProtection);
576                     if (singleIndirectProtection == Protection.notPresent || addressSpaceNumber != singleIndirectAddressSpaceNumber)
577                     {
578                         return 0u;
579                     }
580                     pteAddress = singleIndirectPageAddress + 8u * digit0;
581                     pte = ReadMemoryULong(pteAddress);
582                     ushort pteAddressSpaceNumber = 0u;
583                     UnpackPageTableEntry(pte, pageAddress, pteAddressSpaceNumber, pageProtection);
584                     if (pageProtection == Protection.notPresent || addressSpaceNumber != pteAddressSpaceNumber)
585                     {
586                         return 0u;
587                     }
588                 }
589             }
590             return pte;
591         }
592         public inline nothrow AddressTranslationCache& GetTranslationCache(ushort addressSpaceNumber)
593         {
594             if (addressSpaceNumber < numDirectTranslationCaches)
595             {
596                 return directTranslationCaches[addressSpaceNumber];
597             }
598             else
599             {
600                 AddressTranslationCache* cache = mappedTranslationCaches[addressSpaceNumber];
601                 if (cache != null)
602                 {
603                     return *cache;
604                 }
605                 else
606                 {
607                     cache = new AddressTranslationCache();
608                     mappedTranslationCaches[addressSpaceNumber] = cache;
609                     return *cache;
610                 }
611             }
612         }
613         public nothrow void ClearTranslationCache(ushort addressSpaceNumber)
614         {
615             if (!UseTranslationCache()) return;
616             AddressTranslationCache& cache = GetTranslationCache(addressSpaceNumber);
617             cache.Clear();
618         }
619         public nothrow void DisposeTranslationCache(ushort addressSpaceNumber)
620         {
621             if (!UseTranslationCache()) return;
622             if (addressSpaceNumber < numDirectTranslationCaches)
623             {
624                 directTranslationCaches[addressSpaceNumber].Clear();
625             }
626             else
627             {
628                 AddressTranslationCache* cache = mappedTranslationCaches[addressSpaceNumber];
629                 if (cache != null)
630                 {
631                     delete cache;
632                     mappedTranslationCaches[addressSpaceNumber] = null;
633                 }
634             }
635         }
636         public nothrow bool GetAddressFromTranslationCache(ulong virtualAddress, ushort& addressSpaceNumber, ulong& pageAddress, ushort& offset, int& entryIndex, ulong& sourcePageNumber)
637         {
638             ulong rv = machine.GetRegisters().GetSpecial(Registers.rV);
639             ulong rootPageAddress = 0u;
640             addressSpaceNumber = 0u;
641             UnpackVirtualTranslationRegisterValue(rv, rootPageAddress, addressSpaceNumber);
642             offset = cast<ushort>(virtualAddress & pageOffsetMask);
643             AddressTranslationCache& cache = GetTranslationCache(addressSpaceNumber);
644             pageAddress = cache.GetEntry(virtualAddress, entryIndex, sourcePageNumber);
645             if (pageAddress == invalidAddress)
646             {
647                 pageAddress = 0u;
648                 addressSpaceNumber = 0u;
649                 return false;
650             }
651             else
652             {
653                 return true;
654             }
655         }
656         public inline nothrow void SetAddressToTranslationCache(ushort addressSpaceNumber, ulong pageAddress, int entryIndex, ulong sourcePageNumber)
657         {
658             AddressTranslationCache& cache = GetTranslationCache(addressSpaceNumber);
659             cache.SetEntry(entryIndex, sourcePageNumber, pageAddress);
660         }
661         public nothrow ulong TranslateAddress(ulong virtualAddress, Protection access, bool pageFault)
662         {
663             ulong pageAddress = 0u;
664             ushort offset = 0u;
665             int entryIndex = 0;
666             ulong sourcePageNumber = 0u;
667             ushort addressSpaceNumber = 0u;
668             if (UseTranslationCache())
669             {
670                 bool foundFromCache = GetAddressFromTranslationCache(virtualAddress, addressSpaceNumber, pageAddress, offset, entryIndex, sourcePageNumber);
671                 if (foundFromCache)
672                 {
673                     return pageAddress + offset;
674                 }
675             }
676             if (CheckSecurityViolation(virtualAddress))
677             {
678                 return invalidAddress;
679             }
680             byte segmentIndex = 0u;
681             Protection pageProtection = Protection.notPresent;
682             ulong pteAddress = 0u;
683             ulong pte = GetPageTableEntry(virtualAddress, segmentIndex, pageAddress, offset, addressSpaceNumber, pageProtection, pteAddress);
684             if (pte == 0 && virtualAddress > stackSegmentBaseAddress && virtualAddress < kernelBaseAddress)
685             {
686                 ulong maxStackSize = GetMaxStackSize(addressSpaceNumber);
687                 ulong requiredStackSize = ((virtualAddress - stackSegmentBaseAddress - 1u) / pageSize + 1u) * pageSize;
688                 if (requiredStackSize <= maxStackSize)
689                 {
690                     bool grown = GrowStack(addressSpaceNumber);
691                     while (grown)
692                     {
693                         pte = GetPageTableEntry(virtualAddress, segmentIndex, pageAddress, offset, addressSpaceNumber, pageProtection, pteAddress);
694                         if (pte == 0)
695                         {
696                             grown = GrowStack(addressSpaceNumber);
697                         }
698                         else
699                         {
700                             break;
701                         }
702                     }
703                     if (pte == 0)
704                     {
705                         if (pageFault)
706                         {
707                             PageFault(virtualAddress, pageProtection, access);
708                         }
709                         return invalidAddress;
710                     }
711                 }
712                 else
713                 {
714                     if (pageFault)
715                     {
716                         PageFault(virtualAddress, pageProtection, access);
717                     }
718                     return invalidAddress;
719                 }
720             }
721             else if (pte != 0u && pageProtection == Protection.copyOnWrite && (access & Protection.write) != 0u)
722             {
723                 ulong newPageAddress = AllocatePage();
724                 CopyPage(pageAddress, newPageAddress);
725                 FreePage(pageAddress);
726                 pageAddress = newPageAddress;
727                 pte = MakePageTableEntry(pageAddress, addressSpaceNumber, cast<Protection>(Protection.read | Protection.write));
728                 WriteMemoryULong(pteAddress, pte);
729             }
730             else if (pte == 0u || (pageProtection & access) != access)
731             {
732                 if (pageFault)
733                 {
734                     PageFault(virtualAddress, pageProtection, access);
735                 }
736                 return invalidAddress;
737             }
738             if (UseTranslationCache())
739             {
740                 SetAddressToTranslationCache(addressSpaceNumber, pageAddress, entryIndex, sourcePageNumber);
741             }
742             ulong physicalAddress = pageAddress + offset;
743             return physicalAddress;
744         }
745         public nothrow byte ReadByte(ulong virtualAddress, Protection access)
746         {
747             return ReadByte(virtualAddress, access, true);
748         }
749         public nothrow byte ReadByte(ulong virtualAddress, Protection access, bool pageFault)
750         {
751             ulong address = TranslateAddress(virtualAddress, access, pageFault);
752             if (address != invalidAddress)
753             {
754                 return ReadMemoryByte(address);
755             }
756             else
757             {
758                 return 0u;
759             }
760         }
761         public nothrow void WriteByte(ulong virtualAddress, byte b, Protection access)
762         {
763             WriteByte(virtualAddress, b, access, true);
764         }
765         public nothrow void WriteByte(ulong virtualAddress, byte b, Protection access, bool pageFault)
766         {
767             ulong address = TranslateAddress(virtualAddress, access, pageFault);
768             if (address != invalidAddress)
769             {
770                 WriteMemoryByte(address, b);
771             }
772         }
773         public nothrow ushort ReadUShort(ulong virtualAddress, Protection access)
774         {
775             return ReadUShort(virtualAddress, access, true);
776         }
777         public nothrow ushort ReadUShort(ulong virtualAddress, Protection access, bool pageFault)
778         {
779             ulong address = TranslateAddress(virtualAddress, access, pageFault);
780             if (address != invalidAddress)
781             {
782                 return ReadMemoryUShort(address);
783             }
784             else
785             {
786                 return 0u;
787             }
788         }
789         public nothrow void WriteUShort(ulong virtualAddress, ushort u, Protection access)
790         {
791             WriteUShort(virtualAddress, u, access, true);
792         }
793         public nothrow void WriteUShort(ulong virtualAddress, ushort u, Protection access, bool pageFault)
794         {
795             ulong address = TranslateAddress(virtualAddress, access, pageFault);
796             if (address != invalidAddress)
797             {
798                 WriteMemoryUShort(address, u);
799             }
800         }
801         public nothrow uint ReadUInt(ulong virtualAddress, Protection access)
802         {
803             return ReadUInt(virtualAddress, access, true);
804         }
805         public nothrow uint ReadUInt(ulong virtualAddress, Protection access, bool pageFault)
806         {
807             ulong address = TranslateAddress(virtualAddress, access, pageFault);
808             if (address != invalidAddress)
809             {
810                 return ReadMemoryUInt(address);
811             }
812             else
813             {
814                 return 0u;
815             }
816         }
817         public nothrow void WriteUInt(ulong virtualAddress, uint u, Protection access)
818         {
819             WriteUInt(virtualAddress, u, access, true);
820         }
821         public nothrow void WriteUInt(ulong virtualAddress, uint u, Protection access, bool pageFault)
822         {
823             ulong address = TranslateAddress(virtualAddress, access, pageFault);
824             if (address != invalidAddress)
825             {
826                 WriteMemoryUInt(address, u);
827             }
828         }
829         public nothrow ulong ReadULong(ulong virtualAddress, Protection access)
830         {
831             return ReadULong(virtualAddress, access, true);
832         }
833         public nothrow ulong ReadULong(ulong virtualAddress, Protection access, bool pageFault)
834         {
835             ulong address = TranslateAddress(virtualAddress, access, pageFault);
836             if (address != invalidAddress)
837             {
838                 return ReadMemoryULong(address);
839             }
840             else
841             {
842                 return 0u;
843             }
844         }
845         public nothrow void WriteULong(ulong virtualAddress, ulong u, Protection access)
846         {
847             WriteULong(virtualAddress, u, access, true);
848         }
849         public nothrow void WriteULong(ulong virtualAddress, ulong u, Protection access, bool pageFault)
850         {
851             ulong address = TranslateAddress(virtualAddress, access, pageFault);
852             if (address != invalidAddress)
853             {
854                 WriteMemoryULong(address, u);
855             }
856         }
857         private nothrow void PageFault(ulong virtualAddress, Protection pageProtection, Protection access)
858         {
859             InvokePageFault(machine.GetRegisters(), virtualAddress, pageProtection, access);
860         }
861         private nothrow bool CheckSecurityViolation(ulong virtualAddress)
862         {
863             Registers& regs = machine.GetRegisters();
864             if ((virtualAddress & kernelBaseAddress) != 0u && !IsProcessorInKernelMode(regs))
865             {
866                 SetSecurityViolation(regs, virtualAddress);
867                 return true;
868             }
869             return false;
870         }
871         private HashMap<ulong, PageFrame*> pageFrameMap;
872         private PageFrame* freePageFrameList;
873         private Machine& machine;
874         private AddressTranslationCache[16] directTranslationCaches;
875         private HashMap<ushort, AddressTranslationCache*> mappedTranslationCaches;
876     }
877 }