VOGONS

Optimizing 8 entry TLB using linked lists?

First post, by superfury

Rank l33t
Rank
l33t

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)?

Reply 1 of 4, by superfury

Rank l33t
Rank
l33t

Just took a look at https://www.quora.com/Why-is-doubly-linked-li … e-GeeksforGeeks .

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/unipcemu/src/ … ing.c?at=master

The core of the new TLB LRU algorithm is:

`1`typedef struct`2`{`3`	uint_32 data; //80386 4-way associative TLB results!`4`	uint_32 TAG; //All TAGs used with the respective TLB!`5`} TLBEntry;`67`typedef struct`8`{`9`	TLBEntry *entry; //What entry are we?`10`	byte index; //What index is said entry?`11`	void *prev, *next; //Previous and next pointers!`12`	byte allocated; //Are we allocated?`13`} TLB_ptr;`1415`typedef struct`16`{`17`	TLBEntry TLB[4][8]; //All TLB entries to use!`18`	TLB_ptr TLB_listnodes[4][8]; //All nodes for all TLB entries!`19`	TLB_ptr *TLB_freelist_head[4], *TLB_freelist_tail[4]; //Head and tail of the free list!`20`	TLB_ptr *TLB_usedlist_head[4], *TLB_usedlist_tail[4]; //Head and tail of the used list!`21`} CPU_TLB; //A TLB to use for the CPU!``
`1`void PagingTLB_initlists()`2`{`3`	byte set; //What set?`4`	byte index; //What index?`5`	TLB_ptr *us; //What is the current entry!`6`	for (set = 0; set < 4; ++set) //process all sets!`7`	{`8`		//Allocate a list from the available entry space, with all items in ascending order in a linked list and index!`9`		CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = NULL; //Nothing!`10`		CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set] = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set] = NULL; //Nothing!`11`		for (index = 7; ((index&0xFF)!=0xFF); --index) //process all indexes!`12`		{`13`			CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].entry = &CPU[activeCPU].Paging_TLB.TLB[set][index]; //What entry(constant value)!`14`			CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].index = index; //What index are we(for lookups)?`15`			CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].allocated = 0; //We're in the free list!`16`			us = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index]; //What entry are we?`17`			us->prev = NULL; //We start out as the head for the added items here, so never anything before us!`18`			us->next = NULL; //We start out as the head, so next is automatically filled!`19`			if (CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]) //Head already set?`20`			{`21`				CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->prev = us; //We're the previous for the current head!`22`				us->next = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Our next is the head!`23`			}`24`			CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = us; //We're the new head!`25`			if (CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] == NULL) //No tail yet?`26`			{`27`				CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Tail=Head when starting out!`28`			}`29`		}`30`	}`31`}`3233`//Move a TLB entry index from an old list to a new list!`34`void Paging_moveListItem(TLB_ptr *listitem, TLB_ptr **newlist_head, TLB_ptr **newlist_tail, TLB_ptr **oldlist_head, TLB_ptr **oldlist_tail)`35`{`36`	//First, remove us from the old head list!`37`	if (listitem->prev) //Do we have anything before us?`38`	{`39`		((TLB_ptr *)listitem->prev)->next = listitem->next; //Remove us from the previous item of the list!`40`	}`41`	else //We're the head, so remove us from the list!`42`	{`43`		*oldlist_head = listitem->next; //Remove us from the head of the list and assign the new head!`44`	}`4546`	if (listitem->next) //Did we have a next item?`47`	{`48`		((TLB_ptr *)listitem->next)->prev = listitem->prev; //Remove us from the next item of the list!`49`	}`50`	else //We're the tail?`51`	{`52`		*oldlist_tail = listitem->prev; //Remove us from the tail of the list and assign the new tail!`53`	}`5455`	listitem->next = NULL; //We don't have a next!`56`	listitem->prev = NULL; //We don't have a previous!`5758`	/* Now, we're removed from the old list and a newly unmapped item! */`5960`	//Now, insert us into the start of the new list!``
`61`	if (*newlist_head) //Anything in the new list already?`62`	{`63`		(*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!`64`		listitem->next = *newlist_head; //Our next is the old head!`65`		*newlist_head = listitem; //We're the new head!`66`	}`67`	else //We're the new list?`68`	{`69`		*newlist_head = listitem; //We're the new head!`70`		*newlist_tail = listitem; //We're the new tail!`71`	}`72`}`7374`TLB_ptr *allocTLB(sbyte set) //Allocate a TLB entry!`75`{`76`	TLB_ptr *result;`77`	if (CPU[activeCPU].Paging_TLB.TLB_freelist_head) //Anything available?`78`	{`79`		result = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //What item are we allocating, take it from the free list!`80`		//Now take the item from the pool and move it to the used list!`81`		CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->allocated = 1; //We're allocated now!`82`		Paging_moveListItem(CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //What item to take!`83`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head`84`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail`85`			&CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head`86`			&CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail`87`		return result; //Give the result!`88`	}`89`	return NULL; //Nothing to allocate!`90`}`9192`void freeTLB(sbyte set, byte TLB_index) //Make an entry available again!`93`{`94`	TLB_ptr *listitem;`95`	listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!`96`	if (listitem->allocated) //Are we allocated at all?`97`	{`98`		listitem->allocated = 0; //Mark us as freed!`99`		Paging_moveListItem(listitem, //What item to take!`100`			&CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //destination head`101`			&CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set], //destination tail`102`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //source head`103`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]); //source tail`104`	}`105`}`106107`void Paging_setNewestTLB(sbyte set, byte TLB_index) //Tick an TLB entry for making it the most recently used!`108`{`109`	TLB_ptr *listitem;`110`	listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!`111`	if (listitem->allocated) //Are we allocated at all?`112`	{`113`		Paging_moveListItem(listitem,`114`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],`115`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set],`116`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],`117`			&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!`118`	}`119`	else //We're not allocated, but marked as newest? Allocate us!`120`	{`121`		listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!`122`		//Now take the item from the pool and move it to the used list!`123`		listitem->allocated = 1; //We're allocated now!`124`		Paging_moveListItem(listitem, //What item to take!`125`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head`126`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail`127`			&CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head`128`			&CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail`129`	}`130`}`131132`byte Paging_oldestTLB(sbyte set) //Find a TLB to be used/overwritten!`133`{`134`	TLB_ptr *entry;`135`	if (CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]) //Anything not allocated yet?`136`	{`137`		if (entry = allocTLB(set)) //Allocated from the free list?`138`		{`139`			return entry->index; //Give the index of the resulting entry that's been allocated!`140`		}`141`	}`142`	else //Allocate from the tail(LRU), since everything is allocated!`143`	{`144`		if (CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]) //Gotten a tail? We're used, so take the LRU!`145`		{`146`			entry = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]; //What entry to take: the LRU!`147`			Paging_setNewestTLB(set, entry->index); //This is the newest TLB now!`148`			return entry->index; //What index is the LRU!`149`		}`150`	}`151`	return 7;`152`}``

`1`void Paging_writeTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 result)`2`{`3`	byte effectiveentry;`4`	uint_32 TAG,TAGMASKED;`5`	if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?`6`	TAG = Paging_generateTAG(logicaladdress, W, U, D); //Generate a TAG!`7`	byte entry;`8`	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!`9`	effectiveentry = 0;`10`	entry = 8; //Init for entry search not found!`11`	do`12`	{`13`		if (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][effectiveentry].allocated) //Allocated entry?`14`		{`15`			if ((CPU[activeCPU].Paging_TLB.TLB[TLB_set][effectiveentry].TAG & 0xFFFFF001) == TAGMASKED) //Match for our own entry?`16`			{`17`				entry = effectiveentry; //Reuse our own entry!`18`				break; //Stop searching: reuse the effective entry!`19`			}`20`		}`21`	} while (++effectiveentry < 8); //Check all entries!`22`	if (entry == 8) //Not found? Take the LRU!`23`	{`24`		entry = Paging_oldestTLB(TLB_set); //Get the oldest/unused TLB!`25`	}`26`	else //We're the newest TLB now!`27`	{`28`		Paging_setNewestTLB(TLB_set, entry); //We're the newest TLB now!`29`	}`30`	CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].data = result; //The result for the lookup!`31`	CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = TAG; //The TAG to find it by!`32`}`3334`//RWDirtyMask: mask for ignoring set bits in the tag, use them otherwise!`35`byte Paging_readTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 WDMask, uint_32 *result, byte updateAges)`36`{`37`	INLINEREGISTER uint_32 TAG, TAGMask;`38`	INLINEREGISTER byte entry = 0;`39`	INLINEREGISTER TLBEntry *curentry;`40`	if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?`41`	TAG = Paging_generateTAG(logicaladdress,W,U,D); //Generate a TAG!`42`	TAGMask = ~WDMask; //Store for fast usage to mask the tag bits unused off!`43`	if (likely(WDMask)) //Used?`44`	{`45`		TAG &= TAGMask; //Ignoring these bits, so mask them off when comparing!`46`	}`47`	curentry = &CPU[activeCPU].Paging_TLB.TLB[TLB_set][0]; //What TLB entry to apply?`48`	do //Check all entries!`49`	{`50` 		if (likely(((curentry->TAG&TAGMask)==TAG) && (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][entry].allocated))) //Found?`51`		{`52`			*result = curentry->data; //Give the stored data!`53`			Paging_setNewestTLB(TLB_set, entry); //Set us as the newest TLB!`54`			return 1; //Found!`55`		}`56`		++curentry; //Next entry!`57`	} while (likely(++entry<8));`58`	return 0; //Not found!`59`}`60`
`61`void Paging_Invalidate(uint_32 logicaladdress) //Invalidate a single address!`62`{`63`	INLINEREGISTER byte TLB_set;`64`	INLINEREGISTER byte entry;`65`	for (TLB_set = 0; TLB_set < 4; ++TLB_set) //Process all possible sets!`66`	{`67`		for (entry = 0; entry < 8; ++entry) //Check all entries!`68`		{`69`			if (Paging_matchTLBaddress(logicaladdress, CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG)) //Matched?`70`			{`71`				CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = 0; //Clear the entry to unused!`72`				freeTLB(TLB_set, entry); //Free this entry from the TLB!`73`			}`74`		}`75`	}`76`}`7778`void Paging_clearTLB()`79`{`80`	memset(&CPU[activeCPU].Paging_TLB,0,sizeof(CPU[activeCPU].Paging_TLB)); //Reset fully and clear the TLB!`81`	PagingTLB_initlists(); //Initialize the TLB lists to become empty!`82`}``

I still see Windows NT booting like always, so it can't be that wrong? What are your opinions?

Reply 2 of 4, by superfury

Rank l33t
Rank
l33t

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).

Reply 4 of 4, by superfury

Rank l33t
Rank
l33t

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:

`1`OPTINLINE void PagingTLB_initlists()`2`{`3`	byte set; //What set?`4`	byte index; //What index?`5`	TLB_ptr *us; //What is the current entry!`6`	for (set = 0; set < 4; ++set) //process all sets!`7`	{`8`		//Allocate a list-to-entry-mapping from the available entry space, with all items in ascending order in a linked list and index!`9`		for (index = 0; (index<8); ++index) //process all indexes!`10`		{`11`			CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].entry = &CPU[activeCPU].Paging_TLB.TLB[set][index]; //What entry(constant value)!`12`			CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].index = index; //What index are we(for lookups)?`13`		}`14`	}`15`}`1617`OPTINLINE void PagingTLB_clearlists()`18`{`19`	byte set; //What set?`20`	byte index; //What index?`21`	TLB_ptr *us; //What is the current entry!`22`	for (set = 0; set < 4; ++set) //process all sets!`23`	{`24`		//Allocate a list from the available entry space, with all items in ascending order in a linked list and index!`25`		CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = NULL; //Nothing!`26`		CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set] = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set] = NULL; //Nothing!`27`		for (index = 7; ((index&0xFF)!=0xFF); --index) //process all indexes!`28`		{`29`			CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index].allocated = 0; //We're in the free list!`30`			us = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][index]; //What entry are we?`31`			us->prev = NULL; //We start out as the head for the added items here, so never anything before us!`32`			us->next = NULL; //We start out as the head, so next is automatically filled!`33`			if (likely(CPU[activeCPU].Paging_TLB.TLB_freelist_head[set])) //Head already set?`34`			{`35`				CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->prev = us; //We're the previous for the current head!`36`				us->next = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Our next is the head!`37`			}`38`			CPU[activeCPU].Paging_TLB.TLB_freelist_head[set] = us; //We're the new head!`39`			if (unlikely(CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] == NULL)) //No tail yet?`40`			{`41`				CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set] = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //Tail=Head when starting out!`42`			}`43`		}`44`	}`45`}`4647`//Move a TLB entry index from an old list to a new list!`48`OPTINLINE void Paging_moveListItem(TLB_ptr *listitem, TLB_ptr **newlist_head, TLB_ptr **newlist_tail, TLB_ptr **oldlist_head, TLB_ptr **oldlist_tail)`49`{`50`	if (likely(*newlist_head == listitem)) return; //Don't do anything when it's already at the correct spot!`5152`	//First, remove us from the old head list!`53`	if (listitem->prev) //Do we have anything before us?`54`	{`55`		((TLB_ptr *)listitem->prev)->next = listitem->next; //Remove us from the previous item of the list!`56`	}`57`	else //We're the head, so remove us from the list!`58`	{`59`		*oldlist_head = listitem->next; //Remove us from the head of the list and assign the new head!`60`	}``
`6162`	if (listitem->next) //Did we have a next item?`63`	{`64`		((TLB_ptr *)listitem->next)->prev = listitem->prev; //Remove us from the next item of the list!`65`	}`66`	else //We're the tail?`67`	{`68`		*oldlist_tail = listitem->prev; //Remove us from the tail of the list and assign the new tail!`69`	}`7071`	listitem->next = NULL; //We don't have a next!`72`	listitem->prev = NULL; //We don't have a previous!`7374`	/* Now, we're removed from the old list and a newly unmapped item! */`7576`	//Now, insert us into the start of the new list!`77`	if (*newlist_head) //Anything in the new list already?`78`	{`79`		(*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!`80`		listitem->next = *newlist_head; //Our next is the old head!`81`		*newlist_head = listitem; //We're the new head!`82`	}`83`	else //We're the new list?`84`	{`85`		*newlist_head = listitem; //We're the new head!`86`		*newlist_tail = listitem; //We're the new tail!`87`	}`88`}`8990`OPTINLINE TLB_ptr *allocTLB(sbyte set) //Allocate a TLB entry!`91`{`92`	TLB_ptr *result;`93`	if (CPU[activeCPU].Paging_TLB.TLB_freelist_head) //Anything available?`94`	{`95`		result = CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]; //What item are we allocating, take it from the free list!`96`		//Now take the item from the pool and move it to the used list!`97`		CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]->allocated = 1; //We're allocated now!`98`		Paging_moveListItem(CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //What item to take!`99`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head`100`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail`101`			&CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head`102`			&CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail`103`		return result; //Give the result!`104`	}`105`	return NULL; //Nothing to allocate!`106`}`107108`OPTINLINE void freeTLB(sbyte set, byte TLB_index) //Make an entry available again!`109`{`110`	TLB_ptr *listitem;`111`	listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!`112`	if (listitem->allocated) //Are we allocated at all?`113`	{`114`		listitem->allocated = 0; //Mark us as freed!`115`		Paging_moveListItem(listitem, //What item to take!`116`			&CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //destination head`117`			&CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set], //destination tail`118`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //source head`119`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]); //source tail`120`	}`121`}`122123`OPTINLINE void Paging_setNewestTLB(sbyte set, byte TLB_index) //Tick an TLB entry for making it the most recently used!`124`{`125`	TLB_ptr *listitem;`126`	listitem = &CPU[activeCPU].Paging_TLB.TLB_listnodes[set][TLB_index]; //Our entry!`127`	if (listitem->allocated) //Are we allocated at all?`128`	{`129`		Paging_moveListItem(listitem,`130`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],`131`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set],`132`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set],`133`			&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!`134`	}`135`	else //We're not allocated, but marked as newest? Allocate us!`136`	{`137`		//Now take the item from the pool and move it to the used list!`138`		listitem->allocated = 1; //We're allocated now!`139`		Paging_moveListItem(listitem, //What item to take!`140`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_head[set], //destination head`141`			&CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set], //destination tail`142`			&CPU[activeCPU].Paging_TLB.TLB_freelist_head[set], //source head`143`			&CPU[activeCPU].Paging_TLB.TLB_freelist_tail[set]); //source tail`144`	}`145`}`146147`OPTINLINE byte Paging_oldestTLB(sbyte set) //Find a TLB to be used/overwritten!`148`{`149`	TLB_ptr *entry;`150`	if (CPU[activeCPU].Paging_TLB.TLB_freelist_head[set]) //Anything not allocated yet?`151`	{`152`		if (entry = allocTLB(set)) //Allocated from the free list?`153`		{`154`			return entry->index; //Give the index of the resulting entry that's been allocated!`155`		}`156`	}`157`	else //Allocate from the tail(LRU), since everything is allocated!`158`	{`159`		if (CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]) //Gotten a tail? We're used, so take the LRU!`160`		{`161`			entry = CPU[activeCPU].Paging_TLB.TLB_usedlist_tail[set]; //What entry to take: the LRU!`162`			Paging_setNewestTLB(set, entry->index); //This is the newest TLB now!`163`			return entry->index; //What index is the LRU!`164`		}`165`	}`166`	return 7; //Safety: return the final entry! Shouldn't happen under normal circumstances.`167`}``

`1`void Paging_writeTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 result)`2`{`3`	byte effectiveentry;`4`	uint_32 TAG,TAGMASKED;`5`	if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?`6`	TAG = Paging_generateTAG(logicaladdress, W, U, D); //Generate a TAG!`7`	byte entry;`8`	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!`9`	effectiveentry = 0;`10`	entry = 8; //Init for entry search not found!`11`	do`12`	{`13`		if (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][effectiveentry].allocated) //Allocated entry?`14`		{`15`			if ((CPU[activeCPU].Paging_TLB.TLB[TLB_set][effectiveentry].TAG & 0xFFFFF001) == TAGMASKED) //Match for our own entry?`16`			{`17`				entry = effectiveentry; //Reuse our own entry!`18`				break; //Stop searching: reuse the effective entry!`19`			}`20`		}`21`	} while (++effectiveentry < 8); //Check all entries!`22`	if (entry == 8) //Not found? Take the LRU!`23`	{`24`		entry = Paging_oldestTLB(TLB_set); //Get the oldest/unused TLB!`25`	}`26`	else //We're the newest TLB now!`27`	{`28`		Paging_setNewestTLB(TLB_set, entry); //We're the newest TLB now!`29`	}`30`	CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].data = result; //The result for the lookup!`31`	CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = TAG; //The TAG to find it by!`32`}`3334`//RWDirtyMask: mask for ignoring set bits in the tag, use them otherwise!`35`byte Paging_readTLB(sbyte TLB_set, uint_32 logicaladdress, byte W, byte U, byte D, uint_32 WDMask, uint_32 *result, byte updateAges)`36`{`37`	INLINEREGISTER uint_32 TAG, TAGMask;`38`	INLINEREGISTER byte entry = 0;`39`	INLINEREGISTER TLBEntry *curentry;`40`	if (TLB_set < 0) TLB_set = Paging_TLBSet(logicaladdress); //Auto set?`41`	TAG = Paging_generateTAG(logicaladdress,W,U,D); //Generate a TAG!`42`	TAGMask = ~WDMask; //Store for fast usage to mask the tag bits unused off!`43`	if (likely(WDMask)) //Used?`44`	{`45`		TAG &= TAGMask; //Ignoring these bits, so mask them off when comparing!`46`	}`47`	curentry = &CPU[activeCPU].Paging_TLB.TLB[TLB_set][0]; //What TLB entry to apply?`48`	do //Check all entries!`49`	{`50` 		if (likely(((curentry->TAG&TAGMask)==TAG) && (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][entry].allocated))) //Found?`51`		{`52`			*result = curentry->data; //Give the stored data!`53`			Paging_setNewestTLB(TLB_set, entry); //Set us as the newest TLB!`54`			return 1; //Found!`55`		}`56`		++curentry; //Next entry!`57`	} while (likely(++entry<8));`58`	return 0; //Not found!`59`}`60`
`61`void Paging_Invalidate(uint_32 logicaladdress) //Invalidate a single address!`62`{`63`	INLINEREGISTER byte TLB_set;`64`	INLINEREGISTER byte entry;`65`	for (TLB_set = 0; TLB_set < 4; ++TLB_set) //Process all possible sets!`66`	{`67`		for (entry = 0; entry < 8; ++entry) //Check all entries!`68`		{`69`			if (Paging_matchTLBaddress(logicaladdress, CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG) && (CPU[activeCPU].Paging_TLB.TLB_listnodes[TLB_set][entry].allocated)) //Matched?`70`			{`71`				CPU[activeCPU].Paging_TLB.TLB[TLB_set][entry].TAG = 0; //Clear the entry to unused!`72`				freeTLB(TLB_set, entry); //Free this entry from the TLB!`73`			}`74`		}`75`	}`76`}`7778`void Paging_clearTLB()`79`{`80`	memset(&CPU[activeCPU].Paging_TLB,0,sizeof(CPU[activeCPU].Paging_TLB)); //Reset fully and clear the TLB!`81`	PagingTLB_clearlists(); //Initialize the TLB lists to become empty!`82`}`8384`void Paging_initTLB()`85`{`86`	PagingTLB_initlists(); //Initialize the TLB lists to become empty!`87`	Paging_clearTLB(); //Clear the TLB! This also calls clearlists, initializing the linked lists!`88`}``