Translation Lookaside Buffer Management (mm_tlb.c, mm_tlb_asid.c)

Exception handling

There are two exceptions handled to provide updating of TLB entries:

• TLB Refill
  • Handled by tlbrefill() function.
  • Recognises which virtual address (precisely Virtual Page Number - VPN¹) has been accessed and searches pagetables for appropriate physical address (Physical Frame Number - PFN²) - see the  Page Tables section.
  • Determines which ASID (Address Space Identifier) is assigned to the current thread. If there is no ASID assigned assignes some (this process is described later in detail).
  • Writes the ASID and virtual address translation (VPN and PFN) to the TLB at random position.
• TLB Invalid
  • Handled by tlbinvalid() function.
  • Same as TLB Refill but writes only PFN at specified index in the TLB (at index where the processor has found an invalid bit set).

ASID Assigning

There are only 256 values (0 - 255) of ASIDs available so if we want to allow running more "processes"³ simultaneously we have to assign ASIDs dynamicaly. ASID 255 is reserved. This number means invalid value.

ASID assigned to a thread is written in its _thread structure in the  asid field unless some pagetable is associated with the thread. If so, the value of the asid field is undefined and the current ASID is written in the pagetable_thread structure. Value 255 means no ASID has been assigned to this thread. If thread with no ASID assigned wants to access memory at some virtual address then appropriate entry must be written to TLB. That's why we need some valid ASID assign to that thread in such case. Process of determination the current thread's ASID follows:

1. If there is a pagetable associated with current thread and the pagetable contains a valid ASID than this one is returned. Otherwise, if the pagetable contains the invalid ASID than go to 3.
2. Is there valid ASID in thread's structure? Return it if so.
3. Is there some ASID unassigned (we determine it using the  used_asids array which is described later)? Return it if so.
4. If all ASIDs are currently used (note that this can occur only if more than 254 processes are running) then we search for some asid that is not written somewhere in TLB now. In such a case there will be no need for changing of TLB entries later. ASIDs that are not in the TLB are determined using asids_in_tlb_bitmap bitmap which is described later. If there is some ASID with associated bit in this bitmap zeroed (so the ASID is not in the TLB) then we assign this ASID to the current thread. The invalid ASID is assigned to a thread whose ASID has been assigned now.
5. In rare cases it may happen all bits in the asids_in_tlb_bitmap bitmap are set. In such a case the bitmap is refreshed by curreent values from the TLB. This operation makes it possible to perform the step number 4 now successfully. So go to 4.

Data structures for ASID assigning

• used_asids array
  An array of 256 pointers to threads. A pointer on index i points to the one of threads which have currently assigned ASID i (note that all threads sharing the same address space have at most one common ASID assigned). If some ASID is unassigned appropriate field in the array is NULL. The array is used for searching for unused ASIDs and for a quick access to a thread structure. These operations are needed when assigning ASID of some thread to another one.
• asids_in_tlb_bitmap bitmap
  If an ASID is in TLB appropriate bit is set in this bitmap. However, a bit which is set in this bitmap doesn't mean that the appropriate ASID is really written in TLB. This ASID could be rewritten with another entry while writing to random position. Bitmap is used to find out wich ASIDs can be assigned without modifying TLB if all asids are used.
  It is updated when a thread is being killed.
• asid_last_assigned
  This value is for optimization only. Every time we assign ASID we write its value to asid_last_assigned.
  If we search for unused ASID in used_asids array we start searching after the asid_last_assigned index, so we have chance that the search for unused ASID takes fewer steps.

1) Virtual Page Number is 20-bits long number of 4KB block in 4GB address space. All addresses that points to the same 4KB block of memory have the same VPN. Simply, VPN is upper 20 bits from 32-bits long virtual address.

2) Physical Frame Number is 24-bits long number of 4KB block in 64GB physical address space. Same as VPN in virtual addres space, so upper 24 bits of physical address creates PFN of block of physical addres space to that address belongs.

3) Process means group of threads sharing one address space. There is no structure associated with process in kernel right now.