Dropping eBPF CPU Cost by About 90% With Memoization (Not AI Gen) :: nathan naveen>
nathannaveen.dev
BlogLeetcodeAbout
5 minutes
09/11/2026Dropping eBPF CPU Cost by About 90% With Memoization (Not AI Gen)My brother and I spent a lot of time designing our eBPF security agent to be really fast from the ground up, but recently we discovered we could make it much faster using memoization!A couple of weeks ago, I profiled the eBPF code and found that the most expensive part of the protection isn’t actually enforcing a policy (allow/deny), but figuring out which policy applies to a given file open.Our policies are path based, so our eBPF leverages an LSM hook that triggers on file open. We then reconstruct the path, walk up parent dentries, and check whether the file or any ancestor directory has a matching policy. While this works, it isn’t performant, and we end up repeating much of the work for files we have already seen (for example, database accesses that repeatedly reaccess file paths).So, we cache which policy applies for each inode. This dropped our kernel CPU cost by about 90%.Additionally, we recently open sourced our repo, so everything in this blog post can be found at https://github.com/bomfather/agent.The ProblemBefore the cache, every file open would walk through the entire path. So the flow would look like this:Get the file path.Walk up the file path with dentries.At each level, check whether a policy exists for the path.Then combine the results to get a final policy, which we can use to decide whether to allow or deny.This works, but if the same file is opened multiple times or multiple files in the same subtree are opened, we have to repeat these steps for each file.For example: In Postgres, if we only want Postgres to be able to touch /var/lib/postgres, we can have this example policy:policies:
- executable: "filepath = /usr/lib/postgresql/16/bin/postgres"
can_access_dirs:
- "/var/lib/postgres:read"
Then Postgres retrieves files from var/lib/postgres/data/base/123, var/lib/postgres/data/base/234, and var/lib/postgres/data/base/345. We would have to walk the entire path of dentries for each of these file accesses, which is really inefficient.For the rest of this blog post, I’ll call this inefficient path walk “the slow path.”What’s in the Cache?Our solution is to use a cache. But we need to make sure the cache isn’t heavy and that it’s safe to reuse cached items.We were thinking of using dentries, but dentries are pointers, and pointers can’t be stored inside eBPF maps. If we wanted to use dentries, we could store the dentries’ contents in a struct and use that struct as the map key, but it would be a pretty heavy struct.So instead, we decided to use an inode based cache. Our cache key has three fields: the mount namespace ID, the mount ID, and the inode number.We can’t cache the inode by itself because inode numbers are unique to a specific mount tree (so if a policy covers multiple mount trees, inodes could overlap). The mount ID helps us identify which mounted tree we observed the file through. The mount namespace ID also prevents us from using cached entries in a different namespace.The cache value has two parts: an access_index and a cache state. We store our policies as bitmasks for space efficiency, and the access_index is the bit position for the path policy (https://nathannaveen.dev/posts/optimizing-ebpf-policies-for-speed-and-space/).So, our cache, along with the keys and values, looks something like this:#define INODE_POLICY_CACHE_NO_POLICY 0
#define INODE_POLICY_CACHE_ACCESS_INDEX 1
#define INODE_POLICY_CACHE_GLOBAL_READ_ONLY 2
#define INODE_POLICY_CACHE_ACCESS_INDEX_AND_GLOBAL_RO 3

struct inode_cache_key {
u64 mntns_id;
u64 mount_id;
u64 inode;
};

struct inode_policy_cache_value {
u32 access_index;
u8 state;
};

struct {
__uint(type, BPF_MAP_TYPE_LRU_HASH);
__uint(max_entries, 10000);
__type(key, struct inode_cache_key);
__type(value, struct inode_policy_cache_value);
} bomfather_inode_policy_cache SEC(".maps");
Now with the cache, our flow looks something like this:We need to build the cache key.We can look up the key in the LRU hash map.If there is a hit, we can enforce the file open based on the cached result.If there is a miss, we can do the slow path and store the result in the cache.Performance ChangesIn our benchmark tests, we opened the same file 200,000 times to analyze performance; the cache reduced kernel cycles from 28 billion to 3.03 billion. Without the cache, our tail_call_security_check appeared on the stack 89.2%, is_restricted_filepath 81.9%, and path_check_callback 63.7% of the time.In the flamegraphs below, we can see that with the cache, the expense from path traversal pretty much disappears after the first lookup. For example, is_restricted_filepath and path_check_callback each shrink to roughly 0.02%, which is small enough to effectively disappear from the graph.Before (without cache):After (with cache):We profiled the kernel CPU with perf using the cycles:k event. This measures kernel side CPU cost during file opens.Edge CasesOne thing we had to account for with this cache is that multiple paths can share a single inode. Hardlinks are the easiest example; with a hardlink, two different paths can share the same inode. This is a big problem because accurate results matter more than cache performance.Our solution is more of a workaround than a real solution. Inodes have a link count (i_nlink) that tells us how many paths point to the inode; we can read it, and if it is greater than 1, we don’t use that cache entry and fall back to the slow path.if (BPF_CORE_READ_INTO(&nlink, inode, i_nlink)) {
return false;
}

if (nlink != 1) {
inode_cache_stats_inc(INODE_CACHE_STATS_SKIPS_NLINK);
return false;
}
This is a trade off since we are giving up some cache coverage, but I don’t think it is too big a deal because having an accurate cache is most important.Final ThoughtsIn the end, this was a really fun thing to work on since I had to work through multiple different ideas for the cache until I landed on this.I am also pretty happy the cache is entirely internal, so a user’s policy doesn’t need to change for the agent to speed up!
eBPFOptimizing eBPF Policies for Speed and Space (Not AI Gen)
→

The motivation behind the work presented by Nathan Naveen was to drastically reduce the CPU cost incurred by an eBPF security agent, achieving a reduction of approximately 90 percent through the implementation of memoization. The fundamental inefficiency resided in the process of policy enforcement, specifically when handling path-based policies that required traversing the file system hierarchy for every file open event. The original method necessitated walking the entire file path through parent directories at each access to determine applicable policies, leading to redundant operations when the same files or files within the same directory subtree were accessed repeatedly. This inefficient path traversal, termed the slow path, consumed significant kernel CPU cycles.

The proposed solution involved caching the policy determination results based on inode information to bypass the repetitive path walking. Since storing file system dentries directly in eBPF maps was deemed impractical due to the overhead of storing large structures, the authors opted for an inode-based caching mechanism. The cache key is constructed using three critical fields: the mount namespace ID, the mount ID, and the inode number. These components are essential because inode numbers are specific to a particular mount tree, and the mount ID helps delineate which mounted tree was observed, ensuring that cached entries are logically isolated across different filesystem contexts. The cached value stores the necessary information, including an access index and a state indicator, with policies being stored efficiently using bitmasks for space optimization.

The operational flow with this cache is designed to prioritize cache lookups. Upon an event, the system first constructs the necessary cache key and checks for a hit in the cache. If a hit occurs, the file open decision is instantly enforced using the cached result. If a miss occurs, the system executes the original slow path to correctly determine the policy and then stores this result in the cache for future reuse. This approach ensures that the costly path traversal is performed only once per unique file access pattern.

Performance benchmarking demonstrated a substantial improvement. When testing with repeated file accesses, which involved opening the same file 200,000 times, the memoization introduced a massive reduction in kernel overhead. The cache effectively reduced kernel cycles from twenty-eight billion to approximately three point zero three billion. Furthermore, the analysis of flamegraphs indicated that the expense associated with path traversal and policy checks, such as is_restricted_filepath and path_check_callback, diminished significantly, shrinking to around two percent or less. This demonstrates that the overhead associated with path traversal is almost entirely eliminated after the initial cache lookup.

A critical consideration addressed by the authors was handling edge cases, particularly the scenario involving hardlinks, where multiple file paths can reference the same inode. Since accurate policy enforcement is paramount, caching must not compromise correctness. To resolve this, the solution leverages the inode link count (i_nlink), which indicates the number of paths pointing to a specific inode. If the link count is greater than one, indicating multiple paths share the inode, the cache entry is bypassed, and the system reverts to the slow path for the access. This trade-off sacrifices some cache coverage for guaranteed accuracy in memory access control decisions. The authors concluded that maintaining cache accuracy is more important than maximizing cache coverage, justifying the decision to forgo caching for shared inode entries. The internal nature of the cache further streamlined the implementation, as external policy changes would not necessitate modifications to the agent itself.