TLB-Hit Model

  • TLB-Hit Model: A performance model that stores frequently used conversion results or policy judgment results in a fast path and omits the complex judgment process when the same request comes again.
  • TLB stands for Translation Lookaside Buffer. CPU is a structure that caches the recently used address conversion results when converting a virtual address to a physical address.
    • When CPU accesses memory, searching the Page Table sequentially each time is expensive. Therefore, the recently used address conversion result is saved in TLB, and when the same address area is accessed again, the conversion result is immediately retrieved from TLB.
  • TLB-Hit Model extends the operation method of TLB into a general system performance optimization model.
    • In other words, instead of performing full verification every time for repeatedly occurring requests, previously calculated results are stored in the cache and quickly reused.

Basic TLB Concepts

To understand TLB, you must first understand virtual memory and address translation.

In modern operating systems, processes do not use physical memory addresses directly, but use virtual addresses.

From the process’s perspective, it appears to be using its own independent memory space, but in reality, the operating system and MMU convert virtual addresses into physical addresses to access memory.

For example, if a process accesses the following address:

0x7fffffff1234

This address is a virtual address, not an actual physical memory address.

In order for CPU to read the data at this address, it must know where the virtual address is mapped to in actual physical memory.

The data structure used at this time is Page Table.

  • Virtual Address: Virtual address used by the process
  • Physical Address: Physical address of real memory
  • Page Table: Table that stores mapping information between virtual addresses and physical addresses.
  • MMU: Hardware component that performs address translation
  • TLB: Fast cache for caching recent address translation results

In other words, TLB exists to reduce the cost of searching the Page Table each time.

Address Translation

Address translation is the process of converting a virtual address into a physical address.

When a process accesses memory, CPU does not immediately use the address as a physical memory address.

First, address conversion is performed through MMU.

The address conversion process proceeds roughly as follows.

  1. CPU requests memory access with a virtual address.
  2. MMU checks whether the conversion information for the corresponding virtual address is in TLB.
  3. If there is conversion information in TLB, the physical address is obtained immediately.
  4. If there is no conversion information in TLB, search the Page Table.
  5. If you find conversion information in the Page Table, save it in TLB.
  6. Access real memory using the converted physical address.

At this time, the case where there is conversion information in TLB, as in number 3, is called TLB Hit, and the case where, as in number 4, there is no conversion information in TLB and the Page Table must be searched, it is called TLB Miss.

TLB Hit

TLB Hit is a case where the necessary address conversion information already exists in TLB.

For example, when CPU attempts to access a specific virtual address, if the physical frame to which the corresponding virtual page is mapped is stored in TLB, there is no need to search the Page Table again.

In this case, MMU directly uses the conversion information stored in TLB.

Virtual Address
        ↓
      TLB
        ↓
Physical Address

When TLB Hit occurs, the address conversion process ends very quickly.

In other words, TLB Hit can be viewed as similar to a cache hit.

Just as you do not need to go down to memory if you find data directly in the cache, you do not need to search the Page Table if you find address translation information directly in TLB.

TLB Miss

TLB Miss is a case where the necessary address conversion information is not in TLB.

If there is no conversion information in TLB, MMU must search the Page Table to find the physical address corresponding to the virtual address.

Virtual Address
        ↓
      TLB
        ↓
     Miss
        ↓
   Page Table Walk
        ↓
Physical Address

This process is called Page Table Walk or Page Walk.

Page Walk is much more expensive than TLB Hit.

In particular, because the x86-64 environment uses a multi-level Page Table structure, it may be necessary to read multiple levels of Page Table Entry for one address conversion.

As a general 4-level paging standard, the following structure can be achieved.

PML4
 ↓
PDPT
 ↓
PD
 ↓
PT
 ↓
Physical Page

In other words, when TLB Miss occurs, multiple levels of memory access may be added rather than simply being checked one more time.

So, even if the memory access itself exists in the cache, if TLB Miss occurs in address translation, the overall access time may increase.

TLB Hit Rate

TLB Hit Rate is the rate at which TLB Hit occurs among all address conversion requests.

TLB Hit Rate = TLB Hit Count / Total Translation Count

For example, if 1000 total address conversion requests occurred, and 990 of them were TLB Hits, the TLB Hit Rate is 99%.

990 / 1000 = 0.99

TLB A high Hit Rate means that most address translations are processed in the fast path.

Conversely, a high TLB Miss Rate means that page walks occur frequently.

TLB Miss Rate = 1 - TLB Hit Rate

If TLB Hit Rate is 99%, TLB Miss Rate is 1%.

Core Idea of the TLB-Hit Model

The core of the TLB-Hit Model is to process repetitive tasks in a fast route.

Originally, TLB caches the address translation results.

However, if we generalize this structure, it can be seen as follows.

  • Frequently repeated requests are stored in the cache.
  • When the same request comes again, it is immediately judged in the cache.
  • Only requests that are not in the cache or are complex are sent to the slow path.
  • When policy or state changes, existing caches are invalidated.

In other words, the TLB-Hit Model is not simple caching, but a model that reduces the average cost of the entire system by separating fast and slow paths.

Request
   ↓
Fast Path Cache
   ↓
Hit  →  Cached Decision
Miss →  Full Evaluation

The important thing here is not to put every request into the cache.

You should only cache requests that are highly repeatable, can reuse the same results, and can be safely invalidated based on state changes.

Fast Path and Slow Path

In TLB-Hit Model, it is usually considered to be divided into Fast Path and Slow Path.

  • Fast Path: Fast path executed when a cache hit occurs.
  • Slow Path: A slow path that performs full judgment when a cache miss occurs.

Fast Path should be very simple.

If you perform tasks like complex string comparisons, many condition checks, external communication, or dynamic memory allocation within the Fast Path, the Fast Path becomes less meaningful.

Conversely, Slow Path can perform relatively complex judgments.

For example, if you have a security policy judgment system, Slow Path can perform the following tasks.

  • Command path inspection
  • File path prefix check
  • Network address check
  • Process permission check
  • Policy table navigation
  • Audit log generation

However, if the same request is repeated, there is no need to perform this process every time.

The results determined as Slow Path in the first request are stored in the cache, and subsequent requests can be processed directly in Fast Path.

Decision Cache

By applying the TLB-Hit Model to security policy judgment, a structure called Decision Cache can be created.

Decision Cache is a cache that stores policy decision results for specific requests.

For example, if you have the following request:

process: mcp-agent
operation: file_open
path: /home/user/workspace/test.txt

If the policy engine checks this request and determines it is allowed, it can store this result in the cache.

key   = mcp-agent:file_open:/home/user/workspace/test.txt
value = allow

Later, when the same process tries to open the same file again, the allow result stored in the cache can be used immediately without rechecking the entire policy.

Request
   ↓
Decision Cache
   ↓
allow

The reason this structure is similar to the TLB-Hit Model is because, just as TLB stores the address conversion results, the Decision Cache stores the policy judgment results.

  • TLB: Virtual Address → Physical Address
  • Decision Cache: Request Key → Policy Decision

In other words, if the TLB-Hit Model is applied to the policy engine, it can be expanded to a policy decision cache rather than an address translation cache.

Cache Key

One of the important things in TLB-Hit Model is Cache Key.

Cache Key is a value to distinguish which request is the same request.

If the Cache Key is made too simple, different requests may be mistakenly judged to be the same request.

Conversely, if the Cache Key is made too complicated, cache hits are unlikely to occur.

For example, if you are caching a file access policy, the following elements can be used as a Cache Key.

  • process identifier
  • job type
  • file path
  • access rights
  • policy generation number
  • Namespace information
  • user identifier

Problems may arise if you simply use the file path as the Cache Key.

key = /etc/passwd

This makes it impossible to tell which process accessed it, whether it was reading or writing, and what the current policy is.

So, in an actual policy cache, a key is usually created by tying together information that can distinguish the meaning of the request.

key = process_id + operation + resource_id + permission + policy_epoch

In this way, even for the same resource, if the access subject or access method is different, it can be judged as a different request.

Cost Difference Between Hits and Misses

TLB-Hit Model is based on the premise of the cost difference between hit and miss.

If the cost of a cache hit is similar to the cost of a miss, there is no reason to have a cache.

For the TLB-Hit Model to be effective, the following conditions are required.

  • Fast Path costs must be sufficiently small.
  • Slow Path costs must be relatively large.
  • The same request must occur repeatedly.
  • The cost of cache invalidation should not be excessively large.

For example, the policy decision cost can be simplified and expressed as follows.

Average Cost = Hit Rate * Hit Cost + Miss Rate * Miss Cost

The higher the Hit Rate and the smaller the Hit Cost, the lower the overall average cost.

For example, if you have the following values:

Hit Rate  = 0.99
Hit Cost  = 100ns
Miss Cost = 5000ns

The average cost can be calculated as follows:

Average Cost = 0.99 * 100ns + 0.01 * 5000ns
             = 99ns + 50ns
             = 149ns

Conversely, if the Hit Rate is 50%, it will be as follows.

Average Cost = 0.5 * 100ns + 0.5 * 5000ns
             = 50ns + 2500ns
             = 2550ns

In other words, it is very important to keep the Hit Rate high in the TLB-Hit Model.

Locality

The reason why TLB-Hit Model works well is because locality exists in programs or system requests.

Locality is the property that recently used data or resources are likely to be used again.

Locality can be broadly divided into two types.

  • Temporal Locality: Recently accessed objects are more likely to be accessed again
  • Spatial Locality: There is a high probability of approaching other objects nearby the object being approached.

In TLB, if you access the same page repeatedly, TLB Hit is likely to occur due to Temporal Locality.

Additionally, if adjacent memory areas are accessed sequentially, conversion information from the same page or nearby pages may be reused due to spatial locality.

Similar locality can also appear in policy decisions.

For example, if an MCP Agent repeatedly reads and writes files within a specific workspace, the same path prefix access is repeated.

/home/user/workspace/a.txt
/home/user/workspace/b.txt
/home/user/workspace/c.txt

In such cases, instead of checking the entire policy every time, caching the results of the Workspace Prefix judgment allows for faster processing.

Policy Epoch

The most important thing to be careful about when using cache in the TLB-Hit Model is outdated judgment results.

If the policy changes and cache results calculated based on the previous policy are still used, security issues may arise.

For example, if the previous policy allowed /tmp/test.txt access,

/tmp/test.txt -> allow

This result can be stored in the cache.

However, if the policy changes later and access to /tmp/test.txt is blocked,

/tmp/test.txt -> deny

If you use the ALLOW result stored in the existing cache as is, the policy change will not be applied.

To solve this problem, you can use the Policy Epoch.

Policy Epoch is the generation number of the policy.

Each time the policy changes, the Epoch value is increased, and the corresponding Epoch is included in the cache key.

key = request + policy_epoch

For example, if the epoch of an existing policy was 1, the cache can be stored as follows.

key   = file_open:/tmp/test.txt:epoch_1
value = allow

If the policy changes and the epoch becomes 2, even the same request will have different keys.

key   = file_open:/tmp/test.txt:epoch_2
value = deny

This helps reduce the issue of incorrect use of cache results created in previous policies in current policies.

Cache Invalidation

Cache Invalidation is the process of making existing cache values unusable.

TLB as well, if the Page Table changes, the existing TLB entry must be invalidated.

For example, if a virtual address was previously mapped to physical address A but later changed to physical address B, using the original TLB entry as is will result in accessing the wrong address.

The same applies to policy cash.

If policies change, resource states change, or process permissions change, the existing cache results must be invalidated.

If Cache Invalidation does not work properly, the following issues may occur.

  • Requests that should have already been blocked continue to be allowed
  • Requests that should have already been allowed continue to be blocked
  • Audit policy changed, but no logs remain
  • Process permission changes are not reflected

Therefore, in the TLB-Hit Model, the accuracy of cache invalidation is just as important as the performance of the cache hit.

L1, L2, and L3 Structures

The TLB-Hit Model can be extended into multiple hierarchical levels.

Just as the CPU cache structure is divided into L1, L2, and L3, the policy decision pipeline can also be divided into several stages.

For example, the following structure can be considered.

L1 Fast Path
    ↓ miss
L2 Semi-Fast Path
    ↓ miss
L3 Slow Path

L1 is the fastest path.

On L1, it only handles exactly the same requests or very simple key-based decisions.

request_key -> decision

L2 is slower than L1 but faster than L3.

On L2, tasks such as prefix matching, resource ID-based cache, and simple policy table lookups can be performed.

L3 is the slowest path.

On L3, you can perform tasks such as comprehensive policy evaluation, complex condition checks, detailed log generation, and user-space integration.

The purpose of this structure is to handle most repetitive requests on L1 or L2, and send only truly complex or new requests to L3.

TLB-Hit Model in eBPF Policy Implementation

The TLB-Hit Model can also be used for eBPF-based policy enforcement.

With eBPF LSM, you can check policies in kernel paths such as file access, command execution, and network connections.

For example, if there is a hook like the following

bprm_check_security
file_open
file_permission
socket_connect

Each Hook can be called very frequently within the system.

If you check the entire policy for every Hook call, the overhead can increase.

Therefore, by applying the TLB-Hit Model, recurring requests can be quickly processed as cache hits, and only new or complex requests can be forwarded to a slower policy evaluation path.

For example, if file read requests occur repeatedly,

file_permission:/home/user/workspace/a.txt:read

The first approach examines the entire policy.

L1 miss
L2 miss
L3 policy evaluation
decision = allow

After that, the results are saved in the cache.

cache[file_permission:/home/user/workspace/a.txt:read] = allow

If the same request comes in again, it is processed directly on L1.

L1 hit
decision = allow

This reduces the recurring cost of policy decisions in the kernel path.

Differences Between the TLB-Hit Model and Simple Caching

The TLB-Hit Model is a bit different from simply using cache.

Simple caching focuses on saving and reusing results.

In contrast, the TLB-Hit Model is closer to designing the entire system’s execution path around Hit.

In other words, the important thing is not to add a single cache data structure, but to design the system so that most requests end on a fast path.

  • The Fast Path should be short and predictable.
  • The Slow Path must handle complex decisions.
  • A key design that can increase the hit rate is necessary.
  • Safe invalidation must be possible when policy changes occur.
  • Even if a miss occurs, the entire system must operate stably.

In this respect, the TLB-Hit Model can be seen as a model that considers both performance optimization and reliability design.

Summary

The TLB-Hit Model is a performance-optimized model derived from the TLB operation of CPU.

TLB caches the result of converting virtual addresses to physical addresses, and omits the Page Table Walk when the same address conversion request comes in again.

If the conversion information is in TLB, it is a TLB Hit; if it is absent, it is a TLB Miss.

The TLB-Hit Model generalizes this structure, processing repetitive requests on a fast path and handling only new or complex requests on a slow path.