exec() or fork() and when a
dynamically linked Linux process is started,
the process must remap its address space to incorporate shared libraries.
In this context, a TLB flush is
actually a TLB invalidate since we updated the page-table PTE dirty/modified
bits when we loaded the PTE into the hash table.
In the worst case, the search requires
16 memory references (2 hash table buckets, containing 8 PTE's each)
for each PTE being flushed. It is not uncommon for ranges of 40 -- 110
pages to be flushed in one shot.
The obvious strategy, and the first one we used, was for the OS to derive VSIDs from the process identifier (so that each process has a distinct virtual address space) and multiplying it by a scalar to scatter entries in the hash table. After doing this, we found that flushing the hash table was extremely expensive, we then came upon the idea of lazy TLB flushes. Our idea of how to do lazy TLB flushes was to keep a counter of memory-management contexts so we could provide unique numbers for use as VSID's instead of using the PID of a process. We reserved segments for the dynamically mapped parts of the kernel (static areas, data and text, are mapped by the BATs) and put a fixed VSID in these segments. When the kernel switched to a task its VSIDs could be loaded from the task structure into hardware registers by software.
When we needed to clear the TLB of all mappings associated with a particular task we only had to change the values (VSIDs) in the task structure and then update the hardware registers and increment the context counter. Even though there could be old PTEs from the previous context (previous VSIDs) in the hash table and TLB marked as valid PTEs (valid bit set in the PTE) their VSID's will not match any VSID's used by any process so incorrect matches won't be made. We could then keep a list of ``zombie'' VSID's (similar to ``zombie'' processes) that are marked as valid in the hash table but aren't actually used and clear them when hash table space became scarce.
What we finally settled on and implemented was different from what we had planned at first. Deciding when to really flush the old PTE's from the hash table and how to handle the ``zombie list'' was more complex than we wanted to deal with at first. Performance would also be inconsistent if we had to occasionally scan the hash table and invalidate ``zombie'' PTE's when we needed more space in the hash table. So, instead, we just allowed the hash table reload code to replace an entry when needed (not checking if it has a currently valid VSID or not). This gave a non-optimal replacement strategy in the hash table since we may replace real PTEs (have a currently active VSID) in the hash table even though there are PTEs that aren't being used (have the VSID of an old memory context).
We were later able to return to this idea of reducing the inefficiency of the hash table replacement algorithm (replacing unused PTE's from an abandoned memory management context marked as valid) by setting the idle task to reclaim zombie hash table entries by scanning the hash table when the cpu is idle and clearing the valid bit in zombie PTEs (physically invalidating those PTEs). This provided a nice balance of simplifying the actual low level assembly to reload the TLB and still maintaining a decent usage ratio of the hash table (zombie PTEs to in-use PTEs).
Without the code to reclaim zombie PTEs in the idle task, the ratio of hash table reloads to evicts (reloads that require a valid entry be replaced) was normally greater than 90%. Since the hot-spots were eliminated in the hash table, entries are scattered across all of the hash table and never invalidated. Invalidation in this case means the valid bit is never cleared even though the VSID may not match a current process. Very quickly the entire hash table fills up. Since the TLB reload code did not differentiate between the two types of invalid entries, it chose an arbitrary PTE to replace when reloading, replacing valid PTEs as well as zombie PTEs. With the reclaim code in the idle task, we saw a drastic decrease in the number of evicts. This is because the hash table reload code was usually able to find an empty TLB entry and was able to avoid replacing valid PTEs.
Our series of changes took hash table use up to 15% and finally down to around 5% since we effectively flush all the TLB entries of a process when doing large TLB flushes (by changing the VSID's of a process). Our optimization to reduce hot-spots in the hash table was not as significant since so few entries stayed in the hash table (about 600-700 out of 16384) at one time due to the flushing of ranges of PTEs. Even with this little of the hash table in use we measured 85% -- 95% hit rates in the hash table on TLB misses. To increase the percentage of hash table use, we could have decreased the size of the hash table and free RAM for use by the system but in performing these benchmarks we decided to keep the hash table size fixed to make comparisons more meaningful. This choice makes the hash table look inefficient with some optimizations but the net gain in performance as measured by hit rate in the hash table and wall-clock time shows it is in fact an advantage.
Another advantage of the idle task invalidating PTEs was that TLB reload code was usually able to find an empty entry in the hash table during a reload. This reduced the number of evicts so the ratio of evicts to TLB reloads became 30% instead of the greater than 90% we were seeing before. This reduced number of evicts also left the hash table with more in-use PTEs so our usage of the hash table jumped to 1400-2200 from 600-700 entries, or to 15% from 5%. The hit rate in the hash table on a TLB miss also increased to as high as 98% from 85%.
Using lazy TLB flushes increased pipe throughput by 5 MB/s (from 71 MB/s)
and reduced 8-process context switch times from 20
s to 17s.
However, the system continued to spend a great deal of time searching
the hash table because for certain operations, the
OS was attempting to clear a range of virtual addresses from the
TLB and hash table.
The OS must ensure that the new mappings are the only mappings for those
virtual addresses in the TLB and hash table. The system call to change
address space is mmap and LmBench showed
mmap() latency to be more than 3 milliseconds. The kernel was
clearing the range of addresses by searching the hash
table for each PTE in turn.
We fixed this problem by invalidating the whole memory management context
of any process needing to invalidate more than a small set of pages.
This effectively invalidates all of the TLB entries of this process.
This was a
cheap operation with the mechanism we used since it just involved a reset of
the VSID whose amortized cost (later TLB reloads vs. cost of flushing
specific PTEs) is much lower. Once the process received a new VSID and its old VSID
was marked as zombie, all the process' PTEs in the TLB and hash table
were automatically inactive. Of course, there is a performance penalty
here as we invalidate some translations that could have remained valid,
but using 20 pages as the cutoff point mmap() latency dropped to
-- an 80 times improvement. Pipe bandwidth increased noticeably and
several latencies dropped as well. These changes come at no cost to the
TLB hit rate since no more or fewer TLB misses occurred with the tunable
parameter to flushing ranges of PTEs. This suggests that the TLB entries
being invalidated along with target range of TLBs were not being used
anyway - so there is no cost for losing them.
Table 2 shows the 603 doing software searches of the hash table and a 604 doing hardware searches with the effect of lazy TLB flushes. Note that the 603 hash table search is using software TLB miss handlers that emulate the 604 hardware search. This table shows the gain from avoiding expensive searches in the hash table when a simple resetting of the VSID's will do.