BPF LRU Per-CPU Hash Map

  • BPF LRU per-CPU hash map(BPF_MAP_TYPE_LRU_PERCPU_HASH): BPF map with LRU eviction and per-CPU value storage methods applied to the hash map structure.
  • Because the BPF program is executed inside the kernel, general userspace data structures cannot be used as is.
    • Therefore, in order to save the state in the BPF program, share data with user space, or cache repeatedly queried values, you must use the BPF map.
  • BPF_MAP_TYPE_LRU_PERCPU_HASH stores data as key-value pairs, keeps a separate value for each CPU, and automatically evicts entries that have not been used recently when the map is full.

In other words, BPF LRU per-CPU hash map is a map that combines the following three concepts.

  • Hash map
  • LRU
  • Per-CPU map

BPF Map

BPF map is an internal kernel data structure used by the BPF program and user space to exchange data.

Because the BPF program runs within the kernel, it cannot freely use general global variables or dynamic memory allocation.

Therefore, when the state needs to be saved while the BPF program is running, or when a user space program needs to read the results of the BPF program, the BPF map is used.

BPF map is usually used for the following purposes.

  • Save packet counter
  • Store state by process
  • Save policy information
  • Save event statistics
  • save cache
  • BPF Data sharing between program and user space

For example, if you want to store whether access to a specific PID is allowed, you can set PID as the key and save whether to allow access as the value.

key: pid
value: decision

The BPF program can retrieve the policy decision result for the corresponding PID by querying the map every time the hook is executed.

Hash Map

Hash map is a data structure that stores values based on keys.

BPF to BPF_MAP_TYPE_HASH is a map that can be used as a general key-value storage.

For example, data can be stored in the following format:

key: 1000
value: 1

Here, key is 1000 and value is 1.

In BPF hash map, key and value can be created not only with simple integers but also with struct.

For example, in the policy cache, the key can be configured as follows.

struct cache_key {
    __u32 pid;
    __u32 resource_hash;
};

In this way, rather than simply judging by PID, you can use PID and resource hash together as one key.

In other words, BPF hash map can be viewed as a data structure used to quickly query the status of a specific key within the BPF program.

Per-CPU Map

Per-CPU map is a BPF map that has a separate value storage space for each CPU.

In a general hash map, there is one value for one key.

key -> value

However, in the per-CPU hash map, there is a separate value for each key CPU.

key -> value for CPU 0
key -> value for CPU 1
key -> value for CPU 2
key -> value for CPU 3

In other words, even if the same key is searched, the value slot accessed may vary depending on CPU where the BPF program is currently running.

By separating the values for each CPU like this, you can reduce the situation where multiple CPU are modifying the same memory area at the same time.

In a general map, a race condition may occur if multiple CPU modifies the same value at the same time.

For example, if several CPU increase the same counter at the same time, synchronization such as atomic operation or spin lock may be necessary to safely update the value.

However, in the per-CPU map, the value space is separated for each CPU, so only the current value of CPU needs to be modified.

Therefore, it is advantageous in terms of performance in write-heavy situations.

However, per-CPU map must have a separate value space equal to the number of CPU.

Therefore, if the number of CPU is large and the value size is large, memory usage increases.

In other words, per-CPU map is a structure that uses more memory instead of reducing synchronization costs.

LRU

LRU is an abbreviation for Least Recently Used.

LRU is a method that removes the longest unused data first.

This is one of the policies frequently used in caches, and is used when managing a limited size of storage space.

For example, if the maximum number of map entries is 3, data can be entered as follows.

A
B
C

In this state, if new data D needs to be inserted, but the map is already full, the oldest unused entry among the existing data is removed and D is inserted.

B
C
D

At this time, if the removed entry is A, it can be said that A was the entry that was not used the longest.

BPF LRU hash map operates similarly.

If you try to insert a new key when the maximum number of entries set by max_entries is reached, the kernel removes one of the existing entries and inserts a new entry according to the LRU policy.

BPF_MAP_TYPE_LRU_HASH

BPF_MAP_TYPE_LRU_HASH adds LRU eviction to a standard BPF hash map.

The basic hash map may fail if you try to insert a new entry when the map is full.

However, in the LRU hash map, when you try to insert a new entry when the map is full, you can secure space by removing entries that have not been used for a long time.

That is, BPF_MAP_TYPE_LRU_HASH has the following characteristics.

  • Data is stored in key-value format.
  • The maximum size of map is set to max_entries.
  • When the map is full, entries are removed according to the LRU policy.
  • value is one value shared by all CPU.

In the general LRU hash map, multiple CPU can see the same value.

Therefore, when multiple CPU modify the same entry at the same time, synchronization or atomic operations must be considered.

BPF_MAP_TYPE_LRU_PERCPU_HASH

BPF_MAP_TYPE_LRU_PERCPU_HASH combines an LRU hash map with a per-CPU hash map.

In other words, data is stored in key-value format like a hash map, and when the map is full, entries are removed according to the LRU policy, and values are separated by CPU.

To summarize, it is as follows.

  • Data is stored in key-value format.
  • The value exists separately for each CPU.
  • When the map is full, unused entries are removed using the LRU policy.
  • When bpf_map_lookup_elem() is called in the BPF program, the value slot of the current CPU is accessed.
  • When bpf_map_update_elem() is called in the BPF program, the value slot of the current CPU is accessed.

For example, if you search the same key in CPU 0, you will get the value of CPU 0, and if you search the same key in CPU 1, you will get the value of CPU 1.

key A
    CPU 0 value
    CPU 1 value
    CPU 2 value
    CPU 3 value

This structure is useful when storing rapidly updated data independently in each CPU.

Differences Between LRU_HASH and LRU_PERCPU_HASH

BPF_MAP_TYPE_LRU_HASH and BPF_MAP_TYPE_LRU_PERCPU_HASH both support LRU eviction.

However, the way the value is stored is different.

  • BPF_MAP_TYPE_LRU_HASH: One value per key.
  • BPF_MAP_TYPE_LRU_PERCPU_HASH: Stores a separate value for each CPU under one key.

For example, if the key is A, BPF_MAP_TYPE_LRU_HASH has the following structure.

A -> value

By contrast, BPF_MAP_TYPE_LRU_PERCPU_HASH has the following structure.

A -> CPU 0 value
A -> CPU 1 value
A -> CPU 2 value
A -> CPU 3 value

Therefore, if all CPU must share the same value, BPF_MAP_TYPE_LRU_HASH may be more appropriate.

Conversely, BPF_MAP_TYPE_LRU_PERCPU_HASH is more suitable when you want to maintain independent statistics or caches for each CPU.

BPF_F_NO_COMMON_LRU

The part that is easy to confuse when understanding the LRU hash map is BPF_F_NO_COMMON_LRU.

The LRU lists are not necessarily separated completely by CPU merely because the map type is BPF_MAP_TYPE_LRU_PERCPU_HASH.

Basically, LRU map can use the common LRU list.

The BPF_F_NO_COMMON_LRU flag requests per-CPU LRU lists.

To summarize, it is as follows.

BPF_MAP_TYPE_LRU_HASH
No BPF_F_NO_COMMON_LRU -> Global LRU, global value
There is BPF_F_NO_COMMON_LRU -> Per-CPU LRU, global value

BPF_MAP_TYPE_LRU_PERCPU_HASH
No BPF_F_NO_COMMON_LRU -> Global LRU, per-CPU value
There is BPF_F_NO_COMMON_LRU -> Per-CPU LRU, per-CPU value

What is important here is that the range of map type and LRU list are different concepts.

In BPF_MAP_TYPE_LRU_PERCPU_HASH, “per-CPU” means that values are separated by CPU.

By contrast, BPF_F_NO_COMMON_LRU controls whether the LRU list is shared or separated by CPU.

Therefore, BPF_MAP_TYPE_LRU_PERCPU_HASH and BPF_F_NO_COMMON_LRU do not mean the same thing.

Map Declaration

In libbpf CO-RE style, a BPF_MAP_TYPE_LRU_PERCPU_HASH map can be declared as follows.

#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>

struct cache_key {
    __u32 pid;
    __u32 resource_hash;
};

struct cache_value {
    __u64 decision;
    __u64 timestamp;
};

struct {
    __uint(type, BPF_MAP_TYPE_LRU_PERCPU_HASH);
    __uint(max_entries, 8192);
    __uint(map_flags, BPF_F_NO_COMMON_LRU);
    __type(key, struct cache_key);
    __type(value, struct cache_value);
} decision_cache SEC(".maps");

The above map has the following meaning.

  • Map type is BPF_MAP_TYPE_LRU_PERCPU_HASH.
  • The maximum number of entries is 8192.
  • The key is struct cache_key.
  • value is struct cache_value.
  • The value is separated by CPU.
  • LRU list is also separated by CPU due to BPF_F_NO_COMMON_LRU.

This form can be used to cache high-frequency policy decisions or to store CPU-local statistics.

Lookup Operation

When looking up a map in the BPF program, use the bpf_map_lookup_elem() helper.

static __always_inline int lookup_decision(struct cache_key *key)
{
    struct cache_value *value;

    value = bpf_map_lookup_elem(&decision_cache, key);
    if (!value)
        return -1;

    return value->decision;
}

When bpf_map_lookup_elem() is called on a BPF_MAP_TYPE_LRU_PERCPU_HASH map, it looks up the value slot for the current CPU.

In other words, even if the same key is searched at CPU 0, the value of CPU 0 is retrieved, and when searched at CPU 1, the value of CPU 1 is retrieved.

For this reason, when using per-CPU map, you should not think that “since it is the same key, the same value always comes out.”

The value may vary depending on the currently running CPU.

Update Behavior

When entering or updating values in the map in the BPF program, use the bpf_map_update_elem() helper.

static __always_inline int update_decision(struct cache_key *key, __u64 decision)
{
    struct cache_value value = {
        .decision = decision,
        .timestamp = bpf_ktime_get_ns(),
    };

    return bpf_map_update_elem(&decision_cache, key, &value, BPF_ANY);
}

BPF_ANY creates a new key if it does not exist, and updates the existing value if the key already exists.

BPF_NOEXIST is created only when there is no key.

BPF_EXIST updates only when the key already exists.

BPF_ANY     -> create or update
BPF_NOEXIST -> create only
BPF_EXIST   -> update only

In LRU map, update can be connected to eviction.

If the map is not full yet, just add a new entry.

However, if the map has reached max_entries, one of the existing entries must be removed to add a new entry.

At this time, the LRU policy is used.

Delete Operation

When deleting an entry in the BPF program, use the bpf_map_delete_elem() helper.

static __always_inline int delete_decision(struct cache_key *key)
{
    return bpf_map_delete_elem(&decision_cache, key);
}

Deletion is performed on a key-by-key basis.

Therefore, even if it is a map with per-CPU value, if you delete the key, the entry linked to that key is removed.

In other words, it can be understood that the key itself is removed rather than the value of a specific CPU being deleted separately.

User-Space Access

When searching the per-CPU map in user space, you must think differently than when searching inside the BPF program.

Inside the BPF program, the value slot of CPU is currently accessed.

However, when reading the per-CPU map in user space, the values for each CPU must be handled together.

For example, if there are 4 CPU, the following value array must be read for one key in user space.

value[0] -> CPU 0 value
value[1] -> CPU 1 value
value[2] -> CPU 2 value
value[3] -> CPU 3 value

Therefore, if you store a value such as counter, you must add up all values for each CPU in user space to obtain the total value.

total = value[0] + value[1] + value[2] + value[3]

Because of this structure, per-CPU map is fast inside the BPF program, but the process of reading and interpreting values in user space can become a little more complicated.

Memory Structure

BPF_MAP_TYPE_LRU_PERCPU_HASH uses more memory than a regular hash map because it stores a value for each CPU.

A typical hash map stores only one value for one key.

key -> value

However, per-CPU hash map stores as many values as CPU for one key.

key -> value[CPU count]

For example, if the value size is 16 bytes and there are 8 CPU, approximately 128 bytes of value storage space are required for one key.

16 * 8 = 128

In addition, kernel internal metadata required for hash map entry management and LRU list management costs are also added.

Therefore, if max_entries is set large and used in an environment with a large number of CPU, memory usage may increase rapidly.

In other words, per-CPU map is a structure that uses more memory to achieve performance.

LRU Eviction Process

LRU eviction is the process of removing existing entries to add new entries when the map is full.

In a typical hash map, if the map is full, new entries cannot be inserted and may fail.

However, in the LRU hash map, you can remove entries that have not been used for a long time and add new entries.

The flow is roughly as follows.

  1. BPF program updates the new key.
  2. Check if there is empty space in map.
  3. If there is empty space, add the entry as is.
  4. If there is no empty space, candidate LRU is searched.
  5. Remove long unused entries.
  6. Insert a new entry in the removed space.

However, the LRU implementation inside the kernel should not be considered to operate with only a simple linked list.

Structures such as CPU-local state, global list, and batch processing can be used together to reduce performance and lock contention.

Therefore, it is appropriate to understand that BPF LRU map’s LRU is a structure that considers both performance and approximate LRU properties in the kernel environment, rather than a structure that perfectly sorts and manages all access orders like a general userspace LRU cache.

Global LRU and Per-CPU LRU

In the LRU map, the LRU list can be managed globally or by CPU.

Global LRU is a method in which all CPU share one LRU list.

CPU 0
CPU 1
CPU 2
CPU 3
  -> Global LRU

This method is easy to select entries that have not been used for a long time from the overall map perspective.

However, because multiple CPU use one LRU list together, contention may occur.

Per-CPU LRU is a method of having a separate LRU list for each CPU.

CPU 0 -> LRU 0
CPU 1 -> LRU 1
CPU 2 -> LRU 2
CPU 3 -> LRU 3

This method can reduce contention by CPU.

However, because the LRU list of each CPU is separated, a situation may arise where one CPU has insufficient space, but the list of another CPU has space.

In other words, per-CPU LRU may be advantageous in terms of performance, but it is difficult to say that the space of the entire map is always utilized equally.

BPF_F_NO_COMMON_LRU Precautions

When BPF_F_NO_COMMON_LRU is used, the LRU lists are separated by CPU.

At this time, the LRU node cannot freely move between different LRU lists.

Therefore, if the entry pressure increases in the LRU list of a specific CPU, eviction occurs in the list of CPU.

Conversely, even if there is free space in the list on the other CPU side, the method of directly retrieving and using that free space may be limited.

BPF_F_NO_COMMON_LRU reduces contention for performance, but introduces a trade-off in overall space utilization.

To summarize, it is as follows.

  • Global LRU is good to manage from the overall map perspective.
  • Per-CPU LRU is good for reducing contention between CPU.
  • Per-CPU LRU may have spatial deviations per CPU.
  • BPF_F_NO_COMMON_LRU does not make values per-CPU; it makes the LRU lists per-CPU.

Summary

BPF LRU per-CPU hash map is It means BPF_MAP_TYPE_LRU_PERCPU_HASH

This map is the BPF map, which combines the hash map, LRU, and per-CPU value storage methods.

Because it is a Hash map, data is stored in key-value format, and because it is a LRU map, entries that have not been used for a long time are automatically removed when the map is full.

Also, because it is a per-CPU map, there is a separate value space for each CPU key.