Optimizing 8 entry TLB using linked lists?

Emulation of old PCs, PC hardware, or PC peripherals.

Optimizing 8 entry TLB using linked lists?

Postby superfury » 2019-1-31 @ 14:10

Would a linked list (entry ptr, next ptr, prev ptr in 8 records, initialized linearly) provide a speedup compared to an array-sort LRU method of sorting and placing increasing numbers in the entries themselves?

The TLB has 8 sorted entries, with 4 way association(so 8x4 sets to sort, one at a time)?
superfury
l33t
 
Posts: 3230
Joined: 2014-3-08 @ 11:25
Location: Netherlands

Re: Optimizing 8 entry TLB using linked lists?

Postby superfury » 2019-1-31 @ 20:05

Just took a look at https://www.quora.com/Why-is-doubly-lin ... ksforGeeks .

After understanding the principles of how it works(in a rough sense; it's pretty simple when you think about it), I started coding myself and came up with this(in UniPCemu's paging code algorithm):

https://bitbucket.org/superfury/unipcem ... ?at=master

The core of the new TLB LRU algorithm is:
Code: Select all
typedef struct
{
   uint_32 data; //80386 4-way associative TLB results!
   uint_32 TAG; //All TAGs used with the respective TLB!
} TLBEntry;

typedef struct
{
   TLBEntry *entry; //What entry are we?
   byte index; //What index is said entry?
   void *prev, *next; //Previous and next pointers!
   byte allocated; //Are we allocated?
} TLB_ptr;

typedef struct
{
   TLBEntry TLB[4][8]; //All TLB entries to use!
   TLB_ptr TLB_listnodes[4][8]; //All nodes for all TLB entries!
   TLB_ptr *TLB_freelist_head[4], *TLB_freelist_tail[4]; //Head and tail of the free list!
   TLB_ptr *TLB_usedlist_head[4], *TLB_usedlist_tail[4]; //Head and tail of the used list!
} CPU_TLB; //A TLB to use for the CPU!


Code: Select all
void PagingTLB_initlists()
{
   byte set; //What set?
   byte index; //What index?
   TLB_ptr *us; //What is the current entry!
   for (set = 0; set < 4; ++set) //process all sets!
   {
      //Allocate a list from the available entry space, with all items in ascending order in a linked list and index!
      CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = NULL; //Nothing!
      CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set] = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set] = NULL; //Nothing!
      for (index = 7; ((index&0xFF)!=0xFF); --index) //process all indexes!
      {
         CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].entry = &CPU[activeCPU].Paging_TLB.TLB[set][index]; //What entry(constant value)!
         CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].index = index; //What index are we(for lookups)?
         CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].allocated = 0; //We're in the free list!
         us = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index]; //What entry are we?
         us->prev = NULL; //We start out as the head for the added items here, so never anything before us!
         us->next = NULL; //We start out as the head, so next is automatically filled!
         if (CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]) //Head already set?
         {
            CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->prev = us; //We're the previous for the current head!
            us->next = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Our next is the head!
         }
         CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = us; //We're the new head!
         if (CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] == NULL) //No tail yet?
         {
            CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Tail=Head when starting out!
         }
      }
   }
}

//Move a TLB entry index from an old list to a new list!
void Paging_moveListItem(TLB_ptr *listitem, TLB_ptr **newlist_head, TLB_ptr **newlist_tail, TLB_ptr **oldlist_head, TLB_ptr **oldlist_tail)
{
   //First, remove us from the old head list!
   if (listitem->prev) //Do we have anything before us?
   {
      ((TLB_ptr *)listitem->prev)->next = listitem->next; //Remove us from the previous item of the list!
   }
   else //We're the head, so remove us from the list!
   {
      *oldlist_head = listitem->next; //Remove us from the head of the list and assign the new head!
   }

   if (listitem->next) //Did we have a next item?
   {
      ((TLB_ptr *)listitem->next)->prev = listitem->prev; //Remove us from the next item of the list!
   }
   else //We're the tail?
   {
      *oldlist_tail = listitem->prev; //Remove us from the tail of the list and assign the new tail!
   }

   listitem->next = NULL; //We don't have a next!
   listitem->prev = NULL; //We don't have a previous!

   /* Now, we're removed from the old list and a newly unmapped item! */

   //Now, insert us into the start of the new list!
   if (*newlist_head) //Anything in the new list already?
   {
      (*newlist_head)->prev = listitem; //We're at the start of the new list, so point the head to us, us to the head and make us the new head!
      listitem->next = *newlist_head; //Our next is the old head!
      *newlist_head = listitem; //We're the new head!
   }
   else //We're the new list?
   {
      *newlist_head = listitem; //We're the new head!
      *newlist_tail = listitem; //We're the new tail!
   }
}

TLB_ptr *allocTLB(sbyte set) //Allocate a TLB entry!
{
   TLB_ptr *result;
   if (CPU[activeCPU].Paging_TLB.TLB_freelist_head) //Anything available?
   {
      result = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //What item are we allocating, take it from the free list!
      //Now take the item from the pool and move it to the used list!
      CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->allocated = 1; //We're allocated now!
      Paging_moveListItem(CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //What item to take!
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail
         &CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head
         &CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail
      return result; //Give the result!
   }
   return NULL; //Nothing to allocate!
}

void freeTLB(sbyte set, byte TLB_index) //Make an entry available again!
{
   TLB_ptr *listitem;
   listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!
   if (listitem->allocated) //Are we allocated at all?
   {
      listitem->allocated = 0; //Mark us as freed!
      Paging_moveListItem(listitem, //What item to take!
         &CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //destination head
         &CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set], //destination tail
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //source head
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]); //source tail
   }
}

void Paging_setNewestTLB(sbyte set, byte TLB_index) //Tick an TLB entry for making it the most recently used!
{
   TLB_ptr *listitem;
   listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!
   if (listitem->allocated) //Are we allocated at all?
   {
      Paging_moveListItem(listitem,
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set],
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]); //Move us to the start of the TLB used list to mark us as the most recently accessed!
   }
   else //We're not allocated, but marked as newest? Allocate us!
   {
      listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!
      //Now take the item from the pool and move it to the used list!
      listitem->allocated = 1; //We're allocated now!
      Paging_moveListItem(listitem, //What item to take!
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail
         &CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head
         &CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail
   }
}

byte Paging_oldestTLB(sbyte set) //Find a TLB to be used/overwritten!
{
   TLB_ptr *entry;
   if (CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]) //Anything not allocated yet?
   {
      if (entry = allocTLB(set)) //Allocated from the free list?
      {
         return entry->index; //Give the index of the resulting entry that's been allocated!
      }
   }
   else //Allocate from the tail(LRU), since everything is allocated!
   {
      if (CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]) //Gotten a tail? We're used, so take the LRU!
      {
         entry = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]; //What entry to take: the LRU!
         Paging_setNewestTLB(set, entry->index); //This is the newest TLB now!
         return entry->index; //What index is the LRU!
      }
   }
   return 7;
}


Then the write/read/init TLB functions use it like this(barely adjusted):
Code: Select all
void Paging_writeTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 result)
{
   byte effectiveentry;
   uint_32 TAG,TAGMASKED;
   if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?
   TAG = Paging_generateTAG(logicaladdress, W, U, D); //Generate a TAG!
   byte entry;
   TAGMASKED = (TAG&0xFFFFF001); //Masked tag for fast lookup! Match P/U/W/address only! Thus dirty updates the existing entry, while other bit changing create a new entry!
   effectiveentry = 0;
   entry = 8; //Init for entry search not found!
   do
   {
      if (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][effectiveentry].allocated) //Allocated entry?
      {
         if ((CPU[activeCPU].Paging_TLB.TLB[TLB_set][effectiveentry].TAG & 0xFFFFF001) == TAGMASKED) //Match for our own entry?
         {
            entry = effectiveentry; //Reuse our own entry!
            break; //Stop searching: reuse the effective entry!
         }
      }
   } while (++effectiveentry < 8); //Check all entries!
   if (entry == 8) //Not found? Take the LRU!
   {
      entry = Paging_oldestTLB(TLB_set); //Get the oldest/unused TLB!
   }
   else //We're the newest TLB now!
   {
      Paging_setNewestTLB(TLB_set, entry); //We're the newest TLB now!
   }
   CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].data = result; //The result for the lookup!
   CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = TAG; //The TAG to find it by!
}

//RWDirtyMask: mask for ignoring set bits in the tag, use them otherwise!
byte Paging_readTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 WDMask, uint_32 *result, byte updateAges)
{
   INLINEREGISTER uint_32 TAG, TAGMask;
   INLINEREGISTER byte entry = 0;
   INLINEREGISTER TLBEntry *curentry;
   if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?
   TAG = Paging_generateTAG(logicaladdress,W,U,D); //Generate a TAG!
   TAGMask = ~WDMask; //Store for fast usage to mask the tag bits unused off!
   if (likely(WDMask)) //Used?
   {
      TAG &= TAGMask; //Ignoring these bits, so mask them off when comparing!
   }
   curentry = &CPU[activeCPU].Paging_TLB.TLB[TLB_set][0]; //What TLB entry to apply?
   do //Check all entries!
   {
       if (likely(((curentry->TAG&TAGMask)==TAG) && (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][entry].allocated))) //Found?
      {
         *result = curentry->data; //Give the stored data!
         Paging_setNewestTLB(TLB_set, entry); //Set us as the newest TLB!
         return 1; //Found!
      }
      ++curentry; //Next entry!
   } while (likely(++entry<8));
   return 0; //Not found!
}

void Paging_Invalidate(uint_32 logicaladdress) //Invalidate a single address!
{
   INLINEREGISTER byte TLB_set;
   INLINEREGISTER byte entry;
   for (TLB_set = 0; TLB_set < 4; ++TLB_set) //Process all possible sets!
   {
      for (entry = 0; entry < 8; ++entry) //Check all entries!
      {
         if (Paging_matchTLBaddress(logicaladdress, CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG)) //Matched?
         {
            CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = 0; //Clear the entry to unused!
            freeTLB(TLB_set, entry); //Free this entry from the TLB!
         }
      }
   }
}

void Paging_clearTLB()
{
   memset(&CPU[activeCPU].Paging_TLB,0,sizeof(CPU[activeCPU].Paging_TLB)); //Reset fully and clear the TLB!
   PagingTLB_initlists(); //Initialize the TLB lists to become empty!
}


I still see Windows NT booting like always, so it can't be that wrong? What are your opinions?
superfury
l33t
 
Posts: 3230
Joined: 2014-3-08 @ 11:25
Location: Netherlands

Re: Optimizing 8 entry TLB using linked lists?

Postby superfury » 2019-1-31 @ 22:57

Hmmmm.... Interesting.... When running Simcity 2000 with paging deliberately enabled(with "set dos4gvm=maxmem#4096 virtualsize#32768 swapname#d:\swapfile.swp"), I see it crashing in protected mode over and over again on a FFFFh opcode? Interesting, since it runs fine in normal mode(without paging afaik).
superfury
l33t
 
Posts: 3230
Joined: 2014-3-08 @ 11:25
Location: Netherlands

Re: Optimizing 8 entry TLB using linked lists?

Postby superfury » 2019-1-31 @ 23:41

Now trying to run Prime95 under MS-DOS to check for bugs. So far up to DMA controllers pass(Cache memory hangs it seems).
superfury
l33t
 
Posts: 3230
Joined: 2014-3-08 @ 11:25
Location: Netherlands

Re: Optimizing 8 entry TLB using linked lists?

Postby superfury » 2019-2-01 @ 12:16

Managed to optimize it a bit by inlining the code and ignoring moving entries from the head to the head of the same queue(so in effect nothing happens, just wasted instructions).

TLB entry allocation/free/LRU/MRU handling:
Code: Select all
OPTINLINE void PagingTLB_initlists()
{
   byte set; //What set?
   byte index; //What index?
   TLB_ptr *us; //What is the current entry!
   for (set = 0; set < 4; ++set) //process all sets!
   {
      //Allocate a list-to-entry-mapping from the available entry space, with all items in ascending order in a linked list and index!
      for (index = 0; (index<8); ++index) //process all indexes!
      {
         CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].entry = &CPU[activeCPU].Paging_TLB.TLB[set][index]; //What entry(constant value)!
         CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].index = index; //What index are we(for lookups)?
      }
   }
}

OPTINLINE void PagingTLB_clearlists()
{
   byte set; //What set?
   byte index; //What index?
   TLB_ptr *us; //What is the current entry!
   for (set = 0; set < 4; ++set) //process all sets!
   {
      //Allocate a list from the available entry space, with all items in ascending order in a linked list and index!
      CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = NULL; //Nothing!
      CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set] = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set] = NULL; //Nothing!
      for (index = 7; ((index&0xFF)!=0xFF); --index) //process all indexes!
      {
         CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].allocated = 0; //We're in the free list!
         us = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index]; //What entry are we?
         us->prev = NULL; //We start out as the head for the added items here, so never anything before us!
         us->next = NULL; //We start out as the head, so next is automatically filled!
         if (likely(CPU[activeCPU].Paging_TLB.TLB_freelist_head[set])) //Head already set?
         {
            CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->prev = us; //We're the previous for the current head!
            us->next = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Our next is the head!
         }
         CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = us; //We're the new head!
         if (unlikely(CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] == NULL)) //No tail yet?
         {
            CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Tail=Head when starting out!
         }
      }
   }
}

//Move a TLB entry index from an old list to a new list!
OPTINLINE void Paging_moveListItem(TLB_ptr *listitem, TLB_ptr **newlist_head, TLB_ptr **newlist_tail, TLB_ptr **oldlist_head, TLB_ptr **oldlist_tail)
{
   if (likely(*newlist_head == listitem)) return; //Don't do anything when it's already at the correct spot!

   //First, remove us from the old head list!
   if (listitem->prev) //Do we have anything before us?
   {
      ((TLB_ptr *)listitem->prev)->next = listitem->next; //Remove us from the previous item of the list!
   }
   else //We're the head, so remove us from the list!
   {
      *oldlist_head = listitem->next; //Remove us from the head of the list and assign the new head!
   }

   if (listitem->next) //Did we have a next item?
   {
      ((TLB_ptr *)listitem->next)->prev = listitem->prev; //Remove us from the next item of the list!
   }
   else //We're the tail?
   {
      *oldlist_tail = listitem->prev; //Remove us from the tail of the list and assign the new tail!
   }

   listitem->next = NULL; //We don't have a next!
   listitem->prev = NULL; //We don't have a previous!

   /* Now, we're removed from the old list and a newly unmapped item! */

   //Now, insert us into the start of the new list!
   if (*newlist_head) //Anything in the new list already?
   {
      (*newlist_head)->prev = listitem; //We're at the start of the new list, so point the head to us, us to the head and make us the new head!
      listitem->next = *newlist_head; //Our next is the old head!
      *newlist_head = listitem; //We're the new head!
   }
   else //We're the new list?
   {
      *newlist_head = listitem; //We're the new head!
      *newlist_tail = listitem; //We're the new tail!
   }
}

OPTINLINE TLB_ptr *allocTLB(sbyte set) //Allocate a TLB entry!
{
   TLB_ptr *result;
   if (CPU[activeCPU].Paging_TLB.TLB_freelist_head) //Anything available?
   {
      result = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //What item are we allocating, take it from the free list!
      //Now take the item from the pool and move it to the used list!
      CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->allocated = 1; //We're allocated now!
      Paging_moveListItem(CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //What item to take!
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail
         &CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head
         &CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail
      return result; //Give the result!
   }
   return NULL; //Nothing to allocate!
}

OPTINLINE void freeTLB(sbyte set, byte TLB_index) //Make an entry available again!
{
   TLB_ptr *listitem;
   listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!
   if (listitem->allocated) //Are we allocated at all?
   {
      listitem->allocated = 0; //Mark us as freed!
      Paging_moveListItem(listitem, //What item to take!
         &CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //destination head
         &CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set], //destination tail
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //source head
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]); //source tail
   }
}

OPTINLINE void Paging_setNewestTLB(sbyte set, byte TLB_index) //Tick an TLB entry for making it the most recently used!
{
   TLB_ptr *listitem;
   listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!
   if (listitem->allocated) //Are we allocated at all?
   {
      Paging_moveListItem(listitem,
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set],
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]); //Move us to the start of the TLB used list to mark us as the most recently accessed!
   }
   else //We're not allocated, but marked as newest? Allocate us!
   {
      //Now take the item from the pool and move it to the used list!
      listitem->allocated = 1; //We're allocated now!
      Paging_moveListItem(listitem, //What item to take!
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head
         &CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail
         &CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head
         &CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail
   }
}

OPTINLINE byte Paging_oldestTLB(sbyte set) //Find a TLB to be used/overwritten!
{
   TLB_ptr *entry;
   if (CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]) //Anything not allocated yet?
   {
      if (entry = allocTLB(set)) //Allocated from the free list?
      {
         return entry->index; //Give the index of the resulting entry that's been allocated!
      }
   }
   else //Allocate from the tail(LRU), since everything is allocated!
   {
      if (CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]) //Gotten a tail? We're used, so take the LRU!
      {
         entry = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]; //What entry to take: the LRU!
         Paging_setNewestTLB(set, entry->index); //This is the newest TLB now!
         return entry->index; //What index is the LRU!
      }
   }
   return 7; //Safety: return the final entry! Shouldn't happen under normal circumstances.
}


TLB reads/writes/initialization/clearing:
Code: Select all
void Paging_writeTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 result)
{
   byte effectiveentry;
   uint_32 TAG,TAGMASKED;
   if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?
   TAG = Paging_generateTAG(logicaladdress, W, U, D); //Generate a TAG!
   byte entry;
   TAGMASKED = (TAG&0xFFFFF001); //Masked tag for fast lookup! Match P/U/W/address only! Thus dirty updates the existing entry, while other bit changing create a new entry!
   effectiveentry = 0;
   entry = 8; //Init for entry search not found!
   do
   {
      if (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][effectiveentry].allocated) //Allocated entry?
      {
         if ((CPU[activeCPU].Paging_TLB.TLB[TLB_set][effectiveentry].TAG & 0xFFFFF001) == TAGMASKED) //Match for our own entry?
         {
            entry = effectiveentry; //Reuse our own entry!
            break; //Stop searching: reuse the effective entry!
         }
      }
   } while (++effectiveentry < 8); //Check all entries!
   if (entry == 8) //Not found? Take the LRU!
   {
      entry = Paging_oldestTLB(TLB_set); //Get the oldest/unused TLB!
   }
   else //We're the newest TLB now!
   {
      Paging_setNewestTLB(TLB_set, entry); //We're the newest TLB now!
   }
   CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].data = result; //The result for the lookup!
   CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = TAG; //The TAG to find it by!
}

//RWDirtyMask: mask for ignoring set bits in the tag, use them otherwise!
byte Paging_readTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 WDMask, uint_32 *result, byte updateAges)
{
   INLINEREGISTER uint_32 TAG, TAGMask;
   INLINEREGISTER byte entry = 0;
   INLINEREGISTER TLBEntry *curentry;
   if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?
   TAG = Paging_generateTAG(logicaladdress,W,U,D); //Generate a TAG!
   TAGMask = ~WDMask; //Store for fast usage to mask the tag bits unused off!
   if (likely(WDMask)) //Used?
   {
      TAG &= TAGMask; //Ignoring these bits, so mask them off when comparing!
   }
   curentry = &CPU[activeCPU].Paging_TLB.TLB[TLB_set][0]; //What TLB entry to apply?
   do //Check all entries!
   {
       if (likely(((curentry->TAG&TAGMask)==TAG) && (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][entry].allocated))) //Found?
      {
         *result = curentry->data; //Give the stored data!
         Paging_setNewestTLB(TLB_set, entry); //Set us as the newest TLB!
         return 1; //Found!
      }
      ++curentry; //Next entry!
   } while (likely(++entry<8));
   return 0; //Not found!
}

void Paging_Invalidate(uint_32 logicaladdress) //Invalidate a single address!
{
   INLINEREGISTER byte TLB_set;
   INLINEREGISTER byte entry;
   for (TLB_set = 0; TLB_set < 4; ++TLB_set) //Process all possible sets!
   {
      for (entry = 0; entry < 8; ++entry) //Check all entries!
      {
         if (Paging_matchTLBaddress(logicaladdress, CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG) && (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][entry].allocated)) //Matched?
         {
            CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = 0; //Clear the entry to unused!
            freeTLB(TLB_set, entry); //Free this entry from the TLB!
         }
      }
   }
}

void Paging_clearTLB()
{
   memset(&CPU[activeCPU].Paging_TLB,0,sizeof(CPU[activeCPU].Paging_TLB)); //Reset fully and clear the TLB!
   PagingTLB_clearlists(); //Initialize the TLB lists to become empty!
}

void Paging_initTLB()
{
   PagingTLB_initlists(); //Initialize the TLB lists to become empty!
   Paging_clearTLB(); //Clear the TLB! This also calls clearlists, initializing the linked lists!
}
superfury
l33t
 
Posts: 3230
Joined: 2014-3-08 @ 11:25
Location: Netherlands


Return to PC Emulation

Who is online

Users browsing this forum: No registered users and 3 guests